Skip List - a probabilistic ordered data structure. More...

#include <tpl_skipList.H>

Collaboration diagram for Aleph::SkipList< Key, Type >:

Classes
class	HeaderNode

class	Iterator
	Iterator for traversing SkipList elements in ascending order. More...

class	Node

Public Member Functions
void	set_seed (unsigned long seed) noexcept
	Set the random number generator seed.

gsl_rng *	gsl_rng_object () noexcept
	Get a pointer to the GSL random number generator.

	SkipList (unsigned long seed, double p=defaultProbability)
	Construct a SkipList with given seed and probability.

	SkipList (double p=defaultProbability)
	Construct a SkipList with time-based seed.

	~SkipList ()
	Destructor - frees GSL random number generator.

	SkipList (const SkipList &)=delete

SkipList &	operator= (const SkipList &)=delete

	SkipList (SkipList &&other) noexcept

SkipList &	operator= (SkipList &&other) noexcept

Node *	search (const Key &searchKey) noexcept
	Search for a key in the skip list.

Node *	insert (Node *p) noexcept
	Insert a node into the skip list.

Node *	get_first () noexcept
	Get the first node in the list.

Node *	remove (const Key &searchKey) noexcept
	Remove a key from the skip list.

int	generateRandomLevel () noexcept
	Generate a random level for a new node.

bool	checkSkipList () const noexcept
	Verify skip list invariants (for debugging).

Node *	new_node () noexcept
	Placeholder for node allocation (override in derived classes).

Iterator	begin () const noexcept
	Get iterator to first element.

Iterator	end () const noexcept
	Get iterator past the last element.

Static Public Attributes
static const int	maxLevel = 32
	Maximum level for any node (supports up to 2^32 elements efficiently)

static const double	defaultProbability = 0.5
	Default probability for level generation (0.5 = geometric distribution)

Private Member Functions
void	init (unsigned long seed)

Private Attributes
HeaderNode	header

HeaderNode *	headerPtr

gsl_rng *	r

double	probability

int	level

Detailed Description

template<class Key, class Type>
class Aleph::SkipList< Key, Type >

Skip List - a probabilistic ordered data structure.

A Skip List is an ordered list where each node contains an array of forward pointers. The structure was proposed by William Pugh (1990).

Each node has a randomly determined level that defines how many forward pointers it contains. Higher levels allow faster traversal, giving O(log n) expected time for search, insert, and delete.

Key properties:

Expected O(log n) search, insert, delete
O(n) space complexity
Simple implementation compared to balanced trees
Good cache locality for sequential access

The class internally uses the gsl random number generator of GSL - GNU Scientific Library. By default, the Mersenne twister is used and the seed is taken from system time.

Warning: Nodes must be allocated with extra space for forward pointers: sizeof(Node) + sizeof(Node*) * level

Template Parameters

Key	Key type (must be comparable with <, ==)
Type	Data type stored alongside keys

See also: Pugh, W. "Skip Lists: A Probabilistic Alternative to Balanced Trees" Communications of the ACM, 1990.

Definition at line 93 of file tpl_skipList.H.

Constructor & Destructor Documentation

◆ SkipList() [1/4]

template<class Key , class Type >

Aleph::SkipList< Key, Type >::SkipList	(	unsigned long	seed,
		double	p = `defaultProbability`
	)

inline

Construct a SkipList with given seed and probability.

Parameters

[in]	seed	Random seed for level generation.
[in]	p	Probability for level increase (default 0.5).

Definition at line 270 of file tpl_skipList.H.

References Aleph::init, Aleph::maps(), and Aleph::SkipList< Key, Type >::probability.

◆ SkipList() [2/4]

template<class Key , class Type >

Aleph::SkipList< Key, Type >::SkipList ( double p = defaultProbability )

inlineexplicit

Construct a SkipList with time-based seed.

Parameters

[in] p Probability for level increase (default 0.5).

Definition at line 283 of file tpl_skipList.H.

◆ ~SkipList()

template<class Key , class Type >

Aleph::SkipList< Key, Type >::~SkipList ( )

inline

Destructor - frees GSL random number generator.

Definition at line 290 of file tpl_skipList.H.

References Aleph::maps(), and Aleph::SkipList< Key, Type >::r.

◆ SkipList() [3/4]

template<class Key , class Type >

Aleph::SkipList< Key, Type >::SkipList ( const SkipList< Key, Type > & )

delete

◆ SkipList() [4/4]

template<class Key , class Type >

Aleph::SkipList< Key, Type >::SkipList ( SkipList< Key, Type > && other )

inlinenoexcept

Definition at line 301 of file tpl_skipList.H.

References Aleph::maps().

Member Function Documentation

◆ begin()

