00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 #ifndef __bitset_h__
00035 #define __bitset_h__
00036
00037 #include <inttypes.h>
00038 #include <assert.h>
00039
00040
00041
00042
00043
00044
00045
00046 typedef uint32_t _bitset_word_t;
00047 typedef _bitset_word_t *bitset_t;
00048
00049 #define WORD_SIZE(cardinality) (1+((cardinality)+31)/32)
00050 #define BYTE_SIZE(cardinality) (WORD_SIZE(cardinality)*sizeof(_bitset_word_t))
00051 #define WORD_INDEX(element) (1+(element)/32)
00052 #define BIT_INDEX(element) ((element)&037)
00053
00054 static inline void
00055 bitset_add(bitset_t set
00056 , unsigned int element)
00057 {
00058 assert(element < set
00059 [0]);
00060 set
00061 [WORD_INDEX(element)] |= (1 << BIT_INDEX(element));
00062 }
00063
00064 static inline void
00065 bitset_copy(bitset_t to_set, bitset_t from_set)
00066 {
00067 assert(to_set[0] == from_set[0]);
00068 memcpy(to_set, from_set, BYTE_SIZE(to_set[0]));
00069 }
00070
00071 static inline void
00072 bitset_create(bitset_t *set
00073 , unsigned int cardinality)
00074 {
00075 *set
00076 = (bitset_t) calloc(WORD_SIZE(cardinality),
00077 sizeof(_bitset_word_t));
00078 assert(*set
00079 );
00080 *set
00081 [0] = cardinality;
00082 }
00083
00084 static inline void
00085 bitset_destroy(bitset_t *set
00086 )
00087 {
00088 if (*set
00089 ) {
00090 free(*set
00091 );
00092 *set
00093 = (bitset_t) 0;
00094 }
00095 }
00096
00097 static inline int
00098 bitset_empty(bitset_t set
00099 )
00100 {
00101 int i;
00102 _bitset_word_t result = 0;
00103 int nwords = WORD_SIZE(set
00104 [0]);
00105 for (i = 1; i < nwords; i++) {
00106 result |= set
00107 [i];
00108 }
00109 return (result == 0);
00110 }
00111
00112 static inline int
00113 bitset_contains(bitset_t set
00114 , unsigned int element)
00115 {
00116 assert(element < set
00117 [0]);
00118 return (0 != (set
00119 [WORD_INDEX(element)] & (1 << BIT_INDEX(element))));
00120 }
00121
00122 static inline void
00123 bitset_remove(bitset_t set
00124 , unsigned int element)
00125 {
00126 assert(element < set
00127 [0]);
00128 set
00129 [WORD_INDEX(element)] &= ~(1 << BIT_INDEX(element));
00130 }
00131
00132 #endif