diff options
Diffstat (limited to 'libk')
-rw-r--r-- | libk/makefile | 5 | ||||
-rw-r--r-- | libk/stdlib.h | 2 | ||||
-rw-r--r-- | libk/stdlib/console.cc | 4 | ||||
-rw-r--r-- | libk/stdlib/quicksort.h | 31 | ||||
-rw-r--r-- | libk/stdlib/virtual.cc | 6 | ||||
-rw-r--r-- | libk/string.h | 8 | ||||
-rw-r--r-- | libk/string/memory.cc (renamed from libk/stdlib/memory.cc) | 7 | ||||
-rw-r--r-- | libk/string/string.cc | 26 | ||||
-rw-r--r-- | libk/test/quicksort.cc | 21 |
9 files changed, 54 insertions, 56 deletions
diff --git a/libk/makefile b/libk/makefile index 9063f72..f3b9aeb 100644 --- a/libk/makefile +++ b/libk/makefile @@ -1,5 +1,5 @@ -CXX_OBJ = string/string.o string/integerview.o \ - stdlib/abort.o stdlib/console.o stdlib/memory.o +CXX_OBJ = string/integerview.o string/memory.o \ + stdlib/abort.o stdlib/console.o stdlib/virtual.o CXX_OBJ := $(addprefix $(OBJ_DIR)/, $(CXX_OBJ)) CXX_DEP = $(CXX_OBJ:%.o=%.d) CXX_JSON = $(CXX_OBJ:.o=.json) @@ -30,6 +30,7 @@ $(TEST_CXX_OBJ): $(OBJ_DIR)/%.o : %.cc @$(TEST_CXX) -target $(TARGET) $(TEST_CXX_FLAGS) $(CXX_INCLUDE) -MMD -c $< -o $@ compile_commands.json: $(CXX_JSON) + @echo " GEN $@" @echo [ > $@ @cat $(CXX_JSON) >> $@ @echo ] >> $@ diff --git a/libk/stdlib.h b/libk/stdlib.h index fe8736d..6fab4c5 100644 --- a/libk/stdlib.h +++ b/libk/stdlib.h @@ -62,7 +62,7 @@ void printk(const T& a, const Args&... x) { } } -extern "C" __attribute__((__noreturn__)) void abort(); +extern "C" [[noreturn]] void abort(); #define runtime_assert(x, msg) \ if (!x) { \ diff --git a/libk/stdlib/console.cc b/libk/stdlib/console.cc index c076297..3054120 100644 --- a/libk/stdlib/console.cc +++ b/libk/stdlib/console.cc @@ -1,8 +1,8 @@ #include "stdlib.h" constexpr size_t max_consoles = 4; -static Console* global_console[max_consoles] = {nullptr}; -static size_t last_console = 0; +Console* global_console[max_consoles] = {nullptr}; +size_t last_console = 0; void Console::set(Console* ptr) { if (ptr != nullptr && last_console < max_consoles) { diff --git a/libk/stdlib/quicksort.h b/libk/stdlib/quicksort.h index 632a962..77b437b 100644 --- a/libk/stdlib/quicksort.h +++ b/libk/stdlib/quicksort.h @@ -2,6 +2,8 @@ #include <types.h> +enum struct SortOrder { Ascending, Descending }; + template <typename T> constexpr void swap(T& l, T& r) { const T t = r; @@ -24,7 +26,7 @@ constexpr void qsort_pivot(T a[], const size_t begin, const size_t end) { * Quicksort Lomuend partition scheme * The pivot is assumed end be the last position */ -template <typename T> +template <typename T, auto order = SortOrder::Ascending> constexpr auto qsort_partition(T a[], const size_t begin, const size_t end) { struct { size_t left; @@ -39,10 +41,17 @@ constexpr auto qsort_partition(T a[], const size_t begin, const size_t end) { // - place any value less than the pivot on the left // - place any value equal end the pivot on the right for (auto j = begin; j < p; ++j) { - if (a[j] < pivot) - swap(a[j], a[i++]); - else if (a[j] == pivot) - swap(a[j], a[--p]); + if constexpr (order == SortOrder::Ascending) { + if (a[j] < pivot) + swap(a[j], a[i++]); + else if (a[j] == pivot) + swap(a[j], a[--p]); + } else if constexpr (order == SortOrder::Descending) { + if (a[j] > pivot) + swap(a[j], a[i++]); + else if (a[j] == pivot) + swap(a[j], a[--p]); + } } // We now have all the values less than the pivot left of i, and all the pivots right of p @@ -57,7 +66,7 @@ constexpr auto qsort_partition(T a[], const size_t begin, const size_t end) { /** * Sort an array in place */ -template <typename T> +template <typename T, auto order = SortOrder::Ascending> constexpr void qsort(T a[], const size_t begin, const size_t end) { if (begin >= end) return; @@ -67,15 +76,15 @@ constexpr void qsort(T a[], const size_t begin, const size_t end) { // Reorder the array so that all elements less than the pivot are left of it, and all elements greater than the // pivot are end the right. Equal elements can go either way. After partitioning, the pivot is in its final // position. - const auto limit = qsort_partition(a, begin, end); + const auto limit = qsort_partition<T, order>(a, begin, end); // Recursively sort the left and right sub-arrays // Sort the shorter subarray first if ((limit.left - begin) < (end - limit.right)) { - qsort(a, begin, limit.left); - qsort(a, limit.right, end); + qsort<T, order>(a, begin, limit.left); + qsort<T, order>(a, limit.right, end); } else { - qsort(a, limit.right, end); - qsort(a, begin, limit.left); + qsort<T, order>(a, limit.right, end); + qsort<T, order>(a, begin, limit.left); } } diff --git a/libk/stdlib/virtual.cc b/libk/stdlib/virtual.cc new file mode 100644 index 0000000..880b22e --- /dev/null +++ b/libk/stdlib/virtual.cc @@ -0,0 +1,6 @@ +#include <stdlib.h> + +extern "C" void __cxa_pure_virtual() { // NOLINT + printk("__cxa_pure_virtual called, aborting...\n"); + abort(); +} diff --git a/libk/string.h b/libk/string.h index d0a0b32..7c0afb9 100644 --- a/libk/string.h +++ b/libk/string.h @@ -2,10 +2,10 @@ #include <types.h> extern "C" { -void* memcpy(void* dstptr, const void* srcptr, const size_t n); -void* memset(void* bufptr, const int value, const size_t n); -void* memmove(void* dstptr, const void* srcptr, const size_t n); -int memcmp(const void* aptr, const void* bptr, const size_t n); +void* memcpy(void* dstptr, const void* srcptr, size_t n); +void* memset(void* bufptr, int value, size_t n); +void* memmove(void* dstptr, const void* srcptr, size_t n); +int memcmp(const void* aptr, const void* bptr, size_t n); } /** diff --git a/libk/stdlib/memory.cc b/libk/string/memory.cc index b5c8f6d..5b8a1f8 100644 --- a/libk/stdlib/memory.cc +++ b/libk/string/memory.cc @@ -1,9 +1,4 @@ -#include <stdlib.h> - -extern "C" void __cxa_pure_virtual() { - printk("__cxa_pure_virtual\n"); - abort(); -} +#include <types.h> extern "C" void* memcpy(void* dstptr, const void* srcptr, const size_t n) { auto* dst = static_cast<uint8_t*>(dstptr); diff --git a/libk/string/string.cc b/libk/string/string.cc deleted file mode 100644 index c75feb1..0000000 --- a/libk/string/string.cc +++ /dev/null @@ -1,26 +0,0 @@ -#include "string.h" - -// TODO - -// int strcpy(char *dst, const char *stc); -// void strcat(void *dst, const void *src); -// char* strncpy(char *dest, const char *src, int length); -// int strncmp(const char *s1, const char *s2, int c); - -/* strcmp - compare two C-strings */ -constexpr int strcmp(const char* s1, const char* s2) { - const auto s1_len = strlen(s1); - for (size_t i = 0; i < s1_len; ++i) { - if (s1[i] == s2[i]) - continue; - if (s1[i] > s2[i]) - return 1; - if (s1[i] < s2[i]) - return -1; - } - return 0; -} - -static_assert(strcmp("one", "one") == 0); -static_assert(strcmp("one", "two") < 0); -static_assert(strcmp("foo", "bar") > 0); diff --git a/libk/test/quicksort.cc b/libk/test/quicksort.cc index 582e49e..7a25c08 100644 --- a/libk/test/quicksort.cc +++ b/libk/test/quicksort.cc @@ -1,9 +1,14 @@ #include <stdlib/quicksort.h> -constexpr bool is_sorted(int a[], size_t from, size_t to) { +constexpr bool is_sorted_asc(int a[], size_t from, size_t to) { for (; from < to - 1; ++from) - if (a[from] > a[from + 1]) - return false; + if (a[from] > a[from + 1]) return false; + return true; +} + +constexpr bool is_sorted_desc(int a[], size_t from, size_t to) { + for (; from < to - 1; ++from) + if (a[from] < a[from + 1]) return false; return true; } @@ -12,5 +17,13 @@ static_assert([]() { const size_t a_len = sizeof(a) / sizeof(int); qsort(a, 0, a_len - 1); - return is_sorted(a, 0, a_len - 1); + return is_sorted_asc(a, 0, a_len - 1); +}()); + +static_assert([]() { + int a[] = {12, 82, 347, 92, 74, 123, 0, 56}; + const size_t a_len = sizeof(a) / sizeof(int); + + qsort<int, SortOrder::Descending>(a, 0, a_len - 1); + return is_sorted_desc(a, 0, a_len - 1); }()); |