diff options
Diffstat (limited to 'core/container/bit_array')
| -rw-r--r-- | core/container/bit_array/bit_array.odin | 74 | ||||
| -rw-r--r-- | core/container/bit_array/doc.odin | 8 |
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" |