`package container` with `Queue` and `Array`

2 files changed, 308 insertions, 0 deletions

diff --git a/core/container/array.odin b/core/container/array.odin
new file mode 100644
index 000000000..273657eb6
--- /dev/null
+++ b/core/container/array.odin
@@ -0,0 +1,160 @@
+package container
+
+import "core:mem"
+
+Array :: struct(T: typeid) {
+	data:      ^T,
+	len:       int,
+	cap:       int,
+	allocator: mem.Allocator,
+}
+
+array_init_none :: proc(a: ^$A/Array, allocator := context.allocator) {
+	array_init_len(a, 0, allocator);
+}
+array_init_len :: proc(a: ^$A/Array, len: int, allocator := context.allocator) {
+	array_init_len_cap(a, 0, 16, allocator);
+}
+array_init_len_cap :: proc(a: ^$A/Array($T), len: int, cap: int, allocator := context.allocator) {
+	a.data = (^T)(mem.alloc(size_of(T)*cap, align_of(T), allocator));
+	a.len = len;
+	a.cap = cap;
+	a.allocator = allocator;
+}
+
+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_get :: proc(a: $A/Array($T), index: int) -> T {
+	return (^T)(uintptr(a.data) + size_of(T)*uintptr(index))^;
+}
+
+array_set :: proc(a: ^$A/Array($T), index: int, item: T)  {
+	(^T)(uintptr(a.data) + size_of(T)*uintptr(index))^ = item;
+}
+
+
+array_reserve :: proc(a: ^$A/Array, capacity: int) {
+	if capacity > a.size {
+		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.size += 1;
+	array_set(a, a.size, 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)) -> T {
+	assert(a.len > 0);
+	item := array_get(a^, a.len-1);
+	a.len -= 1;
+	return item;
+}
+
+array_pop_font :: proc(a: ^$A/Array($T)) -> T {
+	assert(a.len > 0);
+	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) {
+	assert(a.size >= count);
+	a.size -= count;
+}
+
+
+array_trim :: proc(a: ^$A/Array($T)) {
+	array_set_capacity(a, a.len);
+}
+
+array_clear :: proc(q: ^$Q/Queue($T)) {
+	array_resize(q, 0);
+}
+
+
+array_push :: proc(a: ^$A/Array($T), items: ..T) {
+	if array_space(a^) < len(items) {
+		array_grow(a, a.size + len(items));
+	}
+	offset := a.len;
+	a.len += len(items);
+	data := array_slice(a^);
+	n := copy(data[offset:], items);
+	a.len = offset + n;
+}
+
+
+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 {
+		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.data = new_data;
+	a.cap = new_capacity;
+}
+array_grow :: proc(a: ^$A/Array, min_capacity: int = 0) {
+	new_capacity := max(len(a.data)*2 + 8, min_capacity);
+	array_set_capacity(a, new_capacity);
+}
diff --git a/core/container/queue.odin b/core/container/queue.odin
new file mode 100644
index 000000000..ce6e75559
--- /dev/null
+++ b/core/container/queue.odin
@@ -0,0 +1,148 @@
+package container
+
+Queue :: struct(T: typeid) {
+	data: Array(T),
+	len: int,
+	offset: int,
+}
+
+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;
+	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);
+}