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).

Synopsis

Declared in <bdlcc_skiplist.h>

template<
    class KEY,
    class DATA>
class SkipList;

Type Aliases

Name

Description

Pair

Unmanaged reference to a key/data pair in this list.

PairHandle

Managed handle to a key/data pair in this list.

Enums

Name

Description

Unnamed enum

Status codes returned by skip‐list operations.

Member Functions

Name

Description

SkipList [constructor]

Constructors

~SkipList [destructor]

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

operator=

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

add

add overloads

addAtLevelRaw

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

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

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

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

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

addR overloads

addRaw

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

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

addUnique overloads

addUniqueR

addUniqueR overloads

addUniqueRaw

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

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

Return the allocator used by this object to supply memory.

back

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

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.

data

Load into the specified value the "data" value of the pair identified by the reference.

exists

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

find

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

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

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.

findLowerBoundRRaw

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.

findLowerBoundRaw

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.

findR

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.

findRRaw

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.

findRaw

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.

findUpperBound

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

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.

findUpperBoundRRaw

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.

findUpperBoundRaw

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.

front

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

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

Return true if this list is empty, and false otherwise.

key

Load into the specified value the "key" value of the pair identified by the reference.

length

Return the number of items in this list.

next

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

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.

popFront

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

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

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

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

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

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

remove

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

removeAll overloads

removeAllRaw

removeAllRaw overloads

skipBackward

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

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

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

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

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

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.

operator BloombergLP::bslmf::NestedTraitDeclaration<SkipList, UsesBslmaAllocator>

Declare that this type uses a bslma allocator.

Static Member Functions

Name

Description

level

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

Specializations

Name

Description

SkipList<long long, EventData>

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).

SkipList<long long, RecurringEventData>

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).

Friends

Name

Description

BloombergLP::bdlcc::operator!=

Return true if the specified lists have different values.

BloombergLP::bdlcc::operator==

Return true if the specified lists have the same value.

BloombergLP::bdlcc::SkipListPairHandle

Objects of this class refer to an association (pair) in a SkipList. A bdlcc::SkipListPairHandle is implicitly convertible to a const Pair* and thus may be used anywhere in the SkipList API that a const Pair* is expected.

BloombergLP::bdlcc::SkipListPair

Pointers to objects of this class are used in the "raw" API of SkipList; however, objects of the class are never constructed as the class serves only to provide type‐safe pointers.

Non-Member Functions

Name

Description

operator!=

Return true if the specified lhs list list has a different value from the specified rhs list, and false otherwise. Two lists A and B have different values if they have a different of elements, or if there exists an i in the range [0, numberOfElements) such that the i'th pair from the] front of A differs in key or data values from i'th pair from the front of B.

operator==

Return true if the specified lhs list has the same value as the specified rhs list, and false otherwise. Two lists A and B have the same value if they have the same number of elements, and if for all i in the range [0, numberOfElements), the i'th pair from the front of A has the] same key and data values as the i'th pair from the front of B. Note that if there are duplicate key values in a list, the order of iteration over those pairs may be different than for another list that was constructed from the same sequence of values (and thus the lists may not compare equal).

Created with MrDocs