bdlcc::SkipList< KEY, DATA > Class Template Reference

#include <bdlcc_skiplist.h>

Classes
class	PairFactory
class	PairHandleFactory

Public Types
enum	{   e_SUCCESS = 0 , e_NOT_FOUND = 1 , e_DUPLICATE = 2 , e_INVALID = 3 ,   BCEC_SUCCESS = e_SUCCESS , BCEC_NOT_FOUND = e_NOT_FOUND , BCEC_DUPLICATE = e_DUPLICATE , BCEC_INVALID = e_INVALID ,   RET_SUCCESS = e_SUCCESS , RET_NOT_FOUND = e_NOT_FOUND , RET_DUPLICATE = e_DUPLICATE , RET_INVALID = e_INVALID }
typedef SkipListPair< KEY, DATA >	Pair
typedef SkipListPairHandle< KEY, DATA >	PairHandle

Public Member Functions
	BSLMF_NESTED_TRAIT_DECLARATION (SkipList, bslma::UsesBslmaAllocator)
	SkipList (bslma::Allocator *basicAllocator=0)
	SkipList (const SkipList &original, bslma::Allocator *basicAllocator=0)
	~SkipList ()
SkipList &	operator= (const SkipList &rhs)
void	releaseReferenceRaw (const Pair *reference)
void	add (const KEY &key, const DATA &data, bool *newFrontFlag=0)
void	add (PairHandle *result, const KEY &key, const DATA &data, bool *newFrontFlag=0)
void	addAtLevelRaw (Pair **result, int level, const KEY &key, const DATA &data, bool *newFrontFlag=0)
int	addAtLevelUniqueRaw (Pair **result, int level, const KEY &key, const DATA &data, bool *newFrontFlag=0)
void	addRaw (Pair **result, const KEY &key, const DATA &data, bool *newFrontFlag=0)
int	addUnique (const KEY &key, const DATA &data, bool *newFrontFlag=0)
int	addUnique (PairHandle *result, const KEY &key, const DATA &data, bool *newFrontFlag=0)
int	addUniqueRaw (Pair **result, const KEY &key, const DATA &data, bool *newFrontFlag=0)
void	addAtLevelRawR (Pair **result, int level, const KEY &key, const DATA &data, bool *newFrontFlag=0)
int	addAtLevelUniqueRawR (Pair **result, int level, const KEY &key, const DATA &data, bool *newFrontFlag=0)
void	addR (const KEY &key, const DATA &data, bool *newFrontFlag=0)
void	addR (PairHandle *result, const KEY &key, const DATA &data, bool *newFrontFlag=0)
void	addRawR (Pair **result, const KEY &key, const DATA &data, bool *newFrontFlag=0)
int	addUniqueR (const KEY &key, const DATA &data, bool *newFrontFlag=0)
int	addUniqueR (PairHandle *result, const KEY &key, const DATA &data, bool *newFrontFlag=0)
int	addUniqueRawR (Pair **result, const KEY &key, const DATA &data, bool *newFrontFlag=0)
int	popFront (PairHandle *item=0)
int	popFrontRaw (Pair **item)
int	remove (const Pair *reference)
int	removeAll ()
int	removeAll (bsl::vector< PairHandle > *removed)
int	removeAll (std::vector< PairHandle > *removed)
int	removeAllRaw (bsl::vector< Pair * > *removed)
int	removeAllRaw (std::vector< Pair * > *removed)
int	update (const Pair *reference, const KEY &newKey, bool *newFrontFlag=0, bool allowDuplicates=true)
int	updateR (const Pair *reference, const KEY &newKey, bool *newFrontFlag=0, bool allowDuplicates=true)
Pair *	addPairReferenceRaw (const Pair *reference) const
int	back (PairHandle *back) const
int	backRaw (Pair **back) const
bool	exists (const KEY &key) const
int	front (PairHandle *front) const
int	frontRaw (Pair **front) const
bool	isEmpty () const
	Return true if this list is empty, and false otherwise.
int	length () const
	Return the number of items in this list.
