ID Management System

Relevant source files

Cargo.toml

src/lib.rs

This document covers the bitmap-based ID allocation and management system used by FlattenObjects to assign unique identifiers to stored objects. The system provides efficient ID allocation, reuse, and tracking using a bitmap data structure from the external bitmaps crate.

For information about the overall container architecture, see Internal Data Structures. For details about memory safety and object lifecycle, see Memory Management and Safety.

Core ID Management Architecture

The ID management system centers around a bitmap that tracks which IDs are currently assigned. Each bit position corresponds to a potential object ID, with true indicating an assigned ID and false indicating an available ID.

flowchart TD
subgraph subGraph2["ID Operations"]
    add_op["add()"]
    add_at_op["add_at(id, value)"]
    remove_op["remove(id)"]
    is_assigned_op["is_assigned(id)"]
end
subgraph subGraph1["bitmaps Crate"]
    Bitmap["Bitmap"]
    BitsImpl["BitsImpl: Bits"]
    first_false_index["first_false_index()"]
    get_method["get(id: usize)"]
    set_method["set(id: usize, value: bool)"]
    into_iter["into_iter() -> Iter"]
end
subgraph subGraph0["FlattenObjects"]
    id_bitmap["id_bitmap: Bitmap"]
    objects["objects: [MaybeUninit; CAP]"]
    count["count: usize"]
end

Bitmap --> BitsImpl
add_at_op --> get_method
add_op --> first_false_index
first_false_index --> objects
id_bitmap --> Bitmap
is_assigned_op --> get_method
objects --> count
remove_op --> set_method
set_method --> count
set_method --> objects

Bitmap-based ID Management

Sources: src/lib.rs(L34) src/lib.rs(L49) Cargo.toml(L16)

ID Allocation Algorithm

The system uses a "first-fit" allocation strategy where new objects receive the smallest available ID. This is implemented through the first_false_index() method from the bitmaps crate.

flowchart TD
add_call["add(value: T)"]
find_id["id_bitmap.first_false_index()"]
check_cap["id < CAP?"]
check_available["ID available?"]
assign_id["id_bitmap.set(id, true)"]
write_object["objects[id].write(value)"]
increment_count["count += 1"]
return_ok["return Ok(id)"]
return_err["return Err(value)"]

add_call --> find_id
assign_id --> write_object
check_available --> assign_id
check_available --> return_err
check_cap --> check_available
check_cap --> return_err
find_id --> check_cap
increment_count --> return_ok
write_object --> increment_count

ID Allocation Flow

Sources: src/lib.rs(L222 - L232) src/lib.rs(L223) src/lib.rs(L226)

ID State Transitions

Each ID in the system can be in one of two states, tracked by the corresponding bitmap bit. The state transitions occur during object lifecycle operations.

Operation	Bitmap Bit Change	Count Change	Object Array Effect
add()	false→true	+1	MaybeUninit::uninit()→MaybeUninit::new(value)
add_at(id)	false→true	+1	MaybeUninit::uninit()→MaybeUninit::new(value)
remove(id)	true→false	-1	MaybeUninit::new(value)→MaybeUninit::uninit()
add_or_replace_at(id)	unchanged	0or+1	Replaces existing value

ID State Transition Table

Sources: src/lib.rs(L226) src/lib.rs(L254) src/lib.rs(L317) src/lib.rs(L292)

Bitmap Integration Details

The system integrates with the bitmaps crate v3.2, which provides efficient bitmap operations with compile-time size verification through the Bits trait constraint.

flowchart TD
subgraph subGraph2["FlattenObjects Methods"]
    CAP["const CAP: usize"]
    BitsImpl_CAP["BitsImpl<{CAP}>"]
    Bits_trait["Bits trait"]
    add_method["add()"]
    is_assigned_method["is_assigned()"]
    remove_method["remove()"]
    ids_method["ids()"]
end
subgraph subGraph1["Bitmap Operations"]
    first_false["first_false_index() -> Option"]
    get_bit["get(index: usize) -> bool"]
    set_bit["set(index: usize, value: bool)"]
    iter_bits["into_iter() -> Iter"]
end
subgraph subGraph0["Type Constraints"]
    CAP["const CAP: usize"]
    BitsImpl_CAP["BitsImpl<{CAP}>"]
    Bits_trait["Bits trait"]
    add_method["add()"]
    is_assigned_method["is_assigned()"]
    remove_method["remove()"]
end

BitsImpl_CAP --> Bits_trait
CAP --> BitsImpl_CAP
add_method --> first_false
ids_method --> iter_bits
is_assigned_method --> get_bit
remove_method --> set_bit

Bitmap Integration Architecture

Sources: src/lib.rs(L46) src/lib.rs(L34) src/lib.rs(L144 - L146) src/lib.rs(L344 - L346)

ID Reuse Strategy

