From 53e30e4621558f5d003eacc7b4a7f209723670c4 Mon Sep 17 00:00:00 2001 From: Jeroen van Rijn Date: Tue, 7 Dec 2021 18:45:46 +0100 Subject: [core:container/bit_vector] Create new package. A dynamic bit array, optionally allowing negative indices. --- core/container/bit_array/bit_array.odin | 124 ++++++++++++++++++++++++++++++++ 1 file changed, 124 insertions(+) create mode 100644 core/container/bit_array/bit_array.odin (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 new file mode 100644 index 000000000..61f6f86e8 --- /dev/null +++ b/core/container/bit_array/bit_array.odin @@ -0,0 +1,124 @@ +package dynamic_bit_array + +import "core:intrinsics" + +/* + Note that these constants are dependent on the backing being a u64. +*/ +@(private="file") +INDEX_SHIFT :: 6 + +@(private="file") +INDEX_MASK :: 63 + +Bit_Array :: struct { + bits: [dynamic]u64, + bias: int, +} + +/* + In: + - ba: ^Bit_Array - a pointer to the Bit Array + - index: The bit index. Can be an enum member. + + Out: + - res: The bit you're interested in. + - ok: Whether the index was valid. Returns `false` if the index is smaller than the bias. + + The `ok` return value may be ignored. +*/ +get :: proc(ba: ^Bit_Array, #any_int index: uint, allocator := context.allocator) -> (res: bool, ok: bool) { + 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 + + /* + 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 } + + val := u64(1 << uint(bit_index)) + res = ba.bits[leg_index] & val == val + + return res, true +} + +/* + In: + - ba: ^Bit_Array - a pointer to the Bit Array + - index: The bit index. Can be an enum member. + + Out: + - ok: Whether or not we managed to set requested bit. + + `set` automatically resizes the Bit Array to accommodate the requested index if needed. +*/ +set :: proc(ba: ^Bit_Array, #any_int index: uint, allocator := context.allocator) -> (ok: bool) { + + idx := int(index) - ba.bias + + if ba == nil || int(index) < ba.bias { return false } + context.allocator = allocator + + leg_index := idx >> INDEX_SHIFT + bit_index := idx & INDEX_MASK + + resize_if_needed(ba, leg_index) or_return + + ba.bits[leg_index] |= 1 << uint(bit_index) + return true +} + +/* + A helper function to create a Bit Array with optional bias, in case your smallest index is non-zero (including negative). +*/ +create :: proc(max_index: int, min_index := 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 + + res = Bit_Array{ + bias = min_index, + } + return res, resize_if_needed(&res, size_in_bits) +} + +/* + Sets all bits to `false`. +*/ +clear :: proc(ba: ^Bit_Array) { + if ba == nil { return } + ba.bits = {} +} + +/* + Releases the memory used by the Bit Array. +*/ +destroy :: proc(ba: ^Bit_Array) { + if ba == nil { return } + delete(ba.bits) +} + +/* + Resizes the Bit Array. For internal use. + If you want to reserve the memory for a given-sized Bit Array up front, you can use `create`. +*/ +@(private="file") +resize_if_needed :: proc(ba: ^Bit_Array, legs: int, allocator := context.allocator) -> (ok: bool) { + if ba == nil { return false } + + context.allocator = allocator + + if legs + 1 > len(ba.bits) { + resize(&ba.bits, legs + 1) + } + return len(ba.bits) > legs +} \ No newline at end of file -- cgit v1.2.3 From 515fd2a228835afa71cefec645b906729cda399e Mon Sep 17 00:00:00 2001 From: Jeroen van Rijn Date: Tue, 25 Jan 2022 17:08:32 +0100 Subject: bit_array: Fix initial size. --- 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 61f6f86e8..0fa80c623 100644 --- a/core/container/bit_array/bit_array.odin +++ b/core/container/bit_array/bit_array.odin @@ -88,7 +88,7 @@ create :: proc(max_index: int, min_index := 0, allocator := context.allocator) - res = Bit_Array{ bias = min_index, } - return res, resize_if_needed(&res, size_in_bits) + return res, resize_if_needed(&res, legs) } /* -- cgit v1.2.3 From 48af78e46981540b9071b382052777060ba83c23 Mon Sep 17 00:00:00 2001 From: Andrea Piseri Date: Fri, 4 Feb 2022 22:12:07 +0100 Subject: add `iterator` to `core:container/bit_array` --- core/container/bit_array/bit_array.odin | 43 ++++++++++++++++++++++++++++++++- 1 file changed, 42 insertions(+), 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 0fa80c623..f06cf74e7 100644 --- a/core/container/bit_array/bit_array.odin +++ b/core/container/bit_array/bit_array.odin @@ -11,11 +11,52 @@ INDEX_SHIFT :: 6 @(private="file") INDEX_MASK :: 63 +@(private="file") +NUM_BITS :: 64 + Bit_Array :: struct { bits: [dynamic]u64, bias: int, } +Bit_Array_Iterator :: struct { + array: ^Bit_Array, + current_word: uint, + current_bit: uint, +} + +/* + In: + - it: ^Bit_Array_Iterator - the iterator struct 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 +*/ +iterator :: proc (it: ^Bit_Array_Iterator) -> (int, bool) { + words := it.array.bits + // if the word is empty or we have already gone over all the bits in it, + // b.current_bit is greater than the index of any set bit in the word, + // meaning that word >> b.current_bit == 0. + for it.current_word < len(words) && (words[it.current_word] >> it.current_bit == 0) { + it.current_word += 1 + it.current_bit = 0 + } + + if it.current_word >= len(words) { return 0, false } + + // since we exited the loop and didn't return, this word has some bits higher than + // or equal to `it.current_bit` set. + offset := intrinsics.count_trailing_zeros(words[it.current_word] >> it.current_bit) + // skip over the bit, if the resulting it.current_bit is over 63, + // it is handled by the initial for loop in the next iteration. + it.current_bit += uint(offset) + defer it.current_bit += 1 + return int(it.current_word * NUM_BITS + it.current_bit) + it.array.bias, true +} + + /* In: - ba: ^Bit_Array - a pointer to the Bit Array @@ -121,4 +162,4 @@ resize_if_needed :: proc(ba: ^Bit_Array, legs: int, allocator := context.allocat resize(&ba.bits, legs + 1) } return len(ba.bits) > legs -} \ No newline at end of file +} -- cgit v1.2.3 From b54fc96b1e36ff83922d7af9d8126e3fff0d8078 Mon Sep 17 00:00:00 2001 From: ap29600 <66381278+ap29600@users.noreply.github.com> Date: Fri, 4 Feb 2022 22:39:47 +0100 Subject: rename `iterator` proc to `next`, add named return values --- 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 f06cf74e7..bf2ae3a40 100644 --- a/core/container/bit_array/bit_array.odin +++ b/core/container/bit_array/bit_array.odin @@ -34,7 +34,7 @@ Bit_Array_Iterator :: struct { - ok: bool - `true` if the iterator returned a valid index, `false` if there were no more bits set */ -iterator :: proc (it: ^Bit_Array_Iterator) -> (int, bool) { +next :: proc (it: ^Bit_Array_Iterator) -> (index: int, ok: bool) { words := it.array.bits // if the word is empty or we have already gone over all the bits in it, // b.current_bit is greater than the index of any set bit in the word, -- cgit v1.2.3 From bccbdefde952f605bde620c8d9d0c7f9a5dfc3e0 Mon Sep 17 00:00:00 2001 From: Andrea Piseri Date: Sat, 5 Feb 2022 18:00:59 +0100 Subject: Update interface to allow more modes of iteration It's now possible to iterate over: - all keys in the range min_value ..= max_value, with `iterate_all` - all set keys in the bit array, with `iterate_set` - all unset keys in the range min_value ..= max_value, with `iterate_unset` `Bit_Array` now stores the `max_value` provided during construction, and updates it when a key that was previously out of range is set. --- core/container/bit_array/bit_array.odin | 111 ++++++++++++++++++++++++++------ 1 file changed, 90 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 bf2ae3a40..0a92e3dc4 100644 --- a/core/container/bit_array/bit_array.odin +++ b/core/container/bit_array/bit_array.odin @@ -17,12 +17,24 @@ NUM_BITS :: 64 Bit_Array :: struct { bits: [dynamic]u64, bias: int, + max_index: int, } Bit_Array_Iterator :: struct { array: ^Bit_Array, - current_word: uint, - current_bit: uint, + word_idx: int, + bit_idx: uint, +} + +/* + In: + - ba: ^Bit_Array - the array to iterate over + + Out: + - it: ^Bit_Array_Iterator - the iterator that holds iteration state +*/ +make_iterator :: proc (ba: ^Bit_Array) -> (it: Bit_Array_Iterator) { + return Bit_Array_Iterator { array = ba } } /* @@ -30,30 +42,85 @@ Bit_Array_Iterator :: struct { - it: ^Bit_Array_Iterator - the iterator struct 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 + - 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 +*/ +iterate_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 } + + word := it.array.bits[it.word_idx] if len(it.array.bits) > it.word_idx else 0 + set = (word >> it.bit_idx & 1) == 1 + + it.bit_idx += 1 + if it.bit_idx >= NUM_BITS { + it.bit_idx = 0 + it.word_idx += 1 + } + + return set, index, true +} + +/* + In: + - it: ^Bit_Array_Iterator - the iterator struct 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 +*/ +iterate_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. + + 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 */ -next :: proc (it: ^Bit_Array_Iterator) -> (index: int, ok: bool) { - words := it.array.bits +iterate_unset:: proc (it: ^Bit_Array_Iterator) -> (index: int, ok: bool) { + return iterate_internal_(it, false) +} + +@(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, - // b.current_bit is greater than the index of any set bit in the word, - // meaning that word >> b.current_bit == 0. - for it.current_word < len(words) && (words[it.current_word] >> it.current_bit == 0) { - it.current_word += 1 - it.current_bit = 0 + // 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 { + 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 + 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) { + return 0, false + } } - if it.current_word >= len(words) { return 0, false } + // 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 - // since we exited the loop and didn't return, this word has some bits higher than - // or equal to `it.current_bit` set. - offset := intrinsics.count_trailing_zeros(words[it.current_word] >> it.current_bit) - // skip over the bit, if the resulting it.current_bit is over 63, - // it is handled by the initial for loop in the next iteration. - it.current_bit += uint(offset) - defer it.current_bit += 1 - return int(it.current_word * NUM_BITS + it.current_bit) + it.array.bias, true + it.bit_idx += 1 + if it.bit_idx >= NUM_BITS { + it.bit_idx = 0 + it.word_idx += 1 + } + return index, index <= it.array.max_index } @@ -111,6 +178,7 @@ set :: proc(ba: ^Bit_Array, #any_int index: uint, allocator := context.allocator resize_if_needed(ba, leg_index) or_return + if idx > ba.max_index { ba.max_index = idx } ba.bits[leg_index] |= 1 << uint(bit_index) return true } @@ -128,6 +196,7 @@ create :: proc(max_index: int, min_index := 0, allocator := context.allocator) - res = Bit_Array{ bias = min_index, + max_index = max_index, } return res, resize_if_needed(&res, legs) } -- cgit v1.2.3 From b6ebfe4b2c1445f59ed35c20bf8d4ba8910b59de Mon Sep 17 00:00:00 2001 From: Andrea Piseri Date: Sat, 5 Feb 2022 18:11:48 +0100 Subject: rename iterator procedures --- 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 0a92e3dc4..5fbac69af 100644 --- a/core/container/bit_array/bit_array.odin +++ b/core/container/bit_array/bit_array.odin @@ -47,7 +47,7 @@ make_iterator :: proc (ba: ^Bit_Array) -> (it: Bit_Array_Iterator) { - ok: bool - `true` if the iterator returned a valid index, `false` if there were no more bits */ -iterate_all :: proc (it: ^Bit_Array_Iterator) -> (set: bool, index: int, ok: bool) { +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 } @@ -72,7 +72,7 @@ iterate_all :: proc (it: ^Bit_Array_Iterator) -> (set: bool, index: int, ok: boo - ok: bool - `true` if the iterator returned a valid index, `false` if there were no more bits set */ -iterate_set :: proc (it: ^Bit_Array_Iterator) -> (index: int, ok: bool) { +iterate_by_set :: proc (it: ^Bit_Array_Iterator) -> (index: int, ok: bool) { return iterate_internal_(it, true) } @@ -85,7 +85,7 @@ iterate_set :: proc (it: ^Bit_Array_Iterator) -> (index: int, ok: bool) { - ok: bool - `true` if the iterator returned a valid index, `false` if there were no more unset bits */ -iterate_unset:: proc (it: ^Bit_Array_Iterator) -> (index: int, ok: bool) { +iterate_by_unset:: proc (it: ^Bit_Array_Iterator) -> (index: int, ok: bool) { return iterate_internal_(it, false) } -- cgit v1.2.3 From 697f8c7ee6ef3d0af4d8e44163e770ef1f2227c5 Mon Sep 17 00:00:00 2001 From: ap29600 <66381278+ap29600@users.noreply.github.com> Date: Sat, 5 Feb 2022 18:46:25 +0100 Subject: replace a branch with `max` in `core:container/bit_array.set` --- 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 5fbac69af..5eebe1bcb 100644 --- a/core/container/bit_array/bit_array.odin +++ b/core/container/bit_array/bit_array.odin @@ -178,7 +178,7 @@ set :: proc(ba: ^Bit_Array, #any_int index: uint, allocator := context.allocator resize_if_needed(ba, leg_index) or_return - if idx > ba.max_index { ba.max_index = idx } + ba.max_index = max(idx, ba.max_index) ba.bits[leg_index] |= 1 << uint(bit_index) return true } -- cgit v1.2.3 From bff3426d254bf728b330c6f93fac97339cc41c67 Mon Sep 17 00:00:00 2001 From: Andrea Piseri Date: Sun, 6 Mar 2022 10:21:46 +0100 Subject: Fix leak in `core:container/bit_array` calling `clear` on a `bit_array` no longer leaks the previous allocation, instead it sets all bits to `false` preserving the same backing dynamic array. --- core/container/bit_array/bit_array.odin | 3 ++- 1 file changed, 2 insertions(+), 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 5eebe1bcb..0016ca105 100644 --- a/core/container/bit_array/bit_array.odin +++ b/core/container/bit_array/bit_array.odin @@ -1,6 +1,7 @@ package dynamic_bit_array import "core:intrinsics" +import "core:mem" /* Note that these constants are dependent on the backing being a u64. @@ -206,7 +207,7 @@ create :: proc(max_index: int, min_index := 0, allocator := context.allocator) - */ clear :: proc(ba: ^Bit_Array) { if ba == nil { return } - ba.bits = {} + mem.zero_slice(ba.bits[:]) } /* -- cgit v1.2.3 From ce057ff755d2fe852cb83e4025686d9efd3053d7 Mon Sep 17 00:00:00 2001 From: Jeroen van Rijn Date: Sun, 6 Mar 2022 12:29:17 +0100 Subject: [bit_array] Really fix the leak. --- core/container/bit_array/bit_array.odin | 26 +++++++++++++++----------- core/container/bit_array/doc.odin | 13 +++++++------ 2 files changed, 22 insertions(+), 17 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 0016ca105..98ef4b542 100644 --- a/core/container/bit_array/bit_array.odin +++ b/core/container/bit_array/bit_array.odin @@ -16,15 +16,16 @@ INDEX_MASK :: 63 NUM_BITS :: 64 Bit_Array :: struct { - bits: [dynamic]u64, - bias: int, - max_index: int, + bits: [dynamic]u64, + bias: int, + max_index: int, + free_pointer: bool, } Bit_Array_Iterator :: struct { - array: ^Bit_Array, + array: ^Bit_Array, word_idx: int, - bit_idx: uint, + bit_idx: uint, } /* @@ -187,7 +188,7 @@ set :: proc(ba: ^Bit_Array, #any_int index: uint, allocator := context.allocator /* A helper function to create a Bit Array with optional bias, in case your smallest index is non-zero (including negative). */ -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 := 0, allocator := context.allocator) -> (res: ^Bit_Array, ok: bool) #optional_ok { context.allocator = allocator size_in_bits := max_index - min_index @@ -195,11 +196,11 @@ create :: proc(max_index: int, min_index := 0, allocator := context.allocator) - legs := size_in_bits >> INDEX_SHIFT - res = Bit_Array{ - bias = min_index, - max_index = max_index, - } - return res, resize_if_needed(&res, legs) + res = new(Bit_Array) + res.bias = min_index + res.max_index = max_index + res.free_pointer = true + return res, resize_if_needed(res, legs) } /* @@ -216,6 +217,9 @@ clear :: proc(ba: ^Bit_Array) { destroy :: proc(ba: ^Bit_Array) { if ba == nil { return } delete(ba.bits) + if ba.free_pointer { // Only free if this Bit_Array was created using `create`, not when on the stack. + free(ba) + } } /* diff --git a/core/container/bit_array/doc.odin b/core/container/bit_array/doc.odin index 91e1362dd..52e252d8a 100644 --- a/core/container/bit_array/doc.odin +++ b/core/container/bit_array/doc.odin @@ -21,6 +21,7 @@ package dynamic_bit_array // returns `false`, `false`, because this Bit Array wasn't created to allow negative indices. was_set, was_retrieved := get(&bits, -1) fmt.println(was_set, was_retrieved) + destroy(&bits) } -- A Bit Array can optionally allow for negative indices, if the mininum value was given during creation: @@ -40,13 +41,13 @@ package dynamic_bit_array using bit_array bits := create(int(max(Foo)), int(min(Foo))) - defer destroy(&bits) + defer destroy(bits) - fmt.printf("Set(Bar): %v\n", set(&bits, Foo.Bar)) - fmt.printf("Get(Bar): %v, %v\n", get(&bits, Foo.Bar)) - fmt.printf("Set(Negative_Test): %v\n", set(&bits, Foo.Negative_Test)) - fmt.printf("Get(Leaves): %v, %v\n", get(&bits, Foo.Leaves)) - fmt.printf("Get(Negative_Test): %v, %v\n", get(&bits, Foo.Negative_Test)) + fmt.printf("Set(Bar): %v\n", set(bits, Foo.Bar)) + fmt.printf("Get(Bar): %v, %v\n", get(bits, Foo.Bar)) + fmt.printf("Set(Negative_Test): %v\n", set(bits, Foo.Negative_Test)) + fmt.printf("Get(Leaves): %v, %v\n", get(bits, Foo.Leaves)) + fmt.printf("Get(Negative_Test): %v, %v\n", get(bits, Foo.Negative_Test)) fmt.printf("Freed.\n") } */ \ No newline at end of file -- cgit v1.2.3