Struct InternodeNode 

pub struct InternodeNode { /* private fields */ }

An internal routing node in the MassTree.

Stores up to 15 keys and 16 child pointers. Keys are always in sorted physical order (no permutation needed).

Design Note

Unlike leaf nodes, internodes don’t store values - only u64 keys and *mut u8 child pointers. This struct is therefore non-generic, reducing code monomorphization (one InternodeNode implementation regardless of the tree’s slot type).

Invariants

• nkeys <= WIDTH (max 15 keys)
• For nkeys keys, there are nkeys + 1 valid children (child[0..=nkeys])
• Keys are in ascending order: ikey[i] < ikey[i+1] for all i < nkeys-1
• child[i] contains keys < ikey[i]
• child[i+1] contains keys >= ikey[i]

Memory Layout

Uses #[repr(C, align(64))] for cache-line alignment. Total size is 264 bytes of data, 320 bytes with alignment (5 cache lines).

Implementations

impl InternodeNode

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 nkeys(&self) -> usize

Get the number of keys in this internode.

pub fn size(&self) -> usize

Alias for Self::nkeys for API consistency with leaf nodes.

pub fn is_empty(&self) -> bool

Check if the internode has no keys.

pub fn is_full(&self) -> bool

Check if the internode is full.

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

Get the key at the given index.

Panics

Panics in debug mode if i >= WIDTH.

pub fn load_all_ikeys(&self) -> [u64; 15]

Batch load all ikeys into a local array.

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

Set the key at the given index.

Panics

Panics in debug mode if i >= WIDTH.

pub const fn height(&self) -> u32

Get the tree height.

pub const fn children_are_leaves(&self) -> bool

Check if children are leaves (height == 0).

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

Get the child pointer at the given index.

Panics

Panics in debug mode if i > WIDTH.

pub unsafe fn child_unguarded(&self, i: usize) -> *mut u8

Get the child pointer without guard protection.

Safety

Caller must ensure the child pointer’s target won’t be retired during use. Valid when:

• Called during Drop (no concurrent access)
• Called in teardown after reclaim_all()

pub fn child_with_prefetch( &self, i: usize, nkeys: usize, guard: &impl Guard, ) -> *mut u8

Get the child pointer with prefetch hint for the next likely child.

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

Get the child pointer with depth-first prefetch for tree descent.

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

Get the child pointer with full prefetch for tree descent.

pub fn set_child(&self, i: usize, child: *mut u8)

Set the child pointer at the given index.

Panics

Panics in debug mode if i > WIDTH.

pub fn assign(&self, p: usize, ikey: u64, right_child: *mut u8)

Assign a key and its right child at position p.

Panics

Panics in debug mode if p >= WIDTH.

pub fn set_nkeys(&self, n: u8)

Set the number of keys.

Panics

Panics in debug mode if n > WIDTH.

pub fn inc_nkeys(&self)

Increment the number of keys by 1.

Panics

Panics in debug mode if already at WIDTH.

impl InternodeNode

pub unsafe fn init_at(ptr: *mut Self, height: u32)

Initialize an internode in-place at the given pointer.

This is used by pool allocators to initialize directly in pool memory, avoiding the intermediate Box allocation.

Safety

• ptr must be valid for writes of size_of::<Self>() bytes
• ptr must be properly aligned for Self
• The caller must have exclusive access to the memory
• The memory does not need to be initialized (will be overwritten)

pub unsafe fn init_at_root(ptr: *mut Self, height: u32)

Initialize an internode in-place as a root node.

Safety

Same requirements as Self::init_at.

pub unsafe fn init_at_for_split( ptr: *mut Self, parent_version: &NodeVersion, height: u32, )

Initialize an internode in-place for a split operation.

Creates a split-locked version copied from the parent’s locked version. This prevents other threads from locking the sibling until installed.

Safety

• Same requirements as Self::init_at
• parent_version must be from a locked node

pub fn new(height: u32) -> Box<Self>

Create a new internode at the given height.

Arguments

• height - Tree height (0 = children are leaves)

Returns

A boxed internode with zero keys and null children.

pub fn new_root(height: u32) -> Box<Self>

Create a new internode as root of a tree/layer.

Same as new() but marks the node as root.

pub fn new_for_split(parent_version: &NodeVersion, height: u32) -> Box<Self>

Create a new internode sibling for a split operation.

The new internode is created with a split-locked version copied from the locked parent. This prevents other threads from locking the sibling until it is installed into the tree and its parent pointer is set.

Help-Along Protocol

This is the internode equivalent of leaf NodeVersion::new_for_split(). The caller MUST call version().unlock_for_split() exactly once after:

