From 001b2b9d8f021eb88db82d7a4cce47c6cdaf44de Mon Sep 17 00:00:00 2001 From: Feoramund <161657516+Feoramund@users.noreply.github.com> Date: Tue, 3 Sep 2024 05:40:10 -0400 Subject: Let `bit_array.create` make zero-length arrays --- core/container/bit_array/bit_array.odin | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'core/container/bit_array/bit_array.odin') diff --git a/core/container/bit_array/bit_array.odin b/core/container/bit_array/bit_array.odin index b53bacda7..61119ef96 100644 --- a/core/container/bit_array/bit_array.odin +++ b/core/container/bit_array/bit_array.odin @@ -275,7 +275,7 @@ create :: proc(max_index: int, min_index: int = 0, allocator := context.allocato context.allocator = allocator size_in_bits := max_index - min_index - if size_in_bits < 1 { return {}, false } + if size_in_bits < 0 { return {}, false } legs := size_in_bits >> INDEX_SHIFT if size_in_bits & INDEX_MASK > 0 {legs+=1} -- cgit v1.2.3 From b8f8cb95823e0e56e0d8fd6ace5b38d9d57d03ff Mon Sep 17 00:00:00 2001 From: Feoramund <161657516+Feoramund@users.noreply.github.com> Date: Tue, 3 Sep 2024 06:02:18 -0400 Subject: Add `bit_array.shrink` --- core/container/bit_array/bit_array.odin | 30 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+) (limited to 'core/container/bit_array/bit_array.odin') diff --git a/core/container/bit_array/bit_array.odin b/core/container/bit_array/bit_array.odin index 61119ef96..b1149e82e 100644 --- a/core/container/bit_array/bit_array.odin +++ b/core/container/bit_array/bit_array.odin @@ -1,5 +1,6 @@ package container_dynamic_bit_array +import "base:builtin" import "base:intrinsics" import "core:mem" @@ -299,6 +300,35 @@ clear :: proc(ba: ^Bit_Array) { mem.zero_slice(ba.bits[:]) } /* +Shrinks the Bit_Array's backing storage to the smallest possible size. + +Inputs: +- ba: The target Bit_Array +*/ +shrink :: proc(ba: ^Bit_Array) #no_bounds_check { + if ba == nil { return } + legs_needed := len(ba.bits) + for i := legs_needed - 1; i >= 0; i -= 1 { + if ba.bits[i] == 0 { + legs_needed -= 1 + } else { + break + } + } + if legs_needed == len(ba.bits) { + return + } + ba.max_index = 0 + if legs_needed > 0 { + if legs_needed > 1 { + ba.max_index = (legs_needed - 1) * NUM_BITS + } + ba.max_index += NUM_BITS - 1 - int(intrinsics.count_leading_zeros(ba.bits[legs_needed - 1])) + } + resize(&ba.bits, legs_needed) + builtin.shrink(&ba.bits) +} +/* Deallocates the Bit_Array and its backing storage Inputs: -- cgit v1.2.3 From d86e56089a3435990dcfa88b16805062c152d350 Mon Sep 17 00:00:00 2001 From: Feoramund <161657516+Feoramund@users.noreply.github.com> Date: Tue, 3 Sep 2024 15:34:14 -0400 Subject: Fix iteration of biased `Bit_Array` --- core/container/bit_array/bit_array.odin | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'core/container/bit_array/bit_array.odin') diff --git a/core/container/bit_array/bit_array.odin b/core/container/bit_array/bit_array.odin index b1149e82e..70ea6ec77 100644 --- a/core/container/bit_array/bit_array.odin +++ b/core/container/bit_array/bit_array.odin @@ -53,7 +53,7 @@ Returns: */ iterate_by_all :: proc (it: ^Bit_Array_Iterator) -> (set: bool, index: int, ok: bool) { index = it.word_idx * NUM_BITS + int(it.bit_idx) + it.array.bias - if index > it.array.max_index { return false, 0, false } + if index > it.array.max_index + it.array.bias { return false, 0, false } word := it.array.bits[it.word_idx] if len(it.array.bits) > it.word_idx else 0 set = (word >> it.bit_idx & 1) == 1 @@ -136,7 +136,7 @@ iterate_internal_ :: proc (it: ^Bit_Array_Iterator, $ITERATE_SET_BITS: bool) -> it.bit_idx = 0 it.word_idx += 1 } - return index, index <= it.array.max_index + return index, index <= it.array.max_index + it.array.bias } /* Gets the state of a bit in the bit-array @@ -285,7 +285,7 @@ create :: proc(max_index: int, min_index: int = 0, allocator := context.allocato res = new(Bit_Array) res.bits = bits res.bias = min_index - res.max_index = max_index + res.max_index = max_index - min_index res.free_pointer = true return } -- cgit v1.2.3 From c3bd94a27e46b93bf805db9c9eda4fba1bc7f796 Mon Sep 17 00:00:00 2001 From: Feoramund <161657516+Feoramund@users.noreply.github.com> Date: Tue, 3 Sep 2024 16:43:10 -0400 Subject: Change `Bit_Array.max_index` to `length` This will allow correct iteration of empty `bit_array`s. --- core/container/bit_array/bit_array.odin | 52 +++++++++++++++++++++------------ core/flags/internal_assignment.odin | 6 ++-- 2 files changed, 37 insertions(+), 21 deletions(-) (limited to 'core/container/bit_array/bit_array.odin') diff --git a/core/container/bit_array/bit_array.odin b/core/container/bit_array/bit_array.odin index 70ea6ec77..9a76dc78f 100644 --- a/core/container/bit_array/bit_array.odin +++ b/core/container/bit_array/bit_array.odin @@ -19,7 +19,7 @@ NUM_BITS :: 64 Bit_Array :: struct { bits: [dynamic]u64, bias: int, - max_index: int, + length: int, free_pointer: bool, } @@ -53,9 +53,9 @@ Returns: */ iterate_by_all :: proc (it: ^Bit_Array_Iterator) -> (set: bool, index: int, ok: bool) { index = it.word_idx * NUM_BITS + int(it.bit_idx) + it.array.bias - if index > it.array.max_index + it.array.bias { return false, 0, false } + if index >= it.array.length + it.array.bias { return false, 0, false } - word := it.array.bits[it.word_idx] if len(it.array.bits) > it.word_idx else 0 + word := it.array.bits[it.word_idx] if builtin.len(it.array.bits) > it.word_idx else 0 set = (word >> it.bit_idx & 1) == 1 it.bit_idx += 1 @@ -107,22 +107,22 @@ Returns: */ @(private="file") iterate_internal_ :: proc (it: ^Bit_Array_Iterator, $ITERATE_SET_BITS: bool) -> (index: int, ok: bool) { - word := it.array.bits[it.word_idx] if len(it.array.bits) > it.word_idx else 0 + word := it.array.bits[it.word_idx] if builtin.len(it.array.bits) > it.word_idx else 0 when ! ITERATE_SET_BITS { word = ~word } // If the word is empty or we have already gone over all the bits in it, // b.bit_idx is greater than the index of any set bit in the word, // meaning that word >> b.bit_idx == 0. - for it.word_idx < len(it.array.bits) && word >> it.bit_idx == 0 { + for it.word_idx < builtin.len(it.array.bits) && word >> it.bit_idx == 0 { it.word_idx += 1 it.bit_idx = 0 - word = it.array.bits[it.word_idx] if len(it.array.bits) > it.word_idx else 0 + word = it.array.bits[it.word_idx] if builtin.len(it.array.bits) > it.word_idx else 0 when ! ITERATE_SET_BITS { word = ~word } } // If we are iterating the set bits, reaching the end of the array means we have no more bits to check when ITERATE_SET_BITS { - if it.word_idx >= len(it.array.bits) { + if it.word_idx >= builtin.len(it.array.bits) { return 0, false } } @@ -136,7 +136,7 @@ iterate_internal_ :: proc (it: ^Bit_Array_Iterator, $ITERATE_SET_BITS: bool) -> it.bit_idx = 0 it.word_idx += 1 } - return index, index <= it.array.max_index + it.array.bias + return index, index < it.array.length + it.array.bias } /* Gets the state of a bit in the bit-array @@ -161,7 +161,7 @@ get :: proc(ba: ^Bit_Array, #any_int index: uint) -> (res: bool, ok: bool) #opti If we `get` a bit that doesn't fit in the Bit Array, it's naturally `false`. This early-out prevents unnecessary resizing. */ - if leg_index + 1 > len(ba.bits) { return false, true } + if leg_index + 1 > builtin.len(ba.bits) { return false, true } val := u64(1 << uint(bit_index)) res = ba.bits[leg_index] & val == val @@ -209,7 +209,7 @@ set :: proc(ba: ^Bit_Array, #any_int index: uint, set_to: bool = true, allocator resize_if_needed(ba, leg_index) or_return - ba.max_index = max(idx, ba.max_index) + ba.length = max(1 + idx, ba.length) if set_to { ba.bits[leg_index] |= 1 << uint(bit_index) @@ -262,6 +262,9 @@ unsafe_unset :: proc(b: ^Bit_Array, bit: int) #no_bounds_check { /* A helper function to create a Bit Array with optional bias, in case your smallest index is non-zero (including negative). +The range of bits created by this procedure is `min_index.. (length: int) { + if ba == nil { return } + return ba.length +} +/* Shrinks the Bit_Array's backing storage to the smallest possible size. Inputs: @@ -307,7 +323,7 @@ Inputs: */ shrink :: proc(ba: ^Bit_Array) #no_bounds_check { if ba == nil { return } - legs_needed := len(ba.bits) + legs_needed := builtin.len(ba.bits) for i := legs_needed - 1; i >= 0; i -= 1 { if ba.bits[i] == 0 { legs_needed -= 1 @@ -315,15 +331,15 @@ shrink :: proc(ba: ^Bit_Array) #no_bounds_check { break } } - if legs_needed == len(ba.bits) { + if legs_needed == builtin.len(ba.bits) { return } - ba.max_index = 0 + ba.length = 0 if legs_needed > 0 { if legs_needed > 1 { - ba.max_index = (legs_needed - 1) * NUM_BITS + ba.length = (legs_needed - 1) * NUM_BITS } - ba.max_index += NUM_BITS - 1 - int(intrinsics.count_leading_zeros(ba.bits[legs_needed - 1])) + ba.length += NUM_BITS - int(intrinsics.count_leading_zeros(ba.bits[legs_needed - 1])) } resize(&ba.bits, legs_needed) builtin.shrink(&ba.bits) @@ -351,8 +367,8 @@ resize_if_needed :: proc(ba: ^Bit_Array, legs: int, allocator := context.allocat context.allocator = allocator - if legs + 1 > len(ba.bits) { + if legs + 1 > builtin.len(ba.bits) { resize(&ba.bits, legs + 1) } - return len(ba.bits) > legs + return builtin.len(ba.bits) > legs } diff --git a/core/flags/internal_assignment.odin b/core/flags/internal_assignment.odin index bb49977eb..be3997ef1 100644 --- a/core/flags/internal_assignment.odin +++ b/core/flags/internal_assignment.odin @@ -14,10 +14,10 @@ import "core:reflect" // positionals first before adding it to a fallback field. @(optimization_mode="favor_size") push_positional :: #force_no_inline proc (model: ^$T, parser: ^Parser, arg: string) -> (error: Error) { - if bit_array.get(&parser.filled_pos, parser.filled_pos.max_index) { - // The max index is set, which means we're out of space. + if set, valid_index := bit_array.get(&parser.filled_pos, parser.filled_pos.length - 1); set || !valid_index { + // The index below the last one is either set or invalid, which means we're out of space. // Add one free bit by setting the index above to false. - bit_array.set(&parser.filled_pos, 1 + parser.filled_pos.max_index, false) + bit_array.set(&parser.filled_pos, parser.filled_pos.length, false) } pos: int = --- -- cgit v1.2.3