Merge pull request #2502 from jon-lipstate/ba-cleanup

Bit_Array: Update docs, add unsafe_get/set, round up on Create

1 files changed, 137 insertions, 78 deletions

diff --git a/core/container/bit_array/bit_array.odin b/core/container/bit_array/bit_array.odin
index 763a19f8b..d649d039f 100644
--- a/core/container/bit_array/bit_array.odin
+++ b/core/container/bit_array/bit_array.odin
@@ -27,27 +27,28 @@ Bit_Array_Iterator :: struct {
 	word_idx: int,
 	bit_idx:  uint,
 }
-
 /*
-	In:
-		- ba:   ^Bit_Array - the array to iterate over
+Wraps a `Bit_Array` into an Iterator
+
+Inputs:
+- ba: Pointer to the Bit_Array
 
-	Out:
-		- it:   ^Bit_Array_Iterator - the iterator that holds iteration state
+Returns:
+- it: Iterator struct
 */
 make_iterator :: proc (ba: ^Bit_Array) -> (it: Bit_Array_Iterator) {
 	return Bit_Array_Iterator { array = ba }
 }
-
 /*
-	In:
-		- it:    ^Bit_Array_Iterator - the iterator struct that holds the state.
-
-	Out:
-		- set:    bool - the state of the bit at `index`
-		- index:  int - the next bit of the Bit_Array referenced by `it`.
-		- ok:	  bool - `true` if the iterator returned a valid index,
-			  `false` if there were no more bits
+Returns the next bit, including its set-state. ok=false once exhausted
+
+Inputs:
+- it: The iterator that holds the state.
+
+Returns:
+- set: `true` if the bit at `index` is set.
+- index: The next bit of the Bit_Array referenced by `it`.
+- ok: `true` if the iterator can continue, `false` if the iterator is done
 */
 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
@@ -64,39 +65,51 @@ iterate_by_all :: proc (it: ^Bit_Array_Iterator) -> (set: bool, index: int, ok:
 
 	return set, index, true
 }
-
 /*
-	In:
-		- it:     ^Bit_Array_Iterator - the iterator struct that holds the state.
+Returns the next Set Bit, for example if `0b1010`, then the iterator will return index={1, 3} over two calls.
+
+Inputs:
+- it: The iterator that holds the state.
 
-	Out:
-		- index:  int - the next set bit of the Bit_Array referenced by `it`.
-		- ok:	  bool - `true` if the iterator returned a valid index,
-			  `false` if there were no more bits set
+Returns:
+- index: The next *set* bit of the Bit_Array referenced by `it`.
+- ok: `true` if the iterator can continue, `false` if the iterator is done
 */
 iterate_by_set :: proc (it: ^Bit_Array_Iterator) -> (index: int, ok: bool) {
 	return iterate_internal_(it, true)
 }
-
 /*
-	In:
-		- it:	  ^Bit_Array_Iterator - the iterator struct that holds the state.
+Returns the next Unset Bit, for example if `0b1010`, then the iterator will return index={0, 2} over two calls.
+
+Inputs:
+- it: The iterator that holds the state.
 
-	Out:
-		- index:  int - the next unset bit of the Bit_Array referenced by `it`.
-		- ok:	  bool - `true` if the iterator returned a valid index,
-			  `false` if there were no more unset bits
+Returns:
+- index: The next *unset* bit of the Bit_Array referenced by `it`.
+- ok: `true` if the iterator can continue, `false` if the iterator is done
 */
 iterate_by_unset:: proc (it: ^Bit_Array_Iterator) -> (index: int, ok: bool) {
 	return iterate_internal_(it, false)
 }
+/*
+Iterates through set/unset bits
 
+*Private*
+
+Inputs:
+- it: The iterator that holds the state.
+- ITERATE_SET_BITS: `true` for returning only set bits, false for returning only unset bits
+
+Returns:
+- index: The next *unset* bit of the Bit_Array referenced by `it`.
+- ok: `true` if the iterator can continue, `false` if the iterator is done
+*/
 @(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
 	when ! ITERATE_SET_BITS { word = ~word }
 
-	// if the word is empty or we have already gone over all the bits in it,
+	// 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 {
@@ -106,14 +119,14 @@ iterate_internal_ :: proc (it: ^Bit_Array_Iterator, $ITERATE_SET_BITS: bool) ->
 		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
+	// 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) {
 			return 0, false
 		}
 	}
 
