Merge pull request #6177 from odin-lang/bill/handle-map

`core:container/handle_map`

5 files changed, 433 insertions, 7 deletions

diff --git a/core/container/handle_map/doc.odin b/core/container/handle_map/doc.odin
new file mode 100644
index 000000000..c1949ffdd
--- /dev/null
+++ b/core/container/handle_map/doc.odin
@@ -0,0 +1,56 @@
+/*
+Handle-based map using fixed-length arrays.
+
+Example:
+	import hm "core:container/handle_map"
+
+	Handle :: hm.Handle32
+
+	Entity :: struct {
+		handle: Handle,
+		pos:    [2]f32,
+	}
+
+	{ // static map
+		entities: hm.Static_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}
+		}
+	}
+
+	{ // 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}})
+
+		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..067212a54
--- /dev/null
+++ b/core/container/handle_map/dynamic_handle_map.odin
@@ -0,0 +1,141 @@
+package container_handle_map
+
+import "base:runtime"
+import "base:builtin"
+import "base:intrinsics"
+@(require) 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_unsafe(&m.items, i)
+		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_unsafe(&m.items, i)
+	ptr^ = item
+
+	ptr.handle.idx = auto_cast i
+	ptr.handle.gen = 1
+	return ptr.handle, nil
+}
+
+@(require_results)
+dynamic_get :: proc "contextless" (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_unsafe(&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 "contextless" (m: ^$D/Dynamic_Handle_Map($T, $Handle_Type), h: Handle_Type) -> bool {
+	return h.idx > 0 && int(u32(h.idx)) < xar.len(m.items) && xar.get_ptr_unsafe(&m.items, h.idx).handle == h
+}
+
+// Returns the number of possibly valid items in the handle map.
+@(require_results)
+dynamic_len :: proc "contextless" (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 "contextless" (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 "contextless" (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 "contextless" (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 "contextless" (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_unsafe(&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/static_handle_map.odin b/core/container/handle_map/static_handle_map.odin
new file mode 100644
index 000000000..f308c5e95
--- /dev/null
+++ b/core/container/handle_map/static_handle_map.odin
@@ -0,0 +1,221 @@
+package container_handle_map
+
+import "base:builtin"
+import "base:intrinsics"
+
+// Default 16-bit Handle type which can be used for handle maps which only need a maximum of 254 (1<<8 - 2) items
+Handle16 :: struct {
+	idx: u8,
+	gen: u8,
+}
+
+// Default 32-bit Handle type which can be used for handle maps which only need a maximum of 65534 (1<<16 - 2) items
+Handle32 :: struct {
+	idx: u16,
+	gen: u16,
+}
+
+// Default 64-bit Handle type which can be used for handle maps which only need a maximum of 4294967294 (1<<32 - 2) items
+Handle64 :: struct {
+	idx: u32,
+	gen: u32,
+}
+
+Static_Handle_Map :: struct($N: uint, $T: typeid, $Handle_Type: typeid)
+	where
+		0 < N, N < uint(1<<31 - 1),
+
+		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"),
+
+		N < uint(max(intrinsics.type_field_type(Handle_Type, "idx"))),
+
+		intrinsics.type_has_field (T, "handle"),
+		intrinsics.type_field_type(T, "handle") == Handle_Type {
+
+	// The zero element represent a zero-value sentinel (dummy value), allowing for `idx == 0` to mean a no-handle.
+	// This means the capacity is actually N-1 items.
+	items: [N]T,
+
+	used_len:     u32, // How many of the items are in use
+	unused_len:   u32, // Use to calculate the number of valid items
+	unused_items: [N]u32,
+	next_unused:  u32,
+}
+
+
+// `add` a value of type `T` to the handle map. This will return a pointer to the item and an optional boolean to check for validity.
+@(require_results)
+static_add :: proc "contextless" (m: ^$H/Static_Handle_Map($N, $T, $Handle_Type), item: T) -> (handle: Handle_Type, ok: bool) #optional_ok {
+	if i := m.next_unused; i != 0 {
+		ptr := &m.items[i]
+
+		m.next_unused = m.unused_items[i]
+		m.unused_items[i] = 0
+
+		prev_gen := ptr.handle.gen
+		ptr^ = item
+
+		ptr.handle.idx = auto_cast i
+		ptr.handle.gen = auto_cast (prev_gen + 1)
+		m.unused_len -= 1
+		return ptr.handle, true
+	}
+
+	if m.used_len == 0 {
+		// initialize the zero-value sentinel
+		m.items[0] = {}
+		m.used_len += 1
+	}
+
+	if m.used_len == builtin.len(m.items) {
+		return {}, false
+	}
+
+	ptr := &m.items[m.used_len]
+	ptr^ = item
+
+	ptr.handle.idx = auto_cast m.used_len
+	ptr.handle.gen = 1
+	m.used_len += 1
+	return ptr.handle, true
+}
+
+// `get` a stable pointer of type `^T` by resolving the handle `h`. If the handle is not valid, then `nil, false` is returned.
+@(require_results)
+static_get :: proc "contextless" (m: ^$H/Static_Handle_Map($N, $T, $Handle_Type), h: Handle_Type) -> (^T, bool) #optional_ok {
+	if h.idx <= 0 || u32(h.idx) >= m.used_len {
+		return nil, false
+	}
+	if e := &m.items[h.idx]; e.handle == h {
+		return e, true
+	}
+	return nil, false
+}
+
+// `remove` an item from the handle map from the handle `h`.
+static_remove :: proc "contextless" (m: ^$H/Static_Handle_Map($N, $T, $Handle_Type), h: Handle_Type) -> bool {
+	if h.idx <= 0 || u32(h.idx) >= m.used_len {
+		return false
+	}
+
+	if item := &m.items[h.idx]; item.handle == h {
+		m.unused_items[h.idx] = m.next_unused
+		m.next_unused = u32(h.idx)
+		m.unused_len += 1
+		item.handle.idx = 0
+		return true
+	}
+
+	return false
+}
+
+// Returns true when the handle `h` is valid relating to the handle map.
+@(require_results)
+static_is_valid :: proc "contextless" (m: $H/Static_Handle_Map($N, $T, $Handle_Type), h: Handle_Type) -> bool {
+	return h.idx > 0 && u32(h.idx) < m.used_len && m.items[h.idx].handle == h
+}
+
+// Returns the number of possibly valid items in the handle map.
+@(require_results)
+static_len :: proc "contextless" (m: $H/Static_Handle_Map($N, $T, $Handle_Type)) -> uint {
+	n := uint(m.used_len) - uint(m.unused_len)
+	return n-1 if n > 0 else 0
+}
+
+// Returns the capacity of the items in a handle map.
+// This is equivalent to `N-1` as the zero value is reserved for the zero-value sentinel.
+@(require_results)
+static_cap :: proc "contextless" (m: $H/Static_Handle_Map($N, $T, $Handle_Type)) -> uint {
+	// We could just return `N` but I am doing this for clarity
+	return builtin.len(m.items)-1
+}
+
+// `clear` the handle map by zeroing all of the memory.
+// Internally this does not do `m^ = {}` but rather uses `intrinsics.mem_zero` explicitly improve performance.
+static_clear :: proc "contextless" (m: ^$H/Static_Handle_Map($N, $T, $Handle_Type)) {
+	intrinsics.mem_zero(m, size_of(m^))
+}
+
+// An iterator for a handle map.
+Static_Handle_Map_Iterator :: struct($H: typeid) {
+	m:     ^H,
+	index: u32,
+}
+
+// Makes an iterator from a handle map.
+@(require_results)
+static_iterator_make :: proc "contextless" (m: ^$H/Static_Handle_Map($N, $T, $Handle_Type)) -> Static_Handle_Map_Iterator(H) {
+	return {m, 1}
+}
+
+/*
+	Iterate over a handle map. It will skip over unused item slots (e.g. handle.idx == 0).
+	Usage:
+		it := hm.iterator_make(&the_handle_map)
+		for item, handle in hm.iterate(&it) {
+			...
+		}
+*/
+@(require_results)
+static_iterate :: proc "contextless" (it: ^$HI/Static_Handle_Map_Iterator($H/Static_Handle_Map($N, $T, $Handle_Type))) -> (val: ^T, h: Handle_Type, ok: bool) {
+	for _ in it.index..<it.m.used_len {
+		e := &it.m.items[it.index]
+		it.index += 1
+
+		if e.handle.idx != 0 {
+			return e, e.handle, true
+		}
+	}
+	return
+}
+
+
+
+add :: proc{
+	static_add,
+	dynamic_add,
+}
+
+get :: proc{
+	static_get,
+	dynamic_get,
+}
+
+remove :: proc{
+	static_remove,
+	dynamic_remove,
+}
+
+is_valid :: proc{
+	static_is_valid,
+	dynamic_is_valid,
+}
+
+len :: proc{
+	static_len,
+	dynamic_len,
+}
+
+cap :: proc{
+	static_cap,
+	dynamic_cap,
+}
+
+clear :: proc{
+	static_clear,
+	dynamic_clear,
+}
+
+iterator_make :: proc{
+	static_iterator_make,
+	dynamic_iterator_make,
+}
+
+iterate :: proc{
+	static_iterate,
+	dynamic_iterate,
+}
diff --git a/core/container/xar/xar.odin b/core/container/xar/xar.odin
index 07fdf5a15..556f93ee5 100644
--- a/core/container/xar/xar.odin
+++ b/core/container/xar/xar.odin
@@ -109,19 +109,19 @@ destroy :: proc(x: ^$X/Array($T, $SHIFT)) {
 Resets the array's length to zero without freeing memory.
 Allocated chunks are retained for reuse.
 */
-clear :: proc(x: ^$X/Array($T, $SHIFT)) {
+clear :: proc "contextless" (x: ^$X/Array($T, $SHIFT)) {
 	x.len = 0
 }
 
 // Returns the length of the exponential-array
 @(require_results)
-len :: proc(x: $X/Array($T, $SHIFT)) -> int {
+len :: proc "contextless" (x: $X/Array($T, $SHIFT)) -> int {
 	return x.len
 }
 
 // Returns the number of allocated elements
 @(require_results)
-cap :: proc(x: $X/Array($T, $SHIFT)) -> int {
+cap :: proc "contextless" (x: $X/Array($T, $SHIFT)) -> int {
 	#reverse for c, i in x.chunks {
 		if c != nil {
 			return 1 << (SHIFT + uint(i if i > 0 else 1))
@@ -132,7 +132,7 @@ cap :: proc(x: $X/Array($T, $SHIFT)) -> int {
 
 // Internal: computes chunk index, element index within chunk, and chunk capacity for a given index.
 @(require_results)
-_meta_get :: #force_inline proc($SHIFT: uint, index: uint) -> (chunk_idx, elem_idx, chunk_cap: uint) {
+_meta_get :: #force_inline proc "contextless" ($SHIFT: uint, index: uint) -> (chunk_idx, elem_idx, chunk_cap: uint) {
 	elem_idx = index
 	chunk_cap = uint(1) << SHIFT
 	chunk_idx = 0
@@ -206,6 +206,13 @@ get_ptr :: proc(x: ^$X/Array($T, $SHIFT), #any_int index: int, loc := #caller_lo
 	return &x.chunks[chunk_idx][elem_idx]
 }
 
+// No bounds checking
+@(require_results)
+get_ptr_unsafe :: proc "contextless" (x: ^$X/Array($T, $SHIFT), #any_int index: int) -> (val: ^T) #no_bounds_check {
+	chunk_idx, elem_idx, _ := _meta_get(SHIFT, uint(index))
+	return &x.chunks[chunk_idx][elem_idx]
+}
+
 /*
 Set the element at the specified index to the given value.
 
diff --git a/examples/all/all_main.odin b/examples/all/all_main.odin
index a7f230022..c5f627653 100644
--- a/examples/all/all_main.odin
+++ b/examples/all/all_main.odin
@@ -17,13 +17,14 @@ package all
 
 @(require) import "core:container/avl"
 @(require) import "core:container/bit_array"
+@(require) import "core:container/handle_map"
+@(require) import "core:container/intrusive/list"
+@(require) import "core:container/lru"
 @(require) import "core:container/pool"
 @(require) import "core:container/priority_queue"
 @(require) import "core:container/queue"
-@(require) import "core:container/small_array"
-@(require) import "core:container/lru"
-@(require) import "core:container/intrusive/list"
 @(require) import "core:container/rbtree"
+@(require) import "core:container/small_array"
 @(require) import "core:container/topological_sort"
 @(require) import "core:container/xar"