1/* ====================================================================== 2 * Copyright (c) 2000,2006 Theo Schlossnagle 3 * All rights reserved. 4 * The following code was written by Theo Schlossnagle for use in the 5 * Backhand project at The Center for Networking and Distributed Systems 6 * at The Johns Hopkins University. 7 * 8 * This is a skiplist implementation to be used for abstract structures 9 * and is release under the LGPL license version 2.1 or later. A copy 10 * of this license can be found file LGPL. 11 * 12 * Alternatively, this file may be licensed under the new BSD license. 13 * A copy of this license can be found file BSD. 14 * 15 * ====================================================================== 16*/ 17 18extern "C" 19{ 20#include <stdio.h> 21#include <stdlib.h> 22#include <assert.h> 23 24#include "skiplist.h" 25} 26 27#ifdef USE_DMALLOC 28# include <dmalloc.h> 29#endif 30 31#ifndef MIN 32#define MIN(a,b) ((a<b)?(a):(b)) 33#endif 34 35#define MALLOC(type, ptr) do { \ 36 void *tmptr = malloc(sizeof(struct type)); \ 37 if (tmptr == NULL){ \ 38 fprintf(stderr, \ 39 "In file %s on line %d: malloc failed to allocate memory, exiting...", \ 40 __FILE__, __LINE__); \ 41 assert(0); \ 42 } \ 43 ptr = (struct type*)tmptr; \ 44} while (0) 45 46#define MALLOC_N(type, num, ptr) do { \ 47 void *tmptr = NULL; \ 48 assert(num >= 0); \ 49 tmptr = malloc(sizeof(struct type) * num); \ 50 if (tmptr == NULL){ \ 51 fprintf(stderr, \ 52 "In file %s on line %d: malloc failed to allocate memory, exiting...", \ 53 __FILE__, __LINE__); \ 54 assert(0); \ 55 } \ 56 ptr = (struct type*)tmptr; \ 57} while (0) 58 59static int get_b_rand(void) { 60 static int ph=32; /* More bits than we will ever use */ 61 static unsigned long randseq; 62 if(ph > 31) { /* Num bits in return of lrand48() */ 63 ph=0; 64 randseq = lrand48(); 65 } 66 ph++; 67 return ((randseq & (1 << (ph-1))) >> (ph-1)); 68} 69 70void skiplisti_init(Skiplist *sl) { 71 sl->compare = (SkiplistComparator)NULL; 72 sl->comparek = (SkiplistComparator)NULL; 73 sl->height=0; 74 sl->preheight=0; 75 sl->size=0; 76 sl->top = NULL; 77 sl->bottom = NULL; 78 sl->index = NULL; 79} 80 81static int indexing_comp(void *a, void *b) { 82 assert(a); 83 assert(b); 84 return (void *)(((Skiplist *)a)->compare)>(void *)(((Skiplist *)b)->compare); 85} 86static int indexing_compk(void *a, void *b) { 87 assert(b); 88 return a>(void *)(((Skiplist *)b)->compare); 89} 90 91void skiplist_init(Skiplist *sl) { 92 skiplisti_init(sl); 93 MALLOC(_iskiplist, sl->index); 94 skiplisti_init(sl->index); 95 skiplist_set_compare(sl->index, indexing_comp, indexing_compk); 96} 97 98void skiplist_set_compare(Skiplist *sl, 99 SkiplistComparator comp, 100 SkiplistComparator compk) { 101 if(sl->compare && sl->comparek) { 102 skiplist_add_index(sl, comp, compk); 103 } else { 104 sl->compare = comp; 105 sl->comparek = compk; 106 } 107} 108 109void skiplist_add_index(Skiplist *sl, 110 SkiplistComparator comp, 111 SkiplistComparator compk) { 112 struct skiplistnode *m; 113 Skiplist *ni; 114 int icount=0; 115#ifdef SLDEBUG 116 fprintf(stderr, "Adding index to %p\n", sl); 117#endif 118 skiplist_find(sl->index, (void *)comp, &m); 119 if(m) return; /* Index already there! */ 120 MALLOC(_iskiplist, ni); 121 skiplisti_init(ni); 122 skiplist_set_compare(ni, comp, compk); 123 /* Build the new index... This can be expensive! */ 124 m = skiplist_insert(sl->index, ni); 125 while(m->prev) m=m->prev, icount++; 126 for(m=skiplist_getlist(sl); m; skiplist_next(sl, &m)) { 127 int j=icount-1; 128 struct skiplistnode *nsln; 129 nsln = skiplist_insert(ni, m->data); 130 /* skip from main index down list */ 131 while(j>0) m=m->nextindex, j--; 132 /* insert this node in the indexlist after m */ 133 nsln->nextindex = m->nextindex; 134 if(m->nextindex) m->nextindex->previndex = nsln; 135 nsln->previndex = m; 136 m->nextindex = nsln; 137 } 138} 139 140struct skiplistnode *skiplist_getlist(Skiplist *sl) { 141 if(!sl->bottom) return NULL; 142 return sl->bottom->next; 143} 144 145void *skiplist_find(Skiplist *sl, 146 void *data, 147 struct skiplistnode **iter) { 148 void *ret; 149 struct skiplistnode *aiter; 150 if(!sl->compare) return 0; 151 if(iter) 152 ret = skiplist_find_compare(sl, data, iter, sl->compare); 153 else 154 ret = skiplist_find_compare(sl, data, &aiter, sl->compare); 155 return ret; 156} 157void *skiplist_find_compare(Skiplist *sli, 158 void *data, 159 struct skiplistnode **iter, 160 SkiplistComparator comp) { 161 struct skiplistnode *m = NULL; 162 Skiplist *sl; 163 if(comp==sli->compare || !sli->index) { 164 sl = sli; 165 } else { 166 skiplist_find(sli->index, (void *)comp, &m); 167 assert(m); 168 sl= (Skiplist *) m->data; 169 } 170 skiplisti_find_compare(sl, data, iter, sl->comparek); 171 return (*iter)?((*iter)->data):(*iter); 172} 173int skiplisti_find_compare(Skiplist *sl, 174 void *data, 175 struct skiplistnode **ret, 176 SkiplistComparator comp) { 177 struct skiplistnode *m = NULL; 178 int count=0; 179 m = sl->top; 180 while(m) { 181 int compared; 182 if(m->next) compared=comp(data, m->next->data); 183 if(compared == 0) { 184#ifdef SL_DEBUG 185 printf("Looking -- found in %d steps\n", count); 186#endif 187 m=m->next; 188 while(m->down) m=m->down; 189 *ret = m; 190 return count; 191 } 192 if((m->next == NULL) || (compared<0)) 193 m = m->down, count++; 194 else 195 m = m->next, count++; 196 } 197#ifdef SL_DEBUG 198 printf("Looking -- not found in %d steps\n", count); 199#endif 200 *ret = NULL; 201 return count; 202} 203void *skiplist_next(Skiplist *sl, struct skiplistnode **iter) { 204 if(!*iter) return NULL; 205 *iter = (*iter)->next; 206 return (*iter)?((*iter)->data):NULL; 207} 208void *skiplist_previous(Skiplist *sl, struct skiplistnode **iter) { 209 if(!*iter) return NULL; 210 *iter = (*iter)->prev; 211 return (*iter)?((*iter)->data):NULL; 212} 213struct skiplistnode *skiplist_insert(Skiplist *sl, 214 void *data) { 215 if(!sl->compare) return 0; 216 return skiplist_insert_compare(sl, data, sl->compare); 217} 218 219struct skiplistnode *skiplist_insert_compare(Skiplist *sl, 220 void *data, 221 SkiplistComparator comp) { 222 struct skiplistnode *m, *p, *tmp, *ret, **stack; 223 int nh=1, ch, stacki; 224#ifdef SLDEBUG 225 skiplist_print_struct(sl, "BI: "); 226#endif 227 if(!sl->top) { 228 sl->height = 1; 229 MALLOC(skiplistnode, sl->bottom); 230 sl->topend = sl->bottomend = sl->top = sl->bottom; 231 assert(sl->top); 232 sl->top->next = (struct skiplistnode *) NULL; 233 sl->top->data = (struct skiplistnode *) NULL; 234 sl->top->prev =(struct skiplistnode *) NULL; 235 sl->top->up = (struct skiplistnode *) NULL; 236 sl->top->down = (struct skiplistnode *) NULL; 237 sl->top->nextindex= (struct skiplistnode *) NULL; 238 sl->top->previndex = (struct skiplistnode *) NULL; 239 sl->top->sl = sl; 240 } 241 if(sl->preheight) { 242 while(nh < sl->preheight && get_b_rand()) nh++; 243 } else { 244 while(nh <= sl->height && get_b_rand()) nh++; 245 } 246 /* Now we have the new height at which we wish to insert our new node */ 247 /* Let us make sure that our tree is a least that tall (grow if necessary)*/ 248 for(;sl->height<nh;sl->height++) { 249 MALLOC(skiplistnode, sl->top->up); 250 sl->top->up->down = sl->top; 251 sl->top = sl->topend = sl->top->up; 252 sl->top->prev = sl->top->next = sl->top->nextindex = 253 sl->top->previndex = sl->top->up = NULL; 254 sl->top->data = NULL; 255 sl->top->sl = sl; 256 } 257 ch = sl->height; 258 /* Find the node (or node after which we would insert) */ 259 /* Keep a stack to pop back through for insertion */ 260 m = sl->top; 261 MALLOC_N(skiplistnode*, nh, stack); 262 stacki=0; 263 while(m) { 264 int compared=-1; 265 if(m->next) compared=comp(data, m->next->data); 266 if(compared == 0) { 267 free(stack); 268 return 0; 269 } 270 if((m->next == NULL) || (compared<0)) { 271 if(ch<=nh) { 272 /* push on stack */ 273 stack[stacki++] = m; 274 } 275 m = m->down; 276 ch--; 277 } else { 278 m = m->next; 279 } 280 } 281 /* Pop the stack and insert nodes */ 282 p = NULL; 283 for(;stacki>0;stacki--) { 284 m = stack[stacki-1]; 285 MALLOC(skiplistnode, tmp); 286 tmp->next = m->next; 287 if(m->next) m->next->prev=tmp; 288 tmp->prev = m; 289 tmp->up = NULL; 290 tmp->nextindex = tmp->previndex = NULL; 291 tmp->down = p; 292 if(p) p->up=tmp; 293 tmp->data = data; 294 tmp->sl = sl; 295 m->next = tmp; 296 /* This sets ret to the bottom-most node we are inserting */ 297 if(!p) ret=tmp; 298 p = tmp; 299 } 300 free(stack); 301 if(sl->index != NULL) { 302 /* this is a external insertion, we must insert into each index as well */ 303 struct skiplistnode *p, *ni, *li; 304 li=ret; 305 for(p = skiplist_getlist(sl->index); p; skiplist_next(sl->index, &p)) { 306 ni = skiplist_insert((Skiplist *)p->data, ret->data); 307 assert(ni); 308#ifdef SLDEBUG 309 fprintf(stderr, "Adding %p to index %p\n", ret->data, p->data); 310#endif 311 li->nextindex = ni; 312 ni->previndex = li; 313 li = ni; 314 } 315 } else { 316 sl->size++; 317 } 318#ifdef SLDEBUG 319 skiplist_print_struct(sl, "AI: "); 320#endif 321 return ret; 322} 323struct skiplistnode *skiplist_append(Skiplist *sl, void *data) { 324 int nh=1, ch, compared; 325 struct skiplistnode *lastnode, *nodeago; 326 if(sl->bottomend != sl->bottom) { 327 compared=sl->compare(data, sl->bottomend->prev->data); 328 /* If it doesn't belong at the end, then fail */ 329 if(compared<=0) return NULL; 330 } 331 if(sl->preheight) { 332 while(nh < sl->preheight && get_b_rand()) nh++; 333 } else { 334 while(nh <= sl->height && get_b_rand()) nh++; 335 } 336 /* Now we have the new height at which we wish to insert our new node */ 337 /* Let us make sure that our tree is a least that tall (grow if necessary)*/ 338 lastnode = sl->bottomend; 339 nodeago = NULL; 340 341 if(!lastnode) return skiplist_insert(sl, data); 342 343 for(;sl->height<nh;sl->height++) { 344 MALLOC(skiplistnode, sl->top->up); 345 assert(sl->top); 346 sl->top->up->down = sl->top; 347 sl->top = sl->top->up; 348 sl->top->prev = sl->top->next = sl->top->nextindex = 349 sl->top->previndex = NULL; 350 sl->top->data = NULL; 351 sl->top->sl = sl; 352 } 353 ch = sl->height; 354 while(nh) { 355 struct skiplistnode *anode; 356 MALLOC(skiplistnode, anode); 357 anode->next = lastnode; 358 anode->prev = lastnode->prev; 359 anode->up = NULL; 360 anode->down = nodeago; 361 if(lastnode->prev) { 362 if(lastnode == sl->bottom) 363 sl->bottom = anode; 364 else if (lastnode == sl->top) 365 sl->top = anode; 366 } 367 nodeago = anode; 368 lastnode = lastnode->up; 369 nh--; 370 } 371 sl->size++; 372 return sl->bottomend; 373} 374Skiplist *skiplist_concat(Skiplist *sl1, Skiplist *sl2) { 375 /* Check integrity! */ 376 int compared, eheight; 377 Skiplist temp; 378 struct skiplistnode *lbottom, *lbottomend, *b1, *e1, *b2, *e2; 379 if(sl1->bottomend == NULL || sl1->bottomend->prev == NULL) { 380 skiplist_remove_all(sl1, free); 381 temp = *sl1; 382 *sl1 = *sl2; 383 *sl2 = temp; 384 /* swap them so that sl2 can be freed normally upon return. */ 385 return sl1; 386 } 387 if(sl2->bottom == NULL || sl2->bottom->next == NULL) { 388 skiplist_remove_all(sl2, free); 389 return sl1; 390 } 391 compared = sl1->compare(sl1->bottomend->prev->data, sl2->bottom->data); 392 /* If it doesn't belong at the end, then fail */ 393 if(compared<=0) return NULL; 394 395 /* OK now append sl2 onto sl1 */ 396 lbottom = lbottomend = NULL; 397 eheight = MIN(sl1->height, sl2->height); 398 b1 = sl1->bottom; e1 = sl1->bottomend; 399 b2 = sl2->bottom; e2 = sl2->bottomend; 400 while(eheight) { 401 e1->prev->next = b2; 402 b2->prev = e1->prev->next; 403 e2->prev->next = e1; 404 e1->prev = e2->prev; 405 e2->prev = NULL; 406 b2 = e2; 407 b1->down = lbottom; 408 e1->down = lbottomend; 409 if(lbottom) lbottom->up = b1; 410 if(lbottomend) lbottomend->up = e1; 411 412 lbottom = b1; 413 lbottomend = e1; 414 } 415 /* Take the top of the longer one (if it is sl2) and make it sl1's */ 416 if(sl2->height > sl1->height) { 417 b1->up = b2->up; 418 e1->up = e2->up; 419 b1->up->down = b1; 420 e1->up->down = e1; 421 sl1->height = sl2->height; 422 sl1->top = sl2->top; 423 sl1->topend = sl2->topend; 424 } 425 426 /* move the top pointer to here if it isn't there already */ 427 sl2->top = sl2->topend = b2; 428 sl2->top->up = NULL; /* If it isn't already */ 429 sl1->size += sl2->size; 430 skiplist_remove_all(sl2, free); 431 return sl1; 432} 433int skiplist_remove(Skiplist *sl, 434 void *data, FreeFunc myfree) { 435 if(!sl->compare) return 0; 436 return skiplist_remove_compare(sl, data, myfree, sl->comparek); 437} 438void skiplist_print_struct(Skiplist *sl, char *prefix) { 439 struct skiplistnode *p, *q; 440 fprintf(stderr, "Skiplist Structure (height: %d)\n", sl->height); 441 p = sl->bottom; 442 while(p) { 443 q = p; 444 fprintf(stderr, "%s", prefix); 445 while(q) { 446 fprintf(stderr, "%p ", q->data); 447 q=q->up; 448 } 449 fprintf(stderr, "\n"); 450 p=p->next; 451 } 452} 453int skiplisti_remove(Skiplist *sl, struct skiplistnode *m, FreeFunc myfree) { 454 struct skiplistnode *p; 455 if(!m) return 0; 456 if(m->nextindex) skiplisti_remove(m->nextindex->sl, m->nextindex, NULL); 457 else sl->size--; 458#ifdef SLDEBUG 459 skiplist_print_struct(sl, "BR:"); 460#endif 461 while(m->up) m=m->up; 462 while(m) { 463 p=m; 464 p->prev->next = p->next; /* take me out of the list */ 465 if(p->next) p->next->prev = p->prev; /* take me out of the list */ 466 m=m->down; 467 /* This only frees the actual data in the bottom one */ 468 if(!m && myfree && p->data) myfree(p->data); 469 free(p); 470 } 471 while(sl->top && sl->top->next == NULL) { 472 /* While the row is empty and we are not on the bottom row */ 473 p = sl->top; 474 sl->top = sl->top->down; /* Move top down one */ 475 if(sl->top) sl->top->up = NULL; /* Make it think its the top */ 476 free(p); 477 sl->height--; 478 } 479 if(!sl->top) sl->bottom = NULL; 480 assert(sl->height>=0); 481#ifdef SLDEBUG 482 skiplist_print_struct(sl, "AR: "); 483#endif 484 return sl->height; 485} 486int skiplist_remove_compare(Skiplist *sli, 487 void *data, 488 FreeFunc myfree, SkiplistComparator comp) { 489 struct skiplistnode *m; 490 Skiplist *sl; 491 if(comp==sli->comparek || !sli->index) { 492 sl = sli; 493 } else { 494 skiplist_find(sli->index, (void *)comp, &m); 495 assert(m); 496 sl= (Skiplist *) m->data; 497 } 498 skiplisti_find_compare(sl, data, &m, comp); 499 if(!m) return 0; 500 while(m->previndex) m=m->previndex; 501 return skiplisti_remove(sl, m, myfree); 502} 503void skiplist_remove_all(Skiplist *sl, FreeFunc myfree) { 504 /* This must remove even the place holder nodes (bottom though top) 505 because we specify in the API that one can free the Skiplist after 506 making this call without memory leaks */ 507 struct skiplistnode *m, *p, *u; 508 m=sl->bottom; 509 while(m) { 510 p = m->next; 511 if(myfree && p->data) myfree(p->data); 512 while(m) { 513 u = m->up; 514 free(m); 515 m=u; 516 } 517 m = p; 518 } 519 sl->top = sl->bottom = NULL; 520 sl->height = 0; 521 sl->size = 0; 522} 523 524void *skiplist_pop(Skiplist * a, FreeFunc myfree) 525{ 526 struct skiplistnode *sln; 527 void *data = NULL; 528 sln = skiplist_getlist(a); 529 if (sln) { 530 data = sln->data; 531 skiplisti_remove(a, sln, myfree); 532 } 533 return data; 534} 535