#ifndef HASHTABLE_H
#define HASHTABLE_H
-#include "datatype.h"
+#include "map.h"
typedef struct ht hashtable_t;
void ht_print (hashtable_t *ht);
void ht_free (hashtable_t *ht);
+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
+};
+
#endif//HASHTABLE_H
#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);
void ll_print (list_t *ll);
void ll_free (list_t *ll);
+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
+};
+
#endif//LIST_H
#include "datatype.h"
typedef struct map map_t;
+typedef struct map_impl map_impl_t;
-typedef const struct map_impl *map_type_t;
-
-extern map_type_t MAP_TYPE_HASHTABLE;
-
-map_t * map_alloc (map_type_t map_type, const datatype_t *key_type);
+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);
void map_print (map_t *map);
void map_free (map_t *map);
+/////////////////////////////////////////////////////////////////////////////////////
+
+#define CAS_EXPECT_DOES_NOT_EXIST ( 0)
+#define CAS_EXPECT_EXISTS (-1)
+#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 *);
+
+struct map_impl {
+ map_alloc_t alloc;
+ map_cas_t cas;
+ map_get_t get;
+ map_remove_t remove;
+ map_count_t count;
+ map_print_t print;
+ map_free_t free_;
+};
+
#endif//MAP_H
#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);
void sl_print (skiplist_t *sl);
void sl_free (skiplist_t *sl);
+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
+};
+
#endif//SKIPLIST_H
typedef struct txn txn_t;
+void txn_init (void);
+
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);
#include "common.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
const datatype_t *key_type;
};
-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
-};
-
-const map_impl_t *MAP_TYPE_HASHTABLE = &ht_map_impl;
-
static const uint64_t COPIED_VALUE = -1;
static const uint64_t TOMBSTONE = STRIP_TAG(-1);
#include <string.h>
#include "common.h"
-#include "mlocal.h"
#include "list.h"
#include "mem.h"
const datatype_t *key_type;
};
-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
-};
-
-const map_impl_t *MAP_TYPE_LIST = &ll_map_impl;
-
static node_t *node_alloc (void *key, uint64_t val) {
node_t *item = (node_t *)nbd_malloc(sizeof(node_t));
item->key = key;
*/
#include "common.h"
-#include "mlocal.h"
-#include "mem.h"
#include "map.h"
+#include "mem.h"
struct map {
const map_impl_t *impl;
void *data;
};
-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_alloc (const map_impl_t *map_impl, const datatype_t *key_type) {
map_t *map = nbd_malloc(sizeof(map_t));
map->impl = map_impl;
map->data = map->impl->alloc(key_type);
+++ /dev/null
-#ifndef MLOCAL_H
-#define MLOCAL_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) (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 struct map_impl {
- map_alloc_t alloc;
- map_cas_t cas;
- map_get_t get;
- map_remove_t remove;
- map_count_t count;
- map_print_t print;
- map_free_t free_;
-} map_impl_t;
-
-#endif//MLOCAL_H
#include "common.h"
#include "runtime.h"
-#include "mlocal.h"
#include "skiplist.h"
#include "mem.h"
const datatype_t *key_type;
};
-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
-};
-
-const map_impl_t *MAP_TYPE_SKIPLIST = &sl_map_impl;
-
static int random_level (void) {
unsigned r = nbd_rand();
if (r & 1)
}
}
- map_type_t map_types[] = { MAP_TYPE_LIST, MAP_TYPE_SKIPLIST, MAP_TYPE_HASHTABLE };
+ static const map_impl_t *map_types[] = { &ll_map_impl, &sl_map_impl, &ht_map_impl };
for (int i = 0; i < sizeof(map_types)/sizeof(*map_types); ++i) {
#ifdef TEST_STRING_KEYS
map_ = map_alloc(map_types[i], &DATATYPE_NSTRING);
volatile int *wait;
} worker_data_t;
-static map_type_t map_type_;
+static const map_impl_t *map_type_;
// Test some basic stuff; add a few keys, remove a few keys
void simple (CuTest* tc) {
nbd_init();
lwt_set_trace_level("h3");
- map_type_t map_types[] = { MAP_TYPE_LIST, MAP_TYPE_SKIPLIST, MAP_TYPE_HASHTABLE };
+ static const map_impl_t *map_types[] = { &ll_map_impl, &sl_map_impl, &ht_map_impl };
for (int i = 0; i < sizeof(map_types)/sizeof(*map_types); ++i) {
map_type_ = map_types[i];
#define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y)
void test1 (CuTest* tc) {
- map_t *map = map_alloc(MAP_TYPE_HASHTABLE, NULL);
+ 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);
tm_set(t1, "abc", 2);
int main (void) {
nbd_init();
+ txn_init();
CuString *output = CuStringNew();
CuSuite* suite = CuSuiteNew();
- 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
+- allow values of 0 to be inserted into maps (change DOES_NOT_EXIST to something else)
static map_t *active_ = NULL;
void txn_init (void) {
- active_ = map_alloc(MAP_TYPE_SKIPLIST, NULL);
+ active_ = map_alloc(&sl_map_impl, NULL);
}
// Validate the updates for <key>. Validation fails for a key we have written to if there is a