root/src/utils/noit_skiplist.h

Revision ef59bc73bec75f7ab931c023663f3d3e50f569c4, 4.1 kB (checked in by Theo Schlossnagle <jesus@omniti.com>, 10 years ago)

cleanup some makefiles and code -- make it easier to see warnings

  • 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)(const void *, const 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   struct _iskiplist *index;
43 } noit_skiplist;
44
45 typedef struct _noit_skiplist_node {
46   void *data;
47   struct _noit_skiplist_node *next;
48   struct _noit_skiplist_node *prev;
49   struct _noit_skiplist_node *down;
50   struct _noit_skiplist_node *up;
51   struct _noit_skiplist_node *previndex;
52   struct _noit_skiplist_node *nextindex;
53   noit_skiplist *sl;
54 } noit_skiplist_node;
55
56
57 void noit_skiplist_init(noit_skiplist *sl);
58 void noit_skiplist_set_compare(noit_skiplist *sl, noit_skiplist_comparator_t,
59                                noit_skiplist_comparator_t);
60 void noit_skiplist_add_index(noit_skiplist *sl, noit_skiplist_comparator_t,
61                              noit_skiplist_comparator_t);
62 noit_skiplist_node *noit_skiplist_getlist(noit_skiplist *sl);
63 void *noit_skiplist_find_compare(noit_skiplist *sl, const void *data,
64                                  noit_skiplist_node **iter,
65                                  noit_skiplist_comparator_t func);
66 void *noit_skiplist_find_neighbors_compare(noit_skiplist *sl, const void *data,
67                                            noit_skiplist_node **iter,
68                                            noit_skiplist_node **prev,
69                                            noit_skiplist_node **next,
70                                            noit_skiplist_comparator_t func);
71 void *noit_skiplist_find(noit_skiplist *sl, const void *data,
72                          noit_skiplist_node **iter);
73 void *noit_skiplist_find_neighbors(noit_skiplist *sl, const void *data,
74                                    noit_skiplist_node **iter,
75                                    noit_skiplist_node **prev,
76                                    noit_skiplist_node **next);
77 void *noit_skiplist_next(noit_skiplist *sl, noit_skiplist_node **);
78 void *noit_skiplist_previous(noit_skiplist *sl, noit_skiplist_node **);
79
80 noit_skiplist_node *noit_skiplist_insert_compare(noit_skiplist *sl,
81                                                  const void *data,
82                                                  noit_skiplist_comparator_t comp);
83 noit_skiplist_node *noit_skiplist_insert(noit_skiplist *sl, const void *data);
84 int noit_skiplist_remove_compare(noit_skiplist *sl, const void *data,
85                                  noit_freefunc_t myfree,
86                                  noit_skiplist_comparator_t comp);
87 int noit_skiplist_remove(noit_skiplist *sl, const void *data,
88                          noit_freefunc_t myfree);
89 int noit_skiplisti_remove(noit_skiplist *sl, noit_skiplist_node *m,
90                           noit_freefunc_t myfree);
91 void noit_skiplist_remove_all(noit_skiplist *sl, noit_freefunc_t myfree);
92
93 void *noit_skiplist_pop(noit_skiplist * a, noit_freefunc_t myfree);
94 void *noit_skiplist_peek(noit_skiplist * a);
95
96 int noit_compare_voidptr(const void *, const void *);
97
98 #endif
Note: See TracBrowser for help on using the browser.