The system implements immediate ID reuse - when an object is removed, its ID becomes immediately available for the next allocation. This is achieved by setting the corresponding bitmap bit to false.

sequenceDiagram
    participant Client as Client
    participant FlattenObjects as FlattenObjects
    participant id_bitmap as id_bitmap
    participant objects_array as objects_array

    Client ->> FlattenObjects: add(value1)
    FlattenObjects ->> id_bitmap: first_false_index()
    id_bitmap -->> FlattenObjects: Some(0)
    FlattenObjects ->> id_bitmap: set(0, true)
    FlattenObjects ->> objects_array: objects[0].write(value1)
    FlattenObjects -->> Client: Ok(0)
    Client ->> FlattenObjects: add(value2)
    FlattenObjects ->> id_bitmap: first_false_index()
    id_bitmap -->> FlattenObjects: Some(1)
    FlattenObjects ->> id_bitmap: set(1, true)
    FlattenObjects ->> objects_array: objects[1].write(value2)
    FlattenObjects -->> Client: Ok(1)
    Client ->> FlattenObjects: remove(0)
    FlattenObjects ->> id_bitmap: set(0, false)
    FlattenObjects ->> objects_array: objects[0].assume_init_read()
    FlattenObjects -->> Client: Some(value1)
    Client ->> FlattenObjects: add(value3)
    FlattenObjects ->> id_bitmap: first_false_index()
    id_bitmap -->> FlattenObjects: Some(0)
    Note over FlattenObjects: ID 0 is reused
    FlattenObjects ->> id_bitmap: set(0, true)
    FlattenObjects ->> objects_array: objects[0].write(value3)
    FlattenObjects -->> Client: Ok(0)

ID Reuse Sequence

Sources: src/lib.rs(L315 - L326) src/lib.rs(L317) src/lib.rs(L322)

Capacity Constraints and Limitations

The ID management system has several built-in constraints that ensure safe operation within the bounds of the bitmaps crate implementation.

Maximum Capacity Constraint

The system enforces a maximum capacity of 1024 objects, which is a limitation of the underlying bitmaps crate implementation.

flowchart TD
CAP_check["CAP <= 1024?"]
compile_success["Compilation succeeds"]
compile_fail["Compilation fails"]
BitsImpl_constraint["BitsImpl<{CAP}>: Bits"]

BitsImpl_constraint --> compile_success
CAP_check --> BitsImpl_constraint
CAP_check --> compile_fail

Capacity Constraint Validation

Sources: src/lib.rs(L42 - L43) src/lib.rs(L61) src/lib.rs(L75 - L76)

ID Range Validation

All ID operations include bounds checking to ensure IDs remain within the valid range <FileRef file-url="https://github.com/arceos-org/flatten_objects/blob/ac0a74b9/0, CAP).\n\n| Method | ID Validation | Behavior on Invalid ID |\n|--------|---------------|----------------------|\n| is_assigned(id) | id < CAP | Returns false |\n| add_at(id, value) | id >= CAP | Returns Err(value) |\n| add_or_replace_at(id, value) | id >= CAP | Returns Err(None) |\n| get(id) / get_mut(id) | Via is_assigned(id) | Returns None |\n\nID Validation Table\n\nSources#LNaN-LNaN" NaN file-path="0, CAP).\n\n| Method | ID Validation | Behavior on Invalid ID |\n|--------|---------------|----------------------|\n|is_assigned(id)|id < CAP| Returnsfalse|\n|add_at(id, value)|id >= CAP| ReturnsErr(value)|\n|add_or_replace_at(id, value)|id >= CAP| ReturnsErr(None)|\n|get(id)/get_mut(id)| Viais_assigned(id)| ReturnsNone` |\n\nID Validation Table\n\nSources">Hii src/lib.rs(L250) src/lib.rs(L278)

Bitmap Initialization and Safety

The bitmap is initialized with zero values, ensuring all IDs start as available. This initialization uses unsafe code but is considered safe because zero-initialization is valid for integer arrays.

// From new() method - line 81
id_bitmap: unsafe { MaybeUninit::zeroed().assume_init() }

The zero-initialization strategy ensures:

All bitmap bits start as false (available)
No undefined behavior from uninitialized memory
Deterministic initial state for ID allocation

Sources: src/lib.rs(L80 - L82)

Iterator Support

The system provides iteration over assigned IDs through the ids() method, which returns an iterator from the underlying bitmap.

flowchart TD
ids_method["ids() -> Iter"]
bitmap_iter["id_bitmap.into_iter()"]
assigned_ids["Iterator over assigned IDs"]
note1["Only returns IDs where bitmap bit = true"]

assigned_ids --> note1
bitmap_iter --> assigned_ids
ids_method --> bitmap_iter

ID Iterator Implementation

Sources: src/lib.rs(L344 - L346)

ArceOS Crates Book