Expand bootstrap common library with generic Array and more String utility functions

Signed-off-by: Mel <mel@rnrd.eu>

1 files changed, 291 insertions, 52 deletions

diff --git a/boot/common.c b/boot/common.c
index b8587bc..e453065 100644
--- a/boot/common.c
+++ b/boot/common.c
@@ -8,9 +8,6 @@
  * SPDX-License-Identifier: MPL-2.0
  */
 
-// TODO: merge our common library with `boot/runtime/core.c`
-// to avoid implementing a semi-standard library twice!
-
 #pragma once
 
 #include <math.h>
@@ -147,6 +144,146 @@ unreachable()
 // statically allocates a region of memory for a type.
 #define REGION(type, of) REGION_OF_SIZE(type, of, REGION_SIZE)
 
+// the global array data region.
+REGION(byte, array_data)
+
+// a simple fixed-size array type that uses static allocation.
+struct _Array
+{
+    uint element_size;
+    void* data;
+    uint length;
+    uint capacity;
+};
+
+#define Array(type) struct _Array
+
+// allocate memory from the static array region.
+void*
+array_allocate_static(size_t size)
+{
+    check(region_array_data_cursor + size <= ARRAY_SIZE(region_array_data), "out of array memory");
+    void* ptr = region_array_data + region_array_data_cursor;
+    region_array_data_cursor += size;
+    return ptr;
+}
+
+// creates a new, empty array with fixed capacity using static allocation.
+struct _Array
+_array_new(uint element_size, uint capacity)
+{
+    void* data = array_allocate_static(capacity * element_size);
+    struct _Array array = {
+        .element_size = element_size,
+        .data = data,
+        .length = 0,
+        .capacity = capacity,
+    };
+    return array;
+}
+
+#define array_new(type, capacity) _array_new(sizeof(type), capacity)
+
+// returns the number of elements in the array.
+uint
+array_length(const struct _Array* array)
+{
+    return array->length;
+}
+
+// returns the total capacity of the array.
+uint
+array_capacity(const struct _Array* array)
+{
+    return array->capacity;
+}
+
+// checks if the array is empty.
+bool
+array_is_empty(const struct _Array* array)
+{
+    return array->length == 0;
+}
+
+// internal use, prefer the array_push macro.
+void
+_array_push(struct _Array* array, const void* element)
+{
+    check(array->length < array->capacity, "array is full: %u/%u", array->length, array->capacity);
+    memcpy((ascii*)array->data + (array->length * array->element_size), element, array->element_size);
+    ++array->length;
+}
+
+#define array_push(array, element) _array_push(array, (const void*)(element))
+
+// internal use, prefer the array_at macro.
+void*
+_array_at(const struct _Array* array, uint index)
+{
+    check(index < array->length, "array index out of bounds: %u (length: %u)", index, array->length);
+    return (ascii*)array->data + (index * array->element_size);
+}
+
+#define array_at(type, array, index) ((type*)_array_at(array, index))
+
+// internal use, prefer the array_get macro.
+void
+_array_get(const struct _Array* array, uint index, void* out_element)
+{
+    check(index < array->length, "array index out of bounds: %u (length: %u)", index, array->length);
+    memcpy(out_element, (ascii*)array->data + (index * array->element_size), array->element_size);
+}
+
+#define array_get(array, index, out_element) _array_get(array, index, (void*)(out_element))
+
+// a slice is a view into a block of memory.
+struct _Slice
+{
+    uint element_size;
+    void* data;
+    uint length;
+};
+
+#define Slice(type) struct _Slice
+
+// creates a new slice from data.
+struct _Slice
+_slice_new(void* data, uint length, uint element_size)
+{
+    struct _Slice slice = {
+        .data = data,
+        .length = length,
+        .element_size = element_size
+    };
+    return slice;
+}
+
+#define slice_new(data, length) _slice_new((void*)(data), (length), sizeof(*(data)))
+
+// returns the length of a slice.
+uint
+slice_length(const struct _Slice* slice)
+{
+    return slice->length;
+}
+
+// internal use, prefer the slice_at macro.
+void*
+_slice_at(const struct _Slice* slice, uint index)
+{
+    check(index < slice->length, "slice index out of bounds: %u (length: %u)", index, slice->length);
+    return (ascii*)slice->data + (index * slice->element_size);
+}
+
+#define slice_at(type, slice, index) ((type*)_slice_at(slice, index))
+
+// a macro for iterating over each element in an array.
+#define FOR_EACH_ARRAY(type, element_var, array_ptr, action) \
+    for (uint i = 0; i < array_length(array_ptr); ++i) { \
+        type element_var = *array_at(type, array_ptr, i); \
+        action; \
+    }
+
 // the global string region.
 REGION(ascii, string)
 
