Allocator not passed as a parameter on "core:container/handle_map" procedures

Explain
1

Why do procedures that allocate memory within the “core:container/handle_map” package, like dynamic_add, not pass the allocator as a parameter?

For example, dynamic_add is defined as:

dynamic_add :: proc(m: ^$D/Dynamic_Handle_Map($T, $Handle_Type), item: T, loc := #caller_location) → (handle: Handle_Type, err: runtime.Allocator_Error) #optional_allocator_error {…}

instead of:

dynamic_add :: proc(m: ^$D/Dynamic_Handle_Map($T, $Handle_Type), item: T, allocator := context.allocator, loc := #caller_location) → (handle: Handle_Type, err: runtime.Allocator_Error) #optional_allocator_error {…}

Neither do the underlying exponential array’s procedures pass the allocator as a parameter. I think it would be more convenient if they did, to no extra cost.

2

Short Answer:

Memory is allocated for the Dynamic Handle Map when initialized and the allocator used is stored within the underlying array. When you call dynamic_add. the data being added is copied into the existing memory of the map’s backing array and no external allocations are required for this process. Thus, no need for an allocator to be passed into the procedure.

Longer Answer:

Consider the overview from core:container/handle_map and some of the underlying procedures and data types:

Handle-based map using either fixed-length arrays, or exponential arrays from “core:container/xar”.

// https://pkg.odin-lang.org/core/container/handle_map/#dynamic_add
dynamic_add :: proc(m: ^$D/Dynamic_Handle_Map($T, $Handle_Type), item: $T, loc := #caller_location) -> (handle: $$deferred_return, err: runtime.Allocator_Error) #optional_ok {…}

// https://github.com/odin-lang/Odin/blob/master/core/container/handle_map/dynamic_handle_map.odin#L8
Dynamic_Handle_Map :: struct($T: typeid, $Handle_Type: typeid)
	where
		intrinsics.type_has_field(Handle_Type, "idx"),
		intrinsics.type_has_field(Handle_Type, "gen"),
		intrinsics.type_is_unsigned(intrinsics.type_field_type(Handle_Type, "idx")),
		intrinsics.type_is_unsigned(intrinsics.type_field_type(Handle_Type, "gen")),
		intrinsics.type_field_type(Handle_Type, "idx") == intrinsics.type_field_type(Handle_Type, "gen"),

		intrinsics.type_has_field (T, "handle"),
		intrinsics.type_field_type(T, "handle") == Handle_Type {

	items:        xar.Array(T, 4), // <-- underlying exponential array
	unused_items: xar.Array(u32, 4),  
}

Now when you combine that with the overview from core:container/xar and the definition for xar.Array, things should become more clear.

Exponential Array (Xar).
A dynamically growing array using exponentially-sized chunks, providing stable memory addresses for all elements. Unlike [dynamic]T, elements are never moved once allocated, making it safe to hold pointers to elements.
For more information: A Survey of Dynamic Array Structures

// https://github.com/odin-lang/Odin/blob/master/core/container/xar/xar.odin#L72
Array :: struct($T: typeid, $SHIFT: uint) where 0 < SHIFT, SHIFT <= MAX_SHIFT {
	chunks:    [(1 << (_LOG2_PLATFORM_BITS - intrinsics.constant_log2(SHIFT))) + 1][^]T,
	len:       int,
	allocator: runtime.Allocator,
}

Once you initialize a Dynamic_Handle_Map, the underlying data structure of xar.Arrays will store the allocator used. Making any additional allocations is unnecessary as the data is copied into the array and does not require any allocations outside of potentially expanding the exponential array itself. The exponential array will use the stored allocator to acquire the additional memory chunks needed to expand.

Also when consulting the example code found in the overview, there is an indication that one should prefer the procedure groups, like add, over of the specific procedure, like dynamic_add, when possible.

{ // dynamic map
	entities: hm.Dynamic_Handle_Map(Entity, Handle)
	hm.dynamic_init(&entities, context.allocator)
	defer hm.dynamic_destroy(&entities)

	h1 := hm.add(&entities, Entity{pos = {1,  4}})
	h2 := hm.add(&entities, Entity{pos = {9, 16}})

	if e, ok := hm.get(&entities, h2); ok {
		e.pos.x += 32
	}

	hm.remove(&entities, h1)

	h3 := hm.add(&entities, Entity{pos = {6, 7}})
	assert(hm.is_valid(entities, h3))

	it := hm.iterator_make(&entities)
	for e, h in hm.iterate(&it) {
		assert(hm.is_valid(entities, h))
		e.pos += {1, 2}
	}
}
3 Likes