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);
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
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
#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);
/////////////////////////////////////////////////////////////////////////////////////
#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;
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
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;
}
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);
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
#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
int x = hti->copy_scan;
TRACE("h1", "ht_cas: help copy. scan is %llu, size is %llu", x, 1<<hti->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) {
} 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
}
}
-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 {
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);
}
-
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);
}
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;
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);
+}
}
}
-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);
}
#define NUM_ITERATIONS 10000000
-#define TEST_STRING_KEYS
+//#define TEST_STRING_KEYS
static volatile int wait_;
static long num_threads_;
#define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y)
-#define TEST_STRING_KEYS
+//#define TEST_STRING_KEYS
typedef struct worker_data {
int id;
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);
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) );
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) );
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) {
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
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];
// 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) {
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);
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));
}
-- 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
uint32_t writes_size;
uint32_t writes_count;
uint32_t writes_scan;
- txn_type_e type;
txn_state_e state;
};
// 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);
}
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;
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 {
}
// 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;
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