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 _SKIPLIST_P_H
19#define _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 */
29typedef int (*SkiplistComparator)(void *, void *);
30typedef void (*FreeFunc)(void *);
31
32struct skiplistnode;
33
34typedef struct _iskiplist {
35  SkiplistComparator compare;
36  SkiplistComparator comparek;
37  int height;
38  int preheight;
39  int size;
40  struct skiplistnode *top;
41  struct skiplistnode *bottom;
42  /* These two are needed for appending */
43  struct skiplistnode *topend;
44  struct skiplistnode *bottomend;
45  struct _iskiplist *index;
46} Skiplist;
47
48struct skiplistnode {
49  void *data;
50  struct skiplistnode *next;
51  struct skiplistnode *prev;
52  struct skiplistnode *down;
53  struct skiplistnode *up;
54  struct skiplistnode *previndex;
55  struct skiplistnode *nextindex;
56  Skiplist *sl;
57};
58
59
60void skiplist_init(Skiplist *sl);
61void skiplist_set_compare(Skiplist *sl, SkiplistComparator,
62		    SkiplistComparator);
63void skiplist_add_index(Skiplist *sl, SkiplistComparator,
64		  SkiplistComparator);
65struct skiplistnode *skiplist_getlist(Skiplist *sl);
66void *skiplist_find_compare(Skiplist *sl, void *data, struct skiplistnode **iter,
67		      SkiplistComparator func);
68void *skiplist_find(Skiplist *sl, void *data, struct skiplistnode **iter);
69void *skiplist_next(Skiplist *sl, struct skiplistnode **);
70void *skiplist_previous(Skiplist *sl, struct skiplistnode **);
71
72struct skiplistnode *skiplist_insert_compare(Skiplist *sl,
73				       void *data, SkiplistComparator comp);
74struct skiplistnode *skiplist_insert(Skiplist *sl, void *data);
75int skiplist_remove_compare(Skiplist *sl, void *data,
76		      FreeFunc myfree, SkiplistComparator comp);
77int skiplist_remove(Skiplist *sl, void *data, FreeFunc myfree);
78int skiplisti_remove(Skiplist *sl, struct skiplistnode *m, FreeFunc myfree);
79void skiplist_remove_all(Skiplist *sl, FreeFunc myfree);
80
81int skiplisti_find_compare(Skiplist *sl,
82		    void *data,
83		    struct skiplistnode **ret,
84		    SkiplistComparator comp);
85
86void *skiplist_pop(Skiplist * a, FreeFunc myfree);
87
88#endif
89