csutil/bitarray.h
Go to the documentation of this file.00001 /* 00002 Copyright (C) 2000 by Andrew Kirmse 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 // A one-dimensional array of bits, similar to STL bitset. 00020 // 00021 // Copyright 2000 Andrew Kirmse. All rights reserved. 00022 // 00023 // Permission is granted to use this code for any purpose, as long as this 00024 // copyright message remains intact. 00025 00026 #ifndef __CS_BITARRAY_H__ 00027 #define __CS_BITARRAY_H__ 00028 00033 #include "csextern.h" 00034 #include "comparator.h" 00035 #include "hash.h" 00036 00037 class csBitArray; 00038 CS_SPECIALIZE_TEMPLATE class csComparator<csBitArray, csBitArray>; 00039 CS_SPECIALIZE_TEMPLATE class csHashComputer<csBitArray>; 00040 00044 class CS_CRYSTALSPACE_EXPORT csBitArray 00045 { 00046 public: 00047 typedef unsigned long store_type; 00048 00049 private: 00050 friend class csComparator<csBitArray, csBitArray>; 00051 friend class csHashComputer<csBitArray>; 00052 enum 00053 { 00054 bits_per_byte = 8, 00055 cell_size = sizeof(store_type) * bits_per_byte 00056 }; 00057 00058 store_type* mpStore; 00059 store_type mSingleWord; // Use this buffer when mLength is 1 00060 size_t mLength; // Length of mpStore in units of store_type 00061 size_t mNumBits; 00062 00064 static size_t GetIndex (size_t bit_num) 00065 { 00066 return bit_num / cell_size; 00067 } 00068 00070 static size_t GetOffset (size_t bit_num) 00071 { 00072 return bit_num % cell_size; 00073 } 00074 00079 store_type const* GetStore() const 00080 { 00081 return mLength <= 1 ? &mSingleWord : mpStore; 00082 } 00083 00088 store_type* GetStore() 00089 { 00090 return mLength <= 1 ? &mSingleWord : mpStore; 00091 } 00092 00094 void Trim() 00095 { 00096 size_t extra_bits = mNumBits % cell_size; 00097 if (mLength > 0 && extra_bits != 0) 00098 GetStore()[mLength - 1] &= ~((~(store_type)0) << extra_bits); 00099 } 00100 00101 public: 00105 class CS_CRYSTALSPACE_EXPORT BitProxy 00106 { 00107 private: 00108 csBitArray &mArray; 00109 size_t mPos; 00110 public: 00112 BitProxy(csBitArray &array, size_t pos): mArray(array), mPos(pos) 00113 {} 00114 00116 BitProxy &operator= (bool value) 00117 { 00118 mArray.Set (mPos, value); 00119 return *this; 00120 } 00121 00123 BitProxy &operator= (const BitProxy &that) 00124 { 00125 mArray.Set (mPos, that.mArray.IsBitSet (that.mPos)); 00126 return *this; 00127 } 00128 00130 operator bool() const 00131 { 00132 return mArray.IsBitSet (mPos); 00133 } 00134 00139 bool Flip() 00140 { 00141 mArray.FlipBit (mPos); 00142 return mArray.IsBitSet (mPos); 00143 } 00144 }; 00145 friend class BitProxy; 00146 00150 csBitArray () : mpStore(0), mSingleWord(0), mLength(0), mNumBits(0) 00151 { 00152 SetSize (0); 00153 } 00154 00158 explicit csBitArray(size_t size) : 00159 mpStore(0), mSingleWord(0), mLength(0), mNumBits(0) 00160 { 00161 SetSize (size); 00162 } 00163 00167 csBitArray (const csBitArray &that) : 00168 mpStore(0), mSingleWord(0), mLength(0), mNumBits(0) 00169 { 00170 *this = that; // Invokes this->operator=(). 00171 } 00172 00174 ~csBitArray() 00175 { 00176 if (mpStore != 0) 00177 delete[] mpStore; 00178 } 00179 00181 size_t GetSize() const 00182 { 00183 return mNumBits; 00184 } 00185 00190 size_t Length () const 00191 { 00192 return GetSize(); 00193 } 00194 00199 void SetLength (size_t newSize) 00200 { 00201 SetSize (newSize); 00202 } 00203 00209 void SetSize (size_t newSize) 00210 { 00211 size_t newLength; 00212 if (newSize == 0) 00213 newLength = 0; 00214 else 00215 newLength = 1 + GetIndex (newSize - 1); 00216 00217 if (newLength != mLength) 00218 { 00219 // Avoid allocation if length is 1 (common case) 00220 store_type* newStore; 00221 if (newLength <= 1) 00222 newStore = &mSingleWord; 00223 else 00224 newStore = new store_type[newLength]; 00225 00226 if (newLength > 0) 00227 { 00228 if (mLength > 0) 00229 { 00230 store_type const* oldStore = GetStore(); 00231 if (newStore != oldStore) 00232 { 00233 memcpy (newStore, oldStore, 00234 (MIN (mLength, newLength)) * sizeof (store_type)); 00235 if (newLength > mLength) 00236 memset(newStore + mLength, 0, 00237 (newLength - mLength) * sizeof (store_type)); 00238 } 00239 } 00240 else 00241 memset (newStore, 0, newLength * sizeof (store_type)); 00242 } 00243 00244 if (mpStore != 0) 00245 delete[] mpStore; 00246 00247 mpStore = newLength > 1 ? newStore : 0; 00248 mLength = newLength; 00249 } 00250 00251 mNumBits = newSize; 00252 Trim(); 00253 } 00254 00255 // 00256 // Operators 00257 // 00258 00260 csBitArray &operator=(const csBitArray &that) 00261 { 00262 if (this != &that) 00263 { 00264 SetSize (that.mNumBits); 00265 memcpy (GetStore(), that.GetStore(), mLength * sizeof(store_type)); 00266 } 00267 return *this; 00268 } 00269 00271 BitProxy operator[] (size_t pos) 00272 { 00273 CS_ASSERT (pos < mNumBits); 00274 return BitProxy(*this, pos); 00275 } 00276 00278 bool operator[] (size_t pos) const 00279 { 00280 return IsBitSet(pos); 00281 } 00282 00284 bool operator==(const csBitArray &that) const 00285 { 00286 if (mNumBits != that.mNumBits) 00287 return false; 00288 00289 store_type const* p0 = GetStore(); 00290 store_type const* p1 = that.GetStore(); 00291 for (unsigned i = 0; i < mLength; i++) 00292 if (p0[i] != p1[i]) 00293 return false; 00294 return true; 00295 } 00296 00298 bool operator != (const csBitArray &that) const 00299 { 00300 return !(*this == that); 00301 } 00302 00304 csBitArray& operator &= (const csBitArray &that) 00305 { 00306 CS_ASSERT (mNumBits == that.mNumBits); 00307 store_type* p0 = GetStore(); 00308 store_type const* p1 = that.GetStore(); 00309 for (size_t i = 0; i < mLength; i++) 00310 p0[i] &= p1[i]; 00311 return *this; 00312 } 00313 00315 csBitArray operator |= (const csBitArray &that) 00316 { 00317 CS_ASSERT (mNumBits == that.mNumBits); 00318 store_type* p0 = GetStore(); 00319 store_type const* p1 = that.GetStore(); 00320 for (size_t i = 0; i < mLength; i++) 00321 p0[i] |= p1[i]; 00322 return *this; 00323 } 00324 00326 csBitArray operator ^= (const csBitArray &that) 00327 { 00328 CS_ASSERT (mNumBits == that.mNumBits); 00329 store_type* p0 = GetStore(); 00330 store_type const* p1 = that.GetStore(); 00331 for (size_t i = 0; i < mLength; i++) 00332 p0[i] ^= p1[i]; 00333 return *this; 00334 } 00335 00337 csBitArray operator~() const 00338 { 00339 return csBitArray(*this).FlipAllBits(); 00340 } 00341 00343 friend csBitArray operator& (const csBitArray &a1, const csBitArray &a2) 00344 { 00345 return csBitArray(a1) &= a2; 00346 } 00347 00349 friend csBitArray operator | (const csBitArray &a1, const csBitArray &a2) 00350 { 00351 return csBitArray(a1) |= a2; 00352 } 00353 00355 friend csBitArray operator ^ (const csBitArray &a1, const csBitArray &a2) 00356 { 00357 return csBitArray(a1) ^= a2; 00358 } 00359 00360 // 00361 // Plain English interface 00362 // 00363 00365 void Clear() 00366 { 00367 memset (GetStore(), 0, mLength * sizeof(store_type)); 00368 } 00369 00371 void SetBit (size_t pos) 00372 { 00373 CS_ASSERT (pos < mNumBits); 00374 GetStore()[GetIndex(pos)] |= ((store_type)1) << GetOffset(pos); 00375 } 00376 00378 void ClearBit (size_t pos) 00379 { 00380 CS_ASSERT (pos < mNumBits); 00381 GetStore()[GetIndex(pos)] &= ~(((store_type)1) << GetOffset(pos)); 00382 } 00383 00385 void FlipBit (size_t pos) 00386 { 00387 CS_ASSERT (pos < mNumBits); 00388 GetStore()[GetIndex(pos)] ^= ((store_type)1) << GetOffset(pos); 00389 } 00390 00392 void Set (size_t pos, bool val = true) 00393 { 00394 if (val) 00395 SetBit(pos); 00396 else 00397 ClearBit(pos); 00398 } 00399 00401 bool IsBitSet (size_t pos) const 00402 { 00403 CS_ASSERT (pos < mNumBits); 00404 return (GetStore()[GetIndex(pos)] & (((store_type)1) << GetOffset(pos))) 00405 != 0; 00406 } 00407 00409 bool AreSomeBitsSet (size_t pos, size_t count) const 00410 { 00411 CS_ASSERT (pos + count <= mNumBits); 00412 store_type const* p = GetStore(); 00413 while (count > 0) 00414 { 00415 size_t index = GetIndex (pos); 00416 size_t offset = GetOffset (pos); 00417 size_t checkCount = MIN(count, cell_size - offset); 00418 store_type mask = ((checkCount == cell_size) ? ~(store_type)0 : 00419 ((((store_type)1) << checkCount) - 1)) << offset; 00420 if (p[index] & mask) 00421 return true; 00422 pos += checkCount; 00423 count -= checkCount; 00424 } 00425 return false; 00426 } 00427 00429 bool AllBitsFalse() const 00430 { 00431 store_type const* p = GetStore(); 00432 for (size_t i = 0; i < mLength; i++) 00433 if (p[i] != 0) 00434 return false; 00435 return true; 00436 } 00437 00439 csBitArray &FlipAllBits() 00440 { 00441 store_type* p = GetStore(); 00442 for (size_t i = 0; i < mLength; i++) 00443 p[i] = ~p[i]; 00444 Trim(); 00445 return *this; 00446 } 00447 00452 void Delete(size_t pos, size_t count) 00453 { 00454 if (count > 0) 00455 { 00456 size_t dst = pos; 00457 size_t src = pos + count; 00458 CS_ASSERT(src <= mNumBits); 00459 size_t ntail = mNumBits - src; 00460 while (ntail-- > 0) 00461 Set(dst++, IsBitSet(src++)); 00462 SetSize(mNumBits - count); 00463 } 00464 } 00465 00470 csBitArray Slice(size_t pos, size_t count) const 00471 { 00472 CS_ASSERT(pos + count <= mNumBits); 00473 csBitArray a(count); 00474 for (size_t i = pos, o = 0; i < pos + count; i++) 00475 if (IsBitSet(i)) 00476 a.SetBit(o++); 00477 return a; 00478 } 00479 00481 store_type* GetArrayBits() 00482 { 00483 return GetStore(); 00484 } 00485 00490 store_type GetSingleWord() 00491 { 00492 CS_ASSERT(mpStore == 0); 00493 return mSingleWord; 00494 } 00495 00500 void SetSingleWord (store_type sw) 00501 { 00502 CS_ASSERT(mpStore == 0); 00503 mSingleWord = sw; 00504 } 00505 }; 00506 00511 CS_SPECIALIZE_TEMPLATE 00512 class csComparator<csBitArray, csBitArray> 00513 { 00514 public: 00515 static int Compare (csBitArray const& key1, csBitArray const& key2) 00516 { 00517 csBitArray::store_type const* p0 = key1.GetStore(); 00518 csBitArray::store_type const* p1 = key2.GetStore(); 00519 size_t compareNum = MIN (key1.mLength, key2.mLength); 00520 size_t i = 0; 00521 for (; i < compareNum; i++) 00522 if (p0[i] != p1[i]) 00523 return (int)p0[i] - (int)p1[i]; 00524 if (key1.mLength > key2.mLength) 00525 { 00526 for (; i < key1.mLength; i++) 00527 if (p0[i] != 0) 00528 return (int)p0[i]; 00529 } 00530 else 00531 { 00532 for (; i < key2.mLength; i++) 00533 if (p1[i] != 0) 00534 return -((int)p1[i]); 00535 } 00536 return 0; 00537 } 00538 }; 00539 00544 CS_SPECIALIZE_TEMPLATE 00545 class csHashComputer<csBitArray> 00546 { 00547 public: 00548 static uint ComputeHash (csBitArray const& key) 00549 { 00550 const size_t uintCount = sizeof (csBitArray::store_type) / sizeof (uint); 00551 union 00552 { 00553 csBitArray::store_type store; 00554 uint ui[uintCount]; 00555 } bitStoreToUint; 00556 uint hash = 0; 00557 csBitArray::store_type const* p = key.GetStore(); 00558 // @@@ Not very good. Find a better hash function; however, it should 00559 // return the same hash for two bit arrays that are the same except for 00560 // the amount of trailing zeros. (e.g. f(10010110) == f(100101100000...)) 00561 for (size_t i = 0; i < key.mLength; i++) 00562 { 00563 bitStoreToUint.store = p[i]; 00564 for (size_t j = 0; j < uintCount; j++) 00565 hash += bitStoreToUint.ui[j]; 00566 } 00567 return hash; 00568 } 00569 }; 00570 00571 00572 #endif // __CS_BITARRAY_H__
Generated for Crystal Space by doxygen 1.4.6