bsl::ostream &	print (bsl::ostream &stream, int level=0, int spacesPerLevel=4) const
int	find (PairHandle *item, const KEY &key) const
int	findRaw (Pair **item, const KEY &key) const
int	findR (PairHandle *item, const KEY &key) const
int	findRRaw (Pair **item, const KEY &key) const
int	findLowerBound (PairHandle *item, const KEY &key) const
int	findLowerBoundRaw (Pair **item, const KEY &key) const
int	findLowerBoundR (PairHandle *item, const KEY &key) const
int	findLowerBoundRRaw (Pair **item, const KEY &key) const
int	findUpperBound (PairHandle *item, const KEY &key) const
int	findUpperBoundRaw (Pair **item, const KEY &key) const
int	findUpperBoundR (PairHandle *item, const KEY &key) const
int	findUpperBoundRRaw (Pair **item, const KEY &key) const
int	next (PairHandle *next, const Pair *reference) const
int	nextRaw (Pair **next, const Pair *reference) const
int	previous (PairHandle *prevPair, const Pair *reference) const
int	previousRaw (Pair **prevPair, const Pair *reference) const
int	skipBackward (PairHandle *item) const
int	skipBackwardRaw (Pair **item) const
int	skipForward (PairHandle *item) const
int	skipForwardRaw (Pair **item) const
bslma::Allocator *	allocator () const
	Return the allocator used by this object to supply memory.

Static Public Member Functions
static int	level (const Pair *reference)

Friends
class	SkipListPair< KEY, DATA >
class	SkipListPairHandle< KEY, DATA >
template<class KEY2 , class DATA2 >
bool	operator== (const SkipList< KEY2, DATA2 > &, const SkipList< KEY2, DATA2 > &)
template<class KEY2 , class DATA2 >
bool	operator!= (const SkipList< KEY2, DATA2 > &, const SkipList< KEY2, DATA2 > &)

Detailed Description

template<class KEY, class DATA>
class bdlcc::SkipList< KEY, DATA >

This class provides a generic thread-safe Skip List (an ordered associative container). It supports an almost complete set of value semantic operations, including copy construction, assignment, equality comparison, and ostream printing (but not BDEX serialization).

See bdlcc_skiplist

Member Typedef Documentation

Pair

template<class KEY , class DATA >

typedef SkipListPair<KEY, DATA> bdlcc::SkipList< KEY, DATA >::Pair

PairHandle

template<class KEY , class DATA >

typedef SkipListPairHandle<KEY, DATA> bdlcc::SkipList< KEY, DATA >::PairHandle

Member Enumeration Documentation

anonymous enum

template<class KEY , class DATA >

anonymous enum

Enumerator
e_SUCCESS
e_NOT_FOUND
e_DUPLICATE
e_INVALID
BCEC_SUCCESS
BCEC_NOT_FOUND
BCEC_DUPLICATE
BCEC_INVALID
RET_SUCCESS
RET_NOT_FOUND
RET_DUPLICATE
RET_INVALID

Constructor & Destructor Documentation

SkipList() [1/2]

template<class KEY , class DATA >

bdlcc::SkipList< KEY, DATA >::SkipList ( bslma::Allocator *  basicAllocator = 0 )

explicit

Create a new Skip List. Optionally specify a basicAllocator used to supply memory. If basicAllocator is 0, the currently installed default allocator is used.

SkipList() [2/2]

template<class KEY , class DATA >

bdlcc::SkipList< KEY, DATA >::SkipList	(	const SkipList< KEY, DATA > &	original,
		bslma::Allocator *	basicAllocator = 0
	)

Create a new Skip List initialized to the value of the specified original list. Optionally specify a basicAllocator used to supply memory. If basicAllocator is 0, the currently installed default allocator is used.

~SkipList()

template<class KEY , class DATA >

bdlcc::SkipList< KEY, DATA >::~SkipList

(

)

Destroy this Skip List. The behavior is undefined if references are outstanding to any pairs in the list.

Member Function Documentation

add() [1/2]

template<class KEY , class DATA >

void bdlcc::SkipList< KEY, DATA >::add ( const KEY &  key, const DATA &  data, bool *  newFrontFlag = 0  )

inline

Add the specified key / data pair to this list. Load into the the optionally specified newFrontFlag a true value if the pair is at the front of the list, and a false value otherwise.

add() [2/2]

template<class KEY , class DATA >

void bdlcc::SkipList< KEY, DATA >::add ( PairHandle *  result, const KEY &  key, const DATA &  data, bool *  newFrontFlag = 0  )

