diff options
| -rw-r--r-- | .clangd | 2 | ||||
| -rw-r--r-- | Makefile | 16 | ||||
| -rw-r--r-- | main.c | 50 | ||||
| -rw-r--r-- | moonshine.h | 662 | ||||
| -rw-r--r-- | moonshine.m4 | 4 |
5 files changed, 360 insertions, 374 deletions
@@ -1,5 +1,5 @@ CompileFlags: - Add: [-xc, --analyze, -nostdlib, -nostdinc, -Wno-incompatible-library-redeclaration, -Wall, -Wextra] + Add: [-xc, -nostartfiles, -nostdlib, -nostdinc, -Wno-incompatible-library-redeclaration, -Wall, -Wextra] Remove: [-Wincompatible-library-redeclaration] Compiler: clang @@ -1,8 +1,12 @@ -FLAGS = -Wno-incompatible-library-redeclaration -nostartfiles +FLAGS = -Wno-incompatible-library-redeclaration -nostartfiles -nostdlib SIZE_FLAGS = -Wl,--undefined=main -flto -Oz -ffunction-sections -fdata-sections -Wl,--gc-sections -Wl,--strip-all -finline-hint-functions -fno-builtin -Wl,--print-gc-sections -fno-unwind-tables -fomit-frame-pointer -fno-asynchronous-unwind-tables -fno-ident -fvisibility=hidden -march=native -Wl,--build-id=none all: m4 c test +clean: + rm -rf out.* + rm -rf *.m4.h + m4: m4 moonshine.m4 > moonshine.m4.h @@ -17,16 +21,6 @@ profile: perf record ./out.bin.profile perf report > ./out.profile.txt -# useless. it don't work. -# profile: -# clang -D__MOONSHINE_PROFILER main.c -o out.bin.profile $(FLAGS) $(SIZE_FLAGS) -fprofile-generate -# echo NOTE: Let the program run completely and provide it with typical inputs. -# ./out.bin.profile -# llvm-profdata merge -output=default.profdata profile.profraw -# rm -rf profile.profraw -# clang main.c -o out.bin.release $(FLAGS) $(SIZE_FLAGS) -fprofile-use -# rm -rf profile.profdata - release: clang main.c -o out.bin.release $(FLAGS) $(SIZE_FLAGS) @@ -2,7 +2,7 @@ #include "moonshine.h" -const enum { test_datatype, test_linkedlist, test_hashtable, test_alloc, test_array } current_test = test_array; +const enum { test_datatype, test_linkedlist, test_hashtable, test_alloc, test_array, test_hashtable_2 } current_test = test_hashtable; int main() { if (current_test == test_alloc) { @@ -14,26 +14,37 @@ int main() { *v1 = 2; *v2 = 99; - print(*v1, *v2); + println(*v1, *v2); release(v1); - print(*v2); + println(*v2); } else if (current_test == test_array) { auto arr = new (int); push(arr, 4); push(arr, 9); + push(arr, 3); + push(arr, 5); set(arr, 0, 2); - print(get(arr, 0)); + + println("Original"); + + foreach(i in arr) println("[", (u8)i_index, "] ", i); + + println("Reversed"); + + reverse_array(arr); + + foreach(i in arr) println("[", (u8)i_index, "] ", i); } else if (current_test == test_datatype) { datatype(binarytree, ((leaf, int), (node, binarytree *, int, binarytree *) )); const auto tree = instance(binarytree, leaf, 3); - print(&tree); + println(&tree); match(tree) { - of(leaf, v) print("Leafy ", v); - of(node, _, v, _) print("Nodey ", v); - other() print("Idk man"); + of(leaf, v) println("Leafy ", v); + of(node, _, v, _) println("Nodey ", v); + other() println("Idk man"); } } else if (current_test == test_linkedlist) { const auto ll = create_linkedlist(); @@ -42,20 +53,27 @@ int main() { print((u8) index_to_ptr(ll, 12)->data); } else if (current_test == test_hashtable) { - const auto ht = create_table( - table_hash_2, (struct hashtable_optimizations) { .run_ptr_check = true, .collision_character_check_count = 10 }); + const auto ht = create_hasharray( + table_hash_2); - for (u8 i = 0; i < 10000; i++) { - if (i % 1000 == 0) print("I ", i); - set_hashtable(ht, "hello", "world"); - set_hashtable(ht, "how", "are you"); + for (u8 i = 0; i < 10000000; i++) { + if (i % 1000000 == 0) println("I ", i); + set_hasharray(ht, "hello", "world"); + set_hasharray(ht, "how", "are you"); } - print((string) get_hashtable(ht, "hello"), ' ', (string) get_hashtable(ht, "how"), ' ', get_hashtable(ht, "wowie")); + println((string) get_hasharray(ht, "hello"), ' ', (string) get_hasharray(ht, "how"), ' ', get_hasharray(ht, "wowie")); + } else if (current_test == test_hashtable_2) { + const auto ht = create_hasharray(table_hash_2); + + set_hasharray(ht, "hello", "hi"); + println("Value: ", (string)get_hasharray(ht, "hello")); + set_hasharray(ht, "hello", "meow"); + println("Value after: ", (string)get_hasharray(ht, "hello")); } else { - print("Unknown test."); + throw("Unknown test."); } return 0; diff --git a/moonshine.h b/moonshine.h index 9f545b8..241f365 100644 --- a/moonshine.h +++ b/moonshine.h @@ -10,12 +10,13 @@ #include "moonshine.m4.h" -#define overload __attribute__((overloadable)) -#define line overload flatten -#define unused __attribute__((unused)) +#define fn_overload __attribute__((overloadable)) +#define fn_line fn_overload flatten +#define attr_unused __attribute__((unused)) // algebraic data type macros +#define exp(a, ...) a(__VA_ARGS__) #define expand(...) __VA_ARGS__ #define tail(x, ...) __VA_ARGS__ #define head(x, ...) x @@ -37,7 +38,7 @@ } #define instance(__type, kind, ...) ((struct __type) { .type = cat(kind, _type), .data.kind = { __VA_ARGS__ } }) #define scope(name, ...) \ - _Pragma("unroll") for (auto name unused = __VA_ARGS__, datatype_break = (typeof(name)) 0; \ + _Pragma("unroll") for (auto name attr_unused = __VA_ARGS__, datatype_break = (typeof(name)) 0; \ datatype_break == (typeof(name)) 0; \ datatype_break = (typeof(name)) 1) #define match(value) scope(parent_value, &value) switch (parent_value->type) @@ -53,6 +54,13 @@ // array macros #define obj(type) (type *) alloc(sizeof(type)) +#define clone(value) \ + ({ \ + auto _val = value; \ + auto _ptr = alloc(sizeof(_val)); \ + memcpy(_ptr, &_val, sizeof(_val)); \ + _ptr; \ + }) #define new(a, ...) ((a **) new_x(a __VA_OPT__(, ) __VA_ARGS__, new2, new1)(a __VA_OPT__(, ) __VA_ARGS__)) #define new_x(a, b, c, ...) c @@ -275,7 +283,8 @@ void puts_static_ptr(car value, u8 size) { puts_size(*(string *) value, size); } } \ }); -#define print(...) \ +#define print(...) ({ EXPAND_general(print_local, "broken print", __VA_ARGS__); }) +#define println(...) \ ({ \ EXPAND_general(print_local, "broken print", __VA_ARGS__); \ putchar('\n'); \ @@ -468,21 +477,21 @@ bool mine(const ptr pointer) { return output; } -line void printer(const char x, ctring unused text) { putchar(x); } -line void printer(ctring x, ctring unused text) { puts(x); } -line void printer(const int x, ctring text) { +fn_line void printer(const char x, ctring attr_unused text) { putchar(x); } +fn_line void printer(ctring x, ctring attr_unused text) { puts(x); } +fn_line void printer(const int x, ctring text) { if (text[ 0 ] == '\'') putchar(x); else puts_number(x, 1); } -line void printer(const long x, ctring unused text) { puts_number(x, true); } -line void printer(const unsigned long x, ctring unused text) { puts_number(x, false); } -line void printer(const u4 x, ctring unused text) { puts_number(x, false); } -line void printer(const short x, ctring unused text) { puts_number(x, false); } -line void printer(const unsigned short x, ctring unused text) { puts_number(x, false); } -line void printer(const float x, ctring unused text) { puts_float(x); } -line void printer(const double x, ctring unused text) { puts_float(x); } -line void printer(const bool x, ctring unused text) { +fn_line void printer(const long x, ctring attr_unused text) { puts_number(x, true); } +fn_line void printer(const unsigned long x, ctring attr_unused text) { puts_number(x, false); } +fn_line void printer(const u4 x, ctring attr_unused text) { puts_number(x, false); } +fn_line void printer(const short x, ctring attr_unused text) { puts_number(x, false); } +fn_line void printer(const unsigned short x, ctring attr_unused text) { puts_number(x, false); } +fn_line void printer(const float x, ctring attr_unused text) { puts_float(x); } +fn_line void printer(const double x, ctring attr_unused text) { puts_float(x); } +fn_line void printer(const bool x, ctring attr_unused text) { if (x) puts_static("true"); else if (x == 0) { puts_static("false"); @@ -490,7 +499,7 @@ line void printer(const bool x, ctring unused text) { putchar(x); } } -line void printer(var x, ctring unused text) { +fn_line void printer(var x, ctring attr_unused text) { if (mine(x)) { if (mine(*(var *) x)) { // handle array @@ -524,7 +533,7 @@ UNKNOWN:; puts_number((u8) x, false); puts_static(")>"); } -line void printer(car x, ctring unused text) { printer((var) x, text); } +fn_line void printer(car x, ctring attr_unused text) { printer((var) x, text); } #define SYS_read 0 @@ -548,6 +557,8 @@ void realloc() __attribute__((deprecated(MOONSHINE_LEGACY_LIBC_WARNING, "remap") void free() __attribute__((deprecated(MOONSHINE_LEGACY_LIBC_WARNING, "release"))); #endif +#define t(type) type ** + __attribute__((diagnose_as_builtin(__builtin_strcmp, 1, 2))) byte strcmp(ctring left, ctring right) { while (*left && (*left == *right) && left++ && right++); return (byte) (*left) - (byte) (*right); @@ -562,7 +573,9 @@ __attribute__((diagnose_as_builtin(__builtin_strncmp, 1, 2, 3))) byte strncmp(ct return (n == 0) ? 0 : ((byte) (*left) - (byte) (*right)); } -#define eq(a, b) (strcmp(a, b) == 0) +fn_line bool eq(ctring l, ctring r) { return strcmp(l, r) == 0; } +fn_line bool eq(t(char) l, t(char) r) { return strcmp(l[ 0 ], r[ 0 ]) == 0; } +fn_line bool eq(int l, int r) { return l == r; } u8 strnlen(ctring txt, u8 len) { u8 s = 0; @@ -616,14 +629,24 @@ __attribute__((diagnose_as_builtin(__builtin_memcpy, 1, 2, 3))) void memcpy(var #define bg_ansi(r, g, b) "\e[48;2;" #r ";" #g ";" #b "m" #define no_ansi() "\e[0m" -#define throw(...) \ - ({ \ - print(fg_ansi(255, 90, 90) "Error: ", __VA_ARGS__, no_ansi()); \ - puts_static(fg_ansi(235, 235, 50) "The following is an exception-related crash: " no_ansi()); \ - (void) raise(SIGILL); \ - __builtin_unreachable(); \ - 0; \ - }) +#ifdef __MOONSHINE_EXCEPTION_DEBUGGER + #define throw(...) \ + ({ \ + println(fg_ansi(255, 90, 90) "Error: ", __VA_ARGS__, no_ansi()); \ + puts_static(fg_ansi(235, 235, 50) "The following is an exception-related crash: " no_ansi()); \ + (void) raise(SIGILL); \ + __builtin_unreachable(); \ + 0; \ + }) +#else + #define throw(...) \ + ({ \ + println(fg_ansi(255, 90, 90) "Error: ", __VA_ARGS__, no_ansi()); \ + exit(1); \ + __builtin_unreachable(); \ + 0; \ + }) +#endif var __bare_mremap(const var ptr, const uint64_t old, const uint64_t new) [[clang::allocating]] { const var new_ptr = __bare_alloc(new); @@ -720,18 +743,11 @@ static int compare_locations(const void *a, const void *b) { return 0; } -struct FreeBlock find_free_space(struct Page *page) [[clang::nonallocating]] { +struct FreeBlock find_free_space(struct Page *page) { if (!page->dirty) return page->last_result; struct FreeBlock max_free = { 0, 0 }; - if (page == NULL) return max_free; - - uint64_t allocated_count = 0; - for (uint64_t i = 0; i < page->pointers.size; ++i) { - if (page->pointers.data[ i ].allocated) allocated_count++; - } - - if (allocated_count == 0) { + if (page == NULL || page->pointers.size == 0) { max_free.start = 0; max_free.size = page->size; page->dirty = false; @@ -739,45 +755,46 @@ struct FreeBlock find_free_space(struct Page *page) [[clang::nonallocating]] { return max_free; } - struct AllocatedPointer allocated_blocks[ allocated_count ]; - uint64_t idx = 0; - for (uint64_t i = 0; i < page->pointers.size; ++i) { - if (page->pointers.data[ i ].allocated) { allocated_blocks[ idx++ ] = page->pointers.data[ i ]; } - } + struct AllocatedPointer sorted_pointers[ sizeof(struct AllocatedPointer) * page->pointers.size ]; + for (u8 i = 0; i < page->pointers.size; i++) { sorted_pointers[ i ] = page->pointers.data[ i ]; } - qsort(allocated_blocks, allocated_count, sizeof(struct AllocatedPointer), compare_locations); + qsort(sorted_pointers, page->pointers.size, sizeof(struct AllocatedPointer), compare_locations); - uint64_t prev_end = 0; - max_free.size = 0; + u8 prev_end = 0; + for (u8 i = 0; i < page->pointers.size; i++) { + struct AllocatedPointer *block = &sorted_pointers[ i ]; + if (!block->allocated) continue; - for (uint64_t i = 0; i < allocated_count; ++i) { - struct AllocatedPointer *block = &allocated_blocks[ i ]; - uint64_t block_end = block->location + block->size; - uint64_t current_end = block_end > page->size ? page->size : block_end; + u8 block_start = block->location; + u8 block_end = block_start + block->size; - if (block->location > prev_end) { - uint64_t gap_size = block->location - prev_end; + if (block_start > prev_end) { + u8 gap_size = block_start - prev_end; if (gap_size > max_free.size) { max_free.start = prev_end; max_free.size = gap_size; } } - - if (current_end > prev_end) { prev_end = current_end; } + if (block_end > prev_end) { prev_end = block_end; } } if (prev_end < page->size) { - uint64_t gap_size = page->size - prev_end; + u8 gap_size = page->size - prev_end; if (gap_size > max_free.size) { max_free.start = prev_end; max_free.size = gap_size; } } - if (max_free.start % 16 != 0) { - const u8 change = align_value(max_free.start) - max_free.start; - max_free.start += change; - max_free.size -= change; + if (max_free.size > 0) { + u8 aligned_start = (max_free.start + 15) & ~15ULL; + u8 adjustment = aligned_start - max_free.start; + if (adjustment < max_free.size) { + max_free.start = aligned_start; + max_free.size -= adjustment; + } else { + max_free.size = 0; // No space after alignment + } } page->dirty = false; @@ -916,7 +933,7 @@ struct FoundPointer find_pointer(const var addr) { } } - if (!best_ptr->allocated) throw("Unallocated pointer? "); + if (!best_ptr->allocated) throw("Unallocated pointer? ", addr); if (best_ptr == NULL) throw("Pointer for location does not exist in page"); return (struct FoundPointer) { @@ -949,7 +966,6 @@ __attribute__((diagnose_as_builtin(__builtin_realloc, 1, 2))) var remap(const va return new_ptr; } -#define t(type) type ** #define de(obj) (*(obj)) const var *__new_array(const string type_name, const u4 type_size, const u4 count) [[clang::allocating]] { @@ -1043,7 +1059,8 @@ void unsafe_push(var *array, const var ptr, const u4 ptr_size) [[clang::allocati #define count(array) ((u4) cast_index(cast_ptr(cast_ptr(cast_ptr(*array, byte, -addon_size), magic_type, 1), string, 1), u4, 1)) #define element_size(array) \ (u4) cast_index(cast_ptr(cast_ptr(cast_ptr(*array, byte, -addon_size), magic_type, 1), string, 1), u4, 0) -#define last(array) ((array)[ 0 ][ count(array) ]) +#define last(array) ((array)[ 0 ][ count(array) ]) +#define first(array) get(array, 0) #define safe_push(type, array, ptr, ...) \ ({ \ type **_array = array; \ @@ -1052,34 +1069,65 @@ void unsafe_push(var *array, const var ptr, const u4 ptr_size) [[clang::allocati }) #define push(array, ptr, ...) safe_push(typeof((array)[ 0 ][ 0 ]), array, ptr __VA_OPT__(, ) __VA_ARGS__) -var return_item(var **arr, u8 index) { +var return_item(var **arr, i8 index) { if (unlikely(index >= count(arr))) { throw("Requested index in array (", index, ") exceeds the size of the array! (", count(arr), ")"); } - if (unlikely(index < 0)) throw("Cannot access negative offset in array!"); + if (unlikely(index < 0)) throw("Cannot access negative offset ", index, " in array!"); - return &arr[ 0 ][ index * element_size(arr) ]; + return &((byte **) arr)[ 0 ][ index * element_size(arr) ]; } -void set_item(var **arr, u8 index, var value) { +var return_item_unbound(var **arr, i8 index) { return &((byte **) arr)[ 0 ][ index * element_size(arr) ]; } + +void set_item(var **arr, i8 index, var value) { if (unlikely(index >= count(arr))) { throw("Target index in array (", index, ") exceeds the size of the array! (", count(arr), ")"); } - if (unlikely(index < 0)) throw("Cannot write to negative offset in array!"); + if (unlikely(index < 0)) throw("Cannot write to negative offset ", index, " in array!"); - memcpy(&arr[ 0 ][ index * element_size(arr) ], value, element_size(arr)); + memcpy(&((byte **) arr)[ 0 ][ index * element_size(arr) ], value, element_size(arr)); } -#define address_item(__array, __index) (typeof(__array[0])) return_item((var **) __array, __index) -#define get(__array, __index) (*(typeof(__array[0])) return_item((var **) __array, __index)) -#define set(__array, __index, __value) ({ typeof(__array[0][0]) v = __value; set_item((var **) __array, __index, &v); }) +#define branchless(c, a, b) !!c * a + !!!c * b + +#define address_item(__array, __index) (typeof(__array[ 0 ])) return_item((var **) __array, (u8) __index) +#define get(__array, __index) (*(typeof(__array[ 0 ])) return_item((var **) __array, (u8) __index)) +#define get_unbound(__array, __index) (*(typeof(__array[ 0 ])) return_item_unbound((var **) __array, (u8) __index)) +#define set(__array, __index, __value) \ + ({ \ + typeof(__array[ 0 ][ 0 ]) v = __value; \ + set_item((var **) __array, __index, &v); \ + }) -#define in , -#define foreach(...) foreach_xp(foreach_inner, (__VA_ARGS__)) -#define foreach_xp(a, b) a b -#define foreach_inner(item, array) \ - scope(cat(item, _index), (var) 0) for (auto item = get(array, (u8) 0); (u8) cat(item, _index) < count(array); \ - item = get(array, (u8) ++cat(item, _index))) +#define in , +#define foreach(...) foreach_inner(__VA_ARGS__) +#define foreach_inner(item, array) foreach_inner_2(item, cat(item, _index), array) +#define foreach_inner_2(item, index, array) \ + scope( \ + index, (var) 0) for (auto attr_unused item = get_unbound(array, (u8) 0); (u8) index < count(array); \ + item = get_unbound( \ + array, (u8) index == count(array) - 1 ? count(array) - 1 + 0 * (u8) ++index : (u8) ++index)) + +#define map(tuple, ...) exp(map__inner, expand tuple, __VA_ARGS__) +#define map__inner(out_type, array, item, ...) \ + ({ \ + auto __original_array = array; \ + t(out_type) __result_array = new (out_type, count(array)); \ + foreach (item in __original_array) { \ + out_type result = __VA_ARGS__; \ + set(__result_array, (u8) cat(item, _index), result); \ + } \ + __result_array; \ + }) +#define reduce(array, tuple, ...) exp(reduce__inner, array, expand tuple, __VA_ARGS__) +#define reduce__inner(array, initial, item, ...) \ + ({ \ + auto __original_array = array; \ + auto output = initial; \ + foreach (item in __original_array) { output = __VA_ARGS__; }; \ + output; \ + }) #define LIBC_WARNINGS_TEXT(name) \ "[[>>> The " name \ @@ -1105,14 +1153,14 @@ t(char) strdup(ctring str) { } var **__reverse_array(var **array) { - const u4 element_size = element_size(array); - const u4 count_val = count(array); + const u8 element_size = element_size(array); + const u8 count_val = count(array); if (count_val <= 1) return array; byte temp[ element_size ]; - for (u4 i = 0; i < count_val / 2; i++) { - u4 left_idx = i; - u4 right_idx = count_val - 1 - i; + for (u8 i = 0; i < count_val / 2; i++) { + u8 left_idx = i; + u8 right_idx = count_val - 1 - i; memcpy(temp, address_item(array, left_idx), element_size); memcpy(address_item(array, left_idx), address_item(array, right_idx), element_size); @@ -1122,7 +1170,7 @@ var **__reverse_array(var **array) { return array; } -#define reverse_array(...) (typeof(__VA_ARGS__)) __reverse_array((var *) __VA_ARGS__) +#define reverse_array(...) (typeof(__VA_ARGS__)) __reverse_array((var **) __VA_ARGS__) t(char) strndup(ctring str, u8 len) { const auto obj = new (char, len + 1); @@ -1138,18 +1186,15 @@ typedef struct linkednode linkednode; // A typical node in a linked list. struct linkednode { - bool init; linkednode *back[ 2 ]; // Double-index back-refernece for the node linkednode *front[ 2 ]; // Double-index forward-feference for the node var data; // The data for the linked list node }; typedef struct linkedlist { - u8 size; // The size of a linked list - linkednode *head; // The head pointer for the linked list - linkednode *tail; // The tail pointer for the linked list - u8 pool_size; // The size of the last memory pool. - t(t(linkednode)) pools; // Memory pool. + u8 size; // The size of a linked list + linkednode *head; // The head pointer for the linked list + linkednode *tail; // The tail pointer for the linked list } linkedlist; // Create an empty linked list. @@ -1159,35 +1204,13 @@ flatten linkedlist *create_linkedlist() { list->head = NULL; list->tail = NULL; - list->pool_size = 1024; - list->pools = new (t(linkednode)); - push(list->pools, new (linkednode, list->pool_size)); - return list; } // Push a value to the end of a linked list. -void push_linkedlist(linkedlist *list, var value) { - // Get object reference from memory pool. +linkednode *push_linkedlist(linkedlist *list, var value) { linkednode *node = obj(linkednode); - // foreach (pool in list->pools) { - // if (!pool) continue; - // foreach (candid in pool) { - // if (candid.init) continue; - // node = &pool[ 0 ][ (u8) candid_index ]; - // break; - // } - // } - - // if (node == NULL) { - // t(linkednode) new_pool = new (linkednode, list->pool_size *= 2); - - // node = &last(new_pool); - // push(list->pools, new_pool); - // } - - node->init = true; node->data = value; auto follower = list->tail; @@ -1204,6 +1227,32 @@ void push_linkedlist(linkedlist *list, var value) { list->tail = node; if (!list->head) list->head = node; + + return node; +} + +// Push a value to the front of a linked list. +linkednode *push_front_linkedlist(linkedlist *list, var value) { + linkednode *node = obj(linkednode); + + node->data = value; + + auto next = list->head; + auto double_next = list->head == NULL ? NULL : list->head->front[ 0 ]; + + node->front[ 0 ] = next; + node->front[ 1 ] = double_next; + node->back[ 0 ] = node->back[ 1 ] = NULL; + + if (next) { + next->back[ 0 ] = node; + if (double_next) double_next->back[ 1 ] = node; + } + + list->head = node; + if (!list->tail) list->tail = node; + + return node; } linkednode *index_to_ptr(linkedlist *list, u8 index) { @@ -1259,7 +1308,7 @@ linkednode *index_to_ptr(linkedlist *list, u8 index) { // This function will return a pointer to the linkednode, if free = false, and a pointer to the data contained inside, if free = // true. -overload var pop_item(linkedlist *list, bool free, linkednode *item) { +fn_overload var pop_item(linkedlist *list, bool free, linkednode *item) { if (item == NULL) return NULL; if (list->tail == item) list->tail = item->back[ 0 ]; @@ -1282,7 +1331,6 @@ overload var pop_item(linkedlist *list, bool free, linkednode *item) { auto ptr = item->data; if (free) { - item->init = false; return ptr; } else { return item; @@ -1291,10 +1339,10 @@ overload var pop_item(linkedlist *list, bool free, linkednode *item) { // This function will return a pointer to the linkednode, if free = false, and a pointer to the data contained inside, if free = // true. -line var pop_item(linkedlist *list, bool free, u8 index) { return pop_item(list, free, index_to_ptr(list, index)); } +fn_line var pop_item(linkedlist *list, bool free, u8 index) { return pop_item(list, free, index_to_ptr(list, index)); } // This function removes a node from the linked list, and then places it at the start of the list. -overload void front_insert(linkedlist *list, linkednode *node) { +fn_overload void front_insert(linkedlist *list, linkednode *node) { pop_item(list, false, node); if (list->head) { node->front[ 0 ] = list->head; @@ -1307,7 +1355,35 @@ overload void front_insert(linkedlist *list, linkednode *node) { } // This function removes a node from the linked list, and then places it at the start of the list. -line void front_insert(linkedlist *list, u8 index) { return front_insert(list, index_to_ptr(list, index)); } +fn_line void front_insert(linkedlist *list, u8 index) { return front_insert(list, index_to_ptr(list, index)); } + +linkedlist *clone_linkedlist(linkedlist *original) { + if (original == NULL) { return NULL; } + + linkedlist *new_list = create_linkedlist(); + new_list->size = original->size; + + linkednode *current = original->head; + while (current != NULL) { + push_linkedlist(new_list, current->data); + current = current->front[ 0 ]; + } + + return new_list; +} + +void free_linkedlist(linkedlist *list) { + if (list == NULL) return; + + linkednode *current = list->head; + while (current != NULL) { + linkednode *next = current->front[ 0 ]; + release(current); + current = next; + } + + release(list); +} typedef u8 (*hash_function)(ctring); @@ -1384,261 +1460,159 @@ u8 table_hash_3(ctring data) { return h1; } -typedef struct hashnode { - u8 hash; - ctring key; - car value; -} hashnode; +#define LOAD_FACTOR_THRESHOLD 0.7 -typedef struct hashtable { +typedef enum entry_state { EMPTY, OCCUPIED, TOMBSTONE } entry_state; + +typedef struct hashentry { + entry_state state; + ctring key; + car value; +} hashentry; + +typedef struct hasharray { hash_function proto; - bool use_hash; u8 size; - int8_t current_recent_access; - struct hashtable_optimizations { - bool only_recent_collision_checks; // Fast-ish option? Only checks the recent access table for collisions. - bool no_collision_checks; // Fastest option. Disables collision checking altogether. - bool run_ptr_check; // Faster option. Checks hash equivalency and pointer equivalency. Reduces rate of collisions if - // the string pointers used for fetching entries remain persistent. Setting this option to true - // will disable collision checks. - byte collision_character_check_count; // Fast option. Check the first N characters of the inputs together, alongside the - // hash. Setting this option to a non-zero value will disable collision checks. - bool no_hash; // Slowest option. Always use strcmp to find entries. Does not bother hashing values or checking for - // collisions. - } optimizations; - struct recent_access { - u8 hash; - ctring key; - car value; - } recent_access_nodes[ 16 ]; // Recently accessed table entries. - linkedlist *entries; // Linked list of hashnode structs. -} hashtable; - -// TODO: Add a rehash function that allows the user to change the hash function, recompute all the hashes and detect collisions. + u8 capacity; + hashentry *entries; +} hasharray; + +hasharray *create_hasharray(hash_function proto) { + hasharray *ha = obj(hasharray); + ha->proto = proto; + ha->size = 0; + ha->capacity = 16; + ha->entries = (hashentry *) alloc(sizeof(hashentry) * ha->capacity); + for (u8 i = 0; i < ha->capacity; i++) { + ha->entries[ i ].state = EMPTY; + ha->entries[ i ].key = NULL; + ha->entries[ i ].value = NULL; + } + return ha; +} -// -hashtable *create_table(hash_function proto) { - hashtable node = { .use_hash = true, - .size = 0, - .proto = proto, - .entries = create_linkedlist(), - .current_recent_access = -1, - .recent_access_nodes = { [0] = { 0, 0, 0 }, [15] = { 0, 0, 0 } }, - .optimizations = { // Default optimization options. Check for collisions. - .only_recent_collision_checks = false, - .no_hash = false, - .run_ptr_check = false, - .collision_character_check_count = 0, - .no_collision_checks = false } }; - hashtable *node_ref = obj(hashtable); - *node_ref = node; - - return node_ref; -} - -overload hashtable *create_table(hash_function proto, struct hashtable_optimizations optimizations) { - auto table = create_table(proto); - table->optimizations = optimizations; - return table; -} - -flatten void add_recent_access(hashtable *table, hashnode node) { - auto ref = &table->recent_access_nodes[ table->current_recent_access = (table->current_recent_access + 1) % 16 ]; - if (!table->optimizations.no_hash) ref->hash = node.hash; - ref->key = node.key; - ref->value = node.value; -} - -// TODO: Improve performance - -// Sets a value in the hashtable. -void set_hashtable(hashtable *table, ctring key, car value) { - hashnode *node = obj(hashnode); - node->hash = table->proto(key); - node->key = key; - node->value = value; - - // skip collision detection if optimizations are enabled - if (table->optimizations.no_hash || table->optimizations.no_collision_checks - || table->optimizations.collision_character_check_count > 0) - goto FINISH; - - // maybe there's a better option than checking for collisions all the time? - - table->use_hash = true; - - if (table->optimizations.no_collision_checks) goto FINISH; - - // check for collisions in the recent access - for (u8 i = 0; i < 16; i++) { - if (table->recent_access_nodes[ i ].hash == 0 && table->recent_access_nodes[ i ].key == NULL) continue; - if (table->recent_access_nodes[ i ].hash != node->hash) continue; - // collision detected, disable usage of hashes - table->use_hash = false; - goto FINISH; +void resize_hasharray(hasharray *ha) { + u8 new_capacity = ha->capacity * 2; + hashentry *new_entries = (hashentry *) alloc(sizeof(hashentry) * new_capacity); + for (u8 i = 0; i < new_capacity; i++) { + new_entries[ i ].state = EMPTY; + new_entries[ i ].key = NULL; + new_entries[ i ].value = NULL; } - if (table->optimizations.only_recent_collision_checks) goto FINISH; - - // check for collisions in the hash table, maybe slow? - // improve the speed on this!! - auto c_head = table->entries->head; - auto c_tail = table->entries->tail; - for (; c_head != NULL || c_tail != NULL;) { - if (c_head) { - auto head = (hashnode *) c_head->data; - if (head->hash == node->hash) { // collision detected on head. - table->use_hash = false; - goto FINISH; - } + for (u8 i = 0; i < ha->capacity; i++) { + if (ha->entries[ i ].state == OCCUPIED) { + ctring key = ha->entries[ i ].key; + car value = ha->entries[ i ].value; + u8 hash = ha->proto(key); + u8 index = hash % new_capacity; + while (new_entries[ index ].state == OCCUPIED) { index = (index + 1) % new_capacity; } + new_entries[ index ].state = OCCUPIED; + new_entries[ index ].key = key; + new_entries[ index ].value = value; } + } - if (c_tail) { - auto tail = (hashnode *) c_tail->data; - if (tail->hash == node->hash) { // collision detected on tail. - table->use_hash = false; - goto FINISH; - } + release(ha->entries); + ha->entries = new_entries; + ha->capacity = new_capacity; +} + +void set_hasharray(hasharray *ha, ctring key, car value) { + if (key == NULL) throw("Cannot insert NULL key into hasharray"); + if (ha->size >= (u8) (ha->capacity * LOAD_FACTOR_THRESHOLD)) { resize_hasharray(ha); } + + u8 hash = ha->proto(key); + u8 index = hash % ha->capacity; + u8 original_index = index; + u8 first_tombstone = -1; + + while (true) { + hashentry *entry = &ha->entries[ index ]; + if (entry->state == EMPTY) { + u8 insert_index = (first_tombstone != (u8) -1) ? first_tombstone : index; + hashentry *insert_entry = &ha->entries[ insert_index ]; + insert_entry->state = OCCUPIED; + insert_entry->key = key; + insert_entry->value = value; + ha->size++; + return; + } else if (entry->state == OCCUPIED && eq(entry->key, key)) { + entry->value = value; + return; + } else if (entry->state == TOMBSTONE && first_tombstone == (u8) -1) { + first_tombstone = index; } - - if (c_head) c_head = c_head->front[ 0 ]; - if (c_tail) c_tail = c_tail->back[ 0 ]; + index = (index + 1) % ha->capacity; + if (index == original_index) { throw("Hasharray is full!"); } } - -FINISH: - push_linkedlist(table->entries, node); - // add_recent_access(table, *node); } -overload car get_hashtable(hashtable *table, u8 hash, ctring key); - -// Gets a value from the hashtable using just a key. This approach is not very performant if hashing has been disabled. -overload car get_hashtable(hashtable *table, ctring key) { - if (table->use_hash && !table->optimizations.no_hash) return get_hashtable(table, table->proto(key), key); +car get_hasharray(hasharray *ha, ctring key) { + if (key == NULL) { throw("Cannot retrieve NULL key from hasharray"); } + u8 hash = ha->proto(key); + u8 index = hash % ha->capacity; + u8 original_index = index; - for (byte i = 0; i < 16; i++) { - if (table->recent_access_nodes[ i ].hash == 0 && table->recent_access_nodes[ i ].key == NULL) continue; - if (table->recent_access_nodes[ i ].key == key) return table->recent_access_nodes[ i ].value; - if (eq(table->recent_access_nodes[ i ].key, key)) return table->recent_access_nodes[ i ].value; + while (true) { + hashentry *entry = &ha->entries[ index ]; + if (entry->state == EMPTY) { + return NULL; + } else if (entry->state == OCCUPIED && eq(entry->key, key)) { + return entry->value; + } + index = (index + 1) % ha->capacity; + if (index == original_index) return NULL; } +} - auto c_head = table->entries->head; - auto c_tail = table->entries->tail; - - for (; c_head != NULL || c_tail != NULL;) { - if (c_head) { - hashnode *head = c_head->data; - if (head->key != key) goto LAST; - if (!eq(head->key, key)) goto LAST; - add_recent_access(table, *(hashnode *) head); - return head->value; - } +void delete_hasharray(hasharray *ha, ctring key) { + if (key == NULL) { throw("Cannot delete NULL key from hasharray"); } + u8 hash = ha->proto(key); + u8 index = hash % ha->capacity; + u8 original_index = index; - if (c_tail) { - hashnode *tail = c_tail->data; - if (tail->key != key) goto LAST; - if (!eq(tail->key, key)) goto LAST; - add_recent_access(table, *(hashnode *) tail); - return tail->value; + while (true) { + hashentry *entry = &ha->entries[ index ]; + if (entry->state == EMPTY) return; + else if (entry->state == OCCUPIED && eq(entry->key, key)) { + entry->state = TOMBSTONE; + ha->size--; + return; } - - LAST: - - if (c_head) c_head = c_head->front[ 0 ]; - if (c_tail) c_tail = c_tail->back[ 0 ]; - } - - return NULL; -} - -// Gets a value from the hashtable using a key and a hash. The key is not typically used unless optimization checks are enabled. -overload car get_hashtable(hashtable *table, u8 hash, ctring key) { - if (!table->use_hash || table->optimizations.no_hash) return get_hashtable(table, key); - - bool matched = false; - linkednode *best_candidate = NULL; - - for (byte i = 0; i < 16; i++) { - auto node = table->recent_access_nodes[ i ]; - if (node.hash == 0 && node.key == NULL) continue; - if (node.hash != hash) continue; - // Hash matches. - if (table->optimizations.run_ptr_check && node.key == key) return node.value; - // Check key characters. - if (table->optimizations.collision_character_check_count - && strncmp(node.key, key, table->optimizations.collision_character_check_count) == 0) - return node.value; - // No hash matches. Set best candidate. - matched = true; - best_candidate = (var) node.value; + index = (index + 1) % ha->capacity; + if (index == original_index) return; } +} - // Best candidate here acts as a holder for the value, not an actual linkednode. - if (matched) return best_candidate; - - // Use hash - auto c_head = table->entries->head; - auto c_tail = table->entries->tail; - - for (; c_head != NULL || c_tail != NULL;) { - // Bug: Investigate why this happens. - if (likely(c_head) && unlikely(c_head == c_head->front[ 0 ])) c_head = NULL; - if (likely(c_tail) && unlikely(c_tail == c_tail->back[ 0 ])) c_tail = NULL; - - if (c_head) { - hashnode *head = c_head->data; - if (!head) goto CONT1; - if (head->hash == hash) { // Check optimization flags. - // Hash matches and the pointer check succeeded. Return the candidate immediately. - if (table->optimizations.run_ptr_check && head->key == key) { - add_recent_access(table, *(hashnode *) head); - return head->value; - } // Check key characters. - if (table->optimizations.collision_character_check_count - && strncmp(head->key, key, table->optimizations.collision_character_check_count) == 0) { - add_recent_access(table, *(hashnode *) head); - return head->value; - } - // Hash matches? If so, set it as the best candidate. - best_candidate = c_head; - goto CONT1; - } - } +void free_hasharray(hasharray *ha) { + release(ha->entries); + release(ha); +} - CONT1: +hasharray *clone_hasharray(hasharray *original) { + if (original == NULL) { return NULL; } - if (c_tail) { - hashnode *tail = c_tail->data; - if (!tail) goto CONT2; - if (tail->hash == hash) { // Check optimization flags. - // Hash matches and the pointer check succeeded. Return the candidate immediately. - if (table->optimizations.run_ptr_check && tail->key == key) { - add_recent_access(table, *(hashnode *) tail); - return tail->value; - } - // Check key characters. - if (table->optimizations.collision_character_check_count - && strncmp(tail->key, key, table->optimizations.collision_character_check_count) == 0) { - add_recent_access(table, *(hashnode *) tail); - return tail->value; - } - // Hash matches? If so, set it as the best candidate. - best_candidate = c_tail; - goto CONT2; - } - } + hasharray *clone = obj(hasharray); + if (clone == NULL) { throw("Failed to allocate memory for cloned hasharray"); } - CONT2: + clone->proto = original->proto; + clone->size = original->size; + clone->capacity = original->capacity; - if (c_head) c_head = c_head->front[ 0 ]; - if (c_tail) c_tail = c_tail->back[ 0 ]; + clone->entries = (hashentry *) alloc(sizeof(hashentry) * clone->capacity); + if (clone->entries == NULL) { + release(clone); + throw("Failed to allocate memory for cloned hasharray entries"); } - if (best_candidate) front_insert(table->entries, best_candidate); - else { return NULL; } - add_recent_access(table, *(hashnode *) best_candidate->data); + for (u8 i = 0; i < original->capacity; i++) { + clone->entries[ i ].state = original->entries[ i ].state; + clone->entries[ i ].key = original->entries[ i ].key; + clone->entries[ i ].value = original->entries[ i ].value; + } - return ((hashnode *) best_candidate->data)->value; + return clone; } string *environ; diff --git a/moonshine.m4 b/moonshine.m4 index 16f6253..5eb2615 100644 --- a/moonshine.m4 +++ b/moonshine.m4 @@ -37,8 +37,8 @@ dnl dnl dnl dnl Normally, I only need two of these to work. But if you want to nest more, activate the rest! Make sure to run `make m4` when you change this file. -define_expander([512], general) -define_expander([512], general2) +define_expander([1024], general) +define_expander([1024], general2) dnl Activate these if needed. dnl define_expander([512], general3) dnl define_expander([512], general4) |