-	// reaching here means that the word has some set bits
+	// Reaching here means that the word has some set bits
 	it.bit_idx += uint(intrinsics.count_trailing_zeros(word >> it.bit_idx))
 	index = it.word_idx * NUM_BITS + int(it.bit_idx) + it.array.bias
 
@@ -124,24 +137,21 @@ iterate_internal_ :: proc (it: ^Bit_Array_Iterator, $ITERATE_SET_BITS: bool) ->
 	}
 	return index, index <= it.array.max_index
 }
-
-
 /*
-	In:
-		- ba:    ^Bit_Array - a pointer to the Bit Array
-		- index: The bit index. Can be an enum member.
+Gets the state of a bit in the bit-array
 
-	Out:
-		- res:   The bit you're interested in.
-		- ok:    Whether the index was valid. Returns `false` if the index is smaller than the bias.
+Inputs:
+- ba: Pointer to the Bit_Array
+- index: Which bit in the array
 
-	The `ok` return value may be ignored.
+Returns:
+- res: `true` if the bit at `index` is set.
+- ok: Whether the index was valid. Returns `false` if the index is smaller than the bias.
 */
-get :: proc(ba: ^Bit_Array, #any_int index: uint, allocator := context.allocator) -> (res: bool, ok: bool) {
+get :: proc(ba: ^Bit_Array, #any_int index: uint) -> (res: bool, ok: bool) #optional_ok {
 	idx := int(index) - ba.bias
 
 	if ba == nil || int(index) < ba.bias { return false, false }
-	context.allocator = allocator
 
 	leg_index := idx >> INDEX_SHIFT
 	bit_index := idx &  INDEX_MASK
@@ -157,18 +167,36 @@ get :: proc(ba: ^Bit_Array, #any_int index: uint, allocator := context.allocator
 
 	return res, true
 }
+/*
+Gets the state of a bit in the bit-array
+
+*Bypasses all Checks*
+
+Inputs:
+- ba: Pointer to the Bit_Array
+- index: Which bit in the array
 
+Returns:
+- `true` if bit is set
+*/
+unsafe_get :: #force_inline proc(ba: ^Bit_Array, #any_int index: uint) -> bool #no_bounds_check {
+	return bool((ba.bits[index >> INDEX_SHIFT] >> uint(index & INDEX_MASK)) & 1)
+}
 /*
-	In:
-		- ba:    ^Bit_Array - a pointer to the Bit Array
-		- index: The bit index. Can be an enum member.
+Sets the state of a bit in the bit-array
+
+*Conditionally Allocates (Resizes backing data when `index > len(ba.bits)`)*
 
-	Out:
-		- ok:    Whether or not we managed to set requested bit.
+Inputs:
+- ba: Pointer to the Bit_Array
+- index: Which bit in the array
+- set_to: `true` sets the bit on, `false` to turn it off
+- allocator: (default is context.allocator)
 
-	`set` automatically resizes the Bit Array to accommodate the requested index if needed.
+Returns:
+- ok: Whether the set was successful, `false` on allocation failure or bad index
 */
-set :: proc(ba: ^Bit_Array, #any_int index: uint, allocator := context.allocator) -> (ok: bool) {
+set :: proc(ba: ^Bit_Array, #any_int index: uint, set_to: bool = true, allocator := context.allocator) -> (ok: bool) {
 
 	idx := int(index) - ba.bias
 
@@ -181,65 +209,97 @@ set :: proc(ba: ^Bit_Array, #any_int index: uint, allocator := context.allocator
 	resize_if_needed(ba, leg_index) or_return
 
 	ba.max_index = max(idx, ba.max_index)
-	ba.bits[leg_index] |= 1 << uint(bit_index)
+
+	if set_to{ ba.bits[leg_index] |= 1 << uint(bit_index) }
+	else { ba.bits[leg_index] &= ~(1 << uint(bit_index)) }
+
 	return true
 }
-
 /*
-	In:
-		- ba:    ^Bit_Array - a pointer to the Bit Array
-		- index: The bit index. Can be an enum member.
+Sets the state of a bit in the bit-array
 
-	Out:
-		- ok:    Whether or not we managed to unset requested bit.
+*Bypasses all checks*
 
-	`unset` automatically resizes the Bit Array to accommodate the requested index if needed.
+Inputs:
+- ba: Pointer to the Bit_Array
+- index: Which bit in the array
 */
-unset :: proc(ba: ^Bit_Array, #any_int index: uint, allocator := context.allocator) -> (ok: bool) {
+unsafe_set :: proc(ba: ^Bit_Array, bit: int) #no_bounds_check {
+	ba.bits[bit >> INDEX_SHIFT] |= 1 << uint(bit & INDEX_MASK)
+}
+/*
+Unsets the state of a bit in the bit-array. (Convienence wrapper for `set`)
 
-	idx := int(index) - ba.bias
+*Conditionally Allocates (Resizes backing data when `index > len(ba.bits)`)*
 
-	if ba == nil || int(index) < ba.bias { return false }
-	context.allocator = allocator
+Inputs:
+- ba: Pointer to the Bit_Array
+- index: Which bit in the array
+- allocator: (default is context.allocator)
 
-	leg_index := idx >> INDEX_SHIFT
-	bit_index := idx &  INDEX_MASK
+Returns:
+- ok: Whether the unset was successful, `false` on allocation failure or bad index
+*/
+unset :: #force_inline proc(ba: ^Bit_Array, #any_int index: uint, allocator := context.allocator) -> (ok: bool) {
+	return set(ba, index, false, allocator)
+}
+/*
+Unsets the state of a bit in the bit-array
 
-	resize_if_needed(ba, leg_index) or_return
+*Bypasses all Checks*
 
-	ba.max_index = max(idx, ba.max_index)
-	ba.bits[leg_index] &= ~(1 << uint(bit_index))
-	return true
+Inputs:
+- ba: Pointer to the Bit_Array
+- index: Which bit in the array
+*/
+unsafe_unset :: proc(b: ^Bit_Array, bit: int) #no_bounds_check {
+	b.bits[bit >> INDEX_SHIFT] &= ~(1 << uint(bit & INDEX_MASK))
 }
-
 /*
-	A helper function to create a Bit Array with optional bias, in case your smallest index is non-zero (including negative).
+A helper function to create a Bit Array with optional bias, in case your smallest index is non-zero (including negative).
+
+*Allocates (`new(Bit_Array) & make(ba.bits)`)*
+
+Inputs:
+- max_index: maximum starting index
+- min_index: minimum starting index (used as a bias)
+- allocator: (default is context.allocator)
+
+Returns:
+- ba: Allocates a bit_Array, backing data is set to `max-min / 64` indices, rounded up (eg 65 - 0 allocates for [2]u64).
 */
-create :: proc(max_index: int, min_index := 0, allocator := context.allocator) -> (res: ^Bit_Array, ok: bool) #optional_ok {
+create :: proc(max_index: int, min_index: int = 0, allocator := context.allocator) -> (res: ^Bit_Array, ok: bool) #optional_ok {
 	context.allocator = allocator
 	size_in_bits := max_index - min_index
 
 	if size_in_bits < 1 { return {}, false }
 
 	legs := size_in_bits >> INDEX_SHIFT
-
+	if size_in_bits & INDEX_MASK > 0 {legs+=1}
+	bits, err := make([dynamic]u64, legs)
+	ok = err == mem.Allocator_Error.None
 	res = new(Bit_Array)
+	res.bits         = bits
 	res.bias         = min_index
 	res.max_index    = max_index
 	res.free_pointer = true
-	return res, resize_if_needed(res, legs)
+	return
 }
-
 /*
-	Sets all bits to `false`.
+Sets all values in the Bit_Array to zero.
+
+Inputs:
+- ba: The target Bit_Array
 */
 clear :: proc(ba: ^Bit_Array) {
 	if ba == nil { return }
 	mem.zero_slice(ba.bits[:])
 }
-
 /*
-	Releases the memory used by the Bit Array.
+Deallocates the Bit_Array and its backing storage
+
+Inputs:
+- ba: The target Bit_Array
 */
 destroy :: proc(ba: ^Bit_Array) {
 	if ba == nil { return }
@@ -248,9 +308,8 @@ destroy :: proc(ba: ^Bit_Array) {
 		free(ba)
 	}
 }
-
 /*
-	Resizes the Bit Array. For internal use.
+	Resizes the Bit Array. For internal use. Provisions needed capacity+1
 	If you want to reserve the memory for a given-sized Bit Array up front, you can use `create`.
 */
 @(private="file")