PF_API 0.52

Code/Libs/Utils_LIB/UHash.h

Go to the documentation of this file.
00001 
00002 //    Copyright (C) 2006-2011 Dylan Blair
00003 //
00004 //    email: dblair@alumni.cs.utexas.edu
00005 //
00006 //    This library is free software; you can redistribute it and/or
00007 //    modify it under the terms of the GNU Lesser General Public
00008 //    License as published by the Free Software Foundation; either
00009 //    version 2.1 of the License, or (at your option) any later version.
00010 //
00011 //    This library is distributed in the hope that it will be useful,
00012 //    but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 //    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 //    Lesser General Public License for more details.
00015 //
00016 //    You should have received a copy of the GNU Lesser General Public
00017 //    License along with this library; if not, write to the Free Software
00018 //    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00020 
00021 #ifndef UHASH_H
00022 #define UHASH_H
00023 
00024 #ifdef _DEBUG
00025 #include <math.h>
00026 #endif
00027 #include <assert.h>
00028 
00029 #include "UTypes.h"
00030 
00031 namespace OpenSkyNet {
00032     namespace Utils {
00034         const uint INITIAL_TABLE_SIZE = 512;
00035 
00040         const uint MAX_3D_COMPONENT_KEY = 1024;
00041 
00044         inline uint getCompositeKey(uint x_, uint y_, uint z_) {
00045             assert(MAX_3D_COMPONENT_KEY >= x_);
00046             assert(MAX_3D_COMPONENT_KEY >= y_);
00047             assert(MAX_3D_COMPONENT_KEY >= z_);
00048             return x_ | (y_ << 10) | (z_ << 20);
00049         }
00050 
00052         inline uint HashUIntToUInt(const uint& key_) {
00053             uint hash = 0;
00054 
00055             hash += (key_ & 0x000000FF);
00056             hash += (hash << 10);
00057             hash ^= (hash >> 6);
00058             hash += (key_ & 0x0000FF00);
00059             hash += (hash << 10);
00060             hash ^= (hash >> 6);
00061             hash += (key_ & 0x00FF0000);
00062             hash += (hash << 10);
00063             hash ^= (hash >> 6);
00064             hash += (key_ & 0xFF000000);
00065             hash += (hash << 10);
00066             hash ^= (hash >> 6);
00067 
00068             hash += (hash << 3);
00069             hash ^= (hash >> 11);
00070             hash += (hash << 15);
00071 
00072             //Here, we make the most significant bit 1 so
00073             //we are assured to never have a 0 hash. In
00074             //our table, we signify that a bin is unused
00075             //if it has a 0 hash stored. Although
00076             //assigning this bit divides the available
00077             //key space in 2, we should not have a table
00078             //large enough ( > 2147483648 bins) to need
00079             //the full hash.
00080             hash ^= 0x80000000;
00081 
00082             return hash;
00083         }
00084 
00085         template<class T=uint>
00087         class HashTableUIntKeys {
00088             struct TableNode {
00089                 uint _hash, _key;
00090                 T _value;
00091                 TableNode() : _hash(0), _key(0) {}
00092             };
00093         public:
00094             HashTableUIntKeys(uint powerOf2InitialSize_) :
00095                 _load(0), _size(powerOf2InitialSize_),
00096                 _initSize(_size), _sizeMinusOne(_size - 1),
00097                 _maxLoad(static_cast<uint>(static_cast<float>(_size) * 0.75f)),
00098                 _isUsingDefaultValue(false),
00099                 _table(new TableNode[_size]) {
00100 #ifdef _DEBUG
00101                 assert(_size < 2147483649u);
00102                 double logSize = log(static_cast<double>(powerOf2InitialSize_));
00103                 double log2 = log(2.0);
00104                 double logSizeBase2 = logSize / log2;
00105                 double logSizeBase2Truncated = static_cast<double>(static_cast<uint>(logSizeBase2));
00106                 assert(logSizeBase2 == logSizeBase2Truncated);
00107 #endif
00108             }
00109 
00110             HashTableUIntKeys(uint powerOf2InitialSize_, const T& defaultValue_) :
00111                 _load(0), _size(powerOf2InitialSize_),
00112                 _initSize(_size), _sizeMinusOne(_size - 1),
00113                 _maxLoad(static_cast<uint>(static_cast<float>(_size) * 0.75f)),
00114                 _isUsingDefaultValue(true), _defaultValue(defaultValue_),
00115                 _table(new TableNode[_size]) {
00116 #ifdef _DEBUG
00117                 assert(_size < 2147483649u);
00118                 double logSize = log(static_cast<double>(powerOf2InitialSize_));
00119                 double log2 = log(2.0);
00120                 double logSizeBase2 = logSize / log2;
00121                 double logSizeBase2Truncated = static_cast<double>(static_cast<uint>(logSizeBase2));
00122                 assert(logSizeBase2 == logSizeBase2Truncated);
00123 #endif
00124                 for (uint i = 0; i < _size; i++)
00125                     _table[i]._value = _defaultValue;
00126             }
00127 
00128             ~HashTableUIntKeys() {
00129                 delete[] _table;
00130             }
00131 
00132             HashTableUIntKeys(const HashTableUIntKeys<T>& hashTable_) {
00133                 _table = 0;
00134                 *this = hashTable_;
00135             }
00136 
00137             HashTableUIntKeys& operator=(const HashTableUIntKeys<T>& hashTable_) {
00138                 if (this == &hashTable_) return this;
00139 
00140                 _load = hashTable_._load;
00141                 _size = hashTable_._size;
00142                 _initSize = hashTable_._initSize;
00143                 _sizeMinusOne = hashTable_._sizeMinusOne;
00144                 _maxLoad = hashTable_._maxLoad;
00145                 _isUsingDefaultValue = hashTable_._isUsingDefaultValue;
00146                 _defaultValue = hashTable_._defaultValue;
00147 
00148                 if (_table) delete[] _table;
00149                 _table = new TableNode[_size];
00150                 for (uint i = 0; i < _size; ++i) {
00151                     _table[i]._hash = hashTable_[i]._hash;
00152                     _table[i]._key = hashTable_[i]._key;
00153                     _table[i]._value = hashTable_[i]._value;
00154                 }
00155             }
00156 
00157             inline const T& find(const uint& key_) const {
00158                 return _table[getBin(key_)]._value;
00159             }
00160 
00161             inline bool find(const uint& key_, T& value_) const {
00162                 uint bin = getBin(key_);
00163                 value_ = _table[bin]._value;
00164                 if (_table[bin]._hash) return true;
00165                 return false;
00166             }
00167 
00168             inline bool find(const uint& key_, T*& value_) const {
00169                 uint bin = getBin(key_);
00170                 if (_table[bin]._hash) {
00171                     value_ = &_table[bin]._value;
00172                     return true;
00173                 }
00174                 value_ = 0;
00175                 return false;
00176             }
00177 
00180             inline const T& operator[](const uint& key_) const {
00181                 return find(key_);
00182             }
00183 
00185             inline void add(const uint& key_, const T& value_) {
00186                 uint hash = HashUIntToUInt(key_);
00187                 uint bin = getBin(hash,key_,_table);
00188                 if (_table[bin]._hash) _table[bin]._value = value_;
00189                 else {
00190                     _table[bin]._hash = hash;
00191                     _table[bin]._key = key_;
00192                     _table[bin]._value = value_;
00193                     ++_load;
00194                     if (_load > _maxLoad) resize();
00195                 }
00196             }
00197 
00200             inline T& add(const uint& key_) {
00201                 uint hash = HashUIntToUInt(key_);
00202                 uint bin = getBin(hash,key_,_table);
00203                 if (!_table[bin]._hash) {
00204                     _table[bin]._hash = hash;
00205                     _table[bin]._key = key_;
00206                     ++_load;
00207                     if (_load > _maxLoad) {
00208                         resize();
00209                         bin = getBin(hash,key_,_table);
00210                     }
00211                 }
00212                 return _table[bin]._value;
00213             }
00214 
00216             inline bool remove(const uint& key_) {
00217                 uint i = getBin(key_);
00218                 if (!_table[i]._hash) return false;
00219 
00220                 uint j = (i + 1) % _size;
00221                 uint k = 0;
00222                 while (_table[j]._hash) {
00223                     k = _table[j]._hash & _sizeMinusOne;
00224 
00225                     if ((j > i && (k <= i || k > j)) ||
00226                         (j < i && (k <= i && k > j))) {
00227                         _table[i] = _table[j];
00228                         i = j;
00229                     }
00230 
00231                     j = (j + 1) % _size;
00232                 }
00233 
00234                 _table[i]._hash = 0;
00235                 //There is no harm in setting a default value
00236                 //regardless if _isUsingDefaultValue is false.
00237                 _table[i]._value = _defaultValue;
00238                 --_load;
00239                 return true;
00240             }
00241 
00247             inline void clear(bool doRealloc_=true) {
00248                 _load = 0;
00249 
00250                 if (doRealloc_) {
00251                     _size = _initSize;
00252                     _sizeMinusOne = _size - 1;
00253                     _maxLoad = static_cast<uint>(static_cast<float>(_size) * 0.75f);
00254                     delete[] _table;
00255                     _table = new TableNode[_size];
00256                     if (_isUsingDefaultValue)
00257                         for (uint i = 0; i < _size; ++i)
00258                             _table[i]._value = _defaultValue;
00259                 }
00260                 else {
00261                     if (_isUsingDefaultValue) {
00262                         for (uint i = 0; i < _size; ++i) {
00263                             _table[i]._hash = 0;
00264                             _table[i]._value = _defaultValue;
00265                         }
00266                     }
00267                     else for (uint i = 0; i < _size; ++i)
00268                         _table[i]._hash = 0;
00269                 }
00270             }
00271 
00273             inline uint getLoad() const { return _load; }
00274 
00279             inline void getAllValues(T** values_) const {
00280                 uint numFound = 0;
00281                 for (uint i = 0; i < _size; i++) {
00282                     if (_table[i]._hash) {
00283                         values_[numFound] = &(_table[i]._value);
00284                         ++numFound;
00285                     }
00286                 }
00287             }
00288         private:
00289             inline uint getBin(const uint& hash_, const uint& key_, const TableNode* table_) const {
00290                 uint bin = hash_ & _sizeMinusOne;
00291                 while (table_[bin]._hash && (table_[bin]._key != key_))
00292                     bin = (bin + 1) % _size;
00293                 return bin;
00294             }
00295 
00296             inline uint getBin(const uint& key_) const {
00297                 return getBin(HashUIntToUInt(key_),key_,_table);
00298             }
00299 
00300             inline void resize() {
00301                 uint _oldSize = _size;
00302                 _size = _size << 1;
00303                 assert(_size < 2147483649u);
00304                 _sizeMinusOne = _size - 1;
00305                 _maxLoad = static_cast<uint>(static_cast<float>(_size) * 0.75f);
00306 
00307                 //now fill up a new table
00308                 TableNode* tempTable = new TableNode[_size];
00309                 if (_isUsingDefaultValue)
00310                     for (uint a = 0; a < _size; a++)
00311                         tempTable[a]._value = _defaultValue;
00312                 uint bin = 0;
00313                 for (uint i = 0; i < _oldSize; i++) {
00314                     if (_table[i]._hash) {
00315                         bin = getBin(_table[i]._hash,_table[i]._key,tempTable);
00316                         tempTable[bin]._hash = _table[i]._hash;
00317                         tempTable[bin]._key = _table[i]._key;
00318                         tempTable[bin]._value = _table[i]._value;
00319                     }
00320                 }
00321                 delete[] _table;
00322                 _table = tempTable;
00323             }
00324 
00325             uint _load, _size, _initSize, _sizeMinusOne, _maxLoad;
00326             bool _isUsingDefaultValue;
00327             T _defaultValue;
00328             TableNode* _table;
00329         };
00330     }
00331 }
00332 
00333 #endif //UHASH_TABLE_H
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines