bitset.h
00001 /*
00002 Copyright (C) 2000 by Andrew Zabolotny, <bit@eltech.ru>
00003
00004 This library is free software; you can redistribute it and/or
00005 modify it under the terms of the GNU Library General Public
00006 License as published by the Free Software Foundation; either
00007 version 2 of the License, or (at your option) any later version.
00008
00009 This library is distributed in the hope that it will be useful,
00010 but WITHOUT ANY WARRANTY; without even the implied warranty of
00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
00012 Library General Public License for more details.
00013
00014 You should have received a copy of the GNU Library General Public
00015 License along with this library; if not, write to the Free
00016 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
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 // Processor-dependent macros
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 uint32 *ldst = (uint32 *)bits;
00186 uint32 *lsrc = (uint32 *)bs.bits;
00187 while (sz >= sizeof (uint32))
00188 {
00189 *ldst++ |= *lsrc++;
00190 sz -= sizeof (uint32);
00191 }
00192 uint8 *bdst = (uint8 *)ldst;
00193 uint8 *bsrc = (uint8 *)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 uint32 *ldst = (uint32 *)bits;
00204 uint32 *lsrc = (uint32 *)bs.bits;
00205 while (sz >= sizeof (uint32))
00206 {
00207 *ldst++ &= *lsrc++;
00208 sz -= sizeof (uint32);
00209 }
00210 uint8 *bdst = (uint8 *)ldst;
00211 uint8 *bsrc = (uint8 *)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__
Generated for Crystal Space by doxygen 1.2.5 written by Dimitri van Heesch, ©1997-2000