UHash.h

Go to the documentation of this file.

//    Copyright (C) 2006-2012 Dylan Blair
//
//    email: dblair@alumni.cs.utexas.edu
//
//    This library is free software; you can redistribute it and/or
//    modify it under the terms of the GNU Lesser General Public
//    License as published by the Free Software Foundation; either
//    version 2.1 of the License, or (at your option) any later version.
//
//    This library is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//    Lesser General Public License for more details.
//
//    You should have received a copy of the GNU Lesser General Public
//    License along with this library; if not, write to the Free Software
//    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

#ifndef UHASH_H
#define UHASH_H

#include "UTypes.h"

#ifdef _DEBUG
#include <math.h>
#endif
#include <assert.h>

namespace OpenSkyNet {
    namespace Utils {
        const uint INITIAL_TABLE_SIZE = 512;

        const uint MAX_3D_COMPONENT_KEY = 1024;

        inline uint getCompositeKey(uint x_, uint y_, uint z_) {
            assert(MAX_3D_COMPONENT_KEY >= x_);
            assert(MAX_3D_COMPONENT_KEY >= y_);
            assert(MAX_3D_COMPONENT_KEY >= z_);
            return x_ | (y_ << 10) | (z_ << 20);
        }

        inline uint HashUIntToUInt(const uint& key_) {
            uint hash = 0;

            hash += (key_ & 0x000000FF);
            hash += (hash << 10);
            hash ^= (hash >> 6);
            hash += (key_ & 0x0000FF00);
            hash += (hash << 10);
            hash ^= (hash >> 6);
            hash += (key_ & 0x00FF0000);
            hash += (hash << 10);
            hash ^= (hash >> 6);
            hash += (key_ & 0xFF000000);
            hash += (hash << 10);
            hash ^= (hash >> 6);

            hash += (hash << 3);
            hash ^= (hash >> 11);
            hash += (hash << 15);

            //Here, we make the most significant bit 1 so
            //we are assured to never have a 0 hash. In
            //our table, we signify that a bin is unused
            //if it has a 0 hash stored. Although
            //assigning this bit divides the available
            //key space in 2, we should not have a table
            //large enough ( > 2147483648 bins) to need
            //the full hash.
            hash ^= 0x80000000;

            return hash;
        }

        template<class T=uint>
        class HashTableUIntKeys {
            struct TableNode {
                uint _hash, _key;
                T _value;
                TableNode() : _hash(0), _key(0) {}
            };
        public:
            HashTableUIntKeys(uint powerOf2InitialSize_) :
                _load(0), _size(powerOf2InitialSize_),
                _initSize(_size), _sizeMinusOne(_size - 1),
                _maxLoad(static_cast<uint>(static_cast<float>(_size) * 0.75f)),
                _isUsingDefaultValue(false),
                _table(new TableNode[_size]) {
#ifdef _DEBUG
                assert(_size < 2147483649u);
                double logSize = log(static_cast<double>(powerOf2InitialSize_));
                double log2 = log(2.0);
                double logSizeBase2 = logSize / log2;
                double logSizeBase2Truncated = static_cast<double>(static_cast<uint>(logSizeBase2));
                assert(logSizeBase2 == logSizeBase2Truncated);
#endif
            }

            HashTableUIntKeys(uint powerOf2InitialSize_, const T& defaultValue_) :
                _load(0), _size(powerOf2InitialSize_),
                _initSize(_size), _sizeMinusOne(_size - 1),
                _maxLoad(static_cast<uint>(static_cast<float>(_size) * 0.75f)),
                _isUsingDefaultValue(true), _defaultValue(defaultValue_),
                _table(new TableNode[_size]) {
#ifdef _DEBUG
                assert(_size < 2147483649u);
                double logSize = log(static_cast<double>(powerOf2InitialSize_));
                double log2 = log(2.0);
                double logSizeBase2 = logSize / log2;
                double logSizeBase2Truncated = static_cast<double>(static_cast<uint>(logSizeBase2));
                assert(logSizeBase2 == logSizeBase2Truncated);
#endif
                for (uint i = 0; i < _size; i++)
                    _table[i]._value = _defaultValue;
            }

            ~HashTableUIntKeys() {
                delete[] _table;
            }

            HashTableUIntKeys(const HashTableUIntKeys<T>& hashTable_) {
                _table = 0;
                *this = hashTable_;
            }

            HashTableUIntKeys& operator=(const HashTableUIntKeys<T>& hashTable_) {
                if (this == &hashTable_) return this;

                _load = hashTable_._load;
                _size = hashTable_._size;
                _initSize = hashTable_._initSize;
                _sizeMinusOne = hashTable_._sizeMinusOne;
                _maxLoad = hashTable_._maxLoad;
                _isUsingDefaultValue = hashTable_._isUsingDefaultValue;
                _defaultValue = hashTable_._defaultValue;

                if (_table) delete[] _table;
                _table = new TableNode[_size];
                for (uint i = 0; i < _size; ++i) {
                    _table[i]._hash = hashTable_[i]._hash;
                    _table[i]._key = hashTable_[i]._key;
                    _table[i]._value = hashTable_[i]._value;
                }
            }

