Lines Matching refs:sl
46 void 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;
67 void 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);
74 void skiplist_set_compare(Skiplist *sl,
77 if(sl->compare && sl->comparek) {
78 skiplist_add_index(sl, comp, compk);
80 sl->compare = comp;
81 sl->comparek = compk;
85 void skiplist_add_index(Skiplist *sl,
92 fprintf(stderr, "Adding index to %p\n", sl);
94 skiplist_find(sl->index, (void *)comp, &m);
100 m = skiplist_insert(sl->index, ni);
102 for(m=skiplist_getlist(sl); m; skiplist_next(sl, &m)) {
116 struct skiplistnode *skiplist_getlist(Skiplist *sl) {
117 if(!sl->bottom) return NULL;
118 return sl->bottom->next;
121 void *skiplist_find(Skiplist *sl,
126 if(!sl->compare) return 0;
128 ret = skiplist_find_compare(sl, data, iter, sl->compare);
130 ret = skiplist_find_compare(sl, data, &aiter, sl->compare);
138 Skiplist *sl;
140 sl = sli;
144 sl= (Skiplist *) m->data;
146 skiplisti_find_compare(sl, data, iter, sl->comparek);
149 int skiplisti_find_compare(Skiplist *sl,
155 m = sl->top;
179 void *skiplist_next(Skiplist *sl, struct skiplistnode **iter) {
184 void *skiplist_previous(Skiplist *sl, struct skiplistnode **iter) {
189 struct skiplistnode *skiplist_insert(Skiplist *sl,
191 if(!sl->compare) return 0;
192 return skiplist_insert_compare(sl, data, sl->compare);
195 struct skiplistnode *skiplist_insert_compare(Skiplist *sl,
201 skiplist_print_struct(sl, "BI: ");
203 if(!sl->top) {
204 sl->height = 1;
205 sl->topend = sl->bottomend = sl->top = sl->bottom =
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;
217 if(sl->preheight) {
218 while(nh < sl->preheight && get_b_rand()) nh++;
220 while(nh <= sl->height && get_b_rand()) nh++;
224 for(;sl->height<nh;sl->height++) {
225 sl->top->up =
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;
235 ch = sl->height;
238 m = sl->top;
272 tmp->sl = sl;
279 if(sl->index != NULL) {
283 for(p = skiplist_getlist(sl->index); p; skiplist_next(sl->index, &p)) {
294 sl->size++;
297 skiplist_print_struct(sl, "AI: ");
301 struct skiplistnode *skiplist_append(Skiplist *sl, void *data) {
304 if(sl->bottomend != sl->bottom) {
305 compared=sl->compare(data, sl->bottomend->prev->data);
309 if(sl->preheight) {
310 while(nh < sl->preheight && get_b_rand()) nh++;
312 while(nh <= sl->height && get_b_rand()) nh++;
316 lastnode = sl->bottomend;
319 if(!lastnode) return skiplist_insert(sl, data);
321 for(;sl->height<nh;sl->height++) {
322 sl->top->up =
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;
332 ch = sl->height;
342 if(lastnode == sl->bottom)
343 sl->bottom = anode;
344 else if (lastnode == sl->top)
345 sl->top = anode;
351 sl->size++;
352 return sl->bottomend;
413 int skiplist_remove(Skiplist *sl,
415 if(!sl->compare) return 0;
416 return skiplist_remove_compare(sl, data, myfree, sl->comparek);
418 void skiplist_print_struct(Skiplist *sl, char *prefix) {
420 fprintf(stderr, "Skiplist Structure (height: %d)\n", sl->height);
421 p = sl->bottom;
433 int skiplisti_remove(Skiplist *sl, struct skiplistnode *m, FreeFunc myfree) {
436 if(m->nextindex) skiplisti_remove(m->nextindex->sl, m->nextindex, NULL);
437 else sl->size--;
439 skiplist_print_struct(sl, "BR:");
451 while(sl->top && sl->top->next == NULL) {
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 */
457 sl->height--;
459 if(!sl->top) sl->bottom = NULL;
460 assert(sl->height>=0);
462 skiplist_print_struct(sl, "AR: ");
464 return sl->height;
470 Skiplist *sl;
472 sl = sli;
476 sl= (Skiplist *) m->data;
478 skiplisti_find_compare(sl, data, &m, comp);
481 return skiplisti_remove(sl, m, myfree);
483 void skiplist_remove_all(Skiplist *sl, FreeFunc myfree) {
488 m=sl->bottom;
499 sl->top = sl->bottom = NULL;
500 sl->height = 0;
501 sl->size = 0;