1. The sibling is inserted into its parent (grandparent or new root)
2. The sibling’s parent pointer is set

C++ Reference

Matches next_child->assign_version(*p) in masstree_split.hh:234:

next_child = internode_type::make(height + 1, ti);
next_child->assign_version(*p);
next_child->mark_nonroot();

Safety

The parent_version must be from a locked node (the parent being split).

pub fn insert_key_and_child(&self, p: usize, new_ikey: u64, new_child: *mut u8)

Insert a key and child at position p, shifting existing entries right.

After insertion:

• ikey[p] = new_ikey
• child[p + 1] = new_child
• Keys/children at positions >= p are shifted right by 1

Used when propagating a split up the tree: the new_ikey is the popup key from the child split, and new_child is the new right sibling.

Arguments

• p - Position to insert at (0 <= p <= nkeys)
• new_ikey - The popup key from the child split
• new_child - The new right child (right sibling of the split)

Memory Ordering

Keys use Relaxed stores (validated via version checking by readers). Child pointers use Release stores (readers use Acquire loads during traversal). The final nkeys store with Release ordering publishes the key count.

Panics

Panics in debug mode if node is full or position out of bounds.

pub unsafe fn shift_from( &self, dst_pos: usize, src: &Self, src_pos: usize, count: usize, )

Shift entries from another internode.

Copies count entries starting at src_pos from src to dst_pos in self. Used during internode splits.

Arguments

• dst_pos - Starting position in self
• src - Source internode
• src_pos - Starting position in source
• count - Number of entries to copy

Memory Ordering

Keys use Relaxed stores (validated via version checking by readers). Child pointers use Release stores (readers use Acquire loads during traversal). The caller publishes changes via nkeys.store(WRITE_ORD) after this returns.

Safety

Caller must ensure exclusive access (hold lock on both nodes).

pub fn split_into( &self, new_right: &mut Self, new_right_ptr: *mut Self, insert_pos: usize, insert_ikey: u64, insert_child: *mut u8, ) -> (u64, bool)

Split this internode into self + new_right, simultaneously inserting a new key/child.

This matches the C++ internode::split_into() semantics from reference/masstree_split.hh.

Operation

1. Splits keys and children between self and new_right at midpoint
2. Inserts (insert_ikey, insert_child) at position insert_pos
3. Updates all children’s parent pointers in new_right (for internode children)

After split:

• self contains keys [0, mid)
• new_right contains keys [mid+1, WIDTH+1)
• The key at post-insert position mid becomes the popup key

Arguments

• new_right - The new right sibling (pre-allocated by caller)
• new_right_ptr - Raw pointer to new_right for setting parent pointers
• insert_pos - Position to insert the new key/child (0..=WIDTH)
• insert_ikey - The key to insert (popup key from child split)
• insert_child - The child to insert (new right sibling from child split)

Returns

(popup_key, insert_went_left) where:

• popup_key is the separator key to propagate to the parent
• insert_went_left is true if insert went into self, false otherwise (when insert_pos == mid, the insert becomes the popup key and goes into neither node; this case returns false)

Caller Responsibilities

CRITICAL: When height == 0 (leaf children), the caller MUST update the parent pointers of all leaf children that moved to new_right.** This function only updates internode children’s parent pointers (when height > 0).

Safety

• new_right_ptr must point to new_right
• The caller must hold the lock on self

Reference

reference/masstree_split.hh:123-175

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

Get the parent pointer (as *mut u8) with guard protection.

Cast to *mut InternodeNode at usage sites.

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

Get the parent pointer without guard protection.

Safety

Caller must ensure the parent pointer won’t be retired during use. Valid when:

• Called during Drop (no concurrent access)
• Called while holding exclusive lock that prevents retirement

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

Set the parent pointer.

Accepts *mut u8 for uniformity with LeafNode.

pub fn is_root(&self) -> bool

Check if this is a root node (no parent or version says root).

pub fn compare_key(&self, search_ikey: u64, p: usize) -> Ordering

Compare a search key against the key at position p.

Returns:

• Ordering::Less if search_ikey < ikey[p]
• Ordering::Equal if search_ikey == ikey[p]
• Ordering::Greater if search_ikey > ikey[p]

pub fn find_insert_position(&self, insert_ikey: u64) -> usize

Find the position where a key should be inserted.

Returns the first index i where ikey[i] >= insert_ikey, or nkeys if insert_ikey is greater than all existing keys. This satisfies: ikey[i-1] < insert_ikey <= ikey[i].

Algorithm

