diff options
Diffstat (limited to 'archive/src/std/containers')
| -rw-r--r-- | archive/src/std/containers/container_utils.h | 17 | ||||
| -rw-r--r-- | archive/src/std/containers/darray.h | 151 | ||||
| -rw-r--r-- | archive/src/std/containers/graphs.h | 14 | ||||
| -rw-r--r-- | archive/src/std/containers/hashmap.h | 27 | ||||
| -rw-r--r-- | archive/src/std/containers/hashset.h | 29 | ||||
| -rw-r--r-- | archive/src/std/containers/ring_queue.c | 68 | ||||
| -rw-r--r-- | archive/src/std/containers/ring_queue.h | 35 | ||||
| -rw-r--r-- | archive/src/std/containers/stack_array.h | 19 |
8 files changed, 360 insertions, 0 deletions
diff --git a/archive/src/std/containers/container_utils.h b/archive/src/std/containers/container_utils.h new file mode 100644 index 0000000..e1d164c --- /dev/null +++ b/archive/src/std/containers/container_utils.h @@ -0,0 +1,17 @@ +/** + * @file container_utils.h + * @author your name (you@domain.com) + * @brief + * @version 0.1 + * @date 2024-06-19 + * + * @copyright Copyright (c) 2024 + * + */ + +#pragma once + +typedef struct generic_iterator { +} generic_iterator; + +typedef void* (*iterator_next_item)(void* iterator);
\ No newline at end of file diff --git a/archive/src/std/containers/darray.h b/archive/src/std/containers/darray.h new file mode 100644 index 0000000..080afb4 --- /dev/null +++ b/archive/src/std/containers/darray.h @@ -0,0 +1,151 @@ +/** + * @file darray.h + * @brief Typed dynamic array + * @copyright Copyright (c) 2023 + */ +// COPIED FROM KITC WITH SOME MINOR ADJUSTMENTS + +/* TODO: + - a 'find' function that takes a predicate (maybe wrap with a macro so we dont have to define a + new function?) +*/ + +#ifndef KITC_TYPED_ARRAY_H +#define KITC_TYPED_ARRAY_H + +#include <stddef.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define DARRAY_DEFAULT_CAPACITY 64 +#define DARRAY_RESIZE_FACTOR 3 + +/** @brief create a new darray type and functions with type `N` */ +#define typed_array(T) \ + struct { \ + /* @brief current number of items in the array */ \ + size_t len; \ + size_t capacity; \ + T* data; \ + } + +#define typed_array_iterator(T) \ + struct { \ + T##_darray* array; \ + size_t current_idx; \ + } + +#define PREFIX static + +#define KITC_DECL_TYPED_ARRAY(T) DECL_TYPED_ARRAY(T, T) + +#define DECL_TYPED_ARRAY(T, Type) \ + typedef typed_array(T) Type##_darray; \ + typedef typed_array_iterator(Type) Type##_darray_iter; \ + \ + /* Create a new one growable array */ \ + PREFIX Type##_darray* Type##_darray_new(size_t starting_capacity) { \ + Type##_darray* d; \ + T* data; \ + d = malloc(sizeof(Type##_darray)); \ + data = malloc(starting_capacity * sizeof(T)); \ + \ + d->len = 0; \ + d->capacity = starting_capacity; \ + d->data = data; \ + \ + return d; \ + } \ + \ + PREFIX void Type##_darray_free(Type##_darray* d) { \ + if (d != NULL) { \ + free(d->data); \ + free(d); \ + } \ + } \ + \ + PREFIX T* Type##_darray_resize(Type##_darray* d, size_t capacity) { \ + /* resize the internal data block */ \ + T* new_data = realloc(d->data, sizeof(T) * capacity); \ + /* TODO: handle OOM error */ \ + \ + d->capacity = capacity; \ + d->data = new_data; \ + return new_data; \ + } \ + \ + PREFIX void Type##_darray_push(Type##_darray* d, T value) { \ + if (d->len >= d->capacity) { \ + size_t new_capacity = \ + d->capacity > 0 ? d->capacity * DARRAY_RESIZE_FACTOR : DARRAY_DEFAULT_CAPACITY; \ + T* resized = Type##_darray_resize(d, new_capacity); \ + (void)resized; \ + } \ + \ + d->data[d->len] = value; \ + d->len += 1; \ + } \ + \ + PREFIX void Type##_darray_push_copy(Type##_darray* d, const T* value) { \ + if (d->len >= d->capacity) { \ + size_t new_capacity = \ + d->capacity > 0 ? d->capacity * DARRAY_RESIZE_FACTOR : DARRAY_DEFAULT_CAPACITY; \ + T* resized = Type##_darray_resize(d, new_capacity); \ + (void)resized; \ + } \ + \ + T* place = d->data + d->len; \ + d->len += 1; \ + memcpy(place, value, sizeof(T)); \ + } \ + \ + PREFIX void Type##_darray_pop(Type##_darray* d, T* dest) { \ + T* item = d->data + (d->len - 1); \ + d->len -= 1; \ + memcpy(dest, item, sizeof(T)); \ + } \ + \ + PREFIX void Type##_darray_ins(Type##_darray* d, const T* value, size_t index) { \ + /* check if requires resize */ \ + if (d->len + 1 > d->capacity) { \ + size_t new_capacity = \ + d->capacity > 0 ? d->capacity * DARRAY_RESIZE_FACTOR : DARRAY_DEFAULT_CAPACITY; \ + T* resized = Type##_darray_resize(d, new_capacity); \ + (void)resized; \ + } \ + \ + /* shift existing data after index */ \ + T* insert_dest = d->data + index; \ + T* shift_dest = insert_dest + 1; \ + \ + int num_items = d->len - index; \ + \ + d->len += 1; \ + memcpy(shift_dest, insert_dest, num_items * sizeof(T)); \ + memcpy(insert_dest, value, sizeof(T)); \ + } \ + \ + PREFIX void Type##_darray_clear(Type##_darray* d) { \ + d->len = 0; \ + memset(d->data, 0, d->capacity * sizeof(T)); \ + } \ + \ + PREFIX size_t Type##_darray_len(Type##_darray* d) { return d->len; } \ + \ + PREFIX Type##_darray_iter Type##_darray_iter_new(Type##_darray* d) { \ + Type##_darray_iter iterator; \ + iterator.array = d; \ + iterator.current_idx = 0; \ + return iterator; \ + } \ + \ + PREFIX void* Type##_darray_iter_next(Type##_darray_iter* iterator) { \ + if (iterator->current_idx < iterator->array->len) { \ + return &iterator->array->data[iterator->current_idx++]; \ + } else { \ + return NULL; \ + } \ + } + +#endif // KITC_TYPED_ARRAY_H diff --git a/archive/src/std/containers/graphs.h b/archive/src/std/containers/graphs.h new file mode 100644 index 0000000..5dbec97 --- /dev/null +++ b/archive/src/std/containers/graphs.h @@ -0,0 +1,14 @@ +/** + * @file graphs.h + * @author your name (you@domain.com) + * @brief + * @version 0.1 + * @date 2024-04-27 + * + * @copyright Copyright (c) 2024 + * + */ + +// Adjacency list backed graphs + +// Matrix backed graphs (not as useful)
\ No newline at end of file diff --git a/archive/src/std/containers/hashmap.h b/archive/src/std/containers/hashmap.h new file mode 100644 index 0000000..95c1c6b --- /dev/null +++ b/archive/src/std/containers/hashmap.h @@ -0,0 +1,27 @@ +/** + * @file hashmap.h + * @author your name (you@domain.com) + * @brief + * @version 0.1 + * @date 2024-04-27 + * + * @copyright Copyright (c) 2024 + * + */ + +typedef struct hashmap hashmap; + +/* +Example usage +------------- +init hashmap +insert (string, material) +get (string) -> material_opt or material* ? + +*/ + +void hashmap_init(hashmap* map); + +// ... + +void hashmap_free(hashmap* map);
\ No newline at end of file diff --git a/archive/src/std/containers/hashset.h b/archive/src/std/containers/hashset.h new file mode 100644 index 0000000..7f87213 --- /dev/null +++ b/archive/src/std/containers/hashset.h @@ -0,0 +1,29 @@ +/** + * @file hashset.h + * @author your name (you@domain.com) + * @brief + * @version 0.1 + * @date 2024-04-27 + * + * @copyright Copyright (c) 2024 + * + */ + +#include "defines.h" + +typedef struct hashset hashset; + +/** @brief Describes a function that will take a pointer to a datatype (e.g. a u64 or a struct) + and return a hashed key. */ +typedef uint64_t (*hash_item)(void* item); + +void hashset_init(hashset* set, hash_item hash_func, size_t initial_capacity); +// TODO: void hashset_from_iterator(); +bool hashset_insert(hashset* set, void* item, uint64_t* out_key); +void hashset_batch_insert(hashset* set, void* items, u64 item_count); +bool hashset_contains(hashset* set, void* item); +bool hashset_remove_item(hashset* set, void* item); +bool hashset_remove_key(hashset* set, uint64_t key); +void hashset_merge(hashset* set_a, hashset* set_b); +hashset* hashset_merge_cloned(hashset* set_a, hashset* set_b); +void hashset_free(hashset* set);
\ No newline at end of file diff --git a/archive/src/std/containers/ring_queue.c b/archive/src/std/containers/ring_queue.c new file mode 100644 index 0000000..8bfc10b --- /dev/null +++ b/archive/src/std/containers/ring_queue.c @@ -0,0 +1,68 @@ +#include "ring_queue.h" + +#include <stdlib.h> +#include <string.h> +#include "defines.h" + +ring_queue* ring_queue_new(size_t type_size, size_t capacity, void* memory) { + ring_queue* q = malloc(sizeof(ring_queue)); + q->len = 0; + q->capacity = capacity; + q->type_size = type_size; + q->head = 0; + q->tail = -1; + + if (memory) { + // caller owns the memory + q->owns_memory = false; + q->data = memory; + } else { + // ring queue should own the memory + q->owns_memory = true; + q->data = malloc(capacity * type_size); + } + + return q; +} + +void ring_queue_free(ring_queue* queue) { + if (queue) { + if (queue->owns_memory) { + free(queue->data); + } + free(queue); + } +} + +bool ring_queue_enqueue(ring_queue* queue, const void* value) { + if (queue->len == queue->capacity) { + return false; + } + + queue->tail = (queue->tail + 1) % queue->capacity; + memcpy(queue->data + (queue->tail * queue->type_size), value, queue->type_size); + queue->len++; + return true; +} + +bool ring_queue_dequeue(ring_queue* queue, void* out_value) { + if (queue->len == 0) { + // queue is empty + return false; + } + + memcpy(out_value, queue->data + (queue->head * queue->type_size), queue->type_size); + queue->head = (queue->head + 1) % queue->capacity; + queue->len--; + return true; +} + +bool ring_queue_peek(const ring_queue* queue, void* out_value) { + if (queue->len == 0) { + // queue is empty + return false; + } + + memcpy(out_value, queue->data + (queue->head * queue->type_size), queue->type_size); + return true; +}
\ No newline at end of file diff --git a/archive/src/std/containers/ring_queue.h b/archive/src/std/containers/ring_queue.h new file mode 100644 index 0000000..15d5da4 --- /dev/null +++ b/archive/src/std/containers/ring_queue.h @@ -0,0 +1,35 @@ +/** + * @file ring_queue.h + * @author your name (you@domain.com) + * @brief + * @version 0.1 + * @date 2024-02-24 + * + * @copyright Copyright (c) 2024 + * + */ +#pragma once +#include "defines.h" + +/** + * @brief a fixed-size ring queue + */ +typedef struct ring_queue { + size_t len; + size_t capacity; + size_t type_size; + void* data; + bool owns_memory; + int32_t head; + int32_t tail; +} ring_queue; + +ring_queue* ring_queue_new(size_t type_size, size_t capacity, void* memory_block); + +void ring_queue_free(ring_queue* queue); + +bool ring_queue_enqueue(ring_queue* queue, const void* value); + +bool ring_queue_dequeue(ring_queue* queue, void* out_value); + +bool ring_queue_peek(const ring_queue* queue, void* out_value);
\ No newline at end of file diff --git a/archive/src/std/containers/stack_array.h b/archive/src/std/containers/stack_array.h new file mode 100644 index 0000000..d2b6bdd --- /dev/null +++ b/archive/src/std/containers/stack_array.h @@ -0,0 +1,19 @@ +#pragma once +#include <stdbool.h> + +// Defines "_sarray" types + +#define TYPED_STACK_ARRAY(T, Name, Len) \ + typedef struct Name##_sarray { \ + T items[ Len ]; \ + size_t len; \ + } Name##_sarray; \ + Name##_sarray Name##_sarray_create() { \ + Name##_sarray arr = { .len = 0 }; \ + return arr; \ + } \ + bool Name##_sarray_push(Name##_sarray* arr, T item) { \ + if (arr->len == Len) { return false; }\ + arr->items[arr->len++] = item;\ + return true;\ + } |