hashtable.hpp

Go to the documentation of this file.

/*
 *  Copyright 2009 DreamLab Onet.pl Sp. z o.o.
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *  http://www.apache.org/licenses/LICENSE-2.0
 *
 *   Unless required by applicable law or agreed to in writing, software
 *   distributed under the License is distributed on an "AS IS" BASIS,
 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *   See the License for the specific language governing permissions and
 *   limitations under the License.
 *
 *   Authors:
 *   Michal Szklarzewicz <michal(x)szklarzewicz(y)gmail(x)com>
 *   Grzegorz Jablonski  <jablonski(x)grzegorz(y)gmail(x)com>
 *   (use dot instead of x, and @ instead of y)
 */

#ifndef __HASHTABLE_HPP_
#define __HASHTABLE_HPP_

#include <memory>
#include <stdexcept>
#include <deque>
#include <algorithm>
#include <boost/thread/shared_mutex.hpp>
#include <boost/thread/mutex.hpp>

using namespace boost;

//TEMPLATE CLASS HASHMAP
template<class KeyT, 
class StoreT,
class Allocator = std::allocator< std::pair<KeyT, StoreT> > >
class HashMap;

const size_t table_sizes[26] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 
                                                        393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 
                                                        100663319, 201326611, 402653189, 805306457, 1610612741 };

template<class KeyT, class StoreT, class Allocator>
class HashMap
{
        static const size_t globalBaseSize = 53;
        static const size_t upperFillLimit = 50; // grow if fill >= 100%

        typedef std::pair<KeyT, StoreT> storeType;
        
private:
        size_t(*hash)(size_t maxSize, const KeyT& val);
        size_t(*hash2)(size_t maxSize, const KeyT& val);
        int                             *refC;
        std::deque<HashMap<KeyT, StoreT, Allocator>*>* ref;
        Allocator                alloc;
        storeType               *content;
        size_t                   contentSize;
        size_t                   allocated;
        unsigned char   *allocateStatus; // 0 - free, 1 - deleted (and deallocated), 2 - allocated
    int                          sizeIndex;
        
        enum HashMapAllocateStatus{
                HashMapAllocateStatus_free = 0,
                HashMapAllocateStatus_deleted = 1,
                HashMapAllocateStatus_used = 2
        };

        /* mulit-thread */
public: 
        shared_mutex     hashTableLock; 
        shared_mutex    *hashElementLock;       
        mutex                    checkMutex;
        mutex                   *hashElementMutex;
        /* */
private:
    
        void build(size_t baseSize = globalBaseSize) {
                /* */
                hashTableLock.lock();
                
                refC = new int;
                *refC = 1;
                ref = new std::deque<HashMap<KeyT, StoreT, Allocator>*>;
                ref->push_back(this);
                contentSize = baseSize;
                content = alloc.allocate(contentSize);
                allocateStatus = new unsigned char[contentSize];
                memset(allocateStatus, HashMapAllocateStatus_free, contentSize);
                allocated = 0;
                hashElementMutex = new mutex[contentSize];
                hashElementLock = new shared_mutex[contentSize];
                /* */
                hashTableLock.unlock();
        }
        void build(const HashMap& reference) {
                /* */
                hashTableLock.lock();
                refC = reference.refC;
                ref = reference.ref;
                (*refC)++;
                ref->push_back(this);
                contentSize = reference.contentSize;
                content = reference.content;
                allocateStatus = reference.allocateStatus;
                allocated = reference.allocated;
                /* */
                hashTableLock.unlock();
        }

