| 1 |
/* ====================================================================== |
|---|
| 2 |
* Copyright (c) 2000 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 at http://www.gnu.org/copyleft/lesser.html |
|---|
| 11 |
* ====================================================================== |
|---|
| 12 |
*/ |
|---|
| 13 |
|
|---|
| 14 |
#ifndef _SKIPLIST_P_H |
|---|
| 15 |
#define _SKIPLIST_P_H |
|---|
| 16 |
|
|---|
| 17 |
/* This is a skiplist implementation to be used for abstract structures |
|---|
| 18 |
within the Spread multicast and group communication toolkit |
|---|
| 19 |
|
|---|
| 20 |
This portion written by -- Theo Schlossnagle <jesus@cnds.jhu.eu> |
|---|
| 21 |
*/ |
|---|
| 22 |
|
|---|
| 23 |
/* This is the function type that must be implemented per object type |
|---|
| 24 |
that is used in a skiplist for comparisons to maintain order */ |
|---|
| 25 |
typedef int (*SkiplistComparator)(void *, void *); |
|---|
| 26 |
typedef void (*FreeFunc)(void *); |
|---|
| 27 |
|
|---|
| 28 |
struct skiplistnode; |
|---|
| 29 |
|
|---|
| 30 |
typedef struct _iskiplist { |
|---|
| 31 |
SkiplistComparator compare; |
|---|
| 32 |
SkiplistComparator comparek; |
|---|
| 33 |
int height; |
|---|
| 34 |
int preheight; |
|---|
| 35 |
int size; |
|---|
| 36 |
struct skiplistnode *top; |
|---|
| 37 |
struct skiplistnode *bottom; |
|---|
| 38 |
/* These two are needed for appending */ |
|---|
| 39 |
struct skiplistnode *topend; |
|---|
| 40 |
struct skiplistnode *bottomend; |
|---|
| 41 |
struct _iskiplist *index; |
|---|
| 42 |
} Skiplist; |
|---|
| 43 |
|
|---|
| 44 |
struct skiplistnode { |
|---|
| 45 |
void *data; |
|---|
| 46 |
struct skiplistnode *next; |
|---|
| 47 |
struct skiplistnode *prev; |
|---|
| 48 |
struct skiplistnode *down; |
|---|
| 49 |
struct skiplistnode *up; |
|---|
| 50 |
struct skiplistnode *previndex; |
|---|
| 51 |
struct skiplistnode *nextindex; |
|---|
| 52 |
Skiplist *sl; |
|---|
| 53 |
}; |
|---|
| 54 |
|
|---|
| 55 |
|
|---|
| 56 |
void sl_init(Skiplist *sl); |
|---|
| 57 |
void sl_set_compare(Skiplist *sl, SkiplistComparator, |
|---|
| 58 |
SkiplistComparator); |
|---|
| 59 |
void sl_add_index(Skiplist *sl, SkiplistComparator, |
|---|
| 60 |
SkiplistComparator); |
|---|
| 61 |
struct skiplistnode *sl_getlist(Skiplist *sl); |
|---|
| 62 |
void *sl_find_compare(Skiplist *sl, void *data, struct skiplistnode **iter, |
|---|
| 63 |
SkiplistComparator func); |
|---|
| 64 |
void *sl_find(Skiplist *sl, void *data, struct skiplistnode **iter); |
|---|
| 65 |
void *sl_next(Skiplist *sl, struct skiplistnode **); |
|---|
| 66 |
void *sl_previous(Skiplist *sl, struct skiplistnode **); |
|---|
| 67 |
|
|---|
| 68 |
struct skiplistnode *sl_insert_compare(Skiplist *sl, |
|---|
| 69 |
void *data, SkiplistComparator comp); |
|---|
| 70 |
struct skiplistnode *sl_insert(Skiplist *sl, void *data); |
|---|
| 71 |
int sl_remove_compare(Skiplist *sl, void *data, |
|---|
| 72 |
FreeFunc myfree, SkiplistComparator comp); |
|---|
| 73 |
int sl_remove(Skiplist *sl, void *data, FreeFunc myfree); |
|---|
| 74 |
int sli_remove(Skiplist *sl, struct skiplistnode *m, FreeFunc myfree); |
|---|
| 75 |
void sl_remove_all(Skiplist *sl, FreeFunc myfree); |
|---|
| 76 |
|
|---|
| 77 |
int sli_find_compare(Skiplist *sl, |
|---|
| 78 |
void *data, |
|---|
| 79 |
struct skiplistnode **ret, |
|---|
| 80 |
SkiplistComparator comp); |
|---|
| 81 |
|
|---|
| 82 |
#endif |
|---|
