simplified hashtable

diff --git a/benchmark/cliffc-hashtable/cliffc_hashtable.h b/benchmark/cliffc-hashtable/cliffc_hashtable.h
index 2d3bd7075511d63039ec3c425e021ce680697b8e..ff363fb72f155a6d0ed667ef51043aa38d842ded 100644 (file)
--- a/benchmark/cliffc-hashtable/cliffc_hashtable.h
+++ b/benchmark/cliffc-hashtable/cliffc_hashtable.h
@@ -8,8 +8,6 @@
 
 using namespace std;
 
 
 using namespace std;
 

-
-

 /**
        This header file declares and defines a simplified version of Cliff Click's
        NonblockingHashMap. It contains all the necessary structrues and main
 /**
        This header file declares and defines a simplified version of Cliff Click's
        NonblockingHashMap. It contains all the necessary structrues and main


@@ -40,11 +38,11 @@ struct kvs_data {
                for (i = 0; i < _size; i++) {
                        hashes[i] = 0;
                }
                for (i = 0; i < _size; i++) {
                        hashes[i] = 0;
                }

-               _data[1].store(hashes, memory_order_relaxed);

                // Init the data to Null slot
                for (i = 2; i < real_size; i++) {
                        _data[i].store(NULL, memory_order_relaxed);
                }
                // Init the data to Null slot
                for (i = 2; i < real_size; i++) {
                        _data[i].store(NULL, memory_order_relaxed);
                }

+               _data[1].store(hashes, memory_order_release);

        }
 
        ~kvs_data() {
        }
 
        ~kvs_data() {


@@ -56,13 +54,12 @@ struct kvs_data {
 
 struct slot {
        bool _prime;
 
 struct slot {
        bool _prime;

-       shared_ptr<void> _ptr;
+       void *_ptr;

 
 

-       slot(bool prime, shared_ptr<void> ptr) {
+       slot(bool prime, void *ptr) {

                _prime = prime;
                _ptr = ptr;
        }
                _prime = prime;
                _ptr = ptr;
        }

-

 };
 
 
 };
 
 


@@ -71,9 +68,6 @@ struct slot {
        code for the its object, and "int equals(TypeK anotherKey)" which is
        used to judge equality.
        TypeK and TypeV should define their own copy constructor.
        code for the its object, and "int equals(TypeK anotherKey)" which is
        used to judge equality.
        TypeK and TypeV should define their own copy constructor.

-       To make the memory management safe and similar to Cliff Click's Java
-       implementation, we use shared_ptr instead of normal pointer in terms of the
-       pointers that point to TypeK and TypeV.

 */
 template<typename TypeK, typename TypeV>
 class cliffc_hashtable {
 */
 template<typename TypeK, typename TypeV>
 class cliffc_hashtable {


@@ -268,7 +262,7 @@ friend class CHM;
                        *oldkvs, int idx, void *should_help) {
                        kvs_data *newkvs = _newkvs.load(memory_order_acquire);
                        // We're only here cause the caller saw a Prime
                        *oldkvs, int idx, void *should_help) {
                        kvs_data *newkvs = _newkvs.load(memory_order_acquire);
                        // We're only here cause the caller saw a Prime

-                       if (copy_slot(topmap, idx, oldkvs, _newkvs))
+                       if (copy_slot(topmap, idx, oldkvs, newkvs))

                                copy_check_and_promote(topmap, oldkvs, 1); // Record the slot copied
                        return (should_help == NULL) ? newkvs : topmap->help_copy(newkvs);
                }
                                copy_check_and_promote(topmap, oldkvs, 1); // Record the slot copied
                        return (should_help == NULL) ? newkvs : topmap->help_copy(newkvs);
                }


