Berkeley DB 4.4.16: /home/huihoo/src/db/db-4.4.16/mod

00001 /* ======================================================================
00002  * Copyright (c) 2000 Theo Schlossnagle
00003  * All rights reserved.
00004  * The following code was written by Theo Schlossnagle for use in the
00005  * Backhand project at The Center for Networking and Distributed Systems
00006  * at The Johns Hopkins University.
00007  *
00008  * This is a skiplist implementation to be used for abstract structures
00009  * and is release under the LGPL license version 2.1 or later.  A copy
00010  * of this license can be found at http://www.gnu.org/copyleft/lesser.html
00011  * ======================================================================
00012 */
00013 
00014 #ifndef _SKIPLIST_P_H
00015 #define _SKIPLIST_P_H
00016 
00017 /* This is a skiplist implementation to be used for abstract structures
00018    within the Spread multicast and group communication toolkit
00019 
00020    This portion written by -- Theo Schlossnagle <[email protected]>
00021 */
00022 
00023 /* This is the function type that must be implemented per object type
00024    that is used in a skiplist for comparisons to maintain order */
00025 typedef int (*SkiplistComparator)(void *, void *);
00026 typedef void (*FreeFunc)(void *);
00027 
00028 struct skiplistnode;
00029 
00030 typedef struct _iskiplist {
00031   SkiplistComparator compare;
00032   SkiplistComparator comparek;
00033   int height;
00034   int preheight;
00035   int size;
00036   struct skiplistnode *top;
00037   struct skiplistnode *bottom;
00038   /* These two are needed for appending */
00039   struct skiplistnode *topend;
00040   struct skiplistnode *bottomend;
00041   struct _iskiplist *index;
00042 } Skiplist;
00043 
00044 struct skiplistnode {
00045   void *data;
00046   struct skiplistnode *next;
00047   struct skiplistnode *prev;
00048   struct skiplistnode *down;
00049   struct skiplistnode *up;
00050   struct skiplistnode *previndex;
00051   struct skiplistnode *nextindex;
00052   Skiplist *sl;
00053 };
00054 
00055 
00056 void skiplist_init(Skiplist *sl);
00057 void skiplist_set_compare(Skiplist *sl, SkiplistComparator,
00058                     SkiplistComparator);
00059 void skiplist_add_index(Skiplist *sl, SkiplistComparator,
00060                   SkiplistComparator);
00061 struct skiplistnode *skiplist_getlist(Skiplist *sl);
00062 void *skiplist_find_compare(Skiplist *sl, void *data, struct skiplistnode **iter,
00063                       SkiplistComparator func);
00064 void *skiplist_find(Skiplist *sl, void *data, struct skiplistnode **iter);
00065 void *skiplist_next(Skiplist *sl, struct skiplistnode **);
00066 void *skiplist_previous(Skiplist *sl, struct skiplistnode **);
00067 
00068 struct skiplistnode *skiplist_insert_compare(Skiplist *sl,
00069                                        void *data, SkiplistComparator comp);
00070 struct skiplistnode *skiplist_insert(Skiplist *sl, void *data);
00071 int skiplist_remove_compare(Skiplist *sl, void *data,
00072                       FreeFunc myfree, SkiplistComparator comp);
00073 int skiplist_remove(Skiplist *sl, void *data, FreeFunc myfree);
00074 int skiplisti_remove(Skiplist *sl, struct skiplistnode *m, FreeFunc myfree);
00075 void skiplist_remove_all(Skiplist *sl, FreeFunc myfree);
00076 
00077 int skiplisti_find_compare(Skiplist *sl,
00078                     void *data,
00079                     struct skiplistnode **ret,
00080                     SkiplistComparator comp);
00081 
00082 void *skiplist_pop(Skiplist * a, FreeFunc myfree);
00083 
00084 #endif
skiplist.h
