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 |
---|