Skip list implementation
[Apache Portability Runtime library]

Typedefs
typedef int(*	apr_skiplist_compare )(void *, void *)
typedef void(*	apr_skiplist_freefunc )(void *)
typedef struct apr_skiplist	apr_skiplist
typedef struct apr_skiplistnode	apr_skiplistnode
Functions
void *	apr_skiplist_alloc (apr_skiplist *sl, size_t size)
void	apr_skiplist_free (apr_skiplist *sl, void *mem)
apr_status_t	apr_skiplist_init (apr_skiplist **sl, apr_pool_t *p)
void	apr_skiplist_set_compare (apr_skiplist *sl, apr_skiplist_compare XXX1, apr_skiplist_compare XXX2)
void	apr_skiplist_add_index (apr_skiplist *sl, apr_skiplist_compare XXX1, apr_skiplist_compare XXX2)
apr_skiplistnode *	apr_skiplist_getlist (apr_skiplist *sl)
void *	apr_skiplist_find_compare (apr_skiplist *sl, void *data, apr_skiplistnode **iter, apr_skiplist_compare func)
void *	apr_skiplist_find (apr_skiplist *sl, void *data, apr_skiplistnode **iter)
void *	apr_skiplist_next (apr_skiplist *sl, apr_skiplistnode **iter)
void *	apr_skiplist_previous (apr_skiplist *sl, apr_skiplistnode **iter)
apr_skiplistnode *	apr_skiplist_insert_compare (apr_skiplist *sl, void *data, apr_skiplist_compare comp)
apr_skiplistnode *	apr_skiplist_insert (apr_skiplist *sl, void *data)
int	apr_skiplist_remove_compare (apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree, apr_skiplist_compare comp)
int	apr_skiplist_remove (apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree)
void	apr_skiplist_remove_all (apr_skiplist *sl, apr_skiplist_freefunc myfree)
void	apr_skiplist_destroy (apr_skiplist *sl, apr_skiplist_freefunc myfree)
void *	apr_skiplist_pop (apr_skiplist *sl, apr_skiplist_freefunc myfree)
void *	apr_skiplist_peek (apr_skiplist *sl)
apr_skiplist *	apr_skiplist_merge (apr_skiplist *sl1, apr_skiplist *sl2)

---

Detailed Description

Refer to http://en.wikipedia.org/wiki/Skip_list for information about the purpose of and ideas behind skip lists.

---

Typedef Documentation

typedef struct apr_skiplist apr_skiplist

Opaque structure used to represent the skip list

typedef int(* apr_skiplist_compare)(void *, void *)

apr_skiplist_compare is the function type that must be implemented per object type that is used in a skip list for comparisons to maintain order

typedef void(* apr_skiplist_freefunc)(void *)

apr_skiplist_freefunc is the function type that must be implemented to handle elements as they are removed from a skip list.

typedef struct apr_skiplistnode apr_skiplistnode

Opaque structure

---

Function Documentation

void apr_skiplist_add_index	(	apr_skiplist *	sl,
		apr_skiplist_compare	XXX1,
		apr_skiplist_compare	XXX2
	)

Set the indexing functions to the specified comparison functions and rebuild the index.

Parameters:

	sl	The skip list
	XXX1	FIXME
	XXX2	FIXME

Remarks:

If an index already exists, it will not be replaced and the comparison functions will not be changed.

void* apr_skiplist_alloc	(	apr_skiplist *	sl,
		size_t	size
	)

Allocate memory using the same mechanism as the skip list.

Parameters:

	sl	The skip list
	size	The amount to allocate

Remarks:

If a pool was provided to apr_skiplist_init(), memory will be allocated from the pool or from a free list maintained with the skip list. Otherwise, memory will be allocated using the C standard library heap functions.

void apr_skiplist_destroy	(	apr_skiplist *	sl,
		apr_skiplist_freefunc	myfree
	)

Remove each element from the skip list.

Parameters:

	sl	The skip list
	myfree	A function to be called for each removed element

void* apr_skiplist_find	(	apr_skiplist *	sl,
		void *	data,
		apr_skiplistnode **	iter
	)

Return the next matching element in the skip list using the current comparison function.

Parameters:

	sl	The skip list
	data	The value to search for
	iter	A pointer to the returned skip list node representing the element found

void* apr_skiplist_find_compare	(	apr_skiplist *	sl,
		void *	data,
		apr_skiplistnode **	iter,
		apr_skiplist_compare	func
	)

Return the next matching element in the skip list using the specified comparison function.

Parameters:

	sl	The skip list
	data	The value to search for
	iter	A pointer to the returned skip list node representing the element found
	func	The comparison function to use

void apr_skiplist_free	(	apr_skiplist *	sl,
		void *	mem
	)

