Internal (routing) node holding separator keys and child pointers.

Synopsis

Declared in <folly/ConcurrentBSkipList‐detail.h>

template<typename Traits>
class BSkipNodeInternal
    : public BSkipNode<Traits>

Base Classes

Name

Description

BSkipNode<Traits>

Common base of leaf and internal nodes: next pointer, seqlock, and mutex.

Types

Name

Description

InternalSearchResult

Result of an internal node child search.

Type Aliases

Name

Description

KeyArray

Array of separator key slots.

KeyStorage

The key slot storage type.

Seq

The seqlock type used to bracket concurrent access.

T

The key type.

Member Functions

Name

Description

BSkipNodeInternal [constructor]

Constructs an internal node and registers its arrays with the thread sanitizer.

findChild

Finds the child to descend into for a search key.

insertChildAtSlot

Shifts children right and writes a child pointer at the given slot.

insertKeyAtSlot

Shifts separator keys right and writes a key at the given slot.

loadNextMinKey

Loads the minimum key of the successor node.

minKey

Returns this node's minimum routing key.

splitKeysAndChildren

Moves the tail of this node's keys and children into a destination node.

Protected Member Functions

Name

Description

annotateBaseRaces

Registers the node's shared fields with the thread sanitizer as benign races.

Protected Data Members

Name

Description

level_

Node level; set once at allocation and immutable thereafter.

mutex_

Shared/exclusive mutex guarding locked‐path access.

nextMinKey_

Cached minimum key of the successor node.

next_

Pointer to the next node at this level; readers pair load(acquire) with the release in publishSplitSibling.

numElements_

Number of live elements in this node.

seq_

Seqlock bracketing optimistic reads of this node.

Friends

Name

Description

folly::ConcurrentBSkipList

Concurrent B‐skip‐list container; declared here for friend declarations.

Template Parameters

Name

Description

Traits

The InternalTraits for the list.

Created with MrDocs