move back algorithm

5 files changed, 219 insertions, 2 deletions

diff --git a/source/kit/CMakeLists.txt b/source/kit/CMakeLists.txt
index b5fe0f6..a8aaf02 100644
--- a/source/kit/CMakeLists.txt
+++ b/source/kit/CMakeLists.txt
@@ -2,7 +2,7 @@ target_sources(
   ${KIT_LIBRARY}
     PRIVATE
       atomic.c input_buffer.c threads.win32.c time.c
-      threads.posix.c input_stream.c lower_bound.c string_ref.c
+      threads.posix.c move_back.c input_stream.c lower_bound.c string_ref.c
       async_function.c allocator.c array_ref.c dynamic_array.c
       mersenne_twister_64.c
     PUBLIC
@@ -13,6 +13,7 @@ target_sources(
       $<BUILD_INTERFACE:${CMAKE_CURRENT_LIST_DIR}/threads.h>
       $<BUILD_INTERFACE:${CMAKE_CURRENT_LIST_DIR}/dynamic_array.h>
       $<BUILD_INTERFACE:${CMAKE_CURRENT_LIST_DIR}/async_function.h>
+      $<BUILD_INTERFACE:${CMAKE_CURRENT_LIST_DIR}/move_back.h>
       $<BUILD_INTERFACE:${CMAKE_CURRENT_LIST_DIR}/input_stream.h>
       $<BUILD_INTERFACE:${CMAKE_CURRENT_LIST_DIR}/input_buffer.h>
       $<BUILD_INTERFACE:${CMAKE_CURRENT_LIST_DIR}/lower_bound.h>
diff --git a/source/kit/move_back.c b/source/kit/move_back.c
new file mode 100644
index 0000000..dcb62be
--- /dev/null
+++ b/source/kit/move_back.c
@@ -0,0 +1 @@
+#include "move_back.h"
diff --git a/source/kit/move_back.h b/source/kit/move_back.h
new file mode 100644
index 0000000..2df12cd
--- /dev/null
+++ b/source/kit/move_back.h
@@ -0,0 +1,59 @@
+#ifndef KIT_MOVE_BACK_H
+#define KIT_MOVE_BACK_H
+
+#include <string.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define KIT_MOVE_BACK(new_size, array, value, cond)  \
+  do {                                               \
+    ptrdiff_t     end_ = (array).size;               \
+    unsigned char temp_[sizeof *(array).values];     \
+    for (ptrdiff_t i_ = 0; i_ < end_;) {             \
+      if ((cond) ((array).values[i_], (value))) {    \
+        end_--;                                      \
+        if (i_ != end_) {                            \
+          memcpy(temp_, (array).values + end_,       \
+                 sizeof *(array).values);            \
+          (array).values[end_] = (array).values[i_]; \
+          memcpy((array).values + i_, temp_,         \
+                 sizeof *(array).values);            \
+        }                                            \
+      } else                                         \
+        i_++;                                        \
+    }                                                \
+    (new_size) = end_;                               \
+  } while (0)
+
+#define KIT_MOVE_BACK_REF(new_size, array, value, cond) \
+  do {                                                  \
+    ptrdiff_t     end_ = (array).size;                  \
+    unsigned char temp_[sizeof *(array).values];        \
+    for (ptrdiff_t i_ = 0; i_ < end_;) {                \
+      if ((cond) (&(array).values[i_], &(value))) {     \
+        end_--;                                         \
+        if (i_ != end_) {                               \
+          memcpy(temp_, (array).values + end_,          \
+                 sizeof *(array).values);               \
+          (array).values[end_] = (array).values[i_];    \
+          memcpy((array).values + i_, temp_,            \
+                 sizeof *(array).values);               \
+        }                                               \
+      } else                                            \
+        i_++;                                           \
+    }                                                   \
+    (new_size) = end_;                                  \
+  } while (0)
+
+#ifndef KIT_DISABLE_SHORT_NAMES
+#  define MOVE_BACK KIT_MOVE_BACK
+#  define MOVE_BACK_REF KIT_MOVE_BACK_REF
+#endif
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/source/test/unittests/CMakeLists.txt b/source/test/unittests/CMakeLists.txt
index e64628d..29dd1b2 100644
--- a/source/test/unittests/CMakeLists.txt
+++ b/source/test/unittests/CMakeLists.txt
@@ -5,4 +5,4 @@ target_sources(
       main.test.c string_ref.test.c atomic.test.c thread.test.c
       array_ref.test.c input_stream.test.c lower_bound.test.c
       condition_variable.test.c mersenne_twister_64.test.c input_buffer.test.c
-      dynamic_array.test.c)
+      move_back.test.c dynamic_array.test.c)
diff --git a/source/test/unittests/move_back.test.c b/source/test/unittests/move_back.test.c
new file mode 100644
index 0000000..cbb6f23
--- /dev/null
+++ b/source/test/unittests/move_back.test.c
@@ -0,0 +1,156 @@
+#include "../../kit/move_back.h"
+
+#define TEST_FILE move_back
+#include "../../kit_test/test.h"
+
+static int is_equal(int const x, int const y) {
+  return x == y;
+}
+
+static int is_equal_ref(int const *const x, int const *const y) {
+  return *x == *y;
+}
+
+static int is_even(int const x, int const _) {
+  return (x % 2) == 0;
+}
+
+static int is_even_ref(int const *const x, int const *const _) {
+  return (*x % 2) == 0;
+}
+
+TEST("move back val") {
+  int v[] = { 1, 2, 2, 2, 1, 1 };
+
+  struct {
+    int  size;
+    int *values;
+  } ref = { .size = sizeof v / sizeof *v, .values = v };
+
+  MOVE_BACK(ref.size, ref, 2, is_equal);
+
+  REQUIRE(ref.size == 3);
+  REQUIRE(v[0] == 1);
+  REQUIRE(v[1] == 1);
+  REQUIRE(v[2] == 1);
+}
+
+TEST("move back ref val") {
+  int v[] = { 1, 2, 2, 2, 1, 1 };
+
+  struct {
+    int  size;
+    int *values;
+  } ref = { .size = sizeof v / sizeof *v, .values = v };
+
+  int const two = 2;
+
+  MOVE_BACK_REF(ref.size, ref, two, is_equal_ref);
+
+  REQUIRE(ref.size == 3);
+  REQUIRE(v[0] == 1);
+  REQUIRE(v[1] == 1);
+  REQUIRE(v[2] == 1);
+}
+
+TEST("move back 1") {
+  int v[] = { 1, 2, 3, 4, 5, 6 };
+
+  struct {
+    int  size;
+    int *values;
+  } ref = { .size = sizeof v / sizeof *v, .values = v };
+
+  MOVE_BACK(ref.size, ref, 0, is_even);
+
+  REQUIRE(ref.size == 3);
+  REQUIRE(v[0] == 1);
+  REQUIRE(v[1] == 5);
+  REQUIRE(v[2] == 3);
+}
+
+TEST("move back 2") {
+  int v[] = { 2, 4, 6, 1, 3, 5 };
+
+  struct {
+    int  size;
+    int *values;
+  } ref = { .size = sizeof v / sizeof *v, .values = v };
+
+  MOVE_BACK(ref.size, ref, 0, is_even);
+
+  REQUIRE(ref.size == 3);
+  REQUIRE(v[0] == 5);
+  REQUIRE(v[1] == 3);
+  REQUIRE(v[2] == 1);
+}
+
+TEST("move back 3") {
+  int v[] = { 1, 3, 5, 2, 4, 6 };
+
+  struct {
+    int  size;
+    int *values;
+  } ref = { .size = sizeof v / sizeof *v, .values = v };
+
+  MOVE_BACK(ref.size, ref, 0, is_even);
+
+  REQUIRE(ref.size == 3);
+  REQUIRE(v[0] == 1);
+  REQUIRE(v[1] == 3);
+  REQUIRE(v[2] == 5);
+}
+
+TEST("move back ref 1") {
+  int v[] = { 1, 2, 3, 4, 5, 6 };
+
+  struct {
+    int  size;
+    int *values;
+  } ref = { .size = sizeof v / sizeof *v, .values = v };
+
+  int const nothing = 0;
+
+  MOVE_BACK_REF(ref.size, ref, nothing, is_even_ref);
+
+  REQUIRE(ref.size == 3);
+  REQUIRE(v[0] == 1);
+  REQUIRE(v[1] == 5);
+  REQUIRE(v[2] == 3);
+}
+
+TEST("move back ref 2") {
+  int v[] = { 2, 4, 6, 1, 3, 5 };
+
+  struct {
+    int  size;
+    int *values;
+  } ref = { .size = sizeof v / sizeof *v, .values = v };
+
+  int const nothing = 0;
+
+  MOVE_BACK_REF(ref.size, ref, nothing, is_even_ref);
+
+  REQUIRE(ref.size == 3);
+  REQUIRE(v[0] == 5);
+  REQUIRE(v[1] == 3);
+  REQUIRE(v[2] == 1);
+}
+
+TEST("move back ref 3") {
+  int v[] = { 1, 3, 5, 2, 4, 6 };
+
+  struct {
+    int  size;
+    int *values;
+  } ref = { .size = sizeof v / sizeof *v, .values = v };
+
+  int const nothing = 0;
+
+  MOVE_BACK_REF(ref.size, ref, nothing, is_even_ref);
+
+  REQUIRE(ref.size == 3);
+  REQUIRE(v[0] == 1);
+  REQUIRE(v[1] == 3);
+  REQUIRE(v[2] == 5);
+}