root/src/utils/noit_skiplist.h

Revision b62cf2be087943dcb29b6e068bd4262862fcb17d, 3.8 kB (checked in by Theo Schlossnagle <jesus@omniti.com>, 6 years ago)

more work... fleshing out the eventer

  • Property mode set to 100644
Line 
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 _NOIT_SKIPLIST_P_H
19 #define _NOIT_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 */
29 typedef int (*noit_skiplist_comparator_t)(void *, void *);
30 typedef void (*noit_freefunc_t)(void *);
31
32 struct _noit_skiplist_node;
33
34 typedef struct _iskiplist {
35   noit_skiplist_comparator_t compare;
36   noit_skiplist_comparator_t comparek;
37   int height;
38   int preheight;
39   int size;
40   struct _noit_skiplist_node *top;
41   struct _noit_skiplist_node *bottom;
42   /* These two are needed for appending */
43   struct _noit_skiplist_node *topend;
44   struct _noit_skiplist_node *bottomend;
45   struct _iskiplist *index;
46 } noit_skiplist;
47
48 typedef struct _noit_skiplist_node {
49   void *data;
50   struct _noit_skiplist_node *next;
51   struct _noit_skiplist_node *prev;
52   struct _noit_skiplist_node *down;
53   struct _noit_skiplist_node *up;
54   struct _noit_skiplist_node *previndex;
55   struct _noit_skiplist_node *nextindex;
56   noit_skiplist *sl;
57 } noit_skiplist_node;
58
59
60 void noit_skiplist_init(noit_skiplist *sl);
61 void noit_skiplist_set_compare(noit_skiplist *sl, noit_skiplist_comparator_t,
62                                noit_skiplist_comparator_t);
63 void noit_skiplist_add_index(noit_skiplist *sl, noit_skiplist_comparator_t,
64                              noit_skiplist_comparator_t);
65 noit_skiplist_node *noit_skiplist_getlist(noit_skiplist *sl);
66 void *noit_skiplist_find_compare(noit_skiplist *sl, void *data,
67                                  noit_skiplist_node **iter,
68                                  noit_skiplist_comparator_t func);
69 void *noit_skiplist_find(noit_skiplist *sl, void *data,
70                          noit_skiplist_node **iter);
71 void *noit_skiplist_next(noit_skiplist *sl, noit_skiplist_node **);
72 void *noit_skiplist_previous(noit_skiplist *sl, noit_skiplist_node **);
73
74 noit_skiplist_node *noit_skiplist_insert_compare(noit_skiplist *sl,
75                                                  void *data,
76                                                  noit_skiplist_comparator_t comp);
77 noit_skiplist_node *noit_skiplist_insert(noit_skiplist *sl, void *data);
78 int noit_skiplist_remove_compare(noit_skiplist *sl, void *data,
79                                  noit_freefunc_t myfree,
80                                  noit_skiplist_comparator_t comp);
81 int noit_skiplist_remove(noit_skiplist *sl, void *data, noit_freefunc_t myfree);
82 int noit_skiplisti_remove(noit_skiplist *sl, noit_skiplist_node *m,
83                           noit_freefunc_t myfree);
84 void noit_skiplist_remove_all(noit_skiplist *sl, noit_freefunc_t myfree);
85
86 int noit_skiplisti_find_compare(noit_skiplist *sl, void *data,
87                                 noit_skiplist_node **ret,
88                                 noit_skiplist_comparator_t comp);
89
90 void *noit_skiplist_pop(noit_skiplist * a, noit_freefunc_t myfree);
91 void *noit_skiplist_peek(noit_skiplist * a);
92
93 int noit_compare_voidptr(void *, void *);
94
95 #endif
Note: See TracBrowser for help on using the browser.