CrystalSpace

Public API Reference

Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

bitset.h

Go to the documentation of this file.
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 
00025 #include <stdlib.h>
00026 #include <string.h>
00027 
00029 #define BITS_PER_BYTE   8
00030 
00031 #define MAX_BYTE_VALUE  0xff
00032 
00033 // Processor-dependent macros
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__

Generated for Crystal Space by doxygen 1.2.14