Jack2  1.9.9
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 * $Id: bitset.h,v 1.2 2005/11/23 11:24:29 letz Exp $
14 */
15 
16 /*
17  * Copyright (C) 2005 Jack O'Quin
18  *
19  * This program is free software; you can redistribute it and/or
20  * modify it under the terms of the GNU General Public License as
21  * published by the Free Software Foundation; either version 2 of the
22  * License, or (at your option) any later version.
23  *
24  * This program is distributed in the hope that it will be useful,
25  * but WITHOUT ANY WARRANTY; without even the implied warranty of
26  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
27  * General Public License for more details.
28  *
29  * You should have received a copy of the GNU General Public License
30  * along with this program; if not, write to the Free Software
31  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
32  */
33 
34 #ifndef __bitset_h__
35 #define __bitset_h__
36 
37 #include <inttypes.h> /* POSIX standard fixed-size types */
38 #include <assert.h> /* `#define NDEBUG' to disable */
39 
40 /* On some 64-bit machines, this implementation may be slightly
41  * inefficient, depending on how compilers allocate space for
42  * uint32_t. For the set sizes I currently need, this is acceptable.
43  * It should not be hard to pack the bits better, if that becomes
44  * worthwhile.
45  */
46 typedef uint32_t _bitset_word_t;
47 typedef _bitset_word_t *bitset_t;
48 
49 #define WORD_SIZE(cardinality) (1+((cardinality)+31)/32)
50 #define BYTE_SIZE(cardinality) (WORD_SIZE(cardinality)*sizeof(_bitset_word_t))
51 #define WORD_INDEX(element) (1+(element)/32)
52 #define BIT_INDEX(element) ((element)&037)
53 
54 static inline void
55 bitset_add(bitset_t set
56  , unsigned int element)
57 {
58  assert(element < set
59  [0]);
60  set
61  [WORD_INDEX(element)] |= (1 << BIT_INDEX(element));
62 }
63 
64 static inline void
65 bitset_copy(bitset_t to_set, bitset_t from_set)
66 {
67  assert(to_set[0] == from_set[0]);
68  memcpy(to_set, from_set, BYTE_SIZE(to_set[0]));
69 }
70 
71 static inline void
72 bitset_create(bitset_t *set
73  , unsigned int cardinality)
74 {
75  *set
76  = (bitset_t) calloc(WORD_SIZE(cardinality),
77  sizeof(_bitset_word_t));
78  assert(*set
79  );
80  *set
81  [0] = cardinality;
82 }
83 
84 static inline void
85 bitset_destroy(bitset_t *set
86  )
87 {
88  if (*set
89  ) {
90  free(*set
91  );
92  *set
93  = (bitset_t) 0;
94  }
95 }
96 
97 static inline int
98 bitset_empty(bitset_t set
99  )
100 {
101  int i;
102  _bitset_word_t result = 0;
103  int nwords = WORD_SIZE(set
104  [0]);
105  for (i = 1; i < nwords; i++) {
106  result |= set
107  [i];
108  }
109  return (result == 0);
110 }
111 
112 static inline int
113 bitset_contains(bitset_t set
114  , unsigned int element)
115 {
116  assert(element < set
117  [0]);
118  return (0 != (set
119  [WORD_INDEX(element)] & (1 << BIT_INDEX(element))));
120 }
121 
122 static inline void
123 bitset_remove(bitset_t set
124  , unsigned int element)
125 {
126  assert(element < set
127  [0]);
128  set
129  [WORD_INDEX(element)] &= ~(1 << BIT_INDEX(element));
130 }
131 
132 #endif /* __bitset_h__ */