        void reallocate() {
                /* */
                hashTableLock.lock();
                //make copy
                storeType* oldContent = content;
                unsigned char* oldAllocateStatus = allocateStatus;
                //size_t oldAllocated = allocated;
                size_t oldContentSize = contentSize;
                
                contentSize = table_sizes[++sizeIndex];
                content = alloc.allocate(contentSize);
                allocateStatus = new unsigned char[contentSize];
                memset(allocateStatus, HashMapAllocateStatus_free, contentSize);
                allocated = 0;
                delete[] hashElementMutex;
                delete[] hashElementLock;
                hashElementMutex = new mutex[contentSize];
                hashElementLock = new shared_mutex[contentSize];

                debug("REALLOCATE %lld -> %lld\n", (long long)oldContentSize, (long long)contentSize);
                
                for( size_t p=0;p<oldContentSize;p++ ) {
                        if(oldAllocateStatus[p] == HashMapAllocateStatus_used) {
                                //find pos
                                size_t hashVal = hash( contentSize, oldContent[p].first );
                                size_t hashVal2 = hash2( contentSize, oldContent[p].first );
                                //inserting into hashtable
                                size_t failPos = hashVal;
                                size_t hashFix = 1;
                                while(true) {
                                        if( allocateStatus[failPos] != HashMapAllocateStatus_used ) {
                                                //thisPos is Ok
                                                break;
                                        } else {
                                                //failPos = (hashVal + hashFix) % contentSize;
                                                failPos = (hashVal + hashFix*hashVal2) %contentSize; 
                                                hashFix++;
                                        }
                                }

                                allocateStatus[failPos] = HashMapAllocateStatus_used;
                                alloc.construct( content+failPos, oldContent[p] );
                                alloc.destroy( oldContent+p );
                                allocated++;
                        }
                }
                alloc.deallocate( oldContent, oldContentSize );
                delete[] oldAllocateStatus;
                hashTableLock.unlock();
        }
public:
        HashMap( size_t(*hashFunction)(size_t maxSize, const KeyT& val) ): hash(hashFunction), hash2(hashFunction), sizeIndex(0) {
                build();
        }
        HashMap( size_t(*hashFunction)(size_t maxSize, const KeyT& val),  size_t(*hashFunction2)(size_t maxSize, const KeyT& val)): hash(hashFunction), hash2(hashFunction2), sizeIndex(0) {
                build();
        }
        HashMap( const HashMap& reference ): hash(reference.hash) {
                build(reference);
        }
    size_t size(){
        return allocated;
    }
        void forward_allocate(size_t to_be_filled) {
                //this is unsafe, should be called ONCE
                //sets sizeIndex to fill to_be_filled
                while(table_sizes[sizeIndex] < to_be_filled) {
                        sizeIndex++;
                }
                //now, table size will be about to_be_filled*2 (sizeIndex will be ++ in reallocate anyway)
                reallocate();
        }
        HashMap& operator=( const HashMap& reference ) {
                if(&reference == this) {
                        return *this;
                }
                //left is new
                this->~HashMap();
                build(reference);
                return *this;
        }
        ~HashMap() {
                        delete refC;
                        delete ref;
                        for( size_t p=0;p<contentSize;p++ ) {
                                if(allocateStatus[p] == HashMapAllocateStatus_used) {
                                        alloc.destroy( content+p );
                                }
                        }
                        alloc.deallocate(content, contentSize);
                        delete[] allocateStatus;
            delete[] hashElementMutex;
                    delete[] hashElementLock;
                        //true delete
        }
        
        void lock_table() {
            hashTableLock.lock();   
    }
        void unlock_table() {
            hashTableLock.unlock();
    }

        storeType& first(long long &position) {
            for(long long i=0; i<(long long)contentSize; i++)
                if( allocateStatus[i] == HashMapAllocateStatus_used) {
                    position = i;
                    break;
            } else if (i == (long long)contentSize - 1) {
                position = (long long)contentSize;
            }
        
        if(position >= (long long)contentSize ) {
            position = -1;
            return content[0];   
        }
        //debug("first() %lld\n",position);
        return content[position];
    }
        storeType& next(long long &position) {
                position++;
            for(long long i=position; i<(long long)contentSize; i++)
                if( allocateStatus[i] == HashMapAllocateStatus_used) {
                    position = i;
                    break;
            } else if (i == (long long)contentSize - 1) {
                position = (long long)contentSize;
            }
        
        if(position >= (long long)contentSize ) {
            position = -1;
            return content[0];   
        }
        //debug("next() %lld\n",position);
        return content[position];
    }
    //semi-safe

