Leaf node holding sorted keys, optional payloads, and tombstone bits.

Synopsis

Declared in <folly/ConcurrentBSkipList‐detail.h>

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

Base Classes

Name

Description

BSkipNode<Traits>

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

Types

Name

Description

LeafSearchResult

Result of a leaf key search.

Type Aliases

Name

Description

KeyStorage

The key slot storage type.

PayloadPtr

Pointer to a stored payload, or std::nullptr_t when there is none.

Seq

The seqlock type used to bracket concurrent access.

T

The key type.

Member Functions

Name

Description

BSkipNodeLeaf [constructor]

Constructs a leaf node and registers its storage with the thread sanitizer.

adaptiveRead

Returns an adaptive read guard bound to this leaf.

clearTombstone

Clears the tombstone bit for the given slot.

findLeafSlot

Searches this leaf for a key.

insertKeyAtSlotGuarded

Inserts a key and payload at a slot under a freshly opened write epoch.

insertKeyAtSlotRaw

Inserts a key and payload at a slot and bumps the element count.

keyStorageAt

Returns a const reference to the key slot storage at the given slot.

loadKey

Loads the key at the given slot.

loadNextMinKey

Loads the minimum key of the successor node.

loadPayload

Loads the payload at the given slot.

minKey

Returns this leaf's minimum key.

payloadStorageAt

Returns a const reference to the payload slot storage at the given slot.

setTombstone

Sets the tombstone bit for the given slot.

splitKeys

Moves the tail of this leaf into a destination leaf during a split.

storeKey

Stores a key at the given slot.

storePayload

Stores a payload at the given slot.

tombstoned

Reports whether the slot is tombstoned.

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