Module rxarray 

Rust XArray implementation.

This module implements an extensible array (aka XArray) via the XArray type. See XArray4 and XArray6 for common configurations.

The array can hold two types of entries at the same time where each index independently stores either an owned pointer (T: ForeignOwnable) or a bounded integer up to usize::MAX >> 1 backed by Bounded. Users insert entries via the Entry type. References to entries in the tree are handled by the BorrowedEntry and BorrowedEntryMut types.

Differences from C XArray

The C XArray uses RCU for lock-free reads and an internal spinlock for writes. This implementation does not provide internal locking. A mutable reference is required for writes, a shared reference for reads. Locking can be applied externally. RCU support is planned.

This implementation allocates during store. xa_reserve() and xas_nomem() are not yet supported.

C xa_destroy() frees only internal nodes; callers must free their own stored values. Dropping XArray also frees all stored entries.

C xa_mk_value() issues WARN_ON if the value exceeds LONG_MAX; the left shift overflows, producing a wrong entry. Rust Entry::int() rejects out-of-range values at compile time via Bounded, and Entry::try_int() returns None at runtime.

The C XArray grows in depth on demand to be efficient for small indices, creating a short tree whenever possible and adding levels as larger indices appear. This implementation always walks the full levels, whatever the largest stored index is. Variable height is planned.

C XArray features like search marks, multi-index entries, advanced API, etc. are not yet implemented.

This implementation aims for full feature parity with the C XArray; any gap not covered above is a defect in this list.

Data structure

The XArray is a radix tree that maps usize indices to Entry values. Each node holds an array of SIZE slots (where SIZE = 1 << SHIFT), and the tree depth is ceil(usize::BITS / SHIFT). Indices are decomposed so that each chunk indexes a slot in a node at the corresponding level.

                                XArray
                                   │
                                   ▼
                          ┌────────────────┐
                          │   Root Node    │  Level = levels-1
                          │ slots[0..SIZE] │
                          └────────────────┘
                           /       |       \
              ┌───────────┘        │        └───────────┐
              ▼                    ▼                    ▼
     ┌────────────────┐       ┌────────┐       ┌────────────────┐
     │      Node      │       │ Empty  │       │      Node      │
     │ slots[0..SIZE] │       └────────┘       │ slots[0..SIZE] │
     └────────────────┘                        └────────────────┘
       /           \                                   |
      ▼             ▼                                  ▼
   ...            ...                          ┌────────────────┐
                                               │   Leaf Node    │  Level = 0
                                               │ slots[0..SIZE] │
                                               └────────────────┘
                                                /       |       \
                                               ▼        ▼        ▼
                                            Entry    Empty    Entry
                                            (Int)             (Ptr)

Index decomposition for XArray6 (SHIFT=6, 64 slots per node, 11 levels on 64-bit):

  ┌─────────────────────────────────────────────────────────────────┐
  │ index                                                           │
  ├─────────┬─────────┬───────────────┬─────────┬─────────┬─────────┤
  │ level10 │ level 9 │      ...      │ level 2 │ level 1 │ level 0 │
  │ [63:60] │ [59:54] │               │ [17:12] │ [11:6]  │  [5:0]  │
  └─────────┴─────────┴───────────────┴─────────┴─────────┴─────────┘

At each level, the slot offset is: (index >> (level * SHIFT)) & (SIZE - 1).

C API

This implementation does not have a C API yet. When one is added, its FFI layer must validate at runtime what the Rust API enforces at compile or construction time:

• Int values: use Entry::try_int(); reject None as -EINVAL. C has no Bounded, so the FFI wrapper is the enforcement point.
• Pointers: validate 4-byte alignment and non-null at runtime. const_assert!(T::FOREIGN_ALIGN >= 4) only covers Rust callers.
• NULL pointers: dispatch as erase (xa_store(NULL) == xa_erase) or reserve (XA_FLAGS_ALLOC) before reaching XArray::store().
• Error entries: reject xa_is_err() values; Rust would misclassify them as node pointers (see Slot invariants).

Structs

StoreError

The error returned by XArray::store().

XArray

An extensible array backed by a radix tree, mapping usize indices to Entry values.

Enums

BorrowedEntry

A borrowed entry returned by XArray::load(), containing either an integer or a borrowed pointer.

BorrowedEntryMut

A mutably borrowed entry returned by XArray::load_mut(), containing either an integer or a borrowed pointer.

Entry

An entry is either an Entry::Int integer (0..=usize::MAX >> 1) or an owned Entry::Pointer.

Type Aliases

Value

Type alias for Entry::Int values. Integers that fit in usize::BITS - 1 bits (0..=usize::MAX >> 1).

XArray4

Type alias for XArray with a shift of 4 and 16 slots per node.

XArray6

Type alias for XArray with a shift of 6 and 64 slots per node.