1/*
2  This header file contains the definitions for use with the generic
3  SkipList package.
4
5  THIS CODE COPYRIGHT DOMINIC GIAMPAOLO.  NO WARRANTY IS EXPRESSED
6  OR IMPLIED.  YOU MAY USE THIS CODE AND FREELY DISTRIBUTE IT FOR
7  NON-COMMERCIAL USE AS LONG AS THIS NOTICE REMAINS ATTACHED.
8
9  FOR COMMERCIAL USE, CONTACT DOMINIC GIAMPAOLO (dbg@be.com).
10
11  Dominic Giampaolo
12  dbg@be.com
13 */
14
15#ifndef SKIPLIST_H
16#define SKIPLIST_H
17
18
19/* RAND_MAX should be defined if you are using an ANSI compiler system,
20 * but alas it isn't always.  You should define it to be the correct
21 * value for whatever your library rand() function returns.
22 *
23 * Under unix (mach, bsd, etc), that's 2^31 - 1.  On my Amiga at home
24 * it's 2^15 - 1.  It would be wise to verify what your compiler uses
25 * for RAND_MAX (the maximum value returned from rand()) because otherwise
26 * the code will _not_ work.
27 */
28#ifndef RAND_MAX
29#define RAND_MAX (0x7fffffff)
30#endif
31
32
33#define ALLOW_DUPLICATES  1   /* allow or disallow duplicates in a list */
34#define NO_DUPLICATES     0
35#define DUPLICATE_ITEM   -1   /* ret val from InsertSL if dups not allowed */
36
37
38/* typedef's */
39typedef struct SLNodeStruct *SLNode;
40
41struct SLNodeStruct
42{
43  void   *key;
44  SLNode  forward[1]; /* variable sized array of forward pointers */
45};
46
47typedef struct _SkipList
48{
49  struct SLNodeStruct *header;     /* pointer to header */
50
51  int  (*compare)();
52  void (*freeitem)();
53
54  int flags;
55  int level;               /* max index+1 of the forward array */
56
57  int count;                       /* number of elements in the list */
58} *SkipList;
59
60
61
62/* protos */
63SkipList   NewSL(int (*compare)(), void (*freeitem)(), int flags);
64void       FreeSL(SkipList l);
65int    InsertSL(SkipList l, void *key);
66int    DeleteSL(SkipList l, void *key);
67void      *SearchSL(SkipList l, void *key);
68void       DoForSL(SkipList  l, int (*function)(), void *arg);
69void       DoForRangeSL(SkipList l, void *key, int (*compare)(),
70            int (*func)(), void *arg);
71
72int        NumInSL(SkipList l);
73
74
75/* These defines are to be used as return values from the function
76 * you pass to DoForSL().  They can be or'ed together to do multiple
77 * things (like delete a node and then quit going through the list).
78 */
79#define  SL_CONTINUE  0x00
80#define  SL_DELETE    0x01
81#define  SL_QUIT      0x02
82
83#endif  /* SKIPLIST_H */
84