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