diff options
author | Mitya Selivanov <0x7fffff@guattari.ru> | 2022-08-21 18:24:31 +0400 |
---|---|---|
committer | Mitya Selivanov <0x7fffff@guattari.ru> | 2022-08-21 18:24:31 +0400 |
commit | 73cfec103c8649a2b6f6456e804c23f7d4fa0860 (patch) | |
tree | 67cc41791929293a9a404ea58d3a34f4523f6bb0 /source | |
parent | 4ec4e5e401d1da1777c50f87344a02a006ef0693 (diff) | |
download | kit-73cfec103c8649a2b6f6456e804c23f7d4fa0860.zip |
move back algorithm
Diffstat (limited to 'source')
-rw-r--r-- | source/kit/CMakeLists.txt | 3 | ||||
-rw-r--r-- | source/kit/move_back.c | 1 | ||||
-rw-r--r-- | source/kit/move_back.h | 59 | ||||
-rw-r--r-- | source/test/unittests/CMakeLists.txt | 2 | ||||
-rw-r--r-- | source/test/unittests/move_back.test.c | 156 |
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); +} |