From 73cfec103c8649a2b6f6456e804c23f7d4fa0860 Mon Sep 17 00:00:00 2001 From: Mitya Selivanov <0x7fffff@guattari.ru> Date: Sun, 21 Aug 2022 18:24:31 +0400 Subject: move back algorithm --- source/kit/CMakeLists.txt | 3 +- source/kit/move_back.c | 1 + source/kit/move_back.h | 59 +++++++++++++ source/test/unittests/CMakeLists.txt | 2 +- source/test/unittests/move_back.test.c | 156 +++++++++++++++++++++++++++++++++ 5 files changed, 219 insertions(+), 2 deletions(-) create mode 100644 source/kit/move_back.c create mode 100644 source/kit/move_back.h create mode 100644 source/test/unittests/move_back.test.c 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( $ $ $ + $ $ $ $ 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 + +#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); +} -- cgit v1.2.3