From 2dab66694bb72ee222a44c49c669e9f5adc024f0 Mon Sep 17 00:00:00 2001 From: Mitya Selivanov Date: Thu, 29 Feb 2024 00:51:42 +0100 Subject: Load audio file with miniaudio instead of dr_libs; Fix null dereference when loading empty sampler --- source/kit/astar.h | 401 ++++++++++++++++++++++++++++++++++++++++++++ source/kit/file.c | 8 +- source/kit/input_buffer.c | 6 +- source/kit/shared_mutex.h | 4 +- source/kit/status.h | 2 +- source/kit/string_builder.h | 4 +- source/kit/test.h | 4 +- source/kit/xml.c | 19 ++- 8 files changed, 427 insertions(+), 21 deletions(-) create mode 100644 source/kit/astar.h (limited to 'source/kit') diff --git a/source/kit/astar.h b/source/kit/astar.h new file mode 100644 index 0000000..b4a5909 --- /dev/null +++ b/source/kit/astar.h @@ -0,0 +1,401 @@ +// ================================================================ +// +// A* graph search algorithm +// +// ================================================================ + +// TODO +// - Nearest: save the nearest node when the search is failed or not +// yet finished. +// - Sight: when two nodes are in direct sight of each other, skip +// nodes between them (Theta*). + +#ifndef KIT_ASTAR_INL_H +#define KIT_ASTAR_INL_H + +#include "types.h" +#include "status.h" + +#include +#include +#include + +#ifdef __cplusplus +extern "C" { +#endif + +enum { + ASTAR_PROGRESS = 0, + ASTAR_SUCCESS, + ASTAR_FAIL, + ASTAR_OUT_OF_MEMORY, + ASTAR_INVALID_ARGUMENT, +}; + +typedef struct { + b8 stop; + b8 skip; + i64 neighbor; + i64 distance; +} astar_link_t; + +typedef struct { + i64 id; + i64 previous; + i64 exact_source_to_node; + i64 estimated_source_to_destination; +} astar_node_t; + +typedef struct { + i64 capacity; + i64 size; + astar_node_t *values; +} astar_set_t; + +typedef struct { + astar_set_t open; + astar_set_t closed; + void *user_data; + i64 source; + i64 destination; +} astar_state_t; + +#ifdef __GNUC__ +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wunused-function" +# pragma GCC diagnostic ignored "-Wunknown-pragmas" +# pragma GCC push_options +# pragma GCC optimize("O3") +#endif + +static s32 astar_init(astar_state_t *state, astar_set_t open, + astar_set_t closed, void *user_data, i64 source, + i64 destination) { + assert(state != NULL && open.capacity > 0 && open.values != NULL && + closed.capacity > 0 && closed.values != NULL); + + if (state == NULL) + return KIT_ERROR_INVALID_ARGUMENT; + + memset(state, 0, sizeof *state); + + state->source = source; + state->destination = destination; + state->open = open; + state->closed = closed; + state->user_data = user_data; + + if (state->open.capacity <= 0) + return KIT_ERROR_INVALID_ARGUMENT; + + state->open.values[0] = (astar_node_t) { + .id = source, + .previous = -1, + .exact_source_to_node = 0, + .estimated_source_to_destination = -1, + }; + + state->open.size = 1; + state->closed.size = 0; + + return KIT_OK; +} + +static s32 astar_path(astar_state_t *state, i64 *size, i64 *path) { + assert(state != NULL && size != NULL); + + if (state == NULL || size == NULL) + return KIT_ERROR_INVALID_ARGUMENT; + + i64 path_size = *size; + + *size = 1; + + i64 id = state->destination; + + while (id != state->source) { + if (*size > state->closed.size) + return KIT_ERROR_INTERNAL; + + i64 index = 0; + for (; index < state->closed.size; index++) + if (state->closed.values[index].id == id) + break; + if (index == state->closed.size) + return KIT_ERROR_INTERNAL; + + if (path != NULL && *size <= path_size) + path[*size - 1] = id; + + id = state->closed.values[index].previous; + ++*size; + } + + if (path != NULL && *size <= path_size) + path[*size - 1] = id; + + if (path != NULL) { + if (*size < path_size) + path_size = *size; + + for (i64 i = 0; i < path_size / 2; ++i) { + i64 z = path[i]; + path[i] = path[path_size - 1 - i]; + path[path_size - 1 - i] = z; + } + } + + return KIT_OK; +} + +#ifdef __GNUC__ +# pragma GCC pop_options +# pragma GCC diagnostic pop +#endif + +#ifdef __cplusplus +} +#endif + +#endif + +// ================================================================ +// +// Algorithm template +// +// ================================================================ + +#ifdef ASTAR_TEMPLATE + +#ifdef __cplusplus +extern "C" { +#endif + +#ifndef ASTAR_SUFFIX +# define ASTAR_SUFFIX +#endif + +#ifndef ASTAR_NEIGHBOR +# define ASTAR_NEIGHBOR(user_data_, node_, index_) \ + (astar_link_t) { \ + .stop = 1, \ + } +#endif + +#ifndef ASTAR_HEURISTIC +# define ASTAR_HEURISTIC(user_data_, node_0_, node_2_) (-1) +#endif + +#ifdef __GNUC__ +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wunused-function" +# pragma GCC diagnostic ignored "-Wunknown-pragmas" +# pragma GCC push_options +# pragma GCC optimize("O3") +#endif + +#define CAT1_(x, y) x##y +#define CAT2_(x, y) CAT1_(x, y) +#define NAME_(x) CAT2_(x, ASTAR_SUFFIX) + +static s32 NAME_(astar_iteration)(astar_state_t *state) { + assert(state != NULL); + + if (state == NULL) + return ASTAR_INVALID_ARGUMENT; + + if (state->open.size == 0) + return ASTAR_FAIL; + + if (state->open.values == NULL || state->closed.values == NULL) + return ASTAR_OUT_OF_MEMORY; + + // Find a node in the open set that is closest to the destination + // + astar_node_t nearest_node; + { + i64 index_in_open = 0; + for (i64 i = 1; i < state->open.size; i++) + if (state->open.values[i].estimated_source_to_destination < + state->open.values[index_in_open] + .estimated_source_to_destination) + index_in_open = i; + nearest_node = state->open.values[index_in_open]; + if (index_in_open != state->open.size - 1) + state->open.values[index_in_open] = + state->open.values[state->open.size - 1]; + --state->open.size; + } + + // Check if we reached the destination + // + if (nearest_node.id == state->destination) { + if (state->closed.size + 1 > state->closed.capacity) { + // Restore the state + state->open.values[state->open.size - 1] = nearest_node; + ++state->open.size; + + return ASTAR_OUT_OF_MEMORY; + } + + // Add the nearest node to the closed set + // + state->closed.values[state->closed.size] = nearest_node; + ++state->closed.size; + + // Finish the search + return ASTAR_SUCCESS; + } + + // Enumerate all neighbors + // + for (i64 k = 0;; ++k) { + // Get a link to the next neighbor node + // + (void) state->user_data; + (void) nearest_node.id; + (void) k; + astar_link_t link = ASTAR_NEIGHBOR(state->user_data, + nearest_node.id, k); + + // If there is no more neighbors, break the loop + if (link.stop) + break; + // If there is no link, proceed to the next link + if (link.skip) + continue; + + astar_node_t neighbor_node = { + .id = link.neighbor, + .previous = nearest_node.id, + .exact_source_to_node = nearest_node.exact_source_to_node + + link.distance, + .estimated_source_to_destination = -1, + }; + + // Calculate distance estimations + // + (void) state->user_data; + (void) neighbor_node.id; + (void) state->destination; + i64 estimated_node_to_destination = ASTAR_HEURISTIC( + state->user_data, neighbor_node.id, state->destination); + + neighbor_node.estimated_source_to_destination = + neighbor_node.exact_source_to_node + + estimated_node_to_destination; + + // Check if we reached the destination + // + if (neighbor_node.id == state->destination) { + if (state->closed.size + 2 > state->closed.capacity) { + // Restore the state + state->open.values[state->open.size - 1] = nearest_node; + ++state->open.size; + + return ASTAR_OUT_OF_MEMORY; + } + + // Add the nearest node to the closed set + // + state->closed.values[state->closed.size] = nearest_node; + ++state->closed.size; + + // Add the neighbor node to the closed set + // + state->closed.values[state->closed.size] = neighbor_node; + ++state->closed.size; + + // Finish the search + return ASTAR_SUCCESS; + } + + // Check if this node is already in the closed set + // + { + i64 index_in_closed = -1; + for (i64 i = 0; i < state->closed.size; ++i) + if (state->closed.values[i].id == neighbor_node.id) { + index_in_closed = i; + break; + } + if (index_in_closed != -1) { + if (state->closed.values[index_in_closed] + .exact_source_to_node < + neighbor_node.exact_source_to_node) + // Skip this node + continue; + // Replace the node + state->closed.values[index_in_closed] = neighbor_node; + } + } + + // Check if this node is already in the open set + // + { + i64 index_in_open = -1; + for (i64 i = 0; i < state->closed.size; ++i) + if (state->open.values[i].id == neighbor_node.id) { + index_in_open = i; + break; + } + if (index_in_open != -1) { + // Check if this node has a better estimate + // + if (neighbor_node.estimated_source_to_destination < + state->open.values[index_in_open] + .estimated_source_to_destination) + // Replace the node + state->open.values[index_in_open] = neighbor_node; + continue; + } + } + + if (state->open.size + 1 > state->open.capacity) { + // Restore the state + state->open.values[state->open.size - 1] = nearest_node; + ++state->open.size; + + return ASTAR_OUT_OF_MEMORY; + } + + // Add this node to the open set + // + state->open.values[state->open.size] = neighbor_node; + ++state->open.size; + } + + // Check if we can add a node to the closed set + // + if (state->closed.size + 1 > state->closed.capacity) { + // Restore the state + state->open.values[state->open.size - 1] = nearest_node; + ++state->open.size; + + return ASTAR_OUT_OF_MEMORY; + } + + // Add the nearest node to the closed set + // + state->closed.values[state->closed.size] = nearest_node; + ++state->closed.size; + + // Continue the search + return ASTAR_PROGRESS; +} + +#undef NAME_ +#undef CAT1_ +#undef CAT2_ + +#ifdef __GNUC__ +# pragma GCC pop_options +# pragma GCC diagnostic pop +#endif + +#ifdef __cplusplus +} +#endif + +#undef ASTAR_TEMPLATE +#endif diff --git a/source/kit/file.c b/source/kit/file.c index 76d3249..3eafc70 100644 --- a/source/kit/file.c +++ b/source/kit/file.c @@ -465,7 +465,7 @@ kit_path_list_t kit_folder_enum(kit_str_t path, i64 n = result.files.size; DA_RESIZE(result.files, n + 1); if (result.files.size != n + 1) { - result.status = KIT_ERROR_BAD_ALLOC; + result.status = KIT_ERROR_OUT_OF_MEMORY; break; } @@ -473,7 +473,7 @@ kit_path_list_t kit_folder_enum(kit_str_t path, DA_INIT(result.files.values[n], size, alloc); if (result.files.values[n].size != size) { DA_RESIZE(result.files, n); - result.status = KIT_ERROR_BAD_ALLOC; + result.status = KIT_ERROR_OUT_OF_MEMORY; break; } @@ -499,7 +499,7 @@ kit_path_list_t kit_folder_enum(kit_str_t path, i64 n = result.files.size; DA_RESIZE(result.files, n + 1); if (result.files.size != n + 1) { - result.status = KIT_ERROR_BAD_ALLOC; + result.status = KIT_ERROR_OUT_OF_MEMORY; break; } @@ -507,7 +507,7 @@ kit_path_list_t kit_folder_enum(kit_str_t path, DA_INIT(result.files.values[n], size, alloc); if (result.files.values[n].size != size) { DA_RESIZE(result.files, n); - result.status = KIT_ERROR_BAD_ALLOC; + result.status = KIT_ERROR_OUT_OF_MEMORY; break; } diff --git a/source/kit/input_buffer.c b/source/kit/input_buffer.c index db7e156..59298c8 100644 --- a/source/kit/input_buffer.c +++ b/source/kit/input_buffer.c @@ -19,7 +19,7 @@ static s32 kit_buf_adjust_(kit_input_buffer_t *buf, i64 size) { DA_RESIZE(buf->data, size); if (buf->data.size != size) - return KIT_ERROR_BAD_ALLOC; + return KIT_ERROR_OUT_OF_MEMORY; str_t destination = { .size = size - offset, .values = buf->data.values + offset }; @@ -27,7 +27,7 @@ static s32 kit_buf_adjust_(kit_input_buffer_t *buf, i64 size) { DA_RESIZE(buf->data, offset + n); if (buf->data.size != offset + n) - return KIT_ERROR_BAD_ALLOC; + return KIT_ERROR_OUT_OF_MEMORY; return KIT_OK; } @@ -118,7 +118,7 @@ kit_ib_token_t kit_ib_read(kit_ib_token_t tok, i64 size) { } else { \ DA_INIT(cache_dynamic, data.size, tok.buffer->data.alloc); \ if (cache_dynamic.size != data.size) { \ - (res_).status |= KIT_ERROR_BAD_ALLOC; \ + (res_).status |= KIT_ERROR_OUT_OF_MEMORY; \ return (res_); \ } \ memcpy(cache_dynamic.values, data.values, data.size); \ diff --git a/source/kit/shared_mutex.h b/source/kit/shared_mutex.h index d202090..ad83418 100644 --- a/source/kit/shared_mutex.h +++ b/source/kit/shared_mutex.h @@ -47,7 +47,7 @@ static void kit_shared_mutex_init(kit_shared_mutex_t *m) { memory_order_relaxed); } -static i8 kit_shared_try_lock(kit_shared_mutex_t *m) { +static b8 kit_shared_try_lock(kit_shared_mutex_t *m) { assert(m != NULL); for (;;) { @@ -108,7 +108,7 @@ static void kit_shared_unlock(kit_shared_mutex_t *m) { assert(0); } -static i8 kit_unique_try_lock(kit_shared_mutex_t *m) { +static b8 kit_unique_try_lock(kit_shared_mutex_t *m) { assert(m != NULL); i8 prev_state = KIT_SHARED_MUTEX_READY; diff --git a/source/kit/status.h b/source/kit/status.h index 7ea1c4d..88eb5e0 100644 --- a/source/kit/status.h +++ b/source/kit/status.h @@ -8,7 +8,7 @@ enum { KIT_OK = 0, KIT_PARSING_FAILED = 1, - KIT_ERROR_BAD_ALLOC = (1 << 1), + KIT_ERROR_OUT_OF_MEMORY = (1 << 1), KIT_ERROR_INVALID_ARGUMENT = (1 << 2), KIT_ERROR_MKDIR_FAILED = (1 << 3), KIT_ERROR_RMDIR_FAILED = (1 << 4), diff --git a/source/kit/string_builder.h b/source/kit/string_builder.h index c869afb..23eda65 100644 --- a/source/kit/string_builder.h +++ b/source/kit/string_builder.h @@ -56,7 +56,7 @@ static s32 kit_str_append(kit_str_builder_t *a, kit_str_t b) { i64 n = a->size; KIT_DA_RESIZE(*a, n + b.size); if (a->size != n + b.size) - return KIT_ERROR_BAD_ALLOC; + return KIT_ERROR_OUT_OF_MEMORY; memcpy(a->values + n, b.values, b.size); return KIT_OK; } @@ -71,7 +71,7 @@ static s32 kit_str_insert(kit_str_builder_t *a, i64 index, i64 n = a->size; KIT_DA_RESIZE(*a, n + b.size); if (a->size != n + b.size) - return KIT_ERROR_BAD_ALLOC; + return KIT_ERROR_OUT_OF_MEMORY; if (index < n) memmove(a->values + (index + b.size), a->values + index, n - index); diff --git a/source/kit/test.h b/source/kit/test.h index 24a25c9..ca2b7c0 100644 --- a/source/kit/test.h +++ b/source/kit/test.h @@ -725,7 +725,7 @@ int kit_run_tests(int argc, char **argv) { quiet || printf("FAILED\n"); } - no_color || kit_print_color_(kit_white_); + no_color || kit_print_color_(kit_light_); quiet || printf("\n"); return status; } @@ -1099,7 +1099,7 @@ int kit_run_benchmarks(int argc, char **argv) { printf("DONE WITH ERRORS\n"); } - no_color || kit_print_color_(kit_white_); + no_color || kit_print_color_(kit_light_); printf("\n"); return status; } diff --git a/source/kit/xml.c b/source/kit/xml.c index 8d22bf3..0d8378c 100644 --- a/source/kit/xml.c +++ b/source/kit/xml.c @@ -22,7 +22,7 @@ static s32 kit_xml_alloc_and_unescape_(str_builder_t *dst, str_t str, DA_INIT(*dst, str.size, alloc); if (dst->size != str.size) - return KIT_ERROR_BAD_ALLOC; + return KIT_ERROR_OUT_OF_MEMORY; dst->size = 0; @@ -127,7 +127,8 @@ static ib_token_t kit_xml_parse_text_(ib_token_t begin, assert(dst->size == last.size); if (dst->size != last.size) - last.status |= KIT_ERROR_BAD_ALLOC; + last.status |= KIT_ERROR_OUT_OF_MEMORY +; else if (last.size > 0) memcpy(dst->values, ib_str(last).values, last.size); @@ -147,7 +148,8 @@ static ib_token_t kit_xml_parse_text_(ib_token_t begin, assert(dst->size == n + next_text.size); if (dst->size != n + next_text.size) - next_text.status |= KIT_ERROR_BAD_ALLOC; + next_text.status |= KIT_ERROR_OUT_OF_MEMORY + ; else memcpy(dst->values + n, ib_str(next_text).values, ib_str(next_text).size); @@ -246,7 +248,8 @@ static kit_xml_intermediate_t kit_xml_parse_buf_( assert(tag.properties.size == n + 1); if (tag.properties.size != n + 1) { - last.status |= KIT_ERROR_BAD_ALLOC; + last.status |= KIT_ERROR_OUT_OF_MEMORY + ; DA_DESTROY(tag.properties); } else { last.status |= kit_xml_alloc_and_unescape_( @@ -303,7 +306,8 @@ static kit_xml_intermediate_t kit_xml_parse_buf_( assert(res.tags.size == n + 1); if (res.tags.size != n + 1) { - last.status |= KIT_ERROR_BAD_ALLOC; + last.status |= KIT_ERROR_OUT_OF_MEMORY + ; xml_destroy(&tag); } else { last.status |= kit_xml_alloc_and_unescape_( @@ -390,7 +394,7 @@ static s32 kit_xml_append_text_(str_builder_t *buf, xml_t *xml) { assert(buf->size == n + xml->text.size); if (buf->size != n + xml->text.size) - return KIT_ERROR_BAD_ALLOC; + return KIT_ERROR_OUT_OF_MEMORY; if (xml->text.size > 0) memcpy(buf->values + n, xml->text.values, xml->text.size); @@ -410,7 +414,8 @@ static s32 kit_xml_append_text_(str_builder_t *buf, xml_t *xml) { assert(buf->size == n + tail.size); if (buf->size != n + tail.size) - return KIT_ERROR_BAD_ALLOC; + return KIT_ERROR_OUT_OF_MEMORY +; if (tail.size > 0) memcpy(buf->values + n, tail.values, tail.size); -- cgit v1.2.3