XData< size_type, difference_type, node_type, value_type, N, S, R > Class Template Reference

Shared data for use with XBidiCompositeSkipList and its internal containers. More...

#include <CSCompositeSkipList.h>

List of all members.

Public Types
typedef XTmpContainer < size_type, node_type >	tmp_container_type
	Temporary container type for cut and splice.
Public Member Functions
void	InitData ()
	Custom multilists must call this after setting the Containers[] array in their constructors.
unsigned int	getListCount () const
	Total number of internal containers.
unsigned int	getIndexCount () const
	Index of first non-indexed sorted internal container.
node_type *	Alloc (unsigned int level, const value_type &obj)
	Allocate a node and copy object. O(1)
node_type *	Alloc (unsigned int level)
	Allocate a dummy node. O(1)
void	Free (node_type *item)
	Delete a node. O(1)
unsigned int	GenerateRandomLevel () const
	Generate random level number. O(1)
void	adjust_levels ()
	Makes sure to reduce the internal number of levels. O(1C)
void	scan (node_type *nodex, unsigned int x) const
	Scan by node. O(logn)
void	erase (node_type *node)
	Erase node from all internal containers. O(m)
	XData ()
	Default constructor O(1)
	~XData ()
	Destructor O(m)
Public Attributes
R	rng
	Random number generator to specify level number of new nodes.
unsigned int	maxLevel
	Maximum number of levels possible for forward pointers.
unsigned int	level
	The maximum number of levels for forward pointers currently in use on any given node.
node_type *	head
	Start node.
node_type *	tail
	End node.
double	probability
	Probability to go to the next level.
size_type	items
	Number of items in the list.
size_type	scan_index [N]
	Cache index.
std::pair< size_type, node_type * > *	update [N]
	Cache.
XList< value_type, node_type > *	Containers [N]
	Array of internal containers.
tmp_container_type *	tmp_container
	Temporary container.

---

Detailed Description

template<class size_type, class difference_type, class node_type, class value_type, unsigned int N, unsigned int S, class R>
class XData< size_type, difference_type, node_type, value_type, N, S, R >

Shared data for use with XBidiCompositeSkipList and its internal containers.

All internal containers of the multilist must share the same nodes and elements. Therefore, a common shared class XData stores all the nodes and elements where each internal container is assigned an index into the container array.

Internal containers must appear in the following order.

• XIndexedSkipList
• XMultiAutoSkipList
• XMultiSkipList

Template Parameters:

size_type	Type for unsigned variables relating to sizes.
size_type	Type for signed variables relating to distances.
node_type	Type for internal nodes that contain elements.
value_type	Type of object stored as an element in the container.
N	The total number of internal containers.
S	The index of the first non-indexed, sorted container.
R	The type for the random number generator.

---

Constructor & Destructor Documentation

template<class size_type , class difference_type , class node_type , class value_type , unsigned int N, unsigned int S, class R >

XData< size_type, difference_type, node_type, value_type, N, S, R >::~XData

(

)

[inline]

Destructor O(m)

Deletes start and end nodes. Does not delete any remaining elements in the list. Multilist container such as XBidiCompositeSkipList will do that.

Deletes the cache array for each of the m internal containers.

Deletes the internal temporary container if allocated.

---

Member Function Documentation

template<class size_type , class difference_type , class node_type , class value_type , unsigned int N, unsigned int S, class R >

node_type* XData< size_type, difference_type, node_type, value_type, N, S, R >::Alloc	(	unsigned int	level,
		const value_type &	obj
	)		[inline]

Allocate a node and copy object. O(1)

Parameters:

level	Number of levels for this node.
obj	Object to store in this node.

Returns:

The allocated node.

template<class size_type , class difference_type , class node_type , class value_type , unsigned int N, unsigned int S, class R >

node_type* XData< size_type, difference_type, node_type, value_type, N, S, R >::Alloc

(

unsigned int

level

)

[inline]

Allocate a dummy node. O(1)

Parameters:

level

Number of levels for this node.

Returns:

The allocated node.

template<class size_type , class difference_type , class node_type , class value_type , unsigned int N, unsigned int S, class R >

void XData< size_type, difference_type, node_type, value_type, N, S, R >::Free

(

node_type *

item

)

[inline]

Delete a node. O(1)

Parameters:

item	Node to delete.

template<class size_type , class difference_type , class node_type , class value_type , unsigned int N, unsigned int S, class R >

unsigned int XData< size_type, difference_type, node_type, value_type, N, S, R >::GenerateRandomLevel

(

)

const [inline]

Generate random level number. O(1)

Returns:

Random level number.

template<class size_type , class difference_type , class node_type , class value_type , unsigned int N, unsigned int S, class R >

void XData< size_type, difference_type, node_type, value_type, N, S, R >::scan	(	node_type *	nodex,
		unsigned int	x
	)		const [inline]

Scan by node. O(logn)

This will update the cache so that all levels point to the item just before nodex. This allows the list to be updated.

Parameters:

nodex	Node to search.
x	The index of the internal container to search in.

template<class size_type , class difference_type , class node_type , class value_type , unsigned int N, unsigned int S, class R >

void XData< size_type, difference_type, node_type, value_type, N, S, R >::erase

(

node_type *

node

)

[inline]

Erase node from all internal containers. O(m)

Parameters:

node	Node to erase.

---

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

• CSCompositeSkipList.h