skiplist.h File Reference

Skip list [Pugh 1990]. More...

#include "dict.h"

Include dependency graph for skiplist.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs
typedef struct skiplist	skiplist
	A skip list.
typedef struct skiplist_itor	skiplist_itor
	An iterator over a skip list.

Functions
skiplist *	skiplist_new (dict_compare_func cmp_func, unsigned max_link)
	Create an empty skip list that orders keys with |cmp_func| (must not be NULL).
dict *	skiplist_dict_new (dict_compare_func cmp_func, unsigned max_link)
	Like skiplist_new(), but wrapped in a generic dict for use with the dict_* macros.
size_t	skiplist_free (skiplist *list, dict_delete_func delete_func)
	Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL, and free the list.
dict_insert_result	skiplist_insert (skiplist *list, void *key)
	Insert |key| unless an equal key is present.
void **	skiplist_search (skiplist *list, const void *key)
	Return the address of the datum stored for |key|, or NULL if |key| is not present.
void **	skiplist_search_le (skiplist *list, const void *key)
	Return the address of the datum of the greatest key less than or equal to |key|, or NULL if there is none.
void **	skiplist_search_lt (skiplist *list, const void *key)
	Return the address of the datum of the greatest key less than |key|, or NULL if there is none.
void **	skiplist_search_ge (skiplist *list, const void *key)
	Return the address of the datum of the least key greater than or equal to |key|, or NULL if there is none.
void **	skiplist_search_gt (skiplist *list, const void *key)
	Return the address of the datum of the least key greater than |key|, or NULL if there is none.
dict_remove_result	skiplist_remove (skiplist *list, const void *key)
	Remove the element with key |key|.
size_t	skiplist_clear (skiplist *list, dict_delete_func delete_func)
	Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL.
size_t	skiplist_traverse (skiplist *list, dict_visit_func visit, void *user_data)
	Call |visit|(key, datum, |user_data|) for each element in key order, stopping early if |visit| returns false.
size_t	skiplist_count (const skiplist *list)
	Return the number of elements.
bool	skiplist_verify (const skiplist *list)
	Check the internal invariants of the list and return true if they hold, or print the first failed check to stderr and return false.
size_t	skiplist_link_count_histogram (const skiplist *list, size_t counts[], size_t ncounts)
	Compute the histogram of link counts of the skiplist.
skiplist_itor *	skiplist_itor_new (skiplist *list)
	Create an iterator over |list| that is not positioned on any element yet.
dict_itor *	skiplist_dict_itor_new (skiplist *list)
	Like skiplist_itor_new(), but wrapped in a generic dict_itor for use with the dict_itor_* macros.
void	skiplist_itor_free (skiplist_itor *itor)
	Free an iterator.
bool	skiplist_itor_valid (const skiplist_itor *itor)
	Return whether |itor| is positioned on an element.
void	skiplist_itor_invalidate (skiplist_itor *itor)
	Unposition |itor|, so that it is not positioned on any element.
bool	skiplist_itor_next (skiplist_itor *itor)
	Move |itor| to the next element in key order and return true, or unposition it and return false if there is none.
bool	skiplist_itor_prev (skiplist_itor *itor)
	Move |itor| to the previous element in key order and return true, or unposition it and return false if there is none.
bool	skiplist_itor_nextn (skiplist_itor *itor, size_t count)
	Move |itor| |count| elements forward and return whether it is still positioned.
bool	skiplist_itor_prevn (skiplist_itor *itor, size_t count)
	Move |itor| |count| elements back and return whether it is still positioned.
bool	skiplist_itor_first (skiplist_itor *itor)
	Position |itor| on the first element in key order and return true, or unposition it and return false if the list is empty.
bool	skiplist_itor_last (skiplist_itor *itor)
	Position |itor| on the last element in key order and return true, or unposition it and return false if the list is empty.
bool	skiplist_itor_search (skiplist_itor *itor, const void *key)
	Position |itor| on |key| and return true, or unposition it and return false if |key| is not present.
