Struct LeafNode15 

pub struct LeafNode15<P: LeafPolicy> { /* private fields */ }

B-link leaf node with 15 slots, parameterized over LeafPolicy.

Implementations

impl<P: LeafPolicy> LeafNode15<P>

pub const WIDTH: usize = WIDTH_15

Node width (number of slots). Matches TreeLeafNode::WIDTH.

pub fn new_with_root(is_root: bool) -> Self

Create a new leaf node (unboxed).

pub unsafe fn init_at(ptr: *mut Self, is_root: bool)

Initialize a leaf node directly at the given pointer.

Safety

Inline comments.

pub fn new() -> Box<Self>

Create a new leaf node (boxed).

pub fn new_root() -> Box<Self>

Create a new leaf node as the root of a tree/layer.

pub fn make_layer_root(&self)

Convert this leaf into a layer root.

pub fn new_layer_root() -> Box<Self>

Create a new leaf node configured as a layer root.

pub fn new_boxed() -> Box<Self>

Inherent alias for TreeLeafNode::new_boxed.

pub fn new_root_boxed() -> Box<Self>

Inherent alias for TreeLeafNode::new_root_boxed.

pub fn new_layer_root_boxed() -> Box<Self>

Inherent alias for TreeLeafNode::new_layer_root_boxed.

pub fn load_value(&self, slot: usize) -> Option<P::Output>

Load the terminal value at a slot.

pub fn load_value_relaxed(&self, slot: usize) -> Option<P::Output>

Load the terminal value with Relaxed ordering. For use under lock where the lock’s Acquire provides visibility.

pub fn store_value(&self, slot: usize, output: &P::Output)

Store a terminal value at a slot.

pub fn store_value_relaxed(&self, slot: usize, output: &P::Output)

Store a terminal value with Relaxed ordering.

pub fn update_value_in_place( &self, slot: usize, output: &P::Output, ) -> RetireHandle

Update an existing terminal value in place, returning a retire handle.

pub fn update_value_in_place_relaxed( &self, slot: usize, output: &P::Output, ) -> RetireHandle

Update an existing terminal value with Relaxed store ordering. For use under lock where the lock’s Release on drop provides synchronization.

pub fn take_value(&self, slot: usize) -> Option<P::Output>

Take the terminal value from a slot, leaving it empty.

pub unsafe fn write_through_update_value( &self, slot: usize, new_value: &P::Value, ) -> P::Value

Write-through update: atomically read old value and write new value.

Bypasses Box allocation and EBR retirement. Only callable when P::CAN_WRITE_THROUGH is true.

Safety

• Caller must hold the leaf lock.
• Slot must contain a terminal value.

pub fn load_layer(&self, slot: usize) -> *mut u8

Load the layer pointer at a slot.

pub fn store_layer(&self, slot: usize, ptr: *mut u8)

Store a layer pointer at a slot.

pub fn take_value_for_layer(&self, slot: usize) -> RetireHandle

Take the value at a slot when converting it to a layer pointer.

pub fn prefetch_value(&self, slot: usize)

Prefetch the value at a slot to hide memory latency.

pub fn prefetch_suffix(&self)

Prefetch suffix storage into cache for upcoming access.

pub unsafe fn load_value_ptr(&self, slot: usize) -> *const P::Value

Load the typed value pointer at a slot.

Safety

Caller must ensure the slot contains a terminal value, not a layer.

pub fn is_slot_empty(&self, slot: usize) -> bool

Check if a slot is empty (no value, no layer).

pub fn is_value_empty(&self, slot: usize) -> bool

Check if a slot has no value stored.

pub fn is_value_empty_relaxed(&self, slot: usize) -> bool

Relaxed empty check for OCC search loops.

The permutation Acquire load provides synchronization with writers. The OCC has_changed() check validates after all reads.

pub fn load_layer_raw(&self, slot: usize) -> *mut u8

Load the raw layer pointer at a slot.

pub fn load_value_raw(&self, slot: usize) -> *mut u8

Load the raw value pointer at a slot without interpretation.

pub fn load_value_raw_relaxed(&self, slot: usize) -> *mut u8

Load the raw value pointer with Relaxed ordering.

Use when Acquire on the pointer is redundant (e.g., write-through paths where a subsequent atomic value read provides synchronization).

