summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMitya Selivanov <0x7fffff@guattari.ru>2022-08-21 18:24:31 +0400
committerMitya Selivanov <0x7fffff@guattari.ru>2022-08-21 18:24:31 +0400
commit73cfec103c8649a2b6f6456e804c23f7d4fa0860 (patch)
tree67cc41791929293a9a404ea58d3a34f4523f6bb0
parent4ec4e5e401d1da1777c50f87344a02a006ef0693 (diff)
downloadkit-73cfec103c8649a2b6f6456e804c23f7d4fa0860.zip
move back algorithm
-rw-r--r--source/kit/CMakeLists.txt3
-rw-r--r--source/kit/move_back.c1
-rw-r--r--source/kit/move_back.h59
-rw-r--r--source/test/unittests/CMakeLists.txt2
-rw-r--r--source/test/unittests/move_back.test.c156
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);
+}