bool	skiplist_itor_search_le (skiplist_itor *itor, const void *key)
	Position |itor| on the greatest key less than or equal to |key| and return true, or unposition it and return false if there is none.
bool	skiplist_itor_search_lt (skiplist_itor *itor, const void *key)
	Position |itor| on the greatest key less than |key| and return true, or unposition it and return false if there is none.
bool	skiplist_itor_search_ge (skiplist_itor *itor, const void *key)
	Position |itor| on the least key greater than or equal to |key| and return true, or unposition it and return false if there is none.
bool	skiplist_itor_search_gt (skiplist_itor *itor, const void *key)
	Position |itor| on the least key greater than |key| and return true, or unposition it and return false if there is none.
const void *	skiplist_itor_key (const skiplist_itor *itor)
	Return the key |itor| is positioned on, or NULL if it is not positioned.
void **	skiplist_itor_datum (skiplist_itor *itor)
	Return the address of the datum |itor| is positioned on, through which it can be read or replaced, or NULL if it is not positioned.
int	skiplist_itor_compare (const skiplist_itor *it1, const skiplist_itor *it2)
	Compare the positions of two iterators over the same list: return a negative value, zero, or a positive value as |it1| is before, at, or after |it2| in key order.
bool	skiplist_itor_remove (skiplist_itor *itor)
	Remove the element |itor| is positioned on and unposition |itor|; return false if it was not positioned.

Detailed Description

Skip list [Pugh 1990].

A sorted linked list with additional express links on randomly chosen levels, so insert, search and remove take expected O(log n) time. It supports the near searches but not selecting the nth element. Levels come from random(), which libdict does not seed.

Definition in file skiplist.h.

Typedef Documentation

skiplist

typedef struct skiplist skiplist

A skip list.

Opaque: create one with skiplist_new().

Definition at line 45 of file skiplist.h.

skiplist_itor

typedef struct skiplist_itor skiplist_itor

An iterator over a skip list.

Opaque: create one with skiplist_itor_new().

Definition at line 117 of file skiplist.h.

Function Documentation

skiplist_clear()

size_t skiplist_clear	(	skiplist *	list,
		dict_delete_func	delete_func )

Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL.

Returns the number of elements removed. The list stays usable. See Iterator invalidation for which iterators this invalidates.

Definition at line 453 of file skiplist.c.

skiplist_count()

size_t skiplist_count

(

const skiplist *

list

)

Return the number of elements.

Takes O(1) time.

Definition at line 484 of file skiplist.c.

skiplist_dict_itor_new()

dict_itor * skiplist_dict_itor_new

(

skiplist *

list

)

Like skiplist_itor_new(), but wrapped in a generic dict_itor for use with the dict_itor_* macros.

Free it with dict_itor_free().

Definition at line 563 of file skiplist.c.

Here is the call graph for this function:

skiplist_dict_new()

dict * skiplist_dict_new	(	dict_compare_func	cmp_func,
		unsigned	max_link )

Like skiplist_new(), but wrapped in a generic dict for use with the dict_* macros.

Free it with dict_free(). Returns NULL if memory cannot be allocated.

Definition at line 180 of file skiplist.c.

Here is the call graph for this function:

skiplist_free()

size_t skiplist_free	(	skiplist *	list,
		dict_delete_func	delete_func )

Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL, and free the list.

Returns the number of elements removed. Iterators over the list may afterwards only be freed.

Definition at line 194 of file skiplist.c.

Here is the call graph for this function:

skiplist_insert()

dict_insert_result skiplist_insert	(	skiplist *	list,
		void *	key )

Insert |key| unless an equal key is present.

Returns {&datum, true} for a new key, whose datum starts as NULL; the list stores the |key| pointer itself, it does not copy the key. If an equal key is present, returns {&datum, false} with that key's datum, and |key| is not stored and still belongs to the caller. Returns {NULL, false} if memory cannot be allocated.

Definition at line 228 of file skiplist.c.

skiplist_itor_compare()

