X-Git-Url: https://pd.if.org/git/?p=nbds;a=blobdiff_plain;f=map%2Fskiplist.c;h=6e02e12600673267a80291b2005ae1e90662d4b3;hp=5366d91adae9bcef2c5caa6f91cd95f6c61c8b47;hb=a1d0b3ca99552878b1becf561d8f3291992aaa67;hpb=4ae7c1069667d8f067258d89676126f9b44226d6

diff --git a/map/skiplist.c b/map/skiplist.c
index 5366d91..6e02e12 100644
--- a/map/skiplist.c
+++ b/map/skiplist.c
@@ -21,9 +21,10 @@
 #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
@@ -46,15 +47,15 @@ struct sl {
 
 // 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) {
@@ -116,7 +117,7 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl
     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.
@@ -170,9 +171,9 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl
                     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);
@@ -275,13 +276,11 @@ map_val_t sl_cas (skiplist_t *sl, map_key_t key, map_val_t expectation, map_val_
         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);
@@ -440,9 +439,9 @@ map_val_t sl_remove (skiplist_t *sl, map_key_t 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;
 }
@@ -470,7 +469,7 @@ void sl_print (skiplist_t *sl) {
     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 {
@@ -495,7 +494,11 @@ void sl_print (skiplist_t *sl) {
 
 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;
 }