#include <string.h>
#include "common.h"
-#include "runtime.h"
#include "skiplist.h"
+#include "runtime.h"
#include "mem.h"
+#include "rcu.h"
// Setting MAX_LEVEL to 0 essentially makes this data structure the Harris-Michael lock-free list (in list.c).
#define MAX_LEVEL 31
// Marking the <next> field of a node logically removes it from the list
#if 0
-static inline markable_t MARK_NODE(node_t * x) { return TAG_VALUE((markable_t)x, TAG1); }
-static inline int HAS_MARK(markable_t x) { return (IS_TAGGED(x, TAG1) == TAG1); }
+static inline markable_t MARK_NODE(node_t * x) { return TAG_VALUE((markable_t)x, 0x1); }
+static inline int HAS_MARK(markable_t x) { return (IS_TAGGED(x, 0x1) == 0x1); }
static inline node_t * GET_NODE(markable_t x) { assert(!HAS_MARK(x)); return (node_t *)x; }
-static inline node_t * STRIP_MARK(markable_t x) { return ((node_t *)STRIP_TAG(x, TAG1)); }
+static inline node_t * STRIP_MARK(markable_t x) { return ((node_t *)STRIP_TAG(x, 0x1)); }
#else
-#define MARK_NODE(x) TAG_VALUE((markable_t)(x), TAG1)
-#define HAS_MARK(x) (IS_TAGGED((x), TAG1) == TAG1)
+#define MARK_NODE(x) TAG_VALUE((markable_t)(x), 0x1)
+#define HAS_MARK(x) (IS_TAGGED((x), 0x1) == 0x1)
#define GET_NODE(x) ((node_t *)(x))
-#define STRIP_MARK(x) ((node_t *)STRIP_TAG((x), TAG1))
+#define STRIP_MARK(x) ((node_t *)STRIP_TAG((x), 0x1))
#endif
static int random_level (void) {
node_t *pred = sl->head;
node_t *item = NULL;
TRACE("s2", "find_preds: searching for key %p in skiplist (head is %p)", key, pred);
- int d;
+ int d = 0;
int start_level = MAX_LEVEL;
#if MAX_LEVEL > 2
// Optimization for small lists. No need to traverse empty higher levels.
if (level == 0) {
node_t *unlinked = GET_NODE(other);
if (sl->key_type != NULL) {
- nbd_defer_free((void *)unlinked->key);
+ rcu_defer_free((void *)unlinked->key);
}
- nbd_defer_free(unlinked);
+ rcu_defer_free(unlinked);
}
} else {
TRACE("s3", "find_preds: lost race to unlink item %p from pred %p", item, pred);
if (old_item == NULL) {
// There was not an item in the skiplist that matches the key.
- if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == CAS_EXPECT_EXISTS)) {
+ if (EXPECT_FALSE(expectation != CAS_EXPECT_DOES_NOT_EXIST && expectation != CAS_EXPECT_WHATEVER)) {
TRACE("l1", "sl_cas: the expectation was not met, the skiplist was not changed", 0, 0);
return DOES_NOT_EXIST; // failure
}
- ASSERT(expectation == CAS_EXPECT_DOES_NOT_EXIST || expectation == CAS_EXPECT_WHATEVER);
-
// First insert <new_item> into the bottom level.
TRACE("s3", "sl_cas: attempting to insert item between %p and %p", preds[0], nexts[0]);
map_key_t new_key = sl->key_type == NULL ? key : (map_key_t)sl->key_type->clone((void *)key);
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->key_type != NULL) {
- nbd_defer_free((void *)item->key);
+ rcu_defer_free((void *)item->key);
}
- nbd_defer_free(item);
+ rcu_defer_free(item);
}
return val;
}
int i = 0;
while (item) {
int is_marked = HAS_MARK(item->next[0]);
- printf("%s%p:0x%llx ", is_marked ? "*" : "", item, (map_key_t)item->key);
+ printf("%s%p:0x%llx ", is_marked ? "*" : "", item, (uint64_t)item->key);
if (item != sl->head) {
printf("[%d]", item->top_level);
} else {
sl_iter_t *sl_iter_begin (skiplist_t *sl, map_key_t key) {
sl_iter_t *iter = (sl_iter_t *)nbd_malloc(sizeof(sl_iter_t));
- find_preds(NULL, &iter->next, 0, sl, key, FALSE);
+ if (key != DOES_NOT_EXIST) {
+ find_preds(NULL, &iter->next, 0, sl, key, FALSE);
+ } else {
+ iter->next = GET_NODE(sl->head->next[0]);
+ }
return iter;
}