Skip List container implementation. More...

#include <skipList.h>

Collaboration diagram for original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >:

Classes
class	Iterator
	Forward iterator for skipList. More...

class	skipListNode
	Internal node class for Skip List. More...

Protected Types
using	rebind_alloc_node = typename ALLOC::template rebind_alloc<skipListNode>
	Rebound allocator for nodes.

using	rebind_alloc_pointer = typename ALLOC::template rebind_alloc<skipListNode*>
	Rebound allocator for pointers.

Protected Member Functions
skipListNode *	createNode (const K_TYPE &key=K_TYPE{}, const V_TYPE &value=V_TYPE{}, u_integer levels=1, std::initializer_list< skipListNode * > next={}) const
	Creates a new node with given parameters.

void	destroyNode (skipListNode *node) const
	Destroys a node and deallocates memory.

bool	highPriority (skipListNode cur, skipListNode next) const
	Compares priority between two nodes.

bool	highPriority (const K_TYPE &key, skipListNode *next) const
	Compares priority between a key and a node.

u_integer	getRandomLevels ()
	Generates random number of levels for new node.

u_integer	getCurLevels () const
	Gets current number of levels in list.

void	expandCurLevels (u_integer new_levels)
	Expands list to more levels.

void	shrinkCurLevels (u_integer new_levels)
	Shrinks list to fewer levels.

skipListNode *	listCopy () const
	Creates a deep copy of the list.

skipListNode *	findLastNode () const
	Finds last node in list.

	skipList (Compare compare=Compare{})
	Constructs skipList with given comparison function.

skipListNode *	find (const K_TYPE &key) const
	Finds node with given key.

bool	modify (const K_TYPE &key, const V_TYPE &value)
	Modifies value for existing key.

bool	insert (const K_TYPE &key, const V_TYPE &value)
	Inserts new key-value pair.

bool	erase (const K_TYPE &key)
	Erases node with given key.

void	listDestroy () noexcept
	Destroys entire list and deallocates all nodes.

	~skipList ()
	Destructor.

Static Protected Member Functions
static bool	equal (const K_TYPE &key, skipListNode *next)
	Checks if key matches node's key.

Protected Attributes
u_integer	size_
	Number of elements.

skipListNode *	head_
	Head node pointer.

Compare	compare_
	Comparison function.

rebind_alloc_node	rebind_alloc {}
	Node allocator.

std::mt19937	gen_ {std::random_device{}()}
	Random number generator.

std::uniform_real_distribution< floating >	dis_ {0.0, 1.0}
	Uniform distribution for level generation.

friend	Iterator

Detailed Description

template<typename K_TYPE, typename V_TYPE, typename ALLOC = allocator<K_TYPE>, typename Compare = increaseComparator<K_TYPE>>
class original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >

Skip List container implementation.

Template Parameters

K_TYPE	Key type (must be comparable)
V_TYPE	Value type
ALLOC	Allocator type (default: allocator<K_TYPE>)
Compare	Comparison function type (default: increaseComparator<K_TYPE>)

This class provides a probabilistic alternative to balanced trees with:

Expected O(log n) search/insert/delete operations
Multi-level linked list structure
Custom comparator support
STL-style allocator support

Constructor & Destructor Documentation

◆ skipList()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::skipList ( Compare compare = Compare{} )

explicitprotected

Constructs skipList with given comparison function.

Parameters

compare Comparison function to use

◆ ~skipList()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::~skipList ( )

protected

Destructor.

Cleans up all list nodes and allocated memory

Member Function Documentation

◆ createNode()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::skipListNode * original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::createNode	(	const K_TYPE &	key = K_TYPE{},
		const V_TYPE &	value = V_TYPE{},
		u_integer	levels = 1,
		std::initializer_list< skipListNode * >	next = {} ) const

protected

Creates a new node with given parameters.

Parameters

key	Key for new node
value	Value for new node
levels	Number of levels for new node
next	Initializer list of next pointers

Returns: Pointer to newly created node

Uses allocator to construct node in place

◆ destroyNode()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

void original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::destroyNode ( skipListNode * node ) const

protected

Destroys a node and deallocates memory.

Parameters

node	Node to destroy

Uses allocator to destroy and deallocate node

◆ equal()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

bool original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::equal	(	const K_TYPE &	key,
		skipListNode *	next )

staticprotected

Checks if key matches node's key.

Parameters

key	Key to compare
next	Node to compare

Returns: true if key matches node's key

◆ erase()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

bool original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::erase ( const K_TYPE & key )

protected

Erases node with given key.

Parameters

key	Key to erase

Returns: true if key was found and erased

Automatically adjusts list levels if needed

◆ expandCurLevels()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

void original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::expandCurLevels ( original::u_integer new_levels )

protected

Expands list to more levels.

Parameters

new_levels New total number of levels

◆ find()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::skipListNode * original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::find ( const K_TYPE & key ) const

protected

Finds node with given key.

Parameters

key	Key to search for

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

Uses multi-level search for efficiency

◆ findLastNode()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::skipListNode * original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::findLastNode ( ) const

protected

Finds last node in list.

Returns: Pointer to last node

◆ getCurLevels()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::u_integer original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::getCurLevels ( ) const

protected

Gets current number of levels in list.

Returns: Current maximum number of levels

◆ getRandomLevels()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::u_integer original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::getRandomLevels ( )

protected

Generates random number of levels for new node.

Returns: Random number of levels (geometric distribution)

◆ highPriority() [1/2]

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

bool original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::highPriority	(	const K_TYPE &	key,
		skipListNode *	next ) const

protected

Compares priority between a key and a node.

Parameters

key	Key to compare
next	Node to compare

Returns: true if key has higher priority than node's key

Uses the list's comparison function

◆ highPriority() [2/2]

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

bool original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::highPriority	(	skipListNode *	cur,
		skipListNode *	next ) const

protected

Compares priority between two nodes.

Parameters

cur	First node to compare
next	Second node to compare

Returns: true if cur has higher priority than next

Uses the list's comparison function

◆ insert()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

bool original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::insert	(	const K_TYPE &	key,
		const V_TYPE &	value )

protected

Inserts new key-value pair.

Parameters

key	Key to insert
value	Value to insert

Returns: true if inserted, false if key already existed

Automatically adjusts node levels probabilistically

◆ listCopy()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::skipListNode * original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::listCopy ( ) const

protected

Creates a deep copy of the list.

Returns: Pointer to head of copied list

◆ listDestroy()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

void original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::listDestroy ( )

protectednoexcept

Destroys entire list and deallocates all nodes.

Uses sequential traversal to destroy all nodes

◆ modify()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

bool original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::modify	(	const K_TYPE &	key,
		const V_TYPE &	value )

protected

Modifies value for existing key.

Parameters

key	Key to modify
value	New value to set

Returns: true if key was found and modified

◆ shrinkCurLevels()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

void original::skipList< K_TYPE, V_TYPE, ALLOC, Compare >::shrinkCurLevels ( original::u_integer new_levels )

protected

Shrinks list to fewer levels.

Parameters

new_levels New total number of levels

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

src/core/skipList.h

Classes

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ skipList()

◆ ~skipList()

Member Function Documentation

◆ createNode()

◆ destroyNode()

◆ equal()

◆ erase()

◆ expandCurLevels()

◆ find()

◆ findLastNode()

◆ getCurLevels()

◆ getRandomLevels()

◆ highPriority() [1/2]

◆ highPriority() [2/2]

◆ insert()

◆ listCopy()

◆ listDestroy()

◆ modify()

◆ shrinkCurLevels()