#define MAP_H
typedef struct map map_t;
-typedef enum stat { MAP_STAT_COUNT } map_stat_e;
-typedef enum { MAP_TYPE_HASHTABLE, MAP_TYPE_SKIPLIST, MAP_TYPE_LIST } map_type_e;
-map_t * map_alloc (map_type_e map_type);
-void map_free (map_t *map);
-void map_print (map_t *map);
-uint64_t map_stat (map_t *map, map_stat_e stat_type);
+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);
uint64_t map_get (map_t *map, const void *key_data, uint32_t key_len);
uint64_t map_set (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val);
uint64_t map_add (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val);
uint64_t map_cas (map_t *map, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val);
uint64_t map_replace(map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val);
uint64_t map_remove (map_t *map, const void *key_data, uint32_t key_len);
+uint64_t map_count (map_t *map);
+void map_print (map_t *map);
+void map_free (map_t *map);
#endif//MAP_H
EXES := $(TESTS)
RUNTIME_SRCS := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c
-MAP_SRCS := map/map.c map/hashtable.c map/list.c map/skiplist.c map/nstring.c
+MAP_SRCS := map/map.c map/nstring.c
TEST_SRCS := $(RUNTIME_SRCS) $(MAP_SRCS)
rcu_test_SRCS := $(TEST_SRCS) test/rcu_test.c
-txn_test_SRCS := $(TEST_SRCS) txn/txn.c
-ll_test_SRCS := $(TEST_SRCS) test/ll_test.c
-sl_test_SRCS := $(TEST_SRCS) test/sl_test.c
-ht_test_SRCS := $(TEST_SRCS) test/ht_test.c test/CuTest.c
+txn_test_SRCS := $(TEST_SRCS) txn/txn.c map/hashtable.c
+ll_test_SRCS := $(TEST_SRCS) test/ll_test.c map/list.c
+sl_test_SRCS := $(TEST_SRCS) test/sl_test.c map/skiplist.c
+ht_test_SRCS := $(TEST_SRCS) test/ht_test.c map/hashtable.c test/CuTest.c
tests: $(TESTS)
hashtable_i_t *hti;
};
+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);
* Harris-Michael lock-free list-based set
* http://www.research.ibm.com/people/m/michael/spaa-2002.pdf
*/
+
#include <stdio.h>
#include <string.h>
node_t *head;
};
+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 (const void *key_data, uint32_t key_len, uint64_t val) {
node_t *item = (node_t *)nbd_malloc(sizeof(node_t));
memset(item, 0, sizeof(node_t));
}
void ll_free (list_t *ll) {
+ node_t *item = ll->head->next;
+ while (item) {
+ node_t *next = (node_t *)STRIP_TAG(item->next);
+ nbd_free(item);
+ item = next;
+ }
+}
+
+uint64_t ll_count (list_t *ll) {
+ uint64_t count = 0;
+ node_t *item = ll->head->next;
+ while (item) {
+ count++;
+ item = (node_t *)STRIP_TAG(item->next);
+ }
+ return count;
}
static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, const void *key_data, uint32_t key_len, int help_remove) {
#include "map.h"
struct map {
- map_type_e type;
- void *impl;
+ const map_impl_t *impl;
+ void *data;
};
-map_t *map_alloc (map_type_e map_type) {
- void *impl = NULL;
- switch (map_type) {
- case MAP_TYPE_HASHTABLE: impl = ht_alloc(); break;
- case MAP_TYPE_SKIPLIST: impl = sl_alloc(); break;
- case MAP_TYPE_LIST: impl = ll_alloc(); break;
- }
- map_t *map = NULL;
- if (impl) {
- map = nbd_malloc(sizeof(map_t));
- map->type = map_type;
- map->impl = impl;
- }
+map_t *map_alloc (map_type_t map_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();
return map;
}
void map_free (map_t *map) {
- switch (map->type) {
- case MAP_TYPE_HASHTABLE: ht_free(map->impl); break;
- case MAP_TYPE_SKIPLIST: sl_free(map->impl); break;
- case MAP_TYPE_LIST: ll_free(map->impl); break;
- }
+ map->impl->free_(map->data);
}
void map_print (map_t *map) {
- switch (map->type) {
- case MAP_TYPE_HASHTABLE: ht_print(map->impl); break;
- case MAP_TYPE_SKIPLIST: sl_print(map->impl); break;
- case MAP_TYPE_LIST: ll_print(map->impl); break;
- }
+ map->impl->print(map->data);
}
-uint64_t map_stat (map_t *map, map_stat_e stat_type) {
- switch (stat_type) {
- case MAP_STAT_COUNT:
- if (map->type != MAP_TYPE_HASHTABLE)
- return ERROR_UNSUPPORTED_FEATURE;
- return ht_count(map->impl);
- }
- return ERROR_INVALID_OPTION;
+uint64_t map_count (map_t *map) {
+ return map->impl->count(map->data);
}
uint64_t map_get (map_t *map, const void *key_data, uint32_t key_len) {
- switch (map->type) {
- case MAP_TYPE_HASHTABLE: return ht_get(map->impl, key_data, key_len);
- case MAP_TYPE_SKIPLIST: return sl_lookup(map->impl, key_data, key_len);
- case MAP_TYPE_LIST: return ll_lookup(map->impl, key_data, key_len);
- }
- return ERROR_INVALID_ARGUMENT;
+ return map->impl->get(map->data, key_data, key_len);
}
uint64_t map_set (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val) {
- switch (map->type) {
- case MAP_TYPE_HASHTABLE: return ht_cas(map->impl, key_data, key_len, CAS_EXPECT_WHATEVER, new_val);
- case MAP_TYPE_SKIPLIST: return sl_cas(map->impl, key_data, key_len, CAS_EXPECT_WHATEVER, new_val);
- case MAP_TYPE_LIST: return ll_cas(map->impl, key_data, key_len, CAS_EXPECT_WHATEVER, new_val);
- }
- return ERROR_INVALID_ARGUMENT;
+ return map->impl->cas(map->data, key_data, key_len, CAS_EXPECT_WHATEVER, new_val);
}
uint64_t map_add (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val) {
- switch (map->type) {
- case MAP_TYPE_HASHTABLE: return ht_cas(map->impl, key_data, key_len, CAS_EXPECT_DOES_NOT_EXIST, new_val);
- case MAP_TYPE_SKIPLIST: return sl_cas(map->impl, key_data, key_len, CAS_EXPECT_DOES_NOT_EXIST, new_val);
- case MAP_TYPE_LIST: return ll_cas(map->impl, key_data, key_len, CAS_EXPECT_DOES_NOT_EXIST, new_val);
- }
- return ERROR_INVALID_ARGUMENT;
+ return map->impl->cas(map->data, key_data, key_len, CAS_EXPECT_DOES_NOT_EXIST, new_val);
}
uint64_t map_cas (map_t *map, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val) {
- switch (map->type) {
- case MAP_TYPE_HASHTABLE: return ht_cas(map->impl, key_data, key_len, expected_val, new_val);
- case MAP_TYPE_SKIPLIST: return sl_cas(map->impl, key_data, key_len, expected_val, new_val);
- case MAP_TYPE_LIST: return ll_cas(map->impl, key_data, key_len, expected_val, new_val);
- }
- return ERROR_INVALID_ARGUMENT;
+ return map->impl->cas(map->data, key_data, key_len, expected_val, new_val);
}
uint64_t map_replace(map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val) {
- switch (map->type) {
- case MAP_TYPE_HASHTABLE: return ht_cas(map->impl, key_data, key_len, CAS_EXPECT_EXISTS, new_val);
- case MAP_TYPE_SKIPLIST: return sl_cas(map->impl, key_data, key_len, CAS_EXPECT_EXISTS, new_val);
- case MAP_TYPE_LIST: return ll_cas(map->impl, key_data, key_len, CAS_EXPECT_EXISTS, new_val);
- }
- return ERROR_INVALID_ARGUMENT;
+ return map->impl->cas(map->data, key_data, key_len, CAS_EXPECT_EXISTS, new_val);
}
uint64_t map_remove (map_t *map, const void *key_data, uint32_t key_len) {
- switch (map->type) {
- case MAP_TYPE_HASHTABLE: return ht_remove(map->impl, key_data, key_len);
- case MAP_TYPE_SKIPLIST: return sl_remove(map->impl, key_data, key_len);
- case MAP_TYPE_LIST: return ll_remove(map->impl, key_data, key_len);
- }
- return ERROR_INVALID_ARGUMENT;
+ return map->impl->remove(map->data, key_data, key_len);
}
-#ifndef STRUCT_H
-#define STRUCT_H
+#ifndef MLOCAL_H
+#define MLOCAL_H
#define CAS_EXPECT_DOES_NOT_EXIST ( 0)
#define CAS_EXPECT_EXISTS (-1)
#define CAS_EXPECT_WHATEVER (-2)
+typedef void * (*map_alloc_t) (void);
+typedef uint64_t (*map_cas_t) (void *, const void *, uint32_t, uint64_t, uint64_t);
+typedef uint64_t (*map_get_t) (void *, const void *, uint32_t);
+typedef uint64_t (*map_remove_t) (void *, const void *, uint32_t);
+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;
+
typedef struct ht hashtable_t;
-hashtable_t *ht_alloc (void);
+typedef struct sl skiplist_t;
+typedef struct ll list_t;
+
+hashtable_t * ht_alloc (void);
+skiplist_t * sl_alloc (void);
+list_t * ll_alloc (void);
+
uint64_t ht_cas (hashtable_t *ht, const char *key, uint32_t key_len, uint64_t expected_val, uint64_t val);
uint64_t ht_get (hashtable_t *ht, const char *key, uint32_t len);
uint64_t ht_remove (hashtable_t *ht, const char *key, uint32_t len);
void ht_print (hashtable_t *ht);
void ht_free (hashtable_t *ht);
-typedef struct ll list_t;
-list_t * ll_alloc (void);
-uint64_t ll_lookup (list_t *ll, const void *key_data, uint32_t key_len);
-uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val);
-uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len);
-void ll_print (list_t *ll);
-void ll_free (list_t *ll);
-
-typedef struct sl skiplist_t;
-skiplist_t * sl_alloc (void);
-uint64_t sl_lookup (skiplist_t *sl, const void *key_data, uint32_t key_len);
uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val);
+uint64_t sl_lookup (skiplist_t *sl, const void *key_data, uint32_t key_len);
uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len);
+uint64_t sl_count (skiplist_t *sl);
void sl_print (skiplist_t *sl);
-void sl_free (list_t *sl);
+void sl_free (skiplist_t *sl);
+uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val);
+uint64_t ll_lookup (list_t *ll, const void *key_data, uint32_t key_len);
+uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len);
+uint64_t ll_count (list_t *ll);
+void ll_print (list_t *ll);
+void ll_free (list_t *ll);
-#endif//STRUCT_H
+#endif//MLOCAL_H
* 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.
*/
+
#include <stdio.h>
#include <string.h>
node_t *head;
};
+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)
return sl;
}
-void ll_free (list_t *ll) {
+void sl_free (skiplist_t *sl) {
+ node_t *item = sl->head->next[0];
+ while (item) {
+ node_t *next = (node_t *)STRIP_TAG(item->next[0]);
+ nbd_free(item);
+ item = next;
+ }
+}
+
+uint64_t sl_count (skiplist_t *sl) {
+ uint64_t count = 0;
+ node_t *item = sl->head->next[0];
+ while (item) {
+ count++;
+ item = (node_t *)STRIP_TAG(item->next[0]);
+ }
+ return count;
}
static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl, const void *key_data, uint32_t key_len, int help_remove) {
map_t *ht = map_alloc(MAP_TYPE_HASHTABLE);
- ASSERT_EQUAL( 0, map_stat(ht, MAP_STAT_COUNT) );
- ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"a",2,10) );
- ASSERT_EQUAL( 1, map_stat(ht, MAP_STAT_COUNT) );
- ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"b",2,20) );
- ASSERT_EQUAL( 2, map_stat(ht, MAP_STAT_COUNT) );
- ASSERT_EQUAL( 20, map_get(ht,"b",2) );
- ASSERT_EQUAL( 10, map_set(ht,"a",2,11) );
- ASSERT_EQUAL( 20, map_set(ht,"b",2,21) );
- ASSERT_EQUAL( 2, map_stat(ht, MAP_STAT_COUNT) );
- ASSERT_EQUAL( 21, map_add(ht,"b",2,22) );
- ASSERT_EQUAL( 11, map_remove(ht,"a",2) );
- ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"a",2) );
- ASSERT_EQUAL( 1, map_stat(ht, MAP_STAT_COUNT) );
- ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"a",2) );
- ASSERT_EQUAL( 21, map_remove(ht,"b",2) );
- ASSERT_EQUAL( 0, map_stat(ht, MAP_STAT_COUNT) );
- ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"b",2) );
- ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"c",2) );
- ASSERT_EQUAL( 0, map_stat(ht, MAP_STAT_COUNT) );
+ ASSERT_EQUAL( 0, map_count(ht) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"a",2,10) );
+ ASSERT_EQUAL( 1, map_count(ht) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"b",2,20) );
+ ASSERT_EQUAL( 2, map_count(ht) );
+ ASSERT_EQUAL( 20, map_get(ht,"b",2) );
+ ASSERT_EQUAL( 10, map_set(ht,"a",2,11) );
+ ASSERT_EQUAL( 20, map_set(ht,"b",2,21) );
+ ASSERT_EQUAL( 2, map_count(ht) );
+ ASSERT_EQUAL( 21, map_add(ht,"b",2,22) );
+ ASSERT_EQUAL( 11, map_remove(ht,"a",2) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"a",2) );
+ ASSERT_EQUAL( 1, map_count(ht) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"a",2) );
+ ASSERT_EQUAL( 21, map_remove(ht,"b",2) );
+ ASSERT_EQUAL( 0, map_count(ht) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"b",2) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(ht,"c",2) );
+ ASSERT_EQUAL( 0, map_count(ht) );
- ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"d",2,40) );
- ASSERT_EQUAL( 40, map_get(ht,"d",2) );
- ASSERT_EQUAL( 1, map_stat(ht, MAP_STAT_COUNT) );
- ASSERT_EQUAL( 40, map_remove(ht,"d",2) );
- ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2) );
- ASSERT_EQUAL( 0, map_stat(ht, MAP_STAT_COUNT) );
-
- ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(ht,"d",2,10) );
- ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2) );
- ASSERT_EQUAL( DOES_NOT_EXIST, map_set(ht,"d",2,40) );
- ASSERT_EQUAL( 40, map_replace(ht,"d",2,41) );
- ASSERT_EQUAL( 41, map_get(ht,"d",2) );
- ASSERT_EQUAL( 41, map_remove(ht,"d",2) );
- ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2) );
- ASSERT_EQUAL( 0, map_stat(ht, MAP_STAT_COUNT) );
-
- ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(ht,"b",2,20) );
- ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"b",2) );
- // In the end, all members should be removed
- ASSERT_EQUAL( DOES_NOT_EXIST, map_set(ht,"b",2,20) );
- ASSERT_EQUAL( 20, map_replace(ht,"b",2,21) );
- ASSERT_EQUAL( 21, map_get(ht,"b",2) );
- ASSERT_EQUAL( 21, map_remove(ht,"b",2) );
- ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"b",2) );
- ASSERT_EQUAL( 0, map_stat(ht, MAP_STAT_COUNT) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"d",2,40) );
+ ASSERT_EQUAL( 40, map_get(ht,"d",2) );
+ ASSERT_EQUAL( 1, map_count(ht) );
+ ASSERT_EQUAL( 40, map_remove(ht,"d",2) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2) );
+ ASSERT_EQUAL( 0, map_count(ht) );
+
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(ht,"d",2,10) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_set(ht,"d",2,40) );
+ ASSERT_EQUAL( 40, map_replace(ht,"d",2,41) );
+ ASSERT_EQUAL( 41, map_get(ht,"d",2) );
+ ASSERT_EQUAL( 41, map_remove(ht,"d",2) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"d",2) );
+ ASSERT_EQUAL( 0, map_count(ht) );
+
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(ht,"b",2,20) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"b",2) );
+
+ // In the end, all entries should be removed
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_set(ht,"b",2,20) );
+ ASSERT_EQUAL( 20, map_replace(ht,"b",2,21) );
+ ASSERT_EQUAL( 21, map_get(ht,"b",2) );
+ ASSERT_EQUAL( 21, map_remove(ht,"b",2) );
+ ASSERT_EQUAL( DOES_NOT_EXIST, map_get(ht,"b",2) );
+ ASSERT_EQUAL( 0, map_count(ht) );
map_free(ht);
}
// In the end, all members should be removed
- ASSERT_EQUAL( 0, map_stat(ht, MAP_STAT_COUNT) );
+ ASSERT_EQUAL( 0, map_count(ht) );
// In a quiecent state; it is safe to free.
map_free(ht);
- make interfaces for all data structures consistent
+ make list and skiplist use string keys
+ optimize integer keys
-- sl_free() ll_free() ht_print()
+- ht_print()
projects / nbds / commitdiff