inline

Add the specified key / data pair to this list, and load into the specified result a reference to the pair in the list. Load into the optionally specified newFrontFlag a true value if the pair is at the front of the list, and a false value otherwise.

addAtLevelRaw()

template<class KEY , class DATA >

void bdlcc::SkipList< KEY, DATA >::addAtLevelRaw ( Pair **  result, int  level, const KEY &  key, const DATA &  data, bool *  newFrontFlag = 0  )

inline

Add the specified key / data pair to this list at the specified level, and load into the specified result a reference to the pair in the list. The result reference must be released (using releaseReferenceRaw) when it is no longer needed. Load into the the optionally specified newFrontFlag a true value if the pair is at the front of the list, and a false value otherwise. The behavior is undefined if level is greater than the implementation-defined maximum level of this class, or if level is negative. Note that this method is provided for testing purposes.

addAtLevelRawR()

template<class KEY , class DATA >

void bdlcc::SkipList< KEY, DATA >::addAtLevelRawR ( Pair **  result, int  level, const KEY &  key, const DATA &  data, bool *  newFrontFlag = 0  )

inline

Add the specified key / data pair to this list at the specified level, and load into the specified result a reference to the pair in the list. Search for the correct position for key from the back of the list (in descending order by key value). The result reference must be released (using releaseReferenceRaw) when it is no longer needed. Load into the optionally specified newFrontFlag a true value if the pair is at the front of the list, and a false value otherwise. The behavior is undefined if level is greater than the implementation-defined maximum level of this class, or if level is negative. Note that this method is provided for testing purposes.

addAtLevelUniqueRaw()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::addAtLevelUniqueRaw	(	Pair **	result,
		int	level,
		const KEY &	key,
		const DATA &	data,
		bool *	newFrontFlag = 0
	)

Add the specified key / data pair to this list at the specified level, and load into the specified result a reference to the pair in the list. The result reference must be released (using releaseReferenceRaw) when it is no longer needed. Load into the the optionally specified newFrontFlag a true value if the pair is at the front of the list, and a false value otherwise. The behavior is undefined if level is greater than the implementation-defined maximum level of this class, or if level is negative. Return 0 on success, and a non-zero value (with no effect on the list) if key is already in the list. Note that this method is provided for testing purposes.

addAtLevelUniqueRawR()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::addAtLevelUniqueRawR	(	Pair **	result,
		int	level,
		const KEY &	key,
		const DATA &	data,
		bool *	newFrontFlag = 0
	)

Add the specified key / data pair to this list at the specified level, and load into the specified result a reference to the pair in the list. Search for the correct position for key from the back of the list (in descending order by key value). The result reference must be released (using releaseReferenceRaw) when it is no longer needed. Load into the optionally specified newFrontFlag a true value if the pair is at the front of the list, and a false value otherwise. The behavior is undefined if level is greater than the implementation-defined maximum level of this class, or if level is negative. Return 0 on success, and a non-zero value (with no effect on the list) if key is already in the list. Note that this method is provided for testing purposes.

addPairReferenceRaw()

template<class KEY , class DATA >

SkipListPair< KEY, DATA > * bdlcc::SkipList< KEY, DATA >::addPairReferenceRaw ( const Pair *  reference ) const

inline

Increment the reference count for the list element referred to by the specified reference. There must be a corresponding call to releaseReferenceRaw when the reference is no longer needed. The behavior is undefined item has already been released. Return reference.

addR() [1/2]

template<class KEY , class DATA >

void bdlcc::SkipList< KEY, DATA >::addR ( const KEY &  key, const DATA &  data, bool *  newFrontFlag = 0  )

inline

Add the specified key / data pair to this list. Search for the correct position for key from the back of the list (in descending order by key value). Load into the optionally specified newFrontFlag a true value if the pair is at the front of the list, and a false value otherwise.

addR() [2/2]

template<class KEY , class DATA >

void bdlcc::SkipList< KEY, DATA >::addR ( PairHandle *  result, const KEY &  key, const DATA &  data, bool *  newFrontFlag = 0  )

inline

Add the specified key / data pair to this list, and load into the specified result a reference to the pair in the list. Search for the correct position for key from the back of the list (in descending order by key value). Load into the optionally specified newFrontFlag a true value if the pair is at the front of the list, and a false value otherwise.

