Module idr 

An RCU-protected, lock-free integer ID radix tree (IDR).

Maps 32-bit integer IDs to objects (Arc<T>), optimized for workloads with heavily contended concurrent reads and serialized mutations (such as PID tables, task registries, and descriptor tables).

Concurrency Model

• Readers (lookup, iter): Completely lock-free and wait-free. Traversal operates under an RcuReadScope, ensuring memory reclamation safety without blocking or interfering with writers.
• Writers (alloc, reserve_id, remove): Mutations are serialized via an IdrGuard acquired with Idr::lock, while atomic pointer updates and memory barriers allow concurrent readers to proceed in parallel without interruption.

Key Operations

• Idr::lock: Acquires the writer lock, returning an IdrGuard for mutating operations.
• Idr::lookup: Retrieves the object for a given ID without locking.
• Idr::iter: Iterates over all active (u32, &Arc<T>) entries under an RCU scope.
• Idr::max: Returns the maximal value allowed for allocation in this Idr.
• Idr::set_max: Sets the maximal value allowed for allocation in this Idr.
• IdrGuard::alloc: Allocates an ID using the configured allocation policy (linear from 0 or cyclic from cursor).
• IdrGuard::reserve_id: Marks a specific ID as occupied without inserting an element.
• IdrGuard::remove: Removes an item and restores slot availability.

Structural Architecture

The tree is a 64-ary radix tree (consuming 6 bits per layer, up to 6 layers for 32-bit IDs):

• Intermediate nodes (layer > 0) route down to child nodes.
• Leaf nodes (layer == 0) hold concrete Arc<T> entries.
• Each node maintains an atomic free_bitmap tracking capacity across its 64 sub-slots, enabling $O(1)$ child selection and efficient subtree skipping during allocation.
• The tree dynamically grows upwards in layers as ID requirements expand.

Structs

Idr

A concurrent, lock-free radix tree mapped structure primarily employed to map 32-bit IDs to objects. Optimized for massively contended reads.

IdrGuard

An RAII guard representing exclusive writer access to an Idr.

IdrIterator

A lock-free iterator traversing the allocated elements inside the radix tree under an automated RCU read scope, operating without acquiring any thread locks.

Enums

IdrAllocMode

The allocation mode used by an Idr.