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 18#ifndef _SKIPLIST_P_H 19#define _SKIPLIST_P_H 20 21/* This is a skiplist implementation to be used for abstract structures 22 within the Spread multicast and group communication toolkit 23 24 This portion written by -- Theo Schlossnagle <jesus@cnds.jhu.eu> 25*/ 26 27/* This is the function type that must be implemented per object type 28 that is used in a skiplist for comparisons to maintain order */ 29typedef int (*SkiplistComparator)(void *, void *); 30typedef void (*FreeFunc)(void *); 31 32struct skiplistnode; 33 34typedef struct _iskiplist { 35 SkiplistComparator compare; 36 SkiplistComparator comparek; 37 int height; 38 int preheight; 39 int size; 40 struct skiplistnode *top; 41 struct skiplistnode *bottom; 42 /* These two are needed for appending */ 43 struct skiplistnode *topend; 44 struct skiplistnode *bottomend; 45 struct _iskiplist *index; 46} Skiplist; 47 48struct skiplistnode { 49 void *data; 50 struct skiplistnode *next; 51 struct skiplistnode *prev; 52 struct skiplistnode *down; 53 struct skiplistnode *up; 54 struct skiplistnode *previndex; 55 struct skiplistnode *nextindex; 56 Skiplist *sl; 57}; 58 59 60void skiplist_init(Skiplist *sl); 61void skiplist_set_compare(Skiplist *sl, SkiplistComparator, 62 SkiplistComparator); 63void skiplist_add_index(Skiplist *sl, SkiplistComparator, 64 SkiplistComparator); 65struct skiplistnode *skiplist_getlist(Skiplist *sl); 66void *skiplist_find_compare(Skiplist *sl, void *data, struct skiplistnode **iter, 67 SkiplistComparator func); 68void *skiplist_find(Skiplist *sl, void *data, struct skiplistnode **iter); 69void *skiplist_next(Skiplist *sl, struct skiplistnode **); 70void *skiplist_previous(Skiplist *sl, struct skiplistnode **); 71 72struct skiplistnode *skiplist_insert_compare(Skiplist *sl, 73 void *data, SkiplistComparator comp); 74struct skiplistnode *skiplist_insert(Skiplist *sl, void *data); 75int skiplist_remove_compare(Skiplist *sl, void *data, 76 FreeFunc myfree, SkiplistComparator comp); 77int skiplist_remove(Skiplist *sl, void *data, FreeFunc myfree); 78int skiplisti_remove(Skiplist *sl, struct skiplistnode *m, FreeFunc myfree); 79void skiplist_remove_all(Skiplist *sl, FreeFunc myfree); 80 81int skiplisti_find_compare(Skiplist *sl, 82 void *data, 83 struct skiplistnode **ret, 84 SkiplistComparator comp); 85 86void *skiplist_pop(Skiplist * a, FreeFunc myfree); 87 88#endif 89