addRaw()

template<class KEY , class DATA >

void bdlcc::SkipList< KEY, DATA >::addRaw ( Pair **  result, const KEY &  key, const DATA &  data, bool *  newFrontFlag = 0  )

inline

Add the specified key / data pair to this list, and load into the specified result a reference to the pair in the list. The result reference must be released (using releaseReferenceRaw) when it is no longer needed. Load into the optionally specified newFrontFlag a true value if the pair is at the front of the list, and a false value otherwise.

addRawR()

template<class KEY , class DATA >

void bdlcc::SkipList< KEY, DATA >::addRawR ( Pair **  result, const KEY &  key, const DATA &  data, bool *  newFrontFlag = 0  )

inline

Add the specified key / data pair to this list, and load into the specified result a reference to the pair in the list. Search for the correct position for key from the back of the list (in descending order by key value). The result reference must be released (using releaseReferenceRaw) when it is no longer needed. Load into the optionally specified newFrontFlag a true value if the pair is at the front of the list, and a false value otherwise.

addUnique() [1/2]

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::addUnique ( const KEY &  key, const DATA &  data, bool *  newFrontFlag = 0  )

inline

Add the specified key / data pair to this list. Load into the the optionally specified newFrontFlag a true value if the pair is at the front of the list, and a false value otherwise. Return 0 on success, and a non-zero value (with no effect on the list) if key is already in the list.

addUnique() [2/2]

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::addUnique ( PairHandle *  result, const KEY &  key, const DATA &  data, bool *  newFrontFlag = 0  )

inline

Add the specified key / data pair to this list, and load into the specified result a reference to the pair in the list. Load into the optionally specified newFrontFlag a true value if the pair is at the front of the list, and a false value otherwise. Return 0 on success, and a non-zero value (with no effect on the list) if key is already in the list.

addUniqueR() [1/2]

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::addUniqueR ( const KEY &  key, const DATA &  data, bool *  newFrontFlag = 0  )

inline

Add the specified key / data pair to this list. Search for the correct position for key from the back of the list (in descending order by key value). Load into the optionally specified newFrontFlag a true value if the pair is at the front of the list, and a false value otherwise. Return 0 on success, and a non-zero value (with no effect on the list) if key is already in the list.

addUniqueR() [2/2]

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::addUniqueR	(	PairHandle *	result,
		const KEY &	key,
		const DATA &	data,
		bool *	newFrontFlag = 0
	)

Add the specified key / data pair to this list, and load into the specified result a reference to the pair in the list. Search for the correct position for key from the back of the list (in descending order by key value). Load into the optionally specified newFrontFlag a true value if the pair is at the front of the list, and a false value otherwise. Return 0 on success, and a non-zero value (with no effect on the list) if key is already in the list.

addUniqueRaw()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::addUniqueRaw ( Pair **  result, const KEY &  key, const DATA &  data, bool *  newFrontFlag = 0  )

inline

Add the specified key / data pair to this list, and load into the specified result a reference to the pair in the list. The result reference must be released (using releaseReferenceRaw) when it is no longer needed. Load into the optionally specified newFrontFlag a true value if the pair is at the front of the list, and a false value otherwise. Return 0 on success, and a non-zero value (with no effect on the list) if key is already in the list.

addUniqueRawR()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::addUniqueRawR ( Pair **  result, const KEY &  key, const DATA &  data, bool *  newFrontFlag = 0  )

inline

Add the specified key / data pair to this list, and load into the specified result a reference to the pair in the list. Search for the correct position for key from the back of the list (in descending order by key value). The result reference must be released (using releaseReferenceRaw) when it is no longer needed. Load into the optionally specified newFrontFlag a true value if the pair is at the front of the list, and a false value otherwise. Return 0 on success, and a non-zero value (with no effect on the list) if key is already in the list.

allocator()

template<class KEY , class DATA >

bslma::Allocator * bdlcc::SkipList< KEY, DATA >::allocator ( ) const

inline

back()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::back ( PairHandle *  back ) const

inline

Load into the specified back a reference to the last item in the list. Return 0 on success, and a non-zero value (with no effect on back) if the list is empty.

backRaw()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::backRaw ( Pair **  back ) const

inline