@@ -288,9 +282,11 @@ friend class CHM;
        
                        // Promote the new table to the current table
                        if (copyDone + workdone == oldlen &&
        
                        // Promote the new table to the current table
                        if (copyDone + workdone == oldlen &&

-                               topmap->_kvs.load(memory_order_acquire) == oldkvs)
-                               topmap->_kvs.compare_exchange_strong(oldkvs, _newkvs, memory_order_release,
+                               topmap->_kvs.load(memory_order_acquire) == oldkvs) {
+                               kvs_data *newkvs = _newkvs.load(memory_order_acquire);
+                               topmap->_kvs.compare_exchange_strong(oldkvs, newkvs, memory_order_release,

                                        memory_order_release);
                                        memory_order_release);

+                       }

                }
        
                bool copy_slot(cliffc_hashtable *topmap, int idx, kvs_data *oldkvs,
                }
        
                bool copy_slot(cliffc_hashtable *topmap, int idx, kvs_data *oldkvs,


@@ -375,14 +371,15 @@ friend class CHM;
                        __sequential.equals_val(_Old_Val, __RET__)
                @End
        */
                        __sequential.equals_val(_Old_Val, __RET__)
                @End
        */

-       shared_ptr<TypeV> get(TypeK& key) {
+       TypeV* get(TypeK& key) {

                void *key_ptr = (void*) new TypeK(key);
                void *key_ptr = (void*) new TypeK(key);

-               slot *key_slot = new slot(false, shared_ptr<void>(key_ptr));
+               slot *key_slot = new slot(false, key_ptr);

                int fullhash = hash(key_slot);
                int fullhash = hash(key_slot);

-               slot *V = get_impl(this, _kvs, key_slot, fullhash);
+               kvs_data *kvs = _kvs.load(memory_order_acquire);
+               slot *V = get_impl(this, kvs, key_slot, fullhash);

                if (V == NULL) return NULL;
                assert (!is_prime(V));
                if (V == NULL) return NULL;
                assert (!is_prime(V));

-               return static_pointer_cast<TypeV>(V->_ptr);
+               return (TypeV*) V->_ptr;

        }
 
        /**
        }
 
        /**


@@ -398,7 +395,7 @@ friend class CHM;
                        __sequential.equals_val(__RET__, _Old_Val)
                @End
        */
                        __sequential.equals_val(__RET__, _Old_Val)
                @End
        */

-       shared_ptr<TypeV> put(TypeK& key, TypeV& val) {
+       TypeV* put(TypeK& key, TypeV& val) {

                return putIfMatch(key, val, NO_MATCH_OLD);
        }
 
                return putIfMatch(key, val, NO_MATCH_OLD);
        }
 


@@ -419,7 +416,7 @@ friend class CHM;
                        __COND_SAT__ ? __RET__ == NULL : __sequential.equals_val(_Old_Val, __RET__) 
                @End
        */
                        __COND_SAT__ ? __RET__ == NULL : __sequential.equals_val(_Old_Val, __RET__) 
                @End
        */

-       shared_ptr<TypeV> putIfAbsent(TypeK& key, TypeV& value) {
+       TypeV* putIfAbsent(TypeK& key, TypeV& value) {

                return putIfMatch(key, val, TOMBSTONE);
        }
 
                return putIfMatch(key, val, TOMBSTONE);
        }
 


@@ -435,7 +432,7 @@ friend class CHM;
                        __sequential.equals_val(__RET__, _Old_Val)
                @End
        */
                        __sequential.equals_val(__RET__, _Old_Val)
                @End
        */

-       shared_ptr<TypeV> remove(TypeK& key) {
+       TypeV* remove(TypeK& key) {

                return putIfMatch(key, TOMBSTONE, NO_MATCH_OLD);
        }
 
                return putIfMatch(key, TOMBSTONE, NO_MATCH_OLD);
        }
 


@@ -474,7 +471,7 @@ friend class CHM;
                        __sequential.equals_val(__RET__, _Old_Val)
                @End
        */
                        __sequential.equals_val(__RET__, _Old_Val)
                @End
        */

-       shared_ptr<TypeV> replace(TypeK& key, TypeV& val) {
+       TypeV* replace(TypeK& key, TypeV& val) {

                return putIfMatch(key, val, MATCH_ANY);
        }
 
                return putIfMatch(key, val, MATCH_ANY);
        }
 


@@ -545,7 +542,7 @@ friend class CHM;
 
        static int hash(slot *key_slot) {
                assert(key_slot != NULL && key_slot->_ptr != NULL);
 
        static int hash(slot *key_slot) {
                assert(key_slot != NULL && key_slot->_ptr != NULL);

-               shared_ptr<TypeK> key = static_pointer_cast<TypeK>(key_slot->_ptr);
+               TypeK* key = (TypeK*) key_slot->_ptr;

                int h = key->hashCode();
                // Spread bits according to Cliff Click's code
                h += (h << 15) ^ 0xffffcd7d;
                int h = key->hashCode();
                // Spread bits according to Cliff Click's code
                h += (h << 15) ^ 0xffffcd7d;


@@ -573,7 +570,7 @@ friend class CHM;
                int fullhash) {
                // Caller should've checked this.
                assert (K != NULL);
                int fullhash) {
                // Caller should've checked this.
                assert (K != NULL);

-               shared_ptr<TypeK> key_ptr = static_pointer_cast<TypeK>(key_slot->_ptr);
+               TypeK* key_ptr = (TypeK*) key_slot->_ptr;

                return
                        K == key_slot ||
                                ((hashes[hash] == 0 || hashes[hash] == fullhash) &&
                return
                        K == key_slot ||
                                ((hashes[hash] == 0 || hashes[hash] == fullhash) &&


@@ -583,7 +580,7 @@ friend class CHM;
 
        static bool valeq(slot *val_slot1, slot *val_slot2) {
                assert (val_slot1 != NULL);
 
        static bool valeq(slot *val_slot1, slot *val_slot2) {
                assert (val_slot1 != NULL);

-               shared_ptr<TypeK> ptr1 = static_pointer_cast<TypeV>(val_slot1->_ptr);
+               TypeK* ptr1 = (TypeV*) val_slot1->_ptr;

                if (val_slot2 == NULL || ptr1 == NULL) return false;
                return ptr1->equals(val_slot2->_ptr);
        }
                if (val_slot2 == NULL || ptr1 == NULL) return false;
                return ptr1->equals(val_slot2->_ptr);
        }


@@ -674,21 +671,22 @@ friend class CHM;
        }
 
        // A wrapper of the essential function putIfMatch()
        }
 
        // A wrapper of the essential function putIfMatch()

-       shared_ptr<TypeV> putIfMatch(TypeK& key, TypeV& value, slot *old_val) {
+       TypeV* putIfMatch(TypeK& key, TypeV& value, slot *old_val) {

                // TODO: Should throw an exception rather return NULL
                if (old_val == NULL) {
                        return NULL;
                }
                void *key_ptr = (void*) new TypeK(key);
                // TODO: Should throw an exception rather return NULL
                if (old_val == NULL) {
                        return NULL;
                }
                void *key_ptr = (void*) new TypeK(key);

-               slot *key_slot = new slot(false, shared_ptr<void>(key_ptr));
+               slot *key_slot = new slot(false, key_ptr);

 
                void *val_ptr = (void*) new TypeV(value);
 
                void *val_ptr = (void*) new TypeV(value);

-               slot *value_slot = new slot(false, shared_ptr<void>(val_ptr));
-               slot *res = putIfMatch(this, _kvs, key_slot, value_slot, old_val);
+               slot *value_slot = new slot(false, val_ptr);
+               kvs_data *kvs = _kvs.load(memory_order_acquire);
+               slot *res = putIfMatch(this, kvs, key_slot, value_slot, old_val);

                // Only when copy_slot() call putIfMatch() will it return NULL
                assert (res != NULL); 
                assert (!is_prime(res));
                // Only when copy_slot() call putIfMatch() will it return NULL
                assert (res != NULL); 
                assert (!is_prime(res));

-               return res == TOMBSTONE ? NULL : static_pointer_cast<TypeV>(res->_ptr);
+               return res == TOMBSTONE ? NULL : (TypeV*) res->_ptr;

        }
 
        /**
        }
 
        /**

diff --git a/benchmark/cliffc-hashtable/main.cc b/benchmark/cliffc-hashtable/main.cc
index 86eecb72aa4c5646071781f4ed75135d4c5a7091..6c75aff28849d0e77d3f77163e45153319c39a43 100644 (file)
--- a/benchmark/cliffc-hashtable/main.cc
+++ b/benchmark/cliffc-hashtable/main.cc
@@ -1,5 +1,5 @@
 #include <iostream>
 #include <iostream>

-
+#include <threads.h>

 #include "cliffc_hashtable.h"
 
 using namespace std;
 #include "cliffc_hashtable.h"
 
 using namespace std;


@@ -36,16 +36,16 @@ class IntWrapper {
                        return _val;
                }
 
                        return _val;
                }
 

-               bool equals(const shared_ptr<void> another) {
+               bool equals(const void *another) {

                        if (another == NULL)
                                return false;
                        if (another == NULL)
                                return false;

-                       shared_ptr<IntWrapper> ptr =
-                               static_pointer_cast<IntWrapper>(another);
+                       IntWrapper *ptr =
+                               (IntWrapper*) another;

                        return ptr->_val == _val;
                }
 };
 
                        return ptr->_val == _val;
                }
 };
 

-int main(int argc, char *argv[]) {
+int user_main(int argc, char *argv[]) {

        cliffc_hashtable<IntWrapper, IntWrapper> table;
        IntWrapper k1(3), k2(4), v1(1), v2(2);
        
        cliffc_hashtable<IntWrapper, IntWrapper> table;
        IntWrapper k1(3), k2(4), v1(1), v2(2);