summaryrefslogtreecommitdiff
path: root/src/std
diff options
context:
space:
mode:
Diffstat (limited to 'src/std')
-rw-r--r--src/std/buf.h17
-rw-r--r--src/std/containers/darray.h49
-rw-r--r--src/std/containers/graphs.h14
-rw-r--r--src/std/containers/hashset.h10
-rw-r--r--src/std/containers/hashtable.h10
-rw-r--r--src/std/mem.c97
-rw-r--r--src/std/mem.h57
-rw-r--r--src/std/utils.h4
8 files changed, 233 insertions, 25 deletions
diff --git a/src/std/buf.h b/src/std/buf.h
new file mode 100644
index 0000000..de093ec
--- /dev/null
+++ b/src/std/buf.h
@@ -0,0 +1,17 @@
+/**
+ * @file buf.h
+ * @author your name (you@domain.com)
+ * @brief
+ * @version 0.1
+ * @date 2024-04-28
+ *
+ * @copyright Copyright (c) 2024
+ *
+ */
+#pragma once
+#include "defines.h"
+
+typedef struct bytebuffer {
+ u8* buf;
+ size_t size;
+} bytebuffer;
diff --git a/src/std/containers/darray.h b/src/std/containers/darray.h
index 25bf846..b15d269 100644
--- a/src/std/containers/darray.h
+++ b/src/std/containers/darray.h
@@ -5,6 +5,11 @@
*/
// 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
@@ -39,15 +44,17 @@
/* } else {\ */
/* }\ */
-#define KITC_DECL_TYPED_ARRAY(T) \
- typedef typed_array(T) T##_darray; \
- typedef typed_array_iterator(T) T##_darray_iter; \
+#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 T##_darray *T##_darray_new(size_t starting_capacity) { \
- T##_darray *d; \
+ PREFIX Type##_darray *Type##_darray_new(size_t starting_capacity) { \
+ Type##_darray *d; \
T *data; \
- d = malloc(sizeof(T##_darray)); \
+ d = malloc(sizeof(Type##_darray)); \
data = malloc(starting_capacity * sizeof(T)); \
\
d->len = 0; \
@@ -57,14 +64,14 @@
return d; \
} \
\
- PREFIX void T##_darray_free(T##_darray *d) { \
+ PREFIX void Type##_darray_free(Type##_darray *d) { \
if (d != NULL) { \
free(d->data); \
free(d); \
} \
} \
\
- PREFIX T *T##_darray_resize(T##_darray *d, size_t capacity) { \
+ 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 */ \
@@ -74,22 +81,22 @@
return new_data; \
} \
\
- PREFIX void T##_darray_push(T##_darray *d, T value) { \
+ 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 = T##_darray_resize(d, new_capacity); \
+ T *resized = Type##_darray_resize(d, new_capacity); \
} \
\
d->data[d->len] = value; \
d->len += 1; \
} \
\
- PREFIX void T##_darray_push_copy(T##_darray *d, const T *value) { \
+ 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 = T##_darray_resize(d, new_capacity); \
+ T *resized = Type##_darray_resize(d, new_capacity); \
} \
\
T *place = d->data + d->len; \
@@ -97,18 +104,18 @@
memcpy(place, value, sizeof(T)); \
} \
\
- PREFIX void T##_darray_pop(T##_darray *d, T *dest) { \
+ 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 T##_darray_ins(T##_darray *d, const T *value, size_t index) { \
+ 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 = T##_darray_resize(d, new_capacity); \
+ T *resized = Type##_darray_resize(d, new_capacity); \
} \
\
/* shift existing data after index */ \
@@ -122,14 +129,14 @@
memcpy(insert_dest, value, sizeof(T)); \
} \
\
- PREFIX void T##_darray_clear(T##_darray *d) { \
+ PREFIX void Type##_darray_clear(Type##_darray *d) { \
d->len = 0; \
memset(d->data, 0, d->capacity * sizeof(T)); \
} \
\
- PREFIX size_t T##_darray_len(T##_darray *d) { return d->len; } \
+ PREFIX size_t Type##_darray_len(Type##_darray *d) { return d->len; } \
\
- PREFIX void T##_darray_print(T##_darray *d) { \
+ PREFIX void Type##_darray_print(Type##_darray *d) { \
printf("len: %zu ", d->len); \
printf("capacity: %zu\n", d->capacity); \
for (int i = 0; i < d->len; i++) { \
@@ -137,14 +144,14 @@
} \
} \
\
- PREFIX T##_darray_iter T##_darray_iter_new(T##_darray *d) { \
- T##_darray_iter iterator; \
+ 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 *T##_darray_iter_next(T##_darray_iter *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 { \
diff --git a/src/std/containers/graphs.h b/src/std/containers/graphs.h
new file mode 100644
index 0000000..5dbec97
--- /dev/null
+++ b/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/src/std/containers/hashset.h b/src/std/containers/hashset.h
new file mode 100644
index 0000000..d153fd2
--- /dev/null
+++ b/src/std/containers/hashset.h
@@ -0,0 +1,10 @@
+/**
+ * @file hashset.h
+ * @author your name (you@domain.com)
+ * @brief
+ * @version 0.1
+ * @date 2024-04-27
+ *
+ * @copyright Copyright (c) 2024
+ *
+ */ \ No newline at end of file
diff --git a/src/std/containers/hashtable.h b/src/std/containers/hashtable.h
new file mode 100644
index 0000000..f5d98e7
--- /dev/null
+++ b/src/std/containers/hashtable.h
@@ -0,0 +1,10 @@
+/**
+ * @file hashtable.h
+ * @author your name (you@domain.com)
+ * @brief
+ * @version 0.1
+ * @date 2024-04-27
+ *
+ * @copyright Copyright (c) 2024
+ *
+ */ \ No newline at end of file
diff --git a/src/std/mem.c b/src/std/mem.c
index 00f9c39..a5321fb 100644
--- a/src/std/mem.c
+++ b/src/std/mem.c
@@ -1,13 +1,17 @@
-#include "mem.h"
+#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
+
#include "log.h"
+#include "mem.h"
#ifndef DEFAULT_ALIGNMENT
#define DEFAULT_ALIGNMENT (2 * sizeof(void*))
#endif
+// --- Arena
+
void* arena_alloc_align(arena* a, size_t size, size_t align) {
ptrdiff_t padding = -(uintptr_t)a->curr & (align - 1);
ptrdiff_t available = a->end - a->curr - padding;
@@ -15,7 +19,7 @@ void* arena_alloc_align(arena* a, size_t size, size_t align) {
if (available < 0 || (ptrdiff_t)size > available) {
ERROR_EXIT("Arena ran out of memory\n");
}
- void* p = a->begin + padding;
+ void* p = a->curr + padding;
a->curr += padding + size;
return memset(p, 0, size);
}
@@ -31,4 +35,91 @@ void arena_free_all(arena* a) {
a->curr = a->begin; // pop everything at once and reset to the start.
}
-void arena_free_storage(arena* a) { free(a->begin); } \ No newline at end of file
+void arena_free_storage(arena* a) { free(a->begin); }
+
+arena_save arena_savepoint(arena* a) {
+ arena_save savept = { .arena = a, .savepoint = a->curr };
+ return savept;
+}
+
+void arena_rewind(arena_save savepoint) { savepoint.arena->curr = savepoint.savepoint; }
+
+// --- Pool
+
+void_pool void_pool_create(arena* a, u64 capacity, u64 entry_size) {
+ size_t memory_requirements = capacity * entry_size;
+ void* backing_buf = arena_alloc(a, memory_requirements);
+
+ void_pool pool = { .capacity = capacity,
+ .entry_size = entry_size,
+ .count = 0,
+ .backing_buffer = backing_buf,
+ .free_list_head = NULL };
+
+ void_pool_free_all(&pool);
+
+ return pool;
+}
+
+void void_pool_free_all(void_pool* pool) {
+ // set all entries to be free
+ for (u64 i = 0; i < pool->capacity; i++) {
+ void* ptr = &pool->backing_buffer[i * pool->entry_size];
+ void_pool_header* free_node =
+ (void_pool_header*)ptr; // we reuse the actual entry itself to hold the header
+ if (i == (pool->capacity - 1)) {
+ // if the last one we make its next pointer NULL indicating its full
+ free_node->next = NULL;
+ }
+ free_node->next = pool->free_list_head;
+ // now the head points to this entry
+ pool->free_list_head = free_node;
+ }
+}
+
+void* void_pool_get(void_pool* pool, u32 raw_handle) {
+ // An handle is an index into the array essentially
+ void* ptr = pool->backing_buffer + (raw_handle * pool->entry_size);
+ return ptr;
+}
+
+void* void_pool_alloc(void_pool* pool, u32* out_raw_handle) {
+ // get the next free node
+ if (pool->count == pool->capacity) {
+ WARN("Pool is full!");
+ return NULL;
+ }
+ if (pool->free_list_head == NULL) {
+ ERROR("Pool is full (head = null)");
+ return NULL;
+ }
+ void_pool_header* free_node = pool->free_list_head;
+
+ // What index does this become?
+ uintptr_t start = (uintptr_t)pool->backing_buffer;
+ uintptr_t cur = (uintptr_t)free_node;
+ TRACE("%ld %ld ", start, cur);
+ /* assert(cur > start); */
+ u32 index = (u32)((cur - start) / pool->entry_size);
+ printf("Index %d\n", index);
+ if (out_raw_handle != NULL) {
+ *out_raw_handle = index;
+ }
+
+ pool->free_list_head = free_node->next;
+
+ memset(free_node, 0, pool->entry_size);
+ pool->count++;
+ return (void*)free_node;
+}
+
+void void_pool_dealloc(void_pool* pool, u32 raw_handle) {
+ // push free node back onto the free list
+ void* ptr = void_pool_get(pool, raw_handle);
+ void_pool_header* freed_node = (void_pool_header*)ptr;
+
+ freed_node->next = pool->free_list_head;
+ pool->free_list_head = freed_node;
+
+ pool->count--;
+}
diff --git a/src/std/mem.h b/src/std/mem.h
index 2f92894..26da778 100644
--- a/src/std/mem.h
+++ b/src/std/mem.h
@@ -10,6 +10,9 @@
#pragma once
#include <stddef.h>
+#include "defines.h"
+
+// --- Arena
// Inspired by https://nullprogram.com/blog/2023/09/27/
typedef struct arena {
@@ -18,9 +21,61 @@ typedef struct arena {
char* end;
} arena;
+typedef struct arena_save {
+ arena* arena;
+ char* savepoint;
+} arena_save;
+
arena arena_create(void* backing_buffer, size_t capacity);
void* arena_alloc(arena* a, size_t size);
void* arena_alloc_align(arena* a, size_t size, size_t align);
void arena_free_all(arena* a);
void arena_free_storage(arena* a);
-// TODO: arena_resize \ No newline at end of file
+arena_save arena_savepoint(arena* a);
+void arena_rewind(arena_save savepoint);
+// TODO: arena_resize
+
+// --- Pool
+
+typedef struct void_pool_header void_pool_header;
+struct void_pool_header {
+ void_pool_header* next;
+};
+
+typedef struct void_pool {
+ u64 capacity;
+ u64 entry_size;
+ u64 count;
+ void* backing_buffer;
+ void_pool_header* free_list_head;
+} void_pool;
+
+void_pool void_pool_create(arena* a, u64 capacity, u64 entry_size);
+void void_pool_free_all(void_pool* pool);
+bool void_pool_is_empty(void_pool* pool);
+bool void_pool_is_full(void_pool* pool);
+void* void_pool_get(void_pool* pool, u32 raw_handle);
+void* void_pool_alloc(void_pool* pool, u32* out_raw_handle);
+void void_pool_dealloc(void_pool* pool, u32 raw_handle);
+
+// TODO: macro that lets us specialise
+
+/* typedef struct Name##_handle Name##_handle; \ */
+#define TYPED_POOL(T, Name) \
+ typedef struct Name##_pool { \
+ void_pool inner; \
+ } Name##_pool; \
+ \
+ static Name##_pool Name##_pool_create(arena* a, u64 cap, u64 entry_size) { \
+ void_pool p = void_pool_create(a, cap, entry_size); \
+ return (Name##_pool){ .inner = p }; \
+ } \
+ static inline T* Name##_pool_get(Name##_pool* pool, Name##_handle handle) { \
+ return (T*)void_pool_get(&pool->inner, handle.raw); \
+ } \
+ static inline T* Name##_pool_alloc(Name##_pool* pool, Name##_handle* out_handle) { \
+ return (T*)void_pool_alloc(&pool->inner, &out_handle->raw); \
+ } \
+ static inline void Name##_pool_dealloc(Name##_pool* pool, Name##_handle handle) { \
+ void_pool_dealloc(&pool->inner, handle.raw); \
+ }\
diff --git a/src/std/utils.h b/src/std/utils.h
new file mode 100644
index 0000000..c9827a3
--- /dev/null
+++ b/src/std/utils.h
@@ -0,0 +1,4 @@
+#pragma once
+#include <stdbool.h>
+
+const char* bool_str(bool input) { return input ? "True" : "False"; } \ No newline at end of file
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-01-10 22:06:28 +0000