tpl_skipList.H File Reference

Skip list: probabilistic sorted linked structure. More...

#include <climits>
#include <ctime>
#include <gsl/gsl_rng.h>
#include <aleph.H>
#include <ah-errors.H>

Include dependency graph for tpl_skipList.H:

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

Go to the source code of this file.

Classes
class	Aleph::SkipList< Key, Type >
	Skip List - a probabilistic ordered data structure. More...
class	Aleph::SkipList< Key, Type >::Node
class	Aleph::SkipList< Key, Type >::HeaderNode
class	Aleph::SkipList< Key, Type >::Iterator
	Iterator for traversing SkipList elements in ascending order. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Skip list: probabilistic sorted linked structure.

Multi-level linked list with random tower heights providing expected O(log n) search, insert, and delete.

Features

• Simple implementation (no rotations)
• Good cache locality
• Lock-free variants possible

Complexity: O(log n) expected for all operations

See also

tpl_dynSkipList.H Dynamic variant

Author

Leandro Rabindranath León

Definition in file tpl_skipList.H.