lib/skiplist.c

   1 /* Copyright (C) 2016 Hewlett Packard Enterprise Development LP
   2  * All Rights Reserved.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License"); you may
   5  * not use this file except in compliance with the License. You may obtain
   6  * a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  12  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  13  * License for the specific language governing permissions and limitations
  14  * under the License.
  15  */
  16
  17 /* Skiplist implementation based on:
  18  * "Skip List: A Probabilistic Alternative to Balanced Trees",
  19  * by William Pugh. */
  20
  21 #include <config.h>
  22 #include <stdio.h>
  23 #include <stdbool.h>
  24 #include <stdint.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27
  28 #include "skiplist.h"
  29 #include "random.h"
  30 #include "util.h"
  31
  32 /*
  33  * A maximum height level of 32 should be more than sufficient for
  34  * anticipated use cases, delivering good expected performance with
  35  * up to 2**32 list nodes. Changes to this limit will also require
  36  * changes in skiplist_determine_level().
  37  */
  38 #define SKIPLIST_MAX_LEVELS 32
  39
  40 /* Skiplist node container */
  41 struct skiplist_node {
  42     const void *data;                 /* Pointer to saved data. */
  43     struct skiplist_node *forward[];  /* Links to the next nodes. */
  44 };
  45
  46 /* Skiplist container */
  47 struct skiplist {
  48     struct skiplist_node *header; /* Pointer to head node (not first
  49                                    * data node). */
  50     skiplist_comparator *cmp;     /* Pointer to the skiplist's comparison
  51                                    * function. */
  52     void *cfg;                    /* Pointer to optional comparison
  53                                    * configuration, used by the comparator. */
  54     int level;                    /* Maximum level currently in use. */
  55     uint32_t size;                /* Current number of nodes in skiplist. */
  56 };
  57
  58 /* Create a new skiplist_node with given level and data. */
  59 static struct skiplist_node *
  60 skiplist_create_node(int level, const void *object)
  61 {
  62     struct skiplist_node *new_node;
  63     size_t alloc_size = sizeof *new_node +
  64                         (level + 1) * sizeof new_node->forward[0];
  65
  66     new_node = xmalloc(alloc_size);
  67     new_node->data = object;
  68     memset(new_node->forward, 0,
  69            (level + 1) * sizeof new_node->forward[0]);
  70
  71     return new_node;
  72 }
  73
  74 /*
  75  * Create a new skiplist, configured with given data comparison function
  76  * and configuration.
  77  */
  78 struct skiplist *
  79 skiplist_create(skiplist_comparator object_comparator, void *configuration)
  80 {
  81     random_init();
  82     struct skiplist *sl;
  83
  84     sl = xmalloc(sizeof (struct skiplist));
  85     sl->cfg = configuration;
  86     sl->size = 0;
  87     sl->level = 0;
  88     sl->cmp = object_comparator;
  89     sl->header = skiplist_create_node(SKIPLIST_MAX_LEVELS, NULL);
  90
  91     return sl;
  92 }
  93
  94 /*
  95  * Move the cursor forward to the first node with associated data greater than
  96  * or equal to "value".
  97  */
  98 static struct skiplist_node *
  99 skiplist_forward_to_(struct skiplist *sl, const void *value,
 100                      struct skiplist_node **update)
 101 {
 102     struct skiplist_node *x = sl->header;
 103     int i;
 104
 105     /* Loop invariant: x < value */
 106     for (i = sl->level; i >= 0; i--) {
 107         while (x->forward[i] &&
 108                sl->cmp(x->forward[i]->data, value, sl->cfg) < 0) {
 109             x = x->forward[i];
 110         }
 111         /* x < value <= x->forward[1] */
 112         if (update) {
 113             update[i] = x;
 114         }
 115     }
 116     /* x < value <= x->forward[1] */
 117     x = x->forward[0];
 118     return x;
 119 }
 120
 121 struct skiplist_node *
 122 skiplist_forward_to(struct skiplist *sl, const void *value)
 123 {
 124     return skiplist_forward_to_(sl, value, NULL);
 125 }
 126
 127 /* Find the first exact match of value in the skiplist. */
 128 struct skiplist_node *
 129 skiplist_find(struct skiplist *sl, const void *value)
 130 {
 131     struct skiplist_node *x = skiplist_forward_to(sl, value);
 132
 133     return x && sl->cmp(x->data, value, sl->cfg) == 0 ? x : NULL;
 134 }
 135
 136 /*
 137  * Determine the level for a skiplist node by choosing a level N with
 138  * probability P(N) = 1/(2**(N+1)) in the range 0..32, with  the returned
 139  * level clamped at the current skiplist height plus 1.
 140  */
 141 static int
 142 skiplist_determine_level(struct skiplist *sl)
 143 {
 144     int lvl;
 145
 146     lvl = clz32(random_uint32());
 147
 148     return MIN(lvl, sl->level + 1);
 149 }
 150
 151 /* Insert data into a skiplist. */
 152 void
 153 skiplist_insert(struct skiplist *list, const void *value)
 154 {
 155     struct skiplist_node *update[SKIPLIST_MAX_LEVELS + 1];
 156     struct skiplist_node *x = skiplist_forward_to_(list, value, update);
 157     int i, lvl;
 158
 159     if (x && list->cmp(x->data, value, list->cfg) == 0) {
 160         x->data = value;
 161     } else {
 162         lvl = skiplist_determine_level(list);
 163         if (lvl > list->level) {
 164             for (i = list->level + 1; i <= lvl; i++) {
 165                 update[i] = list->header;
 166             }
 167             list->level = lvl;
 168         }
 169         x = skiplist_create_node(lvl, value);
 170         for (i = 0; i <= lvl; i++) {
 171             x->forward[i] = update[i]->forward[i];
 172             update[i]->forward[i] = x;
 173         }
 174         list->size++;
 175     }
 176 }
 177
 178 /* Remove first node with associated data equal to "value" from skiplist. */
 179 void *
 180 skiplist_delete(struct skiplist *list, const void *value)
 181 {
 182     struct skiplist_node *update[SKIPLIST_MAX_LEVELS + 1];
 183     struct skiplist_node *x;
 184     void *data = NULL;
 185     int i;
 186
 187     x = skiplist_forward_to_(list, value, update);
 188
 189     if (x && list->cmp(x->data, value, list->cfg) == 0) {
 190         for (i = 0; i <= list->level; i++) {
 191             if (update[i]->forward[i] != x) {
 192                 break;
 193             }
 194             update[i]->forward[i] = x->forward[i];
 195         }
 196         data = CONST_CAST(void *, x->data);
 197
 198         free(x);
 199
 200         while (list->level > 0 && !list->header->forward[list->level]) {
 201             list->level--;
 202         }
 203         list->size--;
 204     }
 205     return data;
 206 }
 207
 208 /* Get the associated data value stored in a skiplist node. */
 209 void *
 210 skiplist_get_data(struct skiplist_node *node)
 211 {
 212     return node ? CONST_CAST(void *, node->data) : NULL;
 213 }
 214
 215 /* Get the number of items in a skiplist. */
 216 uint32_t
 217 skiplist_get_size(struct skiplist *sl)
 218 {
 219     return sl->size;
 220 }
 221
 222 /* Get the first node in a skiplist.  */
 223 struct skiplist_node *
 224 skiplist_first(struct skiplist *sl)
 225 {
 226     return sl->header->forward[0];
 227 }
 228
 229 /* Get a node's successor in a skiplist. */
 230 struct skiplist_node *
 231 skiplist_next(struct skiplist_node *node)
 232 {
 233     return node ? node->forward[0] : NULL;
 234 }
 235
 236 /*
 237  * Destroy a skiplist and free all nodes in the list.  If the "data_destroy"
 238  * function pointer is non-NULL, it will be called for each node as it is
 239  * removed to allow any needed cleanups to be performed on the associated
 240  * data.
 241  */
 242 void
 243 skiplist_destroy(struct skiplist *sl, void (*data_destroy)(void *))
 244 {
 245     struct skiplist_node *node, *next;
 246
 247     next = node = sl->header;
 248     while (next != NULL) {
 249         next = node->forward[0];
 250         if (data_destroy) {
 251             data_destroy(CONST_CAST(void *, node->data));
 252         }
 253         free(node);
 254         node = next;
 255     }
 256     free(sl);
 257 }