@@ -277,19 +414,137 @@ string_equals_c_str(const struct String a, const ascii* b)
     if (string_length(a) == 0) return true;
     return memcmp(a.data, b, a.length) == 0;
 }
-void
-string_print(struct String s)
+
+// returns a null-terminated C string representation.
+// the string is already null-terminated in our implementation,
+// thus no copy is required.
+const ascii*
+string_c_str(struct String s)
 {
-    printf("%.*s", (int32)s.length, s.data);
+    return s.data;
+}
+
+// creates a new string with a character appended to
+// the end of the given string.
+struct String
+string_push(struct String s, ascii c)
+{
+    check(region_string_cursor + s.length + 2 < REGION_SIZE, "out of string memory for push");
+
+    ascii* at = region_string + region_string_cursor;
+    region_string_cursor += s.length + 2;
+
+    for (uint i = 0; i < s.length; ++i) at[i] = s.data[i];
+    at[s.length] = c;
+    at[s.length + 1] = '\0';
+
+    return (struct String){
+        .data = at,
+        .length = s.length + 1,
+    };
+}
+
+// creates a new string with the last character of
+// the given string removed.
+// pass a non-nil pointer as `removed_char` to retrieve
+// the removed character.
+struct String
+string_pop(struct String s, ascii* removed_char)
+{
+    check(s.length > 0, "cannot pop from an empty string");
+
+    if (removed_char) *removed_char = s.data[s.length - 1];
+
+    return (struct String){
+        .data = s.data,
+        .length = s.length - 1,
+    };
 }
 
+// creates a new string consisting of string `a` followed by string `b`.
+struct String
+string_append(struct String a, struct String b)
+{
+    if (string_is_empty(b)) return a;
+
+    uint new_length = a.length + b.length;
+    check(region_string_cursor + new_length + 1 < REGION_SIZE, "out of string memory for append");
+
+    ascii* at = region_string + region_string_cursor;
+    region_string_cursor += new_length + 1;
+
+    for (uint i = 0; i < a.length; ++i) at[i] = a.data[i];
+    for (uint i = 0; i < b.length; ++i) at[a.length + i] = b.data[i];
+    at[new_length] = '\0';
+
+    return (struct String){
+        .data = at,
+        .length = new_length,
+    };
+}
+
+// creates a new string consisting of string `a` followed
+// by the contents of the c-style string buffer `b`.
+struct String
+string_append_c_str(struct String a, const ascii* b)
+{
+    uint c_str_len = strlen(b);
+    if (c_str_len == 0) return a;
+
+    uint new_length = a.length + c_str_len;
+    check(region_string_cursor + new_length + 1 < REGION_SIZE, "out of string memory for append_c_str");
+
+    ascii* at = region_string + region_string_cursor;
+    region_string_cursor += new_length + 1;
+
+    for (uint i = 0; i < a.length; ++i) at[i] = a.data[i];
+    for (uint i = 0; i < c_str_len; ++i) at[a.length + i] = b[i];
+    at[new_length] = '\0';
+
+    return (struct String){
+        .data = at,
+        .length = new_length,
+    };
+}
+
+// creates a copy of a string.
+struct String
+string_clone(struct String s)
+{
+    return string_new(s.data, s.length);
+}
+
+// creates a new string consisting of a slice of the original string.
+// the slice range is defined by `[start, end)`.
+// if `start == end`, returns an empty string.
+struct String
+string_slice(struct String s, uint start, uint end)
+{
+    check(start <= end && end <= s.length, "invalid slice range [%u, %u) for string of length %u", start, end, s.length);
+
+    if (start == end) return string_empty();
+
+    uint slice_len = end - start;
+    return string_new(s.data + start, slice_len);
+}
+
+// creates a new string with the contents of string `s`,
+// with the character at index `index` modified to `c`.
+struct String
+string_set(struct String s, uint index, ascii c)
+{
+    check(index < s.length, "index out of bounds: %u (length: %u)", index, s.length);
+
+    struct String new_s = string_clone(s);
+    new_s.data[index] = c;  // safe because we just allocated this
+    return new_s;
+}
+
+// prints the contents of string `s` to stdout.
 void
