From: Peizhao Ou Date: Fri, 17 Jan 2014 19:04:17 +0000 (-0800) Subject: simplified hashtable X-Git-Url: http://plrg.eecs.uci.edu/git/?p=cdsspec-compiler.git;a=commitdiff_plain;h=c120687a518cd2c2e2ea8f4d129cbc5d16bc5c04 simplified hashtable --- diff --git a/benchmark/cliffc-hashtable/cliffc_hashtable.h b/benchmark/cliffc-hashtable/cliffc_hashtable.h index 2d3bd70..ff363fb 100644 --- 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 _ptr; + void *_ptr; - slot(bool prime, shared_ptr 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 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 get(TypeK& key) { + TypeV* get(TypeK& key) { void *key_ptr = (void*) new TypeK(key); - slot *key_slot = new slot(false, shared_ptr(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(V->_ptr); + return (TypeV*) V->_ptr; } /** @@ -398,7 +395,7 @@ friend class CHM; __sequential.equals_val(__RET__, _Old_Val) @End */ - shared_ptr 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 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 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 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 key = static_pointer_cast(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 key_ptr = static_pointer_cast(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 ptr1 = static_pointer_cast(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 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(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(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(res->_ptr); + return res == TOMBSTONE ? NULL : (TypeV*) res->_ptr; } /** diff --git a/benchmark/cliffc-hashtable/main.cc b/benchmark/cliffc-hashtable/main.cc index 86eecb7..6c75aff 100644 --- a/benchmark/cliffc-hashtable/main.cc +++ b/benchmark/cliffc-hashtable/main.cc @@ -1,5 +1,5 @@ #include - +#include #include "cliffc_hashtable.h" using namespace std; @@ -36,16 +36,16 @@ class IntWrapper { return _val; } - bool equals(const shared_ptr another) { + bool equals(const void *another) { if (another == NULL) return false; - shared_ptr ptr = - static_pointer_cast(another); + IntWrapper *ptr = + (IntWrapper*) another; return ptr->_val == _val; } }; -int main(int argc, char *argv[]) { +int user_main(int argc, char *argv[]) { cliffc_hashtable table; IntWrapper k1(3), k2(4), v1(1), v2(2);