pub fn clear_slot(&self, slot: usize)

Clear a slot’s value and keylenx (Relaxed ordering, for use under lock).

pub fn clear_slot_and_permutation(&self, slot: usize)

Clear a slot’s value, keylenx, and permutation entry.

pub fn classify_slot(&self, slot: usize) -> SlotKind<P::Output>

Classify a slot’s contents, extracting the value if present.

pub fn classify_slot_light(&self, slot: usize) -> SlotState

Lightweight slot classification without value extration.

pub fn move_value_to(&self, dst: &Self, src_slot: usize, dst_slot: usize)

Move a slot’s value from this leaf to another leaf.

pub fn move_value_to_relaxed( &self, dst: &Self, src_slot: usize, dst_slot: usize, )

Move a slot’s value with Relaxed store ordering on the destination. For use under lock where the lock’s Release on drop provides synchronization.

pub fn clear_value(&self, slot: usize)

Clear a slot’s value storage (without touching keylenx).

pub fn clear_value_relaxed(&self, slot: usize)

Clear a slot’s value with Relaxed ordering. For use under lock where the lock’s Release on drop provides synchronization.

pub fn ksuf(&self, slot: usize) -> Option<&[u8]>

Get the suffix bytes for a slot.

pub fn ksuf_or_empty(&self, slot: usize) -> &[u8]

Get the suffix bytes for a slot, or an empty slice if none.

pub fn ksuf_equals(&self, slot: usize, suffix: &[u8]) -> bool

Check if a slot’s suffix equals the given bytes.

pub fn ksuf_compare(&self, slot: usize, suffix: &[u8]) -> Option<Ordering>

Compare a slot’s suffix with the given bytes.

pub fn ksuf_matches(&self, slot: usize, ikey: u64, suffix: &[u8]) -> bool

Check if a slot’s full key matches the given ikey + suffix.

pub fn ksuf_match_result(&self, slot: usize, keylenx: u8, suffix: &[u8]) -> i32

Match a slot against a key suffix, returning a result code.

