bit_array.h

Go to the documentation of this file.

/*
 * $Id: inputevt.h 10580 2006-03-14 22:58:17Z cbiere $
 *
 * Copyright (c) 2006, Christian Biere
 *
 *----------------------------------------------------------------------
 * This file is part of gtk-gnutella.
 *
 *  gtk-gnutella is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  gtk-gnutella is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with gtk-gnutella; if not, write to the Free Software
 *  Foundation, Inc.:
 *      59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *----------------------------------------------------------------------
 */

#ifndef _bit_array_h_
#define _bit_array_h_

#include "common.h"

/*
 * Functions for handling arrays of bits. On BSD systems, the macros from
 * <bitstring.h> could be used for better efficiency. So far, the following
 * implementation does not eliminate loop overhead by handling all bits
 * of a "guchar" at once where possible.
 */

typedef unsigned long bit_array_t;

#if LONG_MAX == 0x7fffffffL
#if CHAR_BIT == 8
#define BIT_ARRAY_BITSHIFT  (2 + 3)
#elif CHAR_BIT == 16
#define BIT_ARRAY_BITSHIFT  (2 + 4)
#else
#error "Unsupported size of char"
#endif  /* CHAR_BIT */
#elif (ULONG_MAX >> 31) > 0xffffffffUL
#if CHAR_BIT == 8
#define BIT_ARRAY_BITSHIFT  (3 + 3)
#elif CHAR_BIT == 16
#define BIT_ARRAY_BITSHIFT  (3 + 4)
#else
#error "Unsupported size of char"
#endif  /* CHAR_BIT */
#endif  /* LONG_MAX */

#define BIT_ARRAY_BITSIZE (CHAR_BIT * sizeof(bit_array_t))
#define BIT_ARRAY_BITMASK (BIT_ARRAY_BITSIZE - 1)
#define BIT_ARRAY_WORD(base, i) base[(i) >> BIT_ARRAY_BITSHIFT]
#define BIT_ARRAY_BIT(base, i) (1UL << ((i) & BIT_ARRAY_BITMASK)) 

#define BIT_ARRAY_SIZE(n) \
    ((n) / (CHAR_BIT * sizeof(bit_array_t)) + \
     ((n) % (CHAR_BIT * sizeof(bit_array_t)) ? 1 : 0))

 #define BIT_ARRAY_BYTE_SIZE(n) (BIT_ARRAY_SIZE(n) * sizeof (bit_array_t))

static inline bit_array_t *
bit_array_realloc(bit_array_t *base, size_t n)
{
    size_t size;

    STATIC_ASSERT(0 == (BIT_ARRAY_BITSIZE & BIT_ARRAY_BITMASK));
    
    size = BIT_ARRAY_BYTE_SIZE(n);
    return g_realloc(base, size);
}


static inline void
bit_array_set(bit_array_t *base, size_t i)
{
    BIT_ARRAY_WORD(base, i) |= BIT_ARRAY_BIT(base, i);
}

static inline void 
bit_array_clear(bit_array_t *base, size_t i)
{
    BIT_ARRAY_WORD(base, i) &= ~BIT_ARRAY_BIT(base, i);
}

static inline gboolean
bit_array_flip(bit_array_t *base, size_t i)
{
    return BIT_ARRAY_WORD(base, i) ^= BIT_ARRAY_BIT(base, i);
}

static inline gboolean
bit_array_get(const bit_array_t *base, size_t i)
{
    return 0 != (BIT_ARRAY_WORD(base, i) & BIT_ARRAY_BIT(base, i));
}

static inline void 
bit_array_clear_range(bit_array_t *base, size_t from, size_t to)
{
    size_t i;
    
    g_assert(from <= to);

    for (i = from; i <= to; /* NOTHING */) {
        if (0 == (i & BIT_ARRAY_BITMASK)) {
            size_t n = (to - i) >> BIT_ARRAY_BITSHIFT;

            if (n != 0) {
                size_t j = i >> BIT_ARRAY_BITSHIFT;

                i += n * BIT_ARRAY_BITSIZE;
                do {
                    base[j++] = 0;
                } while (--n != 0);
                continue;
            }
        }
        bit_array_clear(base, i++);
    }
}

static inline void 
bit_array_set_range(bit_array_t *base, size_t from, size_t to)
{
    size_t i;
    
    g_assert(from <= to);

    for (i = from; i <= to; /* NOTHING */) {
        if (0 == (i & BIT_ARRAY_BITMASK)) {
            size_t n = (to - i) >> BIT_ARRAY_BITSHIFT;

            if (n != 0) {
                size_t j = i >> BIT_ARRAY_BITSHIFT;

                i += n * BIT_ARRAY_BITSIZE;
                do {
                    base[j++] = (bit_array_t) -1;
                } while (--n != 0);
                continue;
            }
        }
        bit_array_set(base, i++);
    }
}

static inline size_t
bit_array_first_clear(const bit_array_t *base, size_t from, size_t to)
{
    size_t i;

    g_assert(from <= to);

    for (i = from; i <= to; i++) {
        if (!bit_array_get(base, i))
            return i;
    }

    for (i = from; i <= to; /* NOTHING */) {
        if (0 == (i & BIT_ARRAY_BITMASK)) {
            size_t n = (to - i) >> BIT_ARRAY_BITSHIFT;

            if (n != 0) {
                size_t j = i >> BIT_ARRAY_BITSHIFT;

                while (n-- > 0) {
                    if (base[j++] != (bit_array_t) -1) {
                        bit_array_t value = base[j - 1];
                        while (value & 0x1) {
                            value >>= 1;
                            i++;
                        }
                        return i;
                    }
                    i += BIT_ARRAY_BITSIZE;
                }
            }
        }
        if (!bit_array_get(base, i))
            return i;
        i++;
    }

    return (size_t) -1;
}

#undef BIT_ARRAY_BIT
#undef BIT_ARRAY_BITSIZE
#undef BIT_ARRAY_BITMASK
#undef BIT_ARRAY_BITSHIFT
#undef BIT_ARRAY_WORD

#endif /* _bit_array_h_ */
/* vi: set ts=4 sw=4 cindent: */

---