int skiplist_itor_compare	(	const skiplist_itor *	it1,
		const skiplist_itor *	it2 )

Compare the positions of two iterators over the same list: return a negative value, zero, or a positive value as |it1| is before, at, or after |it2| in key order.

An unpositioned iterator compares before every positioned one.

Definition at line 694 of file skiplist.c.

skiplist_itor_datum()

void ** skiplist_itor_datum

(

skiplist_itor *

itor

)

Return the address of the datum |itor| is positioned on, through which it can be read or replaced, or NULL if it is not positioned.

Definition at line 688 of file skiplist.c.

skiplist_itor_first()

bool skiplist_itor_first

(

skiplist_itor *

itor

)

Position |itor| on the first element in key order and return true, or unposition it and return false if the list is empty.

Definition at line 629 of file skiplist.c.

skiplist_itor_free()

void skiplist_itor_free

(

skiplist_itor *

itor

)

Free an iterator.

Definition at line 577 of file skiplist.c.

skiplist_itor_invalidate()

void skiplist_itor_invalidate

(

skiplist_itor *

itor

)

Unposition |itor|, so that it is not positioned on any element.

Definition at line 589 of file skiplist.c.

skiplist_itor_key()

const void * skiplist_itor_key

(

const skiplist_itor *

itor

)

Return the key |itor| is positioned on, or NULL if it is not positioned.

The key belongs to the container and must not be modified in a way that changes how it compares.

Definition at line 682 of file skiplist.c.

skiplist_itor_last()

bool skiplist_itor_last

(

skiplist_itor *

itor

)

Position |itor| on the last element in key order and return true, or unposition it and return false if the list is empty.

Definition at line 635 of file skiplist.c.

skiplist_itor_new()

skiplist_itor * skiplist_itor_new

(

skiplist *

list

)

Create an iterator over |list| that is not positioned on any element yet.

Returns NULL if memory cannot be allocated.

Definition at line 552 of file skiplist.c.

skiplist_itor_next()

bool skiplist_itor_next

(

skiplist_itor *

itor

)

Move |itor| to the next element in key order and return true, or unposition it and return false if there is none.

An unpositioned iterator stays unpositioned and returns false.

Definition at line 595 of file skiplist.c.

skiplist_itor_nextn()

bool skiplist_itor_nextn	(	skiplist_itor *	itor,
		size_t	count )

Move |itor| |count| elements forward and return whether it is still positioned.

It becomes unpositioned if it runs past the last element.

Definition at line 611 of file skiplist.c.

Here is the call graph for this function:

skiplist_itor_prev()

bool skiplist_itor_prev

(

skiplist_itor *

itor

)

Move |itor| to the previous element in key order and return true, or unposition it and return false if there is none.

An unpositioned iterator stays unpositioned and returns false.

Definition at line 603 of file skiplist.c.

skiplist_itor_prevn()

bool skiplist_itor_prevn	(	skiplist_itor *	itor,
		size_t	count )

Move |itor| |count| elements back and return whether it is still positioned.

It becomes unpositioned if it runs past the first element.

Definition at line 620 of file skiplist.c.

Here is the call graph for this function:

skiplist_itor_remove()

bool skiplist_itor_remove

(

skiplist_itor *

itor

)

Remove the element |itor| is positioned on and unposition |itor|; return false if it was not positioned.

No delete function is called, so fetch the key and datum first if they need freeing. See Iterator invalidation for which iterators this invalidates.

Definition at line 705 of file skiplist.c.

Here is the call graph for this function:

skiplist_itor_search()

bool skiplist_itor_search	(	skiplist_itor *	itor,
		const void *	key )

Position |itor| on |key| and return true, or unposition it and return false if |key| is not present.

Definition at line 652 of file skiplist.c.

skiplist_itor_search_ge()

bool skiplist_itor_search_ge	(	skiplist_itor *	itor,
		const void *	key )

Position |itor| on the least key greater than or equal to |key| and return true, or unposition it and return false if there is none.

Definition at line 670 of file skiplist.c.

