* 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>
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)
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) {
// 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)
} 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) {
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.