Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 1 | /* xf86drmSL.c -- Skip list support |
| 2 | * Created: Mon May 10 09:28:13 1999 by faith@precisioninsight.com |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 3 | * |
| 4 | * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas. |
| 5 | * All Rights Reserved. |
| 6 | * |
| 7 | * Permission is hereby granted, free of charge, to any person obtaining a |
| 8 | * copy of this software and associated documentation files (the "Software"), |
| 9 | * to deal in the Software without restriction, including without limitation |
| 10 | * the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| 11 | * and/or sell copies of the Software, and to permit persons to whom the |
| 12 | * Software is furnished to do so, subject to the following conditions: |
| 13 | * |
| 14 | * The above copyright notice and this permission notice (including the next |
| 15 | * paragraph) shall be included in all copies or substantial portions of the |
| 16 | * Software. |
| 17 | * |
| 18 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 19 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| 20 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| 21 | * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR |
| 22 | * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, |
| 23 | * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER |
| 24 | * DEALINGS IN THE SOFTWARE. |
| 25 | * |
Rik Faith | 1c8b2b5 | 2000-06-13 14:22:03 +0000 | [diff] [blame] | 26 | * Authors: Rickard E. (Rik) Faith <faith@valinux.com> |
| 27 | * |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 28 | * DESCRIPTION |
| 29 | * |
| 30 | * This file contains a straightforward skip list implementation.n |
| 31 | * |
| 32 | * FUTURE ENHANCEMENTS |
| 33 | * |
| 34 | * REFERENCES |
| 35 | * |
| 36 | * [Pugh90] William Pugh. Skip Lists: A Probabilistic Alternative to |
| 37 | * Balanced Trees. CACM 33(6), June 1990, pp. 668-676. |
| 38 | * |
| 39 | */ |
| 40 | |
George Sapountzis | b69b426 | 2007-04-26 14:15:55 +0300 | [diff] [blame] | 41 | #include <stdio.h> |
| 42 | #include <stdlib.h> |
Adam Jackson | f28dddb | 2005-11-30 03:51:46 +0000 | [diff] [blame] | 43 | |
Lucas De Marchi | 26f9ce5 | 2018-09-13 15:42:26 -0700 | [diff] [blame] | 44 | #include "libdrm_macros.h" |
Jan Vesely | 7d8c946 | 2015-03-20 16:58:29 -0400 | [diff] [blame] | 45 | #include "xf86drm.h" |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 46 | |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 47 | #define SL_LIST_MAGIC 0xfacade00LU |
| 48 | #define SL_ENTRY_MAGIC 0x00fab1edLU |
| 49 | #define SL_FREED_MAGIC 0xdecea5edLU |
| 50 | #define SL_MAX_LEVEL 16 |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 51 | #define SL_RANDOM_SEED 0xc01055a1LU |
| 52 | |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 53 | #define SL_RANDOM_DECL static void *state = NULL |
| 54 | #define SL_RANDOM_INIT(seed) if (!state) state = drmRandomCreate(seed) |
| 55 | #define SL_RANDOM drmRandom(state) |
| 56 | |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 57 | typedef struct SLEntry { |
| 58 | unsigned long magic; /* SL_ENTRY_MAGIC */ |
| 59 | unsigned long key; |
| 60 | void *value; |
| 61 | int levels; |
| 62 | struct SLEntry *forward[1]; /* variable sized array */ |
| 63 | } SLEntry, *SLEntryPtr; |
| 64 | |
| 65 | typedef struct SkipList { |
| 66 | unsigned long magic; /* SL_LIST_MAGIC */ |
| 67 | int level; |
| 68 | int count; |
| 69 | SLEntryPtr head; |
| 70 | SLEntryPtr p0; /* Position for iteration */ |
| 71 | } SkipList, *SkipListPtr; |
| 72 | |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 73 | static SLEntryPtr SLCreateEntry(int max_level, unsigned long key, void *value) |
| 74 | { |
| 75 | SLEntryPtr entry; |
| 76 | |
| 77 | if (max_level < 0 || max_level > SL_MAX_LEVEL) max_level = SL_MAX_LEVEL; |
| 78 | |
Jan Vesely | 7d8c946 | 2015-03-20 16:58:29 -0400 | [diff] [blame] | 79 | entry = drmMalloc(sizeof(*entry) |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 80 | + (max_level + 1) * sizeof(entry->forward[0])); |
| 81 | if (!entry) return NULL; |
| 82 | entry->magic = SL_ENTRY_MAGIC; |
| 83 | entry->key = key; |
| 84 | entry->value = value; |
| 85 | entry->levels = max_level + 1; |
| 86 | |
| 87 | return entry; |
| 88 | } |
| 89 | |
| 90 | static int SLRandomLevel(void) |
| 91 | { |
| 92 | int level = 1; |
| 93 | SL_RANDOM_DECL; |
| 94 | |
| 95 | SL_RANDOM_INIT(SL_RANDOM_SEED); |
| 96 | |
| 97 | while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level; |
| 98 | return level; |
| 99 | } |
| 100 | |
Lucas De Marchi | 26f9ce5 | 2018-09-13 15:42:26 -0700 | [diff] [blame] | 101 | drm_public void *drmSLCreate(void) |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 102 | { |
| 103 | SkipListPtr list; |
| 104 | int i; |
| 105 | |
Jan Vesely | 7d8c946 | 2015-03-20 16:58:29 -0400 | [diff] [blame] | 106 | list = drmMalloc(sizeof(*list)); |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 107 | if (!list) return NULL; |
| 108 | list->magic = SL_LIST_MAGIC; |
| 109 | list->level = 0; |
| 110 | list->head = SLCreateEntry(SL_MAX_LEVEL, 0, NULL); |
| 111 | list->count = 0; |
| 112 | |
| 113 | for (i = 0; i <= SL_MAX_LEVEL; i++) list->head->forward[i] = NULL; |
| 114 | |
| 115 | return list; |
| 116 | } |
| 117 | |
Lucas De Marchi | 26f9ce5 | 2018-09-13 15:42:26 -0700 | [diff] [blame] | 118 | drm_public int drmSLDestroy(void *l) |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 119 | { |
| 120 | SkipListPtr list = (SkipListPtr)l; |
| 121 | SLEntryPtr entry; |
| 122 | SLEntryPtr next; |
| 123 | |
| 124 | if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ |
| 125 | |
| 126 | for (entry = list->head; entry; entry = next) { |
| 127 | if (entry->magic != SL_ENTRY_MAGIC) return -1; /* Bad magic */ |
| 128 | next = entry->forward[0]; |
| 129 | entry->magic = SL_FREED_MAGIC; |
Jan Vesely | 7d8c946 | 2015-03-20 16:58:29 -0400 | [diff] [blame] | 130 | drmFree(entry); |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 131 | } |
| 132 | |
| 133 | list->magic = SL_FREED_MAGIC; |
Jan Vesely | 7d8c946 | 2015-03-20 16:58:29 -0400 | [diff] [blame] | 134 | drmFree(list); |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 135 | return 0; |
| 136 | } |
| 137 | |
| 138 | static SLEntryPtr SLLocate(void *l, unsigned long key, SLEntryPtr *update) |
| 139 | { |
| 140 | SkipListPtr list = (SkipListPtr)l; |
| 141 | SLEntryPtr entry; |
| 142 | int i; |
| 143 | |
| 144 | if (list->magic != SL_LIST_MAGIC) return NULL; |
| 145 | |
| 146 | for (i = list->level, entry = list->head; i >= 0; i--) { |
| 147 | while (entry->forward[i] && entry->forward[i]->key < key) |
| 148 | entry = entry->forward[i]; |
| 149 | update[i] = entry; |
| 150 | } |
| 151 | |
| 152 | return entry->forward[0]; |
| 153 | } |
| 154 | |
Lucas De Marchi | 26f9ce5 | 2018-09-13 15:42:26 -0700 | [diff] [blame] | 155 | drm_public int drmSLInsert(void *l, unsigned long key, void *value) |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 156 | { |
| 157 | SkipListPtr list = (SkipListPtr)l; |
| 158 | SLEntryPtr entry; |
| 159 | SLEntryPtr update[SL_MAX_LEVEL + 1]; |
| 160 | int level; |
| 161 | int i; |
| 162 | |
| 163 | if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ |
| 164 | |
| 165 | entry = SLLocate(list, key, update); |
| 166 | |
| 167 | if (entry && entry->key == key) return 1; /* Already in list */ |
| 168 | |
| 169 | |
| 170 | level = SLRandomLevel(); |
| 171 | if (level > list->level) { |
| 172 | level = ++list->level; |
| 173 | update[level] = list->head; |
| 174 | } |
| 175 | |
| 176 | entry = SLCreateEntry(level, key, value); |
| 177 | |
| 178 | /* Fix up forward pointers */ |
| 179 | for (i = 0; i <= level; i++) { |
| 180 | entry->forward[i] = update[i]->forward[i]; |
| 181 | update[i]->forward[i] = entry; |
| 182 | } |
| 183 | |
| 184 | ++list->count; |
| 185 | return 0; /* Added to table */ |
| 186 | } |
| 187 | |
Lucas De Marchi | 26f9ce5 | 2018-09-13 15:42:26 -0700 | [diff] [blame] | 188 | drm_public int drmSLDelete(void *l, unsigned long key) |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 189 | { |
| 190 | SkipListPtr list = (SkipListPtr)l; |
| 191 | SLEntryPtr update[SL_MAX_LEVEL + 1]; |
| 192 | SLEntryPtr entry; |
| 193 | int i; |
| 194 | |
| 195 | if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ |
| 196 | |
| 197 | entry = SLLocate(list, key, update); |
| 198 | |
| 199 | if (!entry || entry->key != key) return 1; /* Not found */ |
| 200 | |
| 201 | /* Fix up forward pointers */ |
| 202 | for (i = 0; i <= list->level; i++) { |
| 203 | if (update[i]->forward[i] == entry) |
| 204 | update[i]->forward[i] = entry->forward[i]; |
| 205 | } |
| 206 | |
| 207 | entry->magic = SL_FREED_MAGIC; |
Jan Vesely | 7d8c946 | 2015-03-20 16:58:29 -0400 | [diff] [blame] | 208 | drmFree(entry); |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 209 | |
| 210 | while (list->level && !list->head->forward[list->level]) --list->level; |
| 211 | --list->count; |
| 212 | return 0; |
| 213 | } |
| 214 | |
Lucas De Marchi | 26f9ce5 | 2018-09-13 15:42:26 -0700 | [diff] [blame] | 215 | drm_public int drmSLLookup(void *l, unsigned long key, void **value) |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 216 | { |
| 217 | SkipListPtr list = (SkipListPtr)l; |
| 218 | SLEntryPtr update[SL_MAX_LEVEL + 1]; |
| 219 | SLEntryPtr entry; |
| 220 | |
| 221 | entry = SLLocate(list, key, update); |
| 222 | |
| 223 | if (entry && entry->key == key) { |
| 224 | *value = entry; |
| 225 | return 0; |
| 226 | } |
| 227 | *value = NULL; |
| 228 | return -1; |
| 229 | } |
| 230 | |
Lucas De Marchi | 26f9ce5 | 2018-09-13 15:42:26 -0700 | [diff] [blame] | 231 | drm_public int drmSLLookupNeighbors(void *l, unsigned long key, |
| 232 | unsigned long *prev_key, void **prev_value, |
| 233 | unsigned long *next_key, void **next_value) |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 234 | { |
| 235 | SkipListPtr list = (SkipListPtr)l; |
Jan Vesely | 3b2ee2b | 2015-02-27 12:20:32 -0500 | [diff] [blame] | 236 | SLEntryPtr update[SL_MAX_LEVEL + 1] = {0}; |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 237 | int retcode = 0; |
| 238 | |
Jan Vesely | 3b2ee2b | 2015-02-27 12:20:32 -0500 | [diff] [blame] | 239 | SLLocate(list, key, update); |
| 240 | |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 241 | *prev_key = *next_key = key; |
| 242 | *prev_value = *next_value = NULL; |
Jan Vesely | 3b2ee2b | 2015-02-27 12:20:32 -0500 | [diff] [blame] | 243 | |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 244 | if (update[0]) { |
| 245 | *prev_key = update[0]->key; |
| 246 | *prev_value = update[0]->value; |
| 247 | ++retcode; |
| 248 | if (update[0]->forward[0]) { |
| 249 | *next_key = update[0]->forward[0]->key; |
| 250 | *next_value = update[0]->forward[0]->value; |
| 251 | ++retcode; |
| 252 | } |
| 253 | } |
| 254 | return retcode; |
| 255 | } |
| 256 | |
Lucas De Marchi | 26f9ce5 | 2018-09-13 15:42:26 -0700 | [diff] [blame] | 257 | drm_public int drmSLNext(void *l, unsigned long *key, void **value) |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 258 | { |
| 259 | SkipListPtr list = (SkipListPtr)l; |
| 260 | SLEntryPtr entry; |
| 261 | |
| 262 | if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ |
| 263 | |
| 264 | entry = list->p0; |
| 265 | |
| 266 | if (entry) { |
| 267 | list->p0 = entry->forward[0]; |
| 268 | *key = entry->key; |
| 269 | *value = entry->value; |
| 270 | return 1; |
| 271 | } |
| 272 | list->p0 = NULL; |
| 273 | return 0; |
| 274 | } |
| 275 | |
Lucas De Marchi | 26f9ce5 | 2018-09-13 15:42:26 -0700 | [diff] [blame] | 276 | drm_public int drmSLFirst(void *l, unsigned long *key, void **value) |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 277 | { |
| 278 | SkipListPtr list = (SkipListPtr)l; |
| 279 | |
| 280 | if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ |
| 281 | |
| 282 | list->p0 = list->head->forward[0]; |
Adam Jackson | 22e41ef | 2006-02-20 23:09:00 +0000 | [diff] [blame] | 283 | return drmSLNext(list, key, value); |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 284 | } |
| 285 | |
| 286 | /* Dump internal data structures for debugging. */ |
Lucas De Marchi | 26f9ce5 | 2018-09-13 15:42:26 -0700 | [diff] [blame] | 287 | drm_public void drmSLDump(void *l) |
Daryll Strauss | b3a5766 | 1999-12-05 01:19:48 +0000 | [diff] [blame] | 288 | { |
| 289 | SkipListPtr list = (SkipListPtr)l; |
| 290 | SLEntryPtr entry; |
| 291 | int i; |
| 292 | |
| 293 | if (list->magic != SL_LIST_MAGIC) { |
| 294 | printf("Bad magic: 0x%08lx (expected 0x%08lx)\n", |
| 295 | list->magic, SL_LIST_MAGIC); |
| 296 | return; |
| 297 | } |
| 298 | |
| 299 | printf("Level = %d, count = %d\n", list->level, list->count); |
| 300 | for (entry = list->head; entry; entry = entry->forward[0]) { |
| 301 | if (entry->magic != SL_ENTRY_MAGIC) { |
| 302 | printf("Bad magic: 0x%08lx (expected 0x%08lx)\n", |
| 303 | list->magic, SL_ENTRY_MAGIC); |
| 304 | } |
| 305 | printf("\nEntry %p <0x%08lx, %p> has %2d levels\n", |
| 306 | entry, entry->key, entry->value, entry->levels); |
| 307 | for (i = 0; i < entry->levels; i++) { |
| 308 | if (entry->forward[i]) { |
| 309 | printf(" %2d: %p <0x%08lx, %p>\n", |
| 310 | i, |
| 311 | entry->forward[i], |
| 312 | entry->forward[i]->key, |
| 313 | entry->forward[i]->value); |
| 314 | } else { |
| 315 | printf(" %2d: %p\n", i, entry->forward[i]); |
| 316 | } |
| 317 | } |
| 318 | } |
| 319 | } |