Merge branch 'master' into macharena

2 files changed, 64 insertions, 18 deletions

diff --git a/core/container/bit_array/bit_array.odin b/core/container/bit_array/bit_array.odin
index b53bacda7..9a76dc78f 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"
 
@@ -18,7 +19,7 @@ NUM_BITS :: 64
 Bit_Array :: struct {
 	bits:         [dynamic]u64,
 	bias:         int,
-	max_index:    int,
+	length:       int,
 	free_pointer: bool,
 }
 
@@ -52,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 { 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
@@ -106,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
 		}
 	}
@@ -135,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.length + it.array.bias
 }
 /*
 Gets the state of a bit in the bit-array
@@ -160,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
@@ -208,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)
@@ -261,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:
@@ -275,7 +279,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}
@@ -284,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
+	res.length       = max_index - min_index
 	res.free_pointer = true
 	return
 }
@@ -299,6 +303,48 @@ 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:
+- ba: The target Bit_Array
+*/
+shrink :: proc(ba: ^Bit_Array) #no_bounds_check {
+	if ba == nil { return }
+	legs_needed := builtin.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 == builtin.len(ba.bits) {
+		return
+	}
+	ba.length = 0
+	if legs_needed > 0 {
+		if legs_needed > 1 {
+			ba.length = (legs_needed - 1) * NUM_BITS
+		}
+		ba.length += NUM_BITS - 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:
@@ -321,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/container/bit_array/doc.odin b/core/container/bit_array/doc.odin
index 77e1904a8..36bf90002 100644
--- a/core/container/bit_array/doc.odin
+++ b/core/container/bit_array/doc.odin
@@ -1,8 +1,8 @@
 /*
 The Bit Array can be used in several ways:
 
-- By default you don't need to instantiate a Bit Array:
-
+By default you don't need to instantiate a Bit Array.
+Example:
 	package test
 
 	import "core:fmt"
@@ -22,8 +22,8 @@ The Bit Array can be used in several ways:
 		destroy(&bits)
 	}
 
-- A Bit Array can optionally allow for negative indices, if the minimum value was given during creation:
-
+A Bit Array can optionally allow for negative indices, if the minimum value was given during creation.
+Example:
 	package test
 
 	import "core:fmt"