--- /dev/null
+#ifndef HASHTABLE_H
+#define HASHTABLE_H
+
+#include "datatype.h"
+
+typedef struct ht hashtable_t;
+
+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);
+uint64_t ht_count (hashtable_t *ht);
+void ht_print (hashtable_t *ht);
+void ht_free (hashtable_t *ht);
+
+#endif//HASHTABLE_H
--- /dev/null
+#ifndef LIST_H
+#define LIST_H
+
+#include "datatype.h"
+#include "map.h"
+
+typedef struct ll list_t;
+
+extern map_type_t MAP_TYPE_LIST;
+
+list_t * ll_alloc (const datatype_t *key_type);
+uint64_t ll_cas (list_t *ll, void *key, uint64_t expected_val, uint64_t new_val);
+uint64_t ll_lookup (list_t *ll, void *key);
+uint64_t ll_remove (list_t *ll, void *key);
+uint64_t ll_count (list_t *ll);
+void ll_print (list_t *ll);
+void ll_free (list_t *ll);
+
+#endif//LIST_H
typedef const struct map_impl *map_type_t;
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, const datatype_t *key_type);
uint64_t map_get (map_t *map, void *key);
--- /dev/null
+#ifndef SKIPLIST_H
+#define SKIPLIST_H
+
+#include "datatype.h"
+#include "map.h"
+
+typedef struct sl skiplist_t;
+
+extern map_type_t MAP_TYPE_SKIPLIST;
+
+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);
+uint64_t sl_count (skiplist_t *sl);
+void sl_print (skiplist_t *sl);
+void sl_free (skiplist_t *sl);
+
+#endif//SKIPLIST_H
#include "map.h"
-typedef enum { TXN_READ_WRITE, TXN_READ_ONLY, TXN_BLIND_WRITE } txn_access_e;
-typedef enum { TXN_REPEATABLE_READ, TXN_READ_COMMITTED, TXN_DIRTY_READ } txn_isolation_e;
+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;
-txn_t * txn_begin (txn_access_e access, txn_isolation_e isolation, map_t *map);
+txn_t * txn_begin (txn_type_e type, 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 tm_get (txn_t *txn, void *key);
+void tm_set (txn_t *txn, void *key, uint64_t value);
#endif//TXN_H
#include "murmur.h"
#include "mem.h"
#include "mlocal.h"
+#include "hashtable.h"
#define GET_PTR(x) ((void *)((x) & MASK(48))) // low-order 48 bits is a pointer to a nstring_t
}
// Compare <expected> with the existing value associated with <key>. If the values match then
-// replace the existing value with <new>. If <new> is TOMBSTONE, delete the value associated with
+// replace the existing value with <new>. If <new> is DOES_NOT_EXIST, delete the value associated with
// the key by replacing it with a TOMBSTONE.
//
// Return the previous value associated with <key>, or DOES_NOT_EXIST if <key> is not in the table
TRACE("h1", "hti_cas: hti %p key %p", hti, key);
TRACE("h1", "hti_cas: value %p expect %p", new, expected);
assert(hti);
- assert(new != DOES_NOT_EXIST && !IS_TAGGED(new));
+ assert(!IS_TAGGED(new));
assert(key);
int is_empty;
return DOES_NOT_EXIST;
// No need to do anything, <key> is already deleted.
- if (new == TOMBSTONE)
+ if (new == DOES_NOT_EXIST)
return DOES_NOT_EXIST;
// Allocate <new_key>.
}
// No need to update if value is unchanged.
- if ((new == TOMBSTONE && !old_existed) || ent_val == new) {
+ if ((new == DOES_NOT_EXIST && !old_existed) || ent_val == new) {
TRACE("h1", "hti_cas: old value and new value were the same", 0, 0);
return ent_val;
}
// CAS the value into the entry. Retry if it fails.
- uint64_t v = SYNC_CAS(&ent->val, ent_val, new);
+ uint64_t v = SYNC_CAS(&ent->val, ent_val, new == DOES_NOT_EXIST ? TOMBSTONE : new);
if (EXPECT_FALSE(v != ent_val)) {
TRACE("h0", "hti_cas: value CAS failed; expected %p found %p", ent_val, v);
return hti_cas(hti, key, key_hash, expected, new); // recursive tail-call
}
// The set succeeded. Adjust the value count.
- if (old_existed && new == TOMBSTONE) {
+ if (old_existed && new == DOES_NOT_EXIST) {
SYNC_ADD(&hti->count, -1);
- } else if (!old_existed && new != TOMBSTONE) {
+ } else if (!old_existed && new != DOES_NOT_EXIST) {
SYNC_ADD(&hti->count, 1);
}
uint64_t val;
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);
+ val = hti_cas(hti, key, key_hash, CAS_EXPECT_WHATEVER, DOES_NOT_EXIST);
if (val != COPIED_VALUE)
return val == TOMBSTONE ? DOES_NOT_EXIST : val;
assert(hti->next);
#include "common.h"
#include "mlocal.h"
+#include "list.h"
#include "mem.h"
typedef struct node {
return DOES_NOT_EXIST;
}
- // Mark <item> removed. This must be atomic. If multiple threads try to remove the same item
- // only one of them should succeed.
+ // Mark <item> removed. If multiple threads try to remove the same item only one of them should succeed.
node_t *next;
node_t *old_next = item->next;
do {
TRACE("l2", "ll_remove: logically removed item %p", item, 0);
ASSERT(IS_TAGGED(item->next));
- // This has to be an atomic swap in case another thread is updating the item while we are removing it.
+ // Atomically swap out the item's value in case another thread is updating the item while we are
+ // removing it. This establishes which operation occurs first logically, the update or the remove.
uint64_t val = SYNC_SWAP(&item->val, DOES_NOT_EXIST);
TRACE("l2", "ll_remove: replaced item's val %p with DOES_NOT_EXIT", val, 0);
map_free_t free_;
} map_impl_t;
-typedef struct ht hashtable_t;
-typedef struct sl skiplist_t;
-typedef struct ll list_t;
-
-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);
-uint64_t ht_remove (hashtable_t *ht, void *key);
-uint64_t ht_count (hashtable_t *ht);
-void ht_print (hashtable_t *ht);
-void ht_free (hashtable_t *ht);
-
-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);
-uint64_t sl_count (skiplist_t *sl);
-void sl_print (skiplist_t *sl);
-void sl_free (skiplist_t *sl);
-
-uint64_t ll_cas (list_t *ll, void *key, uint64_t expected_val, uint64_t new_val);
-uint64_t ll_lookup (list_t *ll, void *key);
-uint64_t ll_remove (list_t *ll, void *key);
-uint64_t ll_count (list_t *ll);
-void ll_print (list_t *ll);
-void ll_free (list_t *ll);
-
#endif//MLOCAL_H
#include <stdio.h>
#include <string.h>
-#define ENABLE_TRACE
-
#include "common.h"
#include "runtime.h"
#include "mlocal.h"
+#include "skiplist.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).
#define MAX_LEVEL 31
TRACE("s1", "sl_remove: marked item %p removed at level 0", item, 0);
// Atomically swap out the item's value in case another thread is updating the item while we are
- // removing it. This establishes which one occurs first, the update or the remove.
+ // removing it. This establishes which operation occurs first logically, the update or the remove.
uint64_t val = SYNC_SWAP(&item->val, DOES_NOT_EXIST);
TRACE("s2", "sl_remove: replaced item %p's value with DOES_NOT_EXIT", item, 0);
#include "nstring.h"
#include "runtime.h"
#include "map.h"
+#include "list.h"
+#include "skiplist.h"
+#include "hashtable.h"
#define NUM_ITERATIONS 10000000
#include "runtime.h"
#include "nstring.h"
#include "map.h"
+#include "list.h"
+#include "skiplist.h"
+#include "hashtable.h"
#include "lwt.h"
#define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y)
#include "common.h"
#include "runtime.h"
#include "txn.h"
+#include "map.h"
+#include "hashtable.h"
#define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y)
void test1 (CuTest* tc) {
- 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);
+ map_t *map = map_alloc(MAP_TYPE_HASHTABLE, NULL);
+ txn_t *t1 = txn_begin(TXN_REPEATABLE_READ, map);
+ txn_t *t2 = txn_begin(TXN_REPEATABLE_READ, map);
tm_set(t1, "abc", 2);
tm_set(t1, "abc", 3);
ASSERT_EQUAL( DOES_NOT_EXIST, tm_get(t2, "abc") );
#include "common.h"
#include "txn.h"
#include "mem.h"
+#include "skiplist.h"
#define UNDETERMINED_VERSION 0
#define INITIAL_WRITES_SIZE 4
uint32_t writes_size;
uint32_t writes_count;
uint32_t writes_scan;
- txn_access_e access;
- txn_isolation_e isolation;
+ txn_type_e type;
txn_state_e state;
};
+static uint64_t version_ = 1;
+
static txn_state_e txn_validate (txn_t *txn);
-static uint64_t version_ = 1;
+static map_t *active_ = NULL;
+
+void txn_init (void) {
+ active_ = map_alloc(MAP_TYPE_SKIPLIST, NULL);
+}
// Validate the updates for <key>. Validation fails for a key we have written to if there is a
// write committed newer than our read version.
return u;
}
-txn_t *txn_begin (txn_access_e access, txn_isolation_e isolation, map_t *map) {
+txn_t *txn_begin (txn_type_e type, map_t *map) {
txn_t *txn = (txn_t *)nbd_malloc(sizeof(txn_t));
memset(txn, 0, sizeof(txn_t));
- txn->access = access;
- txn->isolation = isolation;
- txn->rv = version_;
+ txn->type = type;
txn->wv = UNDETERMINED_VERSION;
txn->state = TXN_RUNNING;
txn->map = map;
- if (isolation != TXN_READ_ONLY) {
+ if (type != TXN_READ_ONLY) {
txn->writes = nbd_malloc(sizeof(*txn->writes) * INITIAL_WRITES_SIZE);
txn->writes_size = INITIAL_WRITES_SIZE;
}
+
+ // aquire the read version for txn.
+ do {
+ txn->rv = version_;
+
+ uint64_t old_count;
+ uint64_t temp = 0;
+ do {
+ old_count = temp;
+ temp = (uint64_t)map_cas(active_, (void *)txn->rv, old_count, old_count + 1);
+ } while (temp != old_count);
+
+ if (txn->rv == version_)
+ break;
+
+ temp = 1;
+ do {
+ old_count = temp;
+ temp = map_cas(active_, (void *)txn->rv, old_count, old_count - 1);
+ } while (temp != old_count);
+ } while (1);
+
return txn;
}