8 files changed, 427 insertions, 21 deletions

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 <assert.h>
+#include <stddef.h>
+#include <string.h>
+
+#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);