        StoreT& operator[](const KeyT &key) {
                //find this, if find fail, default construct
                hashTableLock.lock_shared();
                //hashing algorithm
                size_t hashVal = hash( contentSize, key );
                size_t hashVal2 = hash2( contentSize, key );
                //inserting into hashtable
                size_t failPos = hashVal;
                size_t hashFix = 1;
                while(true) {
            hashElementLock[failPos].lock_shared();
                        if( allocateStatus[failPos] != HashMapAllocateStatus_used ) {
                                //thisPos is Ok for insert, search failed
                hashElementMutex[failPos].lock();
                                
                                hashElementLock[failPos].unlock_shared();
                                hashElementLock[failPos].lock();

                                hashElementMutex[failPos].unlock();
                                break;
                        } else {
                                if( content[failPos].first == key ) {
                                        //correct possition, element found
                    hashElementLock[failPos].unlock_shared();
                                    hashTableLock.unlock_shared();
                                        return content[failPos].second;
                                }
                hashElementLock[failPos].unlock_shared();               

                                failPos = (hashVal + hashFix*hashVal2) % contentSize;
                                hashFix++;
                        }
                }
                //fail - default construct

                storeType h = std::make_pair( key, StoreT() );

                allocateStatus[failPos] = HashMapAllocateStatus_used;
                alloc.construct( content+failPos, h );
                allocated++;
                
                hashElementLock[failPos].unlock();
                hashTableLock.unlock_shared();
                
                return (*this)[key];
        }
        void insert( std::pair<KeyT, StoreT> val ) {
                checkMutex.lock();
                hashTableLock.lock_shared();
        
                if(allocated * 100 / contentSize >= upperFillLimit) {
                    hashTableLock.unlock_shared();      
                        reallocate();
                        hashTableLock.lock_shared();
                }
        
                checkMutex.unlock();

                //deattach();
                
                //hashing algorithm
                size_t hashVal = hash( contentSize, val.first );
                size_t hashVal2 = hash2( contentSize, val.first );
                //inserting into hashtable
                size_t failPos = hashVal;
                size_t hashFix = 1;
                while(true) {
                        hashElementLock[failPos].lock_shared();
                        if( allocateStatus[failPos] != HashMapAllocateStatus_used ) {
                                //thisPos is Ok
                                hashElementMutex[failPos].lock();
                                
                                hashElementLock[failPos].unlock_shared();
                                hashElementLock[failPos].lock();

                                hashElementMutex[failPos].unlock();
                                
                                break;
                        } else {
                                
                                if( content[failPos].first == val.first ) {
                                        hashElementMutex[failPos].lock();
                                        
                                        hashElementLock[failPos].unlock_shared();
                                        hashElementLock[failPos].lock();

                                        hashElementMutex[failPos].unlock();
                                        
                                        content[failPos].second = val.second;

                                        hashElementLock[failPos].unlock();
                                        hashTableLock.unlock_shared();
                                        return; // update only
                                }

                                hashElementLock[failPos].unlock_shared();               

                                //debug("FAILHIT F %lld %lld [%s]\n", (long long)hashFix, (long long)failPos, val.first.uid.data);
                                //failPos = (hashVal + hashFix) % contentSize;
                                failPos = (hashVal + hashFix*hashVal2) % contentSize;
                                hashFix++;
                        }
                }

                allocateStatus[failPos] = HashMapAllocateStatus_used;
                alloc.construct( content+failPos, val );
                allocated++;
                
                hashElementLock[failPos].unlock();
        /*      if(allocated * 100 / contentSize >= upperFillLimit)
                {
                        hashTableLock.unlock_shared();
                        reallocate();
                } */
                
                hashTableLock.unlock_shared();
                
        }
        void insert( KeyT key, StoreT val ) {
            insert(std::pair<KeyT, StoreT>(key, val));
    }
    
        void erase(const KeyT& key ) {
                //find this, if find fail do nothing

                hashTableLock.lock_shared();
                //hashing algorithm
                size_t hashVal = hash( contentSize, key );
                size_t hashVal2 = hash2( contentSize, key );
                //inserting into hashtable
                size_t failPos = hashVal;
                size_t hashFix = 1;
                while(true) {
                        hashElementLock[failPos].lock_shared();
                        if( allocateStatus[failPos] == HashMapAllocateStatus_used && content[failPos].first == key) {
                                hashElementMutex[failPos].lock();
                                        
                                hashElementLock[failPos].unlock_shared();
                                hashElementLock[failPos].lock();

                                hashElementMutex[failPos].unlock();
                                //correct possition, element found
                                break;
                        } else if ( allocateStatus[failPos] == HashMapAllocateStatus_free ) {
                                //search failed, do nothing
                                hashElementLock[failPos].unlock_shared();
                                hashTableLock.unlock_shared();
                                return;
                        } else { //keep on searching
                                hashElementLock[failPos].unlock_shared();
                                //failPos = (hashVal + hashFix) % contentSize;
                                failPos = (hashVal + hashFix*hashVal2) % contentSize;
                                hashFix++;
                        }
                }
                
                //delete it
                allocateStatus[failPos] = HashMapAllocateStatus_deleted;
                alloc.destroy( content+failPos );
                allocated--;
                hashElementLock[failPos].unlock();
                /*if(allocated * 100 / contentSize <= lowerFillLimit)
                {
                        reallocate();
                }*/
                hashTableLock.unlock_shared();
        }

