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
00022 #include <stdlib.h>
00023 #include <string.h>
00024
00026 #define BITS_PER_BYTE 8
00027
00028 #define MAX_BYTE_VALUE 0xff
00029
00030
00031 #if defined (PROC_X86) && defined (COMP_GCC) && !defined(OS_NEXT)
00032 # define BIT_SET(bits,index) \
00033 asm ("bts %1,%0" : : "o" (*bits), "r" (index))
00034 # define BIT_RESET(bits,index) \
00035 asm ("btr %1,%0" : : "o" (*bits), "r" (index))
00036 # define BIT_GET(bits,index) \
00037 ({ bool result; \
00038 asm ("bt %2,%1\nsetc %%al" : "=a" (result) : "o" (*bits), "r" (index)); \
00039 result; })
00040 #else
00041 # define BIT_SET(bits,index) \
00042 bits [index / BITS_PER_BYTE] |= (1 << (index % BITS_PER_BYTE))
00043 # define BIT_RESET(bits,index) \
00044 bits [index / BITS_PER_BYTE] &= ~(1 << (index % BITS_PER_BYTE))
00045 # define BIT_GET(bits,index) \
00046 !!(bits [index / BITS_PER_BYTE] & (1 << (index % BITS_PER_BYTE)))
00047 #endif
00048
00057 class csBitSet
00058 {
00059 protected:
00060 unsigned bit_count;
00061 unsigned byte_count;
00062 unsigned char *bits;
00063 public:
00065 csBitSet () : bit_count (0), byte_count (0), bits (NULL)
00066 {
00067 }
00068
00070 csBitSet (unsigned iBitCount) :
00071 bit_count (iBitCount), byte_count (0), bits (NULL)
00072 {
00073 if (iBitCount > 0)
00074 {
00075 byte_count = (iBitCount + BITS_PER_BYTE - 1) / BITS_PER_BYTE;
00076 bits = (unsigned char *)calloc (1, byte_count);
00077 }
00078 }
00079
00081 ~csBitSet ()
00082 { free (bits); }
00083
00085 unsigned GetByteCount () const
00086 { return byte_count; }
00087
00089 unsigned GetBitCount () const
00090 { return bit_count; }
00091
00093 void Resize (unsigned iBitCount)
00094 {
00095 bit_count = iBitCount;
00096 unsigned old_bytes = byte_count;
00097 byte_count = (iBitCount + BITS_PER_BYTE - 1) / BITS_PER_BYTE;
00098 if (byte_count > 0)
00099 {
00100 if (!bits)
00101 bits = (unsigned char *)calloc (1, byte_count);
00102 else
00103 {
00104 bits = (unsigned char *)realloc (bits, byte_count);
00105 if (byte_count > old_bytes)
00106 memset (bits + old_bytes, 0, byte_count - old_bytes);
00107 }
00108 }
00109 else if (bits)
00110 {
00111 free (bits);
00112 bits = NULL;
00113 }
00114 }
00115
00117 unsigned char *GetBits () const
00118 { return bits; }
00119
00121 inline void Reset ()
00122 { memset (bits, 0, byte_count); }
00123
00125 inline void Set ()
00126 { memset (bits, MAX_BYTE_VALUE, byte_count); }
00127
00129 inline void Set (unsigned index)
00130 { BIT_SET (bits, index); }
00131
00133 inline void Set (unsigned index, unsigned count)
00134 {
00135 unsigned char *start = bits + index / BITS_PER_BYTE;
00136 unsigned char smask = MAX_BYTE_VALUE << (index % BITS_PER_BYTE);
00137 unsigned char *end = bits + (index + count) / BITS_PER_BYTE;
00138 unsigned char emask =
00139 MAX_BYTE_VALUE >> (8 - (index + count) % BITS_PER_BYTE);
00140 if (start == end)
00141 *start |= smask & emask;
00142 else
00143 {
00144 *start++ |= smask;
00145 while (start < end)
00146 *start++ = MAX_BYTE_VALUE;
00147 if (emask) *start |= emask;
00148 }
00149 }
00150
00152 inline void Reset (unsigned index)
00153 { BIT_RESET (bits, index); }
00154
00156 inline void Reset (unsigned index, unsigned count)
00157 {
00158 unsigned char *start = bits + index / BITS_PER_BYTE;
00159 unsigned char smask = MAX_BYTE_VALUE >> (8 - index % BITS_PER_BYTE);
00160 unsigned char *end = bits + (index + count) / BITS_PER_BYTE;
00161 unsigned char emask = MAX_BYTE_VALUE << ((index + count) % BITS_PER_BYTE);
00162 if (start == end)
00163 *start &= smask | emask;
00164 else
00165 {
00166 *start++ &= smask;
00167 while (start < end)
00168 *start++ = 0;
00169 if (emask != MAX_BYTE_VALUE) *start &= emask;
00170 }
00171 }
00172
00174 inline bool Get (unsigned index) const
00175 { return BIT_GET (bits, index); }
00176
00178 inline bool operator [] (unsigned index) const
00179 { return Get (index); }
00180
00182 inline csBitSet &operator |= (csBitSet &bs)
00183 {
00184 unsigned sz = MIN (byte_count, bs.byte_count);
00185 ULong *ldst = (ULong *)bits;
00186 ULong *lsrc = (ULong *)bs.bits;
00187 while (sz >= sizeof (ULong))
00188 {
00189 *ldst++ |= *lsrc++;
00190 sz -= sizeof (ULong);
00191 }
00192 UByte *bdst = (UByte *)ldst;
00193 UByte *bsrc = (UByte *)lsrc;
00194 while (sz--)
00195 *bdst++ |= *bsrc++;
00196 return *this;
00197 }
00198
00200 inline csBitSet &operator &= (csBitSet &bs)
00201 {
00202 unsigned sz = MIN (byte_count, bs.byte_count);
00203 ULong *ldst = (ULong *)bits;
00204 ULong *lsrc = (ULong *)bs.bits;
00205 while (sz >= sizeof (ULong))
00206 {
00207 *ldst++ &= *lsrc++;
00208 sz -= sizeof (ULong);
00209 }
00210 UByte *bdst = (UByte *)ldst;
00211 UByte *bsrc = (UByte *)lsrc;
00212 while (sz--)
00213 *bdst++ &= *bsrc++;
00214 return *this;
00215 }
00216
00221 char *Description() const
00222 {
00223 char *s = new char [bit_count + 1];
00224 char *p = s;
00225 for (unsigned i = 0; i < bit_count; i++)
00226 *p++ = Get(i) ? '1' : '0';
00227 *p = '\0';
00228 return s;
00229 }
00230 };
00231
00232 #endif // __CS_BITSET_H__