Add `Dynamic_Handle_Map`

3 files changed, 174 insertions, 31 deletions

diff --git a/core/container/handle_map/doc.odin b/core/container/handle_map/doc.odin
new file mode 100644
index 000000000..e6ef0b344
--- /dev/null
+++ b/core/container/handle_map/doc.odin
@@ -0,0 +1,32 @@
+/*
+Handle-based map using fixed-length arrays.
+
+Example:
+	import hm "core:container/handle_map"
+
+	Handle :: hm.Handle32
+
+	Entity :: struct {
+		handle: Handle,
+		pos:    [2]f32,
+	}
+
+	entities: hm.Handle_Map(1024, Entity, Handle)
+
+	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}})
+
+	it := hm.iterator_make(&entities)
+	for e, h in hm.iterate(&it) {
+		e.pos += {1, 2}
+	}
+*/
+package container_handle_map
\ No newline at end of file
diff --git a/core/container/handle_map/dynamic_handle_map.odin b/core/container/handle_map/dynamic_handle_map.odin
new file mode 100644
index 000000000..c754f2f25
--- /dev/null
+++ b/core/container/handle_map/dynamic_handle_map.odin
@@ -0,0 +1,142 @@
+package container_handle_map
+
+import "base:builtin"
+import "base:runtime"
+import "base:intrinsics"
+import "core:container/xar"
+
+
+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),
+	unused_items: xar.Array(u32, 4),
+}
+
+dynamic_init :: proc(m: ^$D/Dynamic_Handle_Map($T, $Handle_Type), allocator: runtime.Allocator) {
+	xar.init(&m.items,        allocator)
+	xar.init(&m.unused_items, allocator)
+}
+
+dynamic_destroy :: proc(m: ^$D/Dynamic_Handle_Map($T, $Handle_Type)) {
+	xar.destroy(&m.unused_items)
+	xar.destroy(&m.items)
+}
+
+@(require_results)
+dynamic_add :: proc(m: ^$D/Dynamic_Handle_Map($T, $Handle_Type), item: T, loc := #caller_location) -> (handle: Handle_Type, err: runtime.Allocator_Error) {
+	if xar.len(m.unused_items) > 0 {
+		i := xar.pop(&m.unused_items)
+		ptr := xar.get_ptr(&m.items, i, loc)
+		prev_gen := ptr.handle.gen
+		ptr^ = item
+
+		ptr.handle.idx = auto_cast i
+		ptr.handle.gen = auto_cast (prev_gen + 1)
+		return ptr.handle, nil
+	}
+
+	if xar.len(m.items) == 0 {
+		// initialize the zero-value sentinel
+		xar.append(&m.items, T{}, loc) or_return
+	}
+
+	i := xar.append(&m.items, item, loc) or_return
+
+	ptr := xar.get_ptr(&m.items, i, loc)
+	ptr^ = item
+
+	ptr.handle.idx = auto_cast i
+	ptr.handle.gen = 1
+	return ptr.handle, nil
+}
+
+@(require_results)
+dynamic_get :: proc(m: ^$D/Dynamic_Handle_Map($T, $Handle_Type), h: Handle_Type) -> (^T, bool) #optional_ok {
+	if h.idx <= 0 || int(u32(h.idx)) >= xar.len(m.items) {
+		return nil, false
+	}
+	if e := xar.get_ptr(&m.items, h.idx); e.handle == h {
+		return e, true
+	}
+	return nil, false
+}
+
+dynamic_remove :: proc(m: ^$D/Dynamic_Handle_Map($T, $Handle_Type), h: Handle_Type, loc := #caller_location) -> (found: bool, err: runtime.Allocator_Error) {
+	if h.idx <= 0 || int(u32(h.idx)) >= xar.len(m.items) {
+		return false, nil
+	}
+
+	if item := xar.get_ptr(&m.items, h.idx); item.handle == h {
+		xar.append(&m.unused_items, u32(h.idx), loc) or_return
+		item.handle.idx = 0
+		return true, nil
+	}
+
+	return false, nil
+}
+
+@(require_results)
+dynamic_is_valid :: proc(m: ^$D/Dynamic_Handle_Map($T, $Handle_Type), h: Handle_Type, loc := #caller_location) -> bool {
+	return h.idx > 0 && int(u32(h.idx)) < xar.len(m.items) && xar.get(&m.items, h.idx, loc).handle == h
+}
+
+// Returns the number of possibly valid items in the handle map.
+@(require_results)
+dynamic_len :: proc(m: $D/Dynamic_Handle_Map($T, $Handle_Type)) -> uint {
+	n := xar.len(m.items) - xar.len(m.unused_items)
+	return uint(n-1 if n > 0 else 0)
+}
+
+@(require_results)
+dynamic_cap :: proc(m: $D/Dynamic_Handle_Map($T, $Handle_Type)) -> uint {
+	n := xar.cap(m.items)
+	return uint(n-1 if n > 0 else 0)
+}
+
+dynamic_clear :: proc(m: ^$D/Dynamic_Handle_Map($T, $Handle_Type)) {
+	xar.clear(&m.items)
+	xar.clear(&m.unused_items)
+}
+
+
+// An iterator for a handle map.
+Dynamic_Handle_Map_Iterator :: struct($D: typeid) {
+	m:     ^D,
+	index: int,
+}
+
+// Makes an iterator from a handle map.
+@(require_results)
+dynamic_iterator_make :: proc(m: ^$D/Dynamic_Handle_Map($T, $Handle_Type)) -> Dynamic_Handle_Map_Iterator(D) {
+	return {m, 1}
+}
+
+/*
+	Iterate over a handle map. It will skip over unused item slots (e.g. handle.idx == 0).
+	Usage:
+		it := hm.dynamic_iterator_make(&the_dynamic_handle_map)
+		for item, handle in hm.iterate(&it) {
+			...
+		}
+*/
+@(require_results)
+dynamic_iterate :: proc(it: ^$DHI/Dynamic_Handle_Map_Iterator($D/Dynamic_Handle_Map($T, $Handle_Type))) -> (val: ^T, h: Handle_Type, ok: bool) {
+	for _ in it.index..<xar.len(it.m.items) {
+		e := xar.get_ptr(&it.m.items, it.index)
+		it.index += 1
+
+		if e.handle.idx != 0 {
+			return e, e.handle, true
+		}
+	}
+	return
+}
\ No newline at end of file
diff --git a/core/container/handle_map/handle_map.odin b/core/container/handle_map/handle_map.odin
index 37b8de9f6..485371d42 100644
--- a/core/container/handle_map/handle_map.odin
+++ b/core/container/handle_map/handle_map.odin
@@ -1,34 +1,3 @@
-/*
-Handle-based map using fixed-length arrays.
-
-Example:
-	import hm "core:container/handle_map"
-
-	Handle :: hm.Handle32
-
-	Entity :: struct {
-		handle: Handle,
-		pos:    [2]f32,
-	}
-
-	entities: hm.Handle_Map(1024, Entity, Handle)
-
-	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}})
-
-	it := hm.iterator_make(&entities)
-	for e, h in hm.iterate(&it) {
-		e.pos += {1, 2}
-	}
-*/
 package container_handle_map
 
 import "base:builtin"