        void unlock(const KeyT &key){
                //unlock shared_mutex on key
                size_t hashVal = hash( contentSize, key );
                size_t hashVal2 = hash2( contentSize, key );
                //inserting into hashtable
                size_t failPos = hashVal;
                size_t hashFix = 1;
                while(true) {   
                        hashElementLock[failPos].lock_shared();
                        if( allocateStatus[failPos] == HashMapAllocateStatus_used && content[failPos].first == key ) {
                                //correct possition, element found
                                hashElementLock[failPos].unlock_shared(); //unlock lock from this function
                                hashElementLock[failPos].unlock_shared(); //unlock lock from previous function
                                hashTableLock.unlock_shared();
                                return;
                        }
                        hashElementLock[failPos].unlock_shared();
                        //failPos = (hashVal + hashFix) % contentSize;
                        failPos = (hashVal + hashFix*hashVal2) % contentSize;
                        hashFix++;
                }
                //never come here
        }

        StoreT* find_lock(const KeyT &key) {
                //find this, if find fail, return 0

                //hashing algorithm
                hashTableLock.lock_shared();
                size_t hashVal = hash( contentSize, key );
                size_t hashVal2 = hash2( contentSize, key );
                //inserting into hashtable
                size_t failPos = hashVal;
                size_t hashFix = 1;
                while(true) {   
                        hashElementLock[failPos].lock_shared();
                        if( allocateStatus[failPos] == HashMapAllocateStatus_free ) {
                                hashElementLock[failPos].unlock_shared();
                                hashTableLock.unlock_shared();
                                return 0; //this pos is empty, so chain is broken
                        } else {
                                if( allocateStatus[failPos] == HashMapAllocateStatus_used && content[failPos].first == key ) {
                                        //correct possition, element found
                                        // LOCKED !!!!
                                        return &content[failPos].second;
                                }
                                hashElementLock[failPos].unlock_shared();
                                //failPos = (hashVal + hashFix) % contentSize;
                                failPos = (hashVal + hashFix*hashVal2) % contentSize;
                        //      debug("FAILHIT F %lld %lld [%s]\n", (long long)hashFix, (long long)failPos, key.uid.data);
                                hashFix++;
                        }
                }
                //never come here
        }
        
    StoreT* find(const KeyT &key) {
                //find this, if find fail, return 0

                //hashing algorithm
                hashTableLock.lock_shared();
                size_t hashVal = hash( contentSize, key );
                size_t hashVal2 = hash2( contentSize, key );
                //inserting into hashtable
                size_t failPos = hashVal;
                size_t hashFix = 1;
                while(true) {   
                        hashElementLock[failPos].lock_shared();
                        if( allocateStatus[failPos] == HashMapAllocateStatus_free ) {
                                hashElementLock[failPos].unlock_shared();
                                hashTableLock.unlock_shared();
                                return 0; //this pos is empty, so chain is broken
                        } else {
                                if( allocateStatus[failPos] == HashMapAllocateStatus_used && content[failPos].first == key ) {
                                        //correct possition, element found
                    hashElementLock[failPos].unlock_shared();
                                    hashTableLock.unlock_shared();
                                        return &content[failPos].second;
                                }
                                hashElementLock[failPos].unlock_shared();
                                //failPos = (hashVal + hashFix) % contentSize;
                                failPos = (hashVal + hashFix*hashVal2) % contentSize;
                                //debug("FAILHIT F %lld %lld [%s]\n", (long long)hashFix, (long long)failPos, key.uid.data);
                                hashFix++;
                        }
                }
                //never come here
        }
        void clear() {
                //deattach();

                for( size_t p=0;p<contentSize;p++ ) {
                        if(allocateStatus[p] == HashMapAllocateStatus_used) {
                                alloc.destroy( content+p );
                        }
                }
                memset(allocateStatus, HashMapAllocateStatus_free, contentSize);
                allocated = 0;
        }
};

#endif

---