From: jdybnis Date: Thu, 4 Dec 2008 06:57:19 +0000 (+0000) Subject: all structures are parameterized by the datatype for the key X-Git-Url: https://pd.if.org/git/?p=nbds;a=commitdiff_plain;h=11572afcaf218cfcbb8e9747f22739f75252c4f4 all structures are parameterized by the datatype for the key --- diff --git a/runtime/nstring.c b/datatype/nstring.c similarity index 86% rename from runtime/nstring.c rename to datatype/nstring.c index a3fdd1f..f4f6f38 100644 --- a/runtime/nstring.c +++ b/datatype/nstring.c @@ -3,6 +3,8 @@ #include "murmur.h" #include "mem.h" +const datatype_t DATATYPE_NSTRING = { (cmp_fun_t)ns_cmp, (hash_fun_t)ns_hash, (clone_fun_t)ns_dup }; + nstring_t *ns_alloc (uint32_t len) { nstring_t *ns = nbd_malloc(sizeof(nstring_t) + len); ns->len = len; diff --git a/include/datatype.h b/include/datatype.h new file mode 100644 index 0000000..e0085be --- /dev/null +++ b/include/datatype.h @@ -0,0 +1,14 @@ +#ifndef DATATYPE_H +#define DATATYPE_H + +typedef int (*cmp_fun_t) (void *, void *); +typedef void * (*clone_fun_t) (void *); +typedef uint32_t (*hash_fun_t) (void *); + +typedef struct datatype { + cmp_fun_t cmp; + hash_fun_t hash; + clone_fun_t clone; +} datatype_t; + +#endif//DATATYPE_H diff --git a/include/map.h b/include/map.h index 71d0dde..42a5a1d 100644 --- a/include/map.h +++ b/include/map.h @@ -1,19 +1,17 @@ #ifndef MAP_H #define MAP_H +#include "datatype.h" + typedef struct map map_t; typedef const struct map_impl *map_type_t; -typedef int (*cmp_fun_t) (void *, void *); -typedef void * (*clone_fun_t) (void *); -typedef uint32_t (*hash_fun_t) (void *); - extern map_type_t MAP_TYPE_HASHTABLE; extern map_type_t MAP_TYPE_SKIPLIST; extern map_type_t MAP_TYPE_LIST; -map_t * map_alloc (map_type_t map_type, cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun); +map_t * map_alloc (map_type_t map_type, 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); diff --git a/include/nstring.h b/include/nstring.h index 5d6fc89..6114171 100644 --- a/include/nstring.h +++ b/include/nstring.h @@ -1,6 +1,9 @@ #ifndef NSTRING_H #define NSTRING_H +#include "common.h" +#include "datatype.h" + typedef struct nstring { uint32_t len; char data[]; @@ -11,4 +14,6 @@ int ns_cmp (const nstring_t *ns1, const nstring_t *ns2); uint32_t ns_hash (const nstring_t *ns); nstring_t * ns_dup (const nstring_t *ns); +extern const datatype_t DATATYPE_NSTRING; + #endif//NSTRING_H diff --git a/makefile b/makefile index 21fa6d9..ba6ad31 100644 --- a/makefile +++ b/makefile @@ -10,7 +10,7 @@ INCS := $(addprefix -I, include) TESTS := output/map_test1 output/map_test2 output/rcu_test output/txn_test EXES := $(TESTS) -RUNTIME_SRCS := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c runtime/nstring.c +RUNTIME_SRCS := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c datatype/nstring.c MAP_SRCS := map/map.c map/list.c map/skiplist.c map/hashtable.c rcu_test_SRCS := $(RUNTIME_SRCS) test/rcu_test.c diff --git a/map/hashtable.c b/map/hashtable.c index 1039ff0..da5adae 100644 --- a/map/hashtable.c +++ b/map/hashtable.c @@ -37,10 +37,8 @@ typedef struct hti { } hti_t; struct ht { - hti_t *hti; - cmp_fun_t cmp_fun; - hash_fun_t hash_fun; - clone_fun_t clone_fun; + hti_t *hti; + const datatype_t *key_type; }; static const map_impl_t ht_map_impl = { @@ -93,13 +91,13 @@ static volatile entry_t *hti_lookup (hti_t *hti, void *key, uint32_t key_hash, i uint64_t ent_key = ent->key; if (ent_key == DOES_NOT_EXIST) { TRACE("h1", "hti_lookup: entry %p for key %p is empty", ent, - (hti->ht->clone_fun == NULL) ? (void *)ent_key : GET_PTR(ent_key)); + (hti->ht->key_type == NULL) ? (void *)ent_key : GET_PTR(ent_key)); *is_empty = 1; // indicate an empty so the caller avoids an expensive key compare return ent; } // Compare with the key in the entry. - if (EXPECT_TRUE(hti->ht->cmp_fun == NULL)) { + if (EXPECT_TRUE(hti->ht->key_type == NULL)) { // fast path for integer keys if (ent_key == (uint64_t)key) { TRACE("h1", "hti_lookup: found entry %p with key %p", ent, ent_key); @@ -109,7 +107,7 @@ static volatile entry_t *hti_lookup (hti_t *hti, void *key, uint32_t key_hash, i // The key in is made up of two parts. The 48 low-order bits are a pointer. The // high-order 16 bits are taken from the hash. The bits from the hash are used as a // quick check to rule out non-equal keys without doing a complete compare. - if ((key_hash >> 16) == (ent_key >> 48) && hti->ht->cmp_fun(GET_PTR(ent_key), key) == 0) { + if ((key_hash >> 16) == (ent_key >> 48) && hti->ht->key_type->cmp(GET_PTR(ent_key), key) == 0) { TRACE("h1", "hti_lookup: found entry %p with key %p", ent, GET_PTR(ent_key)); return ent; } @@ -187,7 +185,7 @@ static int hti_copy_entry (hti_t *ht1, volatile entry_t *ht1_ent, uint32_t key_h assert(ht1->next); assert(ht2); assert(ht1_ent >= ht1->table && ht1_ent < ht1->table + (1 << ht1->scale)); - assert(key_hash == 0 || ht1->ht->hash_fun == NULL || (key_hash >> 16) == (ht1_ent->key >> 48)); + assert(key_hash == 0 || ht1->ht->key_type == NULL || (key_hash >> 16) == (ht1_ent->key >> 48)); uint64_t ht1_ent_val = ht1_ent->val; if (EXPECT_FALSE(ht1_ent_val == COPIED_VALUE)) { @@ -219,13 +217,13 @@ static int hti_copy_entry (hti_t *ht1, volatile entry_t *ht1_ent, uint32_t key_h // Install the key in the new table. uint64_t ht1_ent_key = ht1_ent->key; - void *key = (ht1->ht->hash_fun == NULL) ? (void *)ht1_ent_key : GET_PTR(ht1_ent_key); + void *key = (ht1->ht->key_type == NULL) ? (void *)ht1_ent_key : GET_PTR(ht1_ent_key); // The old table's dead entries don't need to be copied to the new table, but their keys need to be freed. assert(COPIED_VALUE == TAG_VALUE(TOMBSTONE)); if (ht1_ent_val == TOMBSTONE) { TRACE("h1", "hti_copy_entry: entry %p old value was deleted, now freeing key %p", ht1_ent, key); - if (EXPECT_FALSE(ht1->ht->clone_fun != NULL)) { + if (EXPECT_FALSE(ht1->ht->key_type != NULL)) { nbd_defer_free(key); } return TRUE; @@ -234,7 +232,7 @@ static int hti_copy_entry (hti_t *ht1, volatile entry_t *ht1_ent, uint32_t key_h // We use 0 to indicate that is uninitiallized. Occasionally the key's hash will really be 0 and we // waste time recomputing it every time. It is rare enough (1 in 65k) that it won't hurt performance. if (key_hash == 0) { - key_hash = (ht1->ht->hash_fun == NULL) ? murmur32_8b(ht1_ent_key) : ht1->ht->hash_fun(key); + key_hash = (ht1->ht->key_type == NULL) ? murmur32_8b(ht1_ent_key) : ht1->ht->key_type->hash(key); } int ht2_ent_is_empty; @@ -328,8 +326,8 @@ static uint64_t hti_cas (hti_t *hti, void *key, uint32_t key_hash, uint64_t expe return DOES_NOT_EXIST; // Allocate . - uint64_t new_key = (uint64_t)((hti->ht->clone_fun == NULL) ? key : hti->ht->clone_fun(key)); - if (EXPECT_FALSE(hti->ht->hash_fun != NULL)) { + uint64_t new_key = (uint64_t)((hti->ht->key_type == NULL) ? key : hti->ht->key_type->clone(key)); + if (EXPECT_FALSE(hti->ht->key_type != NULL)) { // Combine pointer with bits from its hash new_key = ((uint64_t)(key_hash >> 16) << 48) | new_key; } @@ -341,8 +339,8 @@ static uint64_t hti_cas (hti_t *hti, void *key, uint32_t key_hash, uint64_t expe if (old_ent_key != DOES_NOT_EXIST) { TRACE("h0", "hti_cas: lost race to install key %p in entry %p", new_key, ent); TRACE("h0", "hti_cas: found %p instead of NULL", - (hti->ht->clone_fun != NULL) ? (void *)old_ent_key : GET_PTR(old_ent_key), 0); - if (hti->ht->clone_fun != NULL) { + (hti->ht->key_type == NULL) ? (void *)old_ent_key : GET_PTR(old_ent_key), 0); + if (hti->ht->key_type != NULL) { nbd_free(GET_PTR(new_key)); } return hti_cas(hti, key, key_hash, expected, new); // tail-call @@ -351,7 +349,7 @@ static uint64_t hti_cas (hti_t *hti, void *key, uint32_t key_hash, uint64_t expe } TRACE("h0", "hti_cas: entry for key %p is %p", - (hti->ht->clone_fun != NULL) ? (void *)ent->key : GET_PTR(ent->key), ent); + (hti->ht->key_type == NULL) ? (void *)ent->key : GET_PTR(ent->key), ent); // If the entry is in the middle of a copy, the copy must be completed first. uint64_t ent_val = ent->val; @@ -437,7 +435,7 @@ static uint64_t hti_get (hti_t *hti, void *key, uint32_t key_hash) { // uint64_t ht_get (hashtable_t *ht, void *key) { - uint32_t hash = (ht->hash_fun == NULL) ? murmur32_8b((uint64_t)key) : ht->hash_fun(key); + uint32_t hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash(key); return hti_get(ht->hti, key, hash); } @@ -498,7 +496,7 @@ uint64_t ht_cas (hashtable_t *ht, void *key, uint64_t expected_val, uint64_t new } uint64_t old_val; - uint32_t key_hash = (ht->hash_fun == NULL) ? murmur32_8b((uint64_t)key) : ht->hash_fun(key); + uint32_t key_hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash(key); while ((old_val = hti_cas(hti, key, key_hash, expected_val, new_val)) == COPIED_VALUE) { assert(hti->next); hti = hti->next; @@ -512,7 +510,7 @@ uint64_t ht_cas (hashtable_t *ht, void *key, uint64_t expected_val, uint64_t new uint64_t ht_remove (hashtable_t *ht, void *key) { hti_t *hti = ht->hti; uint64_t val; - uint32_t key_hash = (ht->hash_fun == NULL) ? murmur32_8b((uint64_t)key) : ht->hash_fun(key); + uint32_t key_hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash(key); do { val = hti_cas(hti, key, key_hash, CAS_EXPECT_WHATEVER, TOMBSTONE); if (val != COPIED_VALUE) @@ -535,11 +533,9 @@ uint64_t ht_count (hashtable_t *ht) { } // Allocate and initialize a new hash table. -hashtable_t *ht_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun) { +hashtable_t *ht_alloc (const datatype_t *key_type) { hashtable_t *ht = nbd_malloc(sizeof(hashtable_t)); - ht->cmp_fun = cmp_fun; - ht->hash_fun = hash_fun; - ht->clone_fun = clone_fun; + ht->key_type = key_type; ht->hti = (hti_t *)hti_alloc(ht, MIN_SCALE); return ht; } @@ -550,7 +546,7 @@ void ht_free (hashtable_t *ht) { do { for (uint32_t i = 0; i < (1 << hti->scale); ++i) { assert(hti->table[i].val == COPIED_VALUE || !IS_TAGGED(hti->table[i].val)); - if (ht->clone_fun != NULL && hti->table[i].key != DOES_NOT_EXIST) { + if (ht->key_type != NULL && hti->table[i].key != DOES_NOT_EXIST) { nbd_free(GET_PTR(hti->table[i].key)); } } diff --git a/map/list.c b/map/list.c index 979c91e..f7a9cd4 100644 --- a/map/list.c +++ b/map/list.c @@ -21,8 +21,7 @@ typedef struct node { struct ll { node_t *head; - cmp_fun_t cmp_fun; - clone_fun_t clone_fun; + const datatype_t *key_type; }; static const map_impl_t ll_map_impl = { @@ -39,10 +38,9 @@ static node_t *node_alloc (void *key, uint64_t val) { return item; } -list_t *ll_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun) { +list_t *ll_alloc (const datatype_t *key_type) { list_t *ll = (list_t *)nbd_malloc(sizeof(list_t)); - ll->cmp_fun = cmp_fun; - ll->clone_fun = clone_fun; + ll->key_type = key_type; ll->head = node_alloc(NULL, 0); ll->head->next = NULL; return ll; @@ -100,7 +98,7 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, void *ke TRACE("l3", "find_pred: now current item is %p next is %p", item, next); // The thread that completes the unlink should free the memory. - if (ll->clone_fun != NULL) { + if (ll->key_type != NULL) { nbd_defer_free((void*)other->key); } nbd_defer_free(other); @@ -123,10 +121,10 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, void *ke TRACE("l4", "find_pred: key %p val %p", item->key, item->val); int d; - if (EXPECT_TRUE(ll->cmp_fun == NULL)) { + if (EXPECT_TRUE(ll->key_type == NULL)) { d = (uint64_t)item->key - (uint64_t)key; } else { - d = ll->cmp_fun(item->key, key); + d = ll->key_type->cmp(item->key, key); } // If we reached the key (or passed where it should be), we found the right predesssor @@ -195,7 +193,7 @@ uint64_t ll_cas (list_t *ll, void *key, uint64_t expectation, uint64_t new_val) // 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); - void *new_key = (ll->clone_fun == NULL) ? key : ll->clone_fun(key); + void *new_key = (ll->key_type == NULL) ? key : ll->key_type->clone(key); node_t *new_item = node_alloc(new_key, new_val); node_t *next = new_item->next = old_item; node_t *other = SYNC_CAS(&pred->next, next, new_item); @@ -206,7 +204,7 @@ uint64_t ll_cas (list_t *ll, void *key, uint64_t expectation, uint64_t new_val) // Lost a race. Failed to insert the new item into the list. TRACE("l1", "ll_cas: lost a race. CAS failed. expected pred's link to be %p but found %p", next, other); - if (ll->clone_fun != NULL) { + if (ll->key_type != NULL) { nbd_free(new_key); } nbd_free(new_item); @@ -284,7 +282,7 @@ uint64_t ll_remove (list_t *ll, void *key) { } // The thread that completes the unlink should free the memory. - if (ll->clone_fun != NULL) { + if (ll->key_type != NULL) { nbd_defer_free(item->key); } nbd_defer_free(item); diff --git a/map/map.c b/map/map.c index c4749b3..6602a9b 100644 --- a/map/map.c +++ b/map/map.c @@ -15,11 +15,11 @@ struct map { void *data; }; -map_t *map_alloc (map_type_t map_type, cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun) { +map_t *map_alloc (map_type_t map_type, const datatype_t *key_type) { const map_impl_t *map_impl = map_type; map_t *map = nbd_malloc(sizeof(map_t)); map->impl = map_impl; - map->data = map->impl->alloc(cmp_fun, hash_fun, clone_fun); + map->data = map->impl->alloc(key_type); return map; } diff --git a/map/mlocal.h b/map/mlocal.h index 1dae928..f7de2ac 100644 --- a/map/mlocal.h +++ b/map/mlocal.h @@ -1,13 +1,13 @@ #ifndef MLOCAL_H #define MLOCAL_H -#include "map.h" +#include "datatype.h" #define CAS_EXPECT_DOES_NOT_EXIST ( 0) #define CAS_EXPECT_EXISTS (-1) #define CAS_EXPECT_WHATEVER (-2) -typedef void * (*map_alloc_t) (cmp_fun_t, hash_fun_t, clone_fun_t); +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 *); @@ -29,9 +29,9 @@ typedef struct ht hashtable_t; typedef struct sl skiplist_t; typedef struct ll list_t; -hashtable_t * ht_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun); -skiplist_t * sl_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun); -list_t * ll_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun); +hashtable_t * ht_alloc (const datatype_t *key_type); +skiplist_t * sl_alloc (const datatype_t *key_type); +list_t * ll_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); diff --git a/map/skiplist.c b/map/skiplist.c index 66bfb2d..ad05dd1 100644 --- a/map/skiplist.c +++ b/map/skiplist.c @@ -9,9 +9,12 @@ * See also Kir Fraser's dissertation "Practical Lock Freedom". * 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 won't work correctly on platforms with weaker memory - * models if you don't add memory barriers in the right places. + * I've generalized the data structure to support update operations like set() and CAS() in addition to + * the normal add() and remove() operations. + * + * Warning: This code is written for the x86 memory-model. The algorithim depends on certain stores + * and loads being ordered. This code won't work correctly on platforms with weaker memory models if + * you don't add memory barriers in the right places. */ #include @@ -25,8 +28,7 @@ #include "mem.h" #include "tls.h" -// Setting MAX_LEVEL to 0 essentially makes this data structure the Harris-Michael lock-free list -// (in list.c). +// Setting MAX_LEVEL to 0 essentially makes this data structure the Harris-Michael lock-free list (in list.c). #define MAX_LEVEL 31 typedef struct node { @@ -38,8 +40,7 @@ typedef struct node { struct sl { node_t *head; - cmp_fun_t cmp_fun; - clone_fun_t clone_fun; + const datatype_t *key_type; }; static const map_impl_t sl_map_impl = { @@ -72,10 +73,9 @@ static node_t *node_alloc (int level, void *key, uint64_t val) { return item; } -skiplist_t *sl_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun) { +skiplist_t *sl_alloc (const datatype_t *key_type) { skiplist_t *sl = (skiplist_t *)nbd_malloc(sizeof(skiplist_t)); - sl->cmp_fun = cmp_fun; - sl->clone_fun = clone_fun; + sl->key_type = key_type; sl->head = node_alloc(MAX_LEVEL, NULL, 0); memset(sl->head->next, 0, (MAX_LEVEL+1) * sizeof(skiplist_t *)); return sl; @@ -159,7 +159,7 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl // The thread that completes the unlink should free the memory. if (level == 0) { - if (sl->clone_fun != NULL) { + if (sl->key_type != NULL) { nbd_defer_free((void*)other->key); } nbd_defer_free(other); @@ -182,10 +182,10 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl TRACE("s4", "find_preds: visiting item %p (next is %p)", item, next); TRACE("s4", "find_preds: key %p val %p", STRIP_TAG(item->key), item->val); - if (EXPECT_TRUE(sl->cmp_fun == NULL)) { + if (EXPECT_TRUE(sl->key_type == NULL)) { d = (uint64_t)item->key - (uint64_t)key; } else { - d = sl->cmp_fun(item->key, key); + d = sl->key_type->cmp(item->key, key); } if (d >= 0) { @@ -264,7 +264,7 @@ uint64_t sl_cas (skiplist_t *sl, void *key, uint64_t expectation, uint64_t new_v // First insert into the bottom level. TRACE("s3", "sl_cas: attempting to insert item between %p and %p", preds[0], nexts[0]); - void *new_key = (sl->clone_fun == NULL) ? key : sl->clone_fun(key); + void *new_key = (sl->key_type == NULL) ? key : sl->key_type->clone(key); new_item = node_alloc(n, new_key, new_val); node_t *pred = preds[0]; node_t *next = new_item->next[0] = nexts[0]; @@ -277,7 +277,7 @@ uint64_t sl_cas (skiplist_t *sl, void *key, uint64_t expectation, uint64_t new_v break; // success } TRACE("s3", "sl_cas: failed to change pred's link: expected %p found %p", next, other); - if (sl->clone_fun != NULL) { + if (sl->key_type != NULL) { nbd_free(new_key); } nbd_free(new_item); @@ -381,10 +381,10 @@ uint64_t sl_remove (skiplist_t *sl, void *key) { int d = -1; if (!IS_TAGGED(other)) { - if (EXPECT_TRUE(sl->cmp_fun == NULL)) { + if (EXPECT_TRUE(sl->key_type == NULL)) { d = (uint64_t)item->key - (uint64_t)other->key; } else { - d = sl->cmp_fun(item->key, other->key); + d = sl->key_type->cmp(item->key, other->key); } } if (d > 0) { @@ -418,7 +418,7 @@ uint64_t sl_remove (skiplist_t *sl, void *key) { if (SYNC_CAS(&pred->next[0], item, STRIP_TAG(next))) { TRACE("s2", "sl_remove: unlinked item %p from the skiplist at level 0", item, 0); // The thread that completes the unlink should free the memory. - if (sl->clone_fun != NULL) { + if (sl->key_type != NULL) { nbd_defer_free(item->key); } nbd_defer_free(item); @@ -445,7 +445,6 @@ void sl_print (skiplist_t *sl) { printf("\n"); fflush(stdout); } - node_t *item = sl->head; int i = 0; while (item) { diff --git a/test/map_test1.c b/test/map_test1.c index 34d4ba7..7c35b45 100644 --- a/test/map_test1.c +++ b/test/map_test1.c @@ -10,7 +10,7 @@ #define NUM_ITERATIONS 10000000 -//#define TEST_STRING_KEYS +#define TEST_STRING_KEYS static volatile int wait_; static long num_threads_; @@ -85,9 +85,9 @@ int main (int argc, char **argv) { map_type_t map_types[] = { MAP_TYPE_LIST, MAP_TYPE_SKIPLIST, MAP_TYPE_HASHTABLE }; for (int i = 0; i < sizeof(map_types)/sizeof(*map_types); ++i) { #ifdef TEST_STRING_KEYS - map_ = map_alloc(map_types[i], (cmp_fun_t)ns_cmp, (hash_fun_t)ns_hash, (clone_fun_t)ns_dup); + map_ = map_alloc(map_types[i], &DATATYPE_NSTRING); #else - map_ = map_alloc(map_types[i], NULL, NULL, NULL); + map_ = map_alloc(map_types[i], NULL); #endif struct timeval tv1, tv2; diff --git a/test/map_test2.c b/test/map_test2.c index 3e13a68..92a269e 100644 --- a/test/map_test2.c +++ b/test/map_test2.c @@ -10,11 +10,14 @@ #include "common.h" #include "runtime.h" +#include "nstring.h" #include "map.h" #include "lwt.h" #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y) +#define TEST_STRING_KEYS + typedef struct worker_data { int id; CuTest *tc; @@ -27,54 +30,66 @@ static map_type_t map_type_; // Test some basic stuff; add a few keys, remove a few keys void simple (CuTest* tc) { - map_t *map = map_alloc(map_type_, NULL, NULL, NULL); - - ASSERT_EQUAL( 0, map_count(map) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map, (void *)'a',10) ); - ASSERT_EQUAL( 1, map_count(map) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map, (void *)'b',20) ); - ASSERT_EQUAL( 2, map_count(map) ); - ASSERT_EQUAL( 20, map_get(map, (void *)'b') ); - ASSERT_EQUAL( 10, map_set(map, (void *)'a',11) ); - ASSERT_EQUAL( 20, map_set(map, (void *)'b',21) ); - ASSERT_EQUAL( 2, map_count(map) ); - ASSERT_EQUAL( 21, map_add(map, (void *)'b',22) ); - ASSERT_EQUAL( 11, map_remove(map, (void *)'a') ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'a') ); - ASSERT_EQUAL( 1, map_count(map) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(map, (void *)'a') ); - ASSERT_EQUAL( 21, map_remove(map, (void *)'b') ); - ASSERT_EQUAL( 0, map_count(map) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(map, (void *)'b') ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(map, (void *)'c') ); - ASSERT_EQUAL( 0, map_count(map) ); +#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 *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 *k1 = (void *)1; + void *k2 = (void *)2; + void *k3 = (void *)3; + void *k4 = (void *)4; +#endif + + ASSERT_EQUAL( 0, map_count (map) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_add (map, k1,10) ); + ASSERT_EQUAL( 1, map_count (map) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_add (map, k2,20) ); + ASSERT_EQUAL( 2, map_count (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( 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( DOES_NOT_EXIST, map_remove (map, k1) ); + ASSERT_EQUAL( 21, map_remove (map, k2) ); + ASSERT_EQUAL( 0, map_count (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( DOES_NOT_EXIST, map_add(map, (void *)'d',40) ); - ASSERT_EQUAL( 40, map_get(map, (void *)'d') ); - ASSERT_EQUAL( 1, map_count(map) ); - ASSERT_EQUAL( 40, map_remove(map, (void *)'d') ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'d') ); - ASSERT_EQUAL( 0, map_count(map) ); - - ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, (void *)'d',10) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'d') ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_set(map, (void *)'d',40) ); - ASSERT_EQUAL( 40, map_replace(map, (void *)'d',41) ); - ASSERT_EQUAL( 41, map_get(map, (void *)'d') ); - ASSERT_EQUAL( 41, map_remove(map, (void *)'d') ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'d') ); - ASSERT_EQUAL( 0, map_count(map) ); - - ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, (void *)'b',20) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'b') ); + 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( 40, map_remove (map, k4) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_get (map, k4) ); + ASSERT_EQUAL( 0, map_count (map) ); + + ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, k4,10) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_get (map, k4) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_set (map, k4,40) ); + ASSERT_EQUAL( 40, map_replace(map, k4,41) ); + ASSERT_EQUAL( 41, map_get (map, k4) ); + ASSERT_EQUAL( 41, map_remove (map, k4) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_get (map, k4) ); + ASSERT_EQUAL( 0, map_count (map) ); + + ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, k2,20) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_get (map, k2) ); // In the end, all entries should be removed - ASSERT_EQUAL( DOES_NOT_EXIST, map_set(map, (void *)'b',20) ); - ASSERT_EQUAL( 20, map_replace(map, (void *)'b',21) ); - ASSERT_EQUAL( 21, map_get(map, (void *)'b') ); - ASSERT_EQUAL( 21, map_remove(map, (void *)'b') ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'b') ); - ASSERT_EQUAL( 0, map_count(map) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_set (map, k2,20) ); + ASSERT_EQUAL( 20, map_replace(map, k2,21) ); + ASSERT_EQUAL( 21, map_get (map, k2) ); + ASSERT_EQUAL( 21, map_remove (map, k2) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_get (map, k2) ); + ASSERT_EQUAL( 0, map_count (map) ); map_free(map); @@ -87,20 +102,38 @@ void *add_remove_worker (void *arg) { map_t *map = wd->map; CuTest* tc = wd->tc; uint64_t d = wd->id; - int iters = (map_type_ == MAP_TYPE_LIST) ? 5000 : 500000; + int iters = 10000; SYNC_ADD(wd->wait, -1); do { } while (*wd->wait); // wait for all workers to be ready +#ifdef TEST_STRING_KEYS + nstring_t *key = ns_alloc(9); +#else + void *key; +#endif + for (int j = 0; j < 10; ++j) { for (uint64_t i = d+1; i < iters; i+=2) { +#ifdef TEST_STRING_KEYS + memset(key->data, 0, key->len); + snprintf(key->data, key->len, "%llu", i); +#else + 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, (void *)i, d+1) ); + CuAssertIntEquals_Msg(tc, (void *)i, DOES_NOT_EXIST, map_add(map, key, d+1) ); rcu_update(); } for (uint64_t i = d+1; i < iters; i+=2) { +#ifdef TEST_STRING_KEYS + memset(key->data, 0, key->len); + snprintf(key->data, key->len, "%llu", i); +#else + key = (void *)i; +#endif TRACE("t0", "test map_remove() iteration (%llu, %llu)", j, i); - CuAssertIntEquals_Msg(tc, (void *)i, d+1, map_remove(map, (void *)i) ); + CuAssertIntEquals_Msg(tc, (void *)i, d+1, map_remove(map, key) ); rcu_update(); } } @@ -113,7 +146,11 @@ void add_remove (CuTest* tc) { pthread_t thread[2]; worker_data_t wd[2]; volatile int wait = 2; - map_t *map = map_alloc(map_type_, NULL, NULL, NULL); +#ifdef TEST_STRING_KEYS + map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING); +#else + map_t *map = map_alloc(map_type_, NULL); +#endif struct timeval tv1, tv2; gettimeofday(&tv1, NULL); diff --git a/test/txn_test.c b/test/txn_test.c index dee5151..018f19e 100644 --- a/test/txn_test.c +++ b/test/txn_test.c @@ -8,7 +8,7 @@ #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y) void test1 (CuTest* tc) { - map_t *map = map_alloc(MAP_TYPE_LIST, NULL, NULL, NULL); + map_t *map = map_alloc(MAP_TYPE_LIST, NULL); txn_t *t1 = txn_begin(TXN_READ_WRITE, TXN_REPEATABLE_READ, map); txn_t *t2 = txn_begin(TXN_READ_WRITE, TXN_REPEATABLE_READ, map); tm_set(t1, "abc", 2);