Load into the specified back a reference to the last item in the list. The back reference must be released (using releaseReferenceRaw) when it is no longer needed. Return 0 on success, and a non-zero value if the list is empty. Note that if the list is empty, the value of *back is undefined.

BSLMF_NESTED_TRAIT_DECLARATION()

template<class KEY , class DATA >

bdlcc::SkipList< KEY, DATA >::BSLMF_NESTED_TRAIT_DECLARATION	(	SkipList< KEY, DATA >	,
		bslma::UsesBslmaAllocator
	)

exists()

template<class KEY , class DATA >

bool bdlcc::SkipList< KEY, DATA >::exists

(

const KEY &

key

)

const

Return true if there is a pair in the list with the specified key, and false otherwise.

find()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::find ( PairHandle *  item, const KEY &  key  ) const

inline

Load into the specified item a reference to the element in this list with the specified key found by searching the list from the front (in ascending order of key value). If multiple elements having key are in the container, load item with the first matching element. Return 0 on success, and a non-zero value (with no effect on item) if no such element exists. If there are multiple elements in the list with the key, it is undefined which one is returned.

findLowerBound()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::findLowerBound ( PairHandle *  item, const KEY &  key  ) const

inline

Load into the specified item a reference to the first element in this list whose key value is not less than the specified key found by searching the list from the front (in ascending order of key value). Return 0 on success, and a non-zero value (with no effect on item) if no such element exists.

findLowerBoundR()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::findLowerBoundR ( PairHandle *  item, const KEY &  key  ) const

inline

Load into the specified item a reference to the first element in this list whose key value is not less than the specified key found by searching the list from the back (in descending order of key value). Return 0 on success, and a non-zero value (with no effect on item) if no such element exists.

findLowerBoundRaw()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::findLowerBoundRaw ( Pair **  item, const KEY &  key  ) const

inline

Load into the specified item a reference to the first element in this list whose key value is not less than the specified key found by searching the list from the front (in ascending order of key value). Return 0 on success, and a non-zero value (with no effect on item) if no such element exists. The item reference must be released (using releaseReferenceRaw) when it is no longer needed.

findLowerBoundRRaw()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::findLowerBoundRRaw ( Pair **  item, const KEY &  key  ) const

inline

Load into the specified item a reference to the first element in this list whose key value is not less than the specified key found by searching the list from the back (in descending order of key value). Return 0 on success, and a non-zero value (with no effect on item) if no such element exists. The item reference must be released (using releaseReferenceRaw) when it is no longer needed.

findR()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::findR ( PairHandle *  item, const KEY &  key  ) const

inline

Load into the specified item a reference to the element in this list with the specified key found by searching the list from the back (in descending order of key value). If multiple elements having key are in the container, load item with the last matching element. key are present, find the last one. Return 0 on success, and a non-zero value (with no effect on item) if no such element exists. If there are multiple elements in the list with the key, it is undefined which one is returned.

findRaw()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::findRaw ( Pair **  item, const KEY &  key  ) const

inline

Load into the specified item a reference to the element in this list with the specified key found by searching the list from the front (in ascending order of key value). Return 0 on success, and a non-zero value (with no effect on item) if no such element exists. If there are multiple elements in the list with the key, it is undefined which one is returned. The item reference must be released (using releaseReferenceRaw) when it is no longer needed.

findRRaw()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::findRRaw ( Pair **  item, const KEY &  key  ) const

inline

Load into the specified item a reference to the element in this list with the specified key found by searching the list from the back (in descending order of key value). Return 0 on success, and a non-zero value (with no effect on item) if no such element exists. If there are multiple elements in the list with the key, it is undefined which one is returned. The item reference must be released (using releaseReferenceRaw) when it is no longer needed.

findUpperBound()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::findUpperBound ( PairHandle *  item, const KEY &  key  ) const

inline

Load into the specified item a reference to the first element in this list whose key value is greater than the specified key found by searching the list from the front (in ascending order of key value). Return 0 on success, and a non-zero value (with no effect on item) if no such element exists.

findUpperBoundR()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::findUpperBoundR ( PairHandle *  item, const KEY &  key  ) const

inline

Load into the specified item a reference to the first element in this list whose key value is greater than the specified key found by searching the list from the back (in descending order of key value). Return 0 on success, and a non-zero value (with no effect on item) if no such element exists.