template<class Key , class Type >

Iterator Aleph::SkipList< Key, Type >::begin ( ) const

inlinenoexcept

Get iterator to first element.

Definition at line 617 of file tpl_skipList.H.

◆ checkSkipList()

template<class Key , class Type >

bool Aleph::SkipList< Key, Type >::checkSkipList ( ) const

inlinenoexcept

Verify skip list invariants (for debugging).

Returns: true if all keys are in ascending order.

Definition at line 457 of file tpl_skipList.H.

References Aleph::SkipList< Key, Type >::Node::get_key(), Aleph::SkipList< Key, Type >::Node::get_next(), and Aleph::SkipList< Key, Type >::header.

Referenced by Aleph::SkipList< Key, Type >::insert(), and Aleph::SkipList< Key, Type >::remove().

◆ end()

template<class Key , class Type >

Iterator Aleph::SkipList< Key, Type >::end ( ) const

inlinenoexcept

Get iterator past the last element.

Definition at line 620 of file tpl_skipList.H.

◆ generateRandomLevel()

template<class Key , class Type >

int Aleph::SkipList< Key, Type >::generateRandomLevel ( )

inlinenoexcept

Generate a random level for a new node.

Uses GSL Mersenne Twister for high-quality randomness.

Returns: Random level in range [1, maxLevel].

Definition at line 445 of file tpl_skipList.H.

References l, Aleph::maps(), Aleph::SkipList< Key, Type >::maxLevel, Aleph::SkipList< Key, Type >::probability, and Aleph::SkipList< Key, Type >::r.

◆ get_first()

template<class Key , class Type >

Node * Aleph::SkipList< Key, Type >::get_first ( )

inlinenoexcept

Get the first node in the list.

Returns: First node, or NullPtr if empty.

Definition at line 396 of file tpl_skipList.H.

References Aleph::SkipList< Key, Type >::headerPtr.

◆ gsl_rng_object()

template<class Key , class Type >

gsl_rng * Aleph::SkipList< Key, Type >::gsl_rng_object ( )

inlinenoexcept

Get a pointer to the GSL random number generator.

Definition at line 264 of file tpl_skipList.H.

References Aleph::SkipList< Key, Type >::r.

◆ init()

template<class Key , class Type >

void Aleph::SkipList< Key, Type >::init ( unsigned long seed )

inlineprivate

Definition at line 252 of file tpl_skipList.H.

References ah_bad_alloc_if, Aleph::maps(), and Aleph::SkipList< Key, Type >::r.

◆ insert()

template<class Key , class Type >

Node * Aleph::SkipList< Key, Type >::insert ( Node * p )

inlinenoexcept

Insert a node into the skip list.

Parameters

[in] p Node to insert (must be pre-allocated with correct level).

Returns: The inserted node.

Precondition: p->getLevel() > 0 and p->getLevel() <= maxLevel

Definition at line 356 of file tpl_skipList.H.

References Aleph::SkipList< Key, Type >::checkSkipList(), Aleph::SkipList< Key, Type >::Node::get_key(), Aleph::SkipList< Key, Type >::Node::getForward(), Aleph::SkipList< Key, Type >::Node::getLevel(), Aleph::SkipList< Key, Type >::headerPtr, Aleph::SkipList< Key, Type >::Node::level, Aleph::maps(), and Aleph::SkipList< Key, Type >::maxLevel.

◆ new_node()

template<class Key , class Type >

Node * Aleph::SkipList< Key, Type >::new_node ( )

inlinenoexcept

Placeholder for node allocation (override in derived classes).

Definition at line 473 of file tpl_skipList.H.

◆ operator=() [1/2]

template<class Key , class Type >

SkipList & Aleph::SkipList< Key, Type >::operator= ( const SkipList< Key, Type > & )

delete

◆ operator=() [2/2]

template<class Key , class Type >

SkipList & Aleph::SkipList< Key, Type >::operator= ( SkipList< Key, Type > && other )

inlinenoexcept

Definition at line 313 of file tpl_skipList.H.

References Aleph::SkipList< Key, Type >::header, Aleph::SkipList< Key, Type >::headerPtr, Aleph::SkipList< Key, Type >::Node::level, Aleph::maps(), Aleph::SkipList< Key, Type >::probability, and Aleph::SkipList< Key, Type >::r.

◆ remove()

template<class Key , class Type >

Node * Aleph::SkipList< Key, Type >::remove ( const Key & searchKey )

inlinenoexcept

Remove a key from the skip list.

Parameters

[in] searchKey Key to remove.

Returns: Pointer to removed node, or nullptr if not found.

Note: Caller is responsible for deallocating the returned node.

Definition at line 406 of file tpl_skipList.H.

