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 +++++++++++++++++++++------------
 1 file changed, 34 insertions(+), 18 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..<max_index`, and the
+array will be able to expand beyond `max_index` if needed.
+
 *Allocates (`new(Bit_Array) & make(ba.bits)`)*
 
 Inputs:
@@ -285,7 +288,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 - min_index
+	res.length       = max_index - min_index
 	res.free_pointer = true
 	return
 }
@@ -300,6 +303,19 @@ clear :: proc(ba: ^Bit_Array) {
 	mem.zero_slice(ba.bits[:])
 }
 /*
+Gets the length of set and unset valid bits in the Bit_Array.
+
+Inputs:
+- ba: The target Bit_Array
+
+Returns:
+- length: The length of valid bits.
+*/
+len :: proc(ba: ^Bit_Array) -> (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
 }
-- 
cgit v1.2.3