            inline const T& find(const uint& key_) const {
                return _table[getBin(key_)]._value;
            }

            inline bool find(const uint& key_, T& value_) const {
                uint bin = getBin(key_);
                value_ = _table[bin]._value;
                if (_table[bin]._hash) return true;
                return false;
            }

            inline bool find(const uint& key_, T*& value_) const {
                uint bin = getBin(key_);
                if (_table[bin]._hash) {
                    value_ = &_table[bin]._value;
                    return true;
                }
                value_ = 0;
                return false;
            }

            inline const T& operator[](const uint& key_) const {
                return find(key_);
            }

            inline void add(const uint& key_, const T& value_) {
                uint hash = HashUIntToUInt(key_);
                uint bin = getBin(hash,key_,_table);
                if (_table[bin]._hash) _table[bin]._value = value_;
                else {
                    _table[bin]._hash = hash;
                    _table[bin]._key = key_;
                    _table[bin]._value = value_;
                    ++_load;
                    if (_load > _maxLoad) resize();
                }
            }

            inline T& add(const uint& key_) {
                uint hash = HashUIntToUInt(key_);
                uint bin = getBin(hash,key_,_table);
                if (!_table[bin]._hash) {
                    _table[bin]._hash = hash;
                    _table[bin]._key = key_;
                    ++_load;
                    if (_load > _maxLoad) {
                        resize();
                        bin = getBin(hash,key_,_table);
                    }
                }
                return _table[bin]._value;
            }

            inline bool remove(const uint& key_) {
                uint i = getBin(key_);
                if (!_table[i]._hash) return false;

                uint j = (i + 1) % _size;
                uint k = 0;
                while (_table[j]._hash) {
                    k = _table[j]._hash & _sizeMinusOne;

                    if ((j > i && (k <= i || k > j)) ||
                        (j < i && (k <= i && k > j))) {
                        _table[i] = _table[j];
                        i = j;
                    }

                    j = (j + 1) % _size;
                }

                _table[i]._hash = 0;
                //There is no harm in setting a default value
                //regardless if _isUsingDefaultValue is false.
                _table[i]._value = _defaultValue;
                --_load;
                return true;
            }

            inline void clear(bool doRealloc_=true) {
                _load = 0;

                if (doRealloc_) {
                    _size = _initSize;
                    _sizeMinusOne = _size - 1;
                    _maxLoad = static_cast<uint>(static_cast<float>(_size) * 0.75f);
                    delete[] _table;
                    _table = new TableNode[_size];
                    if (_isUsingDefaultValue)
                        for (uint i = 0; i < _size; ++i)
                            _table[i]._value = _defaultValue;
                }
                else {
                    if (_isUsingDefaultValue) {
                        for (uint i = 0; i < _size; ++i) {
                            _table[i]._hash = 0;
                            _table[i]._value = _defaultValue;
                        }
                    }
                    else for (uint i = 0; i < _size; ++i)
                        _table[i]._hash = 0;
                }
            }

            inline uint getLoad() const { return _load; }

            inline void getAllValues(T** values_) const {
                uint numFound = 0;
                for (uint i = 0; i < _size; i++) {
                    if (_table[i]._hash) {
                        values_[numFound] = &(_table[i]._value);
                        ++numFound;
                    }
                }
            }
        private:
            inline uint getBin(const uint& hash_, const uint& key_, const TableNode* table_) const {
                uint bin = hash_ & _sizeMinusOne;
                while (table_[bin]._hash && (table_[bin]._key != key_))
                    bin = (bin + 1) % _size;
                return bin;
            }

            inline uint getBin(const uint& key_) const {
                return getBin(HashUIntToUInt(key_),key_,_table);
            }

            inline void resize() {
                uint _oldSize = _size;
                _size = _size << 1;
                assert(_size < 2147483649u);
                _sizeMinusOne = _size - 1;
                _maxLoad = static_cast<uint>(static_cast<float>(_size) * 0.75f);

                //now fill up a new table
                TableNode* tempTable = new TableNode[_size];
                if (_isUsingDefaultValue)
                    for (uint a = 0; a < _size; a++)
                        tempTable[a]._value = _defaultValue;
                uint bin = 0;
                for (uint i = 0; i < _oldSize; i++) {
                    if (_table[i]._hash) {
                        bin = getBin(_table[i]._hash,_table[i]._key,tempTable);
                        tempTable[bin]._hash = _table[i]._hash;
                        tempTable[bin]._key = _table[i]._key;
                        tempTable[bin]._value = _table[i]._value;
                    }
                }
                delete[] _table;
                _table = tempTable;
            }

            uint _load, _size, _initSize, _sizeMinusOne, _maxLoad;
            bool _isUsingDefaultValue;
            T _defaultValue;
            TableNode* _table;
        };
    }
}

#endif //UHASH_TABLE_H