/*  Skiplist module -- Warwick  */

/* ------------------------------------------------------------------------- *\

 Skiplists, also known as self-balancing trees, have most of the advantages
   of normal trees, but are a little more efficient with memory, and have
   considerably better deletion properties. Insertion is about the same.

 In fact, you are able to 'tune' skiplists to particular situations with
  the 'attrition rate' parameter. This determines the memory/speed tradeoff.


 A 'Header' consists essentially of a vector of pointers. The topmost [0]
 pointer leads to a conventional sorted linked list of nodes. The second, 
 however leads to a list of some of the items in the first list, which in 
 addition to the linked list 'next' have a 'next[1]' pointer, forming the 
 second level list. A third level has some of the items in the second list, 
 and so on.
 
 An item in the first level only has one 'next' pointer.
 An item in the second level has two 'next's.
 An item in the third level has three 'next's. and so on.
 
 A parameter called 'attrition rate' determines how likely it is that an item
 will be added just to the simple chain (most likely), or to higher chains.
 A value of n approximates an n-ary tree.
 
 Searching requires a look along the deepest level, until the item is found 
 and returned, or something later than the item is found, when the previous
 item is taken, and its link to the nexl level is used to search for the 
 item, and so on, until the item is either found, or the first level list 
 is exhausted.

 Adding is a similar process, but depending on whether duplicates are allowed,
 the addition will either fail, or a set of pointers to the deepest level will
 be gained. The order of the future item is then randomly determined, and 
 it is slipped into the lists it will need to span.
 
 Deletion is simply a matter of finding the item and tying the pointers around
 it, before freeing the item.

 * ------------------------------------------------------------------------- *
 
 Hopefully, use is fairly clear.
 
 Inserting items in multiple lists is similarly simple, although clearly,
 skip_destruct should only be given destructors for data not previously 
 deallocated.

 
 int Mycmp ( void *a, void *b ) 
 	{ return strcmp(((MYNODE)a)->name,((MYNODE)b)->name); }
 
 char *MyShow ( void *a ) 
 	{ return ((MYNODE)a)->name; }
 
 void MyKiller( void *a ) 
	{ if (a) free(((MYNODE)a)->name), free(a); }
 
 main ()
 {
 	SKIPHEADER *MyList=new_skip_head( Mycmp, 4);
	
	MYNODE *node=0;
	
	while ( getitem(&node) ) 
		printf( skip_add(node,MyList) ? node=0,"Added.\n" : "Not added.\n" );
	
	skip_print( MyList, printf, MyShow );
	
	while ( getitem(&node) )
		printf( skip_find(node,MyList) ? "Found that.\n" : "Not found.\n" );
	
	skip_destruct( MyKiller, MyList );
 }

\* ------------------------------------------------------------------------- */

/* SKIPHEADER is the 'handle' on the list. */

typedef struct SKIPHEADER SKIPHEADER;

/* skip_error is set after most functions. */

enum { SKIP_NOERROR=0, 					/* No worries. */
		SKIP_NOMEM, 					/* malloc failed during insertion. */
		SKIP_SAMEVALUE, SKIP_SAMEITEM,	/* Insertion found duplicate. */
		SKIP_BADPARAMS, 				/* A function was given null pointers */
		SKIP_CORRUPT 					/* An insert/remove went sadly wrong */
	};
		
extern char skip_error;

/*--------------------------------------------------------------------------*/

/* skip_print is a slightly specialised routine, mainly for debugging.
 * It shows the internal structure of the skiplist. You should supply
 * a header, a printf-like routine for printing, and a function which
 * returns a pointer to a static string representation of the data
 * sent to it.
 *
 * If NULL, node_to_string assumes that the first item in *data is a pointer to
 * a null-terminated string.
 */

extern void skip_print(	SKIPHEADER *head, 
						void (*printf)(char *,...), 
						char *(*node_to_string)(void*)   );
						
/*--------------------------------------------------------------------------*/

/* Creator of SKIPHEADERs. You shall provide a comparison
 *  function, much as required by qsort() in stdlib.h.
 *
 * The attrition rate gives the approximate order of tree to which
 *  the list aspires.
 */

extern SKIPHEADER *new_skip_head( int (*cmp)(void*,void*) , int attrition );

/*--------------------------------------------------------------------------*/

/* skip_destruct destroys a whole list, including header, quickly. 
 * Takes a list header and a destructor for the *data pointer.
 * If kill is NULL, it is assumed that the data needs no deallocation.
 * (For lists sharing items, for instance)
 */

extern void skip_destruct ( void (*kill)(void *), SKIPHEADER *head );

/* You should almost certainly use skip_destruct() rather than free_skip_head()
 *	since skip_destruct() kills both the header and any items in the list 
 *	if non-empty. It is provided mainly for symmetry with new_skip_head().
 */

extern void free_skip_head ( SKIPHEADER *head );

/*--------------------------------------------------------------------------*/

/* Search for a match of 'find' in the list. If found, return a pointer to
 *  the entry. Otherwise, return NULL.
 */

extern void *skip_find( void * find, SKIPHEADER *head );


/* skip_add:		Add item, duplicate data-values and data-items not allowed.
 *					Returns extant data, 	(SKIP_SAMEVALUE)
 *							added data or 	(skip_error unchanged)
 *							NULL.			(SKIP_NOMEM or SKIP_SAMEITEM)
 */

/* skip_insert:	Add item, duplicate data-values allowed, but not data-items.
 *					Returns added data or NULL (SKIP_NOMEM or SKIP_SAMEITEM).
 */

/* skip_jam:	Add item, no restrictions on data added.
 *					Returns added data or NULL (SKIP_NOMEM).
 */

extern void *skip_add	( void *data, SKIPHEADER *head );
extern void *skip_insert	( void *data, SKIPHEADER *head );
extern void *skip_jam	( void *data, SKIPHEADER *head );

/*--------------------------------------------------------------------------*/

/* skip_remove removes a vector from the skiplist. 
 * Returns data for free()ing (or whatever), or NULL if unfound.
 */

extern void *skip_remove( void *data, SKIPHEADER *head );

/*--------------------------------------------------------------------------*/

/* Ordered-list interrogation routines:
 *
 * Both return a pointer to a structure, the first item of which is a 
 *  pointer to the data item. Both return NULL for end-of-list or NULL.
 *
 * You may record returned values if you wish, but be certain that the item is 
 *  still validly in the list before subsequent use with skip_next().
 *
 * An item's position in the list will always be current and sorted.
 *
 * skip_next() should be given a value returned by skip_first() or previous
 * skip_next()s.
 */

extern void **skip_first ( SKIPHEADER *head );
extern void **skip_next ( void **node );