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     int height;                       /* Height of this node. */
  44     struct skiplist_node *forward[];  /* Links to the next nodes. */
  45 };
  46
  47 /* Skiplist container */
  48 struct skiplist {
  49     struct skiplist_node *header; /* Pointer to head node (not first
  50                                    * data node). */
  51     skiplist_comparator *cmp;     /* Pointer to the skiplist's comparison
  52                                    * function. */
  53     void *cfg;                    /* Pointer to optional comparison
  54                                    * configuration, used by the comparator. */
  55     int level;                    /* Maximum level currently in use. */
  56     uint32_t size;                /* Current number of nodes in skiplist. */
  57 };
  58
  59 /* Create a new skiplist_node with given level and data. */
  60 static struct skiplist_node *
  61 skiplist_create_node(int level, const void *object)
  62 {
  63     struct skiplist_node *new_node;
  64     size_t alloc_size = sizeof *new_node +
  65                         (level + 1) * sizeof new_node->forward[0];
  66
  67     new_node = xmalloc(alloc_size);
  68     new_node->data = object;
  69     new_node->height = level;
  70     memset(new_node->forward, 0,
  71            (level + 1) * sizeof new_node->forward[0]);
  72
  73     return new_node;
  74 }
  75
  76 /*
  77  * Create a new skiplist, configured with given data comparison function
  78  * and configuration.
  79  */
  80 struct skiplist *
  81 skiplist_create(skiplist_comparator object_comparator, void *configuration)
  82 {
  83     random_init();
  84     struct skiplist *sl;
  85
  86     sl = xmalloc(sizeof (struct skiplist));
  87     sl->cfg = configuration;
  88     sl->size = 0;
  89     sl->level = 0;
  90     sl->cmp = object_comparator;
  91     sl->header = skiplist_create_node(SKIPLIST_MAX_LEVELS, NULL);
  92
  93     return sl;
  94 }
  95
  96 /*
  97  * Move the cursor forward to the first node with associated data greater than
  98  * or equal to "value".
  99  */
 100 static struct skiplist_node *
 101 skiplist_forward_to_(struct skiplist *sl, const void *value,
 102                      struct skiplist_node **update)
 103 {
 104     struct skiplist_node *x = sl->header;
 105     int i;
 106
 107     /* Loop invariant: x < value */
 108     for (i = sl->level; i >= 0; i--) {
 109         while (x->forward[i] &&
 110                sl->cmp(x->forward[i]->data, value, sl->cfg) < 0) {
 111             x = x->forward[i];
 112         }
 113         /* x < value <= x->forward[1] */
 114         if (update) {
 115             update[i] = x;
 116         }
 117     }
 118     /* x < value <= x->forward[1] */
 119     x = x->forward[0];
 120     return x;
 121 }
 122
 123 struct skiplist_node *
 124 skiplist_forward_to(struct skiplist *sl, const void *value)
 125 {
 126     return skiplist_forward_to_(sl, value, NULL);
 127 }
 128
 129 /* Find the first exact match of value in the skiplist. */
 130 struct skiplist_node *
 131 skiplist_find(struct skiplist *sl, const void *value)
 132 {
 133     struct skiplist_node *x = skiplist_forward_to(sl, value);
 134
 135     return x && sl->cmp(x->data, value, sl->cfg) == 0 ? x : NULL;
 136 }
 137
 138 /*
 139  * Determine the level for a skiplist node by choosing a level N with
 140  * probability P(N) = 1/(2**(N+1)) in the range 0..32, with  the returned
 141  * level clamped at the current skiplist height plus 1.
 142  */
 143 static int
 144 skiplist_determine_level(struct skiplist *sl)
 145 {
 146     int lvl;
 147
 148     lvl = clz32(random_uint32());
 149
 150     return MIN(lvl, sl->level + 1);
 151 }
 152
 153 /* Insert data into a skiplist. */
 154 void
 155 skiplist_insert(struct skiplist *list, const void *value)
 156 {
 157     struct skiplist_node *update[SKIPLIST_MAX_LEVELS + 1];
 158     struct skiplist_node *x = skiplist_forward_to_(list, value, update);
 159     int i, lvl;
 160
 161     if (x && list->cmp(x->data, value, list->cfg) == 0) {
 162         x->data = value;
 163     } else {
 164         lvl = skiplist_determine_level(list);
 165         if (lvl > list->level) {
 166             for (i = list->level + 1; i <= lvl; i++) {
 167                 update[i] = list->header;
 168             }
 169             list->level = lvl;
 170         }
 171         x = skiplist_create_node(lvl, value);
 172         for (i = 0; i <= lvl; i++) {
 173             x->forward[i] = update[i]->forward[i];
 174             update[i]->forward[i] = x;
 175         }
 176         list->size++;
 177     }
 178 }
 179
 180 /* Remove first node with associated data equal to "value" from skiplist. */
 181 void *
 182 skiplist_delete(struct skiplist *list, const void *value)
 183 {
 184     struct skiplist_node *update[SKIPLIST_MAX_LEVELS + 1];
 185     struct skiplist_node *x;
 186     void *data = NULL;
 187     int i;
 188
 189     x = skiplist_forward_to_(list, value, update);
 190
 191     if (x && list->cmp(x->data, value, list->cfg) == 0) {
 192         for (i = 0; i <= list->level; i++) {
 193             if (!update[i]->forward[i] ||
 194                 list->cmp(update[i]->forward[i]->data, value,
 195                           list->cfg) != 0) {
 196                 break;
 197             }
 198             update[i]->forward[i] = x->forward[i];
 199         }
 200         data = CONST_CAST(void *, x->data);
 201
 202         free(x);
 203
 204         while (list->level > 0 && !list->header->forward[list->level]) {
 205             list->level--;
 206         }
 207         list->size--;
 208     }
 209     return data;
 210 }
 211
 212 /* Get the associated data value stored in a skiplist node. */
 213 void *
 214 skiplist_get_data(struct skiplist_node *node)
 215 {
 216     return node ? CONST_CAST(void *, node->data) : NULL;
 217 }
 218
 219 /* Get the number of items in a skiplist. */
 220 uint32_t
 221 skiplist_get_size(struct skiplist *sl)
 222 {
 223     return sl->size;
 224 }
 225
 226 /* Get the first node in a skiplist.  */
 227 struct skiplist_node *
 228 skiplist_first(struct skiplist *sl)
 229 {
 230     return sl->header->forward[0];
 231 }
 232
 233 /* Get a node's successor in a skiplist. */
 234 struct skiplist_node *
 235 skiplist_next(struct skiplist_node *node)
 236 {
 237     return node ? node->forward[0] : NULL;
 238 }
 239
 240 /*
 241  * Destroy a skiplist and free all nodes in the list.  If the "data_destroy"
 242  * function pointer is non-NULL, it will be called for each node as it is
 243  * removed to allow any needed cleanups to be performed on the associated
 244  * data.
 245  */
 246 void
 247 skiplist_destroy(struct skiplist *sl, void (*data_destroy)(void *))
 248 {
 249     struct skiplist_node *node, *next;
 250
 251     next = node = sl->header;
 252     while (next != NULL) {
 253         next = node->forward[0];
 254         if (data_destroy) {
 255             data_destroy(CONST_CAST(void *, node->data));
 256         }
 257         free(node);
 258         node = next;
 259     }
 260     free(sl);
 261 }