Linear search with 4× manual unrolling. Linear search outperforms binary search for WIDTH ≤ 16 due to:

• Predictable forward branches (most iterations don’t match)
• Sequential memory access (prefetcher-friendly)
• No branch misprediction penalty from binary search pivots

TODO: Manual unrolling outperforms LLVM auto-unrolling by 10-25% on mixed workloads (benchmarked, but keep this under scrutiny). This is likely due to better prefetch timing and instruction scheduling around atomic loads.

Memory Ordering

Uses a single Acquire fence followed by Relaxed loads. The Acquire fence orders subsequent Relaxed loads after the caller’s version load. Readers retry if version changes, ensuring consistency even with Relaxed key loads.

Prefetch Strategy

Cache lines are prefetched with lead time to hide L2 latency (~12-16 cycles):

• Before loop: prefetch CL1 (ikey0[6]) if n > 6
• At i=8: prefetch CL2 (ikey0[14]) if n > 13

CL0 is assumed hot from the caller’s version check. Prefetching CL1 before the loop gives ~4 iterations (~16-32 cycles) of lead time before we access ikey0[6] at i=4.

pub fn debug_assert_invariants(&self)

Verify internode invariants (debug builds only).

Checks:

• nkeys <= WIDTH
• Keys are in ascending order
• Children for valid indices are non-null (debug-only assertion)

Panics

If any invariant is violated.

Trait Implementations

impl Debug for InternodeNode

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

Formats the value using the given formatter.

impl Default for InternodeNode

fn default() -> Self

Returns the “default value” for a type.

impl TreeInternode for InternodeNode

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

Get the key at the given index using Relaxed ordering.

Used in internal operations where ordering is handled by caller.

fn ikey_ptr(&self) -> *const u64

Get raw pointer to the ikey array for SIMD operations.

Returns pointer to self.ikey0[0], valid for WIDTH (15) contiguous u64 reads.

Layout

ikey0 starts at offset 16 in InternodeNode:

• Offset 0-15: version (4B) + nkeys (1B) + height (1B) + pad (2B) + parent (8B)
• Offset 16-135: ikey0[0..15] (120 bytes, 15 x 8B)

fn child(&self, idx: usize) -> *mut u8

Safety

This trait method is intended for use under exclusive lock. Uses unguarded loads - caller must ensure no concurrent retirement.

fn parent(&self) -> *mut u8

Safety

This trait method is intended for use under exclusive lock. Uses unguarded loads - caller must ensure no concurrent retirement.

fn shift_from(&self, dst_pos: usize, src: &Self, src_pos: usize, count: usize)

Safety

Called under exclusive lock - uses unguarded child loads.

const WIDTH: usize = WIDTH

Node width (max number of children).

fn new_boxed(height: u32) -> Box<Self>

Create a new internode with specified height.

fn new_root_boxed(height: u32) -> Box<Self>

Create a new root internode with specified height.

fn new_boxed_for_split(parent_version: &NodeVersion, height: u32) -> Box<Self>

Create a new internode sibling for a split operation.

fn version(&self) -> &NodeVersion

Get reference to node version.

fn height(&self) -> u32

Get the height of this internode.

fn children_are_leaves(&self) -> bool

Check if children are leaves (height == 0).

fn nkeys(&self) -> usize

Get number of keys.

fn nkeys_relaxed(&self) -> usize

Get number of keys using Relaxed ordering.

fn set_nkeys(&self, n: u8)

Set number of keys.

fn inc_nkeys(&self)

Increment nkeys by 1.

fn is_full(&self) -> bool

Check if this internode is full.

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

Get key at index (Acquire ordering).

fn set_ikey(&self, idx: usize, key: u64)

Set key at index.

fn compare_key(&self, search_ikey: u64, p: usize) -> Ordering

Compare key at position with search key.

fn find_insert_position(&self, insert_ikey: u64) -> usize

Find insert position for a key.

fn set_child(&self, idx: usize, child: *mut u8)

Set child pointer at index.

fn assign(&self, p: usize, ikey: u64, right_child: *mut u8)

Assign key and right child at position.

fn insert_key_and_child(&self, p: usize, new_ikey: u64, new_child: *mut u8)

Insert key and child at position, shifting existing entries.

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

Set parent pointer.

fn is_root(&self) -> bool

Check if this is a root node.

fn split_into( &self, new_right: &mut Self, new_right_ptr: *mut Self, insert_pos: usize, insert_ikey: u64, insert_child: *mut u8, ) -> (u64, bool)

Split this internode into a new sibling while inserting a key/child.

impl Send for InternodeNode

impl Sync for InternodeNode