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 | |
nethercote | f1e5e15 | 2004-09-01 23:58:16 +0000 | [diff] [blame] | 89 | #include "core.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 | |
| 96 | #include <stdlib.h> |
| 97 | |
| 98 | #define SKIPLIST_DEBUG 0 |
| 99 | |
| 100 | #define SK_MAXHEIGHT 20 /* 2^20 elements */ |
| 101 | #define SKIPLIST_MAGIC 0x5b1ff872 |
| 102 | #define SKIPLIST_HEAD_MAGIC (~SKIPLIST_MAGIC) |
| 103 | |
| 104 | |
| 105 | #if SKIPLIST_DEBUG |
| 106 | #define inline |
| 107 | #endif /* SKIPLIST_DEBUG */ |
| 108 | |
| 109 | struct _SkipNode { |
| 110 | UInt magic; |
| 111 | UShort level; /* level is the max level (level == 0 means 1 next pointer) */ |
| 112 | SkipNode *next[0]; |
| 113 | }; |
| 114 | |
| 115 | |
fitzhardinge | c9730c4 | 2004-06-30 01:27:06 +0000 | [diff] [blame] | 116 | /* |
| 117 | Compute the height of a new node. 1/2 will be 1, 1/4 2, 1/8 3, |
| 118 | etc. |
| 119 | */ |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 120 | static inline Int get_height(void) |
| 121 | { |
| 122 | UInt ret = 0; |
| 123 | |
thughes | aecb291 | 2004-10-28 08:09:05 +0000 | [diff] [blame] | 124 | while((ret < SK_MAXHEIGHT - 1) && (random() & 1)) |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 125 | ret++; |
| 126 | |
| 127 | return ret; |
| 128 | } |
| 129 | |
fitzhardinge | c9730c4 | 2004-06-30 01:27:06 +0000 | [diff] [blame] | 130 | /* |
| 131 | Given a pointer to the node's data, return a pointer to the key. |
| 132 | */ |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 133 | static inline void *key_of_data(const SkipList *l, void *d) |
| 134 | { |
| 135 | return (void *)((Char *)d + l->keyoff); |
| 136 | } |
| 137 | |
fitzhardinge | c9730c4 | 2004-06-30 01:27:06 +0000 | [diff] [blame] | 138 | /* |
| 139 | Given a pointer to the node's data, return the pointer to the SkipNode |
| 140 | structure. If the node has a bad magic number, it will die with an |
| 141 | assertion failure. |
| 142 | */ |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 143 | static inline SkipNode *node_of_data(const SkipList *l, const void *d) |
| 144 | { |
| 145 | SkipNode *n = (SkipNode *)((Char *)d + l->size); |
| 146 | |
| 147 | if (SKIPLIST_DEBUG && n->magic != SKIPLIST_MAGIC) |
| 148 | VG_(printf)("bad magic on node %p = %x (not %x)\n", |
| 149 | n, n->magic, SKIPLIST_MAGIC); |
| 150 | |
| 151 | vg_assert(n->magic == SKIPLIST_MAGIC); |
| 152 | |
| 153 | return n; |
| 154 | } |
| 155 | |
fitzhardinge | c9730c4 | 2004-06-30 01:27:06 +0000 | [diff] [blame] | 156 | /* |
| 157 | Given a SkipNode structure, return the pointer to the node's data. |
| 158 | */ |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 159 | static inline void *data_of_node(const SkipList *l, const SkipNode *n) |
| 160 | { |
| 161 | if (SKIPLIST_DEBUG && n->magic != SKIPLIST_MAGIC) |
| 162 | VG_(printf)("bad magic on node %p = %x (not %x)\n", |
| 163 | n, n->magic, SKIPLIST_MAGIC); |
| 164 | |
| 165 | vg_assert(n->magic == SKIPLIST_MAGIC); |
| 166 | return (void *)((Char *)n - l->size); |
| 167 | } |
| 168 | |
fitzhardinge | c9730c4 | 2004-06-30 01:27:06 +0000 | [diff] [blame] | 169 | /* |
| 170 | Given a SkipNode structure, return the pointer to the node's key. |
| 171 | */ |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 172 | static inline void *key_of_node(const SkipList *l, const SkipNode *n) |
| 173 | { |
| 174 | return key_of_data(l, data_of_node(l, n)); |
| 175 | } |
| 176 | |
| 177 | static inline void validate_skiplist(const SkipList *l, const Char *where) |
| 178 | { |
| 179 | #if SKIPLIST_DEBUG |
| 180 | const SkipNode *prev[SK_MAXHEIGHT]; |
| 181 | Int i; |
| 182 | const SkipNode *n, *next; |
| 183 | |
| 184 | VG_(printf)("---------------- %s ----------------\n", where); |
| 185 | |
| 186 | if (l->head == NULL) |
| 187 | return; |
| 188 | |
| 189 | for(i = 0; i <= l->head->level; i++) { |
| 190 | VG_(printf)("l->head->next[%d]=%p\n", |
| 191 | i, l->head->next[i]); |
| 192 | prev[i] = l->head->next[i]; |
| 193 | } |
| 194 | |
| 195 | for(n = l->head->next[0]; n != NULL; n = next) { |
| 196 | next = n->next[0]; |
| 197 | |
| 198 | VG_(printf)("n=%p next=%p, n->level=%d k=%s\n", |
| 199 | n, next, n->level, (*l->strkey)(key_of_node(l, n))); |
| 200 | for(i = 0; i <= n->level; i++) { |
| 201 | VG_(printf)(" n->next[%d] = %p\n", |
| 202 | i, n->next[i]); |
| 203 | VG_(printf)(" prev[%d] = %p\n", |
| 204 | i, prev[i]); |
| 205 | } |
| 206 | |
| 207 | vg_assert(l->head->level >= n->level); |
| 208 | |
| 209 | for(i = 0; i <= n->level; i++) |
| 210 | vg_assert(prev[i] == n); |
| 211 | |
| 212 | for(i = 0; i <= n->level; i++) |
| 213 | prev[i] = n->next[i]; |
| 214 | |
| 215 | vg_assert(next == NULL || (l->cmp)(key_of_node(l, n), key_of_node(l, next)) < 0); |
| 216 | } |
| 217 | #endif /* SKIPLIST_DEBUG */ |
| 218 | } |
| 219 | |
| 220 | void *VG_(SkipNode_Alloc)(const SkipList *l) |
| 221 | { |
fitzhardinge | 24503fc | 2004-07-27 21:49:23 +0000 | [diff] [blame] | 222 | UInt size; |
| 223 | Int h; |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 224 | SkipNode *n; |
| 225 | Char *ret; |
| 226 | |
fitzhardinge | 24503fc | 2004-07-27 21:49:23 +0000 | [diff] [blame] | 227 | h = get_height(); |
| 228 | |
| 229 | size = l->size; |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 230 | size += sizeof(SkipNode) + (h+1)*sizeof(SkipNode *); |
| 231 | |
| 232 | if (l->arena == -1) |
nethercote | 60f5b82 | 2004-01-26 17:24:42 +0000 | [diff] [blame] | 233 | *(Short *)&l->arena = VG_AR_TOOL; |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 234 | |
| 235 | ret = VG_(arena_malloc)(l->arena, size); |
| 236 | |
| 237 | if (ret == NULL) |
| 238 | return NULL; |
| 239 | |
| 240 | n = (SkipNode *)(ret + l->size); |
| 241 | n->level = h; |
| 242 | n->magic = SKIPLIST_MAGIC; |
| 243 | |
fitzhardinge | 24503fc | 2004-07-27 21:49:23 +0000 | [diff] [blame] | 244 | VG_(memset)(n->next, 0, sizeof(n->next[0]) * (h+1)); |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 245 | |
| 246 | return ret; |
| 247 | } |
| 248 | |
| 249 | void VG_(SkipNode_Free)(const SkipList *l, void *p) |
| 250 | { |
| 251 | if (SKIPLIST_DEBUG) { |
| 252 | SkipNode *n = node_of_data(l, p); |
| 253 | |
| 254 | VG_(printf)("SkipNode_Free: freeing %p (node %p)\n", |
| 255 | p, n); |
| 256 | n->magic = 0x55ffaabb; |
| 257 | } |
| 258 | VG_(arena_free)(l->arena, p); |
| 259 | } |
| 260 | |
| 261 | void *VG_(SkipNode_First)(const SkipList *l) |
| 262 | { |
| 263 | SkipNode *n = l->head ? l->head->next[0] : NULL; |
| 264 | |
| 265 | if (n == NULL) |
| 266 | return NULL; |
| 267 | else |
| 268 | return data_of_node(l, n); |
| 269 | } |
| 270 | |
| 271 | void *VG_(SkipNode_Next)(const SkipList *l, void *data) |
| 272 | { |
| 273 | SkipNode *n = node_of_data(l, data); |
| 274 | |
| 275 | n = n->next[0]; |
| 276 | |
| 277 | if (n == NULL) |
| 278 | return NULL; |
| 279 | |
| 280 | return data_of_node(l, n); |
| 281 | } |
| 282 | |
| 283 | |
| 284 | |
| 285 | static Int cmp(const SkipList *l, SkipNode *n, void *k2) |
| 286 | { |
| 287 | void *k1 = key_of_node(l, n); |
| 288 | |
| 289 | if (k1 == k2) |
| 290 | return 0; |
| 291 | |
| 292 | if (l->head == n) |
| 293 | return -1; |
| 294 | |
| 295 | return (l->cmp)(k1, k2); |
| 296 | } |
| 297 | |
| 298 | /* Search the list for k; it either returns the k if it exists, or the |
| 299 | one before if not. */ |
| 300 | static SkipNode *SkipList__Find(const SkipList *l, void *k, SkipNode **prevs) |
| 301 | { |
| 302 | SkipNode *n; |
| 303 | Int lvl; |
| 304 | |
| 305 | if (SKIPLIST_DEBUG) |
| 306 | VG_(printf)("SkipList__Find: finding %s\n", (*l->strkey)(k)); |
| 307 | |
| 308 | validate_skiplist(l, "SkipList__Find"); |
| 309 | |
| 310 | if (l->head == NULL) |
| 311 | return NULL; |
| 312 | |
| 313 | for(lvl = l->head->level, n = l->head; lvl >= 0; lvl--) { |
| 314 | while(n->next[lvl] != NULL && cmp(l, n->next[lvl], k) < 0) { |
| 315 | if (SKIPLIST_DEBUG) |
| 316 | VG_(printf)("SkipList__Find: n=%p n->next[%d]=%p\n", |
| 317 | n, lvl, n->next[lvl]); |
| 318 | n = n->next[lvl]; |
| 319 | } |
| 320 | if (prevs) |
| 321 | prevs[lvl] = n; |
| 322 | } |
| 323 | |
| 324 | /* XXX Is there a cleaner way of getting this? |
| 325 | |
| 326 | If we get an exact match, return it. |
| 327 | If we get the head, return NULL. |
| 328 | Otherwise return the one before where the hit would be. |
| 329 | */ |
| 330 | if (n->next[0] != NULL && cmp(l, n->next[0], k) == 0) |
| 331 | n = n->next[0]; |
| 332 | if (n == l->head) |
| 333 | n = NULL; |
| 334 | |
| 335 | if (SKIPLIST_DEBUG) { |
| 336 | |
| 337 | VG_(printf)("SkipList__Find returning node %p\n", n); |
| 338 | |
| 339 | if (n == NULL) { |
| 340 | SkipNode *nn; |
| 341 | |
| 342 | for(nn = l->head->next[0]; nn != NULL; nn = nn->next[0]) |
| 343 | vg_assert(cmp(l, nn, k) != 0); |
| 344 | } else |
| 345 | vg_assert(cmp(l, n, k) <= 0); |
| 346 | } |
| 347 | |
| 348 | return n; |
| 349 | } |
| 350 | |
sewardj | b5f6f51 | 2005-03-10 23:59:00 +0000 | [diff] [blame] | 351 | /* Return list element which is <= k, or NULL if there is none. */ |
| 352 | void *VG_(SkipList_Find_Before)(const SkipList *l, void *k) |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 353 | { |
| 354 | SkipNode *n = SkipList__Find(l, k, NULL); |
| 355 | |
| 356 | if (n != NULL) |
| 357 | return data_of_node(l, n); |
| 358 | return NULL; |
| 359 | } |
| 360 | |
sewardj | b5f6f51 | 2005-03-10 23:59:00 +0000 | [diff] [blame] | 361 | /* Return the list element which == k, or NULL if none */ |
| 362 | void *VG_(SkipList_Find_Exact)(const SkipList *l, void *k) |
| 363 | { |
| 364 | SkipNode *n = SkipList__Find(l, k, NULL); |
| 365 | |
| 366 | if (n != NULL && (l->cmp)(key_of_node(l, n), k) == 0) |
| 367 | return data_of_node(l, n); |
| 368 | return NULL; |
| 369 | } |
| 370 | |
| 371 | /* Return the list element which is >= k, or NULL if none */ |
| 372 | void *VG_(SkipList_Find_After)(const SkipList *l, void *k) |
| 373 | { |
| 374 | SkipNode *n = SkipList__Find(l, k, NULL); |
| 375 | |
| 376 | if (n != NULL && (l->cmp)(key_of_node(l, n), k) < 0) |
| 377 | n = n->next[0]; |
| 378 | |
| 379 | if (n != NULL) |
| 380 | return data_of_node(l, n); |
| 381 | |
| 382 | return NULL; |
| 383 | } |
| 384 | |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 385 | void VG_(SkipList_Insert)(SkipList *l, void *data) |
| 386 | { |
| 387 | SkipNode *update[SK_MAXHEIGHT]; |
fitzhardinge | 24503fc | 2004-07-27 21:49:23 +0000 | [diff] [blame] | 388 | SkipNode *n, *nn; |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 389 | void *k = key_of_data(l, data); |
| 390 | Int i; |
| 391 | |
| 392 | if (SKIPLIST_DEBUG) |
| 393 | VG_(printf)("inserting node %p, key %s, height %d\n", |
| 394 | data, (*l->strkey)(key_of_data(l, data)), node_of_data(l, data)->level); |
| 395 | |
| 396 | validate_skiplist(l, "SkipList_Insert before"); |
| 397 | |
| 398 | if (l->head == NULL) { |
fitzhardinge | c9730c4 | 2004-06-30 01:27:06 +0000 | [diff] [blame] | 399 | Int size = sizeof(SkipNode) + sizeof(SkipNode *) * SK_MAXHEIGHT; |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 400 | |
| 401 | if (l->arena == -1) |
nethercote | 60f5b82 | 2004-01-26 17:24:42 +0000 | [diff] [blame] | 402 | *(Short *)&l->arena = VG_AR_TOOL; |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 403 | |
| 404 | l->head = VG_(arena_malloc)(l->arena, size); |
| 405 | VG_(memset)(l->head, 0, size); |
| 406 | |
| 407 | l->head->magic = SKIPLIST_HEAD_MAGIC; |
| 408 | l->head->level = 0; |
| 409 | } |
| 410 | |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 411 | n = node_of_data(l, data); |
| 412 | |
fitzhardinge | 24503fc | 2004-07-27 21:49:23 +0000 | [diff] [blame] | 413 | /* update size of head's next vector to fit this new node */ |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 414 | vg_assert(l->head != NULL); |
| 415 | if (l->head->level < n->level) { |
| 416 | for(i = l->head->level+1; i <= n->level; i++) |
fitzhardinge | 24503fc | 2004-07-27 21:49:23 +0000 | [diff] [blame] | 417 | l->head->next[i] = NULL; |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 418 | l->head->level = n->level; |
| 419 | } |
| 420 | |
fitzhardinge | 24503fc | 2004-07-27 21:49:23 +0000 | [diff] [blame] | 421 | /* Look for the node, but we're mostly interested in setting |
| 422 | "update", which is the set of previous nodes with next pointers |
| 423 | we need to fix up. */ |
| 424 | nn = SkipList__Find(l, k, update); |
| 425 | |
| 426 | /* check the new entry is unique */ |
| 427 | vg_assert(nn == NULL || (l->cmp)(key_of_node(l, nn), k) != 0); |
| 428 | |
| 429 | /* update the previous node's next pointers */ |
fitzhardinge | 7e343cd | 2003-12-16 02:14:00 +0000 | [diff] [blame] | 430 | for(i = 0; i <= n->level; i++) { |
| 431 | n->next[i] = update[i]->next[i]; |
| 432 | update[i]->next[i] = n; |
| 433 | } |
| 434 | |
| 435 | validate_skiplist(l, "SkipList_Insert after"); |
| 436 | } |
| 437 | |
| 438 | void *VG_(SkipList_Remove)(SkipList *l, void *k) |
| 439 | { |
| 440 | SkipNode *update[SK_MAXHEIGHT]; |
| 441 | SkipNode *n; |
| 442 | Int i; |
| 443 | |
| 444 | validate_skiplist(l, "SkipList_Remove before"); |
| 445 | |
| 446 | n = SkipList__Find(l, k, update); |
| 447 | if (n == NULL) |
| 448 | return NULL; |
| 449 | |
| 450 | vg_assert((l->cmp)(k, key_of_node(l, n)) == 0); |
| 451 | |
| 452 | for(i = 0; i <= n->level; i++) { |
| 453 | update[i]->next[i] = n->next[i]; |
| 454 | n->next[i] = NULL; |
| 455 | } |
| 456 | |
| 457 | validate_skiplist(l, "SkipList_Remove after"); |
| 458 | |
| 459 | return data_of_node(l, n); |
| 460 | } |
sewardj | b5f6f51 | 2005-03-10 23:59:00 +0000 | [diff] [blame] | 461 | |
sewardj | b5f6f51 | 2005-03-10 23:59:00 +0000 | [diff] [blame] | 462 | |
| 463 | /* -------------------------------------------------- |
| 464 | Comparison functions |
| 465 | -------------------------------------------------- */ |
| 466 | Int VG_(cmp_Int)(const void *v1, const void *v2) |
| 467 | { |
| 468 | Int a = *(const Int *)v1; |
| 469 | Int b = *(const Int *)v2; |
| 470 | |
| 471 | if (a < b) |
| 472 | return -1; |
| 473 | if (a == b) |
| 474 | return 0; |
| 475 | return 1; |
| 476 | } |
| 477 | |
| 478 | Int VG_(cmp_UInt)(const void *v1, const void *v2) |
| 479 | { |
| 480 | UInt a = *(const UInt *)v1; |
| 481 | UInt b = *(const UInt *)v2; |
| 482 | |
| 483 | if (a < b) |
| 484 | return -1; |
| 485 | if (a == b) |
| 486 | return 0; |
| 487 | return 1; |
| 488 | } |
| 489 | |
| 490 | Int VG_(cmp_Addr)(const void *v1, const void *v2) |
| 491 | { |
| 492 | Addr a = *(const Addr *)v1; |
| 493 | Addr b = *(const Addr *)v2; |
| 494 | |
| 495 | if (a < b) |
| 496 | return -1; |
| 497 | if (a == b) |
| 498 | return 0; |
| 499 | return 1; |
| 500 | } |
| 501 | |
| 502 | Int VG_(cmp_string)(const void *v1, const void *v2) |
| 503 | { |
| 504 | const Char *a = *(const Char **)v1; |
| 505 | const Char *b = *(const Char **)v2; |
| 506 | |
| 507 | return VG_(strcmp)(a, b); |
| 508 | } |
| 509 | |
njn | 641d5cc | 2005-05-12 04:37:27 +0000 | [diff] [blame] | 510 | /*--------------------------------------------------------------------*/ |
| 511 | /*--- end ---*/ |
| 512 | /*--------------------------------------------------------------------*/ |
sewardj | b5f6f51 | 2005-03-10 23:59:00 +0000 | [diff] [blame] | 513 | |