1 /* 2 * The Spread Toolkit. 3 * 4 * The contents of this file are subject to the Spread Open-Source 5 * License, Version 1.0 (the ``License''); you may not use 6 * this file except in compliance with the License. You may obtain a 7 * copy of the License at: 8 * 9 * http://www.spread.org/license/ 10 * 11 * or in the file ``license.txt'' found in this distribution. 12 * 13 * Software distributed under the License is distributed on an AS IS basis, 14 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License 15 * for the specific language governing rights and limitations under the 16 * License. 17 * 18 * The Creators of Spread are: 19 * Yair Amir, Michal Miskin-Amir, Jonathan Stanton. 20 * 21 * Copyright (C) 1993-2004 Spread Concepts LLC <spread@spreadconcepts.com> 22 * 23 * All Rights Reserved. 24 * 25 * Major Contributor(s): 26 * --------------- 27 * Cristina Nita-Rotaru crisn@cs.purdue.edu - group communication security. 28 * Theo Schlossnagle jesus@omniti.com - Perl, skiplists, autoconf. 29 * Dan Schoenblum dansch@cnds.jhu.edu - Java interface. 30 * John Schultz jschultz@cnds.jhu.edu - contribution to process group membership. 31 * 32 */ 33 34 35 #ifndef _SKIPLIST_P_H 36 #define _SKIPLIST_P_H 37 38 /* This is a skiplist implementation to be used for abstract structures 39 within the Spread multicast and group communication toolkit 40 41 This portion written by -- Theo Schlossnagle <jesus@cnds.jhu.eu> 42 */ 43 44 /* This is the function type that must be implemented per object type 45 that is used in a skiplist for comparisons to maintain order */ 46 typedef int (*SkiplistComparator)(void *, void *); 47 typedef void (*FreeFunc)(void *); 48 49 struct skiplistnode; 50 51 typedef struct _iskiplist { 52 SkiplistComparator compare; 53 SkiplistComparator comparek; 54 int height; 55 int preheight; 56 int size; 57 struct skiplistnode *top; 58 struct skiplistnode *bottom; 59 /* These two are needed for appending */ 60 struct skiplistnode *topend; 61 struct skiplistnode *bottomend; 62 struct _iskiplist *index; 63 } Skiplist; 64 65 struct skiplistnode { 66 void *data; 67 struct skiplistnode *next; 68 struct skiplistnode *prev; 69 struct skiplistnode *down; 70 struct skiplistnode *up; 71 struct skiplistnode *previndex; 72 struct skiplistnode *nextindex; 73 Skiplist *sl; 74 }; 75 76 77 void sl_init(Skiplist *sl); 78 void sl_set_compare(Skiplist *sl, SkiplistComparator, 79 SkiplistComparator); 80 void sl_add_index(Skiplist *sl, SkiplistComparator, 81 SkiplistComparator); 82 struct skiplistnode *sl_getlist(Skiplist *sl); 83 void *sl_find_compare(Skiplist *sl, void *data, struct skiplistnode **iter, 84 SkiplistComparator func); 85 void *sl_find(Skiplist *sl, void *data, struct skiplistnode **iter); 86 void *sl_next(Skiplist *sl, struct skiplistnode **); 87 void *sl_previous(Skiplist *sl, struct skiplistnode **); 88 89 struct skiplistnode *sl_insert_compare(Skiplist *sl, 90 void *data, SkiplistComparator comp); 91 struct skiplistnode *sl_insert(Skiplist *sl, void *data); 92 int sl_remove_compare(Skiplist *sl, void *data, 93 FreeFunc myfree, SkiplistComparator comp); 94 int sl_remove(Skiplist *sl, void *data, FreeFunc myfree); 95 int sli_remove(Skiplist *sl, struct skiplistnode *m, FreeFunc myfree); 96 void sl_remove_all(Skiplist *sl, FreeFunc myfree); 97 98 int sli_find_compare(Skiplist *sl, 99 void *data, 100 struct skiplistnode **ret, 101 SkiplistComparator comp); 102 103 #endif 104