#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;
--- /dev/null
+#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
#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);
#ifndef NSTRING_H
#define NSTRING_H
+#include "common.h"
+#include "datatype.h"
+
typedef struct nstring {
uint32_t len;
char data[];
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
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
} 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 = {
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 <key> 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);
// The key in <ent> 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;
}
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)) {
// 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;
// We use 0 to indicate that <key_hash> 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;
return DOES_NOT_EXIST;
// Allocate <new_key>.
- 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 <new_key> pointer with bits from its hash
new_key = ((uint64_t)(key_hash >> 16) << 48) | new_key;
}
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
}
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;
//
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);
}
}
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;
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)
}
// 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;
}
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));
}
}
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 = {
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;
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);
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
// 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);
// 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);
}
// 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);
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;
}
#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 *);
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);
* 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 <stdio.h>
#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 {
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 = {
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;
// 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);
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) {
// First insert <new_item> 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];
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);
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) {
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);
printf("\n");
fflush(stdout);
}
-
node_t *item = sl->head;
int i = 0;
while (item) {
#define NUM_ITERATIONS 10000000
-//#define TEST_STRING_KEYS
+#define TEST_STRING_KEYS
static volatile int wait_;
static long num_threads_;
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;
#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;
// 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);
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();
}
}
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);
#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);
projects / nbds / commitdiff