add lockfree-hashmap

diff --git a/include/lockfree_hashmap.hpp b/include/lockfree_hashmap.hpp
new file mode 100644 (file)
index 0000000..ca7845a
--- /dev/null
+++ b/include/lockfree_hashmap.hpp
@@ -0,0 +1,125 @@
+/*
+//     lockfree_hashmap.hpp
+//
+//     Distributed under the Boost Software License, Version 1.0.(See accompanying
+//     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt
+*/
+
+#ifndef    LOCKFREE_HASHMAP_H
+#define    LOCKFREE_HASHMAP_H
+#include <boost/functional/hash.hpp>
+#include <boost/noncopyable.hpp>
+#include <boost/function.hpp>
+
+//Argument Tkey, its size must be 64bit or less.
+template < class Tkey, class Tvalue, class Hash = boost::hash< const Tkey* > >
+class lockfree_hashmap : boost::noncopyable{
+protected:
+
+       const           size_t          element_num;
+       volatile        mutable         size_t    counter;
+
+       struct container{
+               Tkey*                   key;
+               Tvalue*                 value;
+               bool                    rehash;
+               container() : key ( NULL ), value( NULL ) , rehash( false ) {}
+       };
+
+       volatile container*             hashmap;
+
+public:
+       typedef         Hash    hasher_type;
+       hasher_type     hasher;
+
+       // constractor
+       lockfree_hashmap( size_t num = 65535, Hash inhasher = boost::hash< const Tkey* >() ) :
+               element_num( num ) {
+               hashmap = new container[element_num];
+               hasher = inhasher;
+               __sync_lock_test_and_set( &counter, 0 );
+       }
+
+       // destractor
+       virtual ~lockfree_hashmap(){
+               delete [] hashmap;
+       }
+
+       //inserter
+       void    insert( const Tkey* key, const Tvalue* value ){
+               size_t          hashvalue = get_hashvalue( key );
+               Tkey*           pre_key = NULL;
+               //transaction st
+               do{
+                       for(;;){
+                               if( !hashmap[hashvalue].key ) break;
+                               if( hashmap[hashvalue].key == key ){
+                                       pre_key = hashmap[hashvalue].key;
+                                       break;
+                               }else{
+                                       hashmap[hashvalue].rehash = true;
+                                       hashvalue = get_rehashvalue( hashvalue );
+                               }
+                       }
+               }
+               while( !__sync_bool_compare_and_swap( &hashmap[hashvalue].key, pre_key, key ) );
+               //transaction ed
+               if( __sync_lock_test_and_set(&hashmap[hashvalue].value,value) ){};
+               if( __sync_add_and_fetch( &counter, 1 ) ){};
+       }
+
+       //finder
+       Tvalue* find( const Tkey* key ){
+               size_t    hashvalue = get_hashvalue( key );
+               for(;;){
+                       if( hashmap[hashvalue].key == key ){
+                               return hashmap[hashvalue].value;
+                       }else{
+                               if( !hashmap[hashvalue].rehash ) return NULL;
+                               hashvalue = get_rehashvalue( hashvalue );
+                       }
+               }
+       }
+
+       //eracer
+       void    erase( const Tkey*        key ){
+               size_t    hashvalue = get_hashvalue( key );
+               for(;;){
+                       if( hashmap[hashvalue].key == key ){
+                               if( __sync_lock_test_and_set(&hashmap[hashvalue].key,NULL) ){};
+                               if( __sync_lock_test_and_set(&hashmap[hashvalue].value,NULL) ){};
+                               __sync_sub_and_fetch( &counter, 1 );
+                               return;
+                       }else{
+                               if( !hashmap[hashvalue].rehash ) return;
+                               hashvalue = get_rehashvalue( hashvalue );
+                       }
+               }
+       }
+
+       //clear
+       void    clear(){
+               delete [] hashmap;
+               hashmap = new container[element_num];
+               __sync_lock_test_and_set( &counter, 0 );
+       }
+
+       // size
+       size_t    size(){ return counter; }
+
+       // empty
+       bool    empty(){ return !counter; }
+
+
+private:
+       //get array number by hasher
+       size_t    get_hashvalue(const Tkey* key ){
+               return hasher( key ) % element_num;
+       }
+       //reget array number case of collision(method chain)
+       size_t    get_rehashvalue( size_t& key ){
+               return ((key+1) % element_num);
+       }
+};
+
+#endif   //LOCKFREE_MAP_H