X-Git-Url: https://pd.if.org/git/?p=nbds;a=blobdiff_plain;f=map%2Fskiplist.c;h=ec8a6ff012db11410894c67791c591990d39c07e;hp=c0e869c25e584656c33cf452d50bcacd1797b8f6;hb=df360b20f11476e53534a53c9ce11493d7c7a764;hpb=025017478bb385da88a6b185849c8bcffeb2e2aa

diff --git a/map/skiplist.c b/map/skiplist.c
index c0e869c..ec8a6ff 100644
--- a/map/skiplist.c
+++ b/map/skiplist.c
@@ -13,6 +13,7 @@
  * 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>
 
@@ -38,6 +39,13 @@ struct sl {
     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)
@@ -85,7 +93,23 @@ skiplist_t *sl_alloc (void) {
     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) {
@@ -316,7 +340,7 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_
                 // There in no need to continue linking in the item if another thread removed it.
                 node_t *old_next = ((volatile node_t *)new_item)->next[level];
                 if (IS_TAGGED(old_next))
-                    return new_val;
+                    return DOES_NOT_EXIST; // success
 
                 // Use a CAS so we do not inadvertantly stomp on a mark another thread placed on the item.
                 if (old_next == next || SYNC_CAS(&new_item->next[level], old_next, next) == old_next)
@@ -324,7 +348,7 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_
             } while (1);
         } while (1);
     }
-    return new_val;
+    return DOES_NOT_EXIST; // success
 }
 
 uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len) {
@@ -355,8 +379,9 @@ uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len) {
                 TRACE("s2", "sl_remove: lost race -- %p is already marked for removal by another thread", item, 0);
                 if (level == 0)
                     return DOES_NOT_EXIST;
+                break;
             }
-        } while (!IS_TAGGED(old_next) || next != old_next);
+        } while (next != old_next);
     }
 
     // This has to be an atomic swap in case another thread is updating the item while we are removing it.