aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorgingerBill <bill@gingerbill.org>2021-12-28 14:05:09 +0000
committergingerBill <bill@gingerbill.org>2021-12-28 14:05:09 +0000
commit7f61a90ea1be96c22cae87fdbfdc08b30f2421d6 (patch)
treeff009a150eec737aa4ba6a8abe46e81eda91028c
parent0548db423067bce16d45af651819bf56feb5d411 (diff)
Remove `core:container` contents
-rw-r--r--core/container/array.odin216
-rw-r--r--core/container/bloom_filter.odin80
-rw-r--r--core/container/map.odin377
-rw-r--r--core/container/priority_queue.odin121
-rw-r--r--core/container/queue.odin175
-rw-r--r--core/container/ring.odin74
-rw-r--r--core/container/set.odin240
-rw-r--r--core/container/small_array.odin95
8 files changed, 0 insertions, 1378 deletions
diff --git a/core/container/array.odin b/core/container/array.odin
deleted file mode 100644
index 2d5a64ec3..000000000
--- a/core/container/array.odin
+++ /dev/null
@@ -1,216 +0,0 @@
-package container
-
-import "core:mem"
-import "core:runtime"
-
-Array :: struct($T: typeid) {
- data: ^T,
- len: int,
- cap: int,
- allocator: mem.Allocator,
-}
-
-ARRAY_DEFAULT_CAPACITY :: 16
-
-/*
-array_init :: proc {
- array_init_none,
- array_init_len,
- array_init_len_cap,
-}
-array_init
-array_delete
-array_len
-array_cap
-array_space
-array_slice
-array_get
-array_get_ptr
-array_set
-array_reserve
-array_resize
-array_push = array_append :: proc{
- array_push_back,
- array_push_back_elems,
-}
-array_push_front
-array_pop_back
-array_pop_front
-array_consume
-array_trim
-array_clear
-array_clone
-array_set_capacity
-array_grow
-*/
-
-
-array_init_none :: proc(a: ^$A/Array, allocator := context.allocator) {
- array_init_len_cap(a, 0, ARRAY_DEFAULT_CAPACITY, allocator)
-}
-array_init_len :: proc(a: ^$A/Array, len: int, allocator := context.allocator) {
- array_init_len_cap(a, len, len, allocator)
-}
-array_init_len_cap :: proc(a: ^$A/Array($T), len: int, cap: int, allocator := context.allocator) {
- a.allocator = allocator
- a.data = (^T)(mem.alloc(size_of(T)*cap, align_of(T), a.allocator))
- a.len = len
- a.cap = cap
-}
-
-array_init :: proc{array_init_none, array_init_len, array_init_len_cap}
-
-array_delete :: proc(a: $A/Array) {
- mem.free(a.data, a.allocator)
-}
-
-array_len :: proc(a: $A/Array) -> int {
- return a.len
-}
-
-array_cap :: proc(a: $A/Array) -> int {
- return a.cap
-}
-
-array_space :: proc(a: $A/Array) -> int {
- return a.cap - a.len
-}
-
-array_slice :: proc(a: $A/Array($T)) -> []T {
- s := mem.Raw_Slice{a.data, a.len}
- return transmute([]T)s
-}
-
-array_cap_slice :: proc(a: $A/Array($T)) -> []T {
- s := mem.Raw_Slice{a.data, a.cap}
- return transmute([]T)s
-}
-
-array_get :: proc(a: $A/Array($T), index: int, loc := #caller_location) -> T {
- runtime.bounds_check_error_loc(loc, index, array_len(a))
- return (^T)(uintptr(a.data) + size_of(T)*uintptr(index))^
-}
-array_get_ptr :: proc(a: $A/Array($T), index: int, loc := #caller_location) -> ^T {
- runtime.bounds_check_error_loc(loc, index, array_len(a))
- return (^T)(uintptr(a.data) + size_of(T)*uintptr(index))
-}
-
-array_set :: proc(a: ^$A/Array($T), index: int, item: T, loc := #caller_location) {
- runtime.bounds_check_error_loc(loc, index, array_len(a^))
- (^T)(uintptr(a.data) + size_of(T)*uintptr(index))^ = item
-}
-
-
-array_reserve :: proc(a: ^$A/Array, capacity: int) {
- if capacity > a.len {
- array_set_capacity(a, capacity)
- }
-}
-
-array_resize :: proc(a: ^$A/Array, length: int) {
- if length > a.len {
- array_set_capacity(a, length)
- }
- a.len = length
-}
-
-
-
-array_push_back :: proc(a: ^$A/Array($T), item: T) {
- if array_space(a^) == 0 {
- array_grow(a)
- }
-
- a.len += 1
- array_set(a, a.len-1, item)
-}
-
-array_push_front :: proc(a: ^$A/Array($T), item: T) {
- if array_space(a^) == 0 {
- array_grow(a)
- }
-
- a.len += 1
- data := array_slice(a^)
- copy(data[1:], data[:])
- data[0] = item
-}
-
-array_pop_back :: proc(a: ^$A/Array($T), loc := #caller_location) -> T {
- assert(condition=a.len > 0, loc=loc)
- item := array_get(a^, a.len-1)
- a.len -= 1
- return item
-}
-
-array_pop_front :: proc(a: ^$A/Array($T), loc := #caller_location) -> T {
- assert(condition=a.len > 0, loc=loc)
- item := array_get(a^, 0)
- s := array_slice(a^)
- copy(s[:], s[1:])
- a.len -= 1
- return item
-}
-
-
-array_consume :: proc(a: ^$A/Array($T), count: int, loc := #caller_location) {
- assert(condition=a.len >= count, loc=loc)
- a.len -= count
-}
-
-
-array_trim :: proc(a: ^$A/Array($T)) {
- array_set_capacity(a, a.len)
-}
-
-array_clear :: proc(a: ^$A/Array($T)) {
- array_resize(a, 0)
-}
-
-array_clone :: proc(a: $A/Array($T), allocator := context.allocator) -> A {
- res: A
- array_init(&res, array_len(a), array_len(a), allocator)
- copy(array_slice(res), array_slice(a))
- return res
-}
-
-array_push_back_elems :: proc(a: ^$A/Array($T), items: ..T) {
- if array_space(a^) < len(items) {
- array_grow(a, a.len + len(items))
- }
- offset := a.len
- data := array_cap_slice(a^)
- n := copy(data[a.len:], items)
- a.len += n
-}
-
-array_push :: proc{array_push_back, array_push_back_elems}
-array_append :: proc{array_push_back, array_push_back_elems}
-
-array_set_capacity :: proc(a: ^$A/Array($T), new_capacity: int) {
- if new_capacity == a.cap {
- return
- }
-
- if new_capacity < a.len {
- array_resize(a, new_capacity)
- }
-
- new_data: ^T
- if new_capacity > 0 {
- if a.allocator.procedure == nil {
- a.allocator = context.allocator
- }
- new_data = (^T)(mem.alloc(size_of(T)*new_capacity, align_of(T), a.allocator))
- if new_data != nil {
- mem.copy(new_data, a.data, size_of(T)*a.len)
- }
- }
- mem.free(a.data, a.allocator)
- a.data = new_data
- a.cap = new_capacity
-}
-array_grow :: proc(a: ^$A/Array, min_capacity: int = 0) {
- new_capacity := max(array_len(a^)*2 + 8, min_capacity)
- array_set_capacity(a, new_capacity)
-}
diff --git a/core/container/bloom_filter.odin b/core/container/bloom_filter.odin
deleted file mode 100644
index 8af7aeb85..000000000
--- a/core/container/bloom_filter.odin
+++ /dev/null
@@ -1,80 +0,0 @@
-package container
-
-import "core:mem"
-
-Bloom_Hash_Proc :: #type proc(data: []byte) -> u32
-
-Bloom_Hash :: struct {
- hash_proc: Bloom_Hash_Proc,
- next: ^Bloom_Hash,
-}
-
-Bloom_Filter :: struct {
- allocator: mem.Allocator,
- hash: ^Bloom_Hash,
- bits: []byte,
-}
-
-bloom_filter_init :: proc(b: ^Bloom_Filter, size: int, allocator := context.allocator) {
- b.allocator = allocator
- b.bits = make([]byte, size, allocator)
-}
-
-bloom_filter_destroy :: proc(b: ^Bloom_Filter) {
- context.allocator = b.allocator
- delete(b.bits)
- for b.hash != nil {
- hash := b.hash
- b.hash = b.hash.next
- free(hash)
- }
-}
-
-bloom_filter_add_hash_proc :: proc(b: ^Bloom_Filter, hash_proc: Bloom_Hash_Proc) {
- context.allocator = b.allocator
- h := new(Bloom_Hash)
- h.hash_proc = hash_proc
-
- head := &b.hash
- for head^ != nil {
- head = &(head^.next)
- }
- head^ = h
-}
-
-bloom_filter_add :: proc(b: ^Bloom_Filter, item: []byte) {
- #no_bounds_check for h := b.hash; h != nil; h = h.next {
- hash := h.hash_proc(item)
- hash %= u32(len(b.bits) * 8)
- b.bits[hash >> 3] |= 1 << (hash & 3)
- }
-}
-
-bloom_filter_add_string :: proc(b: ^Bloom_Filter, item: string) {
- bloom_filter_add(b, transmute([]byte)item)
-}
-
-bloom_filter_add_raw :: proc(b: ^Bloom_Filter, data: rawptr, size: int) {
- item := mem.slice_ptr((^byte)(data), size)
- bloom_filter_add(b, item)
-}
-
-bloom_filter_test :: proc(b: ^Bloom_Filter, item: []byte) -> bool {
- #no_bounds_check for h := b.hash; h != nil; h = h.next {
- hash := h.hash_proc(item)
- hash %= u32(len(b.bits) * 8)
- if (b.bits[hash >> 3] & (1 << (hash & 3)) == 0) {
- return false
- }
- }
- return true
-}
-
-bloom_filter_test_string :: proc(b: ^Bloom_Filter, item: string) -> bool {
- return bloom_filter_test(b, transmute([]byte)item)
-}
-
-bloom_filter_test_raw :: proc(b: ^Bloom_Filter, data: rawptr, size: int) -> bool {
- item := mem.slice_ptr((^byte)(data), size)
- return bloom_filter_test(b, item)
-}
diff --git a/core/container/map.odin b/core/container/map.odin
deleted file mode 100644
index 54cbc22fc..000000000
--- a/core/container/map.odin
+++ /dev/null
@@ -1,377 +0,0 @@
-package container
-
-import "core:intrinsics"
-_ :: intrinsics
-
-
-Map :: struct($Key, $Value: typeid) where intrinsics.type_is_valid_map_key(Key) {
- hash: Array(int),
- entries: Array(Map_Entry(Key, Value)),
-}
-
-Map_Entry :: struct($Key, $Value: typeid) where intrinsics.type_is_valid_map_key(Key) {
- hash: uintptr,
- next: int,
- key: Key,
- value: Value,
-}
-
-
-/*
-map_init :: proc{
- map_init_none,
- map_init_cap,
-}
-map_delete
-
-map_has
-map_get
-map_get_default
-map_get_ptr
-map_set
-map_remove
-map_reserve
-map_clear
-
-// Multi Map
-
-multi_map_find_first
-multi_map_find_next
-multi_map_count
-multi_map_get :: proc{
- multi_map_get_array,
- multi_map_get_slice,
-};
-multi_map_get_as_slice
-multi_map_insert
-multi_map_remove
-multi_map_remove_all
-
-*/
-
-map_init :: proc{map_init_none, map_init_cap}
-
-map_init_none :: proc(m: ^$M/Map($Key, $Value), allocator := context.allocator) {
- m.hash.allocator = allocator
- m.entries.allocator = allocator
-}
-
-map_init_cap :: proc(m: ^$M/Map($Key, $Value), cap: int, allocator := context.allocator) {
- m.hash.allocator = allocator
- m.entries.allocator = allocator
- map_reserve(m, cap)
-}
-
-map_delete :: proc(m: $M/Map($Key, $Value)) {
- array_delete(m.hash)
- array_delete(m.entries)
-}
-
-
-map_has :: proc(m: $M/Map($Key, $Value), key: Key) -> bool {
- return _map_find_or_fail(m, key) >= 0
-}
-
-map_get :: proc(m: $M/Map($Key, $Value), key: Key) -> (res: Value, ok: bool) #optional_ok {
- i := _map_find_or_fail(m, key)
- if i < 0 {
- return {}, false
- }
- return array_get(m.entries, i).value, true
-}
-
-map_get_default :: proc(m: $M/Map($Key, $Value), key: Key, default: Value) -> (res: Value, ok: bool) #optional_ok {
- i := _map_find_or_fail(m, key)
- if i < 0 {
- return default, false
- }
- return array_get(m.entries, i).value, true
-}
-
-map_get_ptr :: proc(m: $M/Map($Key, $Value), key: Key) -> ^Value {
- i := _map_find_or_fail(m, key)
- if i < 0 {
- return nil
- }
- return array_get_ptr(m.entries, i).value
-}
-
-map_set :: proc(m: ^$M/Map($Key, $Value), key: Key, value: Value) {
- if array_len(m.hash) == 0 {
- _map_grow(m)
- }
-
- i := _map_find_or_make(m, key)
- array_get_ptr(m.entries, i).value = value
- if _map_full(m^) {
- _map_grow(m)
- }
-}
-
-map_remove :: proc(m: ^$M/Map($Key, $Value), key: Key) {
- fr := _map_find_key(m^, key)
- if fr.entry_index >= 0 {
- _map_erase(m, fr)
- }
-}
-
-
-map_reserve :: proc(m: ^$M/Map($Key, $Value), new_size: int) {
- nm: M
- map_init(&nm, m.hash.allocator)
- array_resize(&nm.hash, new_size)
- array_reserve(&nm.entries, array_len(m.entries))
-
- for i in 0..<new_size {
- array_set(&nm.hash, i, -1)
- }
- for i in 0..<array_len(m.entries) {
- e := array_get(m.entries, i)
- multi_map_insert(&nm, e.key, e.value)
- }
-
- map_delete(m^)
- m^ = nm
-}
-
-map_clear :: proc(m: ^$M/Map($Key, $Value)) {
- array_clear(&m.hash)
- array_clear(&m.entries)
-}
-
-
-
-multi_map_find_first :: proc(m: $M/Map($Key, $Value), key: Key) -> ^Map_Entry(Key, Value) {
- i := _map_find_or_fail(m, key)
- if i < 0 {
- return nil
- }
- return array_get_ptr(m.entries, i)
-}
-
-multi_map_find_next :: proc(m: $M/Map($Key, $Value), e: ^Map_Entry(Key, Value)) -> ^Map_Entry(Key, Value) {
- i := e.next
- for i >= 0 {
- it := array_get_ptr(m.entries, i)
- if it.hash == e.hash && it.key == e.key {
- return it
- }
- i = it.next
- }
- return nil
-}
-
-multi_map_count :: proc(m: $M/Map($Key, $Value), key: Key) -> int {
- n := 0
- e := multi_map_find_first(m, key)
- for e != nil {
- n += 1
- e = multi_map_find_next(m, e)
- }
- return n
-}
-
-multi_map_get :: proc{multi_map_get_array, multi_map_get_slice}
-
-multi_map_get_array :: proc(m: $M/Map($Key, $Value), key: Key, items: ^Array(Value)) {
- if items == nil {
- return
- }
- e := multi_map_find_first(m, key)
- for e != nil {
- array_append(items, e.value)
- e = multi_map_find_next(m, e)
- }
-}
-
-multi_map_get_slice :: proc(m: $M/Map($Key, $Value), key: Key, items: []Value) {
- e := multi_map_find_first(m, key)
- i := 0
- for e != nil && i < len(items) {
- items[i] = e.value
- i += 1
- e = multi_map_find_next(m, e)
- }
-}
-
-multi_map_get_as_slice :: proc(m: $M/Map($Key, $Value), key: Key) -> []Value {
- items: Array(Value)
- array_init(&items, 0)
-
- e := multi_map_find_first(m, key)
- for e != nil {
- array_append(&items, e.value)
- e = multi_map_find_next(m, e)
- }
-
- return array_slice(items)
-}
-
-
-multi_map_insert :: proc(m: ^$M/Map($Key, $Value), key: Key, value: Value) {
- if array_len(m.hash) == 0 {
- _map_grow(m)
- }
-
- i := _map_make(m, key)
- array_get_ptr(m.entries, i).value = value
- if _map_full(m^) {
- _map_grow(m)
- }
-}
-
-multi_map_remove :: proc(m: ^$M/Map($Key, $Value), e: ^Map_Entry(Key, Value)) {
- fr := _map_find_entry(m, e)
- if fr.entry_index >= 0 {
- _map_erase(m, fr)
- }
-}
-
-multi_map_remove_all :: proc(m: ^$M/Map($Key, $Value), key: Key) {
- for map_exist(m^, key) {
- map_remove(m, key)
- }
-}
-
-
-/// Internal
-
-
-Map_Find_Result :: struct {
- hash_index: int,
- entry_prev: int,
- entry_index: int,
-}
-
-_map_add_entry :: proc(m: ^$M/Map($Key, $Value), key: Key) -> int where intrinsics.type_is_valid_map_key(Key) {
- hasher := intrinsics.type_hasher_proc(Key)
-
- e: Map_Entry(Key, Value)
- e.key = key
- e.hash = hasher(&e.key, 0)
- e.next = -1
- idx := array_len(m.entries)
- array_push(&m.entries, e)
- return idx
-}
-
-_map_erase :: proc(m: ^$M/Map, fr: Map_Find_Result) {
- if fr.entry_prev < 0 {
- array_set(&m.hash, fr.hash_index, array_get(m.entries, fr.entry_index).next)
- } else {
- array_get_ptr(m.entries, fr.entry_prev).next = array_get(m.entries, fr.entry_index).next
- }
-
- if fr.entry_index == array_len(m.entries)-1 {
- array_pop_back(&m.entries)
- return
- }
-
- array_set(&m.entries, fr.entry_index, array_get(m.entries, array_len(m.entries)-1))
- last := _map_find_key(m^, array_get(m.entries, fr.entry_index).key)
-
- if last.entry_prev < 0 {
- array_get_ptr(m.entries, last.entry_prev).next = fr.entry_index
- } else {
- array_set(&m.hash, last.hash_index, fr.entry_index)
- }
-}
-
-
-_map_find_key :: proc(m: $M/Map($Key, $Value), key: Key) -> Map_Find_Result where intrinsics.type_is_valid_map_key(Key) {
- fr: Map_Find_Result
- fr.hash_index = -1
- fr.entry_prev = -1
- fr.entry_index = -1
-
- if array_len(m.hash) == 0 {
- return fr
- }
-
- hasher := intrinsics.type_hasher_proc(Key)
-
- key := key
- hash := hasher(&key, 0)
-
- fr.hash_index = int(hash % uintptr(array_len(m.hash)))
- fr.entry_index = array_get(m.hash, fr.hash_index)
- for fr.entry_index >= 0 {
- it := array_get_ptr(m.entries, fr.entry_index)
- if it.hash == hash && it.key == key {
- return fr
- }
- fr.entry_prev = fr.entry_index
- fr.entry_index = it.next
- }
- return fr
-}
-
-_map_find_entry :: proc(m: ^$M/Map($Key, $Value), e: ^Map_Entry(Key, Value)) -> Map_Find_Result {
- fr: Map_Find_Result
- fr.hash_index = -1
- fr.entry_prev = -1
- fr.entry_index = -1
-
- if array_len(m.hash) == 0 {
- return fr
- }
-
- fr.hash_index = int(e.hash % uintptr(array_len(m.hash)))
- fr.entry_index = array_get(m.hash, fr.hash_index)
- for fr.entry_index >= 0 {
- it := array_get_ptr(m.entries, fr.entry_index)
- if it == e {
- return fr
- }
- fr.entry_prev = fr.entry_index
- fr.entry_index = it.next
- }
- return fr
-}
-
-_map_find_or_fail :: proc(m: $M/Map($Key, $Value), key: Key) -> int {
- return _map_find_key(m, key).entry_index
-}
-_map_find_or_make :: proc(m: ^$M/Map($Key, $Value), key: Key) -> int {
- fr := _map_find_key(m^, key)
- if fr.entry_index >= 0 {
- return fr.entry_index
- }
-
- i := _map_add_entry(m, key)
- if fr.entry_prev < 0 {
- array_set(&m.hash, fr.hash_index, i)
- } else {
- array_get_ptr(m.entries, fr.entry_prev).next = i
- }
- return i
-}
-
-
-_map_make :: proc(m: ^$M/Map($Key, $Value), key: Key) -> int {
- fr := _map_find_key(m^, key)
- i := _map_add_entry(m, key)
-
- if fr.entry_prev < 0 {
- array_set(&m.hash, fr.hash_index, i)
- } else {
- array_get_ptr(m.entries, fr.entry_prev).next = i
- }
-
- array_get_ptr(m.entries, i).next = fr.entry_index
-
- return i
-}
-
-
-_map_full :: proc(m: $M/Map($Key, $Value)) -> bool {
- // TODO(bill): Determine good max load factor
- return array_len(m.entries) >= (array_len(m.hash) / 4)*3
-}
-
-_map_grow :: proc(m: ^$M/Map($Key, $Value)) {
- new_size := array_len(m.entries) * 4 + 7 // TODO(bill): Determine good grow rate
- map_reserve(m, new_size)
-}
-
-
diff --git a/core/container/priority_queue.odin b/core/container/priority_queue.odin
deleted file mode 100644
index c54e964a6..000000000
--- a/core/container/priority_queue.odin
+++ /dev/null
@@ -1,121 +0,0 @@
-package container
-
-Priority_Queue :: struct($T: typeid) {
- data: Array(T),
- len: int,
- priority: proc(item: T) -> int,
-}
-
-priority_queue_init_none :: proc(q: ^$Q/Priority_Queue($T), f: proc(item: T) -> int, allocator := context.allocator) {
- queue_init_len(q, f, 0, allocator)
-}
-priority_queue_init_len :: proc(q: ^$Q/Priority_Queue($T), f: proc(item: T) -> int, len: int, allocator := context.allocator) {
- queue_init_len_cap(q, f, 0, 16, allocator)
-}
-priority_queue_init_len_cap :: proc(q: ^$Q/Priority_Queue($T), f: proc(item: T) -> int, len: int, cap: int, allocator := context.allocator) {
- array_init(&q.data, len, cap, allocator)
- q.len = len
- q.priority = f
-}
-
-priority_queue_init :: proc{priority_queue_init_none, priority_queue_init_len, priority_queue_init_len_cap}
-
-
-priority_queue_delete :: proc(q: $Q/Priority_Queue($T)) {
- array_delete(q.data)
-}
-
-priority_queue_clear :: proc(q: ^$Q/Priority_Queue($T)) {
- q.len = 0
-}
-
-priority_queue_len :: proc(q: $Q/Priority_Queue($T)) -> int {
- return q.len
-}
-
-priority_queue_cap :: proc(q: $Q/Priority_Queue($T)) -> int {
- return array_cap(q.data)
-}
-
-priority_queue_space :: proc(q: $Q/Priority_Queue($T)) -> int {
- return array_len(q.data) - q.len
-}
-
-priority_queue_reserve :: proc(q: ^$Q/Priority_Queue($T), capacity: int) {
- if capacity > q.len {
- array_resize(&q.data, new_capacity)
- }
-}
-
-priority_queue_resize :: proc(q: ^$Q/Priority_Queue($T), length: int) {
- if length > q.len {
- array_resize(&q.data, new_capacity)
- }
- q.len = length
-}
-
-_priority_queue_grow :: proc(q: ^$Q/Priority_Queue($T), min_capacity: int = 0) {
- new_capacity := max(array_len(q.data)*2 + 8, min_capacity)
- array_resize(&q.data, new_capacity)
-}
-
-
-priority_queue_push :: proc(q: ^$Q/Priority_Queue($T), item: T) {
- if array_len(q.data) - q.len == 0 {
- _priority_queue_grow(q)
- }
-
- s := array_slice(q.data)
- s[q.len] = item
-
- i := q.len
- for i > 0 {
- p := (i - 1) / 2
- if q.priority(s[p]) <= q.priority(item) {
- break
- }
- s[i] = s[p]
- i = p
- }
-
- q.len += 1
- if q.len > 0 {
- s[i] = item
- }
-}
-
-
-
-priority_queue_pop :: proc(q: ^$Q/Priority_Queue($T)) -> T {
- assert(q.len > 0)
-
- s := array_slice(q.data)
- min := s[0]
- root := s[q.len-1]
- q.len -= 1
-
- i := 0
- for i * 2 + 1 < q.len {
- a := i * 2 + 1
- b := i * 2 + 2
- c := b < q.len && q.priority(s[b]) < q.priority(s[a]) ? b : a
-
- if q.priority(s[c]) >= q.priority(root) {
- break
- }
- s[i] = s[c]
- i = c
- }
-
- if q.len > 0 {
- s[i] = root
- }
- return min
-}
-
-priority_queue_peek :: proc(q: ^$Q/Priority_Queue($T)) -> T {
- assert(q.len > 0)
-
- s := array_slice(q.data)
- return s[0]
-}
diff --git a/core/container/queue.odin b/core/container/queue.odin
deleted file mode 100644
index bab4a18e6..000000000
--- a/core/container/queue.odin
+++ /dev/null
@@ -1,175 +0,0 @@
-package container
-
-Queue :: struct($T: typeid) {
- data: Array(T),
- len: int,
- offset: int,
-}
-
-/*
-queue_init :: proc{
- queue_init_none,
- queue_init_len,
- queue_init_len_cap,
-}
-queue_delete
-queue_clear
-queue_len
-queue_cap
-queue_space
-queue_get
-queue_set
-queue_reserve
-queue_resize
-queue_push :: proc{
- queue_push_back,
- queue_push_elems,
-};
-queue_push_front
-queue_pop_front
-queue_pop_back
-queue_consume
-*/
-
-queue_init_none :: proc(q: ^$Q/Queue($T), allocator := context.allocator) {
- queue_init_len(q, 0, allocator)
-}
-queue_init_len :: proc(q: ^$Q/Queue($T), len: int, allocator := context.allocator) {
- queue_init_len_cap(q, 0, 16, allocator)
-}
-queue_init_len_cap :: proc(q: ^$Q/Queue($T), len: int, cap: int, allocator := context.allocator) {
- array_init(&q.data, len, cap, allocator)
- q.len = len
- q.offset = 0
-}
-
-queue_init :: proc{queue_init_none, queue_init_len, queue_init_len_cap}
-
-queue_delete :: proc(q: $Q/Queue($T)) {
- array_delete(q.data)
-}
-
-queue_clear :: proc(q: ^$Q/Queue($T)) {
- q.len = 0
-}
-
-queue_len :: proc(q: $Q/Queue($T)) -> int {
- return q.len
-}
-
-queue_cap :: proc(q: $Q/Queue($T)) -> int {
- return array_cap(q.data)
-}
-
-queue_space :: proc(q: $Q/Queue($T)) -> int {
- return array_len(q.data) - q.len
-}
-
-queue_get :: proc(q: $Q/Queue($T), index: int) -> T {
- i := (index + q.offset) % array_len(q.data)
- data := array_slice(q.data)
- return data[i]
-}
-
-queue_set :: proc(q: ^$Q/Queue($T), index: int, item: T) {
- i := (index + q.offset) % array_len(q.data)
- data := array_slice(q.data)
- data[i] = item
-}
-
-
-queue_reserve :: proc(q: ^$Q/Queue($T), capacity: int) {
- if capacity > q.len {
- _queue_increase_capacity(q, capacity)
- }
-}
-
-queue_resize :: proc(q: ^$Q/Queue($T), length: int) {
- if length > q.len {
- _queue_increase_capacity(q, length)
- }
- q.len = length
-}
-
-queue_push_back :: proc(q: ^$Q/Queue($T), item: T) {
- if queue_space(q^) == 0 {
- _queue_grow(q)
- }
-
- queue_set(q, q.len, item)
- q.len += 1
-}
-
-queue_push_front :: proc(q: ^$Q/Queue($T), item: T) {
- if queue_space(q^) == 0 {
- _queue_grow(q)
- }
-
- q.offset = (q.offset - 1 + array_len(q.data)) % array_len(q.data)
- q.len += 1
- queue_set(q, 0, item)
-}
-
-queue_pop_front :: proc(q: ^$Q/Queue($T)) -> T {
- assert(q.len > 0)
- item := queue_get(q^, 0)
- q.offset = (q.offset + 1) % array_len(q.data)
- q.len -= 1
- if q.len == 0 {
- q.offset = 0
- }
- return item
-}
-
-queue_pop_back :: proc(q: ^$Q/Queue($T)) -> T {
- assert(q.len > 0)
- item := queue_get(q^, q.len-1)
- q.len -= 1
- return item
-}
-
-queue_consume :: proc(q: ^$Q/Queue($T), count: int) {
- q.offset = (q.offset + count) & array_len(q.data)
- q.len -= count
-}
-
-
-queue_push_elems :: proc(q: ^$Q/Queue($T), items: ..T) {
- if queue_space(q^) < len(items) {
- _queue_grow(q, q.len + len(items))
- }
- size := array_len(q.data)
- insert := (q.offset + q.len) % size
-
- to_insert := len(items)
- if insert + to_insert > size {
- to_insert = size - insert
- }
-
- the_items := items[:]
-
- data := array_slice(q.data)
-
- q.len += copy(data[insert:][:to_insert], the_items)
- the_items = the_items[to_insert:]
- q.len += copy(data[:], the_items)
-}
-
-queue_push :: proc{queue_push_back, queue_push_elems}
-
-
-
-_queue_increase_capacity :: proc(q: ^$Q/Queue($T), new_capacity: int) {
- end := array_len(q.data)
- array_resize(&q.data, new_capacity)
- if q.offset + q.len > end {
- end_items := q.len + end
- data := array_slice(q.data)
- copy(data[new_capacity-end_items:][:end_items], data[q.offset:][:end_items])
- q.offset += new_capacity - end
- }
-}
-_queue_grow :: proc(q: ^$Q/Queue($T), min_capacity: int = 0) {
- new_capacity := max(array_len(q.data)*2 + 8, min_capacity)
- _queue_increase_capacity(q, new_capacity)
-}
diff --git a/core/container/ring.odin b/core/container/ring.odin
deleted file mode 100644
index 61492ec84..000000000
--- a/core/container/ring.odin
+++ /dev/null
@@ -1,74 +0,0 @@
-package container
-
-
-Ring :: struct($T: typeid) {
- next, prev: ^Ring(T),
- value: T,
-}
-
-ring_init :: proc(r: ^$R/Ring) -> ^R {
- r.prev, r.next = r, r
- return r
-}
-
-ring_next :: proc(r: ^$R/Ring) -> ^R {
- if r.next == nil {
- return ring_init(r)
- }
- return r.next
-}
-ring_prev :: proc(r: ^$R/Ring) -> ^R {
- if r.prev == nil {
- return ring_init(r)
- }
- return r.prev
-}
-
-
-ring_move :: proc(r: ^$R/Ring, n: int) -> ^R {
- r := r
- if r.next == nil {
- return ring_init(r)
- }
-
- switch {
- case n < 0:
- for _ in n..<0 {
- r = r.prev
- }
- case n > 0:
- for _ in 0..<n {
- r = r.next
- }
- }
- return r
-}
-
-ring_link :: proc(r, s: ^$R/Ring) -> ^R {
- n := ring_next(r)
- if s != nil {
- p := ring_prev(s)
- r.next = s
- s.prev = r
- n.prev = p
- p.next = n
- }
- return n
-}
-ring_unlink :: proc(r: ^$R/Ring, n: int) -> ^R {
- if n <= 0 {
- return nil
- }
- return ring_link(r, ring_move(r, n+1))
-}
-ring_len :: proc(r: ^$R/Ring) -> int {
- n := 0
- if r != nil {
- n = 1
- for p := ring_next(r); p != r; p = p.next {
- n += 1
- }
- }
- return n
-}
-
diff --git a/core/container/set.odin b/core/container/set.odin
deleted file mode 100644
index 562ac5409..000000000
--- a/core/container/set.odin
+++ /dev/null
@@ -1,240 +0,0 @@
-package container
-
-Set :: struct {
- hash: Array(int),
- entries: Array(Set_Entry),
-}
-
-Set_Entry :: struct {
- key: u64,
- next: int,
-}
-
-
-/*
-set_init :: proc{
- set_init_none,
- set_init_cap,
-}
-set_delete
-
-set_in
-set_not_in
-set_add
-set_remove
-set_reserve
-set_clear
-*/
-
-set_init :: proc{set_init_none, set_init_cap}
-
-set_init_none :: proc(m: ^Set, allocator := context.allocator) {
- m.hash.allocator = allocator
- m.entries.allocator = allocator
-}
-
-set_init_cap :: proc(m: ^Set, cap: int, allocator := context.allocator) {
- m.hash.allocator = allocator
- m.entries.allocator = allocator
- set_reserve(m, cap)
-}
-
-set_delete :: proc(m: Set) {
- array_delete(m.hash)
- array_delete(m.entries)
-}
-
-
-set_in :: proc(m: Set, key: u64) -> bool {
- return _set_find_or_fail(m, key) >= 0
-}
-set_not_in :: proc(m: Set, key: u64) -> bool {
- return _set_find_or_fail(m, key) < 0
-}
-
-set_add :: proc(m: ^Set, key: u64) {
- if array_len(m.hash) == 0 {
- _set_grow(m)
- }
-
- _ = _set_find_or_make(m, key)
- if _set_full(m^) {
- _set_grow(m)
- }
-}
-
-set_remove :: proc(m: ^Set, key: u64) {
- fr := _set_find_key(m^, key)
- if fr.entry_index >= 0 {
- _set_erase(m, fr)
- }
-}
-
-
-set_reserve :: proc(m: ^Set, new_size: int) {
- nm: Set
- set_init(&nm, m.hash.allocator)
- array_resize(&nm.hash, new_size)
- array_reserve(&nm.entries, array_len(m.entries))
-
- for i in 0..<new_size {
- array_set(&nm.hash, i, -1)
- }
- for i in 0..<array_len(m.entries) {
- e := array_get(m.entries, i)
- set_add(&nm, e.key)
- }
-
- set_delete(m^)
- m^ = nm
-}
-
-set_clear :: proc(m: ^Set) {
- array_clear(&m.hash)
- array_clear(&m.entries)
-}
-
-
-set_equal :: proc(a, b: Set) -> bool {
- a_entries := array_slice(a.entries)
- b_entries := array_slice(b.entries)
- if len(a_entries) != len(b_entries) {
- return false
- }
- for e in a_entries {
- if set_not_in(b, e.key) {
- return false
- }
- }
-
- return true
-}
-
-
-
-/// Internal
-
-_set_add_entry :: proc(m: ^Set, key: u64) -> int {
- e: Set_Entry
- e.key = key
- e.next = -1
- idx := array_len(m.entries)
- array_push(&m.entries, e)
- return idx
-}
-
-_set_erase :: proc(m: ^Set, fr: Map_Find_Result) {
- if fr.entry_prev < 0 {
- array_set(&m.hash, fr.hash_index, array_get(m.entries, fr.entry_index).next)
- } else {
- array_get_ptr(m.entries, fr.entry_prev).next = array_get(m.entries, fr.entry_index).next
- }
-
- if fr.entry_index == array_len(m.entries)-1 {
- array_pop_back(&m.entries)
- return
- }
-
- array_set(&m.entries, fr.entry_index, array_get(m.entries, array_len(m.entries)-1))
- last := _set_find_key(m^, array_get(m.entries, fr.entry_index).key)
-
- if last.entry_prev < 0 {
- array_get_ptr(m.entries, last.entry_prev).next = fr.entry_index
- } else {
- array_set(&m.hash, last.hash_index, fr.entry_index)
- }
-}
-
-
-_set_find_key :: proc(m: Set, key: u64) -> Map_Find_Result {
- fr: Map_Find_Result
- fr.hash_index = -1
- fr.entry_prev = -1
- fr.entry_index = -1
-
- if array_len(m.hash) == 0 {
- return fr
- }
-
- fr.hash_index = int(key % u64(array_len(m.hash)))
- fr.entry_index = array_get(m.hash, fr.hash_index)
- for fr.entry_index >= 0 {
- it := array_get_ptr(m.entries, fr.entry_index)
- if it.key == key {
- return fr
- }
- fr.entry_prev = fr.entry_index
- fr.entry_index = it.next
- }
- return fr
-}
-
-_set_find_entry :: proc(m: ^Set, e: ^Set_Entry) -> Map_Find_Result {
- fr: Map_Find_Result
- fr.hash_index = -1
- fr.entry_prev = -1
- fr.entry_index = -1
-
- if array_len(m.hash) == 0 {
- return fr
- }
-
- fr.hash_index = int(e.key % u64(array_len(m.hash)))
- fr.entry_index = array_get(m.hash, fr.hash_index)
- for fr.entry_index >= 0 {
- it := array_get_ptr(m.entries, fr.entry_index)
- if it == e {
- return fr
- }
- fr.entry_prev = fr.entry_index
- fr.entry_index = it.next
- }
- return fr
-}
-
-_set_find_or_fail :: proc(m: Set, key: u64) -> int {
- return _set_find_key(m, key).entry_index
-}
-_set_find_or_make :: proc(m: ^Set, key: u64) -> int {
- fr := _set_find_key(m^, key)
- if fr.entry_index >= 0 {
- return fr.entry_index
- }
-
- i := _set_add_entry(m, key)
- if fr.entry_prev < 0 {
- array_set(&m.hash, fr.hash_index, i)
- } else {
- array_get_ptr(m.entries, fr.entry_prev).next = i
- }
- return i
-}
-
-
-_set_make :: proc(m: ^Set, key: u64) -> int {
- fr := _set_find_key(m^, key)
- i := _set_add_entry(m, key)
-
- if fr.entry_prev < 0 {
- array_set(&m.hash, fr.hash_index, i)
- } else {
- array_get_ptr(m.entries, fr.entry_prev).next = i
- }
-
- array_get_ptr(m.entries, i).next = fr.entry_index
-
- return i
-}
-
-
-_set_full :: proc(m: Set) -> bool {
- // TODO(bill): Determine good max load factor
- return array_len(m.entries) >= (array_len(m.hash) / 4)*3
-}
-
-_set_grow :: proc(m: ^Set) {
- new_size := array_len(m.entries) * 4 + 7 // TODO(bill): Determine good grow rate
- set_reserve(m, new_size)
-}
-
-
diff --git a/core/container/small_array.odin b/core/container/small_array.odin
deleted file mode 100644
index 43b879d2d..000000000
--- a/core/container/small_array.odin
+++ /dev/null
@@ -1,95 +0,0 @@
-package container
-
-Small_Array :: struct($N: int, $T: typeid) where N >= 0 {
- data: [N]T,
- len: int,
-}
-
-
-small_array_len :: proc(a: $A/Small_Array) -> int {
- return a.len
-}
-
-small_array_cap :: proc(a: $A/Small_Array) -> int {
- return len(a.data)
-}
-
-small_array_space :: proc(a: $A/Small_Array) -> int {
- return len(a.data) - a.len
-}
-
-small_array_slice :: proc(a: ^$A/Small_Array($N, $T)) -> []T {
- return a.data[:a.len]
-}
-
-
-small_array_get :: proc(a: $A/Small_Array($N, $T), index: int, loc := #caller_location) -> T {
- return a.data[index]
-}
-small_array_get_ptr :: proc(a: $A/Small_Array($N, $T), index: int, loc := #caller_location) -> ^T {
- return &a.data[index]
-}
-
-small_array_set :: proc(a: ^$A/Small_Array($N, $T), index: int, item: T, loc := #caller_location) {
- a.data[index] = item
-}
-
-small_array_resize :: proc(a: ^$A/Small_Array, length: int) {
- a.len = min(length, len(a.data))
-}
-
-
-small_array_push_back :: proc(a: ^$A/Small_Array($N, $T), item: T) -> bool {
- if a.len < len(a.data) {
- a.len += 1
- a.data[a.len-1] = item
- return true
- }
- return false
-}
-
-small_array_push_front :: proc(a: ^$A/Small_Array($N, $T), item: T) -> bool {
- if a.len < len(a.data) {
- a.len += 1
- data := small_array_slice(a)
- copy(data[1:], data[:])
- data[0] = item
- return true
- }
- return false
-}
-
-small_array_pop_back :: proc(a: ^$A/Small_Array($N, $T), loc := #caller_location) -> T {
- assert(condition=a.len > 0, loc=loc)
- item := a.data[a.len-1]
- a.len -= 1
- return item
-}
-
-small_array_pop_front :: proc(a: ^$A/Small_Array($N, $T), loc := #caller_location) -> T {
- assert(condition=a.len > 0, loc=loc)
- item := a.data[0]
- s := small_array_slice(a)
- copy(s[:], s[1:])
- a.len -= 1
- return item
-}
-
-
-small_array_consume :: proc(a: ^$A/Small_Array($N, $T), count: int, loc := #caller_location) {
- assert(condition=a.len >= count, loc=loc)
- a.len -= count
-}
-
-small_array_clear :: proc(a: ^$A/Small_Array($N, $T)) {
- small_array_resize(a, 0)
-}
-
-small_array_push_back_elems :: proc(a: ^$A/Small_Array($N, $T), items: ..T) {
- n := copy(a.data[a.len:], items[:])
- a.len += n
-}
-
-small_array_push :: proc{small_array_push_back, small_array_push_back_elems}
-small_array_append :: proc{small_array_push_back, small_array_push_back_elems}
-