From 87a93623126c41cdfdbdb62878efb3f1d33b819e Mon Sep 17 00:00:00 2001 From: Andrew Opalach Date: Tue, 25 Aug 2026 19:38:29 -0400 Subject: Add numerical sort for files Signed-off-by: Andrew Opalach --- include/nnwt/sort.h | 3 + meson.build | 1 + src/util/sort.c | 61 ++++++++++++++ src/util/sort.h | 1 + tests/meson.build | 1 + tests/units.c | 224 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 291 insertions(+) create mode 100644 include/nnwt/sort.h create mode 100644 src/util/sort.c create mode 100644 src/util/sort.h create mode 100644 tests/units.c diff --git a/include/nnwt/sort.h b/include/nnwt/sort.h new file mode 100644 index 0000000..571eb5d --- /dev/null +++ b/include/nnwt/sort.h @@ -0,0 +1,3 @@ +#pragma once + +#include "../../src/util/sort.h" diff --git a/meson.build b/meson.build index 14d2245..751f6f6 100644 --- a/meson.build +++ b/meson.build @@ -15,6 +15,7 @@ naunet_src = [ 'src/util/error.c', 'src/util/buffer.c', 'src/util/packet.c', + 'src/util/sort.c', 'src/util/file/util.c' ] naunet_inc = [include_directories('include')] diff --git a/src/util/sort.c b/src/util/sort.c new file mode 100644 index 0000000..8d306a8 --- /dev/null +++ b/src/util/sort.c @@ -0,0 +1,61 @@ +#include + +static inline u32 find_number(str *s) +{ + u32 i = 0; + while (i < s->length && !al_isnumber(al_str_at(s, i))) { i++; } + return (i == s->length) ? AL_STR_NO_POS : i; +} + +static inline u32 find_non_number(str *s) +{ + u32 i = 0; + while (i < s->length && al_isnumber(al_str_at(s, i))) { i++; } + return i; +} + +s32 nn_numerical_compare(const void *a, const void *b) +{ + str s1 = *(str *)a, s2 = *(str *)b; + s32 ret; + str sub1, sub2; + bool error; + s64 n1, n2; + u32 nn1 = find_number(&s1); + u32 nn2 = find_number(&s2); + if (nn1 != nn2) { + goto compare_remainder; + } + s1 = al_str_substr(&s1, nn1, s1.length); + s2 = al_str_substr(&s2, nn2, s2.length); + do { + nn1 = find_non_number(&s1); + nn2 = find_non_number(&s2); + sub1 = al_str_substr(&s1, 0, nn1); + sub2 = al_str_substr(&s2, 0, nn2); + n1 = al_str_to_long(&sub1, 10, &error); + al_assert(!error); + n2 = al_str_to_long(&sub2, 10, &error); + al_assert(!error); + if (n1 > n2) return 1; + else if (n1 < n2) return -1; + s1 = al_str_substr(&s1, nn1, s1.length); + s2 = al_str_substr(&s2, nn2, s2.length); + nn1 = find_number(&s1); + nn2 = find_number(&s2); + if (nn1 == AL_STR_NO_POS || nn2 == AL_STR_NO_POS) { + goto compare_remainder; + } + sub1 = al_str_substr(&s1, 0, nn1); + sub2 = al_str_substr(&s2, 0, nn2); + if (!al_str_eq(&sub1, &sub2)) { + goto compare_remainder; + } + s1 = al_str_substr(&s1, nn1, s1.length); + s2 = al_str_substr(&s2, nn2, s2.length); + } while (1); +compare_remainder: + ret = al_str_cmp(&s1, &s2, 0, MIN(s1.length, s2.length)); + if (ret == 0) return s1.length - s2.length; + return ret; +} diff --git a/src/util/sort.h b/src/util/sort.h new file mode 100644 index 0000000..6c0cfc7 --- /dev/null +++ b/src/util/sort.h @@ -0,0 +1 @@ +s32 nn_numerical_compare(const void *a, const void *b); diff --git a/tests/meson.build b/tests/meson.build index 1074e40..70b06ef 100644 --- a/tests/meson.build +++ b/tests/meson.build @@ -1,3 +1,4 @@ +executable('units', ['units.c'], dependencies: naunet) executable('misc_file', ['misc_file.c'], dependencies: naunet) executable('condition_variable', ['condition_variable.c'], dependencies: naunet) executable('timer_thread', ['timer_thread.c'], dependencies: naunet) diff --git a/tests/units.c b/tests/units.c new file mode 100644 index 0000000..5cbd4a0 --- /dev/null +++ b/tests/units.c @@ -0,0 +1,224 @@ +#include +#include +#include +#include +#include +#include + +#define SHUFFLE_ARRAY(arr) do { \ + al_assert((arr).count > 2); \ + for (u32 i = 0; i < (arr).count - 2; i++) { \ + u32 j = al_random_int(i, (arr).count - 1); \ + SWAP(al_array_at(arr, i), al_array_at(arr, j)); \ + } \ +} while (0) + +static bool sort_test_numerical_compare(void) +{ + AL_TEST_START("sort_numerical_compare"); + + array(str) strings; + al_array_init(strings); + + str files1[] = { + al_str_c("631475239_1.jpg"), + al_str_c("631475239_2.jpg"), + al_str_c("631475239_3.jpg"), + al_str_c("631475239_4.jpg"), + al_str_c("631475239_5.jpg"), + al_str_c("631475239_6.jpg"), + al_str_c("631475239_7.jpg"), + al_str_c("631475239_8.jpg"), + al_str_c("631475239_9.jpg"), + al_str_c("631475239_10.jpg"), + al_str_c("631475239_11.jpg"), + al_str_c("631475239_12.jpg"), + al_str_c("631475239_13.jpg"), + al_str_c("631475239_14.jpg"), + al_str_c("631475239_15.jpg"), + al_str_c("631475239_15.jpg"), + al_str_c("631475239_16.jpg"), + al_str_c("631475239_17.jpg"), + al_str_c("631475239_18.jpg"), + al_str_c("631475239_19.jpg"), + al_str_c("631475239_20.m4v"), + al_str_c("631475239_21.mp4") + }; + + al_array_push(strings, files1[7]); + al_array_push(strings, files1[16]); + al_array_push(strings, files1[2]); + al_array_push(strings, files1[10]); + al_array_push(strings, files1[3]); + al_array_push(strings, files1[13]); + al_array_push(strings, files1[4]); + al_array_push(strings, files1[6]); + al_array_push(strings, files1[17]); + al_array_push(strings, files1[18]); + al_array_push(strings, files1[8]); + al_array_push(strings, files1[19]); + al_array_push(strings, files1[9]); + al_array_push(strings, files1[11]); + al_array_push(strings, files1[5]); + al_array_push(strings, files1[12]); + al_array_push(strings, files1[21]); + al_array_push(strings, files1[0]); + al_array_push(strings, files1[14]); + al_array_push(strings, files1[15]); + al_array_push(strings, files1[1]); + al_array_push(strings, files1[20]); + SHUFFLE_ARRAY(strings); + + al_array_sort(strings, str, nn_numerical_compare); + + for (u32 i = 0; i < strings.count; i++) { + AL_TEST_TRUE(al_str_eq(&al_array_at(strings, i), &files1[i])); + } + + al_array_free(strings); + + al_array_init(strings); + + str files2[] = { + al_str_c("220.1png"), + al_str_c("220.jpg"), + al_str_c("220.png"), + al_str_c("35910.jpg"), + al_str_c("35910a.jpg"), + al_str_c("35910b.jpg"), + al_str_c("35910zzz.jpg"), + }; + + al_array_push(strings, files2[1]); + al_array_push(strings, files2[4]); + al_array_push(strings, files2[0]); + al_array_push(strings, files2[3]); + al_array_push(strings, files2[6]); + al_array_push(strings, files2[2]); + al_array_push(strings, files2[5]); + SHUFFLE_ARRAY(strings); + + al_array_sort(strings, str, nn_numerical_compare); + + for (u32 i = 0; i < strings.count; i++) { + AL_TEST_TRUE(al_str_eq(&al_array_at(strings, i), &files2[i])); + } + + al_array_free(strings); + + al_array_init(strings); + + str files3[] = { + al_str_c("214124_a.jpeg"), + al_str_c("625315_a.jpeg"), + al_str_c("1412310_b_2.png"), + al_str_c("1412311_b.png"), + al_str_c("1412311_b_2.png"), + al_str_c("1412311_b_b.png") + }; + + al_array_push(strings, files3[1]); + al_array_push(strings, files3[4]); + al_array_push(strings, files3[0]); + al_array_push(strings, files3[3]); + al_array_push(strings, files3[2]); + al_array_push(strings, files3[5]); + SHUFFLE_ARRAY(strings); + + al_array_sort(strings, str, nn_numerical_compare); + for (u32 i = 0; i < strings.count; i++) { + AL_TEST_TRUE(al_str_eq(&al_array_at(strings, i), &files3[i])); + } + + al_array_free(strings); + + al_array_init(strings); + + str files4[] = { + al_str_c("pixiv_i_75528824_media0.png"), + al_str_c("pixiv_i_76697911_media0.png"), + al_str_c("pixiv_i_80864793_media0.png"), + al_str_c("pixiv_i_80864793_media0.png"), + al_str_c("pixiv_i_80864793_media0.png"), + al_str_c("pixiv_i_80864793_media1.png"), + al_str_c("pixiv_i_122898592_media0.jpg"), + al_str_c("pixiv_i_122898592_media1.jfif") + }; + + al_array_push(strings, files4[3]); + al_array_push(strings, files4[4]); + al_array_push(strings, files4[6]); + al_array_push(strings, files4[2]); + al_array_push(strings, files4[5]); + al_array_push(strings, files4[7]); + al_array_push(strings, files4[1]); + al_array_push(strings, files4[0]); + SHUFFLE_ARRAY(strings); + + al_array_sort(strings, str, nn_numerical_compare); + + for (u32 i = 0; i < strings.count; i++) { + AL_TEST_TRUE(al_str_eq(&al_array_at(strings, i), &files4[i])); + } + + al_array_free(strings); + + al_array_init(strings); + + str files5[] = { + al_str_c("pixiv_i_24610911_media0.png"), + al_str_c("pixiv_i_27025514_media0.png"), + al_str_c("pixiv_i_33659689_media0.png"), + al_str_c("pixiv_i_42610626_media0.png"), + al_str_c("pixiv_i_49089079_media0.png"), + al_str_c("pixiv_i_49089079_media1.png"), + al_str_c("pixiv_i_49089079_media2.png"), + al_str_c("pixiv_i_49089079_media3.png"), + al_str_c("pixiv_i_49089079_media4.png"), + al_str_c("pixiv_i_49089079_media5.png"), + al_str_c("pixiv_i_49089079_media6.png"), + al_str_c("pixiv_i_49089079_media7.png"), + al_str_c("pixiv_i_49089079_media8.png"), + al_str_c("pixiv_i_49089079_media9.png"), + al_str_c("pixiv_i_49089079_media10.png"), + al_str_c("pixiv_i_49089079_media11.png"), + al_str_c("pixiv_i_49089079_media12.png"), + al_str_c("pixiv_i_49089079_media13.png"), + al_str_c("pixiv_i_49089079_media14.png"), + al_str_c("pixiv_i_49089079_media15.png"), + al_str_c("pixiv_i_49089079_media16.png"), + al_str_c("pixiv_i_49089079_media17.png"), + al_str_c("pixiv_i_49089079_media18.png"), + al_str_c("pixiv_i_49089079_media19.png"), + al_str_c("pixiv_i_49089079_media20.png"), + al_str_c("pixiv_i_49089079_media21.png"), + al_str_c("pixiv_i_114990114_media0.png") + }; + for (u32 i = 0; i < ARRAY_SIZE(files5); i++) { + al_array_push(strings, files5[i]); + } + SHUFFLE_ARRAY(strings); + + al_array_sort(strings, str, nn_numerical_compare); + + for (u32 i = 0; i < strings.count; i++) { + AL_TEST_TRUE(al_str_eq(&al_array_at(strings, i), &files5[i])); + } + + al_array_free(strings); + + AL_TEST_END(); +} + +s32 main(void) +{ + if (!nn_common_init(NULL)) return EXIT_FAILURE; + + AL_TEST_START_GROUP("units"); + + AL_TEST_RUN(sort_test_numerical_compare); + + AL_TEST_END_GROUP(); + + return EXIT_SUCCESS; +} -- cgit v1.2.3-101-g0448