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