jseward | 2886b0e | 2004-01-04 03:46:11 +0000 | [diff] [blame] | 1 | |
| 2 | /* |
| 3 | This file is part of Valgrind, an extensible x86 protected-mode |
| 4 | emulator for monitoring program execution on x86-Unixes. |
| 5 | |
| 6 | Copyright (C) 2002-2004 Nicholas Nethercote |
| 7 | njn25@cam.ac.uk |
| 8 | |
| 9 | This program is free software; you can redistribute it and/or |
| 10 | modify it under the terms of the GNU General Public License as |
| 11 | published by the Free Software Foundation; either version 2 of the |
| 12 | License, or (at your option) any later version. |
| 13 | |
| 14 | This program is distributed in the hope that it will be useful, but |
| 15 | WITHOUT ANY WARRANTY; without even the implied warranty of |
| 16 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 17 | General Public License for more details. |
| 18 | |
| 19 | You should have received a copy of the GNU General Public License |
| 20 | along with this program; if not, write to the Free Software |
| 21 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
| 22 | 02111-1307, USA. |
| 23 | |
| 24 | The GNU General Public License is contained in the file COPYING. |
| 25 | */ |
| 26 | |
fitzhardinge | c9730c4 | 2004-06-30 01:27:06 +0000 | [diff] [blame] | 27 | /* |
| 28 | This file implements a generic skip-list type. |
| 29 | |
| 30 | Skip-lists are described in William Pugh, Skip Lists: A |
| 31 | Probabilistic Alternative to Balanced Trees, CACM, 33(6):668-676, |
| 32 | June 1990. |
| 33 | http://www.cs.unc.edu/~baruah/Teaching/2002f/HandOuts/skiplist-CACM.pdf |
| 34 | |
| 35 | Skip-lists are a randomized linked-list, where a node in the list |
| 36 | has at least one "next" pointer, but may have more. When |
| 37 | traversing the list, the "higher" next pointers allow you to skip |
| 38 | multiple list entries, allowing you to find the right place |
| 39 | quickly. |
| 40 | |
| 41 | On average, 1/2 the entries have one next pointer, 1/4 have 2, 1/8 |
| 42 | have 3, etc. This means that the skiplist has the same search |
| 43 | complexity as a balanced binary tree, but there is no need to |
| 44 | rebalance or do any other structural changes. The randomness also |
| 45 | means that it is invulnerable to pathalogical workloads. |
| 46 | |
| 47 | Because the each node can be a different size, this implementation |
| 48 | puts the SkipNode structure at the end of the allocation, with the |
| 49 | node data starting at the beginning. |
| 50 | |
| 51 | low address ->+---------------+ ^ |
| 52 | | list data | | |
| 53 | key offset->: key : structure size |
| 54 | | | | |
| 55 | +---------------+ V |
| 56 | | struct | |
| 57 | | SkipNode | |
| 58 | +- - - - - - - -+ |
| 59 | | next pointers | |
| 60 | : : |
| 61 | |
| 62 | |
| 63 | When you declare the list with SKIPLIST_INIT, you specify the |
| 64 | structure for each list node, structure member you want to use as a |
| 65 | key, and the function for comparing keys. |
| 66 | |
| 67 | Each node must be allocated with SkipNode_Alloc, which allocates |
| 68 | enough space for the client data, the SkipNode structure, and the |
| 69 | next pointers for this node. |
| 70 | |
| 71 | The helper functions data_of_node and node_of_data do the correct |
| 72 | pointer arithmetic to sort all this out. The SkipNode also has a |
| 73 | magic number which is checked after each operation to make sure |
| 74 | that we're really operating on a SkipNode. |
| 75 | |
| 76 | The first node of the list, the head node, is special. It contains |
| 77 | the maximum number of next pointers (SK_MAXHEIGHT). It has no data |
| 78 | associated with it, and it always compares less-than to all other |
| 79 | nodes. Because it has no data attached to it, it is always an |
| 80 | error to try and use data_of_node on it. To detect this problem, |
| 81 | it has a different magic number from all other SkipNodes so that it |
| 82 | won't be accidentally used. |
| 83 | */ |
| 84 | |
nethercote | f1e5e15 | 2004-09-01 23:58:16 +0000 | [diff] [blame] | 85 | #include "core.h" |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 86 | |
| 87 | #include <stdlib.h> |
| 88 | |
| 89 | #define SKIPLIST_DEBUG 0 |
| 90 | |
| 91 | #define SK_MAXHEIGHT 20 /* 2^20 elements */ |
| 92 | #define SKIPLIST_MAGIC 0x5b1ff872 |
| 93 | #define SKIPLIST_HEAD_MAGIC (~SKIPLIST_MAGIC) |
| 94 | |
| 95 | |
| 96 | #if SKIPLIST_DEBUG |
| 97 | #define inline |
| 98 | #endif /* SKIPLIST_DEBUG */ |
| 99 | |
| 100 | struct _SkipNode { |
| 101 | UInt magic; |
| 102 | UShort level; /* level is the max level (level == 0 means 1 next pointer) */ |
| 103 | SkipNode *next[0]; |
| 104 | }; |
| 105 | |
| 106 | |
fitzhardinge | c9730c4 | 2004-06-30 01:27:06 +0000 | [diff] [blame] | 107 | /* |
| 108 | Compute the height of a new node. 1/2 will be 1, 1/4 2, 1/8 3, |
| 109 | etc. |
| 110 | */ |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 111 | static inline Int get_height(void) |
| 112 | { |
| 113 | UInt ret = 0; |
| 114 | |
thughes | aecb291 | 2004-10-28 08:09:05 +0000 | [diff] [blame] | 115 | while((ret < SK_MAXHEIGHT - 1) && (random() & 1)) |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 116 | ret++; |
| 117 | |
| 118 | return ret; |
| 119 | } |
| 120 | |
fitzhardinge | c9730c4 | 2004-06-30 01:27:06 +0000 | [diff] [blame] | 121 | /* |
| 122 | Given a pointer to the node's data, return a pointer to the key. |
| 123 | */ |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 124 | static inline void *key_of_data(const SkipList *l, void *d) |
| 125 | { |
| 126 | return (void *)((Char *)d + l->keyoff); |
| 127 | } |
| 128 | |
fitzhardinge | c9730c4 | 2004-06-30 01:27:06 +0000 | [diff] [blame] | 129 | /* |
| 130 | Given a pointer to the node's data, return the pointer to the SkipNode |
| 131 | structure. If the node has a bad magic number, it will die with an |
| 132 | assertion failure. |
| 133 | */ |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 134 | static inline SkipNode *node_of_data(const SkipList *l, const void *d) |
| 135 | { |
| 136 | SkipNode *n = (SkipNode *)((Char *)d + l->size); |
| 137 | |
| 138 | if (SKIPLIST_DEBUG && n->magic != SKIPLIST_MAGIC) |
| 139 | VG_(printf)("bad magic on node %p = %x (not %x)\n", |
| 140 | n, n->magic, SKIPLIST_MAGIC); |
| 141 | |
| 142 | vg_assert(n->magic == SKIPLIST_MAGIC); |
| 143 | |
| 144 | return n; |
| 145 | } |
| 146 | |
fitzhardinge | c9730c4 | 2004-06-30 01:27:06 +0000 | [diff] [blame] | 147 | /* |
| 148 | Given a SkipNode structure, return the pointer to the node's data. |
| 149 | */ |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 150 | static inline void *data_of_node(const SkipList *l, const SkipNode *n) |
| 151 | { |
| 152 | if (SKIPLIST_DEBUG && n->magic != SKIPLIST_MAGIC) |
| 153 | VG_(printf)("bad magic on node %p = %x (not %x)\n", |
| 154 | n, n->magic, SKIPLIST_MAGIC); |
| 155 | |
| 156 | vg_assert(n->magic == SKIPLIST_MAGIC); |
| 157 | return (void *)((Char *)n - l->size); |
| 158 | } |
| 159 | |
fitzhardinge | c9730c4 | 2004-06-30 01:27:06 +0000 | [diff] [blame] | 160 | /* |
| 161 | Given a SkipNode structure, return the pointer to the node's key. |
| 162 | */ |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 163 | static inline void *key_of_node(const SkipList *l, const SkipNode *n) |
| 164 | { |
| 165 | return key_of_data(l, data_of_node(l, n)); |
| 166 | } |
| 167 | |
| 168 | static inline void validate_skiplist(const SkipList *l, const Char *where) |
| 169 | { |
| 170 | #if SKIPLIST_DEBUG |
| 171 | const SkipNode *prev[SK_MAXHEIGHT]; |
| 172 | Int i; |
| 173 | const SkipNode *n, *next; |
| 174 | |
| 175 | VG_(printf)("---------------- %s ----------------\n", where); |
| 176 | |
| 177 | if (l->head == NULL) |
| 178 | return; |
| 179 | |
| 180 | for(i = 0; i <= l->head->level; i++) { |
| 181 | VG_(printf)("l->head->next[%d]=%p\n", |
| 182 | i, l->head->next[i]); |
| 183 | prev[i] = l->head->next[i]; |
| 184 | } |
| 185 | |
| 186 | for(n = l->head->next[0]; n != NULL; n = next) { |
| 187 | next = n->next[0]; |
| 188 | |
| 189 | VG_(printf)("n=%p next=%p, n->level=%d k=%s\n", |
| 190 | n, next, n->level, (*l->strkey)(key_of_node(l, n))); |
| 191 | for(i = 0; i <= n->level; i++) { |
| 192 | VG_(printf)(" n->next[%d] = %p\n", |
| 193 | i, n->next[i]); |
| 194 | VG_(printf)(" prev[%d] = %p\n", |
| 195 | i, prev[i]); |
| 196 | } |
| 197 | |
| 198 | vg_assert(l->head->level >= n->level); |
| 199 | |
| 200 | for(i = 0; i <= n->level; i++) |
| 201 | vg_assert(prev[i] == n); |
| 202 | |
| 203 | for(i = 0; i <= n->level; i++) |
| 204 | prev[i] = n->next[i]; |
| 205 | |
| 206 | vg_assert(next == NULL || (l->cmp)(key_of_node(l, n), key_of_node(l, next)) < 0); |
| 207 | } |
| 208 | #endif /* SKIPLIST_DEBUG */ |
| 209 | } |
| 210 | |
| 211 | void *VG_(SkipNode_Alloc)(const SkipList *l) |
| 212 | { |
fitzhardinge | 24503fc | 2004-07-27 21:49:23 +0000 | [diff] [blame] | 213 | UInt size; |
| 214 | Int h; |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 215 | SkipNode *n; |
| 216 | Char *ret; |
| 217 | |
fitzhardinge | 24503fc | 2004-07-27 21:49:23 +0000 | [diff] [blame] | 218 | h = get_height(); |
| 219 | |
| 220 | size = l->size; |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 221 | size += sizeof(SkipNode) + (h+1)*sizeof(SkipNode *); |
| 222 | |
| 223 | if (l->arena == -1) |
nethercote | 60f5b82 | 2004-01-26 17:24:42 +0000 | [diff] [blame] | 224 | *(Short *)&l->arena = VG_AR_TOOL; |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 225 | |
| 226 | ret = VG_(arena_malloc)(l->arena, size); |
| 227 | |
| 228 | if (ret == NULL) |
| 229 | return NULL; |
| 230 | |
| 231 | n = (SkipNode *)(ret + l->size); |
| 232 | n->level = h; |
| 233 | n->magic = SKIPLIST_MAGIC; |
| 234 | |
fitzhardinge | 24503fc | 2004-07-27 21:49:23 +0000 | [diff] [blame] | 235 | VG_(memset)(n->next, 0, sizeof(n->next[0]) * (h+1)); |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 236 | |
| 237 | return ret; |
| 238 | } |
| 239 | |
| 240 | void VG_(SkipNode_Free)(const SkipList *l, void *p) |
| 241 | { |
| 242 | if (SKIPLIST_DEBUG) { |
| 243 | SkipNode *n = node_of_data(l, p); |
| 244 | |
| 245 | VG_(printf)("SkipNode_Free: freeing %p (node %p)\n", |
| 246 | p, n); |
| 247 | n->magic = 0x55ffaabb; |
| 248 | } |
| 249 | VG_(arena_free)(l->arena, p); |
| 250 | } |
| 251 | |
| 252 | void *VG_(SkipNode_First)(const SkipList *l) |
| 253 | { |
| 254 | SkipNode *n = l->head ? l->head->next[0] : NULL; |
| 255 | |
| 256 | if (n == NULL) |
| 257 | return NULL; |
| 258 | else |
| 259 | return data_of_node(l, n); |
| 260 | } |
| 261 | |
| 262 | void *VG_(SkipNode_Next)(const SkipList *l, void *data) |
| 263 | { |
| 264 | SkipNode *n = node_of_data(l, data); |
| 265 | |
| 266 | n = n->next[0]; |
| 267 | |
| 268 | if (n == NULL) |
| 269 | return NULL; |
| 270 | |
| 271 | return data_of_node(l, n); |
| 272 | } |
| 273 | |
| 274 | |
| 275 | |
| 276 | static Int cmp(const SkipList *l, SkipNode *n, void *k2) |
| 277 | { |
| 278 | void *k1 = key_of_node(l, n); |
| 279 | |
| 280 | if (k1 == k2) |
| 281 | return 0; |
| 282 | |
| 283 | if (l->head == n) |
| 284 | return -1; |
| 285 | |
| 286 | return (l->cmp)(k1, k2); |
| 287 | } |
| 288 | |
| 289 | /* Search the list for k; it either returns the k if it exists, or the |
| 290 | one before if not. */ |
| 291 | static SkipNode *SkipList__Find(const SkipList *l, void *k, SkipNode **prevs) |
| 292 | { |
| 293 | SkipNode *n; |
| 294 | Int lvl; |
| 295 | |
| 296 | if (SKIPLIST_DEBUG) |
| 297 | VG_(printf)("SkipList__Find: finding %s\n", (*l->strkey)(k)); |
| 298 | |
| 299 | validate_skiplist(l, "SkipList__Find"); |
| 300 | |
| 301 | if (l->head == NULL) |
| 302 | return NULL; |
| 303 | |
| 304 | for(lvl = l->head->level, n = l->head; lvl >= 0; lvl--) { |
| 305 | while(n->next[lvl] != NULL && cmp(l, n->next[lvl], k) < 0) { |
| 306 | if (SKIPLIST_DEBUG) |
| 307 | VG_(printf)("SkipList__Find: n=%p n->next[%d]=%p\n", |
| 308 | n, lvl, n->next[lvl]); |
| 309 | n = n->next[lvl]; |
| 310 | } |
| 311 | if (prevs) |
| 312 | prevs[lvl] = n; |
| 313 | } |
| 314 | |
| 315 | /* XXX Is there a cleaner way of getting this? |
| 316 | |
| 317 | If we get an exact match, return it. |
| 318 | If we get the head, return NULL. |
| 319 | Otherwise return the one before where the hit would be. |
| 320 | */ |
| 321 | if (n->next[0] != NULL && cmp(l, n->next[0], k) == 0) |
| 322 | n = n->next[0]; |
| 323 | if (n == l->head) |
| 324 | n = NULL; |
| 325 | |
| 326 | if (SKIPLIST_DEBUG) { |
| 327 | |
| 328 | VG_(printf)("SkipList__Find returning node %p\n", n); |
| 329 | |
| 330 | if (n == NULL) { |
| 331 | SkipNode *nn; |
| 332 | |
| 333 | for(nn = l->head->next[0]; nn != NULL; nn = nn->next[0]) |
| 334 | vg_assert(cmp(l, nn, k) != 0); |
| 335 | } else |
| 336 | vg_assert(cmp(l, n, k) <= 0); |
| 337 | } |
| 338 | |
| 339 | return n; |
| 340 | } |
| 341 | |
| 342 | void *VG_(SkipList_Find)(const SkipList *l, void *k) |
| 343 | { |
| 344 | SkipNode *n = SkipList__Find(l, k, NULL); |
| 345 | |
| 346 | if (n != NULL) |
| 347 | return data_of_node(l, n); |
| 348 | return NULL; |
| 349 | } |
| 350 | |
| 351 | void VG_(SkipList_Insert)(SkipList *l, void *data) |
| 352 | { |
| 353 | SkipNode *update[SK_MAXHEIGHT]; |
fitzhardinge | 24503fc | 2004-07-27 21:49:23 +0000 | [diff] [blame] | 354 | SkipNode *n, *nn; |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 355 | void *k = key_of_data(l, data); |
| 356 | Int i; |
| 357 | |
| 358 | if (SKIPLIST_DEBUG) |
| 359 | VG_(printf)("inserting node %p, key %s, height %d\n", |
| 360 | data, (*l->strkey)(key_of_data(l, data)), node_of_data(l, data)->level); |
| 361 | |
| 362 | validate_skiplist(l, "SkipList_Insert before"); |
| 363 | |
| 364 | if (l->head == NULL) { |
fitzhardinge | c9730c4 | 2004-06-30 01:27:06 +0000 | [diff] [blame] | 365 | Int size = sizeof(SkipNode) + sizeof(SkipNode *) * SK_MAXHEIGHT; |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 366 | |
| 367 | if (l->arena == -1) |
nethercote | 60f5b82 | 2004-01-26 17:24:42 +0000 | [diff] [blame] | 368 | *(Short *)&l->arena = VG_AR_TOOL; |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 369 | |
| 370 | l->head = VG_(arena_malloc)(l->arena, size); |
| 371 | VG_(memset)(l->head, 0, size); |
| 372 | |
| 373 | l->head->magic = SKIPLIST_HEAD_MAGIC; |
| 374 | l->head->level = 0; |
| 375 | } |
| 376 | |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 377 | n = node_of_data(l, data); |
| 378 | |
fitzhardinge | 24503fc | 2004-07-27 21:49:23 +0000 | [diff] [blame] | 379 | /* update size of head's next vector to fit this new node */ |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 380 | vg_assert(l->head != NULL); |
| 381 | if (l->head->level < n->level) { |
| 382 | for(i = l->head->level+1; i <= n->level; i++) |
fitzhardinge | 24503fc | 2004-07-27 21:49:23 +0000 | [diff] [blame] | 383 | l->head->next[i] = NULL; |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 384 | l->head->level = n->level; |
| 385 | } |
| 386 | |
fitzhardinge | 24503fc | 2004-07-27 21:49:23 +0000 | [diff] [blame] | 387 | /* Look for the node, but we're mostly interested in setting |
| 388 | "update", which is the set of previous nodes with next pointers |
| 389 | we need to fix up. */ |
| 390 | nn = SkipList__Find(l, k, update); |
| 391 | |
| 392 | /* check the new entry is unique */ |
| 393 | vg_assert(nn == NULL || (l->cmp)(key_of_node(l, nn), k) != 0); |
| 394 | |
| 395 | /* update the previous node's next pointers */ |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 396 | for(i = 0; i <= n->level; i++) { |
| 397 | n->next[i] = update[i]->next[i]; |
| 398 | update[i]->next[i] = n; |
| 399 | } |
| 400 | |
| 401 | validate_skiplist(l, "SkipList_Insert after"); |
| 402 | } |
| 403 | |
| 404 | void *VG_(SkipList_Remove)(SkipList *l, void *k) |
| 405 | { |
| 406 | SkipNode *update[SK_MAXHEIGHT]; |
| 407 | SkipNode *n; |
| 408 | Int i; |
| 409 | |
| 410 | validate_skiplist(l, "SkipList_Remove before"); |
| 411 | |
| 412 | n = SkipList__Find(l, k, update); |
| 413 | if (n == NULL) |
| 414 | return NULL; |
| 415 | |
| 416 | vg_assert((l->cmp)(k, key_of_node(l, n)) == 0); |
| 417 | |
| 418 | for(i = 0; i <= n->level; i++) { |
| 419 | update[i]->next[i] = n->next[i]; |
| 420 | n->next[i] = NULL; |
| 421 | } |
| 422 | |
| 423 | validate_skiplist(l, "SkipList_Remove after"); |
| 424 | |
| 425 | return data_of_node(l, n); |
| 426 | } |