jack/bitset.h

   1 /*
   2  * bitset.h -- some simple bit vector set operations.
   3  *
   4  * This is useful for sets of small non-negative integers.  There are
   5  * some obvious set operations that are not implemented because I
   6  * don't need them right now.
   7  *
   8  * These functions represent sets as arrays of unsigned 32-bit
   9  * integers allocated on the heap.  The first entry contains the set
  10  * cardinality (number of elements allowed), followed by one or more
  11  * words containing bit vectors.
  12  *
  13  */
  14
  15 /*
  16  *  Copyright (C) 2005 Jack O'Quin
  17  *
  18  *  This program is free software; you can redistribute it and/or
  19  *  modify it under the terms of the GNU General Public License as
  20  *  published by the Free Software Foundation; either version 2 of the
  21  *  License, or (at your option) any later version.
  22  *
  23  *  This program is distributed in the hope that it will be useful,
  24  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  25  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  26  *  General Public License for more details.
  27  *
  28  *  You should have received a copy of the GNU General Public License
  29  *  along with this program; if not, write to the Free Software
  30  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  31  */
  32
  33 #ifndef __bitset_h__
  34 #define __bitset_h__
  35
  36 #include <inttypes.h>                   /* POSIX standard fixed-size types */
  37 #include <assert.h>                     /* `#define NDEBUG' to disable */
  38
  39 /* On some 64-bit machines, this implementation may be slightly
  40  * inefficient, depending on how compilers allocate space for
  41  * uint32_t.  For the set sizes I currently need, this is acceptable.
  42  * It should not be hard to pack the bits better, if that becomes
  43  * worthwhile.
  44  */
  45 typedef uint32_t _bitset_word_t;
  46 typedef _bitset_word_t *bitset_t;
  47
  48 #define WORD_SIZE(cardinality) (1+((cardinality)+31)/32)
  49 #define BYTE_SIZE(cardinality) (WORD_SIZE(cardinality)*sizeof(_bitset_word_t))
  50 #define WORD_INDEX(element) (1+(element)/32)
  51 #define BIT_INDEX(element) ((element)&037)
  52
  53 static inline void
  54 bitset_add(bitset_t set, unsigned int element)
  55 {
  56         assert(element < set[0]);
  57         set[WORD_INDEX(element)] |= (1 << BIT_INDEX(element));
  58 }
  59
  60 static inline void
  61 bitset_copy(bitset_t to_set, bitset_t from_set)
  62 {
  63         assert(to_set[0] == from_set[0]);
  64         memcpy(to_set, from_set, BYTE_SIZE(to_set[0]));
  65 }
  66
  67 static inline void
  68 bitset_create(bitset_t *set, unsigned int cardinality)
  69 {
  70         *set = (bitset_t) calloc(WORD_SIZE(cardinality),
  71                                  sizeof(_bitset_word_t));
  72         assert(*set);
  73         *set[0] = cardinality;
  74 }
  75
  76 static inline void
  77 bitset_destroy(bitset_t *set)
  78 {
  79         if (*set) {
  80                 free(*set);
  81                 *set = (bitset_t) 0;
  82         }
  83 }
  84
  85 static inline int
  86 bitset_empty(bitset_t set)
  87 {
  88         int i;
  89         _bitset_word_t result = 0;
  90         int nwords = WORD_SIZE(set[0]);
  91         for (i = 1; i < nwords; i++) {
  92                 result |= set[i];
  93         }
  94         return (result == 0);
  95 }
  96
  97 static inline int
  98 bitset_contains(bitset_t set, unsigned int element)
  99 {
 100         assert(element < set[0]);
 101         return (0 != (set[WORD_INDEX(element)] & (1<<BIT_INDEX(element))));
 102 }
 103
 104 static inline void
 105 bitset_remove(bitset_t set, unsigned int element)
 106 {
 107         assert(element < set[0]);
 108         set[WORD_INDEX(element)] &= ~(1<<BIT_INDEX(element));
 109 }
 110
 111 #endif /* __bitset_h__ */