-string_format(struct String s, const ascii* format, ...)
+string_print(struct String s)
 {
-    va_list args;
-    va_start(args, format);
-    vprintf(format, args);
-    va_end(args);
+    printf("%.*s", (int32)s.length, s.data);
 }
 
 enum String_Concat_Arg
@@ -301,6 +556,10 @@ enum String_Concat_Arg
 
 #define MAX_STRING_CONCAT_LENGTH 2048
 
+// concatenates multiple strings and ascii buffers into a single string.
+// each new argument is prepended by a `String_Concat_Arg` value,
+// either `ARG_STRING` or `ARG_ASCII`, followed by the argument itself.
+// the final argument must be `ARG_END`.
 struct String
 string_concatenate(enum String_Concat_Arg type1, ...)
 {
@@ -364,6 +623,8 @@ string_concatenate(enum String_Concat_Arg type1, ...)
     return string_new(buffer, total_length);
 }
 
+// creates a new string view from a substring of the given string `s`.
+// the view range is defined by `[start, end)`.
 struct String_View
 string_substring(struct String s, uint start, uint end)
 {
@@ -428,6 +689,25 @@ string_view_at(struct String_View view, uint index)
     return view.data[index];
 }
 
+// creates a new string view from a c-style string buffer.
+struct String_View
+string_view_from_c_str(const ascii* c_str)
+{
+    return (struct String_View){
+        .data = (ascii*)c_str,
+        .length = strlen(c_str),
+    };
+}
+
+// compares two string views for equality.
+bool
+string_view_equals(struct String_View a, struct String_View b)
+{
+    if (a.length != b.length) return false;
+    if (a.length == 0) return true;
+    return memcmp(a.data, b.data, a.length) == 0;
+}
+
 // prints a string view to stdout.
 void
 string_view_print(struct String_View view)
@@ -483,47 +763,6 @@ _internal_string_format(FILE* stream, uint string_length, const ascii* format, .
     va_end(args);
 }
 
-#define STRING_ARRAY_MAX 8
-
-// a string array, used for storing multiple strings.
-// if we ever need more strings, just bump `STRING_ARRAY_MAX` up.
-struct String_Array
-{
-    struct String strings[STRING_ARRAY_MAX];
-    uint count;
-};
-
-// initializes a string array with no strings.
-struct String_Array
-string_array_new(void)
-{
-    return (struct String_Array){
-        .strings = { 0 },
-        .count = 0,
-    };
-}
-
-// adds a string to the string array.
-bool
-string_array_add(struct String_Array* array, struct String string)
-{
-    if (array->count >= STRING_ARRAY_MAX) return false;
-
-    array->strings[array->count++] = string;
-    return true;
-}
-
-struct String
-string_array_at(const struct String_Array* array, uint index)
-{
-    check(index < array->count, "index out of bounds");
-    return array->strings[index];
-}
-
-#define STRING_ARRAY_FOR_EACH(cursor, str, array) \
-    struct String str = array.strings[0];         \
-    for (uint cursor = 0; cursor < array.count; str = array.strings[++cursor])
-
 // a source file given to the compiler.
 struct Source_File
 {