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;
 
-
-
 /**
        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;
                }
-               _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);
                }
+               _data[1].store(hashes, memory_order_release);
        }
 
        ~kvs_data() {
@@ -56,13 +54,12 @@ struct kvs_data {
 
 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;
        }
-
 };
 
 
@@ -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.
-       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 {
@@ -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
-                       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);
                }
@@ -288,9 +282,11 @@ friend class CHM;
        
                        // 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);
+                       }
                }
        
                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
        */
-       shared_ptr<TypeV> get(TypeK& key) {
+       TypeV* get(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);
-               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));
-               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
        */
-       shared_ptr<TypeV> put(TypeK& key, TypeV& val) {
+       TypeV* put(TypeK& key, TypeV& val) {
                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
        */
-       shared_ptr<TypeV> putIfAbsent(TypeK& key, TypeV& value) {
+       TypeV* putIfAbsent(TypeK& key, TypeV& value) {
                return putIfMatch(key, val, TOMBSTONE);
        }
 
@@ -435,7 +432,7 @@ friend class CHM;
                        __sequential.equals_val(__RET__, _Old_Val)
                @End
        */
-       shared_ptr<TypeV> remove(TypeK& key) {
+       TypeV* remove(TypeK& key) {
                return putIfMatch(key, TOMBSTONE, NO_MATCH_OLD);
        }
 
@@ -474,7 +471,7 @@ friend class CHM;
                        __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);
        }
 
@@ -545,7 +542,7 @@ friend class CHM;
 
        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;
@@ -573,7 +570,7 @@ friend class CHM;
                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) &&
@@ -583,7 +580,7 @@ friend class CHM;
 
        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);
        }
@@ -674,21 +671,22 @@ friend class CHM;
        }
 
        // 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);
-               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);
-               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));
-               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 <threads.h>
 #include "cliffc_hashtable.h"
 
 using namespace std;
@@ -36,16 +36,16 @@ class IntWrapper {
                        return _val;
                }
 
-               bool equals(const shared_ptr<void> another) {
+               bool equals(const void *another) {
                        if (another == NULL)
                                return false;
-                       shared_ptr<IntWrapper> ptr =
-                               static_pointer_cast<IntWrapper>(another);
+                       IntWrapper *ptr =
+                               (IntWrapper*) another;
                        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);