#include <iostream>
#include <atomic>
-#include <memory>
-#include <assert.h>
+#include <common.h>
+#include <model-assert.h>
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
kvs_data(int sz) {
_size = sz;
- int real_size = sizeof(atomic<void*>) * 2 + 2;
+ int real_size = sz * 2 + 2;
_data = new atomic<void*>[real_size];
// The control block should be initialized in resize()
// Init the hash record array
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() {
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;
}
-
};
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 {
public:
CHM(int size) {
+ _newkvs.store(NULL, memory_order_relaxed);
_size.store(size, memory_order_relaxed);
_slots.store(0, memory_order_relaxed);
}
kvs_data* resize(cliffc_hashtable *topmap, kvs_data *kvs) {
+ //model_print("resizing...\n");
kvs_data *newkvs = _newkvs.load(memory_order_acquire);
if (newkvs != NULL)
return newkvs;
newkvs = new kvs_data(newsz);
void *chm = (void*) new CHM(sz);
- newkvs->_data[0].store(chm, memory_order_relaxed);
+ newkvs->_data[0].store(chm, memory_order_release);
kvs_data *cur_newkvs;
// Another check after the slow allocation
void help_copy_impl(cliffc_hashtable *topmap, kvs_data *oldkvs,
bool copy_all) {
- assert (get_chm(oldkvs) == this);
+ MODEL_ASSERT (get_chm(oldkvs) == this);
kvs_data *newkvs = _newkvs.load(memory_order_acquire);
int oldlen = oldkvs->_size;
int min_copy_work = oldlen > 1024 ? 1024 : oldlen;
*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);
}
// 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,
private:
- static const int Default_Init_Size = 8; // Intial table size
+ static const int Default_Init_Size = 4; // Intial table size
static slot* const MATCH_ANY;
static slot* const NO_MATCH_OLD;
__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);
+ MODEL_ASSERT (!is_prime(V));
+ return (TypeV*) V->_ptr;
}
/**
__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);
}
__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);
}
__sequential.equals_val(__RET__, _Old_Val)
@End
*/
- shared_ptr<TypeV> remove(TypeK& key) {
+ TypeV* remove(TypeK& key) {
return putIfMatch(key, TOMBSTONE, NO_MATCH_OLD);
}
__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);
}
private:
static CHM* get_chm(kvs_data* kvs) {
- return (CHM*) kvs->_data[0].load(memory_order_relaxed);
+ CHM *res = (CHM*) kvs->_data[0].load(memory_order_relaxed);
+ return res;
}
static int* get_hashes(kvs_data *kvs) {
// Preserve happens-before semantics on newly inserted keys
static inline slot* key(kvs_data *kvs, int idx) {
- assert (idx >= 0 && idx < kvs->_size);
+ MODEL_ASSERT (idx >= 0 && idx < kvs->_size);
// Corresponding to the volatile read in get_impl() and putIfMatch in
// Cliff Click's Java implementation
- return (slot*) kvs->_data[idx * 2 + 2].load(memory_order_acquire);
+ slot *res = (slot*) kvs->_data[idx * 2 + 2].load(memory_order_acquire);
+ return res;
}
/**
*/
// Preserve happens-before semantics on newly inserted values
static inline slot* val(kvs_data *kvs, int idx) {
- assert (idx >= 0 && idx < kvs->_size);
+ MODEL_ASSERT (idx >= 0 && idx < kvs->_size);
// Corresponding to the volatile read in get_impl() and putIfMatch in
// Cliff Click's Java implementation
slot *res = (slot*) kvs->_data[idx * 2 + 3].load(memory_order_acquire);
}
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);
+ MODEL_ASSERT(key_slot != NULL && key_slot->_ptr != NULL);
+ TypeK* key = (TypeK*) key_slot->_ptr;
int h = key->hashCode();
// Spread bits according to Cliff Click's code
h += (h << 15) ^ 0xffffcd7d;
static bool keyeq(slot *K, slot *key_slot, int *hashes, int hash,
int fullhash) {
// Caller should've checked this.
- assert (K != NULL);
- shared_ptr<TypeK> key_ptr = static_pointer_cast<TypeK>(key_slot->_ptr);
+ MODEL_ASSERT (K != NULL);
+ TypeK* key_ptr = (TypeK*) key_slot->_ptr;
return
K == key_slot ||
((hashes[hash] == 0 || hashes[hash] == fullhash) &&
}
static bool valeq(slot *val_slot1, slot *val_slot2) {
- assert (val_slot1 != NULL);
- shared_ptr<TypeK> ptr1 = static_pointer_cast<TypeV>(val_slot1->_ptr);
+ MODEL_ASSERT (val_slot1 != NULL);
+ TypeK* ptr1 = (TypeV*) val_slot1->_ptr;
if (val_slot2 == NULL || ptr1 == NULL) return false;
return ptr1->equals(val_slot2->_ptr);
}
@End
*/
- if (V == NULL) return NULL; // A miss
+ if (K == NULL) return NULL; // A miss
if (keyeq(K, key_slot, hashes, idx, fullhash)) {
// Key hit! Check if table-resize in progress
}
// 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);
+ MODEL_ASSERT (res != NULL);
+ MODEL_ASSERT (!is_prime(res));
+ return res == TOMBSTONE ? NULL : (TypeV*) res->_ptr;
}
/**
*/
static slot* putIfMatch(cliffc_hashtable *topmap, kvs_data *kvs, slot
*key_slot, slot *val_slot, slot *expVal) {
- assert (val_slot != NULL);
- assert (!is_prime(val_slot));
- assert (!is_prime(expVal));
+ MODEL_ASSERT (val_slot != NULL);
+ MODEL_ASSERT (!is_prime(val_slot));
+ MODEL_ASSERT (!is_prime(expVal));
int fullhash = hash(key_slot);
int len = kvs->_size;
break;
}
K = key(kvs, idx); // CAS failed, get updated value
- assert (K != NULL);
+ MODEL_ASSERT (K != NULL);
}
// Key slot not null, there exists a Key here
// Decided to update the existing table
while (true) {
- assert (!is_prime(V));
+ MODEL_ASSERT (!is_prime(V));
if (expVal != NO_MATCH_OLD &&
V != expVal &&
projects / cdsspec-compiler.git / blobdiff