skiplist_itor_search_gt()

bool skiplist_itor_search_gt	(	skiplist_itor *	itor,
		const void *	key )

Position |itor| on the least key greater than |key| and return true, or unposition it and return false if there is none.

Definition at line 676 of file skiplist.c.

skiplist_itor_search_le()

bool skiplist_itor_search_le	(	skiplist_itor *	itor,
		const void *	key )

Position |itor| on the greatest key less than or equal to |key| and return true, or unposition it and return false if there is none.

Definition at line 658 of file skiplist.c.

skiplist_itor_search_lt()

bool skiplist_itor_search_lt	(	skiplist_itor *	itor,
		const void *	key )

Position |itor| on the greatest key less than |key| and return true, or unposition it and return false if there is none.

Definition at line 664 of file skiplist.c.

skiplist_itor_valid()

bool skiplist_itor_valid

(

const skiplist_itor *

itor

)

Return whether |itor| is positioned on an element.

Definition at line 583 of file skiplist.c.

skiplist_link_count_histogram()

size_t skiplist_link_count_histogram	(	const skiplist *	list,
		size_t	counts[],
		size_t	ncounts )

Compute the histogram of link counts of the skiplist.

For 0 <= x < |ncounts|, |counts|[x] will be set to the number of nodes with x links, and the maximal link count will be returned. If the return value is greater than or equal to |ncounts|, not all link counts could be stored in |counts| (i.e. the array was not large enough).

Definition at line 536 of file skiplist.c.

skiplist_new()

skiplist * skiplist_new	(	dict_compare_func	cmp_func,
		unsigned	max_link )

Create an empty skip list that orders keys with |cmp_func| (must not be NULL).

|max_link| is the number of levels in the list. It is clamped into the usable range [2, 32]: a node receives at most max_link - 1 links, so fewer than 2 levels could not link anything. Returns NULL if memory cannot be allocated.

Definition at line 151 of file skiplist.c.

skiplist_remove()

dict_remove_result skiplist_remove	(	skiplist *	list,
		const void *	key )

Remove the element with key |key|.

Returns {key, datum, true}, handing the stored key and datum back to the caller (no delete function is called), or {NULL, NULL, false} if |key| is not present. See Iterator invalidation for which iterators this invalidates.

Definition at line 407 of file skiplist.c.

skiplist_search()

void ** skiplist_search	(	skiplist *	list,
		const void *	key )

Return the address of the datum stored for |key|, or NULL if |key| is not present.

Definition at line 372 of file skiplist.c.

skiplist_search_ge()

void ** skiplist_search_ge	(	skiplist *	list,
		const void *	key )

Return the address of the datum of the least key greater than or equal to |key|, or NULL if there is none.

Definition at line 393 of file skiplist.c.

skiplist_search_gt()

void ** skiplist_search_gt	(	skiplist *	list,
		const void *	key )

Return the address of the datum of the least key greater than |key|, or NULL if there is none.

Definition at line 400 of file skiplist.c.

skiplist_search_le()

void ** skiplist_search_le	(	skiplist *	list,
		const void *	key )

Return the address of the datum of the greatest key less than or equal to |key|, or NULL if there is none.

Definition at line 379 of file skiplist.c.

skiplist_search_lt()

void ** skiplist_search_lt	(	skiplist *	list,
		const void *	key )

Return the address of the datum of the greatest key less than |key|, or NULL if there is none.

Definition at line 386 of file skiplist.c.

skiplist_traverse()

size_t skiplist_traverse	(	skiplist *	list,
		dict_visit_func	visit,
		void *	user_data )

Call |visit|(key, datum, |user_data|) for each element in key order, stopping early if |visit| returns false.

Returns the number of calls made.

Definition at line 473 of file skiplist.c.

skiplist_verify()

bool skiplist_verify

(

const skiplist *

list

)

Check the internal invariants of the list and return true if they hold, or print the first failed check to stderr and return false.

Meant for testing and debugging; takes O(n) time.

Definition at line 490 of file skiplist.c.