00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef __CS_BITSET_H__
00020 #define __CS_BITSET_H__
00021
00025 #include <stdlib.h>
00026 #include <string.h>
00027
00029 #define BITS_PER_BYTE 8
00030
00031 #define MAX_BYTE_VALUE 0xff
00032
00033
00034 #if defined (PROC_X86) && defined (COMP_GCC)
00035 # define BIT_SET(bits,index) \
00036 asm ("bts %1,%0" : : "o" (*bits), "r" (index))
00037 # define BIT_RESET(bits,index) \
00038 asm ("btr %1,%0" : : "o" (*bits), "r" (index))
00039 # define BIT_GET(bits,index) \
00040 ({ bool result; \
00041 asm ("bt %2,%1\nsetc %%al" : "=a" (result) : "o" (*bits), "r" (index)); \
00042 result; })
00043 #else
00044 # define BIT_SET(bits,index) \
00045 bits [index / BITS_PER_BYTE] |= (1 << (index % BITS_PER_BYTE))
00046 # define BIT_RESET(bits,index) \
00047 bits [index / BITS_PER_BYTE] &= ~(1 << (index % BITS_PER_BYTE))
00048 # define BIT_GET(bits,index) \
00049 !!(bits [index / BITS_PER_BYTE] & (1 << (index % BITS_PER_BYTE)))
00050 #endif
00051
00060 class csBitSet
00061 {
00062 protected:
00063 unsigned bit_count;
00064 unsigned byte_count;
00065 unsigned char *bits;
00066 public:
00068 csBitSet () : bit_count (0), byte_count (0), bits (NULL)
00069 {
00070 }
00071
00073 csBitSet (unsigned iBitCount) :
00074 bit_count (iBitCount), byte_count (0), bits (NULL)
00075 {
00076 if (iBitCount > 0)
00077 {
00078 byte_count = (iBitCount + BITS_PER_BYTE - 1) / BITS_PER_BYTE;
00079 bits = (unsigned char *)calloc (1, byte_count);
00080 }
00081 }
00082
00084 ~csBitSet ()
00085 { free (bits); }
00086
00088 unsigned GetByteCount () const
00089 { return byte_count; }
00090
00092 unsigned GetBitCount () const
00093 { return bit_count; }
00094
00096 void Resize (unsigned iBitCount)
00097 {
00098 bit_count = iBitCount;
00099 unsigned old_bytes = byte_count;
00100 byte_count = (iBitCount + BITS_PER_BYTE - 1) / BITS_PER_BYTE;
00101 if (byte_count > 0)
00102 {
00103 if (!bits)
00104 bits = (unsigned char *)calloc (1, byte_count);
00105 else
00106 {
00107 bits = (unsigned char *)realloc (bits, byte_count);
00108 if (byte_count > old_bytes)
00109 memset (bits + old_bytes, 0, byte_count - old_bytes);
00110 }
00111 }
00112 else if (bits)
00113 {
00114 free (bits);
00115 bits = NULL;
00116 }
00117 }
00118
00120 unsigned char *GetBits () const
00121 { return bits; }
00122
00124 inline void Reset ()
00125 { memset (bits, 0, byte_count); }
00126
00128 inline void Set ()
00129 { memset (bits, MAX_BYTE_VALUE, byte_count); }
00130
00132 inline void Set (unsigned index)
00133 { BIT_SET (bits, index); }
00134
00136 inline void Set (unsigned index, unsigned count)
00137 {
00138 unsigned char *start = bits + index / BITS_PER_BYTE;
00139 unsigned char smask = MAX_BYTE_VALUE << (index % BITS_PER_BYTE);
00140 unsigned char *end = bits + (index + count) / BITS_PER_BYTE;
00141 unsigned char emask =
00142 MAX_BYTE_VALUE >> (8 - (index + count) % BITS_PER_BYTE);
00143 if (start == end)
00144 *start |= smask & emask;
00145 else
00146 {
00147 *start++ |= smask;
00148 while (start < end)
00149 *start++ = MAX_BYTE_VALUE;
00150 if (emask) *start |= emask;
00151 }
00152 }
00153
00155 inline void Reset (unsigned index)
00156 { BIT_RESET (bits, index); }
00157
00159 inline void Reset (unsigned index, unsigned count)
00160 {
00161 unsigned char *start = bits + index / BITS_PER_BYTE;
00162 unsigned char smask = MAX_BYTE_VALUE >> (8 - index % BITS_PER_BYTE);
00163 unsigned char *end = bits + (index + count) / BITS_PER_BYTE;
00164 unsigned char emask = MAX_BYTE_VALUE << ((index + count) % BITS_PER_BYTE);
00165 if (start == end)
00166 *start &= smask | emask;
00167 else
00168 {
00169 *start++ &= smask;
00170 while (start < end)
00171 *start++ = 0;
00172 if (emask != MAX_BYTE_VALUE) *start &= emask;
00173 }
00174 }
00175
00177 inline bool Get (unsigned index) const
00178 { return BIT_GET (bits, index); }
00179
00181 inline bool operator [] (unsigned index) const
00182 { return Get (index); }
00183
00185 inline csBitSet &operator |= (csBitSet &bs)
00186 {
00187 unsigned sz = MIN (byte_count, bs.byte_count);
00188 uint32 *ldst = (uint32 *)bits;
00189 uint32 *lsrc = (uint32 *)bs.bits;
00190 while (sz >= sizeof (uint32))
00191 {
00192 *ldst++ |= *lsrc++;
00193 sz -= sizeof (uint32);
00194 }
00195 uint8 *bdst = (uint8 *)ldst;
00196 uint8 *bsrc = (uint8 *)lsrc;
00197 while (sz--)
00198 *bdst++ |= *bsrc++;
00199 return *this;
00200 }
00201
00203 inline csBitSet &operator &= (csBitSet &bs)
00204 {
00205 unsigned sz = MIN (byte_count, bs.byte_count);
00206 uint32 *ldst = (uint32 *)bits;
00207 uint32 *lsrc = (uint32 *)bs.bits;
00208 while (sz >= sizeof (uint32))
00209 {
00210 *ldst++ &= *lsrc++;
00211 sz -= sizeof (uint32);
00212 }
00213 uint8 *bdst = (uint8 *)ldst;
00214 uint8 *bsrc = (uint8 *)lsrc;
00215 while (sz--)
00216 *bdst++ &= *bsrc++;
00217 return *this;
00218 }
00219
00224 char *Description() const
00225 {
00226 char *s = new char [bit_count + 1];
00227 char *p = s;
00228 for (unsigned i = 0; i < bit_count; i++)
00229 *p++ = Get(i) ? '1' : '0';
00230 *p = '\0';
00231 return s;
00232 }
00233 };
00234
00235 #endif // __CS_BITSET_H__