From 329b5ab58cde015f4faec1879d3106f635294dd6 Mon Sep 17 00:00:00 2001 From: jdybnis Date: Mon, 15 Dec 2008 01:32:01 +0000 Subject: [PATCH] generic map iterator interface --- include/hashtable.h | 13 ++--- include/list.h | 10 ++-- include/map.h | 45 +++++++++----- include/murmur.h | 39 ++++++++++++- include/skiplist.h | 12 ++-- include/txn.h | 7 +-- map/hashtable.c | 39 +++++-------- map/list.c | 38 ++++++------ map/map.c | 21 +++++++ map/skiplist.c | 38 ++++++------ test/map_test1.c | 2 +- test/map_test2.c | 139 ++++++++++++++++++++++++++++++++++++++------ test/txn_test.c | 16 ++--- todo | 25 +++++--- txn/txn.c | 18 +++--- 15 files changed, 317 insertions(+), 145 deletions(-) diff --git a/include/hashtable.h b/include/hashtable.h index 5ae84c1..0a9ea20 100644 --- a/include/hashtable.h +++ b/include/hashtable.h @@ -6,7 +6,7 @@ typedef struct ht hashtable_t; typedef struct ht_iter ht_iter_t; -hashtable_t *ht_alloc (const datatype_t *key_type); +hashtable_t * ht_alloc (const datatype_t *key_type); uint64_t ht_cas (hashtable_t *ht, void *key, uint64_t expected_val, uint64_t val); uint64_t ht_get (hashtable_t *ht, void *key); uint64_t ht_remove (hashtable_t *ht, void *key); @@ -14,15 +14,14 @@ uint64_t ht_count (hashtable_t *ht); void ht_print (hashtable_t *ht); void ht_free (hashtable_t *ht); -ht_iter_t *ht_iter_start (hashtable_t *ht, void *key); -ht_iter_t *ht_iter_next (ht_iter_t *iter); -uint64_t ht_iter_val (ht_iter_t *iter); -uint64_t ht_iter_key (ht_iter_t *iter); -void ht_iter_free (ht_iter_t *iter); +ht_iter_t * ht_iter_begin (hashtable_t *ht, void *key); +uint64_t ht_iter_next (ht_iter_t *iter, void **key_ptr); +void ht_iter_free (ht_iter_t *iter); static const map_impl_t ht_map_impl = { (map_alloc_t)ht_alloc, (map_cas_t)ht_cas, (map_get_t)ht_get, (map_remove_t)ht_remove, - (map_count_t)ht_count, (map_print_t)ht_print, (map_free_t)ht_free + (map_count_t)ht_count, (map_print_t)ht_print, (map_free_t)ht_free, (map_iter_begin_t)ht_iter_begin, + (map_iter_next_t)ht_iter_next, (map_iter_free_t)ht_iter_free }; #endif//HASHTABLE_H diff --git a/include/list.h b/include/list.h index e4cba2d..69e6814 100644 --- a/include/list.h +++ b/include/list.h @@ -15,14 +15,14 @@ void ll_print (list_t *ll); void ll_free (list_t *ll); void * ll_min_key (list_t *sl); -ll_iter_t *ll_iter_start (list_t *ll, void *key); -ll_iter_t *ll_iter_next (ll_iter_t *iter); -uint64_t ll_iter_val (ll_iter_t *iter); -void * ll_iter_key (ll_iter_t *iter); +ll_iter_t * ll_iter_begin (list_t *ll, void *key); +uint64_t ll_iter_next (ll_iter_t *iter, void **key_ptr); +void ll_iter_free (ll_iter_t *iter); static const map_impl_t ll_map_impl = { (map_alloc_t)ll_alloc, (map_cas_t)ll_cas, (map_get_t)ll_lookup, (map_remove_t)ll_remove, - (map_count_t)ll_count, (map_print_t)ll_print, (map_free_t)ll_free + (map_count_t)ll_count, (map_print_t)ll_print, (map_free_t)ll_free, (map_iter_begin_t)ll_iter_begin, + (map_iter_next_t)ll_iter_next, (map_iter_free_t)ll_iter_free }; #endif//LIST_H diff --git a/include/map.h b/include/map.h index 4d8b78f..27e8dae 100644 --- a/include/map.h +++ b/include/map.h @@ -4,18 +4,23 @@ #include "datatype.h" typedef struct map map_t; +typedef struct map_iter map_iter_t; typedef struct map_impl map_impl_t; -map_t * map_alloc (const map_impl_t *map_impl, const datatype_t *key_type); -uint64_t map_get (map_t *map, void *key); -uint64_t map_set (map_t *map, void *key, uint64_t new_val); -uint64_t map_add (map_t *map, void *key, uint64_t new_val); -uint64_t map_cas (map_t *map, void *key, uint64_t expected_val, uint64_t new_val); -uint64_t map_replace(map_t *map, void *key, uint64_t new_val); -uint64_t map_remove (map_t *map, void *key); -uint64_t map_count (map_t *map); -void map_print (map_t *map); -void map_free (map_t *map); +map_t * map_alloc (const map_impl_t *map_impl, const datatype_t *key_type); +uint64_t map_get (map_t *map, void *key); +uint64_t map_set (map_t *map, void *key, uint64_t new_val); +uint64_t map_add (map_t *map, void *key, uint64_t new_val); +uint64_t map_cas (map_t *map, void *key, uint64_t expected_val, uint64_t new_val); +uint64_t map_replace (map_t *map, void *key, uint64_t new_val); +uint64_t map_remove (map_t *map, void *key); +uint64_t map_count (map_t *map); +void map_print (map_t *map); +void map_free (map_t *map); + +map_iter_t * map_iter_begin (map_t *map, void *key); +uint64_t map_iter_next (map_iter_t *iter, void **key); +void map_iter_free (map_iter_t *iter); ///////////////////////////////////////////////////////////////////////////////////// @@ -24,12 +29,16 @@ void map_free (map_t *map); #define CAS_EXPECT_WHATEVER (-2) typedef void * (*map_alloc_t) (const datatype_t *); -typedef uint64_t (*map_cas_t) (void *, void *, uint64_t, uint64_t); -typedef uint64_t (*map_get_t) (void *, void *); -typedef uint64_t (*map_remove_t) (void *, void *); -typedef uint64_t (*map_count_t) (void *); -typedef void (*map_print_t) (void *); -typedef void (*map_free_t) (void *); +typedef uint64_t (*map_cas_t) (map_impl_t *, void *, uint64_t, uint64_t); +typedef uint64_t (*map_get_t) (map_impl_t *, void *); +typedef uint64_t (*map_remove_t) (map_impl_t *, void *); +typedef uint64_t (*map_count_t) (map_impl_t *); +typedef void (*map_print_t) (map_impl_t *); +typedef void (*map_free_t) (map_impl_t *); + +typedef map_iter_t * (*map_iter_begin_t) (map_impl_t *, void *); +typedef uint64_t (*map_iter_next_t) (map_iter_t *, void **); +typedef void (*map_iter_free_t) (map_iter_t *); struct map_impl { map_alloc_t alloc; @@ -39,6 +48,10 @@ struct map_impl { map_count_t count; map_print_t print; map_free_t free_; + + map_iter_begin_t iter_begin; + map_iter_next_t iter_next; + map_iter_free_t iter_free; }; #endif//MAP_H diff --git a/include/murmur.h b/include/murmur.h index 84d7135..1d79652 100644 --- a/include/murmur.h +++ b/include/murmur.h @@ -64,5 +64,42 @@ static inline unsigned int murmur32 (const char *key, int len) static inline unsigned int murmur32_8b (uint64_t key) { - return murmur32((char *)&key, 8); + // 'm' and 'r' are mixing constants generated offline. + // They're not really 'magic', they just happen to work well. + + const unsigned int m = 0x5bd1e995; + const int r = 24; + + // Initialize the hash to a 'random' value + unsigned int h = 8; + + const unsigned char *data = (const unsigned char *)key; + + uint32_t k1 = *(uint32_t *)&data; + data += 4; + uint32_t k2 = *(uint32_t *)&data; + + k1 *= m; + k1 ^= k1 >> r; + k1 *= m; + + k2 *= m; + k2 ^= k2 >> r; + k2 *= m; + + // Mix 4 bytes at a time into the hash + + h *= m; + h ^= k1; + h *= m; + h ^= k2; + + // Do a few final mixes of the hash to ensure the last few + // bytes are well-incorporated. + + h ^= h >> 13; + h *= m; + h ^= h >> 15; + + return h; } diff --git a/include/skiplist.h b/include/skiplist.h index cf70656..8df577a 100644 --- a/include/skiplist.h +++ b/include/skiplist.h @@ -6,7 +6,7 @@ typedef struct sl skiplist_t; typedef struct sl_iter sl_iter_t; -skiplist_t *sl_alloc (const datatype_t *key_type); +skiplist_t * sl_alloc (const datatype_t *key_type); uint64_t sl_cas (skiplist_t *sl, void *key, uint64_t expected_val, uint64_t new_val); uint64_t sl_lookup (skiplist_t *sl, void *key); uint64_t sl_remove (skiplist_t *sl, void *key); @@ -15,14 +15,14 @@ void sl_print (skiplist_t *sl); void sl_free (skiplist_t *sl); void * sl_min_key (skiplist_t *sl); -sl_iter_t *sl_iter_start (skiplist_t *sl, void *key); -sl_iter_t *sl_iter_next (sl_iter_t *iter); -uint64_t sl_iter_val (sl_iter_t *iter); -void * sl_iter_key (sl_iter_t *iter); +sl_iter_t * sl_iter_begin (skiplist_t *sl, void *key); +uint64_t sl_iter_next (sl_iter_t *iter, void **key_ptr); +void sl_iter_free (sl_iter_t *iter); static const map_impl_t sl_map_impl = { (map_alloc_t)sl_alloc, (map_cas_t)sl_cas, (map_get_t)sl_lookup, (map_remove_t)sl_remove, - (map_count_t)sl_count, (map_print_t)sl_print, (map_free_t)sl_free + (map_count_t)sl_count, (map_print_t)sl_print, (map_free_t)sl_free, (map_iter_begin_t)sl_iter_begin, + (map_iter_next_t)sl_iter_next, (map_iter_free_t)sl_iter_free }; #endif//SKIPLIST_H diff --git a/include/txn.h b/include/txn.h index fc6b691..339a3e5 100644 --- a/include/txn.h +++ b/include/txn.h @@ -7,18 +7,17 @@ #include "map.h" -typedef enum { TXN_REPEATABLE_READ, TXN_READ_COMMITTED, TXN_READ_ONLY } txn_type_e; typedef enum { TXN_RUNNING, TXN_VALIDATING, TXN_VALIDATED, TXN_ABORTED } txn_state_e; typedef struct txn txn_t; void txn_init (void); -txn_t * txn_begin (txn_type_e type, map_t *map); +txn_t * txn_begin (map_t *map); void txn_abort (txn_t *txn); txn_state_e txn_commit (txn_t *txn); -uint64_t tm_get (txn_t *txn, void *key); -void tm_set (txn_t *txn, void *key, uint64_t value); +uint64_t txn_map_get (txn_t *txn, void *key); +void txn_map_set (txn_t *txn, void *key, uint64_t value); #endif//TXN_H diff --git a/map/hashtable.c b/map/hashtable.c index b4d7a5d..a853b4c 100644 --- a/map/hashtable.c +++ b/map/hashtable.c @@ -447,7 +447,7 @@ int hti_help_copy (hti_t *hti) { int x = hti->copy_scan; TRACE("h1", "ht_cas: help copy. scan is %llu, size is %llu", x, 1<scale); - if (total_copied == (1 << hti->scale)) { + if (total_copied != (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) { @@ -464,8 +464,8 @@ int hti_help_copy (hti_t *hti) { } else { TRACE("h1", "ht_cas: help copy panic", 0, 0); // scan the whole table - limit = (1 << hti->scale); ent = hti->table; + limit = (1 << hti->scale); } // Copy the entries @@ -588,7 +588,8 @@ void ht_print (hashtable_t *ht) { } } -ht_iter_t *ht_iter_start (hashtable_t *ht, void *key) { +ht_iter_t *ht_iter_begin (hashtable_t *ht, void *key) { + assert(key == NULL); hti_t *hti = ht->hti; int rcount; do { @@ -613,44 +614,36 @@ ht_iter_t *ht_iter_start (hashtable_t *ht, void *key) { return iter; } -ht_iter_t *ht_iter_next (ht_iter_t *iter) { +uint64_t ht_iter_next (ht_iter_t *iter, void **key_ptr) { volatile entry_t *ent; uint64_t key; uint64_t val; uint64_t table_size = (1 << iter->hti->scale); do { - if (++iter->idx == table_size) { - ht_iter_free(iter); - return NULL; + iter->idx++; + if (iter->idx == table_size) { + return DOES_NOT_EXIST; } - ent = &iter->hti->table[++iter->idx]; + ent = &iter->hti->table[iter->idx]; key = ent->key; val = ent->val; } while (key == DOES_NOT_EXIST || val == DOES_NOT_EXIST || val == TOMBSTONE); - iter->key = key; + if (key_ptr) { + *key_ptr = (void *)key; + } if (val == COPIED_VALUE) { uint32_t hash = (iter->hti->ht->key_type == NULL) ? murmur32_8b(key) : iter->hti->ht->key_type->hash((void *)key); - iter->val = hti_get(iter->hti->next, (void *)ent->key, hash); - } else { - iter->val = val; - } + val = hti_get(iter->hti->next, (void *)ent->key, hash); + } - return iter; -} - -uint64_t ht_iter_val (ht_iter_t *iter) { - return iter->val; -} - -uint64_t ht_iter_key (ht_iter_t *iter) { - return iter->key; + return val; } void ht_iter_free (ht_iter_t *iter) { SYNC_ADD(&iter->hti->references, -1); + nbd_free(iter); } - diff --git a/map/list.c b/map/list.c index 9e66787..f2e9c82 100644 --- a/map/list.c +++ b/map/list.c @@ -307,29 +307,29 @@ void ll_print (list_t *ll) { printf("\n"); } -ll_iter_t *ll_iter_start (list_t *ll, void *key) { - node_t *item; - find_pred(NULL, &item, ll, key, FALSE); - return item; +ll_iter_t *ll_iter_begin (list_t *ll, void *key) { + node_t *iter = node_alloc(0,0); + find_pred(NULL, &iter->next, ll, key, FALSE); + return iter; } -ll_iter_t *ll_iter_next (ll_iter_t *iter) { +uint64_t ll_iter_next (ll_iter_t *iter, void **key_ptr) { assert(iter); - if (EXPECT_FALSE(!iter)) - return NULL; - - node_t *next = iter->next; - while (next != NULL && IS_TAGGED(next->next, TAG1)) { - next = (node_t *)STRIP_TAG(next->next, TAG1); + node_t *item = iter->next; + while (item != NULL && IS_TAGGED(item->next, TAG1)) { + item = (node_t *)STRIP_TAG(item->next, TAG1); } - - return next; -} - -uint64_t ll_iter_val (ll_iter_t *iter) { - return iter->val; + if (item == NULL) { + iter->next = NULL; + return DOES_NOT_EXIST; + } + iter->next = item->next; + if (key_ptr != NULL) { + *key_ptr = item->key; + } + return item->val; } -void *ll_iter_key (ll_iter_t *iter) { - return iter->key; +void ll_iter_free (ll_iter_t *iter) { + nbd_free(iter); } diff --git a/map/map.c b/map/map.c index 0db50bd..fcd9f83 100644 --- a/map/map.c +++ b/map/map.c @@ -14,6 +14,11 @@ struct map { void *data; }; +struct map_iter { + const map_impl_t *impl; + void *state; +}; + map_t *map_alloc (const map_impl_t *map_impl, const datatype_t *key_type) { map_t *map = nbd_malloc(sizeof(map_t)); map->impl = map_impl; @@ -56,3 +61,19 @@ uint64_t map_replace(map_t *map, void *key, uint64_t new_val) { uint64_t map_remove (map_t *map, void *key) { return map->impl->remove(map->data, key); } + +map_iter_t * map_iter_begin (map_t *map, void *key) { + map_iter_t *iter = nbd_malloc(sizeof(map_iter_t)); + iter->impl = map->impl; + iter->state = map->impl->iter_begin(map->data, key); + return iter; +} + +uint64_t map_iter_next (map_iter_t *iter, void **key_ptr) { + return iter->impl->iter_next(iter->state, key_ptr); +} + +void map_iter_free (map_iter_t *iter) { + iter->impl->iter_free(iter->state); + nbd_free(iter); +} diff --git a/map/skiplist.c b/map/skiplist.c index 16f7538..1f608b4 100644 --- a/map/skiplist.c +++ b/map/skiplist.c @@ -475,29 +475,29 @@ void sl_print (skiplist_t *sl) { } } -sl_iter_t *sl_iter_start (skiplist_t *sl, void *key) { - node_t *item; - find_preds(NULL, &item, 0, sl, key, FALSE); - return item; +sl_iter_t *sl_iter_begin (skiplist_t *sl, void *key) { + node_t *iter = node_alloc(0, 0, 0); + find_preds(NULL, &iter->next[0], 0, sl, key, FALSE); + return iter; } -sl_iter_t *sl_iter_next (sl_iter_t *iter) { +uint64_t sl_iter_next (sl_iter_t *iter, void **key_ptr) { assert(iter); - if (EXPECT_FALSE(!iter)) - return NULL; - - node_t *next = iter->next[0]; - while (next != NULL && IS_TAGGED(next->next[0], TAG1)) { - next = (node_t *)STRIP_TAG(next->next[0], TAG1); + node_t *item = iter->next[0]; + while (item != NULL && IS_TAGGED(item->next[0], TAG1)) { + item = (node_t *)STRIP_TAG(item->next[0], TAG1); } - - return next; -} - -uint64_t sl_iter_val (sl_iter_t *iter) { - return iter->val; + if (item == NULL) { + iter->next[0] = NULL; + return DOES_NOT_EXIST; + } + iter->next[0] = item->next[0]; + if (key_ptr != NULL) { + *key_ptr = item->key; + } + return item->val; } -void *sl_iter_key (sl_iter_t *iter) { - return iter->key; +void sl_iter_free (sl_iter_t *iter) { + nbd_free(iter); } diff --git a/test/map_test1.c b/test/map_test1.c index 6639359..f380918 100644 --- a/test/map_test1.c +++ b/test/map_test1.c @@ -13,7 +13,7 @@ #define NUM_ITERATIONS 10000000 -#define TEST_STRING_KEYS +//#define TEST_STRING_KEYS static volatile int wait_; static long num_threads_; diff --git a/test/map_test2.c b/test/map_test2.c index 51b17b3..1ba4e42 100644 --- a/test/map_test2.c +++ b/test/map_test2.c @@ -19,7 +19,7 @@ #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y) -#define TEST_STRING_KEYS +//#define TEST_STRING_KEYS typedef struct worker_data { int id; @@ -30,8 +30,18 @@ typedef struct worker_data { static const map_impl_t *map_type_; +static uint64_t iterator_size (map_t *map) { + map_iter_t *iter = map_iter_begin(map, NULL); + uint64_t count = 0; + while (map_iter_next(iter, NULL) != DOES_NOT_EXIST) { + count++; + } + map_iter_free(iter); + return count; +} + // Test some basic stuff; add a few keys, remove a few keys -void simple (CuTest* tc) { +void basic_test (CuTest* tc) { #ifdef TEST_STRING_KEYS map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING); @@ -50,29 +60,37 @@ void simple (CuTest* tc) { ASSERT_EQUAL( 0, map_count (map) ); ASSERT_EQUAL( DOES_NOT_EXIST, map_add (map, k1,10) ); ASSERT_EQUAL( 1, map_count (map) ); + ASSERT_EQUAL( 1, iterator_size(map) ); ASSERT_EQUAL( DOES_NOT_EXIST, map_add (map, k2,20) ); ASSERT_EQUAL( 2, map_count (map) ); + ASSERT_EQUAL( 2, iterator_size(map) ); ASSERT_EQUAL( 20, map_get (map, k2) ); ASSERT_EQUAL( 10, map_set (map, k1,11) ); ASSERT_EQUAL( 20, map_set (map, k2,21) ); ASSERT_EQUAL( 2, map_count (map) ); + ASSERT_EQUAL( 2, iterator_size(map) ); ASSERT_EQUAL( 21, map_add (map, k2,22) ); ASSERT_EQUAL( 11, map_remove (map, k1) ); ASSERT_EQUAL( DOES_NOT_EXIST, map_get (map, k1) ); ASSERT_EQUAL( 1, map_count (map) ); + ASSERT_EQUAL( 1, iterator_size(map) ); ASSERT_EQUAL( DOES_NOT_EXIST, map_remove (map, k1) ); ASSERT_EQUAL( 21, map_remove (map, k2) ); ASSERT_EQUAL( 0, map_count (map) ); + ASSERT_EQUAL( 0, iterator_size(map) ); ASSERT_EQUAL( DOES_NOT_EXIST, map_remove (map, k2) ); ASSERT_EQUAL( DOES_NOT_EXIST, map_remove (map, k3) ); ASSERT_EQUAL( 0, map_count (map) ); + ASSERT_EQUAL( 0, iterator_size(map) ); ASSERT_EQUAL( DOES_NOT_EXIST, map_add (map, k4,40) ); ASSERT_EQUAL( 40, map_get (map, k4) ); ASSERT_EQUAL( 1, map_count (map) ); + ASSERT_EQUAL( 1, iterator_size(map) ); ASSERT_EQUAL( 40, map_remove (map, k4) ); ASSERT_EQUAL( DOES_NOT_EXIST, map_get (map, k4) ); ASSERT_EQUAL( 0, map_count (map) ); + ASSERT_EQUAL( 0, iterator_size(map) ); ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, k4,10) ); ASSERT_EQUAL( DOES_NOT_EXIST, map_get (map, k4) ); @@ -82,6 +100,7 @@ void simple (CuTest* tc) { ASSERT_EQUAL( 41, map_remove (map, k4) ); ASSERT_EQUAL( DOES_NOT_EXIST, map_get (map, k4) ); ASSERT_EQUAL( 0, map_count (map) ); + ASSERT_EQUAL( 0, iterator_size(map) ); ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, k2,20) ); ASSERT_EQUAL( DOES_NOT_EXIST, map_get (map, k2) ); @@ -93,11 +112,14 @@ void simple (CuTest* tc) { ASSERT_EQUAL( 21, map_remove (map, k2) ); ASSERT_EQUAL( DOES_NOT_EXIST, map_get (map, k2) ); ASSERT_EQUAL( 0, map_count (map) ); + ASSERT_EQUAL( 0, iterator_size(map) ); map_free(map); - // In a quiecent state; it is safe to free. - rcu_update(); + rcu_update(); // In a quiecent state. +#ifdef TEST_STRING_KEYS + nbd_free(k1); nbd_free(k2); nbd_free(k3); nbd_free(k4); +#endif } void *add_remove_worker (void *arg) { @@ -125,8 +147,8 @@ void *add_remove_worker (void *arg) { key = (void *)i; #endif TRACE("t0", "test map_add() iteration (%llu, %llu)", j, i); - CuAssertIntEquals_Msg(tc, (void *)i, DOES_NOT_EXIST, map_add(map, key, d+1) ); - rcu_update(); + ASSERT_EQUAL(DOES_NOT_EXIST, map_add(map, key, d+1) ); + rcu_update(); // In a quiecent state. } for (uint64_t i = d+1; i < iters; i+=2) { #ifdef TEST_STRING_KEYS @@ -136,15 +158,15 @@ void *add_remove_worker (void *arg) { key = (void *)i; #endif TRACE("t0", "test map_remove() iteration (%llu, %llu)", j, i); - CuAssertIntEquals_Msg(tc, (void *)i, d+1, map_remove(map, key) ); - rcu_update(); + ASSERT_EQUAL(d+1, map_remove(map, key) ); + rcu_update(); // In a quiecent state. } } return NULL; } // Do some simple concurrent testing -void add_remove (CuTest* tc) { +void concurrent_add_remove_test (CuTest* tc) { pthread_t thread[2]; worker_data_t wd[2]; @@ -181,20 +203,101 @@ void add_remove (CuTest* tc) { // In the end, all members should be removed ASSERT_EQUAL( 0, map_count(map) ); + ASSERT_EQUAL( 0, iterator_size(map) ); // In a quiecent state; it is safe to free. map_free(map); } -void *inserter_worker (void *arg) { - //pthread_t thread[NUM_THREADS]; +void basic_iteration_test (CuTest* tc) { +#ifdef TEST_STRING_KEYS + map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING); + nstring_t *k1 = ns_alloc(3); strcpy(k1->data, "k1"); + nstring_t *k2 = ns_alloc(3); strcpy(k1->data, "k2"); + nstring_t *x_k; + nstring_t *y_k; +#else + map_t *map = map_alloc(map_type_, NULL); + void *k1 = (void *)1; + void *k2 = (void *)2; + void *x_k; + void *y_k; +#endif - //map_t *map = map_alloc(map_type_); - return NULL; + ASSERT_EQUAL( DOES_NOT_EXIST, map_add (map, k1,1) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_add (map, k2,2) ); + + uint64_t x_v, y_v; + map_iter_t *iter = map_iter_begin(map, NULL); + x_v = map_iter_next(iter, &x_k); + y_v = map_iter_next(iter, &y_k); + ASSERT_EQUAL( DOES_NOT_EXIST, map_iter_next(iter, NULL) ); + map_iter_free(iter); +#ifdef TEST_STRING_KEYS + ASSERT_EQUAL( TRUE, (ns_cmp(x_k, k1) == 0 && x_v == 1) || (ns_cmp(y_k, k1) == 0 && y_v == 1) ); + ASSERT_EQUAL( TRUE, (ns_cmp(x_k, k2) == 0 && x_v == 2) || (ns_cmp(y_k, k2) == 0 && y_v == 2) ); + nbd_free(k1); + nbd_free(k2); +#else + ASSERT_EQUAL( TRUE, (x_k == k1 && x_v == 1) || (y_k == k1 && y_v == 1) ); + ASSERT_EQUAL( TRUE, (x_k == k2 && x_v == 2) || (y_k == k2 && y_v == 2) ); +#endif + + map_free(map); } -// Concurrent insertion -void concurrent_insert (CuTest* tc) { +void big_iteration_test (CuTest* tc) { + static const int n = 10000; + +#ifdef TEST_STRING_KEYS + map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING); + nstring_t *key = ns_alloc(9); + nstring_t *k3 = ns_alloc(3); strcpy(k1->data, "k3"); + nstring_t *k4 = ns_alloc(3); strcpy(k1->data, "k4"); +#else + map_t *map = map_alloc(map_type_, NULL); + void *k3 = (void *)3; + void *k4 = (void *)4; + void *key; +#endif + + for (size_t i = 1; i <= n; ++i) { +#ifdef TEST_STRING_KEYS + memset(key->data, 0, key->len); + snprintf(key->data, key->len, "k%llu", i); +#else + key = (void *)i; +#endif + ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, key) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_set(map, key, i) ); + ASSERT_EQUAL( i, map_get(map, key) ); + rcu_update(); // In a quiecent state. + } + + ASSERT_EQUAL( n, map_count(map) ); + ASSERT_EQUAL( n, iterator_size(map) ); + + uint64_t sum = 0; + uint64_t val; + map_iter_t *iter = map_iter_begin(map, NULL); + while ((val = map_iter_next(iter, NULL)) != DOES_NOT_EXIST) { + sum += val; + } + map_iter_free(iter); + ASSERT_EQUAL(n*(n+1)/2, sum); + ASSERT_EQUAL(3, map_remove(map, k3)); + ASSERT_EQUAL(4, map_remove(map, k4)); + sum = 0; + iter = map_iter_begin(map, NULL); + while ((val = map_iter_next(iter, NULL)) != DOES_NOT_EXIST) { + sum += val; + } + map_iter_free(iter); + ASSERT_EQUAL(n*(n+1)/2 - (3+4), sum); + +#ifdef TEST_STRING_KEYS + nbd_free(key); +#endif } int main (void) { @@ -210,8 +313,10 @@ int main (void) { CuString *output = CuStringNew(); CuSuite* suite = CuSuiteNew(); - SUITE_ADD_TEST(suite, simple); - SUITE_ADD_TEST(suite, add_remove); + SUITE_ADD_TEST(suite, basic_test); + SUITE_ADD_TEST(suite, concurrent_add_remove_test); + SUITE_ADD_TEST(suite, basic_iteration_test); + SUITE_ADD_TEST(suite, big_iteration_test); CuSuiteRun(suite); CuSuiteDetails(suite, output); diff --git a/test/txn_test.c b/test/txn_test.c index b721f2d..80b8f93 100644 --- a/test/txn_test.c +++ b/test/txn_test.c @@ -11,15 +11,15 @@ void test1 (CuTest* tc) { map_t *map = map_alloc(&ht_map_impl, NULL); - txn_t *t1 = txn_begin(TXN_REPEATABLE_READ, map); - txn_t *t2 = txn_begin(TXN_REPEATABLE_READ, map); + txn_t *t1 = txn_begin(map); + txn_t *t2 = txn_begin(map); void *k1 = (void *)1; - tm_set(t1, k1, 2); - tm_set(t1, k1, 3); - ASSERT_EQUAL( DOES_NOT_EXIST, tm_get(t2, k1) ); - tm_set(t2, k1, 4); - ASSERT_EQUAL( 3, tm_get(t1, k1) ); - ASSERT_EQUAL( 4, tm_get(t2, k1) ); + txn_map_set(t1, k1, 2); + txn_map_set(t1, k1, 3); + ASSERT_EQUAL( DOES_NOT_EXIST, txn_map_get(t2, k1) ); + txn_map_set(t2, k1, 4); + ASSERT_EQUAL( 3, txn_map_get(t1, k1) ); + ASSERT_EQUAL( 4, txn_map_get(t2, k1) ); ASSERT_EQUAL( TXN_VALIDATED, txn_commit(t2)); ASSERT_EQUAL( TXN_ABORTED, txn_commit(t1)); } diff --git a/todo b/todo index fef96ad..807a31a 100644 --- a/todo +++ b/todo @@ -1,17 +1,26 @@ -- make rcu try yielding when its buffer gets full, instead of throwing an assert + fix makefile to compute dependency info as a side-effect of compilation (-MF) -- investigate 16 byte CAS; ht can store GUIDs inline instead of pointers to actual keys -- testing, testing, testing + support integer keys for ht -- validate arguments to interface functions + optimize tracing code, still too much overhead + use NULL instead of a sentinal node in skiplist and list + make the interfaces for all data structures consistent + make list and skiplist use string keys + optimize integer keys + ht_print() -- iterators -- characterize performance of data structures -- experiment with the performance impact of not passing the hash between functions -- experiment with embedding keys in the list/skiplist nodes ++ iterators +- make rcu yield when its buffer gets full instead of throwing an assert +- alternate memory reclamation schemes, hazard pointers and/or reference count +- investigate 16 byte CAS; ht can store GUIDs inline instead of pointers to actual keys +- document usage +- document algorithms +- port tests from lib-high-scale +- 32 bit version of hashtable +- verify list and skiplist work on 32 bit platforms +- transaction tests +- validate the arguments to interface functions +- shortcut from write-set to entries/nodes +- use a shared scan for write-set validation, similar to ht copy logic +- characterize the performance of hashtable, list and skiplist +- experiment with the performance impact of not passing the hash between functions in ht +- experiment with embedding the keys in the list/skiplist nodes - allow values of 0 to be inserted into maps (change DOES_NOT_EXIST to something else) +- see if it's possible to rename nbd_malloc to malloc diff --git a/txn/txn.c b/txn/txn.c index 26e0209..bb304b3 100644 --- a/txn/txn.c +++ b/txn/txn.c @@ -32,7 +32,6 @@ struct txn { uint32_t writes_size; uint32_t writes_count; uint32_t writes_scan; - txn_type_e type; txn_state_e state; }; @@ -52,7 +51,7 @@ void txn_init (void) { // If we encounter a potential conflict with a transaction that is in the process of validating, we help it // complete validating. It must be finished before we can decide to rollback or commit. // -static txn_state_e tm_validate_key (txn_t *txn, void *key) { +static txn_state_e validate_key (txn_t *txn, void *key) { assert(txn->state != TXN_RUNNING); update_t *update = (update_t *) map_get(txn->map, key); @@ -123,7 +122,7 @@ static txn_state_e txn_validate (txn_t *txn) { } for (i = 0; i < txn->writes_count; ++i) { - txn_state_e s = tm_validate_key(txn, txn->writes[i].key); + txn_state_e s = validate_key(txn, txn->writes[i].key); if (s == TXN_ABORTED) { txn->state = TXN_ABORTED; break; @@ -152,17 +151,14 @@ static update_t *alloc_update_rec (void) { return u; } -txn_t *txn_begin (txn_type_e type, map_t *map) { +txn_t *txn_begin (map_t *map) { txn_t *txn = (txn_t *)nbd_malloc(sizeof(txn_t)); memset(txn, 0, sizeof(txn_t)); - txn->type = type; txn->wv = UNDETERMINED_VERSION; txn->state = TXN_RUNNING; txn->map = map; - if (type != TXN_READ_ONLY) { - txn->writes = nbd_malloc(sizeof(*txn->writes) * INITIAL_WRITES_SIZE); - txn->writes_size = INITIAL_WRITES_SIZE; - } + txn->writes = nbd_malloc(sizeof(*txn->writes) * INITIAL_WRITES_SIZE); + txn->writes_size = INITIAL_WRITES_SIZE; // acquire the read version for txn. must be careful to avoid a race do { @@ -237,7 +233,7 @@ txn_state_e txn_commit (txn_t *txn) { } // Get most recent committed version prior to our read version. -uint64_t tm_get (txn_t *txn, void *key) { +uint64_t txn_map_get (txn_t *txn, void *key) { if (txn->state != TXN_RUNNING) return ERROR_TXN_NOT_RUNNING; @@ -349,7 +345,7 @@ uint64_t tm_get (txn_t *txn, void *key) { return value; } -void tm_set (txn_t *txn, void *key, uint64_t value) { +void txn_map_set (txn_t *txn, void *key, uint64_t value) { if (txn->state != TXN_RUNNING) return; // TODO: return some sort of error code -- 2.40.0