From 2a0c6b4cfeb5d1725e65e714ce7f324583dfa388 Mon Sep 17 00:00:00 2001 From: Syndamia Date: Tue, 21 Apr 2026 19:32:40 +0300 Subject: feat!: Initial implementation --- Array.c | 80 ++++++++++++++++++++ Array.h | 15 ++++ BumpAlloc.c | 116 +++++++++++++++++++++++++++++ BumpAlloc.h | 16 ++++ GlobalArena.c | 28 +++++++ GlobalArena.h | 17 +++++ String.c | 230 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ String.h | 25 +++++++ Types.h | 33 +++++++++ main.c | 29 ++++++++ 10 files changed, 589 insertions(+) create mode 100644 Array.c create mode 100644 Array.h create mode 100644 BumpAlloc.c create mode 100644 BumpAlloc.h create mode 100644 GlobalArena.c create mode 100644 GlobalArena.h create mode 100644 String.c create mode 100644 String.h create mode 100644 Types.h create mode 100644 main.c diff --git a/Array.c b/Array.c new file mode 100644 index 0000000..c9c9984 --- /dev/null +++ b/Array.c @@ -0,0 +1,80 @@ +#include "Array.h" +#include "Types.h" +#include +#include + +struct ArrayMeta { + BumpArena b; + usize element_size; + usize count; + usize length; +}; + +static inline struct ArrayMeta* +Array_metadata(void* arr) { + return arr - sizeof(struct ArrayMeta); +} + +typedef void* Array; + +Array +Array_new(BumpArena b, usize element_size, usize length) { + if (NULL == b) + return NULL; + + struct ArrayMeta am = { + .b = b, + .element_size = element_size, + .count = 0, + .length = length, + }; + + void* start = Balloc(b, sizeof(am) + element_size * length); + memcpy(start, &am, sizeof(am)); + return start + sizeof(am); +} + +usize +Array_length(Array arr) { + if (NULL == arr) + return 0; + return Array_metadata(arr)->length; +} + +usize +Array_count(Array arr) { + if (NULL == arr) + return 0; + return Array_metadata(arr)->count; +} + +Result +Array_push(Array arr, void *value) { + if (NULL == arr) + return R_Uninitialized; + + struct ArrayMeta *am = Array_metadata(arr); + + if (am->count >= am->length) { + if (!Bresizeable(am->b, arr)) + abort(); + Bresize(am->b, sizeof(*am) + am->element_size * (am->length <<= 2)); + } + + memcpy(arr + am->count++ * am->element_size, value, am->element_size); + + return R_Ok; +} + +void* +Array_pop(Array arr) { + if (NULL == arr) + return NULL; + + struct ArrayMeta *am = Array_metadata(arr); + + if (am->count == 0) + return NULL; + + return arr + am->element_size * --am->count; +} diff --git a/Array.h b/Array.h new file mode 100644 index 0000000..41b36e7 --- /dev/null +++ b/Array.h @@ -0,0 +1,15 @@ +#ifndef _ARRAY +#define _ARRAY + +#include "Types.h" +#include "BumpAlloc.h" + +typedef void* Array; + +Array Array_new(BumpArena b, usize element_size, usize length); +usize Array_length(Array arr); +usize Array_count(Array arr); +Result Array_push(Array arr, void *value); +void* Array_pop(Array arr); + +#endif /* _ARRAY */ diff --git a/BumpAlloc.c b/BumpAlloc.c new file mode 100644 index 0000000..327bfd5 --- /dev/null +++ b/BumpAlloc.c @@ -0,0 +1,116 @@ +#include "BumpAlloc.h" +#include "Types.h" +#include +#include + +struct BumpArena { + void* memory; + usize size; + usize top; +}; + +BumpArena +Bcreate(usize size) { + struct BumpArena *b = malloc(sizeof(struct BumpArena)); + b->memory = malloc(size); + b->size = size; + b->top = 0; + + return b; +} + +Result +Bdestroy(BumpArena bp) { + if (NULL == bp) + return R_Uninitialized; + + struct BumpArena b = *(struct BumpArena*)bp; + + if (NULL == b.memory) + return R_Uninitialized; + + free(b.memory); + b.memory = NULL; + b.size = b.top = 0; + + return R_Ok; +} + +static inline usize* +top_size(struct BumpArena* b) { + return (usize*)(b->memory + b->top); +} + +void* +Balloc(BumpArena bp, usize size) { + if (bp == NULL || size == 0) + return NULL; + + struct BumpArena *b = (struct BumpArena*)bp; + + if (size + b->top + sizeof(usize) > b->size) + return NULL; + + if (b->top > 0) + b->top += sizeof(usize); + usize start = b->top; + + b->top += size; + // Keep allocated memory size at the end of every allocation + *top_size(b) = size; + + return b->memory + start; +} + +int +Bresizeable(BumpArena bp, void* ptr) { + if (NULL == bp) + return 0; + + struct BumpArena *b = (struct BumpArena*)bp; + + return b->memory + b->top - *top_size(b) <= ptr && + ptr < b->memory + b->top; +} + +Result +Bresize(BumpArena bp, usize size) { + if (NULL == bp) + return R_Uninitialized; + + struct BumpArena *b = (struct BumpArena*)bp; + + if (size == 0) { + Bfree(bp); + return R_Ok; + } + + usize last_size = *top_size(b); + usize start = b->top - last_size; + if (start > 0) + start -= sizeof(usize); + + if (start + size + sizeof(usize) > b->size) + return R_OutOfBounds; + + b->top += size; + *top_size(b) = size; + + return R_Ok; +} + +Result +Bfree(BumpArena bp) { + if (NULL == bp) + return R_Uninitialized; + + struct BumpArena *b = (struct BumpArena*)bp; + + if (b->top > 0) { + b->top -= *top_size(b); + if (b->top > 0) + b->top -= sizeof(usize); + } + + return R_Ok; +} diff --git a/BumpAlloc.h b/BumpAlloc.h new file mode 100644 index 0000000..e6ba3e3 --- /dev/null +++ b/BumpAlloc.h @@ -0,0 +1,16 @@ +#ifndef _BUMP_ALLOC +#define _BUMP_ALLOC + +#include "Types.h" + +typedef void* BumpArena; + +BumpArena Bcreate(usize size); +Result Bdestroy(BumpArena b); + +void* Balloc(BumpArena b, usize size); +int Bresizeable(BumpArena b, void* ptr); +Result Bresize(BumpArena b, usize size); +Result Bfree(BumpArena b); + +#endif /* _BUMP_ALLOC */ diff --git a/GlobalArena.c b/GlobalArena.c new file mode 100644 index 0000000..2b45f84 --- /dev/null +++ b/GlobalArena.c @@ -0,0 +1,28 @@ +#include "GlobalArena.h" + +BumpArena g_arena = NULL; + +void* +GBalloc(usize size) { + return Balloc(g_arena, size); +} + +int +GBresizeable(void* ptr) { + return Bresizeable(g_arena, ptr); +} + +Result +GBresize(usize size) { + return Bresize(g_arena, size); +} + +Result +GBfree() { + return Bfree(g_arena); +} + +Array +Array_Gnew(usize element_size, usize length) { + return Array_new(g_arena, element_size, length); +} diff --git a/GlobalArena.h b/GlobalArena.h new file mode 100644 index 0000000..219e743 --- /dev/null +++ b/GlobalArena.h @@ -0,0 +1,17 @@ +#ifndef _GLOBAL_ARENA +#define _GLOBAL_ARENA + +#include "BumpAlloc.h" +#include "Array.h" + +// Global bump arena +extern BumpArena g_arena; + +void* GBalloc(usize size); +int GBresizeable(void* ptr); +Result GBresize(usize size); +Result GBfree(); + +Array Array_Gnew(usize element_size, usize length); + +#endif /* _GLOBAL_ARENA */ diff --git a/String.c b/String.c new file mode 100644 index 0000000..2467189 --- /dev/null +++ b/String.c @@ -0,0 +1,230 @@ +#include "String.h" +#include "GlobalArena.h" +#include "Types.h" +#include +#include +#include + +struct StringMeta { + BumpArena b; + usize length; +}; + +static inline struct StringMeta* +String_metadata(String s) { + return (struct StringMeta*)(s - sizeof(struct StringMeta)); +} + +String +String_new(BumpArena b, const char* str) { + if (NULL == b || NULL == str) + return NULL; + + struct StringMeta sm = { + .b = b, + .length = strlen(str), + }; + + void* start = Balloc(b, sizeof(sm) + sm.length + 1); + + memcpy(start, &sm, sizeof(sm)); + start += sizeof(sm); + memcpy(start, str, sm.length + 1); + + return start; +} + +String +String_newlen(BumpArena b, usize length) { + if (NULL == b) + return NULL; + + struct StringMeta sm = { + .b = b, + .length = length, + }; + + void* start = Balloc(b, sizeof(sm) + sm.length + 1); + + memcpy(start, &sm, sizeof(sm)); + start += sizeof(sm); + memset(start, '\0', sm.length + 1); + + return start; +} + +static inline usize +String_allocated(String s) { + return sizeof(struct StringMeta) + String_length(s) + 1; +} + +String +String_dup(BumpArena b, String s) { + if (NULL == b || NULL == s) + return NULL; + + usize allocated = String_allocated(s); + + void* start = Balloc(b, allocated); + memcpy(start, s - sizeof(struct StringMeta), allocated); + + return NULL; +} + +usize +String_length(String s) { + if (NULL == s) + return 0; + return String_metadata(s)->length; +} + +Result +String_append(String s, const char* str) { + if (NULL == s) + return R_Uninitialized; + + struct StringMeta* sm = String_metadata(s); + + usize strlength = strlen(str); + if (sm->length - strlen(s) < strlength) { + if (!Bresizeable(sm->b, s)) + return R_Err; + Bresize(sm->b, sizeof(*sm) + (sm->length += strlength) + 1); + } + + strcat(s, str); + return R_Ok; +} + +Result +String_prepend(String s, const char* str) { + if (NULL == s) + return R_Uninitialized; + + struct StringMeta* sm = String_metadata(s); + + usize strlength = strlen(str); + if (!Bresizeable(sm->b, s)) + return R_Err; + + usize orig_len = sm->length; + RETURN_NOTOK(Bresize(sm->b, sizeof(*sm) + (sm->length += strlength) + 1)); + + for (usize i = orig_len; i > 0; --i) + s[i - 1 + strlength] = s[i - 1]; + for (usize i = 0; i < strlength; ++i) + s[i] = str[i]; + + return R_Ok; +} + +usize +String_find(String s, char c) { + if (NULL == s) + return -1; + + unsigned index = 0; + while (s[index] != '\0' && s[index] != c) + ++index; + + return index; +} + +static String +String_vconcat(BumpArena b, va_list args) { + usize length = 0; + + va_list temp; + va_copy(temp, args); + for (const char* str = va_arg(temp, const char*); str != NULL; str = va_arg(temp, const char*)) { + length += strlen(str); + } + va_end(temp); + printf("%lu\n", length); + + String result = String_newlen(b, length); + + if (0 < length) { + for (const char* str = va_arg(args, const char*); str != NULL; str = va_arg(args, const char*)) + strncat(result, str, length); + } + return result; +} + +String +String_concat(BumpArena b, ...) { + va_list args; + usize length = 0; + + va_start(args, b); + String result = String_vconcat(b, args); + va_end(args); + + return result; +} + +static String +String_vprintf(BumpArena b, const char* fmt, va_list args) { + va_list temp; + va_copy(temp, args); + usize length = vsnprintf(NULL, 0, fmt, temp); + va_end(temp); + + String result = String_newlen(b, length); + vsnprintf(result, length, fmt, args); + + return result; +} + +String +String_printf(BumpArena b, const char* fmt, ...) { + va_list args; + + va_start(args, fmt); + String result = String_vprintf(b, fmt, args); + va_end(args); + + return result; +} + +String +String_Gnew(const char* str) { + return String_new(g_arena, str); +} + +String +String_Gnewlen(usize length) { + return String_newlen(g_arena, length); +} + +String +String_Gdup(String s) { + return String_dup(g_arena, s); +} + +String +String_Gconcat(const char* str, ...) { + if (str == NULL) + return NULL; + + va_list args; + + va_start(args, str); + String result = String_vconcat(g_arena, args); + va_end(args); + + String_prepend(result, str); + + return result; +} + +String +String_Gprintf(const char* fmt, ...) { + va_list args; + + va_start(args, fmt); + String result = String_vprintf(g_arena, fmt, args); + va_end(args); + + return result; +} diff --git a/String.h b/String.h new file mode 100644 index 0000000..3955339 --- /dev/null +++ b/String.h @@ -0,0 +1,25 @@ +#ifndef _STRING +#define _STRING + +#include "BumpAlloc.h" + +typedef char* String; + +String String_new(BumpArena b, const char* str); +String String_newlen(BumpArena b, usize length); +String String_dup(BumpArena b, String s); +String String_concat(BumpArena b, ...); +String String_printf(BumpArena b, const char* fmt, ...); + +usize String_length(String s); +Result String_append(String s, const char* str); +Result String_prepend(String s, const char* str); +usize String_find(String s, char c); + +String String_Gnew(const char* str); +String String_Gnewlen(usize length); +String String_Gdup(String s); +String String_Gconcat(const char* str, ...); +String String_Gprintf(const char* fmt, ...); + +#endif /* _STRING */ diff --git a/Types.h b/Types.h new file mode 100644 index 0000000..5801d93 --- /dev/null +++ b/Types.h @@ -0,0 +1,33 @@ +#ifndef _TYPES +#define _TYPES + +#include "stdint.h" +#include "stddef.h" + +typedef int_fast8_t i8; +typedef int_fast16_t i16; +typedef int_fast32_t i32; +typedef int_fast64_t i64; +typedef uint_fast8_t u8; +typedef uint_fast16_t u16; +typedef uint_fast32_t u32; +typedef uint_fast64_t u64; +typedef size_t usize; + +typedef enum Result { + R_Ok = 0, + R_Err, + R_Invalid, + R_Uninitialized, + R_OutOfBounds, + R_PRIVATE +} Result; + +#define RETURN_NOTOK(x) { Result r = x; if (R_Ok != r) return r; } + +#define B(x) ((x) * 8) +#define KiB(x) ((x) * 1024) +#define MiB(x) ((x) * 1048576) +#define GiB(x) ((x) * 1073741824) + +#endif /* _TYPES */ diff --git a/main.c b/main.c new file mode 100644 index 0000000..ccec7b2 --- /dev/null +++ b/main.c @@ -0,0 +1,29 @@ +#include "Array.h" +#include "BumpAlloc.h" +#include "GlobalArena.h" +#include "String.h" +#include + +int +main() { + g_arena = Bcreate(KiB(4)); + + int *nums = Array_Gnew(sizeof(int), 8); + for (int i = 10; i < 20; ++i) { + Array_push(nums, &i); + } + + printf("%lu/%lu |", Array_count(nums), Array_length(nums)); + for (int i = 0; i < Array_count(nums); ++i) + printf(" %d", nums[i]); + printf("\n"); + + String s = String_Gconcat("Hello", " ", "World", "!", NULL); + printf("%s\n", s); + + String s1 = String_Gprintf("%s #%d\n", s, 5); + printf("%s\n", s1); + + Bdestroy(g_arena); + return 0; +} -- cgit v1.2.3