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