Implementation Details

Relevant source files

src/lib.rs

This document provides a comprehensive analysis of the internal architecture, data structures, and implementation strategies used in the flatten_objects crate. It covers the low-level details of how the FlattenObjects container manages memory, maintains safety invariants, and implements efficient ID allocation.

For high-level API usage patterns, see Usage Guide and Examples. For specific API method documentation, see FlattenObjects API Documentation.

Core Architecture Overview

The FlattenObjects<T, CAP> struct implements a fixed-capacity object container through three interconnected components that work together to provide safe, efficient object storage with unique ID assignment.

Internal Data Structure Layout

flowchart TD
subgraph subGraph3["External Dependencies"]
    BitsImpl["BitsImpl<CAP>: Bits"]
    MaybeUninit_core["core::mem::MaybeUninit"]
    bitmaps_crate["bitmaps::Bitmap"]
end
subgraph subGraph2["Bitmap Representation"]
    bit0["bit 0: assigned/free"]
    bit1["bit 1: assigned/free"]
    bitN["bit CAP-1: assigned/free"]
end
subgraph subGraph1["Memory Organization"]
    slot0["objects[0]: MaybeUninit<T>"]
    slot1["objects[1]: MaybeUninit<T>"]
    slotN["objects[CAP-1]: MaybeUninit<T>"]
end
subgraph FlattenObjects["FlattenObjects<T, CAP>"]
    objects["objects: [MaybeUninit<T>; CAP]"]
    id_bitmap["id_bitmap: Bitmap<CAP>"]
    count["count: usize"]
end

bit0 --> slot0
bit1 --> slot1
bitN --> slotN
id_bitmap --> bit0
id_bitmap --> bit1
id_bitmap --> bitN
id_bitmap --> bitmaps_crate
objects --> MaybeUninit_core
objects --> slot0
objects --> slot1
objects --> slotN

The structure maintains three critical invariants:

id_bitmap.get(i) == true if and only if objects[i] contains an initialized value
count equals the number of set bits in id_bitmap
All operations preserve these relationships atomically

Sources: src/lib.rs(L44 - L51)

Generic Parameter Constraints

The FlattenObjects implementation relies on compile-time constraints that ensure type safety and capacity limits:

Parameter	Constraint	Purpose
T	Any type	The stored object type
CAP	const usize	Maximum container capacity
BitsImpl<{CAP}>	Bits	Enables bitmap operations for the given capacity

The capacity constraint CAP <= 1024 is enforced through the bitmaps crate's type system and validated at construction time in new().

Sources: src/lib.rs(L44 - L46) src/lib.rs(L59 - L61)

Memory Management Strategy

The implementation uses MaybeUninit<T> to avoid unnecessary initialization overhead and enable precise control over object lifecycle:

Initialization States and Transitions

The bitmap serves as the authoritative source of truth for memory initialization state. All access to objects[i] is guarded by checking id_bitmap.get(i) first.

Sources: src/lib.rs(L48 - L49) src/lib.rs(L77 - L84)

Unsafe Operation Boundaries

The implementation carefully encapsulates unsafe operations within safe method boundaries:

Unsafe Operation	Location	Safety Guarantee
assume_init_ref()	get()method	Protected byis_assigned()check
assume_init_mut()	get_mut()method	Protected byis_assigned()check
assume_init_read()	remove()andadd_or_replace_at()	Protected byis_assigned()check
MaybeUninit::zeroed().assume_init()	new()method	Valid forBitmaptype

Sources: src/lib.rs(L169) src/lib.rs(L198) src/lib.rs(L286) src/lib.rs(L322) src/lib.rs(L81)

ID Allocation and Management

The ID management system uses the bitmaps crate to efficiently track available slots and implement ID reuse:

ID Allocation Flow

flowchart TD
add_request["add(value)"]
find_id["id_bitmap.first_false_index()"]
add_at_request["add_at(id, value)"]
check_bounds["id < CAP"]
add_or_replace_request["add_or_replace_at(id, value)"]
id_available["id.is_some() && id < CAP"]
check_assigned["is_assigned(id)"]
allocate_id["Allocate ID"]
return_error["Err(value)"]
replace_object["Replace existing"]
update_bitmap["id_bitmap.set(id, true)"]
write_value["objects[id].write(value)"]
increment_count["count += 1"]
return_success["Ok(id)"]
end_flow["End"]

add_at_request --> check_bounds
add_or_replace_request --> check_bounds
add_request --> find_id
allocate_id --> update_bitmap
check_assigned --> allocate_id
check_assigned --> replace_object
check_assigned --> return_error
check_bounds --> check_assigned
find_id --> id_available
id_available --> allocate_id
id_available --> return_error
increment_count --> write_value
replace_object --> write_value
return_error --> end_flow
return_success --> end_flow
update_bitmap --> increment_count
write_value --> return_success

The first_false_index() method from the bitmaps crate provides O(1) amortized ID allocation by efficiently finding the first unset bit.

Sources: src/lib.rs(L222 - L232) src/lib.rs(L249 - L257) src/lib.rs(L277 - L297)

Critical Safety Invariants

The implementation maintains several critical invariants that ensure memory safety:

Bitmap-Memory Synchronization: id_bitmap.get(i) == true if and only if objects[i] is initialized
Count Consistency: count equals id_bitmap.into_iter().count()
Bounds Safety: All array access is bounds-checked against CAP
Initialization Ordering: id_bitmap.set(id, true) occurs before objects[id].write(value)
Deinitialization Ordering: id_bitmap.set(id, false) occurs after objects[id].assume_init_read()

These invariants are maintained through careful ordering in methods like add(), remove(), and add_or_replace_at().

Sources: src/lib.rs(L225 - L228) src/lib.rs(L253 - L256) src/lib.rs(L317 - L322)

Capacity Constraints and Compilation

The CAP parameter is constrained by the bitmaps crate's Bits trait implementation, which currently supports capacities up to 1024. This constraint is enforced at compile time through the trait bound BitsImpl<{CAP}>: Bits.

The new() method includes a runtime panic for capacities exceeding 1024, providing clear error messaging during development while maintaining const fn compatibility.

Sources: src/lib.rs(L46) src/lib.rs(L59 - L61) src/lib.rs(L77)

ArceOS Crates Book