#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);
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;
}