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