Free memory using the same mechanism as the skip list.

Parameters:

	sl	The skip list
	mem	The object to free

Remarks:

If a pool was provided to apr_skiplist_init(), memory will be added to a free list maintained with the skip list and be available to operations on the skip list or to other calls to apr_skiplist_alloc(). Otherwise, memory will be freed using the C standard library heap functions.

apr_skiplistnode* apr_skiplist_getlist

(

apr_skiplist *

sl

)

Return the list maintained by the skip list abstraction.

Parameters:

sl

The skip list

apr_status_t apr_skiplist_init	(	apr_skiplist **	sl,
		apr_pool_t *	p
	)

Allocate a new skip list

Parameters:

	sl	The pointer in which to return the newly created skip list
	p	The pool from which to allocate the skip list (optional).

Remarks:

Unlike most APR functions, a pool is optional. If no pool is provided, the C standard library heap functions will be used instead.

apr_skiplistnode* apr_skiplist_insert	(	apr_skiplist *	sl,
		void *	data
	)

Insert an element into the skip list using the existing comparison function.

Parameters:

	sl	The skip list
	data	The element to insert

Remarks:

If no comparison function has been set for the skip list, the element will not be inserted and NULL will be returned.

apr_skiplistnode* apr_skiplist_insert_compare	(	apr_skiplist *	sl,
		void *	data,
		apr_skiplist_compare	comp
	)

Insert an element into the skip list using the specified comparison function.

Parameters:

	sl	The skip list
	data	The element to insert
	comp	The comparison function to use for placement into the skip list

apr_skiplist* apr_skiplist_merge	(	apr_skiplist *	sl1,
		apr_skiplist *	sl2
	)

Merge two skip lists. XXX SEMANTICS

Parameters:

	sl1	One of two skip lists to be merged
	sl2	The other of two skip lists to be merged

void* apr_skiplist_next	(	apr_skiplist *	sl,
		apr_skiplistnode **	iter
	)

Return the next element in the skip list.

Parameters:

	sl	The skip list
	iter	On entry, a pointer to the skip list node to start with; on return, a pointer to the skip list node representing the element returned

Remarks:

If iter points to a NULL value on entry, NULL will be returned.

void* apr_skiplist_peek

(

apr_skiplist *

sl

)

Return the first element in the skip list, leaving the element in the skip list.

Parameters:

sl

The skip list

Remarks:

NULL will be returned if there are no elements

void* apr_skiplist_pop	(	apr_skiplist *	sl,
		apr_skiplist_freefunc	myfree
	)

Return the first element in the skip list, leaving the element in the skip list.

Parameters:

	sl	The skip list
	myfree	A function to be called for the removed element

Remarks:

NULL will be returned if there are no elements

void* apr_skiplist_previous	(	apr_skiplist *	sl,
		apr_skiplistnode **	iter
	)

Return the previous element in the skip list.

Parameters:

	sl	The skip list
	iter	On entry, a pointer to the skip list node to start with; on return, a pointer to the skip list node representing the element returned

Remarks:

If iter points to a NULL value on entry, NULL will be returned.

int apr_skiplist_remove	(	apr_skiplist *	sl,
		void *	data,
		apr_skiplist_freefunc	myfree
	)

Remove an element from the skip list using the existing comparison function for locating the element.

Parameters:

	sl	The skip list
	data	The element to remove
	myfree	A function to be called for each removed element

Remarks:

If the element is not found, 0 will be returned. Otherwise, the heightXXX will be returned.

If no comparison function has been set for the skip list, the element will not be removed and 0 will be returned.

void apr_skiplist_remove_all	(	apr_skiplist *	sl,
		apr_skiplist_freefunc	myfree
	)

Remove all elements from the skip list.

Parameters:

	sl	The skip list
	myfree	A function to be called for each removed element

int apr_skiplist_remove_compare	(	apr_skiplist *	sl,
		void *	data,
		apr_skiplist_freefunc	myfree,
		apr_skiplist_compare	comp
	)

Remove an element from the skip list using the specified comparison function for locating the element.

Parameters:

	sl	The skip list
	data	The element to remove
	myfree	A function to be called for each removed element
	comp	The comparison function to use for placement into the skip list

Remarks:

If the element is not found, 0 will be returned. Otherwise, the heightXXX will be returned.

void apr_skiplist_set_compare	(	apr_skiplist *	sl,
		apr_skiplist_compare	XXX1,
		apr_skiplist_compare	XXX2
	)

Set the comparison functions to be used for searching the skip list.

Parameters:

	sl	The skip list
	XXX1	FIXME
	XXX2	FIXME

Remarks:

If existing comparison functions are being replaced, the index will be replaced during this call. That is a potentially expensive operation.