Skip list implementation

Collaboration diagram for Skip list implementation:

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_last_compare (apr_skiplist *sl, void *data, apr_skiplistnode **iter, apr_skiplist_compare comp)
void *	apr_skiplist_last (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)
void *	apr_skiplist_element (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)
apr_skiplistnode *	apr_skiplist_add_compare (apr_skiplist *sl, void *data, apr_skiplist_compare comp)
apr_skiplistnode *	apr_skiplist_add (apr_skiplist *sl, void *data)
apr_skiplistnode *	apr_skiplist_replace_compare (apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree, apr_skiplist_compare comp)
apr_skiplistnode *	apr_skiplist_replace (apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree)
int	apr_skiplist_remove_node (apr_skiplist *sl, apr_skiplistnode *iter, apr_skiplist_freefunc myfree)
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)
size_t	apr_skiplist_size (const apr_skiplist *sl)
int	apr_skiplist_height (const apr_skiplist *sl)
int	apr_skiplist_preheight (const apr_skiplist *sl)
void	apr_skiplist_set_preheight (apr_skiplist *sl, int to)
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

apr_skiplist

typedef struct apr_skiplist apr_skiplist

Opaque structure used to represent the skip list

apr_skiplist_compare

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

apr_skiplist_freefunc

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.

apr_skiplistnode

typedef struct apr_skiplistnode apr_skiplistnode

Opaque structure

Function Documentation

apr_skiplist_add()

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

Add an element into the skip list using the existing comparison function allowing for duplicates.

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_skiplist_add_compare()

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

Add an element into the skip list using the specified comparison function allowing for duplicates.

Parameters

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

apr_skiplist_add_index()

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