findUpperBoundRaw()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::findUpperBoundRaw ( Pair **  item, const KEY &  key  ) const

inline

Load into the specified item a reference to the first element in this list whose key value is greater than the specified key found by searching the list from the front (in ascending order of key value). Return 0 on success, and a non-zero value (with no effect on item) if no such element exists. The item reference must be released (using releaseReferenceRaw) when it is no longer needed.

findUpperBoundRRaw()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::findUpperBoundRRaw ( Pair **  item, const KEY &  key  ) const

inline

Load into the specified item a reference to the first element in this list whose key value is greater than the specified key found by searching the list from the back (in descending order of key value). Return 0 on success, and a non-zero value (with no effect on item) if no such element exists. The item reference must be released (using releaseReferenceRaw) when it is no longer needed.

front()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::front ( PairHandle *  front ) const

inline

Load into the specified front a reference to the first item in the list. Return 0 on success, and a non-zero value (with no effect on front) if the list is empty.

frontRaw()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::frontRaw ( Pair **  front ) const

inline

Load into the specified front a reference to the first item in the list. The front reference must be released (using releaseReferenceRaw) when it is no longer needed. Return 0 on success, and a non-zero value if the list is empty.

isEmpty()

template<class KEY , class DATA >

bool bdlcc::SkipList< KEY, DATA >::isEmpty ( ) const

inline

length()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::length ( ) const

inline

level()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::level ( const Pair *  reference )

inlinestatic

Return the level of the pair identified by the specified reference. This method is provided for testing.

next()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::next ( PairHandle *  next, const Pair *  reference  ) const

inline

Load into the specified next a reference to the item that appears in the list after the item identified by the specified reference. Return 0 on success, or a non-zero value if reference refers to the back of the list.

nextRaw()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::nextRaw ( Pair **  next, const Pair *  reference  ) const

inline

Load into the specified next a reference to the item that appears in the list after the item identified by the specified reference. The next reference must be released (using releaseReferenceRaw) when it is no longer needed. Return 0 on success, or a non-zero value if reference refers to the back of the list.

operator=()

template<class KEY , class DATA >

SkipList< KEY, DATA > & bdlcc::SkipList< KEY, DATA >::operator=

(

const SkipList< KEY, DATA > &

rhs

)

Assign to this Skip List the value of the specified rhs list and return a reference to the modifiable list.

popFront()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::popFront ( PairHandle *  item = 0 )

inline

Remove the first item from the list and load a reference to it into the optionally specified item. Return 0 on success, and a non-zero value if the list is empty.

popFrontRaw()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::popFrontRaw ( Pair **  item )

inline

Remove the first item from the list and load a reference to it into the specified item. This reference must be released (using releaseReferenceRaw) when it is no longer needed. Return 0 on success, and a non-zero value if the list is empty.

previous()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::previous ( PairHandle *  prevPair, const Pair *  reference  ) const

inline

Load into the specified prevPair a reference to the pair that appears in the list before the pair identified by the specified reference. Return 0 on success, or a non-zero value if reference refers to the front of the list.

previousRaw()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::previousRaw ( Pair **  prevPair, const Pair *  reference  ) const

inline

Load into the specified prevPair a reference to the pair that appears in the list before the pair identified by the specified reference. The prevPair reference must be released (using releaseReferenceRaw) when it is no longer needed. Return 0 on success, or a non-zero value if reference refers to the front of the list.

print()

template<class KEY , class DATA >

bsl::ostream & bdlcc::SkipList< KEY, DATA >::print	(	bsl::ostream &	stream,
		int	level = 0,
		int	spacesPerLevel = 4
	)		const

Format this list object to the specified output stream at the (absolute value of) the optionally specified indentation level and return a reference to stream. If level is specified, optionally specify spacesPerLevel, the number of spaces per indentation level for this and all of its nested objects. If level is negative, suppress indentation of the first line. If spacesPerLevel is negative, suppress all indentation AND format the entire output on one line. If stream is not valid on entry, this operation has no effect.

releaseReferenceRaw()

template<class KEY , class DATA >

void bdlcc::SkipList< KEY, DATA >::releaseReferenceRaw ( const Pair *  reference )

inline

Release the specified reference. After calling this method, the value of reference must not be used or released again.

remove()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::remove ( const Pair *  reference )

inline

