From 025017478bb385da88a6b185849c8bcffeb2e2aa Mon Sep 17 00:00:00 2001 From: jdybnis Date: Sat, 29 Nov 2008 07:55:44 +0000 Subject: [PATCH] generic interface for map-like data structures --- include/common.h | 5 ++ include/map.h | 20 +++++ include/txn.h | 4 +- makefile | 11 +-- {struct => map}/hashtable.c | 64 ++++++++-------- {struct => map}/list.c | 11 ++- include/struct.h => map/mlocal.h | 14 ++-- {struct => map}/nstring.c | 0 {struct => map}/nstring.h | 0 {struct => map}/skiplist.c | 17 +++-- test/ht_test.c | 126 ++++++++++++++----------------- test/ll_test.c | 16 ++-- test/sl_test.c | 16 ++-- todo | 1 + 14 files changed, 165 insertions(+), 140 deletions(-) create mode 100644 include/map.h rename {struct => map}/hashtable.c (88%) rename {struct => map}/list.c (97%) rename include/struct.h => map/mlocal.h (75%) rename {struct => map}/nstring.c (100%) rename {struct => map}/nstring.h (100%) rename {struct => map}/skiplist.c (97%) diff --git a/include/common.h b/include/common.h index 205ea34..bf3d04e 100644 --- a/include/common.h +++ b/include/common.h @@ -36,6 +36,11 @@ #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; diff --git a/include/map.h b/include/map.h new file mode 100644 index 0000000..d670c35 --- /dev/null +++ b/include/map.h @@ -0,0 +1,20 @@ +#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 diff --git a/include/txn.h b/include/txn.h index 54928cb..c23c59b 100644 --- a/include/txn.h +++ b/include/txn.h @@ -4,12 +4,12 @@ */ #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 diff --git a/makefile b/makefile index dfabc2d..0e22b60 100644 --- a/makefile +++ b/makefile @@ -11,12 +11,13 @@ TESTS := output/ll_test output/sl_test output/ht_test output/rcu_test 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) diff --git a/struct/hashtable.c b/map/hashtable.c similarity index 88% rename from struct/hashtable.c rename to map/hashtable.c index 5406d42..69583ac 100644 --- a/struct/hashtable.c +++ b/map/hashtable.c @@ -15,7 +15,7 @@ #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 @@ -287,14 +287,14 @@ static int hti_copy_entry (hashtable_i_t *ht1, volatile entry_t *ht1_e, uint32_t // // NOTE: the returned value matches iff the set succeeds // -// Certain values of have special meaning. If is EXPECT_EXISTS then any +// Certain values of have special meaning. If is CAS_EXPECT_EXISTS then any // real value matches (i.e. not a TOMBSTONE or DOES_NOT_EXIST) as long as is in the table. If -// is EXPECT_WHATEVER then skip the test entirely. +// 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); @@ -312,8 +312,8 @@ static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, cons // Install 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, is already deleted. @@ -329,15 +329,15 @@ static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, cons // 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; @@ -347,18 +347,18 @@ static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, cons 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; } @@ -366,15 +366,15 @@ static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, cons // 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. @@ -385,7 +385,7 @@ static uint64_t hti_compare_and_set (hashtable_i_t *hti, uint32_t key_hash, cons } // 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; } @@ -429,11 +429,10 @@ uint64_t ht_get (hashtable_t *ht, const char *key_data, uint32_t key_len) { } // -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); @@ -446,7 +445,7 @@ uint64_t ht_compare_and_set (hashtable_t *ht, const char *key_data, uint32_t key int num_copied = 0; int x = hti->scan; - TRACE("h1", "ht_compare_and_set: help copy. scan is %llu, size is %llu", x, 1<scale); + TRACE("h1", "ht_cas: help copy. scan is %llu, size is %llu", x, 1<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) { @@ -461,7 +460,7 @@ uint64_t ht_compare_and_set (hashtable_t *ht, const char *key_data, uint32_t key // 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; @@ -487,7 +486,7 @@ uint64_t ht_compare_and_set (hashtable_t *ht, const char *key_data, uint32_t key 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; @@ -503,7 +502,7 @@ uint64_t ht_remove (hashtable_t *ht, const char *key_data, uint32_t key_len) { 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); @@ -546,3 +545,6 @@ void ht_free (hashtable_t *ht) { } while (hti); nbd_free(ht); } + +void ht_print (hashtable_t *ht) { +} diff --git a/struct/list.c b/map/list.c similarity index 97% rename from struct/list.c rename to map/list.c index 5849247..a0f52a5 100644 --- a/struct/list.c +++ b/map/list.c @@ -9,7 +9,7 @@ #include #include "common.h" -#include "struct.h" +#include "mlocal.h" #include "nstring.h" #include "mem.h" @@ -55,6 +55,9 @@ list_t *ll_alloc (void) { 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; @@ -174,12 +177,12 @@ uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t ex 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); @@ -206,7 +209,7 @@ uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t ex 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 diff --git a/include/struct.h b/map/mlocal.h similarity index 75% rename from include/struct.h rename to map/mlocal.h index 9d12f73..548a49f 100644 --- a/include/struct.h +++ b/map/mlocal.h @@ -1,18 +1,17 @@ #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; @@ -21,6 +20,7 @@ uint64_t ll_lookup (list_t *ll, const void *key_data, uint32_t key_len); 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); @@ -28,5 +28,7 @@ uint64_t sl_lookup (skiplist_t *sl, const void *key_data, uint32_t key_len); 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 diff --git a/struct/nstring.c b/map/nstring.c similarity index 100% rename from struct/nstring.c rename to map/nstring.c diff --git a/struct/nstring.h b/map/nstring.h similarity index 100% rename from struct/nstring.h rename to map/nstring.h diff --git a/struct/skiplist.c b/map/skiplist.c similarity index 97% rename from struct/skiplist.c rename to map/skiplist.c index e8060dd..c0e869c 100644 --- a/struct/skiplist.c +++ b/map/skiplist.c @@ -10,15 +10,15 @@ * 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 #include #include "common.h" #include "runtime.h" -#include "struct.h" +#include "mlocal.h" #include "nstring.h" #include "mem.h" #include "tls.h" @@ -50,7 +50,7 @@ static int random_level (void) { 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); @@ -85,6 +85,9 @@ skiplist_t *sl_alloc (void) { 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; @@ -237,12 +240,12 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_ 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 into the bottom level. TRACE("s3", "sl_cas: attempting to insert item between %p and %p", preds[0], nexts[0]); @@ -271,7 +274,7 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_ 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 diff --git a/test/ht_test.c b/test/ht_test.c index a334db2..f90caed 100644 --- a/test/ht_test.c +++ b/test/ht_test.c @@ -7,7 +7,7 @@ #include "runtime.h" #include "CuTest.h" #include "common.h" -#include "struct.h" +#include "map.h" #include "mem.h" #include "lwt.h" @@ -16,74 +16,62 @@ 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(); @@ -91,7 +79,7 @@ void basic_test (CuTest* tc) { 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; @@ -103,14 +91,14 @@ void *simple_worker (void *arg) { 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(); } @@ -123,7 +111,7 @@ void simple_add_remove (CuTest* tc) { 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; @@ -140,17 +128,17 @@ void simple_add_remove (CuTest* tc) { } // 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; } diff --git a/test/ll_test.c b/test/ll_test.c index 03bc81f..490bf7d 100644 --- a/test/ll_test.c +++ b/test/ll_test.c @@ -5,13 +5,13 @@ #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) { @@ -26,15 +26,15 @@ 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 @@ -75,7 +75,7 @@ int main (int argc, char **argv) { } } - ll_ = ll_alloc(); + map_ = map_alloc(MAP_TYPE_LIST); struct timeval tv1, tv2; gettimeofday(&tv1, NULL); @@ -93,7 +93,7 @@ int main (int argc, char **argv) { 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; diff --git a/test/sl_test.c b/test/sl_test.c index 195a5dd..00f9ac0 100644 --- a/test/sl_test.c +++ b/test/sl_test.c @@ -5,13 +5,13 @@ #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) { @@ -26,15 +26,15 @@ 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 @@ -75,7 +75,7 @@ int main (int argc, char **argv) { } } - sl_ = sl_alloc(); + map_ = map_alloc(MAP_TYPE_SKIPLIST); struct timeval tv1, tv2; gettimeofday(&tv1, NULL); @@ -93,7 +93,7 @@ int main (int argc, char **argv) { 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; diff --git a/todo b/todo index 86d19ab..956736a 100644 --- a/todo +++ b/todo @@ -7,3 +7,4 @@ - make interfaces for all data structures consistent + make list and skiplist use string keys + optimize integer keys +- sl_free() ll_free() ht_print() -- 2.40.0