diff options
| -rw-r--r-- | core/container/handle_map/doc.odin | 56 | ||||
| -rw-r--r-- | core/container/handle_map/dynamic_handle_map.odin | 141 | ||||
| -rw-r--r-- | core/container/handle_map/static_handle_map.odin | 221 | ||||
| -rw-r--r-- | core/container/xar/xar.odin | 15 | ||||
| -rw-r--r-- | examples/all/all_main.odin | 7 |
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" |