Remove the item identified by the specified reference from the list. Return 0 on success, and a non-zero value if the pair has already been removed from the list.

removeAll() [1/3]

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::removeAll ( )

inline

removeAll() [2/3]

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::removeAll ( bsl::vector< PairHandle > *  removed )

inline

removeAll() [3/3]

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::removeAll ( std::vector< PairHandle > *  removed )

inline

Remove all items from this list. Optionally specify removed, a vector to which to append handles to the removed nodes. The items appended to removed will be in ascending order by key value. Return the number of items that were removed from this list. Note that all references in removed must be released (i.e., destroyed) before this skip list is destroyed. Note that if removed is not specified, all removed elements will be released by this method.

removeAllRaw() [1/2]

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::removeAllRaw ( bsl::vector< Pair * > *  removed )

inline

removeAllRaw() [2/2]

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::removeAllRaw ( std::vector< Pair * > *  removed )

inline

Remove all items from this list. Append to the specified removed vector pointers that can be used to refer to the removed items. Each such pointer must be released (using releaseReferenceRaw) when it is no longer needed. The pairs appended to removed will be in ascending order by key value. Return the number of items that were removed from this list.

skipBackward()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::skipBackward ( PairHandle *  item ) const

inline

If the item identified by the specified item is not at the front of the list, load a reference to the previous item in the list into item; otherwise reset the value of item. Return 0 on success, and e_NOT_FOUND (with no effect on the value of item) if item is no longer in the list.

skipBackwardRaw()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::skipBackwardRaw ( Pair **  item ) const

inline

If the item identified by the specified item is not at the front of the list, load a reference to the previous item in the list into item; otherwise reset the value of item. Return 0 on success, and e_NOT_FOUND (with no effect on the value of item) if item is no longer in the list.

skipForward()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::skipForward ( PairHandle *  item ) const

inline

If the item identified by the specified item is not at the end of the list, load a reference to the next item in the list into item; otherwise reset the value of item. Return 0 on success, and e_NOT_FOUND (with no effect on the value of item) if item is no longer in the list.

skipForwardRaw()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::skipForwardRaw ( Pair **  item ) const

inline

If the item identified by the specified item is not at the end of the list, load a reference to the next item in the list into item; otherwise reset the value of item. Return 0 on success, and e_NOT_FOUND (with no effect on the value of item) if item is no longer in the list.

update()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::update ( const Pair *  reference, const KEY &  newKey, bool *  newFrontFlag = 0, bool  allowDuplicates = true  )

inline

Assign the specified newKey value to the pair identified by the specified reference, moving the pair within the list as necessary. Load into the optionally specified newFrontFlag a true value if the new location of the pair is the front of the list. Return 0 on success, e_NOT_FOUND if the pair referred to by reference is no longer in the list, or e_DUPLICATE if the optionally specified allowDuplicates is false and newKey already appears in the list.

updateR()

template<class KEY , class DATA >

int bdlcc::SkipList< KEY, DATA >::updateR ( const Pair *  reference, const KEY &  newKey, bool *  newFrontFlag = 0, bool  allowDuplicates = true  )

inline

Assign the specified newKey value to the pair identified by the specified reference, moving the pair within the list as necessary. Search for the new position from the back of the list (in descending order by key value). Load into the optionally specified newFrontFlag a true value if the new location of the pair is the front of the list. Return 0 on success, e_NOT_FOUND if the pair referred to by reference is no longer in the list, or e_DUPLICATE if the optionally specified allowDuplicates is false and newKey already appears in the list.

Friends And Related Symbol Documentation

operator!=

template<class KEY , class DATA >

template<class KEY2 , class DATA2 >

bool operator!= ( const SkipList< KEY2, DATA2 > &  , const SkipList< KEY2, DATA2 > &    )

friend

operator==

template<class KEY , class DATA >

template<class KEY2 , class DATA2 >

bool operator== ( const SkipList< KEY2, DATA2 > &  , const SkipList< KEY2, DATA2 > &    )

friend

SkipListPair< KEY, DATA >

template<class KEY , class DATA >

friend class SkipListPair< KEY, DATA >

friend

SkipListPairHandle< KEY, DATA >

template<class KEY , class DATA >

friend class SkipListPairHandle< KEY, DATA >

friend

---

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

• bdlcc_skiplist.h