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_H 36 #define _SKIPLIST_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 void *data; 51 void *private_use[7]; 52 }; 53 54 typedef struct { 55 SkiplistComparator compare; 56 SkiplistComparator comparek; 57 const int height; 58 int preheight; 59 const int size; 60 void *private_use[5]; 61 } Skiplist; 62 63 /* set up the internals for this skiplist */ 64 void sl_init(Skiplist *sl); 65 66 /* set a compare function to be used by the skiplist */ 67 /* Pass a skiplist in, a comparator for (record, record) and a 68 comparator for (key, record) in the order */ 69 70 void sl_set_compare(Skiplist *, SkiplistComparator, 71 SkiplistComparator); 72 void sl_add_index(Skiplist *sl, SkiplistComparator, 73 SkiplistComparator); 74 75 /* Returns a pointer to the first node in the list 76 DO NOT EDIT THIS LIST! It is maintained internally and should not 77 be toyed with */ 78 struct skiplistnode *sl_getlist(Skiplist *sl); 79 80 /* Find returns NULL on failure and a point to the data on success */ 81 /* sl is the skiplist in which you are looking 82 data the key you are looking for 83 iter is an iterator that is filled out with the found node 84 it is then passed into next and previous to iterate through the list */ 85 void *sl_find(Skiplist *sl, void *data, struct skiplistnode **iter); 86 void *sl_find_compare(Skiplist *sl, void *data, struct skiplistnode **iter, 87 SkiplistComparator comp); 88 void *sl_next(Skiplist *sl, struct skiplistnode **iter); 89 void *sl_previous(Skiplist *sl, struct skiplistnode **iter); 90 91 /* Insert returns 0 on failure and a pointer to the skiplistnode on success */ 92 /* sl is the skiplist in which you are inserting 93 data is a record (not necessarily the key) */ 94 struct skiplistnode *sl_insert(Skiplist *sl, void *data); 95 96 /* Append and concatenate are special.. They are used to effeciently create 97 a skiplist from presorted data. You MUST be sure that there are not 98 multiple indices and that the comparator is the same. 99 Both return NULL on error and the skiplistnode inserted and the new 100 Skiplist on success, respectively */ 101 struct skiplistnode *sl_append(Skiplist *sl, void *data); 102 /* The return value will match dest on success and appending will be empty and 103 thus freeable without leakage */ 104 Skiplist *sl_concat(Skiplist *dest, Skiplist *appending); 105 106 /* Remove returns 0 on failure and the current tree height on success */ 107 /* sl is the skiplist from which you are removing 108 data is the key for the node you wish to remove */ 109 int sl_remove(Skiplist *sl, void *data, FreeFunc myfree); 110 int sl_remove_compare(Skiplist *sl, void *data, FreeFunc myfree, 111 SkiplistComparator comp); 112 113 /* removes all nodes in a skiplist, the list can still be used */ 114 /* sl is the skiplist from which you are removing */ 115 void sl_remove_all(Skiplist *sl, FreeFunc myfree); 116 117 /* removes all nodes in a skiplist, you can free the skiplist itself 118 without memory leaks after calling this function. After calling 119 this function, the list cannot be safely used, it must be freed */ 120 void sl_destruct(Skiplist *sl, FreeFunc myfree); 121 122 123 #endif 124