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