References Aleph::SkipList< Key, Type >::checkSkipList(), Aleph::SkipList< Key, Type >::Node::get_key(), Aleph::SkipList< Key, Type >::Node::getForward(), Aleph::SkipList< Key, Type >::Node::getForward(), Aleph::SkipList< Key, Type >::HeaderNode::getForward(), Aleph::SkipList< Key, Type >::headerPtr, Aleph::SkipList< Key, Type >::Node::level, Aleph::maps(), and Aleph::SkipList< Key, Type >::maxLevel.

◆ search()

template<class Key , class Type >

Node * Aleph::SkipList< Key, Type >::search ( const Key & searchKey )

inlinenoexcept

Search for a key in the skip list.

Parameters

[in] searchKey Key to search for.

Returns: Pointer to node containing the key, or nullptr if not found.

Definition at line 334 of file tpl_skipList.H.

References Aleph::SkipList< Key, Type >::Node::get_key(), Aleph::SkipList< Key, Type >::Node::getForward(), Aleph::SkipList< Key, Type >::headerPtr, Aleph::SkipList< Key, Type >::Node::level, and Aleph::maps().

◆ set_seed()

template<class Key , class Type >

void Aleph::SkipList< Key, Type >::set_seed ( unsigned long seed )

inlinenoexcept

Set the random number generator seed.

Definition at line 261 of file tpl_skipList.H.

References Aleph::maps(), and Aleph::SkipList< Key, Type >::r.

Member Data Documentation

◆ defaultProbability

template<class Key , class Type >

const double Aleph::SkipList< Key, Type >::defaultProbability = 0.5

static

Default probability for level generation (0.5 = geometric distribution)

Definition at line 100 of file tpl_skipList.H.

◆ header

template<class Key , class Type >

HeaderNode Aleph::SkipList< Key, Type >::header

private

Definition at line 245 of file tpl_skipList.H.

Referenced by Aleph::SkipList< Key, Type >::checkSkipList(), and Aleph::SkipList< Key, Type >::operator=().

◆ headerPtr

template<class Key , class Type >

HeaderNode* Aleph::SkipList< Key, Type >::headerPtr

private

Definition at line 246 of file tpl_skipList.H.

Referenced by Aleph::SkipList< Key, Type >::get_first(), Aleph::SkipList< Key, Type >::insert(), Aleph::SkipList< Key, Type >::operator=(), Aleph::SkipList< Key, Type >::remove(), Aleph::SkipList< Key, Type >::Iterator::reset_first(), and Aleph::SkipList< Key, Type >::search().

◆ level

template<class Key , class Type >

int Aleph::SkipList< Key, Type >::level

private

Definition at line 249 of file tpl_skipList.H.

◆ maxLevel

template<class Key , class Type >

const int Aleph::SkipList< Key, Type >::maxLevel = 32

static

Maximum level for any node (supports up to 2^32 elements efficiently)

Definition at line 97 of file tpl_skipList.H.

Referenced by Aleph::SkipList< Key, Type >::HeaderNode::HeaderNode(), Aleph::SkipList< Key, Type >::generateRandomLevel(), Aleph::SkipList< Key, Type >::insert(), and Aleph::SkipList< Key, Type >::remove().

◆ probability

template<class Key , class Type >

double Aleph::SkipList< Key, Type >::probability

private

Definition at line 248 of file tpl_skipList.H.

Referenced by Aleph::SkipList< Key, Type >::SkipList(), Aleph::SkipList< Key, Type >::generateRandomLevel(), and Aleph::SkipList< Key, Type >::operator=().

◆ r

template<class Key , class Type >

gsl_rng* Aleph::SkipList< Key, Type >::r

private

Definition at line 247 of file tpl_skipList.H.

Referenced by Aleph::SkipList< Key, Type >::~SkipList(), Aleph::SkipList< Key, Type >::generateRandomLevel(), Aleph::SkipList< Key, Type >::gsl_rng_object(), Aleph::SkipList< Key, Type >::init(), Aleph::SkipList< Key, Type >::operator=(), and Aleph::SkipList< Key, Type >::set_seed().

The documentation for this class was generated from the following file:

tpl_skipList.H

Classes

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ SkipList() [1/4]

◆ SkipList() [2/4]

◆ ~SkipList()

◆ SkipList() [3/4]

◆ SkipList() [4/4]

Member Function Documentation

◆ begin()

◆ checkSkipList()

◆ end()

◆ generateRandomLevel()

◆ get_first()

◆ gsl_rng_object()

◆ init()

◆ insert()

◆ new_node()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ remove()

◆ search()

◆ set_seed()

Member Data Documentation

◆ defaultProbability

◆ header

◆ headerPtr

◆ level

◆ maxLevel

◆ probability

◆ r