pub unsafe fn assign_ksuf( &self, slot: usize, suffix: &[u8], guard: &LocalGuard<'_>, ) -> *mut u8

Assign a suffix to a slot.

Safety

Inline comments.

pub unsafe fn assign_ksuf_init( &self, slot: usize, suffix: &[u8], guard: &LocalGuard<'_>, )

Assign a suffix during node initialization (sequential slots 0..slot).

Safety

Same as assign_ksuf.

pub unsafe fn assign_ksuf_prealloc( &self, slot: usize, suffix: &[u8], guard: &LocalGuard<'_>, prealloc: Vec<u8>, ) -> *mut u8

Assign a suffix using a pre-allocated buffer.

Safety

Same as assign_ksuf.

pub unsafe fn retire_suffix_bag_ptr(ptr: *mut u8, guard: &LocalGuard<'_>)

Retire a suffix bag pointer returned by assign_ksuf.

Safety

ptr must have come from assign_ksuf and must not be null.

pub unsafe fn clear_ksuf(&self, slot: usize, guard: &LocalGuard<'_>)

Clear a slot’s suffix.

Safety

Caller must hold the leaf lock.

pub fn has_external_ksuf(&self) -> bool

Check if external (overflow) suffix storage has been allocated.

pub const fn version(&self) -> &NodeVersion

Get a reference to the node’s version.

pub const fn version_mut(&mut self) -> &mut NodeVersion

Get a mutable reference to the node’s version.

pub fn ikey(&self, slot: usize) -> u64

Get the ikey at the given physical slot.

Uses Acquire ordering to synchronize with writer’s Release stores.

Panics

Panics in debug mode if slot >= WIDTH_15.

pub fn ikey_relaxed(&self, slot: usize) -> u64

Get the ikey at the given physical slot using Relaxed ordering.

Panics

Panics in debug mode if slot >= WIDTH_15.

pub fn set_ikey(&self, slot: usize, ikey: u64)

Set the ikey at the given physical slot.

pub fn prefetch_ikey(&self, slot: usize)

Prefetch the ikey at the given slot into CPU cache.

Safety

The slot must be in range [0, WIDTH_15). No bounds check in release mode.

pub fn prefetch(&self)

Prefetch leaf node data for range scans.

pub fn prefetch_for_search(&self)

Prefetch for point lookup (permutation + keys + values).

pub fn prefetch_for_search_adaptive(&self, size: usize)

Size-aware prefetch: only fetch cache lines that will be accessed.

pub fn keylenx(&self, slot: usize) -> u8

Get the keylenx at the given physical slot.

pub fn keylenx_relaxed(&self, slot: usize) -> u8

Get the keylenx with Relaxed ordering. For OCC search loops where the permutation Acquire provides synchronization.

pub fn set_keylenx(&self, slot: usize, keylenx: u8)

Set the keylenx at the given physical slot.

pub fn ikey_bound(&self) -> u64

Get the ikey bound (ikey at slot 0, used for B-link tree routing).

pub fn keylenx_bound(&self) -> u8

Get the keylenx bound for this leaf.

pub fn is_layer(&self, slot: usize) -> bool

Check if the given slot contains a layer pointer.

pub fn has_ksuf(&self, slot: usize) -> bool

Check if the given slot has a suffix.

pub const fn keylenx_is_layer(keylenx: u8) -> bool

Check if keylenx indicates a layer pointer (static helper).

pub const fn keylenx_has_ksuf(keylenx: u8) -> bool

Check if keylenx indicates suffix storage (static helper).

pub fn find_ikey_matches(&self, target_ikey: u64) -> u32

Search all 15 ikeys for matches with target, returning a bitmask.

pub fn permutation(&self) -> Permuter15

Load permutation with Acquire ordering.

pub fn set_permutation(&self, perm: Permuter15)

Store permutation with Release ordering.

pub fn set_permutation_relaxed(&self, perm: Permuter15)

Store permutation with Relaxed ordering.

pub fn permutation_raw(&self) -> u64

Get raw permutation value (for debugging).

pub unsafe fn store_key_data_for_cas(&self, slot: usize, ikey: u64, keylenx: u8)

Store key metadata (ikey, keylenx) for a CAS insert attempt.

Safety

• The caller must have successfully claimed the slot via cas_slot_value and ensured the slot still belongs to the CAS attempt (i.e. leaf_values[slot] still equals the claimed pointer).

pub fn size(&self) -> usize

Get the number of keys in this leaf.

pub fn is_empty(&self) -> bool

Check if the leaf is empty.

pub fn is_full(&self) -> bool

Check if the leaf is full.

pub fn safe_next(&self, guard: &impl Guard) -> *mut Self

Get the next leaf pointer, masking the mark bit.

pub unsafe fn safe_next_unguarded(&self) -> *mut Self

Get the next leaf pointer without guard protection.

Safety

Caller must ensure the next pointer’s target won’t be retired during use.

pub fn next_raw(&self, guard: &impl Guard) -> *mut Self

Get the raw next pointer (including mark bit).

pub unsafe fn next_raw_unguarded(&self) -> *mut Self

Get the raw next pointer without guard protection.

Safety

Caller must ensure the next pointer’s target won’t be retired during use.

pub fn next_is_marked(&self) -> bool

Check if the next pointer is marked (split in progress).

pub fn set_next(&self, next: *mut Self)

Set the next leaf pointer.

pub fn mark_next(&self)

Mark the next pointer (during split).

pub fn unmark_next(&self)

Unmark the next pointer.

pub fn wait_for_split(&self)

Wait for an in-progress split to complete.

pub unsafe fn unlink_from_chain(&self)

Unlink this leaf from the B-link doubly-linked chain.

Safety

• Caller must hold the version lock on this leaf
• self.prev() must be non-null (not the leftmost leaf)
• The prev and next pointers must be valid leaves

pub fn prev(&self, guard: &impl Guard) -> *mut Self

Get the previous leaf pointer.

pub unsafe fn prev_unguarded(&self) -> *mut Self

Get the previous leaf pointer without guard protection.

Safety

Caller must ensure the prev pointer’s target won’t be retired during use.

pub fn set_prev(&self, prev: *mut Self)

Set the previous leaf pointer.

pub fn parent(&self, guard: &impl Guard) -> *mut u8

Get the parent pointer.

Uses guard protection to ensure the load participates in seize’s total order, making it safe on all architectures.

pub unsafe fn parent_unguarded(&self) -> *mut u8

Get the parent pointer without guard protection.

Safety

Caller must ensure the parent pointer’s target won’t be retired during use.

pub fn set_parent(&self, parent: *mut u8)

Set the parent pointer.

pub fn modstate(&self) -> u8

Get the raw modification state (includes queued bit).

pub fn set_modstate(&self, state: u8)

Set the modification state (overwrites all bits including queued).

pub fn modstate_relaxed(&self) -> u8

Get the raw modification state (relaxed, for use under lock).

pub fn set_modstate_relaxed(&self, state: u8)

Set the modification state (relaxed, for use under lock).

pub fn deleted_layer(&self) -> bool

Check if this layer has been deleted (garbage collected).

pub fn mark_deleted_layer(&self)

Mark this layer as deleted (for gc_layer). Preserves queued bit.

pub fn mark_remove(&self)

Mark this node as being in remove mode. Preserves queued bit.

pub fn is_removing(&self) -> bool

Check if this node is in remove mode.

pub fn is_empty_state(&self) -> bool

Check if this leaf is in empty state.

pub fn mark_empty(&self)

Mark this leaf as empty (all keys removed). Preserves queued bit.

pub fn clear_empty_state(&self)

Clear empty state, returning to normal insert mode. Stores 0, clearing the queued bit. Correct for insert reuse: invalidates any pending coalesce entry for this leaf.

pub fn is_queued(&self) -> bool

Check if this leaf has a pending coalesce queue entry.

pub fn try_mark_queued(&self) -> bool

Atomically set the queued bit. Returns true if the bit was not already set (this call won the race). This is the sole enqueue gate.

pub fn clear_queued(&self)

Clear the queued bit atomically. Called after gc retires or skips.

pub fn can_reuse_slot0(&self, new_ikey: u64) -> bool

Check if slot 0 can be reused for a new key.

pub fn calculate_split_point( &self, insert_pos: usize, insert_ikey: u64, ) -> Option<SplitPoint>

Calculate the optimal split point for this leaf.

pub unsafe fn split_into_preallocated( &self, split_pos: usize, new_leaf_ptr: *mut Self, guard: &LocalGuard<'_>, ) -> (u64, InsertTarget)

Split entries from position split_pos..size into a new leaf.

Safety

• Caller holds the lock on self.
• new_leaf_ptr is valid, properly aligned, and points to an initialized (via new_with_root(false) or init_at) but empty leaf.
• new_leaf_ptr is not yet visible to other threads.

pub unsafe fn split_all_to_right_preallocated( &self, new_leaf_ptr: *mut Self, guard: &LocalGuard<'_>, ) -> (u64, InsertTarget)

Split ALL entries to the right leaf (used for reverse-sequential pattern).

Safety

Same as split_into_preallocated.

pub unsafe fn split_and_insert( &self, split_pos: usize, new_leaf_ptr: *mut Self, insert_pos: usize, insert_data: &SplitInsertData<'_, P>, guard: &LocalGuard<'_>, ) -> SplitInsertResult

Atomic split + insert: split entries and insert a new key in one operation.

Safety

Same as split_into_preallocated.

pub unsafe fn link_sibling(&self, new_sibling: *mut Self)

Link a new sibling after this leaf during a split.

Safety

• Caller must hold the lock on self.
• new_sibling must be valid and not yet in the chain.

Trait Implementations

impl<P: LeafPolicy> Debug for LeafNode15<P>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<P: LeafPolicy> Drop for LeafNode15<P>

fn drop(&mut self)

Executes the destructor for this type.

impl<P: LeafPolicy> TreeLeafNode<P> for LeafNode15<P>

const WIDTH: usize = WIDTH_15

Node width (number of slots).

const SPLIT_THRESHOLD: usize = WIDTH_15

Split threshold (trigger split when size >= this).

const INLINE_KSUF_CAPACITY: usize = 512

Inline suffix storage capacity in bytes.

type Perm = Permuter

The permutation type for this leaf.

type Internode = InternodeNode

The internode type for this tree variant.

fn new_boxed() -> Box<Self>

Create a new leaf node (boxed, non-root).

fn new_root_boxed() -> Box<Self>

Create a new root leaf node (boxed).

fn new_layer_root_boxed() -> Box<Self>

Create a new layer root leaf node (boxed).

fn version(&self) -> &NodeVersion

Get reference to the node’s version for OCC protocol.

fn permutation(&self) -> Permuter15

Load permutation with Acquire ordering.

fn set_permutation(&self, perm: Permuter15)

Store permutation with Release ordering.

fn set_permutation_relaxed(&self, perm: Permuter15)

Store permutation with Relaxed ordering (for split setup).

fn permutation_raw(&self) -> u64

Get raw permutation value for atomic operations.

fn ikey(&self, slot: usize) -> u64

Get ikey at slot with Acquire ordering.

fn ikey_relaxed(&self, slot: usize) -> u64

Get ikey at slot with Relaxed ordering (after Acquire fence).

fn set_ikey(&self, slot: usize, ikey: u64)

Set ikey at slot with Release ordering.

fn set_ikey_relaxed(&self, slot: usize, ikey: u64)

Set ikey at slot with Relaxed ordering (for split setup).

fn ikey_bound(&self) -> u64

Get the ikey bound (ikey at slot 0, used for B-link routing).

fn find_ikey_matches(&self, target_ikey: u64) -> u32

Find all slots matching target ikey, returning a bitmask.

fn keylenx(&self, slot: usize) -> u8

Get keylenx at slot.

fn keylenx_relaxed(&self, slot: usize) -> u8

Get keylenx with Relaxed ordering (for OCC search loops).

fn set_keylenx(&self, slot: usize, keylenx: u8)

Set keylenx at slot with Release ordering.

fn set_keylenx_relaxed(&self, slot: usize, keylenx: u8)

Set keylenx at slot with Relaxed ordering (for split setup).

fn is_layer(&self, slot: usize) -> bool

Check if slot contains a layer pointer.

fn has_ksuf(&self, slot: usize) -> bool

Check if slot has a key suffix.

fn load_value(&self, slot: usize) -> Option<P::Output>

Load the terminal value at a slot, returning None if empty.

fn store_value(&self, slot: usize, output: &P::Output)

Store a terminal value at a slot with Release ordering.

fn store_value_relaxed(&self, slot: usize, output: &P::Output)

Store a terminal value at a slot with Relaxed ordering (for split setup).

fn update_value_in_place(&self, slot: usize, output: &P::Output) -> RetireHandle

Update value in place, returning a handle for retiring the old value.

fn update_value_in_place_relaxed( &self, slot: usize, output: &P::Output, ) -> RetireHandle

Update value in place with Relaxed store ordering (for use under lock).

fn take_value(&self, slot: usize) -> Option<P::Output>

Take the terminal value from a slot, leaving it empty.

fn load_layer(&self, slot: usize) -> *mut u8

Load the layer pointer at a slot.

fn store_layer(&self, slot: usize, ptr: *mut u8)

Store a layer pointer at a slot.

fn is_slot_empty(&self, slot: usize) -> bool

Check if a slot is empty (no value or layer pointer).

fn classify_slot(&self, slot: usize) -> SlotKind<P::Output>

Classify a slot as empty, value, or layer, returning the value if present.

fn classify_slot_light(&self, slot: usize) -> SlotState

Classify a slot without extracting the value (lightweight variant).

fn move_value_to(&self, dst: &Self, src_slot: usize, dst_slot: usize)

Move a value from one leaf/slot to another leaf/slot.

fn clear_value(&self, slot: usize)

Clear the value at a slot (set to empty).

fn clear_slot(&self, slot: usize)

Clear all data at a slot (value, keylenx, etc.).

fn clear_slot_and_permutation(&self, slot: usize)

Clear a slot and remove it from the permutation.

fn safe_next(&self) -> *mut Self

Get the next leaf pointer, masking the mark bit (unguarded).

fn next_is_marked(&self) -> bool

Check if the next pointer is marked (split in progress).

fn set_next(&self, next: *mut Self)

Set the next leaf pointer.

fn mark_next(&self)

Mark the next pointer (set LSB for split coordination).

fn unmark_next(&self)

Unmark the next pointer (clear LSB).

fn prev(&self) -> *mut Self

Get the previous leaf pointer (unguarded).

fn set_prev(&self, prev: *mut Self)

Set the previous leaf pointer.

fn parent(&self) -> *mut u8

Get the parent internode pointer (unguarded).

fn set_parent(&self, parent: *mut u8)

Set the parent internode pointer.

unsafe fn unlink_from_chain(&self)

Unlink this leaf from the doubly-linked chain.

fn next_raw(&self) -> *mut Self

Get the raw next pointer including mark bit (unguarded).

fn wait_for_split(&self)

Spin-wait until split completes on this leaf.

fn can_reuse_slot0(&self, new_ikey: u64) -> bool

Check if slot 0 can be reused for a new key.

fn calculate_split_point( &self, insert_pos: usize, insert_ikey: u64, ) -> Option<SplitPoint>

Calculate the optimal split point for this leaf.

unsafe fn split_into_preallocated( &self, split_pos: usize, new_leaf_ptr: *mut Self, guard: &LocalGuard<'_>, ) -> (u64, InsertTarget)

Split this leaf into a preallocated sibling.

unsafe fn split_all_to_right_preallocated( &self, new_leaf_ptr: *mut Self, guard: &LocalGuard<'_>, ) -> (u64, InsertTarget)

Split all entries to the right sibling (sequential-append optimization).

unsafe fn split_and_insert( &self, split_pos: usize, new_leaf_ptr: *mut Self, insert_pos: usize, insert_data: &SplitInsertData<'_, P>, guard: &LocalGuard<'_>, ) -> SplitInsertResult

Atomically split this leaf and insert a new key.

unsafe fn link_sibling(&self, new_sibling: *mut Self)

Link a new sibling into the B-link chain.

fn ksuf(&self, slot: usize) -> Option<&[u8]>

Get the suffix at a slot, if present.

unsafe fn assign_ksuf( &self, slot: usize, suffix: &[u8], guard: &LocalGuard<'_>, ) -> *mut u8

Assign a suffix to a slot, returning the old suffix bag pointer.

unsafe fn retire_suffix_bag_ptr(ptr: *mut u8, guard: &LocalGuard<'_>)

Retire a suffix bag pointer for deferred reclamation.

unsafe fn assign_ksuf_init( &self, slot: usize, suffix: &[u8], guard: &LocalGuard<'_>, )

Assign a suffix during initial slot setup.

unsafe fn clear_ksuf(&self, slot: usize, guard: &LocalGuard<'_>)

Clear the suffix at a slot.

fn ksuf_equals(&self, slot: usize, suffix: &[u8]) -> bool

Check if the suffix at a slot equals the given suffix.

fn ksuf_compare(&self, slot: usize, suffix: &[u8]) -> Option<Ordering>

Compare the suffix at a slot with the given suffix.

fn ksuf_or_empty(&self, slot: usize) -> &[u8]

Get the suffix at a slot, or empty slice if none.

fn ksuf_matches(&self, slot: usize, ikey: u64, suffix: &[u8]) -> bool

Check if the suffix at a slot matches the given ikey and suffix.

fn ksuf_match_result(&self, slot: usize, keylenx: u8, suffix: &[u8]) -> i32

Compare suffix, returning match result code.

fn prefetch(&self)

Prefetch leaf data for range scans.

fn prefetch_ikey(&self, slot: usize)

Prefetch the ikey at a slot.

fn prefetch_for_search(&self)

Prefetch for point lookup (permutation + keys).

fn prefetch_for_search_adaptive(&self, size: usize)

Size-aware prefetch: only fetch cache lines that will be accessed.

fn modstate(&self) -> u8

Get the modification state.

fn set_modstate(&self, state: u8)

Set the modification state.

fn deleted_layer(&self) -> bool

Check if the layer has been deleted.

fn mark_deleted_layer(&self)

Mark the layer as deleted.

fn mark_remove(&self)

Mark the node for removal.

fn is_removing(&self) -> bool

Check if the node is being removed.

fn is_empty_state(&self) -> bool

Check if the node is in empty state.

fn mark_empty(&self)

Mark the node as empty.

fn clear_empty_state(&self)

Clear the empty state flag.

fn size(&self) -> usize

Get the number of keys in this leaf.

fn is_empty(&self) -> bool

Check if the leaf is empty.

fn is_full(&self) -> bool

Check if the leaf is full.

impl<P: LeafPolicy> Send for LeafNode15<P>

impl<P: LeafPolicy> Sync for LeafNode15<P>