Jack2 1.9.6
|
00001 /* 00002 * bitset.h -- some simple bit vector set operations. 00003 * 00004 * This is useful for sets of small non-negative integers. There are 00005 * some obvious set operations that are not implemented because I 00006 * don't need them right now. 00007 * 00008 * These functions represent sets as arrays of unsigned 32-bit 00009 * integers allocated on the heap. The first entry contains the set 00010 * cardinality (number of elements allowed), followed by one or more 00011 * words containing bit vectors. 00012 * 00013 * $Id: bitset.h,v 1.2 2005/11/23 11:24:29 letz Exp $ 00014 */ 00015 00016 /* 00017 * Copyright (C) 2005 Jack O'Quin 00018 * 00019 * This program is free software; you can redistribute it and/or 00020 * modify it under the terms of the GNU General Public License as 00021 * published by the Free Software Foundation; either version 2 of the 00022 * License, or (at your option) any later version. 00023 * 00024 * This program is distributed in the hope that it will be useful, 00025 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00026 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00027 * General Public License for more details. 00028 * 00029 * You should have received a copy of the GNU General Public License 00030 * along with this program; if not, write to the Free Software 00031 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00032 */ 00033 00034 #ifndef __bitset_h__ 00035 #define __bitset_h__ 00036 00037 #include <inttypes.h> /* POSIX standard fixed-size types */ 00038 #include <assert.h> /* `#define NDEBUG' to disable */ 00039 00040 /* On some 64-bit machines, this implementation may be slightly 00041 * inefficient, depending on how compilers allocate space for 00042 * uint32_t. For the set sizes I currently need, this is acceptable. 00043 * It should not be hard to pack the bits better, if that becomes 00044 * worthwhile. 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 /* __bitset_h__ */