root/trunk/skiplist.h

Revision 42, 4.3 kB (checked in by jesus, 8 years ago)

function updates and libevent logging

  • 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 <jesus@omniti.com>
3  * Copyright (c) 2001-2004 OmniTI, Inc. All rights reserved
4  *
5  * The following code was written by Theo Schlossnagle for use in the
6  * Backhand project at The Center for Networking and Distributed Systems
7  * at The Johns Hopkins University.
8  *
9  */
10
11 #ifndef _SKIPLIST_P_H
12 #define _SKIPLIST_P_H
13
14 #ifdef __cplusplus
15 extern "C" {
16 #endif
17
18 #ifndef API_EXPORT
19 #define API_EXPORT(a) a
20 #endif
21
22 /* This is a skiplist implementation to be used for abstract structures
23    within the Spread multicast and group communication toolkit
24
25    This portion written by -- Theo Schlossnagle <jesus@cnds.jhu.eu>
26 */
27
28 /* This is the function type that must be implemented per object type
29    that is used in a skiplist for comparisons to maintain order */
30 typedef int (*SkiplistComparator) (const void *, const void *);
31 typedef void (*FreeFunc) (void *);
32
33 /*
34  This is the function type to use with the builtin traversal functions like level_order_apply
35  If it returns 1, the traversal will stop, otherwsie it will continue.
36 */
37 typedef int (*ApplyFunc) (void *);
38
39 struct skiplistnode;
40
41 typedef struct _iskiplist
42 {
43   SkiplistComparator compare;
44   SkiplistComparator comparek;
45   unsigned height:8;
46   unsigned preheight:8;
47   unsigned int size;
48   struct skiplistnode *bottom;
49   /* These two are needed for appending */
50   struct _iskiplist *index;
51   struct _iskiplist *agg;
52 }
53 Skiplist;
54
55 struct skipconn {
56   struct skiplistnode *next;
57   struct skiplistnode *prev;
58 };
59 struct skiplistnode
60 {
61   void *data;
62   Skiplist *sl;
63   unsigned int height;
64   struct skiplistnode *previndex;
65   struct skiplistnode *nextindex;
66   struct skipconn level[1];
67 };
68
69 #define SLNODESIZE(c) (sizeof(struct skiplistnode) + (c-1)*sizeof(struct skipconn))
70
71 /* The height will dictate the size */
72
73
74 API_EXPORT(void) sl_init(Skiplist * sl);
75 API_EXPORT(void) sl_init_mts(Skiplist * sl);
76 API_EXPORT(void) sl_set_compare(Skiplist * sl, SkiplistComparator, SkiplistComparator);
77 API_EXPORT(void) sl_add_index(Skiplist * sl, SkiplistComparator, SkiplistComparator);
78 API_EXPORT(void) sl_attach_aggregate(Skiplist * sl, Skiplist * agg);
79 API_EXPORT(struct skiplistnode *) sl_getlist(Skiplist * sl);
80 API_EXPORT(void *) sl_find_compare(const Skiplist * sl, const void *data,
81                       struct skiplistnode **iter, SkiplistComparator func);
82 API_EXPORT(void *) sl_find_compare_neighbors(const Skiplist * sl, const void *data, struct skiplistnode **iter, struct skiplistnode **prev, struct skiplistnode **next, SkiplistComparator func);
83 API_EXPORT(void *) sl_find(const Skiplist * sl, const void *data, struct skiplistnode **iter);
84 API_EXPORT(void *) sl_find_neighbors(const Skiplist * sl, const void *data, struct skiplistnode **iter, struct skiplistnode **prev, struct skiplistnode **next);
85 API_EXPORT(void *) sl_next(struct skiplistnode **);
86 API_EXPORT(void *) sl_previous(struct skiplistnode **);
87
88 API_EXPORT(struct skiplistnode *) sl_insert_compare(Skiplist * sl,
89                                        void *data, SkiplistComparator comp);
90 API_EXPORT(struct skiplistnode *) sl_insert(Skiplist * sl, void *data);
91 API_EXPORT(int) sl_remove_compare(Skiplist * sl, void *data,
92                       FreeFunc myfree, SkiplistComparator comp);
93 API_EXPORT(int) sl_remove(Skiplist * sl, void *data, FreeFunc myfree);
94 API_EXPORT(int) sli_remove(Skiplist * sl, struct skiplistnode *m, FreeFunc myfree);
95 API_EXPORT(void) sli_remove_all(Skiplist * sl, FreeFunc myfree);
96 API_EXPORT(void) sl_destruct(Skiplist *sl, FreeFunc myfree);
97 API_EXPORT(void) sli_destruct_free(Skiplist *sl, FreeFunc myfree);
98 API_EXPORT(void) sl_node_dataswap(Skiplist *sl, struct skiplistnode *node, void *data);
99
100 API_EXPORT(int) sli_find_compare(const Skiplist * sl,
101                      const void *data,
102                      struct skiplistnode **ret,
103                      struct skiplistnode **ret_prev,
104                      struct skiplistnode **ret_next,
105                      SkiplistComparator comp);
106 API_EXPORT(void) sl_level_order_apply(Skiplist *sl, ApplyFunc myfunc);
107
108 API_EXPORT(struct skiplistnode *) sl_getlist_end(Skiplist *sl);
109
110 #define sl_size(a) ((a)->size)
111
112 #define SL_index_compare (SkiplistComparator)0x01
113 #define SL_index_compare_key (SkiplistComparator)0x02
114 #define SL_INLINE_MAX (SkiplistComparator)0x03
115
116 #ifdef __cplusplus
117 }  /* Close scope of 'extern "C"' declaration which encloses file. */
118 #endif
119
120 #endif
Note: See TracBrowser for help on using the browser.