#define IS_TAGGED(v) ((uint64_t)(v) & TAG)
#define STRIP_TAG(v) ((uint64_t)(v) & ~TAG)
+#define DOES_NOT_EXIST 0
+#define ERROR_INVALID_OPTION (-1)
+#define ERROR_INVALID_ARGUMENT (-2)
+#define ERROR_UNSUPPORTED_FEATURE (-3)
+
typedef unsigned long long uint64_t;
typedef unsigned int uint32_t;
typedef unsigned char uint8_t;
--- /dev/null
+#ifndef MAP_H
+#define MAP_H
+
+typedef struct map map_t;
+typedef enum stat { MAP_STAT_COUNT } map_stat_e;
+typedef enum { MAP_TYPE_HASHTABLE, MAP_TYPE_SKIPLIST, MAP_TYPE_LIST } map_type_e;
+
+map_t * map_alloc (map_type_e map_type);
+void map_free (map_t *map);
+void map_print (map_t *map);
+uint64_t map_stat (map_t *map, map_stat_e stat_type);
+
+uint64_t map_get (map_t *map, const void *key_data, uint32_t key_len);
+uint64_t map_set (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val);
+uint64_t map_add (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val);
+uint64_t map_cas (map_t *map, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val);
+uint64_t map_replace(map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val);
+uint64_t map_remove (map_t *map, const void *key_data, uint32_t key_len);
+
+#endif//MAP_H
*/
#ifndef TXN_H
#define TXN_H
-#include "struct.h"
+#include "map.h"
typedef enum { TXN_READ_WRITE, TXN_READ_ONLY, TXN_BLIND_WRITE } txn_access_t;
typedef enum { TXN_DIRTY_READ, TXN_READ_COMMITTED, TXN_REPEATABLE_READ } txn_isolation_t;
typedef struct txn txn_t;
-txn_t *txn_begin (txn_access_t access, txn_isolation_t isolation, hashtable_t *ht);
+txn_t *txn_begin (txn_access_t access, txn_isolation_t isolation, map_t *map);
#endif//TXN_H
EXES := $(TESTS)
RUNTIME_SRCS := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c
-TEST_SRCS := $(RUNTIME_SRCS)
+MAP_SRCS := map/map.c map/hashtable.c map/list.c map/skiplist.c map/nstring.c
+TEST_SRCS := $(RUNTIME_SRCS) $(MAP_SRCS)
rcu_test_SRCS := $(TEST_SRCS) test/rcu_test.c
-txn_test_SRCS := $(TEST_SRCS) struct/hashtable.c txn/txn.c
-ll_test_SRCS := $(TEST_SRCS) struct/list.c test/ll_test.c struct/nstring.c
-sl_test_SRCS := $(TEST_SRCS) struct/skiplist.c test/sl_test.c struct/nstring.c
-ht_test_SRCS := $(TEST_SRCS) struct/hashtable.c test/ht_test.c test/CuTest.c struct/nstring.c
+txn_test_SRCS := $(TEST_SRCS) txn/txn.c
+ll_test_SRCS := $(TEST_SRCS) test/ll_test.c
+sl_test_SRCS := $(TEST_SRCS) test/sl_test.c
+ht_test_SRCS := $(TEST_SRCS) test/ht_test.c test/CuTest.c
tests: $(TESTS)
#include "common.h"
#include "murmur.h"
#include "mem.h"
-#include "struct.h"
+#include "mlocal.h"
#include "nstring.h"
#define GET_PTR(x) ((nstring_t *)((x) & MASK(48))) // low-order 48 bits is a pointer to a nstring_t
//
// NOTE: the returned value matches <expected> iff the set succeeds
//
-// Certain values of <expected> have special meaning. If <expected> is EXPECT_EXISTS then any
+// Certain values of <expected> have special meaning. If <expected> is CAS_EXPECT_EXISTS then any
// real value matches (i.e. not a TOMBSTONE or DOES_NOT_EXIST) as long as <key> is in the table. If
-// <expected> is EXPECT_WHATEVER then skip the test entirely.
+// <expected> is CAS_EXPECT_WHATEVER then skip the test entirely.
//
-static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, const char *key_data,
- uint32_t key_len, uint64_t expected, uint64_t new) {
- TRACE("h1", "hti_compare_and_set: hti %p key %p", hti, key_data);
- TRACE("h1", "hti_compare_and_set: value %p expect %p", new, expected);
+static uint64_t hti_cas (hashtable_i_t *hti, uint32_t key_hash, const char *key_data, uint32_t key_len,
+ uint64_t expected, uint64_t new) {
+ TRACE("h1", "hti_cas: hti %p key %p", hti, key_data);
+ TRACE("h1", "hti_cas: value %p expect %p", new, expected);
assert(hti);
assert(new != DOES_NOT_EXIST && !IS_TAGGED(new));
assert(key_data);
// Install <key> in the table if it doesn't exist.
if (is_empty) {
- TRACE("h0", "hti_compare_and_set: entry %p is empty", e, 0);
- if (expected != EXPECT_WHATEVER && expected != EXPECT_DOES_NOT_EXIST)
+ TRACE("h0", "hti_cas: entry %p is empty", e, 0);
+ if (expected != CAS_EXPECT_WHATEVER && expected != CAS_EXPECT_DOES_NOT_EXIST)
return DOES_NOT_EXIST;
// No need to do anything, <key> is already deleted.
// Retry if another thread stole the entry out from under us.
if (e_key != DOES_NOT_EXIST) {
- TRACE("h0", "hti_compare_and_set: lost race to install key %p in entry %p", key, e);
- TRACE("h0", "hti_compare_and_set: found %p instead of NULL", GET_PTR(e_key), 0);
+ TRACE("h0", "hti_cas: lost race to install key %p in entry %p", key, e);
+ TRACE("h0", "hti_cas: found %p instead of NULL", GET_PTR(e_key), 0);
nbd_free(key);
- return hti_compare_and_set(hti, key_hash, key_data, key_len, expected, new); // tail-call
+ return hti_cas(hti, key_hash, key_data, key_len, expected, new); // tail-call
}
- TRACE("h2", "hti_compare_and_set: installed key %p in entry %p", key, e);
+ TRACE("h2", "hti_cas: installed key %p in entry %p", key, e);
}
- TRACE("h0", "hti_compare_and_set: entry for key \"%s\" is %p", GET_PTR(e->key)->data, e);
+ TRACE("h0", "hti_cas: entry for key \"%s\" is %p", GET_PTR(e->key)->data, e);
// If the entry is in the middle of a copy, the copy must be completed first.
uint64_t e_value = e->value;
if (did_copy) {
SYNC_ADD(&hti->num_entries_copied, 1);
}
- TRACE("h0", "hti_compare_and_set: value in the middle of a copy, copy completed by %s",
+ TRACE("h0", "hti_cas: value in the middle of a copy, copy completed by %s",
(did_copy ? "self" : "other"), 0);
}
- TRACE("h0", "hti_compare_and_set: value copied to next table, retry on next table", 0, 0);
+ TRACE("h0", "hti_cas: value copied to next table, retry on next table", 0, 0);
return COPIED_VALUE;
}
// Fail if the old value is not consistent with the caller's expectation.
int old_existed = (e_value != TOMBSTONE && e_value != DOES_NOT_EXIST);
- if (EXPECT_FALSE(expected != EXPECT_WHATEVER && expected != e_value)) {
- if (EXPECT_FALSE(expected != (old_existed ? EXPECT_EXISTS : EXPECT_DOES_NOT_EXIST))) {
- TRACE("h1", "hti_compare_and_set: value %p expected by caller not found; found value %p",
+ if (EXPECT_FALSE(expected != CAS_EXPECT_WHATEVER && expected != e_value)) {
+ if (EXPECT_FALSE(expected != (old_existed ? CAS_EXPECT_EXISTS : CAS_EXPECT_DOES_NOT_EXIST))) {
+ TRACE("h1", "hti_cas: value %p expected by caller not found; found value %p",
expected, e_value);
return e_value;
}
// No need to update if value is unchanged.
if ((new == TOMBSTONE && !old_existed) || e_value == new) {
- TRACE("h1", "hti_compare_and_set: old value and new value were the same", 0, 0);
+ TRACE("h1", "hti_cas: old value and new value were the same", 0, 0);
return e_value;
}
// CAS the value into the entry. Retry if it fails.
uint64_t v = SYNC_CAS(&e->value, e_value, new);
if (EXPECT_FALSE(v != e_value)) {
- TRACE("h0", "hti_compare_and_set: value CAS failed; expected %p found %p", e_value, v);
- return hti_compare_and_set(hti, key_hash, key_data, key_len, expected, new); // recursive tail-call
+ TRACE("h0", "hti_cas: value CAS failed; expected %p found %p", e_value, v);
+ return hti_cas(hti, key_hash, key_data, key_len, expected, new); // recursive tail-call
}
// The set succeeded. Adjust the value count.
}
// Return the previous value.
- TRACE("h0", "hti_compare_and_set: CAS succeeded; old value %p new value %p", e_value, new);
+ TRACE("h0", "hti_cas: CAS succeeded; old value %p new value %p", e_value, new);
return e_value;
}
}
//
-uint64_t ht_compare_and_set (hashtable_t *ht, const char *key_data, uint32_t key_len,
- uint64_t expected_val, uint64_t new_val) {
+uint64_t ht_cas (hashtable_t *ht, const char *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val) {
- TRACE("h2", "ht_compare_and_set: key %p len %u", key_data, key_len);
- TRACE("h2", "ht_compare_and_set: expected val %p new val %p", expected_val, new_val);
+ TRACE("h2", "ht_cas: key %p len %u", key_data, key_len);
+ TRACE("h2", "ht_cas: expected val %p new val %p", expected_val, new_val);
assert(key_data);
assert(!IS_TAGGED(new_val) && new_val != DOES_NOT_EXIST);
int num_copied = 0;
int x = hti->scan;
- TRACE("h1", "ht_compare_and_set: help copy. scan is %llu, size is %llu", x, 1<<hti->scale);
+ TRACE("h1", "ht_cas: help copy. scan is %llu, size is %llu", x, 1<<hti->scale);
// Panic if we've been around the array twice and still haven't finished the copy.
int panic = (x >= (1 << (hti->scale + 1)));
if (!panic) {
// the table.
e = hti->table + (x & MASK(hti->scale));
} else {
- TRACE("h1", "ht_compare_and_set: help copy panic", 0, 0);
+ TRACE("h1", "ht_cas: help copy panic", 0, 0);
// scan the whole table
limit = (1 << hti->scale);
e = hti->table;
uint64_t old_val;
uint32_t key_hash = murmur32(key_data, key_len);
- while ((old_val = hti_compare_and_set(hti, key_hash, key_data, key_len, expected_val, new_val))
+ while ((old_val = hti_cas(hti, key_hash, key_data, key_len, expected_val, new_val))
== COPIED_VALUE) {
assert(hti->next);
hti = hti->next;
uint64_t val;
uint32_t key_hash = murmur32(key_data, key_len);
do {
- val = hti_compare_and_set(hti, key_hash, key_data, key_len, EXPECT_WHATEVER, TOMBSTONE);
+ val = hti_cas(hti, key_hash, key_data, key_len, CAS_EXPECT_WHATEVER, TOMBSTONE);
if (val != COPIED_VALUE)
return val == TOMBSTONE ? DOES_NOT_EXIST : val;
assert(hti->next);
} while (hti);
nbd_free(ht);
}
+
+void ht_print (hashtable_t *ht) {
+}
#include <string.h>
#include "common.h"
-#include "struct.h"
+#include "mlocal.h"
#include "nstring.h"
#include "mem.h"
return ll;
}
+void ll_free (list_t *ll) {
+}
+
static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, const void *key_data, uint32_t key_len, int help_remove) {
node_t *pred = ll->head;
node_t *item = pred->next;
if (!find_pred(&pred, &old_item, ll, key_data, key_len, TRUE)) {
// There was not an item in the list that matches the key.
- if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == EXPECT_EXISTS)) {
+ if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == CAS_EXPECT_EXISTS)) {
TRACE("l1", "ll_cas: the expectation was not met, the list was not changed", 0, 0);
return DOES_NOT_EXIST; // failure
}
- ASSERT(expectation == EXPECT_DOES_NOT_EXIST || expectation == EXPECT_WHATEVER);
+ ASSERT(expectation == CAS_EXPECT_DOES_NOT_EXIST || expectation == CAS_EXPECT_WHATEVER);
// Create a new item and insert it into the list.
TRACE("l2", "ll_cas: attempting to insert item between %p and %p", pred, pred->next);
break; // retry
}
- if (EXPECT_FALSE(expectation == EXPECT_DOES_NOT_EXIST)) {
+ if (EXPECT_FALSE(expectation == CAS_EXPECT_DOES_NOT_EXIST)) {
TRACE("l1", "ll_cas: found an item %p in the list that matched the key. the expectation was "
"not met, the list was not changed", old_item, old_item_val);
return old_item_val; // failure
#ifndef STRUCT_H
#define STRUCT_H
-#define DOES_NOT_EXIST 0
-
-#define EXPECT_DOES_NOT_EXIST ( 0)
-#define EXPECT_EXISTS (-1)
-#define EXPECT_WHATEVER (-2)
+#define CAS_EXPECT_DOES_NOT_EXIST ( 0)
+#define CAS_EXPECT_EXISTS (-1)
+#define CAS_EXPECT_WHATEVER (-2)
typedef struct ht hashtable_t;
hashtable_t *ht_alloc (void);
-uint64_t ht_compare_and_set (hashtable_t *ht, const char *key, uint32_t key_len, uint64_t expected_val, uint64_t val);
+uint64_t ht_cas (hashtable_t *ht, const char *key, uint32_t key_len, uint64_t expected_val, uint64_t val);
uint64_t ht_get (hashtable_t *ht, const char *key, uint32_t len);
uint64_t ht_remove (hashtable_t *ht, const char *key, uint32_t len);
uint64_t ht_count (hashtable_t *ht);
+void ht_print (hashtable_t *ht);
void ht_free (hashtable_t *ht);
typedef struct ll list_t;
uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val);
uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len);
void ll_print (list_t *ll);
+void ll_free (list_t *ll);
typedef struct sl skiplist_t;
skiplist_t * sl_alloc (void);
uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val);
uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len);
void sl_print (skiplist_t *sl);
+void sl_free (list_t *sl);
+
#endif//STRUCT_H
* www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf
*
* This code is written for the x86 memory-model. The algorithim depends on certain stores and
- * loads being ordered. Be careful, this code probably won't work correctly on platforms with
- * weaker memory models if you don't add memory barriers in the right places.
+ * loads being ordered. Be careful, this code won't work correctly on platforms with weaker memory
+ * models if you don't add memory barriers in the right places.
*/
#include <stdio.h>
#include <string.h>
#include "common.h"
#include "runtime.h"
-#include "struct.h"
+#include "mlocal.h"
#include "nstring.h"
#include "mem.h"
#include "tls.h"
return n;
}
-node_t *node_alloc (int level, const void *key_data, uint32_t key_len, uint64_t val) {
+static node_t *node_alloc (int level, const void *key_data, uint32_t key_len, uint64_t val) {
assert(level >= 0 && level <= MAX_LEVEL);
size_t sz = sizeof(node_t) + (level + 1) * sizeof(node_t *);
node_t *item = (node_t *)nbd_malloc(sz);
return sl;
}
+void ll_free (list_t *ll) {
+}
+
static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl, const void *key_data, uint32_t key_len, int help_remove) {
node_t *pred = sl->head;
node_t *item = NULL;
if (old_item == NULL) {
// There was not an item in the skiplist that matches the key.
- if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == EXPECT_EXISTS)) {
+ if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == CAS_EXPECT_EXISTS)) {
TRACE("l1", "sl_cas: the expectation was not met, the skiplist was not changed", 0, 0);
return DOES_NOT_EXIST; // failure
}
- ASSERT(expectation == EXPECT_DOES_NOT_EXIST || expectation == EXPECT_WHATEVER);
+ ASSERT(expectation == CAS_EXPECT_DOES_NOT_EXIST || expectation == CAS_EXPECT_WHATEVER);
// First insert <new_item> into the bottom level.
TRACE("s3", "sl_cas: attempting to insert item between %p and %p", preds[0], nexts[0]);
break; // retry
}
- if (EXPECT_FALSE(expectation == EXPECT_DOES_NOT_EXIST)) {
+ if (EXPECT_FALSE(expectation == CAS_EXPECT_DOES_NOT_EXIST)) {
TRACE("s1", "sl_cas: found an item %p in the skiplist that matched the key. the expectation was "
"not met, the skiplist was not changed", old_item, old_item_val);
return old_item_val; // failure
#include "runtime.h"
#include "CuTest.h"
#include "common.h"
-#include "struct.h"
+#include "map.h"
#include "mem.h"
#include "lwt.h"
typedef struct worker_data {
int id;
CuTest *tc;
- hashtable_t *ht;
+ map_t *ht;
int *wait;
} worker_data_t;
-int64_t ht_set (hashtable_t *ht, const char *key, uint32_t key_len, int64_t val) {
- return ht_compare_and_set(ht, key, key_len, EXPECT_WHATEVER, val);
-}
-
-int64_t ht_add (hashtable_t *ht, const char *key, uint32_t key_len, int64_t val) {
- return ht_compare_and_set(ht, key, key_len, EXPECT_DOES_NOT_EXIST, val);
-}
-
-int64_t ht_replace (hashtable_t *ht, const char *key, uint32_t key_len, int64_t val) {
- return ht_compare_and_set(ht, key, key_len, EXPECT_EXISTS, val);
-}
-
// Test some basic stuff; add a few keys, remove a few keys
void basic_test (CuTest* tc) {
- hashtable_t *ht = ht_alloc();
-
- ASSERT_EQUAL( 0, ht_count(ht) );
- ASSERT_EQUAL( DOES_NOT_EXIST, ht_add(ht,"a",2,10) );
- ASSERT_EQUAL( 1, ht_count(ht) );
- ASSERT_EQUAL( DOES_NOT_EXIST, ht_add(ht,"b",2,20) );
- ASSERT_EQUAL( 2, ht_count(ht) );
- ASSERT_EQUAL( 20, ht_get(ht,"b",2) );
- ASSERT_EQUAL( 10, ht_set(ht,"a",2,11) );
- ASSERT_EQUAL( 20, ht_set(ht,"b",2,21) );
- ASSERT_EQUAL( 2, ht_count(ht) );
- ASSERT_EQUAL( 21, ht_add(ht,"b",2,22) );
- ASSERT_EQUAL( 11, ht_remove(ht,"a",2) );
- ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"a",2) );
- ASSERT_EQUAL( 1, ht_count(ht) );
- ASSERT_EQUAL( DOES_NOT_EXIST, ht_remove(ht,"a",2) );
- ASSERT_EQUAL( 21, ht_remove(ht,"b",2) );
- ASSERT_EQUAL( 0, ht_count(ht) );
- ASSERT_EQUAL( DOES_NOT_EXIST, ht_remove(ht,"b",2) );
- ASSERT_EQUAL( DOES_NOT_EXIST, ht_remove(ht,"c",2) );
- ASSERT_EQUAL( 0, ht_count(ht) );
+ map_t *ht = map_alloc(MAP_TYPE_HASHTABLE);
+
+ ASSERT_EQUAL( 0, map_stat(ht, MAP_STAT_COUNT) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"a",2,10) );
+ ASSERT_EQUAL( 1, map_stat(ht, MAP_STAT_COUNT) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"b",2,20) );
+ ASSERT_EQUAL( 2, map_stat(ht, MAP_STAT_COUNT) );
+ ASSERT_EQUAL( 20, map_get(ht,"b",2) );
+ ASSERT_EQUAL( 10, map_set(ht,"a",2,11) );
+ ASSERT_EQUAL( 20, map_set(ht,"b",2,21) );
+ ASSERT_EQUAL( 2, map_stat(ht, MAP_STAT_COUNT) );
+ ASSERT_EQUAL( 21, map_add(ht,"b",2,22) );
+ ASSERT_EQUAL( 11, map_remove(ht,"a",2) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"a",2) );
+ ASSERT_EQUAL( 1, map_stat(ht, MAP_STAT_COUNT) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"a",2) );
+ ASSERT_EQUAL( 21, map_remove(ht,"b",2) );
+ ASSERT_EQUAL( 0, map_stat(ht, MAP_STAT_COUNT) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"b",2) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"c",2) );
+ ASSERT_EQUAL( 0, map_stat(ht, MAP_STAT_COUNT) );
- ASSERT_EQUAL( DOES_NOT_EXIST, ht_add(ht,"d",2,40) );
- ASSERT_EQUAL( 40, ht_get(ht,"d",2) );
- ASSERT_EQUAL( 1, ht_count(ht) );
- ASSERT_EQUAL( 40, ht_remove(ht,"d",2) );
- ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"d",2) );
- ASSERT_EQUAL( 0, ht_count(ht) );
-
- ASSERT_EQUAL( DOES_NOT_EXIST, ht_replace(ht,"d",2,10) );
- ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"d",2) );
- ASSERT_EQUAL( DOES_NOT_EXIST, ht_set(ht,"d",2,40) );
- ASSERT_EQUAL( 40, ht_replace(ht,"d",2,41) );
- ASSERT_EQUAL( 41, ht_get(ht,"d",2) );
- ASSERT_EQUAL( 41, ht_remove(ht,"d",2) );
- ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"d",2) );
- ASSERT_EQUAL( 0, ht_count(ht) );
-
- ASSERT_EQUAL( DOES_NOT_EXIST, ht_replace(ht,"b",2,20) );
- ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"b",2) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"d",2,40) );
+ ASSERT_EQUAL( 40, map_get(ht,"d",2) );
+ ASSERT_EQUAL( 1, map_stat(ht, MAP_STAT_COUNT) );
+ ASSERT_EQUAL( 40, map_remove(ht,"d",2) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2) );
+ ASSERT_EQUAL( 0, map_stat(ht, MAP_STAT_COUNT) );
+
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(ht,"d",2,10) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_set(ht,"d",2,40) );
+ ASSERT_EQUAL( 40, map_replace(ht,"d",2,41) );
+ ASSERT_EQUAL( 41, map_get(ht,"d",2) );
+ ASSERT_EQUAL( 41, map_remove(ht,"d",2) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2) );
+ ASSERT_EQUAL( 0, map_stat(ht, MAP_STAT_COUNT) );
+
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(ht,"b",2,20) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"b",2) );
// In the end, all members should be removed
- ASSERT_EQUAL( DOES_NOT_EXIST, ht_set(ht,"b",2,20) );
- ASSERT_EQUAL( 20, ht_replace(ht,"b",2,21) );
- ASSERT_EQUAL( 21, ht_get(ht,"b",2) );
- ASSERT_EQUAL( 21, ht_remove(ht,"b",2) );
- ASSERT_EQUAL( DOES_NOT_EXIST, ht_get(ht,"b",2) );
- ASSERT_EQUAL( 0, ht_count(ht) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_set(ht,"b",2,20) );
+ ASSERT_EQUAL( 20, map_replace(ht,"b",2,21) );
+ ASSERT_EQUAL( 21, map_get(ht,"b",2) );
+ ASSERT_EQUAL( 21, map_remove(ht,"b",2) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"b",2) );
+ ASSERT_EQUAL( 0, map_stat(ht, MAP_STAT_COUNT) );
- ht_free(ht);
+ map_free(ht);
// In a quiecent state; it is safe to free.
rcu_update();
void *simple_worker (void *arg) {
worker_data_t *wd = (worker_data_t *)arg;
- hashtable_t *ht = wd->ht;
+ map_t *ht = wd->ht;
CuTest* tc = wd->tc;
uint64_t d = wd->id;
int iters = 1000000;
for (int i = d; i < iters; i+=2) {
char key[10];
sprintf(key, "k%u", i);
- TRACE("t0", "test ht_add() iteration (%llu, %llu)", j, i);
- CuAssertIntEquals_Msg(tc, key, DOES_NOT_EXIST, ht_add(ht, key, strlen(key)+1, d+1) );
+ TRACE("t0", "test map_add() iteration (%llu, %llu)", j, i);
+ CuAssertIntEquals_Msg(tc, key, DOES_NOT_EXIST, map_add(ht, key, strlen(key)+1, d+1) );
}
for (int i = d; i < iters; i+=2) {
char key[10];
sprintf(key, "k%u", i);
- TRACE("t0", "test ht_remove() iteration (%llu, %llu)", j, i);
- CuAssertIntEquals_Msg(tc, key, d+1, ht_remove(ht, key, strlen(key)+1) );
+ TRACE("t0", "test map_remove() iteration (%llu, %llu)", j, i);
+ CuAssertIntEquals_Msg(tc, key, d+1, map_remove(ht, key, strlen(key)+1) );
}
rcu_update();
}
pthread_t thread[2];
worker_data_t wd[2];
int wait = 2;
- hashtable_t *ht = ht_alloc();
+ map_t *ht = map_alloc(MAP_TYPE_HASHTABLE);
// In 2 threads, add & remove even & odd elements concurrently
int i;
}
// In the end, all members should be removed
- ASSERT_EQUAL( 0, ht_count(ht) );
+ ASSERT_EQUAL( 0, map_stat(ht, MAP_STAT_COUNT) );
// In a quiecent state; it is safe to free.
- ht_free(ht);
+ map_free(ht);
}
void *inserter_worker (void *arg) {
//pthread_t thread[NUM_THREADS];
- //hashtable_t *ht = ht_alloc();
+ //map_t *ht = map_alloc(MAP_TYPE_HASHTABLE);
return NULL;
}
#include "common.h"
#include "runtime.h"
-#include "struct.h"
+#include "map.h"
#define NUM_ITERATIONS 10000000
static volatile int wait_;
static long num_threads_;
-static list_t *ll_;
+static map_t *map_;
void *worker (void *arg) {
char key_str[10];
sprintf(key_str, "%llX", key);
if (r & (1 << 8)) {
- ll_cas(ll_, key_str, strlen(key_str) + 1, EXPECT_WHATEVER, 1);
+ map_set(map_, key_str, strlen(key_str) + 1, 1);
} else {
- ll_remove(ll_, key_str, strlen(key_str) + 1);
+ map_remove(map_, key_str, strlen(key_str) + 1);
}
#else
if (r & (1 << 8)) {
- ll_cas(ll_, (void *)key, -1, EXPECT_WHATEVER, 1);
+ map_set(map_, (void *)key, -1, 1);
} else {
- ll_remove(ll_, (void *)key, -1);
+ map_remove(map_, (void *)key, -1);
}
#endif
}
}
- ll_ = ll_alloc();
+ map_ = map_alloc(MAP_TYPE_LIST);
struct timeval tv1, tv2;
gettimeofday(&tv1, NULL);
gettimeofday(&tv2, NULL);
int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;
- ll_print(ll_);
+ map_print(map_);
printf("Th:%ld Time:%dms\n", num_threads_, ms);
return 0;
#include "common.h"
#include "runtime.h"
-#include "struct.h"
+#include "map.h"
#define NUM_ITERATIONS 10000000
static volatile int wait_;
static long num_threads_;
-static skiplist_t *sl_;
+static map_t *map_;
void *worker (void *arg) {
char key_str[10];
sprintf(key_str, "%llX", key);
if (r & (1 << 8)) {
- sl_cas(sl_, key_str, strlen(key_str) + 1, EXPECT_WHATEVER, (r & 0xFF)+1);
+ map_set(map_, key_str, strlen(key_str) + 1, (r & 0xFF)+1);
} else {
- sl_remove(sl_, key_str, strlen(key_str) + 1);
+ map_remove(map_, key_str, strlen(key_str) + 1);
}
#else
if (r & (1 << 8)) {
- sl_cas(sl_, (void *)key, -1, EXPECT_WHATEVER, (r & 0xFF)+1);
+ map_set(map_, (void *)key, -1, (r & 0xFF)+1);
} else {
- sl_remove(sl_, (void *)key, -1);
+ map_remove(map_, (void *)key, -1);
}
#endif
}
}
- sl_ = sl_alloc();
+ map_ = map_alloc(MAP_TYPE_SKIPLIST);
struct timeval tv1, tv2;
gettimeofday(&tv1, NULL);
gettimeofday(&tv2, NULL);
int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;
- sl_print(sl_);
+ map_print(map_);
printf("Th:%ld Time:%dms\n", num_threads_, ms);
return 0;
- make interfaces for all data structures consistent
+ make list and skiplist use string keys
+ optimize integer keys
+- sl_free() ll_free() ht_print()