root/trunk/skiplist.h

Revision 2, 2.7 kB (checked in by jesus, 14 years ago)

Initial revision

  • Property svn:eol-style set to native
  • Property svn:executable set to *
  • Property svn:keywords set to Author Date Id Revision
Line 
1 /* ======================================================================
2  * Copyright (c) 2000 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 at http://www.gnu.org/copyleft/lesser.html
11  * ======================================================================
12 */
13
14 #ifndef _SKIPLIST_P_H
15 #define _SKIPLIST_P_H
16
17 /* This is a skiplist implementation to be used for abstract structures
18    within the Spread multicast and group communication toolkit
19
20    This portion written by -- Theo Schlossnagle <jesus@cnds.jhu.eu>
21 */
22
23 /* This is the function type that must be implemented per object type
24    that is used in a skiplist for comparisons to maintain order */
25 typedef int (*SkiplistComparator)(void *, void *);
26 typedef void (*FreeFunc)(void *);
27
28 struct skiplistnode;
29
30 typedef struct _iskiplist {
31   SkiplistComparator compare;
32   SkiplistComparator comparek;
33   int height;
34   int preheight;
35   int size;
36   struct skiplistnode *top;
37   struct skiplistnode *bottom;
38   /* These two are needed for appending */
39   struct skiplistnode *topend;
40   struct skiplistnode *bottomend;
41   struct _iskiplist *index;
42 } Skiplist;
43
44 struct skiplistnode {
45   void *data;
46   struct skiplistnode *next;
47   struct skiplistnode *prev;
48   struct skiplistnode *down;
49   struct skiplistnode *up;
50   struct skiplistnode *previndex;
51   struct skiplistnode *nextindex;
52   Skiplist *sl;
53 };
54
55
56 void sl_init(Skiplist *sl);
57 void sl_set_compare(Skiplist *sl, SkiplistComparator,
58                     SkiplistComparator);
59 void sl_add_index(Skiplist *sl, SkiplistComparator,
60                   SkiplistComparator);
61 struct skiplistnode *sl_getlist(Skiplist *sl);
62 void *sl_find_compare(Skiplist *sl, void *data, struct skiplistnode **iter,
63                       SkiplistComparator func);
64 void *sl_find(Skiplist *sl, void *data, struct skiplistnode **iter);
65 void *sl_next(Skiplist *sl, struct skiplistnode **);
66 void *sl_previous(Skiplist *sl, struct skiplistnode **);
67
68 struct skiplistnode *sl_insert_compare(Skiplist *sl,
69                                        void *data, SkiplistComparator comp);
70 struct skiplistnode *sl_insert(Skiplist *sl, void *data);
71 int sl_remove_compare(Skiplist *sl, void *data,
72                       FreeFunc myfree, SkiplistComparator comp);
73 int sl_remove(Skiplist *sl, void *data, FreeFunc myfree);
74 int sli_remove(Skiplist *sl, struct skiplistnode *m, FreeFunc myfree);
75 void sl_remove_all(Skiplist *sl, FreeFunc myfree);
76
77 int sli_find_compare(Skiplist *sl,
78                     void *data,
79                     struct skiplistnode **ret,
80                     SkiplistComparator comp);
81
82 #endif
Note: See TracBrowser for help on using the browser.