pd.if.org Git - nbds/blob - map/unsafe_skiplist.c

   1 /*
   2  * Written by Josh Dybnis and released to the public domain, as explained at
   3  * http://creativecommons.org/licenses/publicdomain
   4  *
   5  * non thread safe skiplist
   6  */
   7
   8 #include <stdio.h>
   9 #include <string.h>
  10
  11 #include "common.h"
  12 #include "skiplist.h"
  13 #include "runtime.h"
  14 #include "mem.h"
  15
  16 #define MAX_LEVELS 32
  17
  18 typedef struct node {
  19     map_key_t key;
  20     map_val_t val;
  21     int num_levels;
  22     struct node *next[1];
  23 } node_t;
  24
  25 struct sl_iter {
  26     node_t *next;
  27 };
  28
  29 struct sl {
  30     node_t *head;
  31     const datatype_t *key_type;
  32     int high_water; // max level of any item in the list
  33 };
  34
  35 static int random_levels (skiplist_t *sl) {
  36     unsigned r = nbd_rand();
  37     int z = __builtin_ctz(r);
  38     int levels = (int)(z / 1.5);
  39     if (levels == 0)
  40         return 1;
  41     if (levels > sl->high_water) {
  42         levels = SYNC_ADD(&sl->high_water, 1);
  43         TRACE("s2", "random_levels: increased high water mark to %lld", sl->high_water, 0);
  44     }
  45     if (levels > MAX_LEVELS) { levels = MAX_LEVELS; }
  46     return levels;
  47 }
  48
  49 static node_t *node_alloc (int num_levels, map_key_t key, map_val_t val) {
  50     assert(num_levels > 0 && num_levels <= MAX_LEVELS);
  51     size_t sz = sizeof(node_t) + (num_levels - 1) * sizeof(node_t *);
  52     node_t *item = (node_t *)nbd_malloc(sz);
  53     memset(item, 0, sz);
  54     item->key = key;
  55     item->val = val;
  56     item->num_levels = num_levels;
  57     TRACE("s2", "node_alloc: new node %p (%llu levels)", item, num_levels);
  58     return item;
  59 }
  60
  61 skiplist_t *sl_alloc (const datatype_t *key_type) {
  62     skiplist_t *sl = (skiplist_t *)nbd_malloc(sizeof(skiplist_t));
  63     sl->key_type = key_type;
  64     sl->high_water = 1;
  65     sl->head = node_alloc(MAX_LEVELS, 0, 0);
  66     memset(sl->head->next, 0, MAX_LEVELS * sizeof(skiplist_t *));
  67     return sl;
  68 }
  69
  70 void sl_free (skiplist_t *sl) {
  71     node_t *item = sl->head->next[0];
  72     while (item) {
  73         node_t *next = item->next[0];
  74         if (sl->key_type != NULL) {
  75             nbd_free((void *)item->key);
  76         }
  77         nbd_free(item);
  78         item = next;
  79     }
  80 }
  81
  82 size_t sl_count (skiplist_t *sl) {
  83     size_t count = 0;
  84     node_t *item = sl->head->next[0];
  85     while (item) {
  86         count++;
  87         item = item->next[0];
  88     }
  89     return count;
  90 }
  91
  92 static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl, map_key_t key, int unlink) {
  93     node_t *pred = sl->head;
  94     node_t *item = NULL;
  95     TRACE("s2", "find_preds: searching for key %p in skiplist (head is %p)", key, pred);
  96     int d = 0;
  97
  98     // Traverse the levels of <sl> from the top level to the bottom
  99     for (int level = sl->high_water - 1; level >= 0; --level) {
 100         node_t *next = pred->next[level];
 101         if (next == DOES_NOT_EXIST && level >= n)
 102             continue;
 103         TRACE("s3", "find_preds: traversing level %p starting at %p", level, pred);
 104         item = next;
 105         while (item != NULL) {
 106             next = item->next[level];
 107
 108             if (EXPECT_TRUE(sl->key_type == NULL)) {
 109                 d = item->key - key;
 110             } else {
 111                 d = sl->key_type->cmp((void *)item->key, (void *)key);
 112             }
 113
 114             if (d >= 0) {
 115                 if (d == 0 && unlink) {
 116                     pred->next[level] = next;
 117                     TRACE("s3", "find_preds: unlinked item from pred %p", pred, 0);
 118                     item = next;
 119                     next = (item != NULL) ? item->next[level] : DOES_NOT_EXIST;
 120                 }
 121                 break;
 122             }
 123
 124             pred = item;
 125             item = next;
 126         }
 127
 128         TRACE("s3", "find_preds: found pred %p next %p", pred, item);
 129
 130         if (level < n) {
 131             if (preds != NULL) {
 132                 preds[level] = pred;
 133             }
 134             if (succs != NULL) {
 135                 succs[level] = item;
 136             }
 137         }
 138     }
 139
 140     if (d == 0) {
 141         TRACE("s2", "find_preds: found matching item %p in skiplist, pred is %p", item, pred);
 142         return item;
 143     }
 144     TRACE("s2", "find_preds: found proper place for key %p in skiplist, pred is %p. returning null", key, pred);
 145     return NULL;
 146 }
 147
 148 // Fast find that does not return the node's predecessors.
 149 map_val_t sl_lookup (skiplist_t *sl, map_key_t key) {
 150     TRACE("s1", "sl_lookup: searching for key %p in skiplist %p", key, sl);
 151     node_t *item = find_preds(NULL, NULL, 0, sl, key, FALSE);
 152
 153     // If we found an <item> matching the <key> return its value.
 154     if (item != NULL) {
 155         map_val_t val = item->val;
 156         return val;
 157     }
 158
 159     TRACE("s1", "sl_lookup: no item in the skiplist matched the key", 0, 0);
 160     return DOES_NOT_EXIST;
 161 }
 162
 163 map_key_t sl_min_key (skiplist_t *sl) {
 164     node_t *item = sl->head->next[0];
 165     while (item != NULL)
 166         return item->key;
 167     return DOES_NOT_EXIST;
 168 }
 169
 170 map_val_t sl_cas (skiplist_t *sl, map_key_t key, map_val_t expectation, map_val_t new_val) {
 171     TRACE("s1", "sl_cas: key %p skiplist %p", key, sl);
 172     TRACE("s1", "sl_cas: expectation %p new value %p", expectation, new_val);
 173     ASSERT((int64_t)new_val > 0);
 174
 175     node_t *preds[MAX_LEVELS];
 176     node_t *nexts[MAX_LEVELS];
 177     node_t *new_item = NULL;
 178     int n = random_levels(sl);
 179     node_t *old_item = find_preds(preds, nexts, n, sl, key, FALSE);
 180
 181     // If there is already an item in the skiplist that matches the key just update its value.
 182     if (old_item != NULL) {
 183         map_val_t old_val = old_item->val;
 184         if (expectation == CAS_EXPECT_DOES_NOT_EXIST ||
 185            (expectation != CAS_EXPECT_WHATEVER && expectation != CAS_EXPECT_EXISTS && expectation != old_val)) {
 186             TRACE("s1", "sl_cas: the expectation was not met; the skiplist was not changed", 0, 0);
 187             return old_val;
 188         }
 189         old_item->val = new_val;
 190         return old_val;
 191     }
 192
 193     if (EXPECT_FALSE(expectation != CAS_EXPECT_DOES_NOT_EXIST && expectation != CAS_EXPECT_WHATEVER)) {
 194         TRACE("s1", "sl_cas: the expectation was not met, the skiplist was not changed", 0, 0);
 195         return DOES_NOT_EXIST; // failure, the caller expected an item for the <key> to already exist
 196     }
 197
 198     TRACE("s3", "sl_cas: inserting a new item between %p and %p", preds[0], nexts[0]);
 199
 200     // Create a new node and insert it into the skiplist.
 201     map_key_t new_key = sl->key_type == NULL ? key : (map_key_t)sl->key_type->clone((void *)key);
 202     new_item = node_alloc(n, new_key, new_val);
 203
 204     // Set <new_item>'s next pointers to their proper values
 205     for (int level = 0; level < new_item->num_levels; ++level) {
 206         new_item->next[level] = nexts[level];
 207     }
 208
 209     // Link <new_item> into <sl>
 210     for (int level = 0; level < new_item->num_levels; ++level) {
 211         preds[level]->next[level] = new_item;
 212     }
 213
 214     return DOES_NOT_EXIST; // success, inserted a new item
 215 }
 216
 217 map_val_t sl_remove (skiplist_t *sl, map_key_t key) {
 218     TRACE("s1", "sl_remove: removing item with key %p from skiplist %p", key, sl);
 219     node_t *preds[MAX_LEVELS];
 220     node_t *item = find_preds(preds, NULL, sl->high_water, sl, key, FALSE);
 221     if (item == NULL) {
 222         TRACE("s3", "sl_remove: remove failed, an item with a matching key does not exist in the skiplist", 0, 0);
 223         return DOES_NOT_EXIST;
 224     }
 225     map_val_t val = item->val;
 226
 227     // unlink the item
 228     find_preds(NULL, NULL, 0, sl, key, TRUE);
 229
 230     // free the node
 231     if (sl->key_type != NULL) {
 232         nbd_free((void *)item->key);
 233     }
 234     nbd_free(item);
 235
 236     return val;
 237 }
 238
 239 void sl_print (skiplist_t *sl) {
 240
 241     printf("high water: %d levels\n", sl->high_water);
 242     for (int level = MAX_LEVELS - 1; level >= 0; --level) {
 243         node_t *item = sl->head;
 244         if (item->next[level] == DOES_NOT_EXIST)
 245             continue;
 246         printf("(%d) ", level);
 247         int i = 0;
 248         while (item) {
 249             node_t *next = item->next[level];
 250             printf("%p ", item);
 251             item = next;
 252             if (i++ > 30) {
 253                 printf("...");
 254                 break;
 255             }
 256         }
 257         printf("\n");
 258         fflush(stdout);
 259     }
 260     node_t *item = sl->head;
 261     int i = 0;
 262     while (item) {
 263         printf("%p:0x%llx ", item, (uint64_t)item->key);
 264         if (item != sl->head) {
 265             printf("[%d]", item->num_levels);
 266         } else {
 267             printf("[HEAD]");
 268         }
 269         for (int level = 1; level < item->num_levels; ++level) {
 270             node_t *next = item->next[level];
 271             printf(" %p", next);
 272             if (item == sl->head && item->next[level] == DOES_NOT_EXIST)
 273                 break;
 274         }
 275         printf("\n");
 276         fflush(stdout);
 277         item = item->next[0];
 278         if (i++ > 30) {
 279             printf("...\n");
 280             break;
 281         }
 282     }
 283 }
 284
 285 sl_iter_t *sl_iter_begin (skiplist_t *sl, map_key_t key) {
 286     sl_iter_t *iter = (sl_iter_t *)nbd_malloc(sizeof(sl_iter_t));
 287     if (key != DOES_NOT_EXIST) {
 288         find_preds(NULL, &iter->next, 1, sl, key, FALSE);
 289     } else {
 290         iter->next = sl->head->next[0];
 291     }
 292     return iter;
 293 }
 294
 295 map_val_t sl_iter_next (sl_iter_t *iter, map_key_t *key_ptr) {
 296     assert(iter);
 297     node_t *item = iter->next;
 298     if (item == NULL) {
 299         iter->next = NULL;
 300         return DOES_NOT_EXIST;
 301     }
 302     iter->next = item->next[0];
 303     if (key_ptr != NULL) {
 304         *key_ptr = item->key;
 305     }
 306     return item->val;
 307 }
 308
 309 void sl_iter_free (sl_iter_t *iter) {
 310     nbd_free(iter);
 311 }