00001 /// @addtogroup struct 00002 /// @{ 00003 00004 ///////////////////////////////////////////////////////////////////////////// 00005 /// 00006 /// @file bitfield.h 00007 /// 00008 /// This file contains the definition of a bitfield class which works 00009 /// an array of bits. The functionality of this class is very limited 00010 /// and it is optimized for the specific application in the homology 00011 /// computation algorithms. 00012 /// 00013 /// Note that memory allocation and deallocation, 00014 /// as well as remembering the length of the bitfield is the responsibility 00015 /// of the code which uses the bitfield, the class bitfield doesn't take 00016 /// care of these issues. 00017 /// 00018 /// @author Pawel Pilarczyk 00019 /// 00020 ///////////////////////////////////////////////////////////////////////////// 00021 00022 // Copyright (C) 1997-2013 by Pawel Pilarczyk. 00023 // 00024 // This file is part of the Homology Library. This library is free software; 00025 // you can redistribute it and/or modify it under the terms of the GNU 00026 // General Public License as published by the Free Software Foundation; 00027 // either version 2 of the License, or (at your option) any later version. 00028 // 00029 // This library is distributed in the hope that it will be useful, 00030 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00031 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00032 // GNU General Public License for more details. 00033 // 00034 // You should have received a copy of the GNU General Public License along 00035 // with this software; see the file "license.txt". If not, write to the 00036 // Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, 00037 // MA 02111-1307, USA. 00038 00039 // Started in April 1999. Last revision: May 24, 2010. 00040 00041 00042 #ifndef _CHOMP_STRUCT_BITFIELD_H_ 00043 #define _CHOMP_STRUCT_BITFIELD_H_ 00044 00045 #include "chomp/system/config.h" 00046 00047 #include <iostream> 00048 #include <cstdlib> 00049 00050 namespace chomp { 00051 namespace homology { 00052 00053 00054 // classes defined within this header file: 00055 class BitField; 00056 class SetOfBitFields; 00057 00058 /// A lower-case version of the name of a bit field [deprecated]. 00059 typedef BitField bitfield; 00060 00061 /// A lower-case version of the name of a bit field set [deprecated]. 00062 typedef SetOfBitFields bitfieldset; 00063 00064 00065 // -------------------------------------------------- 00066 // ------------------- BitField --------------------- 00067 // -------------------------------------------------- 00068 00069 /// This class defines a bit field that is part of some larger array 00070 /// or that uses an allocated piece of memory. This class may be useful 00071 /// for efficient management of multiple bit fields, or just one bit field. 00072 /// Note the very specific behavior of memory management! 00073 class BitField 00074 { 00075 public: 00076 /// The constructor of an undefined bit field. 00077 BitField (); 00078 00079 /// The destructor which actually does nothing. 00080 ~BitField (); 00081 00082 /// Returns true if the bit field has already been defined, 00083 /// that is, it is bound with some memory piece, or its memory 00084 /// has been allocated. 00085 bool defined () const; 00086 00087 /// Define the bit field as a piece of a larger memory buffer. 00088 /// The memory enough to store the given number of bits 00089 /// (the length of the bit field) will be used. 00090 void define (unsigned char *buf, int_t length); 00091 00092 /// Allocates memory for a bit field. 00093 /// The memory enough to store the given number of bits (the length 00094 /// of the bit field) is allocated with the 'new' operator. 00095 void allocate (int_t length); 00096 00097 /// Releases the memory allocated for the bit field. 00098 /// This must be used if the memory was allocated, because 00099 /// the destructor does not deallocte the memory. 00100 void free (); 00101 00102 /// Sets the given bit to 1. 00103 void set (int_t n); 00104 00105 /// Clears the given bit (sets it to 0). 00106 void clear (int_t n); 00107 00108 /// Tests the given bit. Returns 0 or 1. 00109 int test (int_t n) const; 00110 00111 /// Copies all the bits from the given bitfield. 00112 /// Assumes that both bit fields have the specified length. 00113 /// Note that the bit field itself does not store its length. 00114 void takebits (const BitField &from, int_t length); 00115 00116 /// Clears all the bits in the entire bit field of specified length. 00117 /// Note that the bit field itself does not store its length. 00118 void clearall (int_t length); 00119 00120 /// Finds the first bit that is set to 1, beginning at the given one. 00121 /// Return the number of the bit, or -1 if not found. 00122 /// Note that the bit field itself does not store its length, 00123 /// so this length must be provided as an argument of this function. 00124 int find (int_t after, int_t length) const; 00125 00126 /// Returns the first key for hashing. 00127 /// Note that the bit field itself does not store its length, 00128 /// so this length must be provided as an argument of this function. 00129 int_t hashkey (int_t length) const; 00130 00131 /// Returns the second key for hashing. 00132 /// Note that the bit field itself does not store its length, 00133 /// so this length must be provided as an argument of this function. 00134 int_t hashadd (int_t length) const; 00135 00136 /// Compares two bit fields of the giben length. 00137 /// Returns true if they are the same, false otherwise. 00138 friend bool thesame (const BitField &b1, const BitField &b2, 00139 int_t length); 00140 00141 /// Converts an integer into the bits of a bit field of the given 00142 /// length. The length must not exceed the size of the integer. 00143 friend void int2bits (int bits, int_t length, BitField &field); 00144 00145 /// Converts the bits of a bit field of the given length into 00146 /// an integer. The length must not exceed the size of the integer. 00147 friend int bits2int (const BitField &field, int_t length); 00148 00149 private: 00150 /// The table of 8-bit cells which store the subsequent bits. 00151 /// It is either an address of some allocated memory, or an address 00152 /// of portion of some other memory, for example, allocated 00153 /// collectively for a large number of bit fields. 00154 unsigned char *table; 00155 00156 }; /* BitField */ 00157 00158 // -------------------------------------------------- 00159 00160 inline BitField::BitField () 00161 { 00162 table = NULL; 00163 return; 00164 } /* BitField::BitField */ 00165 00166 inline bool BitField::defined () const 00167 { 00168 return !!table; 00169 } /* BitField::defined */ 00170 00171 inline void BitField::free () 00172 { 00173 delete [] table; 00174 table = NULL; 00175 return; 00176 } /* BitField::free */ 00177 00178 inline BitField::~BitField () 00179 { 00180 return; 00181 } /* BitField::~BitField */ 00182 00183 inline void BitField::set (int_t n) 00184 { 00185 table [n >> 3] |= static_cast<unsigned char> (0x01 << (n & 0x07)); 00186 return; 00187 } /* BitField::set */ 00188 00189 inline void BitField::clear (int_t n) 00190 { 00191 table [n >> 3] &= static_cast<unsigned char> (~(0x01 << (n & 0x07))); 00192 return; 00193 } /* BitField::clear */ 00194 00195 inline int BitField::test (int_t n) const 00196 { 00197 return !!(table [n >> 3] & (0x01 << (n & 0x07))); 00198 } /* BitField::test */ 00199 00200 inline void int2bits (int bits, int_t length, BitField &field) 00201 { 00202 unsigned char *tab = field. table; 00203 if (!tab) 00204 throw "Trying to set values to an undefined bitfield."; 00205 while (length >= 0) 00206 { 00207 *(tab ++) = static_cast<unsigned char> (bits & 0xFF); 00208 bits >>= 8; 00209 length -= 8; 00210 } 00211 return; 00212 } /* int2bits */ 00213 00214 inline int bits2int (const BitField &field, int_t length) 00215 { 00216 const unsigned char *tab = field. table; 00217 if (!tab) 00218 throw "Trying to set values to an undefined bitfield."; 00219 int n = 0; 00220 int shiftvalue = 0; 00221 while (length >= 8) 00222 { 00223 n |= (*(tab ++)) << shiftvalue; 00224 length -= 8; 00225 shiftvalue += 8; 00226 } 00227 const int bitmasks [] = {0x00, 0x01, 0x03, 0x07, 0x0F, 0x1F, 0x3F, 0x7F, 0xFF}; 00228 if (length > 0) 00229 n |= ((*(tab ++)) & bitmasks [length]) << shiftvalue; 00230 return n; 00231 } /* bits2int */ 00232 00233 00234 // -------------------------------------------------- 00235 // ----------------- SetOfBitFields ----------------- 00236 // -------------------------------------------------- 00237 00238 /// This class defines a set of bit fields of the same length 00239 /// which are to be stored in a contiguous piece of memory 00240 /// to avoid multiple memory allocation/deallocation. 00241 /// Each bit field in the set is assigned a value 1 or 0. 00242 /// Hashing is used for quick retrieval of the values of bit fields. 00243 class SetOfBitFields 00244 { 00245 public: 00246 /// The constructor of a set of a fixed maximal number of bit fields, 00247 /// each of the same length. The set is initially empty. 00248 SetOfBitFields (int_t len, int_t maxelem); 00249 00250 /// The destructor. 00251 ~SetOfBitFields (); 00252 00253 /// Adds a bit field to the set. If it already was there then returns 00254 /// its value. If there is no room available for the bit field 00255 /// then returns -1. Otherwise returns 2. 00256 int add (const BitField &b, int value); 00257 00258 /// Returns the value of the given bit field value 00259 /// or return -1 if the bit field is not in the set. 00260 int check (const BitField &b) const; 00261 00262 /// Returns the number of bit fields contained in the set. 00263 int used (void) const; 00264 00265 /// Forgets all the bit fields and deallocates the memory. 00266 void forget (); 00267 00268 private: 00269 /// The number of bit fields that still can be stored. 00270 int avail; 00271 00272 /// The number of bit fields used. 00273 int usedcount; 00274 00275 /// The actual size of the table. 00276 int_t size; 00277 00278 /// The length of bit fields. 00279 int_t length; 00280 00281 /// The table of bit fields. 00282 BitField *bf; 00283 00284 /// The values of bit fields. 00285 BitField values; 00286 00287 /// The memory buffer used for bit fields. 00288 unsigned char *buf; 00289 00290 /// The current position in the buffer. 00291 unsigned char *bufcur; 00292 00293 }; /* class SetOfBitFields */ 00294 00295 // -------------------------------------------------- 00296 00297 inline SetOfBitFields::~SetOfBitFields () 00298 { 00299 if (bf) 00300 delete [] bf; 00301 if (buf) 00302 delete [] buf; 00303 if (length) 00304 values. free (); 00305 return; 00306 } /* SetOfBitFields::~SetOfBitFields */ 00307 00308 inline int SetOfBitFields::used () const 00309 { 00310 return usedcount; 00311 } /* SetOfBitFields::used */ 00312 00313 inline void SetOfBitFields::forget () 00314 { 00315 if (bf) 00316 delete [] bf; 00317 bf = NULL; 00318 if (buf) 00319 delete [] buf; 00320 buf = NULL; 00321 if (length) 00322 values. free (); 00323 length = 0; 00324 size = 0; 00325 avail = 0; 00326 return; 00327 } /* SetOfBitFields::forget */ 00328 00329 00330 } // namespace homology 00331 } // namespace chomp 00332 00333 #endif // _CHOMP_STRUCT_BITFIELD_H_ 00334 00335 /// @} 00336
1.7.2