diff options
author | David Robillard <d@drobilla.net> | 2020-12-31 15:15:05 +0100 |
---|---|---|
committer | David Robillard <d@drobilla.net> | 2020-12-31 15:21:29 +0100 |
commit | 741c3349b09c8774fcd013e3bdd7d9e7f6b470ce (patch) | |
tree | a941f6567b85255570e5492f3c66a842704ba9f7 | |
parent | 841c766d86dc35ab37c4fef8ec866d06c41bc383 (diff) | |
download | zix-741c3349b09c8774fcd013e3bdd7d9e7f6b470ce.tar.gz zix-741c3349b09c8774fcd013e3bdd7d9e7f6b470ce.tar.bz2 zix-741c3349b09c8774fcd013e3bdd7d9e7f6b470ce.zip |
Format all code with clang-format
39 files changed, 3979 insertions, 3791 deletions
diff --git a/.clang-format b/.clang-format new file mode 100644 index 0000000..d2c0991 --- /dev/null +++ b/.clang-format @@ -0,0 +1,26 @@ +--- +AlignConsecutiveAssignments: true +AlignConsecutiveDeclarations: true +AlignEscapedNewlinesLeft: true +BasedOnStyle: Mozilla +BraceWrapping: + AfterEnum: false + AfterExternBlock: false + AfterFunction: true + AfterStruct: false + AfterUnion: false +BreakBeforeBraces: Custom +Cpp11BracedListStyle: true +IndentCaseLabels: false +IndentPPDirectives: AfterHash +KeepEmptyLinesAtTheStartOfBlocks: false +SpacesInContainerLiterals: false +StatementMacros: + - ZIX_API + - ZIX_CONST_API + - ZIX_CONST_API + - ZIX_MALLOC_API + - ZIX_PRIVATE + - ZIX_PURE_API + - ZIX_UNUSED +... diff --git a/benchmark/bench.h b/benchmark/bench.h index 716601b..3fc907f 100644 --- a/benchmark/bench.h +++ b/benchmark/bench.h @@ -22,23 +22,22 @@ static inline double elapsed_s(const struct timespec* start, const struct timespec* end) { - return ( (double)(end->tv_sec - start->tv_sec) - + ((double)(end->tv_nsec - start->tv_nsec) * 0.000000001) ); + return ((double)(end->tv_sec - start->tv_sec) + + ((double)(end->tv_nsec - start->tv_nsec) * 0.000000001)); } static inline struct timespec bench_start(void) { - struct timespec start_t; - clock_gettime(CLOCK_MONOTONIC, &start_t); - return start_t; + struct timespec start_t; + clock_gettime(CLOCK_MONOTONIC, &start_t); + return start_t; } static inline double bench_end(const struct timespec* start_t) { - struct timespec end_t; - clock_gettime(CLOCK_MONOTONIC, &end_t); - return elapsed_s(start_t, &end_t); + struct timespec end_t; + clock_gettime(CLOCK_MONOTONIC, &end_t); + return elapsed_s(start_t, &end_t); } - diff --git a/benchmark/dict_bench.c b/benchmark/dict_bench.c index 3cb2f0d..0ed794f 100644 --- a/benchmark/dict_bench.c +++ b/benchmark/dict_bench.c @@ -35,138 +35,139 @@ ZIX_LOG_FUNC(1, 2) static int test_fail(const char* fmt, ...) { - va_list args; - va_start(args, fmt); - fprintf(stderr, "error: "); - vfprintf(stderr, fmt, args); - va_end(args); - return 1; + va_list args; + va_start(args, fmt); + fprintf(stderr, "error: "); + vfprintf(stderr, fmt, args); + va_end(args); + return 1; } int main(int argc, char** argv) { - if (argc != 2) { - return test_fail("Usage: %s INPUT_FILE\n", argv[0]); - } - - const char* file = argv[1]; - FILE* fd = fopen(file, "r"); - if (!fd) { - return test_fail("Failed to open file %s\n", file); - } - - size_t max_n_strings = 100000000; - - /* Read input strings */ - char** strings = NULL; - size_t* lengths = NULL; - size_t n_strings = 0; - char* buf = (char*)calloc(1, 1); - size_t buf_len = 1; - size_t this_str_len = 0; - for (int c; (c = fgetc(fd)) != EOF;) { - if (isspace(c)) { - if (this_str_len == 0) { - continue; - } - strings = (char**)realloc(strings, (n_strings + 1) * sizeof(char*)); - lengths = (size_t*)realloc(lengths, (n_strings + 1) * sizeof(size_t)); - strings[n_strings] = (char*)malloc(buf_len); - lengths[n_strings] = this_str_len; - memcpy(strings[n_strings], buf, buf_len); - this_str_len = 0; - if (++n_strings == max_n_strings) { - break; - } - } else { - ++this_str_len; - if (buf_len < this_str_len + 1) { - buf_len = this_str_len + 1; - buf = (char*)realloc(buf, buf_len); - } - buf[this_str_len - 1] = (char)c; - buf[this_str_len] = '\0'; - } - } - - fclose(fd); - - FILE* insert_dat = fopen("dict_insert.txt", "w"); - FILE* search_dat = fopen("dict_search.txt", "w"); - fprintf(insert_dat, "# n\tGHashTable\tZixHash\n"); - fprintf(search_dat, "# n\tGHashTable\tZixHash\n"); - - for (size_t n = n_strings / 16; n <= n_strings; n *= 2) { - printf("Benchmarking n = %zu\n", n); - GHashTable* hash = g_hash_table_new(g_str_hash, g_str_equal); - ZixHash* zhash = zix_hash_new((ZixHashFunc)zix_chunk_hash, - (ZixEqualFunc)zix_chunk_equal, - sizeof(ZixChunk)); - fprintf(insert_dat, "%zu", n); - fprintf(search_dat, "%zu", n); - - // Benchmark insertion - - // GHashTable - struct timespec insert_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - g_hash_table_insert(hash, strings[i], strings[i]); - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // ZixHash - insert_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - const ZixChunk chunk = { strings[i], lengths[i] + 1 }; - ZixStatus st = zix_hash_insert(zhash, &chunk, NULL); - if (st && st != ZIX_STATUS_EXISTS) { - return test_fail("Failed to insert `%s'\n", strings[i]); - } - } - fprintf(insert_dat, "\t%lf\n", bench_end(&insert_start)); - - // Benchmark search - - // GHashTable - srand(seed); - struct timespec search_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - const size_t index = rand() % n; - char* match = (char*)g_hash_table_lookup(hash, strings[index]); - if (strcmp(match, strings[index])) { - return test_fail("Bad match for `%s'\n", strings[index]); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // ZixHash - srand(seed); - search_start = bench_start(); - for (size_t i = 0; i < n; ++i) { - const size_t index = rand() % n; - const ZixChunk key = { strings[index], lengths[index] + 1 }; - const ZixChunk* match = NULL; - if (!(match = (const ZixChunk*)zix_hash_find(zhash, &key))) { - return test_fail("Hash: Failed to find `%s'\n", strings[index]); - } - if (strcmp((const char*)match->buf, strings[index])) { - return test_fail("Hash: Bad match %p for `%s': `%s'\n", - (const void*)match, - strings[index], - (const char*)match->buf); - } - } - fprintf(search_dat, "\t%lf\n", bench_end(&search_start)); - - zix_hash_free(zhash); - g_hash_table_unref(hash); - } - - fclose(insert_dat); - fclose(search_dat); - - fprintf(stderr, "Wrote dict_insert.txt dict_search.txt\n"); - - return 0; + if (argc != 2) { + return test_fail("Usage: %s INPUT_FILE\n", argv[0]); + } + + const char* file = argv[1]; + FILE* fd = fopen(file, "r"); + if (!fd) { + return test_fail("Failed to open file %s\n", file); + } + + size_t max_n_strings = 100000000; + + /* Read input strings */ + char** strings = NULL; + size_t* lengths = NULL; + size_t n_strings = 0; + char* buf = (char*)calloc(1, 1); + size_t buf_len = 1; + size_t this_str_len = 0; + for (int c; (c = fgetc(fd)) != EOF;) { + if (isspace(c)) { + if (this_str_len == 0) { + continue; + } + strings = (char**)realloc(strings, (n_strings + 1) * sizeof(char*)); + lengths = (size_t*)realloc(lengths, (n_strings + 1) * sizeof(size_t)); + strings[n_strings] = (char*)malloc(buf_len); + lengths[n_strings] = this_str_len; + memcpy(strings[n_strings], buf, buf_len); + this_str_len = 0; + if (++n_strings == max_n_strings) { + break; + } + } else { + ++this_str_len; + if (buf_len < this_str_len + 1) { + buf_len = this_str_len + 1; + buf = (char*)realloc(buf, buf_len); + } + buf[this_str_len - 1] = (char)c; + buf[this_str_len] = '\0'; + } + } + + fclose(fd); + + FILE* insert_dat = fopen("dict_insert.txt", "w"); + FILE* search_dat = fopen("dict_search.txt", "w"); + fprintf(insert_dat, "# n\tGHashTable\tZixHash\n"); + fprintf(search_dat, "# n\tGHashTable\tZixHash\n"); + + for (size_t n = n_strings / 16; n <= n_strings; n *= 2) { + printf("Benchmarking n = %zu\n", n); + GHashTable* hash = g_hash_table_new(g_str_hash, g_str_equal); + ZixHash* zhash = zix_hash_new((ZixHashFunc)zix_chunk_hash, + (ZixEqualFunc)zix_chunk_equal, + sizeof(ZixChunk)); + fprintf(insert_dat, "%zu", n); + fprintf(search_dat, "%zu", n); + + // Benchmark insertion + + // GHashTable + struct timespec insert_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + g_hash_table_insert(hash, strings[i], strings[i]); + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + // ZixHash + insert_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + const ZixChunk chunk = {strings[i], lengths[i] + 1}; + ZixStatus st = zix_hash_insert(zhash, &chunk, NULL); + if (st && st != ZIX_STATUS_EXISTS) { + return test_fail("Failed to insert `%s'\n", strings[i]); + } + } + fprintf(insert_dat, "\t%lf\n", bench_end(&insert_start)); + + // Benchmark search + + // GHashTable + srand(seed); + struct timespec search_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + const size_t index = rand() % n; + char* match = (char*)g_hash_table_lookup(hash, strings[index]); + if (strcmp(match, strings[index])) { + return test_fail("Bad match for `%s'\n", strings[index]); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + // ZixHash + srand(seed); + search_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + const size_t index = rand() % n; + const ZixChunk key = {strings[index], lengths[index] + 1}; + const ZixChunk* match = NULL; + if (!(match = (const ZixChunk*)zix_hash_find(zhash, &key))) { + return test_fail("Hash: Failed to find `%s'\n", strings[index]); + } + + if (strcmp((const char*)match->buf, strings[index])) { + return test_fail("Hash: Bad match %p for `%s': `%s'\n", + (const void*)match, + strings[index], + (const char*)match->buf); + } + } + fprintf(search_dat, "\t%lf\n", bench_end(&search_start)); + + zix_hash_free(zhash); + g_hash_table_unref(hash); + } + + fclose(insert_dat); + fclose(search_dat); + + fprintf(stderr, "Wrote dict_insert.txt dict_search.txt\n"); + + return 0; } diff --git a/benchmark/tree_bench.c b/benchmark/tree_bench.c index b458bb1..d07c204 100644 --- a/benchmark/tree_bench.c +++ b/benchmark/tree_bench.c @@ -36,182 +36,185 @@ static size_t unique_rand(size_t i) { - i ^= 0x5CA1AB1E; // Juggle bits to avoid linear clumps + i ^= 0x5CA1AB1E; // Juggle bits to avoid linear clumps - // Largest prime < 2^32 which satisfies (2^32 = 3 mod 4) - static const size_t prime = 4294967291; - if (i >= prime) { - return i; // Values >= prime are mapped to themselves - } + // Largest prime < 2^32 which satisfies (2^32 = 3 mod 4) + static const size_t prime = 4294967291; + if (i >= prime) { + return i; // Values >= prime are mapped to themselves + } - const size_t residue = ((uint64_t)i * i) % prime; - return (i <= prime / 2) ? residue : prime - residue; + const size_t residue = ((uint64_t)i * i) % prime; + return (i <= prime / 2) ? residue : prime - residue; } static int int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data)) { - const intptr_t ia = (intptr_t)a; - const intptr_t ib = (intptr_t)b; + const intptr_t ia = (intptr_t)a; + const intptr_t ib = (intptr_t)b; - // note the (ia - ib) trick here would overflow + // note the (ia - ib) trick here would overflow - if (ia == ib) { - return 0; - } + if (ia == ib) { + return 0; + } - if (ia < ib) { - return -1; - } + if (ia < ib) { + return -1; + } - return 1; + return 1; } static int g_int_cmp(const void* a, const void* b, void* user_data) { - return int_cmp(a, b, user_data); + return int_cmp(a, b, user_data); } ZIX_LOG_FUNC(1, 2) static int test_fail(const char* fmt, ...) { - va_list args; - va_start(args, fmt); - fprintf(stderr, "error: "); - vfprintf(stderr, fmt, args); - va_end(args); - return EXIT_FAILURE; + va_list args; + va_start(args, fmt); + fprintf(stderr, "error: "); + vfprintf(stderr, fmt, args); + va_end(args); + return EXIT_FAILURE; } static void start_test(const char* name) { - fprintf(stderr, "Benchmarking %s\n", name); + fprintf(stderr, "Benchmarking %s\n", name); } static int bench_zix_tree(size_t n_elems, - FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat) + FILE* insert_dat, + FILE* search_dat, + FILE* iter_dat, + FILE* del_dat) { - start_test("ZixTree"); - - intptr_t r = 0; - ZixTreeIter* ti = NULL; - ZixTree* t = zix_tree_new(false, int_cmp, NULL, NULL); - - // Insert n_elems elements - struct timespec insert_start = bench_start(); - for (size_t i = 0; i < n_elems; i++) { - r = unique_rand(i); - int status = zix_tree_insert(t, (void*)r, &ti); - if (status) { - return test_fail("Failed to insert %" PRIdPTR "\n", r); - } - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // Search for all elements - struct timespec search_start = bench_start(); - for (size_t i = 0; i < n_elems; i++) { - r = unique_rand(i); - if (zix_tree_find(t, (void*)r, &ti)) { - return test_fail("Failed to find %" PRIdPTR "\n", r); - } - if ((intptr_t)zix_tree_get(ti) != r) { - return test_fail("Failed to get %" PRIdPTR "\n", r); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // Iterate over all elements - struct timespec iter_start = bench_start(); - for (ZixTreeIter* iter = zix_tree_begin(t); - !zix_tree_iter_is_end(iter); - iter = zix_tree_iter_next(iter)) { - zix_tree_get(iter); - } - fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); - - // Delete all elements - struct timespec del_start = bench_start(); - for (size_t i = 0; i < n_elems; i++) { - r = unique_rand(i); - ZixTreeIter* item; - if (zix_tree_find(t, (void*)r, &item)) { - return test_fail("Failed to find %" PRIdPTR " to delete\n", r); - } - if (zix_tree_remove(t, item)) { - return test_fail("Failed to remove %" PRIdPTR "\n", r); - } - } - fprintf(del_dat, "\t%lf", bench_end(&del_start)); - - zix_tree_free(t); - - return EXIT_SUCCESS; + start_test("ZixTree"); + + intptr_t r = 0; + ZixTreeIter* ti = NULL; + ZixTree* t = zix_tree_new(false, int_cmp, NULL, NULL); + + // Insert n_elems elements + struct timespec insert_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = unique_rand(i); + int status = zix_tree_insert(t, (void*)r, &ti); + if (status) { + return test_fail("Failed to insert %" PRIdPTR "\n", r); + } + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + // Search for all elements + struct timespec search_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = unique_rand(i); + if (zix_tree_find(t, (void*)r, &ti)) { + return test_fail("Failed to find %" PRIdPTR "\n", r); + } + if ((intptr_t)zix_tree_get(ti) != r) { + return test_fail("Failed to get %" PRIdPTR "\n", r); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + // Iterate over all elements + struct timespec iter_start = bench_start(); + for (ZixTreeIter* iter = zix_tree_begin(t); !zix_tree_iter_is_end(iter); + iter = zix_tree_iter_next(iter)) { + zix_tree_get(iter); + } + fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); + + // Delete all elements + struct timespec del_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = unique_rand(i); + ZixTreeIter* item; + if (zix_tree_find(t, (void*)r, &item)) { + return test_fail("Failed to find %" PRIdPTR " to delete\n", r); + } + if (zix_tree_remove(t, item)) { + return test_fail("Failed to remove %" PRIdPTR "\n", r); + } + } + fprintf(del_dat, "\t%lf", bench_end(&del_start)); + + zix_tree_free(t); + + return EXIT_SUCCESS; } static int bench_zix_btree(size_t n_elems, - FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat) + FILE* insert_dat, + FILE* search_dat, + FILE* iter_dat, + FILE* del_dat) { - start_test("ZixBTree"); - - intptr_t r = 0; - ZixBTreeIter* ti = NULL; - ZixBTree* t = zix_btree_new(int_cmp, NULL, NULL); - - // Insert n_elems elements - struct timespec insert_start = bench_start(); - for (size_t i = 0; i < n_elems; i++) { - r = unique_rand(i); - int status = zix_btree_insert(t, (void*)r); - if (status) { - return test_fail("Failed to insert %" PRIdPTR "\n", r); - } - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // Search for all elements - struct timespec search_start = bench_start(); - for (size_t i = 0; i < n_elems; i++) { - r = unique_rand(i); - if (zix_btree_find(t, (void*)r, &ti)) { - return test_fail("Failed to find %" PRIdPTR "\n", r); - } - if ((intptr_t)zix_btree_get(ti) != r) { - return test_fail("Failed to get %" PRIdPTR "\n", r); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // Iterate over all elements - struct timespec iter_start = bench_start(); - ZixBTreeIter* iter = zix_btree_begin(t); - for (; - !zix_btree_iter_is_end(iter); - zix_btree_iter_increment(iter)) { - zix_btree_get(iter); - } - zix_btree_iter_free(iter); - fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); - - // Delete all elements - struct timespec del_start = bench_start(); - for (size_t i = 0; i < n_elems; i++) { - r = unique_rand(i); - void* removed; - if (zix_btree_remove(t, (void*)r, &removed, NULL)) { - return test_fail("Failed to remove %" PRIdPTR "\n", r); - } - } - fprintf(del_dat, "\t%lf", bench_end(&del_start)); - - zix_btree_free(t); - - return EXIT_SUCCESS; + start_test("ZixBTree"); + + intptr_t r = 0; + ZixBTreeIter* ti = NULL; + ZixBTree* t = zix_btree_new(int_cmp, NULL, NULL); + + // Insert n_elems elements + struct timespec insert_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = unique_rand(i); + int status = zix_btree_insert(t, (void*)r); + if (status) { + return test_fail("Failed to insert %" PRIdPTR "\n", r); + } + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + // Search for all elements + struct timespec search_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = unique_rand(i); + if (zix_btree_find(t, (void*)r, &ti)) { + return test_fail("Failed to find %" PRIdPTR "\n", r); + } + if ((intptr_t)zix_btree_get(ti) != r) { + return test_fail("Failed to get %" PRIdPTR "\n", r); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + // Iterate over all elements + struct timespec iter_start = bench_start(); + ZixBTreeIter* iter = zix_btree_begin(t); + for (; !zix_btree_iter_is_end(iter); zix_btree_iter_increment(iter)) { + zix_btree_get(iter); + } + zix_btree_iter_free(iter); + fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); + + // Delete all elements + struct timespec del_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = unique_rand(i); + void* removed; + if (zix_btree_remove(t, (void*)r, &removed, NULL)) { + return test_fail("Failed to remove %" PRIdPTR "\n", r); + } + } + fprintf(del_dat, "\t%lf", bench_end(&del_start)); + + zix_btree_free(t); + + return EXIT_SUCCESS; } #ifdef BENCH_SORTED_ARRAY @@ -219,197 +222,210 @@ bench_zix_btree(size_t n_elems, static int int_ptr_cmp(const void* a, const void* b, void* user_data) { - const intptr_t ia = *(const intptr_t*)a; - const intptr_t ib = *(const intptr_t*)b; - return ia - ib; + const intptr_t ia = *(const intptr_t*)a; + const intptr_t ib = *(const intptr_t*)b; + return ia - ib; } static int bench_zix_sorted_array(size_t n_elems, - FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat) + FILE* insert_dat, + FILE* search_dat, + FILE* iter_dat, + FILE* del_dat) { - start_test("ZixSortedArray"); - - intptr_t r = 0; - ZixSortedArrayIter ti = NULL; - ZixSortedArray* t = zix_sorted_array_new(true, int_ptr_cmp, NULL, sizeof(intptr_t)); - - // Insert n_elems elements - struct timespec insert_start = bench_start(); - for (size_t i = 0; i < n_elems; ++i) { - r = unique_rand(i); - int status = zix_sorted_array_insert(t, &r, &ti); - if (status) { - return test_fail("Insert failed\n"); - } - if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) { - return test_fail("Data corrupt (saw %" PRIdPTR ", expected %zu)\n", - *(intptr_t*)zix_sorted_array_get_data(ti), r); - } - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // Search for all elements - struct timespec search_start = bench_start(); - for (size_t i = 0; i < n_elems; ++i) { - r = unique_rand(i); - if (zix_sorted_array_find(t, &r, &ti)) { - return test_fail("Find failed\n"); - } - if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) { - return test_fail("Data corrupt (saw %" PRIdPTR ", expected %zu)\n", - *(intptr_t*)zix_sorted_array_get_data(ti), r); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // Iterate over all elements - struct timespec iter_start = bench_start(); - size_t i = 0; - intptr_t last = -1; - for (ZixSortedArrayIter iter = zix_sorted_array_begin(t); - !zix_sorted_array_iter_is_end(t, iter); - iter = zix_sorted_array_iter_next(t, iter), ++i) { - r = unique_rand(i); - const intptr_t iter_data = *(intptr_t*)zix_sorted_array_get_data(iter); - if (iter_data < last) { - return test_fail("Iter corrupt (%" PRIdPTR " < %zu)\n", - iter_data, last); - } - last = iter_data; - } - fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); - - // Delete all elements - struct timespec del_start = bench_start(); - for (i = 0; i < n_elems; i++) { - r = unique_rand(i); - ZixSortedArrayIter item; - if (zix_sorted_array_find(t, &r, &item) != ZIX_STATUS_SUCCESS) { - return test_fail("Failed to find item to remove\n"); - } - if (zix_sorted_array_remove(t, item)) { - return test_fail("Error removing item\n"); - } - } - fprintf(del_dat, "\t%lf", bench_end(&del_start)); - - if (zix_sorted_array_size(t) != 0) { - return test_fail("Array is not empty after removing all items\n"); - } - - zix_sorted_array_free(t); - - return EXIT_SUCCESS; - + start_test("ZixSortedArray"); + + intptr_t r = 0; + ZixSortedArrayIter ti = NULL; + ZixSortedArray* t = + zix_sorted_array_new(true, int_ptr_cmp, NULL, sizeof(intptr_t)); + + // Insert n_elems elements + struct timespec insert_start = bench_start(); + for (size_t i = 0; i < n_elems; ++i) { + r = unique_rand(i); + int status = zix_sorted_array_insert(t, &r, &ti); + if (status) { + return test_fail("Insert failed\n"); + } + + if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) { + return test_fail("Data corrupt (saw %" PRIdPTR ", expected %zu)\n", + *(intptr_t*)zix_sorted_array_get_data(ti), + r); + } + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + // Search for all elements + struct timespec search_start = bench_start(); + for (size_t i = 0; i < n_elems; ++i) { + r = unique_rand(i); + if (zix_sorted_array_find(t, &r, &ti)) { + return test_fail("Find failed\n"); + } + + if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) { + return test_fail("Data corrupt (saw %" PRIdPTR ", expected %zu)\n", + *(intptr_t*)zix_sorted_array_get_data(ti), + r); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + // Iterate over all elements + struct timespec iter_start = bench_start(); + size_t i = 0; + intptr_t last = -1; + for (ZixSortedArrayIter iter = zix_sorted_array_begin(t); + !zix_sorted_array_iter_is_end(t, iter); + iter = zix_sorted_array_iter_next(t, iter), ++i) { + r = unique_rand(i); + const intptr_t iter_data = *(intptr_t*)zix_sorted_array_get_data(iter); + if (iter_data < last) { + return test_fail("Iter corrupt (%" PRIdPTR " < %zu)\n", iter_data, last); + } + + last = iter_data; + } + fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); + + // Delete all elements + struct timespec del_start = bench_start(); + for (i = 0; i < n_elems; i++) { + r = unique_rand(i); + ZixSortedArrayIter item; + if (zix_sorted_array_find(t, &r, &item) != ZIX_STATUS_SUCCESS) { + return test_fail("Failed to find item to remove\n"); + } + + if (zix_sorted_array_remove(t, item)) { + return test_fail("Error removing item\n"); + } + } + fprintf(del_dat, "\t%lf", bench_end(&del_start)); + + if (zix_sorted_array_size(t) != 0) { + return test_fail("Array is not empty after removing all items\n"); + } + + zix_sorted_array_free(t); + + return EXIT_SUCCESS; } -#endif // BENCH_SORTED_ARRAY +#endif // BENCH_SORTED_ARRAY static int bench_glib(size_t n_elems, - FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat) + FILE* insert_dat, + FILE* search_dat, + FILE* iter_dat, + FILE* del_dat) { - start_test("GSequence"); - - intptr_t r = 0; - GSequence* t = g_sequence_new(NULL); - - // Insert n_elems elements - struct timespec insert_start = bench_start(); - for (size_t i = 0; i < n_elems; ++i) { - r = unique_rand(i); - GSequenceIter* iter = g_sequence_insert_sorted(t, (void*)r, g_int_cmp, NULL); - if (!iter || g_sequence_iter_is_end(iter)) { - return test_fail("Failed to insert %" PRIdPTR "\n", r); - } - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // Search for all elements - struct timespec search_start = bench_start(); - for (size_t i = 0; i < n_elems; ++i) { - r = unique_rand(i); - GSequenceIter* iter = g_sequence_lookup(t, (void*)r, g_int_cmp, NULL); - if (!iter || g_sequence_iter_is_end(iter)) { - return test_fail("Failed to find %" PRIdPTR "\n", r); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // Iterate over all elements - struct timespec iter_start = bench_start(); - for (GSequenceIter* iter = g_sequence_get_begin_iter(t); - !g_sequence_iter_is_end(iter); - iter = g_sequence_iter_next(iter)) { - g_sequence_get(iter); - } - fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); - - // Delete all elements - struct timespec del_start = bench_start(); - for (size_t i = 0; i < n_elems; ++i) { - r = unique_rand(i); - GSequenceIter* iter = - g_sequence_lookup(t, (void*)r, g_int_cmp, NULL); - if (!iter || g_sequence_iter_is_end(iter)) { - return test_fail("Failed to remove %" PRIdPTR "\n", r); - } - g_sequence_remove(iter); - } - fprintf(del_dat, "\t%lf", bench_end(&del_start)); - - g_sequence_free(t); - - return EXIT_SUCCESS; + start_test("GSequence"); + + intptr_t r = 0; + GSequence* t = g_sequence_new(NULL); + + // Insert n_elems elements + struct timespec insert_start = bench_start(); + for (size_t i = 0; i < n_elems; ++i) { + r = unique_rand(i); + GSequenceIter* iter = + g_sequence_insert_sorted(t, (void*)r, g_int_cmp, NULL); + if (!iter || g_sequence_iter_is_end(iter)) { + return test_fail("Failed to insert %" PRIdPTR "\n", r); + } + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + // Search for all elements + struct timespec search_start = bench_start(); + for (size_t i = 0; i < n_elems; ++i) { + r = unique_rand(i); + GSequenceIter* iter = g_sequence_lookup(t, (void*)r, g_int_cmp, NULL); + if (!iter || g_sequence_iter_is_end(iter)) { + return test_fail("Failed to find %" PRIdPTR "\n", r); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + // Iterate over all elements + struct timespec iter_start = bench_start(); + for (GSequenceIter* iter = g_sequence_get_begin_iter(t); + !g_sequence_iter_is_end(iter); + iter = g_sequence_iter_next(iter)) { + g_sequence_get(iter); + } + fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); + + // Delete all elements + struct timespec del_start = bench_start(); + for (size_t i = 0; i < n_elems; ++i) { + r = unique_rand(i); + GSequenceIter* iter = g_sequence_lookup(t, (void*)r, g_int_cmp, NULL); + if (!iter || g_sequence_iter_is_end(iter)) { + return test_fail("Failed to remove %" PRIdPTR "\n", r); + } + g_sequence_remove(iter); + } + fprintf(del_dat, "\t%lf", bench_end(&del_start)); + + g_sequence_free(t); + + return EXIT_SUCCESS; } int main(int argc, char** argv) { - if (argc != 3) { - fprintf(stderr, "USAGE: %s MIN_N MAX_N\n", argv[0]); - return 1; - } + if (argc != 3) { + fprintf(stderr, "USAGE: %s MIN_N MAX_N\n", argv[0]); + return 1; + } - const size_t min_n = atol(argv[1]); - const size_t max_n = atol(argv[2]); + const size_t min_n = atol(argv[1]); + const size_t max_n = atol(argv[2]); - fprintf(stderr, "Benchmarking %zu .. %zu elements\n", min_n, max_n); + fprintf(stderr, "Benchmarking %zu .. %zu elements\n", min_n, max_n); #define HEADER "# n\tZixTree\tZixBTree\tGSequence\n" - FILE* insert_dat = fopen("tree_insert.txt", "w"); - FILE* search_dat = fopen("tree_search.txt", "w"); - FILE* iter_dat = fopen("tree_iterate.txt", "w"); - FILE* del_dat = fopen("tree_delete.txt", "w"); - fprintf(insert_dat, HEADER); - fprintf(search_dat, HEADER); - fprintf(iter_dat, HEADER); - fprintf(del_dat, HEADER); - for (size_t n = min_n; n <= max_n; n *= 2) { - fprintf(stderr, "n = %zu\n", n); - fprintf(insert_dat, "%zu", n); - fprintf(search_dat, "%zu", n); - fprintf(iter_dat, "%zu", n); - fprintf(del_dat, "%zu", n); - bench_zix_tree(n, insert_dat, search_dat, iter_dat, del_dat); + FILE* insert_dat = fopen("tree_insert.txt", "w"); + FILE* search_dat = fopen("tree_search.txt", "w"); + FILE* iter_dat = fopen("tree_iterate.txt", "w"); + FILE* del_dat = fopen("tree_delete.txt", "w"); + fprintf(insert_dat, HEADER); + fprintf(search_dat, HEADER); + fprintf(iter_dat, HEADER); + fprintf(del_dat, HEADER); + for (size_t n = min_n; n <= max_n; n *= 2) { + fprintf(stderr, "n = %zu\n", n); + fprintf(insert_dat, "%zu", n); + fprintf(search_dat, "%zu", n); + fprintf(iter_dat, "%zu", n); + fprintf(del_dat, "%zu", n); + bench_zix_tree(n, insert_dat, search_dat, iter_dat, del_dat); #ifdef BENCH_SORTED_ARRAY - bench_zix_sorted_array(n, insert_dat, search_dat, iter_dat, del_dat); + bench_zix_sorted_array(n, insert_dat, search_dat, iter_dat, del_dat); #endif - bench_zix_btree(n, insert_dat, search_dat, iter_dat, del_dat); - bench_glib(n, insert_dat, search_dat, iter_dat, del_dat); - fprintf(insert_dat, "\n"); - fprintf(search_dat, "\n"); - fprintf(iter_dat, "\n"); - fprintf(del_dat, "\n"); - } - fclose(insert_dat); - fclose(search_dat); - fclose(iter_dat); - fclose(del_dat); - - fprintf(stderr, "Wrote tree_insert.txt tree_search.txt tree_iterate.txt tree_del.txt\n"); - - return EXIT_SUCCESS; + bench_zix_btree(n, insert_dat, search_dat, iter_dat, del_dat); + bench_glib(n, insert_dat, search_dat, iter_dat, del_dat); + fprintf(insert_dat, "\n"); + fprintf(search_dat, "\n"); + fprintf(iter_dat, "\n"); + fprintf(del_dat, "\n"); + } + fclose(insert_dat); + fclose(search_dat); + fclose(iter_dat); + fclose(del_dat); + + fprintf( + stderr, + "Wrote tree_insert.txt tree_search.txt tree_iterate.txt tree_del.txt\n"); + + return EXIT_SUCCESS; } diff --git a/test/bitset_test.c b/test/bitset_test.c index 8fa610f..5482f1b 100644 --- a/test/bitset_test.c +++ b/test/bitset_test.c @@ -20,7 +20,7 @@ #include <stdarg.h> #include <stdio.h> -#define N_BITS 256 +#define N_BITS 256 #define N_ELEMS (ZIX_BITSET_ELEMS(N_BITS)) #define MIN(a, b) (((a) < (b)) ? (a) : (b)) @@ -29,64 +29,64 @@ ZIX_LOG_FUNC(1, 2) static int test_fail(const char* fmt, ...) { - va_list args; - va_start(args, fmt); - fprintf(stderr, "error: "); - vfprintf(stderr, fmt, args); - va_end(args); - return 1; + va_list args; + va_start(args, fmt); + fprintf(stderr, "error: "); + vfprintf(stderr, fmt, args); + va_end(args); + return 1; } int main(void) { - ZixBitset b[N_ELEMS]; - ZixBitsetTally t[N_ELEMS]; - - zix_bitset_clear(b, t, N_BITS); - if (zix_bitset_count_up_to(b, t, N_BITS) != 0) { - return test_fail("Cleared bitset has non-zero count\n"); - } - - for (size_t i = 0; i < N_BITS; ++i) { - zix_bitset_set(b, t, i); - const size_t count = zix_bitset_count_up_to(b, t, N_BITS); - if (count != i + 1) { - return test_fail("Count %zu != %zu\n", count, i + 1); - } - - if (!zix_bitset_get(b, i)) { - return test_fail("Bit %zu is not set\n", i); - } - } - - for (size_t i = 0; i <= N_BITS; ++i) { - const size_t count = zix_bitset_count_up_to(b, t, i); - if (count != i) { - return test_fail("Count to %zu is %zu != %zu\n", i, count, i); - } - } - - for (size_t i = 0; i <= N_BITS; ++i) { - if (i < N_BITS) { - zix_bitset_reset(b, t, i); - } - const size_t count = zix_bitset_count_up_to(b, t, i); - if (count != 0) { - return test_fail("Count to %zu is %zu != %d\n", i, count, 0); - } - } - - zix_bitset_clear(b, t, N_BITS); - for (size_t i = 0; i < N_BITS; i += 2) { - zix_bitset_set(b, t, i); - - const size_t count = zix_bitset_count_up_to(b, t, i + 1); - const size_t result = MIN(N_BITS / 2, i / 2 + 1); - if (count != result) { - return test_fail("Count to %zu is %zu != %zu\n", i, count, result); - } - } - - return 0; + ZixBitset b[N_ELEMS]; + ZixBitsetTally t[N_ELEMS]; + + zix_bitset_clear(b, t, N_BITS); + if (zix_bitset_count_up_to(b, t, N_BITS) != 0) { + return test_fail("Cleared bitset has non-zero count\n"); + } + + for (size_t i = 0; i < N_BITS; ++i) { + zix_bitset_set(b, t, i); + const size_t count = zix_bitset_count_up_to(b, t, N_BITS); + if (count != i + 1) { + return test_fail("Count %zu != %zu\n", count, i + 1); + } + + if (!zix_bitset_get(b, i)) { + return test_fail("Bit %zu is not set\n", i); + } + } + + for (size_t i = 0; i <= N_BITS; ++i) { + const size_t count = zix_bitset_count_up_to(b, t, i); + if (count != i) { + return test_fail("Count to %zu is %zu != %zu\n", i, count, i); + } + } + + for (size_t i = 0; i <= N_BITS; ++i) { + if (i < N_BITS) { + zix_bitset_reset(b, t, i); + } + const size_t count = zix_bitset_count_up_to(b, t, i); + if (count != 0) { + return test_fail("Count to %zu is %zu != %d\n", i, count, 0); + } + } + + zix_bitset_clear(b, t, N_BITS); + for (size_t i = 0; i < N_BITS; i += 2) { + zix_bitset_set(b, t, i); + + const size_t count = zix_bitset_count_up_to(b, t, i + 1); + const size_t result = MIN(N_BITS / 2, i / 2 + 1); + if (count != result) { + return test_fail("Count to %zu is %zu != %zu\n", i, count, result); + } + } + + return 0; } diff --git a/test/btree_test.c b/test/btree_test.c index 3336d91..5c32020 100644 --- a/test/btree_test.c +++ b/test/btree_test.c @@ -34,483 +34,506 @@ static bool expect_failure = false; static uintptr_t unique_rand(size_t i) { - i ^= 0x00005CA1Eu; // Juggle bits to avoid linear clumps + i ^= 0x00005CA1Eu; // Juggle bits to avoid linear clumps - // Largest prime < 2^32 which satisfies (2^32 = 3 mod 4) - static const uint32_t prime = 4294967291; - if (i >= prime) { - return i; // Values >= prime are mapped to themselves - } + // Largest prime < 2^32 which satisfies (2^32 = 3 mod 4) + static const uint32_t prime = 4294967291; + if (i >= prime) { + return i; // Values >= prime are mapped to themselves + } - const uint64_t residue = ((uint64_t)i * i) % prime; - return (i <= prime / 2) ? residue : prime - residue; + const uint64_t residue = ((uint64_t)i * i) % prime; + return (i <= prime / 2) ? residue : prime - residue; } static int int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data)) { - const uintptr_t ia = (uintptr_t)a; - const uintptr_t ib = (uintptr_t)b; + const uintptr_t ia = (uintptr_t)a; + const uintptr_t ib = (uintptr_t)b; - return ia < ib ? -1 : ia > ib ? 1 : 0; + return ia < ib ? -1 : ia > ib ? 1 : 0; } static uintptr_t ith_elem(const unsigned test_num, const size_t n_elems, const size_t i) { - switch (test_num % 3) { - case 0: return i + 1; // Increasing - case 1: return n_elems - i; // Decreasing - default: return unique_rand(i); // Pseudo-random - } + switch (test_num % 3) { + case 0: + return i + 1; // Increasing + case 1: + return n_elems - i; // Decreasing + default: + return unique_rand(i); // Pseudo-random + } } -static void destroy(void* ZIX_UNUSED(ptr)) +static void +destroy(void* ZIX_UNUSED(ptr)) { } typedef struct { - unsigned test_num; - size_t n_elems; + unsigned test_num; + size_t n_elems; } TestContext; static uintptr_t wildcard_cut(unsigned test_num, size_t n_elems) { - return ith_elem(test_num, n_elems, n_elems / 3); + return ith_elem(test_num, n_elems, n_elems / 3); } /** Wildcard comparator where 0 matches anything >= wildcard_cut(n_elems). */ static int wildcard_cmp(const void* a, const void* b, const void* user_data) { - const TestContext* ctx = (const TestContext*)user_data; - const size_t n_elems = ctx->n_elems; - const unsigned test_num = ctx->test_num; - const uintptr_t ia = (uintptr_t)a; - const uintptr_t ib = (uintptr_t)b; + const TestContext* ctx = (const TestContext*)user_data; + const size_t n_elems = ctx->n_elems; + const unsigned test_num = ctx->test_num; + const uintptr_t ia = (uintptr_t)a; + const uintptr_t ib = (uintptr_t)b; - if (ia == 0) { - if (ib >= wildcard_cut(test_num, n_elems)) { - return 0; // Wildcard match - } + if (ia == 0) { + if (ib >= wildcard_cut(test_num, n_elems)) { + return 0; // Wildcard match + } - return 1; // Wildcard a > b - } + return 1; // Wildcard a > b + } - if (ib == 0) { - if (ia >= wildcard_cut(test_num, n_elems)) { - return 0; // Wildcard match - } + if (ib == 0) { + if (ia >= wildcard_cut(test_num, n_elems)) { + return 0; // Wildcard match + } - return -1; // Wildcard b > a - } + return -1; // Wildcard b > a + } - return int_cmp(a, b, user_data); + return int_cmp(a, b, user_data); } ZIX_LOG_FUNC(2, 3) static int test_fail(ZixBTree* t, const char* fmt, ...) { - zix_btree_free(t); - if (expect_failure) { - return EXIT_SUCCESS; - } - va_list args; - va_start(args, fmt); - fprintf(stderr, "error: "); - vfprintf(stderr, fmt, args); - va_end(args); - return EXIT_FAILURE; + zix_btree_free(t); + if (expect_failure) { + return EXIT_SUCCESS; + } + va_list args; + va_start(args, fmt); + fprintf(stderr, "error: "); + vfprintf(stderr, fmt, args); + va_end(args); + return EXIT_FAILURE; } static int stress(const unsigned test_num, const size_t n_elems) { - if (n_elems == 0) { - return 0; - } - - uintptr_t r = 0; - ZixBTree* t = zix_btree_new(int_cmp, NULL, NULL); - ZixStatus st = ZIX_STATUS_SUCCESS; - - if (!t) { - return test_fail(t, "Failed to allocate tree\n"); - } - - // Ensure begin iterator is end on empty tree - ZixBTreeIter* ti = zix_btree_begin(t); - ZixBTreeIter* end = zix_btree_end(t); - if (!ti) { - return test_fail(t, "Failed to allocate iterator\n"); - } - - if (!zix_btree_iter_is_end(ti)) { - return test_fail(t, "Begin iterator on empty tree is not end\n"); - } - - if (!zix_btree_iter_equals(ti, end)) { - return test_fail(t, "Begin and end of empty tree are not equal\n"); - } - - zix_btree_iter_free(end); - zix_btree_iter_free(ti); - - if (zix_btree_iter_copy(NULL)) { - return test_fail(t, "Copy of null iterator returned non-null\n"); - } - - // Insert n_elems elements - for (size_t i = 0; i < n_elems; ++i) { - r = ith_elem(test_num, n_elems, i); - if (!zix_btree_find(t, (void*)r, &ti)) { - return test_fail(t, "%" PRIuPTR " already in tree\n", (uintptr_t)r); - } - - if ((st = zix_btree_insert(t, (void*)r))) { - return test_fail(t, "Insert %" PRIuPTR " failed (%s)\n", - (uintptr_t)r, zix_strerror(st)); - } - } - - // Ensure tree size is correct - if (zix_btree_size(t) != n_elems) { - return test_fail(t, "Tree size %zu != %zu\n", zix_btree_size(t), n_elems); - } - - // Ensure begin no longer equals end - ti = zix_btree_begin(t); - end = zix_btree_end(t); - if (zix_btree_iter_equals(ti, end)) { - return test_fail(t, "Begin and end of non-empty tree are equal\n"); - } - zix_btree_iter_free(end); - - // Ensure non-null iterator copying works - ZixBTreeIter* begin_copy = zix_btree_iter_copy(ti); - if (!zix_btree_iter_equals(ti, begin_copy)) { - return test_fail(t, "Iterator copy is not equal to original\n"); - } - zix_btree_iter_free(begin_copy); - zix_btree_iter_free(ti); - - // Search for all elements - for (size_t i = 0; i < n_elems; ++i) { - r = ith_elem(test_num, n_elems, i); - if (zix_btree_find(t, (void*)r, &ti)) { - return test_fail(t, "Find %" PRIuPTR " @ %zu failed\n", (uintptr_t)r, i); - } - - if ((uintptr_t)zix_btree_get(ti) != r) { - return test_fail(t, "Search data corrupt (%" PRIuPTR " != %" PRIuPTR ")\n", - (uintptr_t)zix_btree_get(ti), r); - } - - zix_btree_iter_free(ti); - } - - if (zix_btree_lower_bound(NULL, (void*)r, &ti) != ZIX_STATUS_BAD_ARG) { - return test_fail(t, "Lower bound on NULL tree succeeded\n"); - } - - // Find the lower bound of all elements and ensure it's exact - for (size_t i = 0; i < n_elems; ++i) { - r = ith_elem(test_num, n_elems, i); - if (zix_btree_lower_bound(t, (void*)r, &ti)) { - return test_fail(t, "Lower bound %" PRIuPTR " @ %zu failed\n", - (uintptr_t)r, i); - } - - if (zix_btree_iter_is_end(ti)) { - return test_fail(t, "Lower bound %" PRIuPTR " @ %zu hit end\n", - (uintptr_t)r, i); - } - - if ((uintptr_t)zix_btree_get(ti) != r) { - return test_fail(t, "Lower bound corrupt (%" PRIuPTR " != %" PRIuPTR "\n", - (uintptr_t)zix_btree_get(ti), r); - } - - zix_btree_iter_free(ti); - } - - // Search for elements that don't exist - for (size_t i = 0; i < n_elems; ++i) { - r = ith_elem(test_num, n_elems * 3, n_elems + i); - if (!zix_btree_find(t, (void*)r, &ti)) { - return test_fail(t, "Unexpectedly found %" PRIuPTR "\n", - (uintptr_t)r); - } - } - - // Iterate over all elements - size_t i = 0; - uintptr_t last = 0; - for (ti = zix_btree_begin(t); - !zix_btree_iter_is_end(ti); - zix_btree_iter_increment(ti), ++i) { - const uintptr_t iter_data = (uintptr_t)zix_btree_get(ti); - if (iter_data < last) { - return test_fail(t, "Iter @ %zu corrupt (%" PRIuPTR " < %" PRIuPTR ")\n", - i, iter_data, last); - } - last = iter_data; - } - zix_btree_iter_free(ti); - if (i != n_elems) { - return test_fail(t, "Iteration stopped at %zu/%zu elements\n", i, n_elems); - } - - // Insert n_elems elements again, ensuring duplicates fail - for (i = 0; i < n_elems; ++i) { - r = ith_elem(test_num, n_elems, i); - if (!zix_btree_insert(t, (void*)r)) { - return test_fail(t, "Duplicate insert succeeded\n"); - } - } - - // Search for the middle element then iterate from there - r = ith_elem(test_num, n_elems, n_elems / 2); - if (zix_btree_find(t, (void*)r, &ti)) { - return test_fail(t, "Find %" PRIuPTR " failed\n", (uintptr_t)r); - } - last = (uintptr_t)zix_btree_get(ti); - zix_btree_iter_increment(ti); - for (i = 1; !zix_btree_iter_is_end(ti); zix_btree_iter_increment(ti), ++i) { - if ((uintptr_t)zix_btree_get(ti) == last) { - return test_fail(t, "Duplicate element @ %" PRIuPTR " %" PRIuPTR "\n", i, last); - } - last = (uintptr_t)zix_btree_get(ti); - } - zix_btree_iter_free(ti); - - // Delete all elements - ZixBTreeIter* next = NULL; - for (size_t e = 0; e < n_elems; e++) { - r = ith_elem(test_num, n_elems, e); - uintptr_t removed; - if (zix_btree_remove(t, (void*)r, (void**)&removed, &next)) { - return test_fail(t, "Error removing item %" PRIuPTR "\n", - (uintptr_t)r); - } - - if (removed != r) { - return test_fail(t, - "Removed wrong item %" PRIuPTR " != %" PRIuPTR "\n", - removed, (uintptr_t)r); - } - - if (test_num == 0) { - const uintptr_t next_value = ith_elem(test_num, n_elems, e + 1); - if (!((zix_btree_iter_is_end(next) && e == n_elems - 1) || - (uintptr_t)zix_btree_get(next) == next_value)) { - return test_fail(t, - "Delete all next iterator %" PRIuPTR " != %" PRIuPTR "\n", - (uintptr_t)zix_btree_get(next), next_value); - } - } - } - zix_btree_iter_free(next); - next = NULL; - - // Ensure the tree is empty - if (zix_btree_size(t) != 0) { - return test_fail(t, "Tree size %zu != 0\n", zix_btree_size(t)); - } - - // Insert n_elems elements again (to test non-empty destruction) - for (size_t e = 0; e < n_elems; ++e) { - r = ith_elem(test_num, n_elems, e); - if (zix_btree_insert(t, (void*)r)) { - return test_fail(t, "Post-deletion insert failed\n"); - } - } - - // Delete elements that don't exist - for (size_t e = 0; e < n_elems; e++) { - r = ith_elem(test_num, n_elems * 3, n_elems + e); - uintptr_t removed; - if (!zix_btree_remove(t, (void*)r, (void**)&removed, &next)) { - return test_fail(t, "Non-existant deletion of %" PRIuPTR " succeeded\n", - (uintptr_t)r); - } - } - zix_btree_iter_free(next); - next = NULL; - - // Ensure tree size is still correct - if (zix_btree_size(t) != n_elems) { - return test_fail(t, "Tree size %zu != %zu\n", zix_btree_size(t), n_elems); - } - - // Delete some elements towards the end - for (size_t e = 0; e < n_elems / 4; e++) { - r = ith_elem(test_num, n_elems, n_elems - (n_elems / 4) + e); - uintptr_t removed; - if (zix_btree_remove(t, (void*)r, (void**)&removed, &next)) { - return test_fail(t, "Deletion of %" PRIuPTR " failed\n", (uintptr_t)r); - } - - if (removed != r) { - return test_fail(t, "Removed wrong item %" PRIuPTR " != %" PRIuPTR "\n", - removed, (uintptr_t)r); - } - - if (test_num == 0) { - const uintptr_t next_value = ith_elem(test_num, n_elems, e + 1); - if (!zix_btree_iter_is_end(next) && - (uintptr_t)zix_btree_get(next) == next_value) { - return test_fail(t, "Next iterator %" PRIuPTR " != %" PRIuPTR "\n", - (uintptr_t)zix_btree_get(next), next_value); - } - } - } - zix_btree_iter_free(next); - next = NULL; - - // Check tree size - if (zix_btree_size(t) != n_elems - (n_elems / 4)) { - return test_fail(t, "Tree size %zu != %zu\n", zix_btree_size(t), n_elems); - } - - // Delete some elements in a random order - for (size_t e = 0; e < zix_btree_size(t) / 2; e++) { - r = ith_elem(test_num, n_elems, rand() % n_elems); - uintptr_t removed; - ZixStatus rst = zix_btree_remove(t, (void*)r, (void**)&removed, &next); - if (rst != ZIX_STATUS_SUCCESS && rst != ZIX_STATUS_NOT_FOUND) { - return test_fail(t, "Error deleting %" PRIuPTR "\n", (uintptr_t)r); - } - } - zix_btree_iter_free(next); - next = NULL; - - // Delete all remaining elements via next iterator - next = zix_btree_begin(t); - uintptr_t last_value = 0; - while (!zix_btree_iter_is_end(next)) { - const uintptr_t value = (uintptr_t)zix_btree_get(next); - uintptr_t removed = 0; - if (zix_btree_remove(t, zix_btree_get(next), (void**)&removed, &next)) { - return test_fail(t, "Error removing next item %" PRIuPTR "\n", - (uintptr_t)r); - } - - if (removed != value) { - return test_fail(t, "Removed wrong next item %" PRIuPTR " != %" PRIuPTR "\n", - removed, (uintptr_t)value); - } - - if (removed < last_value) { - return test_fail(t, "Removed unordered next item %" PRIuPTR " < %" PRIuPTR "\n", - removed, (uintptr_t)value); - } - - last_value = removed; - } - assert(!next || zix_btree_size(t) == 0); - zix_btree_iter_free(next); - next = NULL; - - zix_btree_free(t); - - // Test lower_bound with wildcard comparator - - TestContext ctx = { test_num, n_elems }; - if (!(t = zix_btree_new(wildcard_cmp, &ctx, destroy))) { - return test_fail(t, "Failed to allocate tree\n"); - } - - // Insert n_elems elements - for (i = 0; i < n_elems; ++i) { - r = ith_elem(test_num, n_elems, i); - if (r != 0) { // Can't insert wildcards - if ((st = zix_btree_insert(t, (void*)r))) { - return test_fail(t, "Insert %" PRIuPTR " failed (%s)\n", - (uintptr_t)r, zix_strerror(st)); - } - } - } - - // Find lower bound of wildcard - const uintptr_t wildcard = 0; - if (zix_btree_lower_bound(t, (void*)wildcard, &ti)) { - return test_fail(t, "Lower bound failed\n"); - } - - if (zix_btree_iter_is_end(ti)) { - return test_fail(t, "Lower bound reached end\n"); - } - - // Check value - const uintptr_t iter_data = (uintptr_t)zix_btree_get(ti); - const uintptr_t cut = wildcard_cut(test_num, n_elems); - if (iter_data != cut) { - return test_fail(t, "Lower bound %" PRIuPTR " != %" PRIuPTR "\n", - iter_data, cut); - } - - if (wildcard_cmp((void*)wildcard, (void*)iter_data, &ctx)) { - return test_fail(t, "Wildcard lower bound %" PRIuPTR " != %" PRIuPTR "\n", - iter_data, cut); - } - - zix_btree_iter_free(ti); - - // Find lower bound of value past end - const uintptr_t max = (uintptr_t)-1; - if (zix_btree_lower_bound(t, (void*)max, &ti)) { - return test_fail(t, "Lower bound failed\n"); - } - - if (!zix_btree_iter_is_end(ti)) { - return test_fail(t, "Lower bound of maximum value is not end\n"); - } - - zix_btree_iter_free(ti); - zix_btree_free(t); - - return EXIT_SUCCESS; + if (n_elems == 0) { + return 0; + } + + uintptr_t r = 0; + ZixBTree* t = zix_btree_new(int_cmp, NULL, NULL); + ZixStatus st = ZIX_STATUS_SUCCESS; + + if (!t) { + return test_fail(t, "Failed to allocate tree\n"); + } + + // Ensure begin iterator is end on empty tree + ZixBTreeIter* ti = zix_btree_begin(t); + ZixBTreeIter* end = zix_btree_end(t); + if (!ti) { + return test_fail(t, "Failed to allocate iterator\n"); + } + + if (!zix_btree_iter_is_end(ti)) { + return test_fail(t, "Begin iterator on empty tree is not end\n"); + } + + if (!zix_btree_iter_equals(ti, end)) { + return test_fail(t, "Begin and end of empty tree are not equal\n"); + } + + zix_btree_iter_free(end); + zix_btree_iter_free(ti); + + if (zix_btree_iter_copy(NULL)) { + return test_fail(t, "Copy of null iterator returned non-null\n"); + } + + // Insert n_elems elements + for (size_t i = 0; i < n_elems; ++i) { + r = ith_elem(test_num, n_elems, i); + if (!zix_btree_find(t, (void*)r, &ti)) { + return test_fail(t, "%" PRIuPTR " already in tree\n", (uintptr_t)r); + } + + if ((st = zix_btree_insert(t, (void*)r))) { + return test_fail( + t, "Insert %" PRIuPTR " failed (%s)\n", (uintptr_t)r, zix_strerror(st)); + } + } + + // Ensure tree size is correct + if (zix_btree_size(t) != n_elems) { + return test_fail(t, "Tree size %zu != %zu\n", zix_btree_size(t), n_elems); + } + + // Ensure begin no longer equals end + ti = zix_btree_begin(t); + end = zix_btree_end(t); + if (zix_btree_iter_equals(ti, end)) { + return test_fail(t, "Begin and end of non-empty tree are equal\n"); + } + zix_btree_iter_free(end); + + // Ensure non-null iterator copying works + ZixBTreeIter* begin_copy = zix_btree_iter_copy(ti); + if (!zix_btree_iter_equals(ti, begin_copy)) { + return test_fail(t, "Iterator copy is not equal to original\n"); + } + zix_btree_iter_free(begin_copy); + zix_btree_iter_free(ti); + + // Search for all elements + for (size_t i = 0; i < n_elems; ++i) { + r = ith_elem(test_num, n_elems, i); + if (zix_btree_find(t, (void*)r, &ti)) { + return test_fail(t, "Find %" PRIuPTR " @ %zu failed\n", (uintptr_t)r, i); + } + + if ((uintptr_t)zix_btree_get(ti) != r) { + return test_fail(t, + "Search data corrupt (%" PRIuPTR " != %" PRIuPTR ")\n", + (uintptr_t)zix_btree_get(ti), + r); + } + + zix_btree_iter_free(ti); + } + + if (zix_btree_lower_bound(NULL, (void*)r, &ti) != ZIX_STATUS_BAD_ARG) { + return test_fail(t, "Lower bound on NULL tree succeeded\n"); + } + + // Find the lower bound of all elements and ensure it's exact + for (size_t i = 0; i < n_elems; ++i) { + r = ith_elem(test_num, n_elems, i); + if (zix_btree_lower_bound(t, (void*)r, &ti)) { + return test_fail( + t, "Lower bound %" PRIuPTR " @ %zu failed\n", (uintptr_t)r, i); + } + + if (zix_btree_iter_is_end(ti)) { + return test_fail( + t, "Lower bound %" PRIuPTR " @ %zu hit end\n", (uintptr_t)r, i); + } + + if ((uintptr_t)zix_btree_get(ti) != r) { + return test_fail(t, + "Lower bound corrupt (%" PRIuPTR " != %" PRIuPTR "\n", + (uintptr_t)zix_btree_get(ti), + r); + } + + zix_btree_iter_free(ti); + } + + // Search for elements that don't exist + for (size_t i = 0; i < n_elems; ++i) { + r = ith_elem(test_num, n_elems * 3, n_elems + i); + if (!zix_btree_find(t, (void*)r, &ti)) { + return test_fail(t, "Unexpectedly found %" PRIuPTR "\n", (uintptr_t)r); + } + } + + // Iterate over all elements + size_t i = 0; + uintptr_t last = 0; + for (ti = zix_btree_begin(t); !zix_btree_iter_is_end(ti); + zix_btree_iter_increment(ti), ++i) { + const uintptr_t iter_data = (uintptr_t)zix_btree_get(ti); + if (iter_data < last) { + return test_fail(t, + "Iter @ %zu corrupt (%" PRIuPTR " < %" PRIuPTR ")\n", + i, + iter_data, + last); + } + last = iter_data; + } + zix_btree_iter_free(ti); + if (i != n_elems) { + return test_fail(t, "Iteration stopped at %zu/%zu elements\n", i, n_elems); + } + + // Insert n_elems elements again, ensuring duplicates fail + for (i = 0; i < n_elems; ++i) { + r = ith_elem(test_num, n_elems, i); + if (!zix_btree_insert(t, (void*)r)) { + return test_fail(t, "Duplicate insert succeeded\n"); + } + } + + // Search for the middle element then iterate from there + r = ith_elem(test_num, n_elems, n_elems / 2); + if (zix_btree_find(t, (void*)r, &ti)) { + return test_fail(t, "Find %" PRIuPTR " failed\n", (uintptr_t)r); + } + last = (uintptr_t)zix_btree_get(ti); + zix_btree_iter_increment(ti); + for (i = 1; !zix_btree_iter_is_end(ti); zix_btree_iter_increment(ti), ++i) { + if ((uintptr_t)zix_btree_get(ti) == last) { + return test_fail( + t, "Duplicate element @ %" PRIuPTR " %" PRIuPTR "\n", i, last); + } + last = (uintptr_t)zix_btree_get(ti); + } + zix_btree_iter_free(ti); + + // Delete all elements + ZixBTreeIter* next = NULL; + for (size_t e = 0; e < n_elems; e++) { + r = ith_elem(test_num, n_elems, e); + uintptr_t removed; + if (zix_btree_remove(t, (void*)r, (void**)&removed, &next)) { + return test_fail(t, "Error removing item %" PRIuPTR "\n", (uintptr_t)r); + } + + if (removed != r) { + return test_fail(t, + "Removed wrong item %" PRIuPTR " != %" PRIuPTR "\n", + removed, + (uintptr_t)r); + } + + if (test_num == 0) { + const uintptr_t next_value = ith_elem(test_num, n_elems, e + 1); + if (!((zix_btree_iter_is_end(next) && e == n_elems - 1) || + (uintptr_t)zix_btree_get(next) == next_value)) { + return test_fail(t, + "Delete all next iterator %" PRIuPTR " != %" PRIuPTR + "\n", + (uintptr_t)zix_btree_get(next), + next_value); + } + } + } + zix_btree_iter_free(next); + next = NULL; + + // Ensure the tree is empty + if (zix_btree_size(t) != 0) { + return test_fail(t, "Tree size %zu != 0\n", zix_btree_size(t)); + } + + // Insert n_elems elements again (to test non-empty destruction) + for (size_t e = 0; e < n_elems; ++e) { + r = ith_elem(test_num, n_elems, e); + if (zix_btree_insert(t, (void*)r)) { + return test_fail(t, "Post-deletion insert failed\n"); + } + } + + // Delete elements that don't exist + for (size_t e = 0; e < n_elems; e++) { + r = ith_elem(test_num, n_elems * 3, n_elems + e); + uintptr_t removed; + if (!zix_btree_remove(t, (void*)r, (void**)&removed, &next)) { + return test_fail( + t, "Non-existant deletion of %" PRIuPTR " succeeded\n", (uintptr_t)r); + } + } + zix_btree_iter_free(next); + next = NULL; + + // Ensure tree size is still correct + if (zix_btree_size(t) != n_elems) { + return test_fail(t, "Tree size %zu != %zu\n", zix_btree_size(t), n_elems); + } + + // Delete some elements towards the end + for (size_t e = 0; e < n_elems / 4; e++) { + r = ith_elem(test_num, n_elems, n_elems - (n_elems / 4) + e); + uintptr_t removed; + if (zix_btree_remove(t, (void*)r, (void**)&removed, &next)) { + return test_fail(t, "Deletion of %" PRIuPTR " failed\n", (uintptr_t)r); + } + + if (removed != r) { + return test_fail(t, + "Removed wrong item %" PRIuPTR " != %" PRIuPTR "\n", + removed, + (uintptr_t)r); + } + + if (test_num == 0) { + const uintptr_t next_value = ith_elem(test_num, n_elems, e + 1); + if (!zix_btree_iter_is_end(next) && + (uintptr_t)zix_btree_get(next) == next_value) { + return test_fail(t, + "Next iterator %" PRIuPTR " != %" PRIuPTR "\n", + (uintptr_t)zix_btree_get(next), + next_value); + } + } + } + zix_btree_iter_free(next); + next = NULL; + + // Check tree size + if (zix_btree_size(t) != n_elems - (n_elems / 4)) { + return test_fail(t, "Tree size %zu != %zu\n", zix_btree_size(t), n_elems); + } + + // Delete some elements in a random order + for (size_t e = 0; e < zix_btree_size(t) / 2; e++) { + r = ith_elem(test_num, n_elems, rand() % n_elems); + uintptr_t removed; + ZixStatus rst = zix_btree_remove(t, (void*)r, (void**)&removed, &next); + if (rst != ZIX_STATUS_SUCCESS && rst != ZIX_STATUS_NOT_FOUND) { + return test_fail(t, "Error deleting %" PRIuPTR "\n", (uintptr_t)r); + } + } + zix_btree_iter_free(next); + next = NULL; + + // Delete all remaining elements via next iterator + next = zix_btree_begin(t); + uintptr_t last_value = 0; + while (!zix_btree_iter_is_end(next)) { + const uintptr_t value = (uintptr_t)zix_btree_get(next); + uintptr_t removed = 0; + if (zix_btree_remove(t, zix_btree_get(next), (void**)&removed, &next)) { + return test_fail( + t, "Error removing next item %" PRIuPTR "\n", (uintptr_t)r); + } + + if (removed != value) { + return test_fail(t, + "Removed wrong next item %" PRIuPTR " != %" PRIuPTR "\n", + removed, + (uintptr_t)value); + } + + if (removed < last_value) { + return test_fail(t, + "Removed unordered next item %" PRIuPTR " < %" PRIuPTR + "\n", + removed, + (uintptr_t)value); + } + + last_value = removed; + } + assert(!next || zix_btree_size(t) == 0); + zix_btree_iter_free(next); + next = NULL; + + zix_btree_free(t); + + // Test lower_bound with wildcard comparator + + TestContext ctx = {test_num, n_elems}; + if (!(t = zix_btree_new(wildcard_cmp, &ctx, destroy))) { + return test_fail(t, "Failed to allocate tree\n"); + } + + // Insert n_elems elements + for (i = 0; i < n_elems; ++i) { + r = ith_elem(test_num, n_elems, i); + if (r != 0) { // Can't insert wildcards + if ((st = zix_btree_insert(t, (void*)r))) { + return test_fail(t, + "Insert %" PRIuPTR " failed (%s)\n", + (uintptr_t)r, + zix_strerror(st)); + } + } + } + + // Find lower bound of wildcard + const uintptr_t wildcard = 0; + if (zix_btree_lower_bound(t, (void*)wildcard, &ti)) { + return test_fail(t, "Lower bound failed\n"); + } + + if (zix_btree_iter_is_end(ti)) { + return test_fail(t, "Lower bound reached end\n"); + } + + // Check value + const uintptr_t iter_data = (uintptr_t)zix_btree_get(ti); + const uintptr_t cut = wildcard_cut(test_num, n_elems); + if (iter_data != cut) { + return test_fail( + t, "Lower bound %" PRIuPTR " != %" PRIuPTR "\n", iter_data, cut); + } + + if (wildcard_cmp((void*)wildcard, (void*)iter_data, &ctx)) { + return test_fail( + t, "Wildcard lower bound %" PRIuPTR " != %" PRIuPTR "\n", iter_data, cut); + } + + zix_btree_iter_free(ti); + + // Find lower bound of value past end + const uintptr_t max = (uintptr_t)-1; + if (zix_btree_lower_bound(t, (void*)max, &ti)) { + return test_fail(t, "Lower bound failed\n"); + } + + if (!zix_btree_iter_is_end(ti)) { + return test_fail(t, "Lower bound of maximum value is not end\n"); + } + + zix_btree_iter_free(ti); + zix_btree_free(t); + + return EXIT_SUCCESS; } int main(int argc, char** argv) { - if (argc > 2) { - fprintf(stderr, "Usage: %s [N_ELEMS]\n", argv[0]); - return EXIT_FAILURE; - } - - const unsigned n_tests = 3; - unsigned n_elems = (argc > 1) ? (unsigned)atol(argv[1]) : 524288u; - - printf("Running %u tests with %u elements", n_tests, n_elems); - for (unsigned i = 0; i < n_tests; ++i) { - printf("."); - fflush(stdout); - if (stress(i, n_elems)) { - return EXIT_FAILURE; - } - } - printf("\n"); + if (argc > 2) { + fprintf(stderr, "Usage: %s [N_ELEMS]\n", argv[0]); + return EXIT_FAILURE; + } + + const unsigned n_tests = 3; + unsigned n_elems = (argc > 1) ? (unsigned)atol(argv[1]) : 524288u; + + printf("Running %u tests with %u elements", n_tests, n_elems); + for (unsigned i = 0; i < n_tests; ++i) { + printf("."); + fflush(stdout); + if (stress(i, n_elems)) { + return EXIT_FAILURE; + } + } + printf("\n"); #ifdef ZIX_WITH_TEST_MALLOC - const size_t total_n_allocs = test_malloc_get_n_allocs(); - const size_t fail_n_elems = 1000; - printf("Testing 0 ... %zu failed allocations\n", total_n_allocs); - expect_failure = true; - for (size_t i = 0; i < total_n_allocs; ++i) { - test_malloc_reset(i); - stress(0, fail_n_elems); - if (i > test_malloc_get_n_allocs()) { - break; - } - } - - test_malloc_reset((size_t)-1); + const size_t total_n_allocs = test_malloc_get_n_allocs(); + const size_t fail_n_elems = 1000; + printf("Testing 0 ... %zu failed allocations\n", total_n_allocs); + expect_failure = true; + for (size_t i = 0; i < total_n_allocs; ++i) { + test_malloc_reset(i); + stress(0, fail_n_elems); + if (i > test_malloc_get_n_allocs()) { + break; + } + } + + test_malloc_reset((size_t)-1); #endif - return EXIT_SUCCESS; + return EXIT_SUCCESS; } diff --git a/test/digest_test.c b/test/digest_test.c index 00a58d9..809f432 100644 --- a/test/digest_test.c +++ b/test/digest_test.c @@ -24,68 +24,68 @@ static void test_bytes(void) { - static const uint8_t data[] = {1, 2, 3, 4, 5, 6, 7, 8}; + static const uint8_t data[] = {1, 2, 3, 4, 5, 6, 7, 8}; - for (size_t offset = 0; offset < 7; ++offset) { - const size_t len = 8 - offset; + for (size_t offset = 0; offset < 7; ++offset) { + const size_t len = 8 - offset; - uint32_t d = zix_digest_start(); - for (size_t i = offset; i < 8; ++i) { - const uint32_t new_d = zix_digest_add(d, &data[i], 1); - assert(new_d != d); - d = new_d; - } + uint32_t d = zix_digest_start(); + for (size_t i = offset; i < 8; ++i) { + const uint32_t new_d = zix_digest_add(d, &data[i], 1); + assert(new_d != d); + d = new_d; + } - assert(zix_digest_add(zix_digest_start(), &data[offset], len) == d); - } + assert(zix_digest_add(zix_digest_start(), &data[offset], len) == d); + } } static void test_64(void) { - static const uint64_t data[] = {1, 2, 3, 4, 5, 6, 7, 8}; + static const uint64_t data[] = {1, 2, 3, 4, 5, 6, 7, 8}; - uint32_t d = zix_digest_start(); - for (size_t i = 0; i < 8; ++i) { - const uint32_t new_d = zix_digest_add_64(d, &data[i], sizeof(uint64_t)); - assert(new_d != d); - d = new_d; - } + uint32_t d = zix_digest_start(); + for (size_t i = 0; i < 8; ++i) { + const uint32_t new_d = zix_digest_add_64(d, &data[i], sizeof(uint64_t)); + assert(new_d != d); + d = new_d; + } - assert(zix_digest_add(zix_digest_start(), data, 8 * sizeof(uint64_t)) == d); + assert(zix_digest_add(zix_digest_start(), data, 8 * sizeof(uint64_t)) == d); } static void test_ptr(void) { - static const uint64_t pointees[] = {1, 2, 3, 4, 5, 6, 7, 8}; - - static const void* data[] = {&pointees[0], - &pointees[1], - &pointees[2], - &pointees[3], - &pointees[4], - &pointees[5], - &pointees[6], - &pointees[7], - &pointees[8]}; - - uint32_t d = zix_digest_start(); - for (size_t i = 0; i < 8; ++i) { - const uint32_t new_d = zix_digest_add_ptr(d, data[i]); - assert(new_d != d); - d = new_d; - } - - assert(zix_digest_add(zix_digest_start(), data, 8 * sizeof(void*)) == d); + static const uint64_t pointees[] = {1, 2, 3, 4, 5, 6, 7, 8}; + + static const void* data[] = {&pointees[0], + &pointees[1], + &pointees[2], + &pointees[3], + &pointees[4], + &pointees[5], + &pointees[6], + &pointees[7], + &pointees[8]}; + + uint32_t d = zix_digest_start(); + for (size_t i = 0; i < 8; ++i) { + const uint32_t new_d = zix_digest_add_ptr(d, data[i]); + assert(new_d != d); + d = new_d; + } + + assert(zix_digest_add(zix_digest_start(), data, 8 * sizeof(void*)) == d); } ZIX_PURE_FUNC int main(void) { - test_bytes(); - test_64(); - test_ptr(); + test_bytes(); + test_64(); + test_ptr(); - return 0; + return 0; } diff --git a/test/hash_test.c b/test/hash_test.c index bfddc49..b55820c 100644 --- a/test/hash_test.c +++ b/test/hash_test.c @@ -29,34 +29,34 @@ static bool expect_failure = false; static const char* strings[] = { - "one", "two", "three", "four", "five", "six", "seven", "eight", - "2one", "2two", "2three", "2four", "2five", "2six", "2seven", "2eight", - "3one", "3two", "3three", "3four", "3five", "3six", "3seven", "3eight", - "4one", "4two", "4three", "4four", "4five", "4six", "4seven", "4eight", - "5one", "5two", "5three", "5four", "5five", "5six", "5seven", "5eight", - "6one", "6two", "6three", "6four", "6five", "6six", "6seven", "6eight", - "7one", "7two", "7three", "7four", "7five", "7six", "7seven", "7eight", - "8one", "8two", "8three", "8four", "8five", "8six", "8seven", "8eight", - "9one", "9two", "9three", "9four", "9five", "9six", "9seven", "9eight", - "Aone", "Atwo", "Athree", "Afour", "Afive", "Asix", "Aseven", "Aeight", - "Bone", "Btwo", "Bthree", "Bfour", "Bfive", "Bsix", "Bseven", "Beight", - "Cone", "Ctwo", "Cthree", "Cfour", "Cfive", "Csix", "Cseven", "Ceight", - "Done", "Dtwo", "Dthree", "Dfour", "Dfive", "Dsix", "Dseven", "Deight", + "one", "two", "three", "four", "five", "six", "seven", "eight", + "2one", "2two", "2three", "2four", "2five", "2six", "2seven", "2eight", + "3one", "3two", "3three", "3four", "3five", "3six", "3seven", "3eight", + "4one", "4two", "4three", "4four", "4five", "4six", "4seven", "4eight", + "5one", "5two", "5three", "5four", "5five", "5six", "5seven", "5eight", + "6one", "6two", "6three", "6four", "6five", "6six", "6seven", "6eight", + "7one", "7two", "7three", "7four", "7five", "7six", "7seven", "7eight", + "8one", "8two", "8three", "8four", "8five", "8six", "8seven", "8eight", + "9one", "9two", "9three", "9four", "9five", "9six", "9seven", "9eight", + "Aone", "Atwo", "Athree", "Afour", "Afive", "Asix", "Aseven", "Aeight", + "Bone", "Btwo", "Bthree", "Bfour", "Bfive", "Bsix", "Bseven", "Beight", + "Cone", "Ctwo", "Cthree", "Cfour", "Cfive", "Csix", "Cseven", "Ceight", + "Done", "Dtwo", "Dthree", "Dfour", "Dfive", "Dsix", "Dseven", "Deight", }; ZIX_LOG_FUNC(1, 2) static int test_fail(const char* fmt, ...) { - if (expect_failure) { - return 0; - } - va_list args; - va_start(args, fmt); - fprintf(stderr, "error: "); - vfprintf(stderr, fmt, args); - va_end(args); - return 1; + if (expect_failure) { + return 0; + } + va_list args; + va_start(args, fmt); + fprintf(stderr, "error: "); + vfprintf(stderr, fmt, args); + va_end(args); + return 1; } static unsigned n_checked = 0; @@ -64,163 +64,161 @@ static unsigned n_checked = 0; static void check(void* value, void* ZIX_UNUSED(user_data)) { - if (strlen(*(const char*const*)value) >= 3) { - ++n_checked; - } else { - fprintf(stderr, "ERROR: %s\n", (const char*)value); - } + if (strlen(*(const char* const*)value) >= 3) { + ++n_checked; + } else { + fprintf(stderr, "ERROR: %s\n", (const char*)value); + } } static uint32_t string_ptr_hash(const void* value) { - const char* const str = *(const char* const*)value; + const char* const str = *(const char* const*)value; - return zix_digest_add(zix_digest_start(), str, strlen(str)); + return zix_digest_add(zix_digest_start(), str, strlen(str)); } static bool string_ptr_equal(const void* a, const void* b) { - return !strcmp(*(const char*const*)a, *(const char*const*)b); + return !strcmp(*(const char* const*)a, *(const char* const*)b); } static int stress(void) { - ZixHash* hash = zix_hash_new( - string_ptr_hash, string_ptr_equal, sizeof(const char*)); - if (!hash) { - return test_fail("Failed to allocate hash\n"); - } - - const size_t n_strings = sizeof(strings) / sizeof(const char*); - - // Insert each string - for (size_t i = 0; i < n_strings; ++i) { - void* inserted = NULL; - ZixStatus st = zix_hash_insert(hash, &strings[i], &inserted); - if (st) { - return test_fail("Failed to insert `%s'\n", strings[i]); - } - - if (*(const void*const*)inserted != strings[i]) { - return test_fail("Corrupt insertion %s != %s\n", - strings[i], *(const char*const*)inserted); - } - } - - // Ensure hash size is correct - if (zix_hash_size(hash) != n_strings) { - return test_fail("Hash size %zu != %zu\n", - zix_hash_size(hash), n_strings); - } - - //zix_hash_print_dot(hash, stdout); - - // Attempt to insert each string again - for (size_t i = 0; i < n_strings; ++i) { - void* inserted = NULL; - ZixStatus st = zix_hash_insert(hash, &strings[i], &inserted); - if (st != ZIX_STATUS_EXISTS) { - return test_fail("Double inserted `%s'\n", strings[i]); - } - } - - // Search for each string - for (size_t i = 0; i < n_strings; ++i) { - const char*const* match = (const char*const*)zix_hash_find( - hash, &strings[i]); - if (!match) { - return test_fail("Failed to find `%s'\n", strings[i]); - } - if (*match != strings[i]) { - return test_fail("Bad match for `%s': `%s'\n", strings[i], *match); - } - } - - // Try some false matches - const char* not_indexed[] = { - "ftp://example.org/not-there-at-all", - "http://example.org/foobar", - "http://", - "http://otherdomain.com" - }; - const size_t n_not_indexed = sizeof(not_indexed) / sizeof(char*); - for (size_t i = 0; i < n_not_indexed; ++i) { - const char*const* match = (const char*const*)zix_hash_find( - hash, ¬_indexed[i]); - if (match) { - return test_fail("Unexpectedly found `%s'\n", not_indexed[i]); - } - } - - // Remove strings - for (size_t i = 0; i < n_strings; ++i) { - // Remove string - ZixStatus st = zix_hash_remove(hash, &strings[i]); - if (st) { - return test_fail("Failed to remove `%s'\n", strings[i]); - } - - // Ensure second removal fails - st = zix_hash_remove(hash, &strings[i]); - if (st != ZIX_STATUS_NOT_FOUND) { - return test_fail("Unexpectedly removed `%s' twice\n", strings[i]); - } - - // Check to ensure remaining strings are still present - for (size_t j = i + 1; j < n_strings; ++j) { - const char*const* match = (const char*const*)zix_hash_find( - hash, &strings[j]); - if (!match) { - return test_fail("Failed to find `%s' after remove\n", strings[j]); - } - if (*match != strings[j]) { - return test_fail("Bad match for `%s' after remove\n", strings[j]); - } - } - } - - // Insert each string again (to check non-empty destruction) - for (size_t i = 0; i < n_strings; ++i) { - ZixStatus st = zix_hash_insert(hash, &strings[i], NULL); - if (st) { - return test_fail("Failed to insert `%s'\n", strings[i]); - } - } - - // Check key == value (and test zix_hash_foreach) - zix_hash_foreach(hash, check, NULL); - if (n_checked != n_strings) { - return test_fail("Check failed\n"); - } - - zix_hash_free(hash); - - return 0; + ZixHash* hash = + zix_hash_new(string_ptr_hash, string_ptr_equal, sizeof(const char*)); + if (!hash) { + return test_fail("Failed to allocate hash\n"); + } + + const size_t n_strings = sizeof(strings) / sizeof(const char*); + + // Insert each string + for (size_t i = 0; i < n_strings; ++i) { + void* inserted = NULL; + ZixStatus st = zix_hash_insert(hash, &strings[i], &inserted); + if (st) { + return test_fail("Failed to insert `%s'\n", strings[i]); + } + + if (*(const void* const*)inserted != strings[i]) { + return test_fail("Corrupt insertion %s != %s\n", + strings[i], + *(const char* const*)inserted); + } + } + + // Ensure hash size is correct + if (zix_hash_size(hash) != n_strings) { + return test_fail("Hash size %zu != %zu\n", zix_hash_size(hash), n_strings); + } + + // zix_hash_print_dot(hash, stdout); + + // Attempt to insert each string again + for (size_t i = 0; i < n_strings; ++i) { + void* inserted = NULL; + ZixStatus st = zix_hash_insert(hash, &strings[i], &inserted); + if (st != ZIX_STATUS_EXISTS) { + return test_fail("Double inserted `%s'\n", strings[i]); + } + } + + // Search for each string + for (size_t i = 0; i < n_strings; ++i) { + const char* const* match = + (const char* const*)zix_hash_find(hash, &strings[i]); + if (!match) { + return test_fail("Failed to find `%s'\n", strings[i]); + } + if (*match != strings[i]) { + return test_fail("Bad match for `%s': `%s'\n", strings[i], *match); + } + } + + // Try some false matches + const char* not_indexed[] = {"ftp://example.org/not-there-at-all", + "http://example.org/foobar", + "http://", + "http://otherdomain.com"}; + const size_t n_not_indexed = sizeof(not_indexed) / sizeof(char*); + for (size_t i = 0; i < n_not_indexed; ++i) { + const char* const* match = + (const char* const*)zix_hash_find(hash, ¬_indexed[i]); + if (match) { + return test_fail("Unexpectedly found `%s'\n", not_indexed[i]); + } + } + + // Remove strings + for (size_t i = 0; i < n_strings; ++i) { + // Remove string + ZixStatus st = zix_hash_remove(hash, &strings[i]); + if (st) { + return test_fail("Failed to remove `%s'\n", strings[i]); + } + + // Ensure second removal fails + st = zix_hash_remove(hash, &strings[i]); + if (st != ZIX_STATUS_NOT_FOUND) { + return test_fail("Unexpectedly removed `%s' twice\n", strings[i]); + } + + // Check to ensure remaining strings are still present + for (size_t j = i + 1; j < n_strings; ++j) { + const char* const* match = + (const char* const*)zix_hash_find(hash, &strings[j]); + if (!match) { + return test_fail("Failed to find `%s' after remove\n", strings[j]); + } + if (*match != strings[j]) { + return test_fail("Bad match for `%s' after remove\n", strings[j]); + } + } + } + + // Insert each string again (to check non-empty destruction) + for (size_t i = 0; i < n_strings; ++i) { + ZixStatus st = zix_hash_insert(hash, &strings[i], NULL); + if (st) { + return test_fail("Failed to insert `%s'\n", strings[i]); + } + } + + // Check key == value (and test zix_hash_foreach) + zix_hash_foreach(hash, check, NULL); + if (n_checked != n_strings) { + return test_fail("Check failed\n"); + } + + zix_hash_free(hash); + + return 0; } int main(void) { - zix_hash_free(NULL); + zix_hash_free(NULL); - if (stress()) { - return 1; - } + if (stress()) { + return 1; + } #ifdef ZIX_WITH_TEST_MALLOC - const size_t total_n_allocs = test_malloc_get_n_allocs(); - printf("Testing 0 ... %zu failed allocations\n", total_n_allocs); - expect_failure = true; - for (size_t i = 0; i < total_n_allocs; ++i) { - test_malloc_reset(i); - stress(); - } - - test_malloc_reset((size_t)-1); + const size_t total_n_allocs = test_malloc_get_n_allocs(); + printf("Testing 0 ... %zu failed allocations\n", total_n_allocs); + expect_failure = true; + for (size_t i = 0; i < total_n_allocs; ++i) { + test_malloc_reset(i); + stress(); + } + + test_malloc_reset((size_t)-1); #endif - return 0; + return 0; } diff --git a/test/inline_test.c b/test/inline_test.c index 75c43d0..b07f28a 100644 --- a/test/inline_test.c +++ b/test/inline_test.c @@ -25,7 +25,7 @@ ZIX_CONST_FUNC int main(void) { - zix_hash_free(NULL); - zix_tree_free(NULL); - return 0; + zix_hash_free(NULL); + zix_tree_free(NULL); + return 0; } diff --git a/test/ring_test.c b/test/ring_test.c index 092606b..915d099 100644 --- a/test/ring_test.c +++ b/test/ring_test.c @@ -35,200 +35,202 @@ ZIX_LOG_FUNC(1, 2) static int failure(const char* fmt, ...) { - va_list args; - va_start(args, fmt); - fprintf(stderr, "error: "); - vfprintf(stderr, fmt, args); - va_end(args); - return 1; + va_list args; + va_start(args, fmt); + fprintf(stderr, "error: "); + vfprintf(stderr, fmt, args); + va_end(args); + return 1; } static int gen_msg(int* msg, int start) { - for (int i = 0; i < MSG_SIZE; ++i) { - msg[i] = start; - start = (start + 1) % INT_MAX; - } - return start; + for (int i = 0; i < MSG_SIZE; ++i) { + msg[i] = start; + start = (start + 1) % INT_MAX; + } + return start; } static int cmp_msg(int* msg1, int* msg2) { - for (int i = 0; i < MSG_SIZE; ++i) { - if (msg1[i] != msg2[i]) { - return !failure("%d != %d @ %d\n", msg1[i], msg2[i], i); - } - } + for (int i = 0; i < MSG_SIZE; ++i) { + if (msg1[i] != msg2[i]) { + return !failure("%d != %d @ %d\n", msg1[i], msg2[i], i); + } + } - return 1; + return 1; } static void* reader(void* ZIX_UNUSED(arg)) { - printf("Reader starting\n"); - - int ref_msg[MSG_SIZE]; // Reference generated for comparison - int read_msg[MSG_SIZE]; // Read from ring - unsigned count = 0; - int start = gen_msg(ref_msg, 0); - for (unsigned i = 0; i < n_writes; ++i) { - if (zix_ring_read_space(ring) >= MSG_SIZE * sizeof(int)) { - if (zix_ring_read(ring, read_msg, MSG_SIZE * sizeof(int))) { - if (!cmp_msg(ref_msg, read_msg)) { - printf("FAIL: Message %u is corrupt\n", count); - read_error = true; - return NULL; - } - start = gen_msg(ref_msg, start); - ++count; - } - } - } - - printf("Reader finished\n"); - return NULL; + printf("Reader starting\n"); + + int ref_msg[MSG_SIZE]; // Reference generated for comparison + int read_msg[MSG_SIZE]; // Read from ring + unsigned count = 0; + int start = gen_msg(ref_msg, 0); + for (unsigned i = 0; i < n_writes; ++i) { + if (zix_ring_read_space(ring) >= MSG_SIZE * sizeof(int)) { + if (zix_ring_read(ring, read_msg, MSG_SIZE * sizeof(int))) { + if (!cmp_msg(ref_msg, read_msg)) { + printf("FAIL: Message %u is corrupt\n", count); + read_error = true; + return NULL; + } + start = gen_msg(ref_msg, start); + ++count; + } + } + } + + printf("Reader finished\n"); + return NULL; } static void* writer(void* ZIX_UNUSED(arg)) { - printf("Writer starting\n"); - - int write_msg[MSG_SIZE]; // Written to ring - int start = gen_msg(write_msg, 0); - for (unsigned i = 0; i < n_writes; ++i) { - if (zix_ring_write_space(ring) >= MSG_SIZE * sizeof(int)) { - if (zix_ring_write(ring, write_msg, MSG_SIZE * sizeof(int))) { - start = gen_msg(write_msg, start); - } - } - } - - printf("Writer finished\n"); - return NULL; + printf("Writer starting\n"); + + int write_msg[MSG_SIZE]; // Written to ring + int start = gen_msg(write_msg, 0); + for (unsigned i = 0; i < n_writes; ++i) { + if (zix_ring_write_space(ring) >= MSG_SIZE * sizeof(int)) { + if (zix_ring_write(ring, write_msg, MSG_SIZE * sizeof(int))) { + start = gen_msg(write_msg, start); + } + } + } + + printf("Writer finished\n"); + return NULL; } int main(int argc, char** argv) { - if (argc > 1 && argv[1][0] == '-') { - printf("Usage: %s SIZE N_WRITES\n", argv[0]); - return 1; - } - - unsigned size = 1024; - if (argc > 1) { - size = (unsigned)atoi(argv[1]); - } - - n_writes = size * 1024; - if (argc > 2) { - n_writes = (unsigned)atoi(argv[2]); - } - - printf("Testing %u writes of %d ints to a %u int ring...\n", - n_writes, MSG_SIZE, size); - - ring = zix_ring_new(size); - if (zix_ring_read_space(ring) != 0) { - return failure("New ring is not empty\n"); - } - if (zix_ring_write_space(ring) != zix_ring_capacity(ring)) { - return failure("New ring write space != capacity\n"); - } - - zix_ring_mlock(ring); - - ZixThread reader_thread; - if (zix_thread_create(&reader_thread, MSG_SIZE * 4, reader, NULL)) { - return failure("Failed to create reader thread\n"); - } - - ZixThread writer_thread; - if (zix_thread_create(&writer_thread, MSG_SIZE * 4, writer, NULL)) { - return failure("Failed to create writer thread\n"); - } - - zix_thread_join(reader_thread, NULL); - zix_thread_join(writer_thread, NULL); - - if (read_error) { - return failure("Read error\n"); - } - - zix_ring_reset(ring); - if (zix_ring_read_space(ring) > 0) { - return failure("Reset did not empty ring.\n"); - } - if (zix_ring_write_space(ring) != zix_ring_capacity(ring)) { - return failure("Empty write space != capacity\n"); - } - - zix_ring_write(ring, "a", 1); - zix_ring_write(ring, "b", 1); - - char buf; - uint32_t n = zix_ring_peek(ring, &buf, 1); - if (n != 1) { - return failure("Peek n (%u) != 1\n", n); - } - if (buf != 'a') { - return failure("Peek error: '%c' != 'a'\n", buf); - } - - n = zix_ring_skip(ring, 1); - if (n != 1) { - return failure("Skip n (%u) != 1\n", n); - } - - if (zix_ring_read_space(ring) != 1) { - return failure("Read space %u != 1\n", zix_ring_read_space(ring)); - } - - n = zix_ring_read(ring, &buf, 1); - if (n != 1) { - return failure("Peek n (%u) != 1\n", n); - } - if (buf != 'b') { - return failure("Peek error: '%c' != 'b'\n", buf); - } - - if (zix_ring_read_space(ring) != 0) { - return failure("Read space %u != 0\n", zix_ring_read_space(ring)); - } - - n = zix_ring_peek(ring, &buf, 1); - if (n > 0) { - return failure("Successful underrun peak\n"); - } - - n = zix_ring_read(ring, &buf, 1); - if (n > 0) { - return failure("Successful underrun read\n"); - } - - n = zix_ring_skip(ring, 1); - if (n > 0) { - return failure("Successful underrun read\n"); - } - - char* big_buf = (char*)calloc(size, 1); - n = zix_ring_write(ring, big_buf, size - 1); - if (n != (uint32_t)size - 1) { - free(big_buf); - return failure("Maximum size write failed (wrote %u)\n", n); - } - - n = zix_ring_write(ring, big_buf, size); - if (n != 0) { - free(big_buf); - return failure("Successful overrun write (size %u)\n", n); - } - - free(big_buf); - zix_ring_free(ring); - return 0; + if (argc > 1 && argv[1][0] == '-') { + printf("Usage: %s SIZE N_WRITES\n", argv[0]); + return 1; + } + + unsigned size = 1024; + if (argc > 1) { + size = (unsigned)atoi(argv[1]); + } + + n_writes = size * 1024; + if (argc > 2) { + n_writes = (unsigned)atoi(argv[2]); + } + + printf("Testing %u writes of %d ints to a %u int ring...\n", + n_writes, + MSG_SIZE, + size); + + ring = zix_ring_new(size); + if (zix_ring_read_space(ring) != 0) { + return failure("New ring is not empty\n"); + } + if (zix_ring_write_space(ring) != zix_ring_capacity(ring)) { + return failure("New ring write space != capacity\n"); + } + + zix_ring_mlock(ring); + + ZixThread reader_thread; + if (zix_thread_create(&reader_thread, MSG_SIZE * 4, reader, NULL)) { + return failure("Failed to create reader thread\n"); + } + + ZixThread writer_thread; + if (zix_thread_create(&writer_thread, MSG_SIZE * 4, writer, NULL)) { + return failure("Failed to create writer thread\n"); + } + + zix_thread_join(reader_thread, NULL); + zix_thread_join(writer_thread, NULL); + + if (read_error) { + return failure("Read error\n"); + } + + zix_ring_reset(ring); + if (zix_ring_read_space(ring) > 0) { + return failure("Reset did not empty ring.\n"); + } + if (zix_ring_write_space(ring) != zix_ring_capacity(ring)) { + return failure("Empty write space != capacity\n"); + } + + zix_ring_write(ring, "a", 1); + zix_ring_write(ring, "b", 1); + + char buf; + uint32_t n = zix_ring_peek(ring, &buf, 1); + if (n != 1) { + return failure("Peek n (%u) != 1\n", n); + } + if (buf != 'a') { + return failure("Peek error: '%c' != 'a'\n", buf); + } + + n = zix_ring_skip(ring, 1); + if (n != 1) { + return failure("Skip n (%u) != 1\n", n); + } + + if (zix_ring_read_space(ring) != 1) { + return failure("Read space %u != 1\n", zix_ring_read_space(ring)); + } + + n = zix_ring_read(ring, &buf, 1); + if (n != 1) { + return failure("Peek n (%u) != 1\n", n); + } + if (buf != 'b') { + return failure("Peek error: '%c' != 'b'\n", buf); + } + + if (zix_ring_read_space(ring) != 0) { + return failure("Read space %u != 0\n", zix_ring_read_space(ring)); + } + + n = zix_ring_peek(ring, &buf, 1); + if (n > 0) { + return failure("Successful underrun peak\n"); + } + + n = zix_ring_read(ring, &buf, 1); + if (n > 0) { + return failure("Successful underrun read\n"); + } + + n = zix_ring_skip(ring, 1); + if (n > 0) { + return failure("Successful underrun read\n"); + } + + char* big_buf = (char*)calloc(size, 1); + n = zix_ring_write(ring, big_buf, size - 1); + if (n != (uint32_t)size - 1) { + free(big_buf); + return failure("Maximum size write failed (wrote %u)\n", n); + } + + n = zix_ring_write(ring, big_buf, size); + if (n != 0) { + free(big_buf); + return failure("Successful overrun write (size %u)\n", n); + } + + free(big_buf); + zix_ring_free(ring); + return 0; } diff --git a/test/sem_test.c b/test/sem_test.c index 7ff9b08..5db7c08 100644 --- a/test/sem_test.c +++ b/test/sem_test.c @@ -26,63 +26,63 @@ static unsigned n_signals = 1024; static void* reader(void* ZIX_UNUSED(arg)) { - printf("Reader starting\n"); + printf("Reader starting\n"); - for (unsigned i = 0; i < n_signals; ++i) { - zix_sem_wait(&sem); - } + for (unsigned i = 0; i < n_signals; ++i) { + zix_sem_wait(&sem); + } - printf("Reader finished\n"); - return NULL; + printf("Reader finished\n"); + return NULL; } static void* writer(void* ZIX_UNUSED(arg)) { - printf("Writer starting\n"); + printf("Writer starting\n"); - for (unsigned i = 0; i < n_signals; ++i) { - zix_sem_post(&sem); - } + for (unsigned i = 0; i < n_signals; ++i) { + zix_sem_post(&sem); + } - printf("Writer finished\n"); - return NULL; + printf("Writer finished\n"); + return NULL; } int main(int argc, char** argv) { - if (argc > 2) { - printf("Usage: %s N_SIGNALS\n", argv[0]); - return 1; - } - - if (argc > 1) { - n_signals = (unsigned)atoi(argv[1]); - } - - printf("Testing %u signals...\n", n_signals); - - if (zix_sem_init(&sem, 0)) { - fprintf(stderr, "Failed to create semaphore.\n"); - return 1; - } - - ZixThread reader_thread; - if (zix_thread_create(&reader_thread, 128, reader, NULL)) { - fprintf(stderr, "Failed to create reader thread\n"); - return 1; - } - - ZixThread writer_thread; - if (zix_thread_create(&writer_thread, 128, writer, NULL)) { - fprintf(stderr, "Failed to create writer thread\n"); - return 1; - } - - zix_thread_join(reader_thread, NULL); - zix_thread_join(writer_thread, NULL); - - zix_sem_destroy(&sem); - return 0; + if (argc > 2) { + printf("Usage: %s N_SIGNALS\n", argv[0]); + return 1; + } + + if (argc > 1) { + n_signals = (unsigned)atoi(argv[1]); + } + + printf("Testing %u signals...\n", n_signals); + + if (zix_sem_init(&sem, 0)) { + fprintf(stderr, "Failed to create semaphore.\n"); + return 1; + } + + ZixThread reader_thread; + if (zix_thread_create(&reader_thread, 128, reader, NULL)) { + fprintf(stderr, "Failed to create reader thread\n"); + return 1; + } + + ZixThread writer_thread; + if (zix_thread_create(&writer_thread, 128, writer, NULL)) { + fprintf(stderr, "Failed to create writer thread\n"); + return 1; + } + + zix_thread_join(reader_thread, NULL); + zix_thread_join(writer_thread, NULL); + + zix_sem_destroy(&sem); + return 0; } diff --git a/test/sorted_array_test.c b/test/sorted_array_test.c index db7c1d0..d991784 100644 --- a/test/sorted_array_test.c +++ b/test/sorted_array_test.c @@ -29,149 +29,155 @@ static unsigned seed = 1; static int int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data)) { - const intptr_t ia = *(const intptr_t*)a; - const intptr_t ib = *(const intptr_t*)b; + const intptr_t ia = *(const intptr_t*)a; + const intptr_t ib = *(const intptr_t*)b; - return ia < ib ? -1 : ia > ib ? 1 : 0; + return ia < ib ? -1 : ia > ib ? 1 : 0; } static intptr_t ith_elem(unsigned test_num, unsigned n_elems, unsigned i) { - switch (test_num % 3) { - case 0: - return i; // Increasing (worst case) - case 1: - return n_elems - i; // Decreasing (worse case) - case 2: - default: - return rand() % 100; // Random - } + switch (test_num % 3) { + case 0: + return i; // Increasing (worst case) + case 1: + return n_elems - i; // Decreasing (worse case) + case 2: + default: + return rand() % 100; // Random + } } static int test_fail(void) { - return EXIT_FAILURE; + return EXIT_FAILURE; } static int stress(unsigned test_num, unsigned n_elems) { - intptr_t r; - ZixSortedArrayIter ti; - - ZixSortedArray* t = zix_sorted_array_new(true, int_cmp, NULL, sizeof(intptr_t)); - - srand(seed); - - // Insert n_elems elements - for (unsigned i = 0; i < n_elems; ++i) { - r = ith_elem(test_num, n_elems, i); - int status = zix_sorted_array_insert(t, &r, &ti); - if (status) { - fprintf(stderr, "Insert failed\n"); - return test_fail(); - } - if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) { - fprintf(stderr, "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n", - *(intptr_t*)zix_sorted_array_get_data(ti), r); - return test_fail(); - } - } - - srand(seed); - - // Search for all elements - for (unsigned i = 0; i < n_elems; ++i) { - r = ith_elem(test_num, n_elems, i); - if (zix_sorted_array_find(t, &r, &ti)) { - fprintf(stderr, "Find failed\n"); - return test_fail(); - } - if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) { - fprintf(stderr, "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n", - *(intptr_t*)zix_sorted_array_get_data(ti), r); - return test_fail(); - } - } - - srand(seed); - - // Iterate over all elements - unsigned i = 0; - intptr_t last = -1; - for (ZixSortedArrayIter iter = zix_sorted_array_begin(t); - !zix_sorted_array_iter_is_end(t, iter); - iter = zix_sorted_array_iter_next(t, iter), ++i) { - r = ith_elem(test_num, n_elems, i); - const intptr_t iter_data = *(intptr_t*)zix_sorted_array_get_data(iter); - if (iter_data < last) { - fprintf(stderr, "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n", - iter_data, last); - return test_fail(); - } - last = iter_data; - } - - srand(seed); - - // Delete all elements - for (unsigned e = 0; e < n_elems; e++) { - r = ith_elem(test_num, n_elems, e); - ZixSortedArrayIter item; - if (zix_sorted_array_find(t, &r, &item) != ZIX_STATUS_SUCCESS) { - fprintf(stderr, "Failed to find item to remove\n"); - return test_fail(); - } - if (zix_sorted_array_remove(t, item)) { - fprintf(stderr, "Error removing item\n"); - } - } - - if (zix_sorted_array_size(t) != 0) { - fprintf(stderr, "Array is not empty after removing all items\n"); - return test_fail(); - } - - zix_sorted_array_free(t); - - return EXIT_SUCCESS; + intptr_t r; + ZixSortedArrayIter ti; + + ZixSortedArray* t = + zix_sorted_array_new(true, int_cmp, NULL, sizeof(intptr_t)); + + srand(seed); + + // Insert n_elems elements + for (unsigned i = 0; i < n_elems; ++i) { + r = ith_elem(test_num, n_elems, i); + int status = zix_sorted_array_insert(t, &r, &ti); + if (status) { + fprintf(stderr, "Insert failed\n"); + return test_fail(); + } + if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) { + fprintf(stderr, + "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n", + *(intptr_t*)zix_sorted_array_get_data(ti), + r); + return test_fail(); + } + } + + srand(seed); + + // Search for all elements + for (unsigned i = 0; i < n_elems; ++i) { + r = ith_elem(test_num, n_elems, i); + if (zix_sorted_array_find(t, &r, &ti)) { + fprintf(stderr, "Find failed\n"); + return test_fail(); + } + if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) { + fprintf(stderr, + "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n", + *(intptr_t*)zix_sorted_array_get_data(ti), + r); + return test_fail(); + } + } + + srand(seed); + + // Iterate over all elements + unsigned i = 0; + intptr_t last = -1; + for (ZixSortedArrayIter iter = zix_sorted_array_begin(t); + !zix_sorted_array_iter_is_end(t, iter); + iter = zix_sorted_array_iter_next(t, iter), ++i) { + r = ith_elem(test_num, n_elems, i); + const intptr_t iter_data = *(intptr_t*)zix_sorted_array_get_data(iter); + if (iter_data < last) { + fprintf(stderr, + "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n", + iter_data, + last); + return test_fail(); + } + last = iter_data; + } + + srand(seed); + + // Delete all elements + for (unsigned e = 0; e < n_elems; e++) { + r = ith_elem(test_num, n_elems, e); + ZixSortedArrayIter item; + if (zix_sorted_array_find(t, &r, &item) != ZIX_STATUS_SUCCESS) { + fprintf(stderr, "Failed to find item to remove\n"); + return test_fail(); + } + if (zix_sorted_array_remove(t, item)) { + fprintf(stderr, "Error removing item\n"); + } + } + + if (zix_sorted_array_size(t) != 0) { + fprintf(stderr, "Array is not empty after removing all items\n"); + return test_fail(); + } + + zix_sorted_array_free(t); + + return EXIT_SUCCESS; } int main(int argc, char** argv) { - const unsigned n_tests = 3; - unsigned n_elems = 0; - - if (argc == 1) { - n_elems = 4096; - } else { - n_elems = (unsigned)atol(argv[1]); - if (argc > 2) { - seed = (unsigned)atol(argv[2]); - } else { - seed = (unsigned)time(NULL); - } - } - - if (n_elems == 0) { - fprintf(stderr, "USAGE: %s [N_ELEMS]\n", argv[0]); - return 1; - } - - printf("Running %u tests with %u elements (seed %u)", - n_tests, n_elems, seed); - - for (unsigned i = 0; i < n_tests; ++i) { - printf("."); - fflush(stdout); - if (stress(i, n_elems)) { - fprintf(stderr, "FAIL: Random seed %u\n", seed); - return test_fail(); - } - } - printf("\n"); - return EXIT_SUCCESS; + const unsigned n_tests = 3; + unsigned n_elems = 0; + + if (argc == 1) { + n_elems = 4096; + } else { + n_elems = (unsigned)atol(argv[1]); + if (argc > 2) { + seed = (unsigned)atol(argv[2]); + } else { + seed = (unsigned)time(NULL); + } + } + + if (n_elems == 0) { + fprintf(stderr, "USAGE: %s [N_ELEMS]\n", argv[0]); + return 1; + } + + printf("Running %u tests with %u elements (seed %u)", n_tests, n_elems, seed); + + for (unsigned i = 0; i < n_tests; ++i) { + printf("."); + fflush(stdout); + if (stress(i, n_elems)) { + fprintf(stderr, "FAIL: Random seed %u\n", seed); + return test_fail(); + } + } + printf("\n"); + return EXIT_SUCCESS; } diff --git a/test/strindex_test.c b/test/strindex_test.c index 1dcd062..d19d77e 100644 --- a/test/strindex_test.c +++ b/test/strindex_test.c @@ -25,37 +25,35 @@ ZIX_LOG_FUNC(1, 2) static int test_fail(const char* fmt, ...) { - va_list args; - va_start(args, fmt); - fprintf(stderr, "error: "); - vfprintf(stderr, fmt, args); - va_end(args); - return 1; + va_list args; + va_start(args, fmt); + fprintf(stderr, "error: "); + vfprintf(stderr, fmt, args); + va_end(args); + return 1; } int main(void) { - const char* str = "BANANA"; - const size_t str_len = strlen(str); - ZixStrindex* strindex = zix_strindex_new(str); - - for (size_t l = 1; l <= str_len; ++l) { - for (size_t i = 0; i < str_len - l; ++i) { - char* match = NULL; - ZixStatus ret = zix_strindex_find(strindex, str + i, &match); - if (ret) { - return test_fail("No match for substring at %zu length %zu\n", - i, l); - } - - if (strncmp(str + i, match, l)) { - return test_fail("Bad match for substring at %zu length %zu\n", - i, l); - } - } - } - - zix_strindex_free(strindex); - return 0; + const char* str = "BANANA"; + const size_t str_len = strlen(str); + ZixStrindex* strindex = zix_strindex_new(str); + + for (size_t l = 1; l <= str_len; ++l) { + for (size_t i = 0; i < str_len - l; ++i) { + char* match = NULL; + ZixStatus ret = zix_strindex_find(strindex, str + i, &match); + if (ret) { + return test_fail("No match for substring at %zu length %zu\n", i, l); + } + + if (strncmp(str + i, match, l)) { + return test_fail("Bad match for substring at %zu length %zu\n", i, l); + } + } + } + + zix_strindex_free(strindex); + return 0; } diff --git a/test/test_malloc.c b/test/test_malloc.c index 1138502..971d583 100644 --- a/test/test_malloc.c +++ b/test/test_malloc.c @@ -15,7 +15,7 @@ */ #ifndef __APPLE__ -#define _GNU_SOURCE +# define _GNU_SOURCE #endif #include "test_malloc.h" @@ -34,64 +34,64 @@ static volatile bool in_test_malloc_init = false; static void* test_malloc(size_t size) { - if (in_test_malloc_init) { - return NULL; // dlsym is asking for memory, but handles this fine - } + if (in_test_malloc_init) { + return NULL; // dlsym is asking for memory, but handles this fine + } - if (!test_malloc_sys_malloc) { - test_malloc_init(); - } + if (!test_malloc_sys_malloc) { + test_malloc_init(); + } - if (test_malloc_n_allocs < test_malloc_fail_after) { - ++test_malloc_n_allocs; - return test_malloc_sys_malloc(size); - } + if (test_malloc_n_allocs < test_malloc_fail_after) { + ++test_malloc_n_allocs; + return test_malloc_sys_malloc(size); + } - return NULL; + return NULL; } void* malloc(size_t size) { - return test_malloc(size); + return test_malloc(size); } void* calloc(size_t nmemb, size_t size) { - void* ptr = test_malloc(nmemb * size); - if (ptr) { - memset(ptr, 0, nmemb * size); - } - return ptr; + void* ptr = test_malloc(nmemb * size); + if (ptr) { + memset(ptr, 0, nmemb * size); + } + return ptr; } void test_malloc_reset(size_t fail_after) { - test_malloc_fail_after = fail_after; - test_malloc_n_allocs = 0; + test_malloc_fail_after = fail_after; + test_malloc_n_allocs = 0; } void test_malloc_init(void) { - in_test_malloc_init = true; + in_test_malloc_init = true; - /* Avoid pedantic warnings about casting pointer to function pointer by - casting dlsym instead. */ + /* Avoid pedantic warnings about casting pointer to function pointer by + casting dlsym instead. */ - typedef void* (*MallocFunc)(size_t); - typedef MallocFunc (*MallocFuncGetter)(void*, const char*); + typedef void* (*MallocFunc)(size_t); + typedef MallocFunc (*MallocFuncGetter)(void*, const char*); - MallocFuncGetter dlfunc = (MallocFuncGetter)dlsym; - test_malloc_sys_malloc = (MallocFunc)dlfunc(RTLD_NEXT, "malloc"); + MallocFuncGetter dlfunc = (MallocFuncGetter)dlsym; + test_malloc_sys_malloc = (MallocFunc)dlfunc(RTLD_NEXT, "malloc"); - in_test_malloc_init = false; + in_test_malloc_init = false; } size_t test_malloc_get_n_allocs(void) { - return test_malloc_n_allocs; + return test_malloc_n_allocs; } diff --git a/test/test_malloc.h b/test/test_malloc.h index be59008..42b22df 100644 --- a/test/test_malloc.h +++ b/test/test_malloc.h @@ -18,6 +18,12 @@ #include <stddef.h> -void test_malloc_init(void); -void test_malloc_reset(size_t fail_after); -ZIX_PURE_API size_t test_malloc_get_n_allocs(void); +void +test_malloc_init(void); + +void +test_malloc_reset(size_t fail_after); + +ZIX_PURE_API +size_t +test_malloc_get_n_allocs(void); diff --git a/test/tree_test.c b/test/tree_test.c index 52caede..08913e8 100644 --- a/test/tree_test.c +++ b/test/tree_test.c @@ -30,199 +30,206 @@ static unsigned seed = 1; static int int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data)) { - const intptr_t ia = (intptr_t)a; - const intptr_t ib = (intptr_t)b; + const intptr_t ia = (intptr_t)a; + const intptr_t ib = (intptr_t)b; - return ia < ib ? -1 : ia > ib ? 1 : 0; + return ia < ib ? -1 : ia > ib ? 1 : 0; } static uintptr_t ith_elem(unsigned test_num, size_t n_elems, size_t i) { - switch (test_num % 3) { - case 0: - return i; // Increasing (worst case) - case 1: - return n_elems - i; // Decreasing (worse case) - case 2: - default: - return rand() % 100; // Random - } + switch (test_num % 3) { + case 0: + return i; // Increasing (worst case) + case 1: + return n_elems - i; // Decreasing (worse case) + case 2: + default: + return rand() % 100; // Random + } } static int test_fail(void) { - return EXIT_FAILURE; + return EXIT_FAILURE; } static int stress(unsigned test_num, size_t n_elems) { - intptr_t r; - ZixTreeIter* ti; - - ZixTree* t = zix_tree_new(true, int_cmp, NULL, NULL); - - srand(seed); - - // Insert n_elems elements - for (size_t i = 0; i < n_elems; ++i) { - r = ith_elem(test_num, n_elems, i); - int status = zix_tree_insert(t, (void*)r, &ti); - if (status) { - fprintf(stderr, "Insert failed\n"); - return test_fail(); - } - if ((intptr_t)zix_tree_get(ti) != r) { - fprintf(stderr, "Data corrupt (%" PRIdPTR" != %" PRIdPTR ")\n", - (intptr_t)zix_tree_get(ti), r); - return test_fail(); - } - } - - // Ensure tree size is correct - if (zix_tree_size(t) != n_elems) { - fprintf(stderr, "Tree size %zu != %zu\n", zix_tree_size(t), n_elems); - return test_fail(); - } - - srand(seed); - - // Search for all elements - for (size_t i = 0; i < n_elems; ++i) { - r = ith_elem(test_num, n_elems, i); - if (zix_tree_find(t, (void*)r, &ti)) { - fprintf(stderr, "Find failed\n"); - return test_fail(); - } - if ((intptr_t)zix_tree_get(ti) != r) { - fprintf(stderr, "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n", - (intptr_t)zix_tree_get(ti), r); - return test_fail(); - } - } - - srand(seed); - - // Iterate over all elements - size_t i = 0; - intptr_t last = -1; - for (ZixTreeIter* iter = zix_tree_begin(t); - !zix_tree_iter_is_end(iter); - iter = zix_tree_iter_next(iter), ++i) { - const intptr_t iter_data = (intptr_t)zix_tree_get(iter); - if (iter_data < last) { - fprintf(stderr, "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n", - iter_data, last); - return test_fail(); - } - last = iter_data; - } - if (i != n_elems) { - fprintf(stderr, "Iteration stopped at %zu/%zu elements\n", i, n_elems); - return test_fail(); - } - - srand(seed); - - // Iterate over all elements backwards - i = 0; - last = INTPTR_MAX; - for (ZixTreeIter* iter = zix_tree_rbegin(t); - !zix_tree_iter_is_rend(iter); - iter = zix_tree_iter_prev(iter), ++i) { - const intptr_t iter_data = (intptr_t)zix_tree_get(iter); - if (iter_data > last) { - fprintf(stderr, "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n", - iter_data, last); - return test_fail(); - } - last = iter_data; - } - - srand(seed); - - // Delete all elements - for (size_t e = 0; e < n_elems; e++) { - r = ith_elem(test_num, n_elems, e); - ZixTreeIter* item; - if (zix_tree_find(t, (void*)r, &item) != ZIX_STATUS_SUCCESS) { - fprintf(stderr, "Failed to find item to remove\n"); - return test_fail(); - } - if (zix_tree_remove(t, item)) { - fprintf(stderr, "Error removing item\n"); - } - } - - // Ensure the tree is empty - if (zix_tree_size(t) != 0) { - fprintf(stderr, "Tree size %zu != 0\n", zix_tree_size(t)); - return test_fail(); - } - - srand(seed); - - // Insert n_elems elements again (to test non-empty destruction) - for (size_t e = 0; e < n_elems; ++e) { - r = ith_elem(test_num, n_elems, e); - int status = zix_tree_insert(t, (void*)r, &ti); - if (status) { - fprintf(stderr, "Insert failed\n"); - return test_fail(); - } - if ((intptr_t)zix_tree_get(ti) != r) { - fprintf(stderr, "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n", - (intptr_t)zix_tree_get(ti), r); - return test_fail(); - } - } - - // Ensure tree size is correct - if (zix_tree_size(t) != n_elems) { - fprintf(stderr, "Tree size %zu != %zu\n", zix_tree_size(t), n_elems); - return test_fail(); - } - - zix_tree_free(t); - - return EXIT_SUCCESS; + intptr_t r; + ZixTreeIter* ti; + + ZixTree* t = zix_tree_new(true, int_cmp, NULL, NULL); + + srand(seed); + + // Insert n_elems elements + for (size_t i = 0; i < n_elems; ++i) { + r = ith_elem(test_num, n_elems, i); + int status = zix_tree_insert(t, (void*)r, &ti); + if (status) { + fprintf(stderr, "Insert failed\n"); + return test_fail(); + } + if ((intptr_t)zix_tree_get(ti) != r) { + fprintf(stderr, + "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n", + (intptr_t)zix_tree_get(ti), + r); + return test_fail(); + } + } + + // Ensure tree size is correct + if (zix_tree_size(t) != n_elems) { + fprintf(stderr, "Tree size %zu != %zu\n", zix_tree_size(t), n_elems); + return test_fail(); + } + + srand(seed); + + // Search for all elements + for (size_t i = 0; i < n_elems; ++i) { + r = ith_elem(test_num, n_elems, i); + if (zix_tree_find(t, (void*)r, &ti)) { + fprintf(stderr, "Find failed\n"); + return test_fail(); + } + if ((intptr_t)zix_tree_get(ti) != r) { + fprintf(stderr, + "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n", + (intptr_t)zix_tree_get(ti), + r); + return test_fail(); + } + } + + srand(seed); + + // Iterate over all elements + size_t i = 0; + intptr_t last = -1; + for (ZixTreeIter* iter = zix_tree_begin(t); !zix_tree_iter_is_end(iter); + iter = zix_tree_iter_next(iter), ++i) { + const intptr_t iter_data = (intptr_t)zix_tree_get(iter); + if (iter_data < last) { + fprintf(stderr, + "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n", + iter_data, + last); + return test_fail(); + } + last = iter_data; + } + if (i != n_elems) { + fprintf(stderr, "Iteration stopped at %zu/%zu elements\n", i, n_elems); + return test_fail(); + } + + srand(seed); + + // Iterate over all elements backwards + i = 0; + last = INTPTR_MAX; + for (ZixTreeIter* iter = zix_tree_rbegin(t); !zix_tree_iter_is_rend(iter); + iter = zix_tree_iter_prev(iter), ++i) { + const intptr_t iter_data = (intptr_t)zix_tree_get(iter); + if (iter_data > last) { + fprintf(stderr, + "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n", + iter_data, + last); + return test_fail(); + } + last = iter_data; + } + + srand(seed); + + // Delete all elements + for (size_t e = 0; e < n_elems; e++) { + r = ith_elem(test_num, n_elems, e); + ZixTreeIter* item; + if (zix_tree_find(t, (void*)r, &item) != ZIX_STATUS_SUCCESS) { + fprintf(stderr, "Failed to find item to remove\n"); + return test_fail(); + } + if (zix_tree_remove(t, item)) { + fprintf(stderr, "Error removing item\n"); + } + } + + // Ensure the tree is empty + if (zix_tree_size(t) != 0) { + fprintf(stderr, "Tree size %zu != 0\n", zix_tree_size(t)); + return test_fail(); + } + + srand(seed); + + // Insert n_elems elements again (to test non-empty destruction) + for (size_t e = 0; e < n_elems; ++e) { + r = ith_elem(test_num, n_elems, e); + int status = zix_tree_insert(t, (void*)r, &ti); + if (status) { + fprintf(stderr, "Insert failed\n"); + return test_fail(); + } + if ((intptr_t)zix_tree_get(ti) != r) { + fprintf(stderr, + "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n", + (intptr_t)zix_tree_get(ti), + r); + return test_fail(); + } + } + + // Ensure tree size is correct + if (zix_tree_size(t) != n_elems) { + fprintf(stderr, "Tree size %zu != %zu\n", zix_tree_size(t), n_elems); + return test_fail(); + } + + zix_tree_free(t); + + return EXIT_SUCCESS; } int main(int argc, char** argv) { - const unsigned n_tests = 3; - unsigned n_elems = 0; - - if (argc == 1) { - n_elems = 100000; - } else { - n_elems = (unsigned)atol(argv[1]); - if (argc > 2) { - seed = (unsigned)atol(argv[2]); - } else { - seed = (unsigned)time(NULL); - } - } - - if (n_elems == 0) { - fprintf(stderr, "USAGE: %s [N_ELEMS]\n", argv[0]); - return 1; - } - - printf("Running %u tests with %u elements (seed %u)", - n_tests, n_elems, seed); - - for (unsigned i = 0; i < n_tests; ++i) { - printf("."); - fflush(stdout); - if (stress(i, n_elems)) { - fprintf(stderr, "FAIL: Random seed %u\n", seed); - return test_fail(); - } - } - printf("\n"); - return EXIT_SUCCESS; + const unsigned n_tests = 3; + unsigned n_elems = 0; + + if (argc == 1) { + n_elems = 100000; + } else { + n_elems = (unsigned)atol(argv[1]); + if (argc > 2) { + seed = (unsigned)atol(argv[2]); + } else { + seed = (unsigned)time(NULL); + } + } + + if (n_elems == 0) { + fprintf(stderr, "USAGE: %s [N_ELEMS]\n", argv[0]); + return 1; + } + + printf("Running %u tests with %u elements (seed %u)", n_tests, n_elems, seed); + + for (unsigned i = 0; i < n_tests; ++i) { + printf("."); + fflush(stdout); + if (stress(i, n_elems)) { + fprintf(stderr, "FAIL: Random seed %u\n", seed); + return test_fail(); + } + } + printf("\n"); + return EXIT_SUCCESS; } diff --git a/zix/bitset.c b/zix/bitset.c index f447b74..cf82ad0 100644 --- a/zix/bitset.c +++ b/zix/bitset.c @@ -17,7 +17,7 @@ #include "zix/bitset.h" #ifdef _MSC_VER -#include <intrin.h> +# include <intrin.h> #endif #include <string.h> @@ -29,96 +29,96 @@ static inline size_t zix_bitset_popcount(const ZixBitset value) { #ifdef _MSC_VER - return (size_t)__popcnt(value); + return (size_t)__popcnt(value); #else - return (size_t)__builtin_popcountl(value); + return (size_t)__builtin_popcountl(value); #endif } void zix_bitset_clear(ZixBitset* b, ZixBitsetTally* t, size_t n_bits) { - memset(b, 0, ZIX_BITSET_ELEMS(n_bits) * sizeof(ZixBitset)); - memset(t, 0, ZIX_BITSET_ELEMS(n_bits) * sizeof(ZixBitsetTally)); + memset(b, 0, ZIX_BITSET_ELEMS(n_bits) * sizeof(ZixBitset)); + memset(t, 0, ZIX_BITSET_ELEMS(n_bits) * sizeof(ZixBitsetTally)); } void zix_bitset_set(ZixBitset* b, ZixBitsetTally* t, size_t i) { - const size_t e = i / ZIX_BITSET_ELEM_BIT; - const size_t ebit = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT - const ZixBitset mask = (ZixBitset)1 << ebit; + const size_t e = i / ZIX_BITSET_ELEM_BIT; + const size_t ebit = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT + const ZixBitset mask = (ZixBitset)1 << ebit; - if (!(b[e] & mask)) { - ++t[e]; - } + if (!(b[e] & mask)) { + ++t[e]; + } - b[e] |= mask; + b[e] |= mask; } void zix_bitset_reset(ZixBitset* b, ZixBitsetTally* t, size_t i) { - const size_t e = i / ZIX_BITSET_ELEM_BIT; - const size_t ebit = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT - const ZixBitset mask = (ZixBitset)1 << ebit; + const size_t e = i / ZIX_BITSET_ELEM_BIT; + const size_t ebit = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT + const ZixBitset mask = (ZixBitset)1 << ebit; - if (b[e] & mask) { - --t[e]; - } + if (b[e] & mask) { + --t[e]; + } - b[e] &= ~mask; + b[e] &= ~mask; } bool zix_bitset_get(const ZixBitset* b, size_t i) { - const size_t e = i / ZIX_BITSET_ELEM_BIT; - const size_t ebit = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT - const ZixBitset mask = (ZixBitset)1 << ebit; + const size_t e = i / ZIX_BITSET_ELEM_BIT; + const size_t ebit = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT + const ZixBitset mask = (ZixBitset)1 << ebit; - return b[e] & mask; + return b[e] & mask; } size_t zix_bitset_count_up_to(const ZixBitset* b, const ZixBitsetTally* t, size_t i) { - const size_t full_elems = i / ZIX_BITSET_ELEM_BIT; - const size_t extra = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT + const size_t full_elems = i / ZIX_BITSET_ELEM_BIT; + const size_t extra = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT - size_t count = 0; - for (size_t e = 0; e < full_elems; ++e) { - count += t[e]; - } + size_t count = 0; + for (size_t e = 0; e < full_elems; ++e) { + count += t[e]; + } - if (extra) { - const ZixBitset mask = ~(~(ZixBitset)0 << extra); - count += zix_bitset_popcount(b[full_elems] & mask); - } + if (extra) { + const ZixBitset mask = ~(~(ZixBitset)0 << extra); + count += zix_bitset_popcount(b[full_elems] & mask); + } - return count; + return count; } size_t zix_bitset_count_up_to_if(const ZixBitset* b, const ZixBitsetTally* t, size_t i) { - const size_t full_elems = i / ZIX_BITSET_ELEM_BIT; - const size_t extra = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT + const size_t full_elems = i / ZIX_BITSET_ELEM_BIT; + const size_t extra = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT - const ZixBitset get_mask = (ZixBitset)1 << extra; - if (!(b[full_elems] & get_mask)) { - return (size_t)-1; - } + const ZixBitset get_mask = (ZixBitset)1 << extra; + if (!(b[full_elems] & get_mask)) { + return (size_t)-1; + } - size_t count = 0; - for (size_t e = 0; e < full_elems; ++e) { - count += t[e]; - } + size_t count = 0; + for (size_t e = 0; e < full_elems; ++e) { + count += t[e]; + } - if (extra) { - const ZixBitset mask = ~(~(ZixBitset)0 << extra); - count += zix_bitset_popcount(b[full_elems] & mask); - } + if (extra) { + const ZixBitset mask = ~(~(ZixBitset)0 << extra); + count += zix_bitset_popcount(b[full_elems] & mask); + } - return count; + return count; } diff --git a/zix/bitset.h b/zix/bitset.h index 5214669..68dd344 100644 --- a/zix/bitset.h +++ b/zix/bitset.h @@ -49,50 +49,58 @@ typedef uint8_t ZixBitsetTally; /** The number of bitset elements needed for the given number of bits. */ -#define ZIX_BITSET_ELEMS(n_bits) \ - (((n_bits) / ZIX_BITSET_BITS_PER_ELEM) + \ - ((n_bits) % ZIX_BITSET_BITS_PER_ELEM ? 1 : 0)) +#define ZIX_BITSET_ELEMS(n_bits) \ + (((n_bits) / ZIX_BITSET_BITS_PER_ELEM) + \ + ((n_bits) % ZIX_BITSET_BITS_PER_ELEM ? 1 : 0)) /** Clear a Bitset. */ -ZIX_API void +ZIX_API +void zix_bitset_clear(ZixBitset* b, ZixBitsetTally* t, size_t n_bits); /** Set bit `i` in `t` to 1. */ -ZIX_API void +ZIX_API +void zix_bitset_set(ZixBitset* b, ZixBitsetTally* t, size_t i); /** Clear bit `i` in `t` (set to 0). */ -ZIX_API void +ZIX_API +void zix_bitset_reset(ZixBitset* b, ZixBitsetTally* t, size_t i); /** Return the `i`th bit in `t`. */ -ZIX_PURE_API bool +ZIX_PURE_API +bool zix_bitset_get(const ZixBitset* b, size_t i); /** Return the number of set bits in `b` up to bit `i` (non-inclusive). */ -ZIX_PURE_API size_t +ZIX_PURE_API +size_t zix_bitset_count_up_to(const ZixBitset* b, const ZixBitsetTally* t, size_t i); /** Return the number of set bits in `b` up to bit `i` (non-inclusive) if bit `i` is set, or (size_t)-1 otherwise. */ -ZIX_PURE_API size_t -zix_bitset_count_up_to_if(const ZixBitset* b, const ZixBitsetTally* t, size_t i); +ZIX_PURE_API +size_t +zix_bitset_count_up_to_if(const ZixBitset* b, + const ZixBitsetTally* t, + size_t i); /** @} @} */ -#endif /* ZIX_BITSET_H */ +#endif /* ZIX_BITSET_H */ diff --git a/zix/btree.c b/zix/btree.c index d8bca23..7435445 100644 --- a/zix/btree.c +++ b/zix/btree.c @@ -25,121 +25,124 @@ // #define ZIX_BTREE_SORTED_CHECK 1 #ifndef ZIX_BTREE_PAGE_SIZE -# define ZIX_BTREE_PAGE_SIZE 4096 +# define ZIX_BTREE_PAGE_SIZE 4096 #endif #define ZIX_BTREE_NODE_SPACE (ZIX_BTREE_PAGE_SIZE - 2 * sizeof(uint16_t)) -#define ZIX_BTREE_LEAF_VALS ((ZIX_BTREE_NODE_SPACE / sizeof(void*)) - 1) +#define ZIX_BTREE_LEAF_VALS ((ZIX_BTREE_NODE_SPACE / sizeof(void*)) - 1) #define ZIX_BTREE_INODE_VALS (ZIX_BTREE_LEAF_VALS / 2) struct ZixBTreeImpl { - ZixBTreeNode* root; - ZixDestroyFunc destroy; - ZixComparator cmp; - const void* cmp_data; - size_t size; - unsigned height; ///< Number of levels, i.e. root only has height 1 + ZixBTreeNode* root; + ZixDestroyFunc destroy; + ZixComparator cmp; + const void* cmp_data; + size_t size; + unsigned height; ///< Number of levels, i.e. root only has height 1 }; struct ZixBTreeNodeImpl { - uint16_t is_leaf; - uint16_t n_vals; - // On 64-bit we rely on some padding here to get page-sized nodes - union { - struct { - void* vals[ZIX_BTREE_LEAF_VALS]; - } leaf; - - struct { - void* vals[ZIX_BTREE_INODE_VALS]; - ZixBTreeNode* children[ZIX_BTREE_INODE_VALS + 1]; - } inode; - } data; + uint16_t is_leaf; + uint16_t n_vals; + // On 64-bit we rely on some padding here to get page-sized nodes + union { + struct { + void* vals[ZIX_BTREE_LEAF_VALS]; + } leaf; + + struct { + void* vals[ZIX_BTREE_INODE_VALS]; + ZixBTreeNode* children[ZIX_BTREE_INODE_VALS + 1]; + } inode; + } data; }; #if (defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112l) || \ - (defined(__cplusplus) && __cplusplus >= 201103L) + (defined(__cplusplus) && __cplusplus >= 201103L) static_assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE, ""); #endif typedef struct { - ZixBTreeNode* node; - unsigned index; + ZixBTreeNode* node; + unsigned index; } ZixBTreeIterFrame; struct ZixBTreeIterImpl { - unsigned n_levels; ///< Maximum depth of stack - unsigned level; ///< Current level in stack - ZixBTreeIterFrame stack[]; ///< Position stack + unsigned n_levels; ///< Maximum depth of stack + unsigned level; ///< Current level in stack + ZixBTreeIterFrame stack[]; ///< Position stack }; #ifdef ZIX_BTREE_DEBUG -ZIX_PRIVATE void +ZIX_PRIVATE +void print_node(const ZixBTreeNode* n, const char* prefix) { - printf("%s[", prefix); - for (uint16_t v = 0; v < n->n_vals; ++v) { - printf(" %lu", (uintptr_t)n->vals[v]); - } - printf(" ]\n"); + printf("%s[", prefix); + for (uint16_t v = 0; v < n->n_vals; ++v) { + printf(" %lu", (uintptr_t)n->vals[v]); + } + printf(" ]\n"); } -ZIX_PRIVATE void +ZIX_PRIVATE +void print_tree(const ZixBTreeNode* parent, const ZixBTreeNode* node, int level) { - if (node) { - if (!parent) { - printf("TREE {\n"); - } - for (int i = 0; i < level + 1; ++i) { - printf(" "); - } - print_node(node, ""); - if (!node->is_leaf) { - for (uint16_t i = 0; i < node->n_vals + 1; ++i) { - print_tree(node, node->data.inode.children[i], level + 1); - } - } - if (!parent) { - printf("}\n"); - } - } -} - -#endif // ZIX_BTREE_DEBUG - -ZIX_PRIVATE ZixBTreeNode* + if (node) { + if (!parent) { + printf("TREE {\n"); + } + for (int i = 0; i < level + 1; ++i) { + printf(" "); + } + print_node(node, ""); + if (!node->is_leaf) { + for (uint16_t i = 0; i < node->n_vals + 1; ++i) { + print_tree(node, node->data.inode.children[i], level + 1); + } + } + if (!parent) { + printf("}\n"); + } + } +} + +#endif // ZIX_BTREE_DEBUG + +ZIX_PRIVATE +ZixBTreeNode* zix_btree_node_new(const bool leaf) { #if !((defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112l) || \ (defined(__cplusplus) && __cplusplus >= 201103L)) - assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE); + assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE); #endif - ZixBTreeNode* node = (ZixBTreeNode*)malloc(sizeof(ZixBTreeNode)); - if (node) { - node->is_leaf = leaf; - node->n_vals = 0; - } - return node; + ZixBTreeNode* node = (ZixBTreeNode*)malloc(sizeof(ZixBTreeNode)); + if (node) { + node->is_leaf = leaf; + node->n_vals = 0; + } + return node; } ZIX_PRIVATE void* zix_btree_value(const ZixBTreeNode* const node, const unsigned i) { - assert(i < node->n_vals); - return node->is_leaf ? node->data.leaf.vals[i] : node->data.inode.vals[i]; + assert(i < node->n_vals); + return node->is_leaf ? node->data.leaf.vals[i] : node->data.inode.vals[i]; } ZIX_PRIVATE ZixBTreeNode* zix_btree_child(const ZixBTreeNode* const node, const unsigned i) { - assert(!node->is_leaf); - assert(i <= ZIX_BTREE_INODE_VALS); - return node->data.inode.children[i]; + assert(!node->is_leaf); + assert(i <= ZIX_BTREE_INODE_VALS); + return node->data.inode.children[i]; } ZixBTree* @@ -147,459 +150,468 @@ zix_btree_new(const ZixComparator cmp, const void* const cmp_data, const ZixDestroyFunc destroy) { - ZixBTree* t = (ZixBTree*)malloc(sizeof(ZixBTree)); - if (t) { - t->root = zix_btree_node_new(true); - t->destroy = destroy; - t->cmp = cmp; - t->cmp_data = cmp_data; - t->size = 0; - t->height = 1; - if (!t->root) { - free(t); - return NULL; - } - } - return t; -} - -ZIX_PRIVATE void + ZixBTree* t = (ZixBTree*)malloc(sizeof(ZixBTree)); + if (t) { + t->root = zix_btree_node_new(true); + t->destroy = destroy; + t->cmp = cmp; + t->cmp_data = cmp_data; + t->size = 0; + t->height = 1; + if (!t->root) { + free(t); + return NULL; + } + } + return t; +} + +ZIX_PRIVATE +void zix_btree_free_rec(ZixBTree* const t, ZixBTreeNode* const n) { - if (n) { - if (n->is_leaf) { - if (t->destroy) { - for (uint16_t i = 0; i < n->n_vals; ++i) { - t->destroy(n->data.leaf.vals[i]); - } - } - } else { - if (t->destroy) { - for (uint16_t i = 0; i < n->n_vals; ++i) { - t->destroy(n->data.inode.vals[i]); - } - } - - for (uint16_t i = 0; i < n->n_vals + 1; ++i) { - zix_btree_free_rec(t, zix_btree_child(n, i)); - } - } - free(n); - } + if (n) { + if (n->is_leaf) { + if (t->destroy) { + for (uint16_t i = 0; i < n->n_vals; ++i) { + t->destroy(n->data.leaf.vals[i]); + } + } + } else { + if (t->destroy) { + for (uint16_t i = 0; i < n->n_vals; ++i) { + t->destroy(n->data.inode.vals[i]); + } + } + + for (uint16_t i = 0; i < n->n_vals + 1; ++i) { + zix_btree_free_rec(t, zix_btree_child(n, i)); + } + } + + free(n); + } } void zix_btree_free(ZixBTree* const t) { - if (t) { - zix_btree_free_rec(t, t->root); - free(t); - } + if (t) { + zix_btree_free_rec(t, t->root); + free(t); + } } size_t zix_btree_size(const ZixBTree* const t) { - return t->size; + return t->size; } -ZIX_PRIVATE uint16_t +ZIX_PRIVATE +uint16_t zix_btree_max_vals(const ZixBTreeNode* const node) { - return node->is_leaf ? ZIX_BTREE_LEAF_VALS : ZIX_BTREE_INODE_VALS; + return node->is_leaf ? ZIX_BTREE_LEAF_VALS : ZIX_BTREE_INODE_VALS; } -ZIX_PRIVATE uint16_t +ZIX_PRIVATE +uint16_t zix_btree_min_vals(const ZixBTreeNode* const node) { - return (uint16_t)(((zix_btree_max_vals(node) + 1U) / 2U) - 1U); + return (uint16_t)(((zix_btree_max_vals(node) + 1U) / 2U) - 1U); } /** Shift pointers in `array` of length `n` right starting at `i`. */ -ZIX_PRIVATE void +ZIX_PRIVATE +void zix_btree_ainsert(void** const array, const unsigned n, const unsigned i, void* const e) { - memmove(array + i + 1, array + i, (n - i) * sizeof(e)); - array[i] = e; + memmove(array + i + 1, array + i, (n - i) * sizeof(e)); + array[i] = e; } /** Erase element `i` in `array` of length `n` and return erased element. */ -ZIX_PRIVATE void* +ZIX_PRIVATE +void* zix_btree_aerase(void** const array, const unsigned n, const unsigned i) { - void* const ret = array[i]; - memmove(array + i, array + i + 1, (n - i) * sizeof(ret)); - return ret; + void* const ret = array[i]; + memmove(array + i, array + i + 1, (n - i) * sizeof(ret)); + return ret; } /** Split lhs, the i'th child of `n`, into two nodes. */ -ZIX_PRIVATE ZixBTreeNode* +ZIX_PRIVATE +ZixBTreeNode* zix_btree_split_child(ZixBTreeNode* const n, const unsigned i, ZixBTreeNode* const lhs) { - assert(lhs->n_vals == zix_btree_max_vals(lhs)); - assert(n->n_vals < ZIX_BTREE_INODE_VALS); - assert(i < n->n_vals + 1U); - assert(zix_btree_child(n, i) == lhs); - - const uint16_t max_n_vals = zix_btree_max_vals(lhs); - ZixBTreeNode* rhs = zix_btree_node_new(lhs->is_leaf); - if (!rhs) { - return NULL; - } - - // LHS and RHS get roughly half, less the middle value which moves up - lhs->n_vals = max_n_vals / 2U; - rhs->n_vals = (uint16_t)(max_n_vals - lhs->n_vals - 1); - - if (lhs->is_leaf) { - // Copy large half from LHS to new RHS node - memcpy(rhs->data.leaf.vals, - lhs->data.leaf.vals + lhs->n_vals + 1, - rhs->n_vals * sizeof(void*)); - - // Move middle value up to parent - zix_btree_ainsert(n->data.inode.vals, - n->n_vals, - i, - lhs->data.leaf.vals[lhs->n_vals]); - } else { - // Copy large half from LHS to new RHS node - memcpy(rhs->data.inode.vals, - lhs->data.inode.vals + lhs->n_vals + 1, - rhs->n_vals * sizeof(void*)); - memcpy(rhs->data.inode.children, - lhs->data.inode.children + lhs->n_vals + 1, - (rhs->n_vals + 1U) * sizeof(ZixBTreeNode*)); - - // Move middle value up to parent - zix_btree_ainsert(n->data.inode.vals, - n->n_vals, - i, - lhs->data.inode.vals[lhs->n_vals]); - } - - // Insert new RHS node in parent at position i - zix_btree_ainsert((void**)n->data.inode.children, ++n->n_vals, i + 1U, rhs); - - return rhs; + assert(lhs->n_vals == zix_btree_max_vals(lhs)); + assert(n->n_vals < ZIX_BTREE_INODE_VALS); + assert(i < n->n_vals + 1U); + assert(zix_btree_child(n, i) == lhs); + + const uint16_t max_n_vals = zix_btree_max_vals(lhs); + ZixBTreeNode* rhs = zix_btree_node_new(lhs->is_leaf); + if (!rhs) { + return NULL; + } + + // LHS and RHS get roughly half, less the middle value which moves up + lhs->n_vals = max_n_vals / 2U; + rhs->n_vals = (uint16_t)(max_n_vals - lhs->n_vals - 1); + + if (lhs->is_leaf) { + // Copy large half from LHS to new RHS node + memcpy(rhs->data.leaf.vals, + lhs->data.leaf.vals + lhs->n_vals + 1, + rhs->n_vals * sizeof(void*)); + + // Move middle value up to parent + zix_btree_ainsert( + n->data.inode.vals, n->n_vals, i, lhs->data.leaf.vals[lhs->n_vals]); + } else { + // Copy large half from LHS to new RHS node + memcpy(rhs->data.inode.vals, + lhs->data.inode.vals + lhs->n_vals + 1, + rhs->n_vals * sizeof(void*)); + memcpy(rhs->data.inode.children, + lhs->data.inode.children + lhs->n_vals + 1, + (rhs->n_vals + 1U) * sizeof(ZixBTreeNode*)); + + // Move middle value up to parent + zix_btree_ainsert( + n->data.inode.vals, n->n_vals, i, lhs->data.inode.vals[lhs->n_vals]); + } + + // Insert new RHS node in parent at position i + zix_btree_ainsert((void**)n->data.inode.children, ++n->n_vals, i + 1U, rhs); + + return rhs; } #ifdef ZIX_BTREE_SORTED_CHECK /** Check that `n` is sorted with respect to search key `e`. */ -ZIX_PRIVATE bool +ZIX_PRIVATE +bool zix_btree_node_is_sorted_with_respect_to(const ZixBTree* const t, const ZixBTreeNode* const n, const void* const e) { - if (n->n_vals <= 1) { - return true; - } + if (n->n_vals <= 1) { + return true; + } - int cmp = t->cmp(zix_btree_value(n, 0), e, t->cmp_data); - for (uint16_t i = 1; i < n->n_vals; ++i) { - const int next_cmp = t->cmp(zix_btree_value(n, i), e, t->cmp_data); - if ((cmp >= 0 && next_cmp < 0) || - (cmp > 0 && next_cmp <= 0)) { - return false; - } - cmp = next_cmp; - } + int cmp = t->cmp(zix_btree_value(n, 0), e, t->cmp_data); + for (uint16_t i = 1; i < n->n_vals; ++i) { + const int next_cmp = t->cmp(zix_btree_value(n, i), e, t->cmp_data); + if ((cmp >= 0 && next_cmp < 0) || (cmp > 0 && next_cmp <= 0)) { + return false; + } + cmp = next_cmp; + } - return true; + return true; } #endif /** Find the first value in `n` that is not less than `e` (lower bound). */ -ZIX_PRIVATE unsigned +ZIX_PRIVATE +unsigned zix_btree_node_find(const ZixBTree* const t, const ZixBTreeNode* const n, const void* const e, bool* const equal) { #ifdef ZIX_BTREE_SORTED_CHECK - assert(zix_btree_node_is_sorted_with_respect_to(t, n, e)); + assert(zix_btree_node_is_sorted_with_respect_to(t, n, e)); #endif - unsigned first = 0U; - unsigned len = n->n_vals; - while (len > 0) { - const unsigned half = len >> 1U; - const unsigned i = first + half; - const int cmp = t->cmp(zix_btree_value(n, i), e, t->cmp_data); - if (cmp == 0) { - *equal = true; - len = half; // Keep searching for wildcard matches - } else if (cmp < 0) { - const unsigned chop = half + 1U; - first += chop; - len -= chop; - } else { - len = half; - } - } - assert(!*equal || t->cmp(zix_btree_value(n, first), e, t->cmp_data) == 0); - return first; + unsigned first = 0U; + unsigned len = n->n_vals; + while (len > 0) { + const unsigned half = len >> 1U; + const unsigned i = first + half; + const int cmp = t->cmp(zix_btree_value(n, i), e, t->cmp_data); + if (cmp == 0) { + *equal = true; + len = half; // Keep searching for wildcard matches + } else if (cmp < 0) { + const unsigned chop = half + 1U; + first += chop; + len -= chop; + } else { + len = half; + } + } + + assert(!*equal || t->cmp(zix_btree_value(n, first), e, t->cmp_data) == 0); + return first; } ZixStatus zix_btree_insert(ZixBTree* const t, void* const e) { - ZixBTreeNode* parent = NULL; // Parent of n - ZixBTreeNode* n = t->root; // Current node - unsigned i = 0; // Index of n in parent - while (n) { - if (n->n_vals == zix_btree_max_vals(n)) { - // Node is full, split to ensure there is space for a leaf split - if (!parent) { - // Root is full, grow tree upwards - if (!(parent = zix_btree_node_new(false))) { - return ZIX_STATUS_NO_MEM; - } - t->root = parent; - parent->data.inode.children[0] = n; - ++t->height; - } - - ZixBTreeNode* const rhs = zix_btree_split_child(parent, i, n); - if (!rhs) { - return ZIX_STATUS_NO_MEM; - } - - const int cmp = t->cmp(parent->data.inode.vals[i], e, t->cmp_data); - if (cmp == 0) { - return ZIX_STATUS_EXISTS; - } - - if (cmp < 0) { - // Move to new RHS - n = rhs; - ++i; - } - } - - assert(!parent || zix_btree_child(parent, i) == n); - - bool equal = false; - i = zix_btree_node_find(t, n, e, &equal); - if (equal) { - return ZIX_STATUS_EXISTS; - } - - if (!n->is_leaf) { - // Descend to child node left of value - parent = n; - n = zix_btree_child(n, i); - } else { - // Insert into internal node - zix_btree_ainsert(n->data.leaf.vals, n->n_vals++, i, e); - break; - } - } - - ++t->size; - - return ZIX_STATUS_SUCCESS; -} - -ZIX_PRIVATE ZixBTreeIter* + ZixBTreeNode* parent = NULL; // Parent of n + ZixBTreeNode* n = t->root; // Current node + unsigned i = 0; // Index of n in parent + while (n) { + if (n->n_vals == zix_btree_max_vals(n)) { + // Node is full, split to ensure there is space for a leaf split + if (!parent) { + // Root is full, grow tree upwards + if (!(parent = zix_btree_node_new(false))) { + return ZIX_STATUS_NO_MEM; + } + t->root = parent; + parent->data.inode.children[0] = n; + ++t->height; + } + + ZixBTreeNode* const rhs = zix_btree_split_child(parent, i, n); + if (!rhs) { + return ZIX_STATUS_NO_MEM; + } + + const int cmp = t->cmp(parent->data.inode.vals[i], e, t->cmp_data); + if (cmp == 0) { + return ZIX_STATUS_EXISTS; + } + + if (cmp < 0) { + // Move to new RHS + n = rhs; + ++i; + } + } + + assert(!parent || zix_btree_child(parent, i) == n); + + bool equal = false; + i = zix_btree_node_find(t, n, e, &equal); + if (equal) { + return ZIX_STATUS_EXISTS; + } + + if (!n->is_leaf) { + // Descend to child node left of value + parent = n; + n = zix_btree_child(n, i); + } else { + // Insert into internal node + zix_btree_ainsert(n->data.leaf.vals, n->n_vals++, i, e); + break; + } + } + + ++t->size; + + return ZIX_STATUS_SUCCESS; +} + +ZIX_PRIVATE +ZixBTreeIter* zix_btree_iter_new(const ZixBTree* const t) { - const size_t s = t->height * sizeof(ZixBTreeIterFrame); + const size_t s = t->height * sizeof(ZixBTreeIterFrame); - ZixBTreeIter* i = (ZixBTreeIter*)calloc(1, sizeof(ZixBTreeIter) + s); - if (i) { - i->n_levels = t->height; - } - return i; + ZixBTreeIter* i = (ZixBTreeIter*)calloc(1, sizeof(ZixBTreeIter) + s); + if (i) { + i->n_levels = t->height; + } + return i; } -ZIX_PRIVATE void +ZIX_PRIVATE +void zix_btree_iter_set_frame(ZixBTreeIter* const ti, ZixBTreeNode* const n, const unsigned i) { - if (ti) { - ti->stack[ti->level].node = n; - ti->stack[ti->level].index = i; - } + if (ti) { + ti->stack[ti->level].node = n; + ti->stack[ti->level].index = i; + } } -ZIX_PRIVATE bool +ZIX_PRIVATE +bool zix_btree_node_is_minimal(ZixBTreeNode* const n) { - assert(n->n_vals >= zix_btree_min_vals(n)); - return n->n_vals == zix_btree_min_vals(n); + assert(n->n_vals >= zix_btree_min_vals(n)); + return n->n_vals == zix_btree_min_vals(n); } /** Enlarge left child by stealing a value from its right sibling. */ -ZIX_PRIVATE ZixBTreeNode* +ZIX_PRIVATE +ZixBTreeNode* zix_btree_rotate_left(ZixBTreeNode* const parent, const unsigned i) { - ZixBTreeNode* const lhs = zix_btree_child(parent, i); - ZixBTreeNode* const rhs = zix_btree_child(parent, i + 1); + ZixBTreeNode* const lhs = zix_btree_child(parent, i); + ZixBTreeNode* const rhs = zix_btree_child(parent, i + 1); - assert(lhs->is_leaf == rhs->is_leaf); + assert(lhs->is_leaf == rhs->is_leaf); - if (lhs->is_leaf) { - // Move parent value to end of LHS - lhs->data.leaf.vals[lhs->n_vals++] = parent->data.inode.vals[i]; + if (lhs->is_leaf) { + // Move parent value to end of LHS + lhs->data.leaf.vals[lhs->n_vals++] = parent->data.inode.vals[i]; - // Move first value in RHS to parent - parent->data.inode.vals[i] = - zix_btree_aerase(rhs->data.leaf.vals, rhs->n_vals, 0); - } else { - // Move parent value to end of LHS - lhs->data.inode.vals[lhs->n_vals++] = parent->data.inode.vals[i]; + // Move first value in RHS to parent + parent->data.inode.vals[i] = + zix_btree_aerase(rhs->data.leaf.vals, rhs->n_vals, 0); + } else { + // Move parent value to end of LHS + lhs->data.inode.vals[lhs->n_vals++] = parent->data.inode.vals[i]; - // Move first value in RHS to parent - parent->data.inode.vals[i] = - zix_btree_aerase(rhs->data.inode.vals, rhs->n_vals, 0); + // Move first value in RHS to parent + parent->data.inode.vals[i] = + zix_btree_aerase(rhs->data.inode.vals, rhs->n_vals, 0); - // Move first child pointer from RHS to end of LHS - lhs->data.inode.children[lhs->n_vals] = (ZixBTreeNode*)zix_btree_aerase( - (void**)rhs->data.inode.children, rhs->n_vals, 0); - } + // Move first child pointer from RHS to end of LHS + lhs->data.inode.children[lhs->n_vals] = (ZixBTreeNode*)zix_btree_aerase( + (void**)rhs->data.inode.children, rhs->n_vals, 0); + } - --rhs->n_vals; + --rhs->n_vals; - return lhs; + return lhs; } /** Enlarge right child by stealing a value from its left sibling. */ -ZIX_PRIVATE ZixBTreeNode* +ZIX_PRIVATE +ZixBTreeNode* zix_btree_rotate_right(ZixBTreeNode* const parent, const unsigned i) { - ZixBTreeNode* const lhs = zix_btree_child(parent, i - 1); - ZixBTreeNode* const rhs = zix_btree_child(parent, i); + ZixBTreeNode* const lhs = zix_btree_child(parent, i - 1); + ZixBTreeNode* const rhs = zix_btree_child(parent, i); - assert(lhs->is_leaf == rhs->is_leaf); + assert(lhs->is_leaf == rhs->is_leaf); - if (lhs->is_leaf) { - // Prepend parent value to RHS - zix_btree_ainsert(rhs->data.leaf.vals, - rhs->n_vals++, - 0, - parent->data.inode.vals[i - 1]); + if (lhs->is_leaf) { + // Prepend parent value to RHS + zix_btree_ainsert( + rhs->data.leaf.vals, rhs->n_vals++, 0, parent->data.inode.vals[i - 1]); - // Move last value from LHS to parent - parent->data.inode.vals[i - 1] = lhs->data.leaf.vals[--lhs->n_vals]; - } else { - // Prepend parent value to RHS - zix_btree_ainsert(rhs->data.inode.vals, - rhs->n_vals++, - 0, - parent->data.inode.vals[i - 1]); + // Move last value from LHS to parent + parent->data.inode.vals[i - 1] = lhs->data.leaf.vals[--lhs->n_vals]; + } else { + // Prepend parent value to RHS + zix_btree_ainsert( + rhs->data.inode.vals, rhs->n_vals++, 0, parent->data.inode.vals[i - 1]); - // Move last child pointer from LHS and prepend to RHS - zix_btree_ainsert((void**)rhs->data.inode.children, - rhs->n_vals, - 0, - lhs->data.inode.children[lhs->n_vals]); + // Move last child pointer from LHS and prepend to RHS + zix_btree_ainsert((void**)rhs->data.inode.children, + rhs->n_vals, + 0, + lhs->data.inode.children[lhs->n_vals]); - // Move last value from LHS to parent - parent->data.inode.vals[i - 1] = lhs->data.inode.vals[--lhs->n_vals]; - } + // Move last value from LHS to parent + parent->data.inode.vals[i - 1] = lhs->data.inode.vals[--lhs->n_vals]; + } - return rhs; + return rhs; } /** Move n[i] down, merge the left and right child, return the merged node. */ -ZIX_PRIVATE ZixBTreeNode* +ZIX_PRIVATE +ZixBTreeNode* zix_btree_merge(ZixBTree* const t, ZixBTreeNode* const n, const unsigned i) { - ZixBTreeNode* const lhs = zix_btree_child(n, i); - ZixBTreeNode* const rhs = zix_btree_child(n, i + 1); - - assert(lhs->is_leaf == rhs->is_leaf); - assert(zix_btree_node_is_minimal(lhs)); - assert(lhs->n_vals + rhs->n_vals < zix_btree_max_vals(lhs)); - - // Move parent value to end of LHS - if (lhs->is_leaf) { - lhs->data.leaf.vals[lhs->n_vals++] = - zix_btree_aerase(n->data.inode.vals, n->n_vals, i); - } else { - lhs->data.inode.vals[lhs->n_vals++] = - zix_btree_aerase(n->data.inode.vals, n->n_vals, i); - } - - // Erase corresponding child pointer (to RHS) in parent - zix_btree_aerase((void**)n->data.inode.children, n->n_vals, i + 1U); - - // Add everything from RHS to end of LHS - if (lhs->is_leaf) { - memcpy(lhs->data.leaf.vals + lhs->n_vals, - rhs->data.leaf.vals, - rhs->n_vals * sizeof(void*)); - } else { - memcpy(lhs->data.inode.vals + lhs->n_vals, - rhs->data.inode.vals, - rhs->n_vals * sizeof(void*)); - memcpy(lhs->data.inode.children + lhs->n_vals, - rhs->data.inode.children, - (rhs->n_vals + 1U) * sizeof(void*)); - } - - lhs->n_vals = (uint16_t)(lhs->n_vals + rhs->n_vals); - - if (--n->n_vals == 0) { - // Root is now empty, replace it with its only child - assert(n == t->root); - t->root = lhs; - free(n); - } - - free(rhs); - return lhs; + ZixBTreeNode* const lhs = zix_btree_child(n, i); + ZixBTreeNode* const rhs = zix_btree_child(n, i + 1); + + assert(lhs->is_leaf == rhs->is_leaf); + assert(zix_btree_node_is_minimal(lhs)); + assert(lhs->n_vals + rhs->n_vals < zix_btree_max_vals(lhs)); + + // Move parent value to end of LHS + if (lhs->is_leaf) { + lhs->data.leaf.vals[lhs->n_vals++] = + zix_btree_aerase(n->data.inode.vals, n->n_vals, i); + } else { + lhs->data.inode.vals[lhs->n_vals++] = + zix_btree_aerase(n->data.inode.vals, n->n_vals, i); + } + + // Erase corresponding child pointer (to RHS) in parent + zix_btree_aerase((void**)n->data.inode.children, n->n_vals, i + 1U); + + // Add everything from RHS to end of LHS + if (lhs->is_leaf) { + memcpy(lhs->data.leaf.vals + lhs->n_vals, + rhs->data.leaf.vals, + rhs->n_vals * sizeof(void*)); + } else { + memcpy(lhs->data.inode.vals + lhs->n_vals, + rhs->data.inode.vals, + rhs->n_vals * sizeof(void*)); + memcpy(lhs->data.inode.children + lhs->n_vals, + rhs->data.inode.children, + (rhs->n_vals + 1U) * sizeof(void*)); + } + + lhs->n_vals = (uint16_t)(lhs->n_vals + rhs->n_vals); + + if (--n->n_vals == 0) { + // Root is now empty, replace it with its only child + assert(n == t->root); + t->root = lhs; + free(n); + } + + free(rhs); + return lhs; } /** Remove and return the min value from the subtree rooted at `n`. */ -ZIX_PRIVATE void* +ZIX_PRIVATE +void* zix_btree_remove_min(ZixBTree* const t, ZixBTreeNode* n) { - while (!n->is_leaf) { - if (zix_btree_node_is_minimal(zix_btree_child(n, 0))) { - // Leftmost child is minimal, must expand - if (!zix_btree_node_is_minimal(zix_btree_child(n, 1))) { - // Child's right sibling has at least one key to steal - n = zix_btree_rotate_left(n, 0); - } else { - // Both child and right sibling are minimal, merge - n = zix_btree_merge(t, n, 0); - } - } else { - n = zix_btree_child(n, 0); - } - } + while (!n->is_leaf) { + if (zix_btree_node_is_minimal(zix_btree_child(n, 0))) { + // Leftmost child is minimal, must expand + if (!zix_btree_node_is_minimal(zix_btree_child(n, 1))) { + // Child's right sibling has at least one key to steal + n = zix_btree_rotate_left(n, 0); + } else { + // Both child and right sibling are minimal, merge + n = zix_btree_merge(t, n, 0); + } + } else { + n = zix_btree_child(n, 0); + } + } - return zix_btree_aerase(n->data.leaf.vals, --n->n_vals, 0); + return zix_btree_aerase(n->data.leaf.vals, --n->n_vals, 0); } /** Remove and return the max value from the subtree rooted at `n`. */ -ZIX_PRIVATE void* +ZIX_PRIVATE +void* zix_btree_remove_max(ZixBTree* const t, ZixBTreeNode* n) { - while (!n->is_leaf) { - if (zix_btree_node_is_minimal(zix_btree_child(n, n->n_vals))) { - // Leftmost child is minimal, must expand - if (!zix_btree_node_is_minimal(zix_btree_child(n, n->n_vals - 1))) { - // Child's left sibling has at least one key to steal - n = zix_btree_rotate_right(n, n->n_vals); - } else { - // Both child and left sibling are minimal, merge - n = zix_btree_merge(t, n, n->n_vals - 1U); - } - } else { - n = zix_btree_child(n, n->n_vals); - } - } + while (!n->is_leaf) { + if (zix_btree_node_is_minimal(zix_btree_child(n, n->n_vals))) { + // Leftmost child is minimal, must expand + if (!zix_btree_node_is_minimal(zix_btree_child(n, n->n_vals - 1))) { + // Child's left sibling has at least one key to steal + n = zix_btree_rotate_right(n, n->n_vals); + } else { + // Both child and left sibling are minimal, merge + n = zix_btree_merge(t, n, n->n_vals - 1U); + } + } else { + n = zix_btree_child(n, n->n_vals); + } + } - return n->data.leaf.vals[--n->n_vals]; + return n->data.leaf.vals[--n->n_vals]; } ZixStatus @@ -608,123 +620,120 @@ zix_btree_remove(ZixBTree* const t, void** const out, ZixBTreeIter** const next) { - ZixBTreeNode* n = t->root; - ZixBTreeIter* ti = NULL; - const bool user_iter = next && *next; - if (next) { - if (!*next && !(*next = zix_btree_iter_new(t))) { - return ZIX_STATUS_NO_MEM; - } - ti = *next; - ti->level = 0; - } - - while (true) { - /* To remove in a single walk down, the tree is adjusted along the way - so that the current node always has at least one more value than the - minimum required in general. Thus, there is always room to remove - without adjusting on the way back up. */ - assert(n == t->root || !zix_btree_node_is_minimal(n)); - - bool equal = false; - const unsigned i = zix_btree_node_find(t, n, e, &equal); - zix_btree_iter_set_frame(ti, n, i); - if (n->is_leaf) { - if (equal) { - // Found in leaf node - *out = zix_btree_aerase(n->data.leaf.vals, --n->n_vals, i); - if (ti && i == n->n_vals) { - if (i == 0) { - ti->level = 0; - ti->stack[0].node = NULL; - } else { - --ti->stack[ti->level].index; - zix_btree_iter_increment(ti); - } - } - --t->size; - return ZIX_STATUS_SUCCESS; - } - - // Not found in leaf node, or tree - if (ti && !user_iter) { - zix_btree_iter_free(ti); - *next = NULL; - } - - return ZIX_STATUS_NOT_FOUND; - } - - if (equal) { - // Found in internal node - ZixBTreeNode* const lhs = zix_btree_child(n, i); - ZixBTreeNode* const rhs = zix_btree_child(n, i + 1); - const size_t l_size = lhs->n_vals; - const size_t r_size = rhs->n_vals; - if (zix_btree_node_is_minimal(lhs) && - zix_btree_node_is_minimal(rhs)) { - // Both preceding and succeeding child are minimal - n = zix_btree_merge(t, n, i); - } else if (l_size >= r_size) { - // Left child can remove without merge - assert(!zix_btree_node_is_minimal(lhs)); - *out = n->data.inode.vals[i]; - n->data.inode.vals[i] = zix_btree_remove_max(t, lhs); - --t->size; - return ZIX_STATUS_SUCCESS; - } else { - // Right child can remove without merge - assert(!zix_btree_node_is_minimal(rhs)); - *out = n->data.inode.vals[i]; - n->data.inode.vals[i] = zix_btree_remove_min(t, rhs); - --t->size; - return ZIX_STATUS_SUCCESS; - } - } else { - // Not found in internal node, key is in/under children[i] - if (zix_btree_node_is_minimal(zix_btree_child(n, i))) { - if (i > 0 && - !zix_btree_node_is_minimal(zix_btree_child(n, i - 1))) { - // Steal a key from child's left sibling - n = zix_btree_rotate_right(n, i); - } else if (i < n->n_vals && - !zix_btree_node_is_minimal( - zix_btree_child(n, i + 1))) { - // Steal a key from child's right sibling - n = zix_btree_rotate_left(n, i); - } else if (n == t->root && n->n_vals == 1) { - // Root has two children, both minimal, delete it - assert(i == 0 || i == 1); - const uint16_t counts[2] = {zix_btree_child(n, 0)->n_vals, - zix_btree_child(n, 1)->n_vals}; - - n = zix_btree_merge(t, n, 0); - if (ti) { - ti->stack[ti->level].node = n; - ti->stack[ti->level].index = counts[i]; - } - } else { - // Both child's siblings are minimal, merge them - if (i < n->n_vals) { - n = zix_btree_merge(t, n, i); - } else { - n = zix_btree_merge(t, n, i - 1U); - if (ti) { - --ti->stack[ti->level].index; - } - } - } - } else { - n = zix_btree_child(n, i); - } - } - if (ti) { - ++ti->level; - } - } - - assert(false); // Not reached - return ZIX_STATUS_ERROR; + ZixBTreeNode* n = t->root; + ZixBTreeIter* ti = NULL; + const bool user_iter = next && *next; + if (next) { + if (!*next && !(*next = zix_btree_iter_new(t))) { + return ZIX_STATUS_NO_MEM; + } + ti = *next; + ti->level = 0; + } + + while (true) { + /* To remove in a single walk down, the tree is adjusted along the way + so that the current node always has at least one more value than the + minimum required in general. Thus, there is always room to remove + without adjusting on the way back up. */ + assert(n == t->root || !zix_btree_node_is_minimal(n)); + + bool equal = false; + const unsigned i = zix_btree_node_find(t, n, e, &equal); + zix_btree_iter_set_frame(ti, n, i); + if (n->is_leaf) { + if (equal) { + // Found in leaf node + *out = zix_btree_aerase(n->data.leaf.vals, --n->n_vals, i); + if (ti && i == n->n_vals) { + if (i == 0) { + ti->level = 0; + ti->stack[0].node = NULL; + } else { + --ti->stack[ti->level].index; + zix_btree_iter_increment(ti); + } + } + --t->size; + return ZIX_STATUS_SUCCESS; + } + + // Not found in leaf node, or tree + if (ti && !user_iter) { + zix_btree_iter_free(ti); + *next = NULL; + } + + return ZIX_STATUS_NOT_FOUND; + } + + if (equal) { + // Found in internal node + ZixBTreeNode* const lhs = zix_btree_child(n, i); + ZixBTreeNode* const rhs = zix_btree_child(n, i + 1); + const size_t l_size = lhs->n_vals; + const size_t r_size = rhs->n_vals; + if (zix_btree_node_is_minimal(lhs) && zix_btree_node_is_minimal(rhs)) { + // Both preceding and succeeding child are minimal + n = zix_btree_merge(t, n, i); + } else if (l_size >= r_size) { + // Left child can remove without merge + assert(!zix_btree_node_is_minimal(lhs)); + *out = n->data.inode.vals[i]; + n->data.inode.vals[i] = zix_btree_remove_max(t, lhs); + --t->size; + return ZIX_STATUS_SUCCESS; + } else { + // Right child can remove without merge + assert(!zix_btree_node_is_minimal(rhs)); + *out = n->data.inode.vals[i]; + n->data.inode.vals[i] = zix_btree_remove_min(t, rhs); + --t->size; + return ZIX_STATUS_SUCCESS; + } + } else { + // Not found in internal node, key is in/under children[i] + if (zix_btree_node_is_minimal(zix_btree_child(n, i))) { + if (i > 0 && !zix_btree_node_is_minimal(zix_btree_child(n, i - 1))) { + // Steal a key from child's left sibling + n = zix_btree_rotate_right(n, i); + } else if (i < n->n_vals && + !zix_btree_node_is_minimal(zix_btree_child(n, i + 1))) { + // Steal a key from child's right sibling + n = zix_btree_rotate_left(n, i); + } else if (n == t->root && n->n_vals == 1) { + // Root has two children, both minimal, delete it + assert(i == 0 || i == 1); + const uint16_t counts[2] = {zix_btree_child(n, 0)->n_vals, + zix_btree_child(n, 1)->n_vals}; + + n = zix_btree_merge(t, n, 0); + if (ti) { + ti->stack[ti->level].node = n; + ti->stack[ti->level].index = counts[i]; + } + } else { + // Both child's siblings are minimal, merge them + if (i < n->n_vals) { + n = zix_btree_merge(t, n, i); + } else { + n = zix_btree_merge(t, n, i - 1U); + if (ti) { + --ti->stack[ti->level].index; + } + } + } + } else { + n = zix_btree_child(n, i); + } + } + if (ti) { + ++ti->level; + } + } + + assert(false); // Not reached + return ZIX_STATUS_ERROR; } ZixStatus @@ -732,32 +741,32 @@ zix_btree_find(const ZixBTree* const t, const void* const e, ZixBTreeIter** const ti) { - ZixBTreeNode* n = t->root; - if (!(*ti = zix_btree_iter_new(t))) { - return ZIX_STATUS_NO_MEM; - } + ZixBTreeNode* n = t->root; + if (!(*ti = zix_btree_iter_new(t))) { + return ZIX_STATUS_NO_MEM; + } - while (n) { - bool equal = false; - const unsigned i = zix_btree_node_find(t, n, e, &equal); + while (n) { + bool equal = false; + const unsigned i = zix_btree_node_find(t, n, e, &equal); - zix_btree_iter_set_frame(*ti, n, i); + zix_btree_iter_set_frame(*ti, n, i); - if (equal) { - return ZIX_STATUS_SUCCESS; - } + if (equal) { + return ZIX_STATUS_SUCCESS; + } - if (n->is_leaf) { - break; - } + if (n->is_leaf) { + break; + } - ++(*ti)->level; - n = zix_btree_child(n, i); - } + ++(*ti)->level; + n = zix_btree_child(n, i); + } - zix_btree_iter_free(*ti); - *ti = NULL; - return ZIX_STATUS_NOT_FOUND; + zix_btree_iter_free(*ti); + *ti = NULL; + return ZIX_STATUS_NOT_FOUND; } ZixStatus @@ -765,181 +774,184 @@ zix_btree_lower_bound(const ZixBTree* const t, const void* const e, ZixBTreeIter** const ti) { - if (!t) { - *ti = NULL; - return ZIX_STATUS_BAD_ARG; - } - - if (!t->root) { - *ti = NULL; - return ZIX_STATUS_SUCCESS; - } - - ZixBTreeNode* n = t->root; - bool found = false; - unsigned found_level = 0; - if (!(*ti = zix_btree_iter_new(t))) { - return ZIX_STATUS_NO_MEM; - } - - while (n) { - bool equal = false; - const unsigned i = zix_btree_node_find(t, n, e, &equal); - - zix_btree_iter_set_frame(*ti, n, i); - - if (equal) { - found_level = (*ti)->level; - found = true; - } - - if (n->is_leaf) { - break; - } - - ++(*ti)->level; - n = zix_btree_child(n, i); - assert(n); - } - - const ZixBTreeIterFrame* const frame = &(*ti)->stack[(*ti)->level]; - assert(frame->node); - if (frame->index == frame->node->n_vals) { - if (found) { - // Found on a previous level but went too far - (*ti)->level = found_level; - } else { - // Reached end (key is greater than everything in tree) - (*ti)->level = 0; - (*ti)->stack[0].node = NULL; - } - } - - return ZIX_STATUS_SUCCESS; + if (!t) { + *ti = NULL; + return ZIX_STATUS_BAD_ARG; + } + + if (!t->root) { + *ti = NULL; + return ZIX_STATUS_SUCCESS; + } + + ZixBTreeNode* n = t->root; + bool found = false; + unsigned found_level = 0; + if (!(*ti = zix_btree_iter_new(t))) { + return ZIX_STATUS_NO_MEM; + } + + while (n) { + bool equal = false; + const unsigned i = zix_btree_node_find(t, n, e, &equal); + + zix_btree_iter_set_frame(*ti, n, i); + + if (equal) { + found_level = (*ti)->level; + found = true; + } + + if (n->is_leaf) { + break; + } + + ++(*ti)->level; + n = zix_btree_child(n, i); + assert(n); + } + + const ZixBTreeIterFrame* const frame = &(*ti)->stack[(*ti)->level]; + assert(frame->node); + if (frame->index == frame->node->n_vals) { + if (found) { + // Found on a previous level but went too far + (*ti)->level = found_level; + } else { + // Reached end (key is greater than everything in tree) + (*ti)->level = 0; + (*ti)->stack[0].node = NULL; + } + } + + return ZIX_STATUS_SUCCESS; } void* zix_btree_get(const ZixBTreeIter* const ti) { - const ZixBTreeIterFrame* const frame = &ti->stack[ti->level]; - assert(frame->node); - assert(frame->index < frame->node->n_vals); - return zix_btree_value(frame->node, frame->index); + const ZixBTreeIterFrame* const frame = &ti->stack[ti->level]; + assert(frame->node); + assert(frame->index < frame->node->n_vals); + return zix_btree_value(frame->node, frame->index); } ZixBTreeIter* zix_btree_begin(const ZixBTree* const t) { - ZixBTreeIter* const i = zix_btree_iter_new(t); - if (!i) { - return NULL; - } - - if (t->size == 0) { - i->level = 0; - i->stack[0].node = NULL; - } else { - ZixBTreeNode* n = t->root; - i->stack[0].node = n; - i->stack[0].index = 0; - while (!n->is_leaf) { - n = zix_btree_child(n, 0); - ++i->level; - i->stack[i->level].node = n; - i->stack[i->level].index = 0; - } - } - return i; + ZixBTreeIter* const i = zix_btree_iter_new(t); + if (!i) { + return NULL; + } + + if (t->size == 0) { + i->level = 0; + i->stack[0].node = NULL; + } else { + ZixBTreeNode* n = t->root; + i->stack[0].node = n; + i->stack[0].index = 0; + while (!n->is_leaf) { + n = zix_btree_child(n, 0); + ++i->level; + i->stack[i->level].node = n; + i->stack[i->level].index = 0; + } + } + + return i; } ZixBTreeIter* zix_btree_end(const ZixBTree* const t) { - return zix_btree_iter_new(t); + return zix_btree_iter_new(t); } ZixBTreeIter* zix_btree_iter_copy(const ZixBTreeIter* const i) { - if (!i) { - return NULL; - } + if (!i) { + return NULL; + } + + const size_t s = i->n_levels * sizeof(ZixBTreeIterFrame); + ZixBTreeIter* j = (ZixBTreeIter*)calloc(1, sizeof(ZixBTreeIter) + s); + if (j) { + memcpy(j, i, sizeof(ZixBTreeIter) + s); + } - const size_t s = i->n_levels * sizeof(ZixBTreeIterFrame); - ZixBTreeIter* j = (ZixBTreeIter*)calloc(1, sizeof(ZixBTreeIter) + s); - if (j) { - memcpy(j, i, sizeof(ZixBTreeIter) + s); - } - return j; + return j; } bool zix_btree_iter_is_end(const ZixBTreeIter* const i) { - return !i || i->stack[0].node == NULL; + return !i || i->stack[0].node == NULL; } bool -zix_btree_iter_equals(const ZixBTreeIter* const lhs, const ZixBTreeIter* const rhs) +zix_btree_iter_equals(const ZixBTreeIter* const lhs, + const ZixBTreeIter* const rhs) { - if (zix_btree_iter_is_end(lhs) && zix_btree_iter_is_end(rhs)) { - return true; - } + if (zix_btree_iter_is_end(lhs) && zix_btree_iter_is_end(rhs)) { + return true; + } - if (zix_btree_iter_is_end(lhs) || zix_btree_iter_is_end(rhs) || - lhs->level != rhs->level) { - return false; - } + if (zix_btree_iter_is_end(lhs) || zix_btree_iter_is_end(rhs) || + lhs->level != rhs->level) { + return false; + } - return !memcmp(lhs, - rhs, - sizeof(ZixBTreeIter) + - (lhs->level + 1) * sizeof(ZixBTreeIterFrame)); + return !memcmp(lhs, + rhs, + sizeof(ZixBTreeIter) + + (lhs->level + 1) * sizeof(ZixBTreeIterFrame)); } void zix_btree_iter_increment(ZixBTreeIter* const i) { - ZixBTreeIterFrame* f = &i->stack[i->level]; - if (f->node->is_leaf) { - // Leaf, move right - assert(f->index < f->node->n_vals); - if (++f->index == f->node->n_vals) { - // Reached end of leaf, move up - f = &i->stack[i->level]; - while (i->level > 0 && f->index == f->node->n_vals) { - f = &i->stack[--i->level]; - assert(f->index <= f->node->n_vals); - } - - if (f->index == f->node->n_vals) { - // Reached end of tree - assert(i->level == 0); - f->node = NULL; - f->index = 0; - } - } - } else { - // Internal node, move down to next child - assert(f->index < f->node->n_vals); - ZixBTreeNode* child = zix_btree_child(f->node, ++f->index); - - f = &i->stack[++i->level]; - f->node = child; - f->index = 0; - - // Move down and left until we hit a leaf - while (!f->node->is_leaf) { - child = zix_btree_child(f->node, 0); - f = &i->stack[++i->level]; - f->node = child; - f->index = 0; - } - } + ZixBTreeIterFrame* f = &i->stack[i->level]; + if (f->node->is_leaf) { + // Leaf, move right + assert(f->index < f->node->n_vals); + if (++f->index == f->node->n_vals) { + // Reached end of leaf, move up + f = &i->stack[i->level]; + while (i->level > 0 && f->index == f->node->n_vals) { + f = &i->stack[--i->level]; + assert(f->index <= f->node->n_vals); + } + + if (f->index == f->node->n_vals) { + // Reached end of tree + assert(i->level == 0); + f->node = NULL; + f->index = 0; + } + } + } else { + // Internal node, move down to next child + assert(f->index < f->node->n_vals); + ZixBTreeNode* child = zix_btree_child(f->node, ++f->index); + + f = &i->stack[++i->level]; + f->node = child; + f->index = 0; + + // Move down and left until we hit a leaf + while (!f->node->is_leaf) { + child = zix_btree_child(f->node, 0); + f = &i->stack[++i->level]; + f->node = child; + f->index = 0; + } + } } void zix_btree_iter_free(ZixBTreeIter* const i) { - free(i); + free(i); } diff --git a/zix/btree.h b/zix/btree.h index c1610a8..dde659f 100644 --- a/zix/btree.h +++ b/zix/btree.h @@ -54,27 +54,29 @@ typedef struct ZixBTreeIterImpl ZixBTreeIter; /** Create a new (empty) B-Tree. */ -ZIX_API ZixBTree* -zix_btree_new(ZixComparator cmp, - const void* cmp_data, - ZixDestroyFunc destroy); +ZIX_API +ZixBTree* +zix_btree_new(ZixComparator cmp, const void* cmp_data, ZixDestroyFunc destroy); /** Free `t`. */ -ZIX_API void +ZIX_API +void zix_btree_free(ZixBTree* t); /** Return the number of elements in `t`. */ -ZIX_PURE_API size_t +ZIX_PURE_API +size_t zix_btree_size(const ZixBTree* t); /** Insert the element `e` into `t`. */ -ZIX_API ZixStatus +ZIX_API +ZixStatus zix_btree_insert(ZixBTree* t, void* e); /** @@ -90,14 +92,16 @@ zix_btree_insert(ZixBTree* t, void* e); also non-NULL, the iterator is reused, otherwise a new one is allocated. To reuse an iterator, no items may have been added since its creation. */ -ZIX_API ZixStatus +ZIX_API +ZixStatus zix_btree_remove(ZixBTree* t, const void* e, void** out, ZixBTreeIter** next); /** Set `ti` to an element equal to `e` in `t`. If no such item exists, `ti` is set to NULL. */ -ZIX_API ZixStatus +ZIX_API +ZixStatus zix_btree_find(const ZixBTree* t, const void* e, ZixBTreeIter** ti); /** @@ -107,13 +111,15 @@ zix_btree_find(const ZixBTree* t, const void* e, ZixBTreeIter** ti); values in the tree, `ti` will be set to the least such element. The search key `e` is always passed as the second argument to the comparator. */ -ZIX_API ZixStatus +ZIX_API +ZixStatus zix_btree_lower_bound(const ZixBTree* t, const void* e, ZixBTreeIter** ti); /** Return the data associated with the given tree item. */ -ZIX_PURE_API void* +ZIX_PURE_API +void* zix_btree_get(const ZixBTreeIter* ti); /** @@ -121,7 +127,8 @@ zix_btree_get(const ZixBTreeIter* ti); The returned iterator must be freed with zix_btree_iter_free(). */ -ZIX_PURE_API ZixBTreeIter* +ZIX_PURE_API +ZixBTreeIter* zix_btree_begin(const ZixBTree* t); /** @@ -129,37 +136,43 @@ zix_btree_begin(const ZixBTree* t); The returned iterator must be freed with zix_btree_iter_free(). */ -ZIX_API ZixBTreeIter* +ZIX_API +ZixBTreeIter* zix_btree_end(const ZixBTree* t); /** Return a new copy of `i`. */ -ZIX_API ZixBTreeIter* +ZIX_API +ZixBTreeIter* zix_btree_iter_copy(const ZixBTreeIter* i); /** Return true iff `lhs` is equal to `rhs`. */ -ZIX_PURE_API bool +ZIX_PURE_API +bool zix_btree_iter_equals(const ZixBTreeIter* lhs, const ZixBTreeIter* rhs); /** Return true iff `i` is an iterator to the end of its tree. */ -ZIX_PURE_API bool +ZIX_PURE_API +bool zix_btree_iter_is_end(const ZixBTreeIter* i); /** Increment `i` to point to the next element in the tree. */ -ZIX_API void +ZIX_API +void zix_btree_iter_increment(ZixBTreeIter* i); /** Free `i`. */ -ZIX_API void +ZIX_API +void zix_btree_iter_free(ZixBTreeIter* i); /** @@ -168,7 +181,7 @@ zix_btree_iter_free(ZixBTreeIter* i); */ #ifdef __cplusplus -} /* extern "C" */ +} /* extern "C" */ #endif -#endif /* ZIX_BTREE_H */ +#endif /* ZIX_BTREE_H */ diff --git a/zix/chunk.c b/zix/chunk.c index 1254d14..bf80f88 100644 --- a/zix/chunk.c +++ b/zix/chunk.c @@ -23,11 +23,11 @@ uint32_t zix_chunk_hash(const ZixChunk* const chunk) { - return zix_digest_add(zix_digest_start(), chunk->buf, chunk->len); + return zix_digest_add(zix_digest_start(), chunk->buf, chunk->len); } bool zix_chunk_equal(const ZixChunk* a, const ZixChunk* b) { - return a->len == b->len && !memcmp(a->buf, b->buf, a->len); + return a->len == b->len && !memcmp(a->buf, b->buf, a->len); } diff --git a/zix/chunk.h b/zix/chunk.h index 193e537..3646718 100644 --- a/zix/chunk.h +++ b/zix/chunk.h @@ -31,18 +31,20 @@ extern "C" { A chunk of memory. */ typedef struct { - void* buf; /**< Start of memory chunk */ - size_t len; /**< Length of memory chunk */ + void* buf; /**< Start of memory chunk */ + size_t len; /**< Length of memory chunk */ } ZixChunk; -ZIX_PURE_API uint32_t +ZIX_PURE_API +uint32_t zix_chunk_hash(const ZixChunk* chunk); -ZIX_PURE_API bool +ZIX_PURE_API +bool zix_chunk_equal(const ZixChunk* a, const ZixChunk* b); #ifdef __cplusplus -} /* extern "C" */ +} /* extern "C" */ #endif -#endif /* ZIX_CHUNK_H */ +#endif /* ZIX_CHUNK_H */ diff --git a/zix/common.h b/zix/common.h index f7ec4c3..865d232 100644 --- a/zix/common.h +++ b/zix/common.h @@ -26,40 +26,48 @@ /** @cond */ #ifdef ZIX_SHARED -# ifdef _WIN32 -# define ZIX_LIB_IMPORT __declspec(dllimport) -# define ZIX_LIB_EXPORT __declspec(dllexport) -# else -# define ZIX_LIB_IMPORT __attribute__((visibility("default"))) -# define ZIX_LIB_EXPORT __attribute__((visibility("default"))) -# endif -# ifdef ZIX_INTERNAL -# define ZIX_API ZIX_LIB_EXPORT -# else -# define ZIX_API ZIX_LIB_IMPORT -# endif -# define ZIX_PRIVATE static +# ifdef _WIN32 +# define ZIX_LIB_IMPORT __declspec(dllimport) +# define ZIX_LIB_EXPORT __declspec(dllexport) +# else +# define ZIX_LIB_IMPORT __attribute__((visibility("default"))) +# define ZIX_LIB_EXPORT __attribute__((visibility("default"))) +# endif +# ifdef ZIX_INTERNAL +# define ZIX_API ZIX_LIB_EXPORT +# else +# define ZIX_API ZIX_LIB_IMPORT +# endif +# define ZIX_PRIVATE static #elif defined(ZIX_INLINE) -# define ZIX_API static inline -# define ZIX_PRIVATE static inline +# define ZIX_API static inline +# define ZIX_PRIVATE static inline #else -# define ZIX_API -# define ZIX_PRIVATE static +# define ZIX_API +# define ZIX_PRIVATE static #endif #ifdef __GNUC__ -# define ZIX_PURE_FUNC __attribute__((pure)) -# define ZIX_CONST_FUNC __attribute__((const)) -# define ZIX_MALLOC_FUNC __attribute__((malloc)) +# define ZIX_PURE_FUNC __attribute__((pure)) +# define ZIX_CONST_FUNC __attribute__((const)) +# define ZIX_MALLOC_FUNC __attribute__((malloc)) #else -# define ZIX_PURE_FUNC -# define ZIX_CONST_FUNC -# define ZIX_MALLOC_FUNC +# define ZIX_PURE_FUNC +# define ZIX_CONST_FUNC +# define ZIX_MALLOC_FUNC #endif -#define ZIX_PURE_API ZIX_API ZIX_PURE_FUNC -#define ZIX_CONST_API ZIX_API ZIX_CONST_FUNC -#define ZIX_MALLOC_API ZIX_API ZIX_MALLOC_FUNC +#define ZIX_PURE_API \ + ZIX_API \ + ZIX_PURE_FUNC + +#define ZIX_CONST_API \ + ZIX_API \ + ZIX_CONST_FUNC + +#define ZIX_MALLOC_API \ + ZIX_API \ + ZIX_MALLOC_FUNC /** @endcond */ @@ -68,43 +76,50 @@ extern "C" { #endif #ifdef __GNUC__ -#define ZIX_LOG_FUNC(fmt, arg1) __attribute__((format(printf, fmt, arg1))) +# define ZIX_LOG_FUNC(fmt, arg1) __attribute__((format(printf, fmt, arg1))) #else -#define ZIX_LOG_FUNC(fmt, arg1) +# define ZIX_LOG_FUNC(fmt, arg1) #endif // Unused parameter macro to suppresses warnings and make it impossible to use #if defined(__cplusplus) -# define ZIX_UNUSED(name) +# define ZIX_UNUSED(name) #elif defined(__GNUC__) -# define ZIX_UNUSED(name) name##_unused __attribute__((__unused__)) +# define ZIX_UNUSED(name) name##_unused __attribute__((__unused__)) #else -# define ZIX_UNUSED(name) name +# define ZIX_UNUSED(name) name #endif typedef enum { - ZIX_STATUS_SUCCESS, - ZIX_STATUS_ERROR, - ZIX_STATUS_NO_MEM, - ZIX_STATUS_NOT_FOUND, - ZIX_STATUS_EXISTS, - ZIX_STATUS_BAD_ARG, - ZIX_STATUS_BAD_PERMS + ZIX_STATUS_SUCCESS, + ZIX_STATUS_ERROR, + ZIX_STATUS_NO_MEM, + ZIX_STATUS_NOT_FOUND, + ZIX_STATUS_EXISTS, + ZIX_STATUS_BAD_ARG, + ZIX_STATUS_BAD_PERMS } ZixStatus; static inline const char* zix_strerror(const ZixStatus status) { - switch (status) { - case ZIX_STATUS_SUCCESS: return "Success"; - case ZIX_STATUS_ERROR: return "Unknown error"; - case ZIX_STATUS_NO_MEM: return "Out of memory"; - case ZIX_STATUS_NOT_FOUND: return "Not found"; - case ZIX_STATUS_EXISTS: return "Exists"; - case ZIX_STATUS_BAD_ARG: return "Bad argument"; - case ZIX_STATUS_BAD_PERMS: return "Bad permissions"; - } - return "Unknown error"; + switch (status) { + case ZIX_STATUS_SUCCESS: + return "Success"; + case ZIX_STATUS_ERROR: + return "Unknown error"; + case ZIX_STATUS_NO_MEM: + return "Out of memory"; + case ZIX_STATUS_NOT_FOUND: + return "Not found"; + case ZIX_STATUS_EXISTS: + return "Exists"; + case ZIX_STATUS_BAD_ARG: + return "Bad argument"; + case ZIX_STATUS_BAD_PERMS: + return "Bad permissions"; + } + return "Unknown error"; } /** @@ -129,7 +144,7 @@ typedef void (*ZixDestroyFunc)(void* ptr); */ #ifdef __cplusplus -} /* extern "C" */ +} /* extern "C" */ #endif -#endif /* ZIX_COMMON_H */ +#endif /* ZIX_COMMON_H */ diff --git a/zix/digest.c b/zix/digest.c index 03a1210..941b05c 100644 --- a/zix/digest.c +++ b/zix/digest.c @@ -17,7 +17,7 @@ #include "zix/digest.h" #ifdef __SSE4_2__ -# include <smmintrin.h> +# include <smmintrin.h> #endif #include <assert.h> @@ -30,75 +30,75 @@ uint32_t zix_digest_start(void) { - return 1; + return 1; } uint32_t zix_digest_add(uint32_t hash, const void* const buf, const size_t len) { - const uint8_t* str = (const uint8_t*)buf; - -#ifdef __x86_64__ - for (size_t i = 0; i < (len / sizeof(uint64_t)); ++i) { - hash = (uint32_t)_mm_crc32_u64(hash, *(const uint64_t*)str); - str += sizeof(uint64_t); - } - if (len & sizeof(uint32_t)) { - hash = _mm_crc32_u32(hash, *(const uint32_t*)str); - str += sizeof(uint32_t); - } -#else - for (size_t i = 0; i < (len / sizeof(uint32_t)); ++i) { - hash = _mm_crc32_u32(hash, *(const uint32_t*)str); - str += sizeof(uint32_t); - } -#endif - if (len & sizeof(uint16_t)) { - hash = _mm_crc32_u16(hash, *(const uint16_t*)str); - str += sizeof(uint16_t); - } - if (len & sizeof(uint8_t)) { - hash = _mm_crc32_u8(hash, *(const uint8_t*)str); - } - - return hash; + const uint8_t* str = (const uint8_t*)buf; + +# ifdef __x86_64__ + for (size_t i = 0; i < (len / sizeof(uint64_t)); ++i) { + hash = (uint32_t)_mm_crc32_u64(hash, *(const uint64_t*)str); + str += sizeof(uint64_t); + } + if (len & sizeof(uint32_t)) { + hash = _mm_crc32_u32(hash, *(const uint32_t*)str); + str += sizeof(uint32_t); + } +# else + for (size_t i = 0; i < (len / sizeof(uint32_t)); ++i) { + hash = _mm_crc32_u32(hash, *(const uint32_t*)str); + str += sizeof(uint32_t); + } +# endif + if (len & sizeof(uint16_t)) { + hash = _mm_crc32_u16(hash, *(const uint16_t*)str); + str += sizeof(uint16_t); + } + if (len & sizeof(uint8_t)) { + hash = _mm_crc32_u8(hash, *(const uint8_t*)str); + } + + return hash; } uint32_t zix_digest_add_64(uint32_t hash, const void* const buf, const size_t len) { - assert((uintptr_t)buf % sizeof(uint64_t) == 0); - assert(len % sizeof(uint64_t) == 0); + assert((uintptr_t)buf % sizeof(uint64_t) == 0); + assert(len % sizeof(uint64_t) == 0); -#ifdef __x86_64__ - const uint64_t* ptr = (const uint64_t*)buf; +# ifdef __x86_64__ + const uint64_t* ptr = (const uint64_t*)buf; - for (size_t i = 0; i < (len / sizeof(uint64_t)); ++i) { - hash = (uint32_t)_mm_crc32_u64(hash, *ptr); - ++ptr; - } + for (size_t i = 0; i < (len / sizeof(uint64_t)); ++i) { + hash = (uint32_t)_mm_crc32_u64(hash, *ptr); + ++ptr; + } - return hash; -#else - const uint32_t* ptr = (const uint32_t*)buf; + return hash; +# else + const uint32_t* ptr = (const uint32_t*)buf; - for (size_t i = 0; i < (len / sizeof(uint32_t)); ++i) { - hash = _mm_crc32_u32(hash, *ptr); - ++ptr; - } + for (size_t i = 0; i < (len / sizeof(uint32_t)); ++i) { + hash = _mm_crc32_u32(hash, *ptr); + ++ptr; + } - return hash; -#endif + return hash; +# endif } uint32_t zix_digest_add_ptr(const uint32_t hash, const void* const ptr) { -#ifdef __x86_64__ - return (uint32_t)_mm_crc32_u64(hash, (uintptr_t)ptr); -#else - return _mm_crc32_u32(hash, (uintptr_t)ptr); -#endif +# ifdef __x86_64__ + return (uint32_t)_mm_crc32_u64(hash, (uintptr_t)ptr); +# else + return _mm_crc32_u32(hash, (uintptr_t)ptr); +# endif } #else @@ -108,34 +108,34 @@ zix_digest_add_ptr(const uint32_t hash, const void* const ptr) uint32_t zix_digest_start(void) { - return 5381; + return 5381; } uint32_t zix_digest_add(uint32_t hash, const void* const buf, const size_t len) { - const uint8_t* str = (const uint8_t*)buf; + const uint8_t* str = (const uint8_t*)buf; - for (size_t i = 0; i < len; ++i) { - hash = (hash << 5u) + hash + str[i]; - } + for (size_t i = 0; i < len; ++i) { + hash = (hash << 5u) + hash + str[i]; + } - return hash; + return hash; } uint32_t zix_digest_add_64(uint32_t hash, const void* const buf, const size_t len) { - assert((uintptr_t)buf % sizeof(uint64_t) == 0); - assert(len % sizeof(uint64_t) == 0); + assert((uintptr_t)buf % sizeof(uint64_t) == 0); + assert(len % sizeof(uint64_t) == 0); - return zix_digest_add(hash, buf, len); + return zix_digest_add(hash, buf, len); } uint32_t zix_digest_add_ptr(const uint32_t hash, const void* const ptr) { - return zix_digest_add(hash, &ptr, sizeof(ptr)); + return zix_digest_add(hash, &ptr, sizeof(ptr)); } #endif diff --git a/zix/digest.h b/zix/digest.h index c9f3ec0..7d44c3d 100644 --- a/zix/digest.h +++ b/zix/digest.h @@ -29,7 +29,8 @@ extern "C" { /** Return an initial empty digest value. */ -ZIX_CONST_API uint32_t +ZIX_CONST_API +uint32_t zix_digest_start(void); /** @@ -37,7 +38,8 @@ zix_digest_start(void); This can be used for any size or alignment. */ -ZIX_PURE_API uint32_t +ZIX_PURE_API +uint32_t zix_digest_add(uint32_t hash, const void* buf, size_t len); /** @@ -45,7 +47,8 @@ zix_digest_add(uint32_t hash, const void* buf, size_t len); Both `buf` and `len` must be evenly divisible by 8 (64 bits). */ -ZIX_PURE_API uint32_t +ZIX_PURE_API +uint32_t zix_digest_add_64(uint32_t hash, const void* buf, size_t len); /** @@ -53,11 +56,12 @@ zix_digest_add_64(uint32_t hash, const void* buf, size_t len); This hashes the value of the pointer itself, and does not dereference `ptr`. */ -ZIX_CONST_API uint32_t +ZIX_CONST_API +uint32_t zix_digest_add_ptr(uint32_t hash, const void* ptr); #ifdef __cplusplus -} /* extern "C" */ +} /* extern "C" */ #endif -#endif /* ZIX_DIGEST_H */ +#endif /* ZIX_DIGEST_H */ @@ -25,109 +25,107 @@ from powers of two as possible. */ static const unsigned sizes[] = { - 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, - 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, - 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 0 -}; + 53, 97, 193, 389, 769, 1543, 3079, + 6151, 12289, 24593, 49157, 98317, 196613, 393241, + 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, + 100663319, 201326611, 402653189, 805306457, 1610612741, 0}; typedef struct ZixHashEntry { - struct ZixHashEntry* next; ///< Next entry in bucket - uint32_t hash; ///< Non-modulo hash value - // Value follows here (access with zix_hash_value) + struct ZixHashEntry* next; ///< Next entry in bucket + uint32_t hash; ///< Non-modulo hash value + // Value follows here (access with zix_hash_value) } ZixHashEntry; struct ZixHashImpl { - ZixHashFunc hash_func; - ZixEqualFunc equal_func; - ZixHashEntry** buckets; - const unsigned* n_buckets; - size_t value_size; - unsigned count; + ZixHashFunc hash_func; + ZixEqualFunc equal_func; + ZixHashEntry** buckets; + const unsigned* n_buckets; + size_t value_size; + unsigned count; }; static inline void* zix_hash_value(ZixHashEntry* entry) { - return entry + 1; + return entry + 1; } ZixHash* -zix_hash_new(ZixHashFunc hash_func, - ZixEqualFunc equal_func, - size_t value_size) +zix_hash_new(ZixHashFunc hash_func, ZixEqualFunc equal_func, size_t value_size) { - ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash)); - if (hash) { - hash->hash_func = hash_func; - hash->equal_func = equal_func; - hash->n_buckets = &sizes[0]; - hash->value_size = value_size; - hash->count = 0; - if (!(hash->buckets = (ZixHashEntry**)calloc(*hash->n_buckets, - sizeof(ZixHashEntry*)))) { - free(hash); - return NULL; - } - } - return hash; + ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash)); + if (hash) { + hash->hash_func = hash_func; + hash->equal_func = equal_func; + hash->n_buckets = &sizes[0]; + hash->value_size = value_size; + hash->count = 0; + if (!(hash->buckets = + (ZixHashEntry**)calloc(*hash->n_buckets, sizeof(ZixHashEntry*)))) { + free(hash); + return NULL; + } + } + return hash; } void zix_hash_free(ZixHash* hash) { - if (!hash) { - return; - } - - for (unsigned b = 0; b < *hash->n_buckets; ++b) { - ZixHashEntry* bucket = hash->buckets[b]; - for (ZixHashEntry* e = bucket; e;) { - ZixHashEntry* next = e->next; - free(e); - e = next; - } - } - - free(hash->buckets); - free(hash); + if (!hash) { + return; + } + + for (unsigned b = 0; b < *hash->n_buckets; ++b) { + ZixHashEntry* bucket = hash->buckets[b]; + for (ZixHashEntry* e = bucket; e;) { + ZixHashEntry* next = e->next; + free(e); + e = next; + } + } + + free(hash->buckets); + free(hash); } size_t zix_hash_size(const ZixHash* hash) { - return hash->count; + return hash->count; } static inline void insert_entry(ZixHashEntry** bucket, ZixHashEntry* entry) { - entry->next = *bucket; - *bucket = entry; + entry->next = *bucket; + *bucket = entry; } static inline ZixStatus rehash(ZixHash* hash, unsigned new_n_buckets) { - ZixHashEntry** new_buckets = (ZixHashEntry**)calloc( - new_n_buckets, sizeof(ZixHashEntry*)); - if (!new_buckets) { - return ZIX_STATUS_NO_MEM; - } - - const unsigned old_n_buckets = *hash->n_buckets; - for (unsigned b = 0; b < old_n_buckets; ++b) { - for (ZixHashEntry* e = hash->buckets[b]; e;) { - ZixHashEntry* const next = e->next; - const unsigned h = e->hash % new_n_buckets; - insert_entry(&new_buckets[h], e); - e = next; - } - } - - free(hash->buckets); - hash->buckets = new_buckets; - - return ZIX_STATUS_SUCCESS; + ZixHashEntry** new_buckets = + (ZixHashEntry**)calloc(new_n_buckets, sizeof(ZixHashEntry*)); + if (!new_buckets) { + return ZIX_STATUS_NO_MEM; + } + + const unsigned old_n_buckets = *hash->n_buckets; + for (unsigned b = 0; b < old_n_buckets; ++b) { + for (ZixHashEntry* e = hash->buckets[b]; e;) { + ZixHashEntry* const next = e->next; + const unsigned h = e->hash % new_n_buckets; + insert_entry(&new_buckets[h], e); + e = next; + } + } + + free(hash->buckets); + hash->buckets = new_buckets; + + return ZIX_STATUS_SUCCESS; } static inline ZixHashEntry* @@ -136,100 +134,97 @@ find_entry(const ZixHash* hash, const unsigned h, const unsigned h_nomod) { - for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) { - if (e->hash == h_nomod && hash->equal_func(zix_hash_value(e), key)) { - return e; - } - } - return NULL; + for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) { + if (e->hash == h_nomod && hash->equal_func(zix_hash_value(e), key)) { + return e; + } + } + return NULL; } void* zix_hash_find(const ZixHash* hash, const void* value) { - const unsigned h_nomod = hash->hash_func(value); - const unsigned h = h_nomod % *hash->n_buckets; - ZixHashEntry* const entry = find_entry(hash, value, h, h_nomod); - return entry ? zix_hash_value(entry) : 0; + const unsigned h_nomod = hash->hash_func(value); + const unsigned h = h_nomod % *hash->n_buckets; + ZixHashEntry* const entry = find_entry(hash, value, h, h_nomod); + return entry ? zix_hash_value(entry) : 0; } ZixStatus zix_hash_insert(ZixHash* hash, const void* value, void** inserted) { - unsigned h_nomod = hash->hash_func(value); - unsigned h = h_nomod % *hash->n_buckets; - - ZixHashEntry* elem = find_entry(hash, value, h, h_nomod); - if (elem) { - assert(elem->hash == h_nomod); - if (inserted) { - *inserted = zix_hash_value(elem); - } - return ZIX_STATUS_EXISTS; - } - - elem = (ZixHashEntry*)malloc(sizeof(ZixHashEntry) + hash->value_size); - if (!elem) { - return ZIX_STATUS_NO_MEM; - } - elem->next = NULL; - elem->hash = h_nomod; - memcpy(elem + 1, value, hash->value_size); - - const unsigned next_n_buckets = *(hash->n_buckets + 1); - if (next_n_buckets != 0 && (hash->count + 1) >= next_n_buckets) { - if (!rehash(hash, next_n_buckets)) { - h = h_nomod % *(++hash->n_buckets); - } - } - - insert_entry(&hash->buckets[h], elem); - ++hash->count; - if (inserted) { - *inserted = zix_hash_value(elem); - } - return ZIX_STATUS_SUCCESS; + unsigned h_nomod = hash->hash_func(value); + unsigned h = h_nomod % *hash->n_buckets; + + ZixHashEntry* elem = find_entry(hash, value, h, h_nomod); + if (elem) { + assert(elem->hash == h_nomod); + if (inserted) { + *inserted = zix_hash_value(elem); + } + return ZIX_STATUS_EXISTS; + } + + elem = (ZixHashEntry*)malloc(sizeof(ZixHashEntry) + hash->value_size); + if (!elem) { + return ZIX_STATUS_NO_MEM; + } + elem->next = NULL; + elem->hash = h_nomod; + memcpy(elem + 1, value, hash->value_size); + + const unsigned next_n_buckets = *(hash->n_buckets + 1); + if (next_n_buckets != 0 && (hash->count + 1) >= next_n_buckets) { + if (!rehash(hash, next_n_buckets)) { + h = h_nomod % *(++hash->n_buckets); + } + } + + insert_entry(&hash->buckets[h], elem); + ++hash->count; + if (inserted) { + *inserted = zix_hash_value(elem); + } + return ZIX_STATUS_SUCCESS; } ZixStatus zix_hash_remove(ZixHash* hash, const void* value) { - const unsigned h_nomod = hash->hash_func(value); - const unsigned h = h_nomod % *hash->n_buckets; - - ZixHashEntry** next_ptr = &hash->buckets[h]; - for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) { - if (h_nomod == e->hash && - hash->equal_func(zix_hash_value(e), value)) { - *next_ptr = e->next; - free(e); - return ZIX_STATUS_SUCCESS; - } - next_ptr = &e->next; - } - - if (hash->n_buckets != sizes) { - const unsigned prev_n_buckets = *(hash->n_buckets - 1); - if (hash->count - 1 <= prev_n_buckets) { - if (!rehash(hash, prev_n_buckets)) { - --hash->n_buckets; - } - } - } - - --hash->count; - return ZIX_STATUS_NOT_FOUND; + const unsigned h_nomod = hash->hash_func(value); + const unsigned h = h_nomod % *hash->n_buckets; + + ZixHashEntry** next_ptr = &hash->buckets[h]; + for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) { + if (h_nomod == e->hash && hash->equal_func(zix_hash_value(e), value)) { + *next_ptr = e->next; + free(e); + return ZIX_STATUS_SUCCESS; + } + next_ptr = &e->next; + } + + if (hash->n_buckets != sizes) { + const unsigned prev_n_buckets = *(hash->n_buckets - 1); + if (hash->count - 1 <= prev_n_buckets) { + if (!rehash(hash, prev_n_buckets)) { + --hash->n_buckets; + } + } + } + + --hash->count; + return ZIX_STATUS_NOT_FOUND; } void -zix_hash_foreach(ZixHash* hash, - ZixHashVisitFunc f, - void* user_data) +zix_hash_foreach(ZixHash* hash, ZixHashVisitFunc f, void* user_data) { - for (unsigned b = 0; b < *hash->n_buckets; ++b) { - ZixHashEntry* bucket = hash->buckets[b]; - for (ZixHashEntry* e = bucket; e; e = e->next) { - f(zix_hash_value(e), user_data); - } - } + for (unsigned b = 0; b < *hash->n_buckets; ++b) { + ZixHashEntry* bucket = hash->buckets[b]; + for (ZixHashEntry* e = bucket; e; e = e->next) { + f(zix_hash_value(e), user_data); + } + } } @@ -43,8 +43,7 @@ typedef uint32_t (*ZixHashFunc)(const void* value); /** Function to visit a hash element. */ -typedef void (*ZixHashVisitFunc)(void* value, - void* user_data); +typedef void (*ZixHashVisitFunc)(void* value, void* user_data); /** Create a new hash table. @@ -59,21 +58,22 @@ typedef void (*ZixHashVisitFunc)(void* value, @param equal_func A function to test value equality. @param value_size The size of the values to be stored. */ -ZIX_API ZixHash* -zix_hash_new(ZixHashFunc hash_func, - ZixEqualFunc equal_func, - size_t value_size); +ZIX_API +ZixHash* +zix_hash_new(ZixHashFunc hash_func, ZixEqualFunc equal_func, size_t value_size); /** Free `hash`. */ -ZIX_API void +ZIX_API +void zix_hash_free(ZixHash* hash); /** Return the number of elements in `hash`. */ -ZIX_PURE_API size_t +ZIX_PURE_API +size_t zix_hash_size(const ZixHash* hash); /** @@ -90,10 +90,9 @@ zix_hash_size(const ZixHash* hash); @param inserted The copy of `value` in the hash table. @return ZIX_STATUS_SUCCESS, ZIX_STATUS_EXISTS, or ZIX_STATUS_NO_MEM. */ -ZIX_API ZixStatus -zix_hash_insert(ZixHash* hash, - const void* value, - void** inserted); +ZIX_API +ZixStatus +zix_hash_insert(ZixHash* hash, const void* value, void** inserted); /** Remove an item from `hash`. @@ -102,9 +101,9 @@ zix_hash_insert(ZixHash* hash, @param value The value to remove. @return ZIX_STATUS_SUCCES or ZIX_STATUS_NOT_FOUND. */ -ZIX_API ZixStatus -zix_hash_remove(ZixHash* hash, - const void* value); +ZIX_API +ZixStatus +zix_hash_remove(ZixHash* hash, const void* value); /** Search for an item in `hash`. @@ -112,9 +111,9 @@ zix_hash_remove(ZixHash* hash, @param hash The hash table. @param value The value to search for. */ -ZIX_API void* -zix_hash_find(const ZixHash* hash, - const void* value); +ZIX_API +void* +zix_hash_find(const ZixHash* hash, const void* value); /** Call `f` on each value in `hash`. @@ -123,10 +122,9 @@ zix_hash_find(const ZixHash* hash, @param f The function to call on each value. @param user_data The user_data parameter passed to `f`. */ -ZIX_API void -zix_hash_foreach(ZixHash* hash, - ZixHashVisitFunc f, - void* user_data); +ZIX_API +void +zix_hash_foreach(ZixHash* hash, ZixHashVisitFunc f, void* user_data); /** @} @@ -134,7 +132,7 @@ zix_hash_foreach(ZixHash* hash, */ #ifdef __cplusplus -} /* extern "C" */ +} /* extern "C" */ #endif -#endif /* ZIX_HASH_H */ +#endif /* ZIX_HASH_H */ @@ -20,200 +20,203 @@ #include <string.h> #ifdef HAVE_MLOCK -# include <sys/mman.h> -# define ZIX_MLOCK(ptr, size) mlock((ptr), (size)) +# include <sys/mman.h> +# define ZIX_MLOCK(ptr, size) mlock((ptr), (size)) #elif defined(_WIN32) -# include <windows.h> -# define ZIX_MLOCK(ptr, size) VirtualLock((ptr), (size)) +# include <windows.h> +# define ZIX_MLOCK(ptr, size) VirtualLock((ptr), (size)) #else -# pragma message("warning: No memory locking, possible RT violations") -# define ZIX_MLOCK(ptr, size) +# pragma message("warning: No memory locking, possible RT violations") +# define ZIX_MLOCK(ptr, size) #endif #if defined(_MSC_VER) -# include <windows.h> -# define ZIX_READ_BARRIER() MemoryBarrier() -# define ZIX_WRITE_BARRIER() MemoryBarrier() +# include <windows.h> +# define ZIX_READ_BARRIER() MemoryBarrier() +# define ZIX_WRITE_BARRIER() MemoryBarrier() #elif defined(__GNUC__) -# define ZIX_READ_BARRIER() __atomic_thread_fence(__ATOMIC_ACQUIRE) -# define ZIX_WRITE_BARRIER() __atomic_thread_fence(__ATOMIC_RELEASE) +# define ZIX_READ_BARRIER() __atomic_thread_fence(__ATOMIC_ACQUIRE) +# define ZIX_WRITE_BARRIER() __atomic_thread_fence(__ATOMIC_RELEASE) #else -# pragma message("warning: No memory barriers, possible SMP bugs") -# define ZIX_READ_BARRIER() -# define ZIX_WRITE_BARRIER() +# pragma message("warning: No memory barriers, possible SMP bugs") +# define ZIX_READ_BARRIER() +# define ZIX_WRITE_BARRIER() #endif struct ZixRingImpl { - uint32_t write_head; ///< Read index into buf - uint32_t read_head; ///< Write index into buf - uint32_t size; ///< Size (capacity) in bytes - uint32_t size_mask; ///< Mask for fast modulo - char* buf; ///< Contents + uint32_t write_head; ///< Read index into buf + uint32_t read_head; ///< Write index into buf + uint32_t size; ///< Size (capacity) in bytes + uint32_t size_mask; ///< Mask for fast modulo + char* buf; ///< Contents }; static inline uint32_t next_power_of_two(uint32_t size) { - // http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 - size--; - size |= size >> 1u; - size |= size >> 2u; - size |= size >> 4u; - size |= size >> 8u; - size |= size >> 16u; - size++; - return size; + // http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 + size--; + size |= size >> 1u; + size |= size >> 2u; + size |= size >> 4u; + size |= size >> 8u; + size |= size >> 16u; + size++; + return size; } ZixRing* zix_ring_new(uint32_t size) { - ZixRing* ring = (ZixRing*)malloc(sizeof(ZixRing)); - ring->write_head = 0; - ring->read_head = 0; - ring->size = next_power_of_two(size); - ring->size_mask = ring->size - 1; - ring->buf = (char*)malloc(ring->size); - return ring; + ZixRing* ring = (ZixRing*)malloc(sizeof(ZixRing)); + ring->write_head = 0; + ring->read_head = 0; + ring->size = next_power_of_two(size); + ring->size_mask = ring->size - 1; + ring->buf = (char*)malloc(ring->size); + return ring; } void zix_ring_free(ZixRing* ring) { - free(ring->buf); - free(ring); + free(ring->buf); + free(ring); } void zix_ring_mlock(ZixRing* ring) { - ZIX_MLOCK(ring, sizeof(ZixRing)); - ZIX_MLOCK(ring->buf, ring->size); + ZIX_MLOCK(ring, sizeof(ZixRing)); + ZIX_MLOCK(ring->buf, ring->size); } void zix_ring_reset(ZixRing* ring) { - ring->write_head = 0; - ring->read_head = 0; + ring->write_head = 0; + ring->read_head = 0; } static inline uint32_t read_space_internal(const ZixRing* ring, uint32_t r, uint32_t w) { - if (r < w) { - return w - r; - } + if (r < w) { + return w - r; + } - return (w - r + ring->size) & ring->size_mask; + return (w - r + ring->size) & ring->size_mask; } uint32_t zix_ring_read_space(const ZixRing* ring) { - return read_space_internal(ring, ring->read_head, ring->write_head); + return read_space_internal(ring, ring->read_head, ring->write_head); } static inline uint32_t write_space_internal(const ZixRing* ring, uint32_t r, uint32_t w) { - if (r == w) { - return ring->size - 1; - } + if (r == w) { + return ring->size - 1; + } - if (r < w) { - return ((r - w + ring->size) & ring->size_mask) - 1; - } + if (r < w) { + return ((r - w + ring->size) & ring->size_mask) - 1; + } - return (r - w) - 1; + return (r - w) - 1; } uint32_t zix_ring_write_space(const ZixRing* ring) { - return write_space_internal(ring, ring->read_head, ring->write_head); + return write_space_internal(ring, ring->read_head, ring->write_head); } uint32_t zix_ring_capacity(const ZixRing* ring) { - return ring->size - 1; + return ring->size - 1; } static inline uint32_t -peek_internal(const ZixRing* ring, uint32_t r, uint32_t w, - uint32_t size, void* dst) +peek_internal(const ZixRing* ring, + uint32_t r, + uint32_t w, + uint32_t size, + void* dst) { - if (read_space_internal(ring, r, w) < size) { - return 0; - } - - if (r + size < ring->size) { - memcpy(dst, &ring->buf[r], size); - } else { - const uint32_t first_size = ring->size - r; - memcpy(dst, &ring->buf[r], first_size); - memcpy((char*)dst + first_size, &ring->buf[0], size - first_size); - } - - return size; + if (read_space_internal(ring, r, w) < size) { + return 0; + } + + if (r + size < ring->size) { + memcpy(dst, &ring->buf[r], size); + } else { + const uint32_t first_size = ring->size - r; + memcpy(dst, &ring->buf[r], first_size); + memcpy((char*)dst + first_size, &ring->buf[0], size - first_size); + } + + return size; } uint32_t zix_ring_peek(ZixRing* ring, void* dst, uint32_t size) { - return peek_internal(ring, ring->read_head, ring->write_head, size, dst); + return peek_internal(ring, ring->read_head, ring->write_head, size, dst); } uint32_t zix_ring_read(ZixRing* ring, void* dst, uint32_t size) { - const uint32_t r = ring->read_head; - const uint32_t w = ring->write_head; + const uint32_t r = ring->read_head; + const uint32_t w = ring->write_head; - if (peek_internal(ring, r, w, size, dst)) { - ZIX_READ_BARRIER(); - ring->read_head = (r + size) & ring->size_mask; - return size; - } + if (peek_internal(ring, r, w, size, dst)) { + ZIX_READ_BARRIER(); + ring->read_head = (r + size) & ring->size_mask; + return size; + } - return 0; + return 0; } uint32_t zix_ring_skip(ZixRing* ring, uint32_t size) { - const uint32_t r = ring->read_head; - const uint32_t w = ring->write_head; - if (read_space_internal(ring, r, w) < size) { - return 0; - } - - ZIX_READ_BARRIER(); - ring->read_head = (r + size) & ring->size_mask; - return size; + const uint32_t r = ring->read_head; + const uint32_t w = ring->write_head; + if (read_space_internal(ring, r, w) < size) { + return 0; + } + + ZIX_READ_BARRIER(); + ring->read_head = (r + size) & ring->size_mask; + return size; } uint32_t zix_ring_write(ZixRing* ring, const void* src, uint32_t size) { - const uint32_t r = ring->read_head; - const uint32_t w = ring->write_head; - if (write_space_internal(ring, r, w) < size) { - return 0; - } - - if (w + size <= ring->size) { - memcpy(&ring->buf[w], src, size); - ZIX_WRITE_BARRIER(); - ring->write_head = (w + size) & ring->size_mask; - } else { - const uint32_t this_size = ring->size - w; - memcpy(&ring->buf[w], src, this_size); - memcpy(&ring->buf[0], (const char*)src + this_size, size - this_size); - ZIX_WRITE_BARRIER(); - ring->write_head = size - this_size; - } - - return size; + const uint32_t r = ring->read_head; + const uint32_t w = ring->write_head; + if (write_space_internal(ring, r, w) < size) { + return 0; + } + + if (w + size <= ring->size) { + memcpy(&ring->buf[w], src, size); + ZIX_WRITE_BARRIER(); + ring->write_head = (w + size) & ring->size_mask; + } else { + const uint32_t this_size = ring->size - w; + memcpy(&ring->buf[w], src, this_size); + memcpy(&ring->buf[0], (const char*)src + this_size, size - this_size); + ZIX_WRITE_BARRIER(); + ring->write_head = size - this_size; + } + + return size; } @@ -135,7 +135,7 @@ zix_ring_write(ZixRing* ring, const void* src, uint32_t size); */ #ifdef __cplusplus -} /* extern "C" */ +} /* extern "C" */ #endif -#endif /* ZIX_RING_H */ +#endif /* ZIX_RING_H */ @@ -20,13 +20,13 @@ #include "zix/common.h" #ifdef __APPLE__ -# include <mach/mach.h> +# include <mach/mach.h> #elif defined(_WIN32) -# include <limits.h> -# include <windows.h> +# include <limits.h> +# include <windows.h> #else -# include <errno.h> -# include <semaphore.h> +# include <errno.h> +# include <semaphore.h> #endif #ifdef __cplusplus @@ -104,126 +104,127 @@ zix_sem_try_wait(ZixSem* sem); #ifdef __APPLE__ struct ZixSemImpl { - semaphore_t sem; + semaphore_t sem; }; static inline ZixStatus zix_sem_init(ZixSem* sem, unsigned val) { - return semaphore_create(mach_task_self(), &sem->sem, SYNC_POLICY_FIFO, val) - ? ZIX_STATUS_ERROR : ZIX_STATUS_SUCCESS; + return semaphore_create(mach_task_self(), &sem->sem, SYNC_POLICY_FIFO, val) + ? ZIX_STATUS_ERROR + : ZIX_STATUS_SUCCESS; } static inline void zix_sem_destroy(ZixSem* sem) { - semaphore_destroy(mach_task_self(), sem->sem); + semaphore_destroy(mach_task_self(), sem->sem); } static inline void zix_sem_post(ZixSem* sem) { - semaphore_signal(sem->sem); + semaphore_signal(sem->sem); } static inline ZixStatus zix_sem_wait(ZixSem* sem) { - if (semaphore_wait(sem->sem) != KERN_SUCCESS) { - return ZIX_STATUS_ERROR; - } - return ZIX_STATUS_SUCCESS; + if (semaphore_wait(sem->sem) != KERN_SUCCESS) { + return ZIX_STATUS_ERROR; + } + return ZIX_STATUS_SUCCESS; } static inline bool zix_sem_try_wait(ZixSem* sem) { - const mach_timespec_t zero = { 0, 0 }; - return semaphore_timedwait(sem->sem, zero) == KERN_SUCCESS; + const mach_timespec_t zero = {0, 0}; + return semaphore_timedwait(sem->sem, zero) == KERN_SUCCESS; } #elif defined(_WIN32) struct ZixSemImpl { - HANDLE sem; + HANDLE sem; }; static inline ZixStatus zix_sem_init(ZixSem* sem, unsigned initial) { - sem->sem = CreateSemaphore(NULL, initial, LONG_MAX, NULL); - return (sem->sem) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_ERROR; + sem->sem = CreateSemaphore(NULL, initial, LONG_MAX, NULL); + return (sem->sem) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_ERROR; } static inline void zix_sem_destroy(ZixSem* sem) { - CloseHandle(sem->sem); + CloseHandle(sem->sem); } static inline void zix_sem_post(ZixSem* sem) { - ReleaseSemaphore(sem->sem, 1, NULL); + ReleaseSemaphore(sem->sem, 1, NULL); } static inline ZixStatus zix_sem_wait(ZixSem* sem) { - if (WaitForSingleObject(sem->sem, INFINITE) != WAIT_OBJECT_0) { - return ZIX_STATUS_ERROR; - } - return ZIX_STATUS_SUCCESS; + if (WaitForSingleObject(sem->sem, INFINITE) != WAIT_OBJECT_0) { + return ZIX_STATUS_ERROR; + } + return ZIX_STATUS_SUCCESS; } static inline bool zix_sem_try_wait(ZixSem* sem) { - return WaitForSingleObject(sem->sem, 0) == WAIT_OBJECT_0; + return WaitForSingleObject(sem->sem, 0) == WAIT_OBJECT_0; } -#else /* !defined(__APPLE__) && !defined(_WIN32) */ +#else /* !defined(__APPLE__) && !defined(_WIN32) */ struct ZixSemImpl { - sem_t sem; + sem_t sem; }; static inline ZixStatus zix_sem_init(ZixSem* sem, unsigned initial) { - return sem_init(&sem->sem, 0, initial) - ? ZIX_STATUS_ERROR : ZIX_STATUS_SUCCESS; + return sem_init(&sem->sem, 0, initial) ? ZIX_STATUS_ERROR + : ZIX_STATUS_SUCCESS; } static inline void zix_sem_destroy(ZixSem* sem) { - sem_destroy(&sem->sem); + sem_destroy(&sem->sem); } static inline void zix_sem_post(ZixSem* sem) { - sem_post(&sem->sem); + sem_post(&sem->sem); } static inline ZixStatus zix_sem_wait(ZixSem* sem) { - while (sem_wait(&sem->sem)) { - if (errno != EINTR) { - return ZIX_STATUS_ERROR; - } - /* Otherwise, interrupted, so try again. */ - } - - return ZIX_STATUS_SUCCESS; + while (sem_wait(&sem->sem)) { + if (errno != EINTR) { + return ZIX_STATUS_ERROR; + } + /* Otherwise, interrupted, so try again. */ + } + + return ZIX_STATUS_SUCCESS; } static inline bool zix_sem_try_wait(ZixSem* sem) { - return (sem_trywait(&sem->sem) == 0); + return (sem_trywait(&sem->sem) == 0); } #endif @@ -235,7 +236,7 @@ zix_sem_try_wait(ZixSem* sem) */ #ifdef __cplusplus -} /* extern "C" */ +} /* extern "C" */ #endif -#endif /* ZIX_SEM_H */ +#endif /* ZIX_SEM_H */ diff --git a/zix/sorted_array.c b/zix/sorted_array.c index c96ea2b..0f84227 100644 --- a/zix/sorted_array.c +++ b/zix/sorted_array.c @@ -26,26 +26,26 @@ // #define ZIX_SORTED_ARRAY_DUMP 1 struct ZixSortedArrayImpl { - void* array; - ZixComparator cmp; - void* cmp_data; - size_t elem_size; - size_t num_elems; - bool allow_duplicates; + void* array; + ZixComparator cmp; + void* cmp_data; + size_t elem_size; + size_t num_elems; + bool allow_duplicates; }; #ifdef ZIX_SORTED_ARRAY_DUMP static void zix_sorted_array_print(ZixSortedArray* a) { - for (size_t i = 0; i < a->num_elems; ++i) { - printf(" %ld", *(intptr_t*)((char*)a->array + (i * a->elem_size))); - } - printf("\n"); + for (size_t i = 0; i < a->num_elems; ++i) { + printf(" %ld", *(intptr_t*)((char*)a->array + (i * a->elem_size))); + } + printf("\n"); } -# define DUMP(a) zix_sorted_array_print(a) +# define DUMP(a) zix_sorted_array_print(a) #else -# define DUMP(a) +# define DUMP(a) #endif ZixSortedArray* @@ -54,27 +54,27 @@ zix_sorted_array_new(bool allow_duplicates, void* cmp_data, size_t elem_size) { - ZixSortedArray* a = (ZixSortedArray*)malloc(sizeof(ZixSortedArray)); - a->array = NULL; - a->cmp = cmp; - a->cmp_data = cmp_data; - a->elem_size = elem_size; - a->num_elems = 0; - a->allow_duplicates = allow_duplicates; - return a; + ZixSortedArray* a = (ZixSortedArray*)malloc(sizeof(ZixSortedArray)); + a->array = NULL; + a->cmp = cmp; + a->cmp_data = cmp_data; + a->elem_size = elem_size; + a->num_elems = 0; + a->allow_duplicates = allow_duplicates; + return a; } void zix_sorted_array_free(ZixSortedArray* a) { - free(a->array); - free(a); + free(a->array); + free(a); } size_t zix_sorted_array_size(const ZixSortedArray* a) { - return a->num_elems; + return a->num_elems; } ZixStatus @@ -82,58 +82,56 @@ zix_sorted_array_insert(ZixSortedArray* a, const void* e, ZixSortedArrayIter* ai) { - if (a->num_elems == 0) { - assert(!a->array); - a->array = malloc(a->elem_size); - memcpy(a->array, e, a->elem_size); - ++a->num_elems; - *ai = a->array; - return ZIX_STATUS_SUCCESS; - } - - zix_sorted_array_find(a, e, ai); - assert(*ai); - const size_t i = (size_t)((char*)*ai - (char*)a->array) / a->elem_size; - - a->array = realloc(a->array, ++a->num_elems * a->elem_size); - memmove((char*)a->array + ((i + 1) * a->elem_size), - (char*)a->array + (i * a->elem_size), - (a->num_elems - i - 1) * a->elem_size); - memcpy((char*)a->array + (i * a->elem_size), - e, - a->elem_size); - - *ai = (char*)a->array + (i * a->elem_size); - DUMP(t); - return ZIX_STATUS_SUCCESS; + if (a->num_elems == 0) { + assert(!a->array); + a->array = malloc(a->elem_size); + memcpy(a->array, e, a->elem_size); + ++a->num_elems; + *ai = a->array; + return ZIX_STATUS_SUCCESS; + } + + zix_sorted_array_find(a, e, ai); + assert(*ai); + const size_t i = (size_t)((char*)*ai - (char*)a->array) / a->elem_size; + + a->array = realloc(a->array, ++a->num_elems * a->elem_size); + memmove((char*)a->array + ((i + 1) * a->elem_size), + (char*)a->array + (i * a->elem_size), + (a->num_elems - i - 1) * a->elem_size); + memcpy((char*)a->array + (i * a->elem_size), e, a->elem_size); + + *ai = (char*)a->array + (i * a->elem_size); + DUMP(t); + return ZIX_STATUS_SUCCESS; } ZixStatus zix_sorted_array_remove(ZixSortedArray* a, ZixSortedArrayIter ai) { - const size_t i = (size_t)((char*)ai - (char*)a->array) / a->elem_size; - memmove((char*)a->array + (i * a->elem_size), - (char*)a->array + ((i + 1) * a->elem_size), - (a->num_elems - i - 1) * a->elem_size); - --a->num_elems; - DUMP(a); - return ZIX_STATUS_SUCCESS; + const size_t i = (size_t)((char*)ai - (char*)a->array) / a->elem_size; + memmove((char*)a->array + (i * a->elem_size), + (char*)a->array + ((i + 1) * a->elem_size), + (a->num_elems - i - 1) * a->elem_size); + --a->num_elems; + DUMP(a); + return ZIX_STATUS_SUCCESS; } static inline void* zix_sorted_array_index_unchecked(const ZixSortedArray* a, size_t index) { - return (char*)a->array + (a->elem_size * index); + return (char*)a->array + (a->elem_size * index); } void* zix_sorted_array_index(const ZixSortedArray* a, size_t index) { - if (index >= a->num_elems) { - return NULL; - } + if (index >= a->num_elems) { + return NULL; + } - return zix_sorted_array_index_unchecked(a, index); + return zix_sorted_array_index_unchecked(a, index); } ZixStatus @@ -141,55 +139,55 @@ zix_sorted_array_find(const ZixSortedArray* a, const void* e, ZixSortedArrayIter* ai) { - intptr_t lower = 0; - intptr_t upper = a->num_elems - 1; - while (upper >= lower) { - const intptr_t i = lower + ((upper - lower) / 2); - void* const elem_i = zix_sorted_array_index_unchecked(a, i); - const int cmp = a->cmp(elem_i, e, a->cmp_data); - - if (cmp == 0) { - *ai = elem_i; - return ZIX_STATUS_SUCCESS; - } - - if (cmp > 0) { - upper = i - 1; - } else { - lower = i + 1; - } - } - - *ai = zix_sorted_array_index_unchecked(a, lower); - return ZIX_STATUS_NOT_FOUND; + intptr_t lower = 0; + intptr_t upper = a->num_elems - 1; + while (upper >= lower) { + const intptr_t i = lower + ((upper - lower) / 2); + void* const elem_i = zix_sorted_array_index_unchecked(a, i); + const int cmp = a->cmp(elem_i, e, a->cmp_data); + + if (cmp == 0) { + *ai = elem_i; + return ZIX_STATUS_SUCCESS; + } + + if (cmp > 0) { + upper = i - 1; + } else { + lower = i + 1; + } + } + + *ai = zix_sorted_array_index_unchecked(a, lower); + return ZIX_STATUS_NOT_FOUND; } void* zix_sorted_array_get_data(ZixSortedArrayIter ai) { - return ai; + return ai; } ZixSortedArrayIter zix_sorted_array_begin(ZixSortedArray* a) { - return a->array; + return a->array; } ZixSortedArrayIter zix_sorted_array_end(ZixSortedArray* a) { - return (char*)a->array + (a->elem_size * a->num_elems); + return (char*)a->array + (a->elem_size * a->num_elems); } bool zix_sorted_array_iter_is_end(ZixSortedArray* a, ZixSortedArrayIter i) { - return i != zix_sorted_array_end(a); + return i != zix_sorted_array_end(a); } ZixSortedArrayIter zix_sorted_array_iter_next(ZixSortedArray* a, ZixSortedArrayIter i) { - return (char*)i + a->elem_size; + return (char*)i + a->elem_size; } diff --git a/zix/sorted_array.h b/zix/sorted_array.h index 5acd50e..92f13e6 100644 --- a/zix/sorted_array.h +++ b/zix/sorted_array.h @@ -48,8 +48,10 @@ typedef void* ZixSortedArrayIter; */ ZIX_API ZixSortedArray* -zix_sorted_array_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data, - size_t elem_size); +zix_sorted_array_new(bool allow_duplicates, + ZixComparator cmp, + void* cmp_data, + size_t elem_size); /** Free `a`. @@ -139,7 +141,7 @@ zix_sorted_array_iter_next(ZixSortedArray* a, ZixSortedArrayIter i); */ #ifdef __cplusplus -} /* extern "C" */ +} /* extern "C" */ #endif -#endif /* ZIX_SORTED_ARRAY_H */ +#endif /* ZIX_SORTED_ARRAY_H */ diff --git a/zix/strindex.c b/zix/strindex.c index 2fdd04f..8cb05c9 100644 --- a/zix/strindex.c +++ b/zix/strindex.c @@ -26,16 +26,16 @@ #include <string.h> typedef struct _ZixStrindexNode { - struct _ZixStrindexNode* children; /* Children of this node */ - size_t num_children; /* Number of outgoing edges */ - char* first; /* Start of this suffix */ - char* label_first; /* Start of incoming label */ - char* label_last; /* End of incoming label */ + struct _ZixStrindexNode* children; /* Children of this node */ + size_t num_children; /* Number of outgoing edges */ + char* first; /* Start of this suffix */ + char* label_first; /* Start of incoming label */ + char* label_last; /* End of incoming label */ } ZixStrindexNode; struct _ZixStrindex { - char* s; /* String contained in this tree */ - ZixStrindexNode* root; /* Root of the tree */ + char* s; /* String contained in this tree */ + ZixStrindexNode* root; /* Root of the tree */ }; static ZixStatus @@ -47,62 +47,64 @@ strindex_insert(ZixStrindexNode* n, ZixStrindex* zix_strindex_new(const char* s) { - const size_t len = strlen(s); + const size_t len = strlen(s); - ZixStrindex* t = (ZixStrindex*)malloc(sizeof(ZixStrindex)); - memset(t, '\0', sizeof(struct _ZixStrindex)); + ZixStrindex* t = (ZixStrindex*)malloc(sizeof(ZixStrindex)); + memset(t, '\0', sizeof(struct _ZixStrindex)); - t->s = (char*)calloc(1, len + 1); - memcpy(t->s, s, len); + t->s = (char*)calloc(1, len + 1); + memcpy(t->s, s, len); - t->root = (ZixStrindexNode*)malloc(sizeof(ZixStrindexNode)); - memset(t->root, '\0', sizeof(ZixStrindexNode)); - t->root->num_children = 0; - t->root->first = t->s; + t->root = (ZixStrindexNode*)malloc(sizeof(ZixStrindexNode)); + memset(t->root, '\0', sizeof(ZixStrindexNode)); + t->root->num_children = 0; + t->root->first = t->s; - for (size_t i = 0; i < len; ++i) { - strindex_insert(t->root, t->s + i, t->s + i, t->s + (len - 1)); - } + for (size_t i = 0; i < len; ++i) { + strindex_insert(t->root, t->s + i, t->s + i, t->s + (len - 1)); + } - return t; + return t; } static void zix_strindex_free_rec(ZixStrindexNode* n) { - if (n) { - for (size_t i = 0; i < n->num_children; ++i) { - zix_strindex_free_rec(&n->children[i]); - } - free(n->children); - } + if (n) { + for (size_t i = 0; i < n->num_children; ++i) { + zix_strindex_free_rec(&n->children[i]); + } + + free(n->children); + } } void zix_strindex_free(ZixStrindex* strindex) { - zix_strindex_free_rec(strindex->root); - free(strindex->s); - free(strindex->root); - free(strindex); + zix_strindex_free_rec(strindex->root); + free(strindex->s); + free(strindex->root); + free(strindex); } static inline int strindex_is_leaf(ZixStrindexNode* n) { - return n->num_children == 0; + return n->num_children == 0; } static int strindex_find_edge(ZixStrindexNode* n, char c, size_t* index) { - for (size_t i = 0; i < n->num_children; ++i) { - if (n->children[i].label_first[0] == c) { - *index = i; - return 1; - } - } - return 0; + for (size_t i = 0; i < n->num_children; ++i) { + if (n->children[i].label_first[0] == c) { + *index = i; + return 1; + } + } + + return 0; } static void @@ -111,149 +113,149 @@ strindex_add_edge(ZixStrindexNode* n, char* first, char* last) { - assert(last > first); - n->children = (ZixStrindexNode*)realloc( - n->children, (n->num_children + 1) * sizeof(ZixStrindexNode)); + assert(last > first); + n->children = (ZixStrindexNode*)realloc( + n->children, (n->num_children + 1) * sizeof(ZixStrindexNode)); - memset(&n->children[n->num_children], '\0', sizeof(ZixStrindexNode)); + memset(&n->children[n->num_children], '\0', sizeof(ZixStrindexNode)); - n->children[n->num_children].first = suffix_first; - n->children[n->num_children].label_first = first; - n->children[n->num_children].label_last = last; - ++n->num_children; + n->children[n->num_children].first = suffix_first; + n->children[n->num_children].label_first = first; + n->children[n->num_children].label_last = last; + ++n->num_children; } /* Split an outgoing edge (to a child) at the given index */ static void -strindex_split_edge(ZixStrindexNode* child, - size_t index) +strindex_split_edge(ZixStrindexNode* child, size_t index) { - ZixStrindexNode* children = child->children; - size_t num_children = child->num_children; + ZixStrindexNode* children = child->children; + size_t num_children = child->num_children; - char* first = child->label_first + index; - char* last = child->label_last; - assert(last > first); - assert(child->first); + char* first = child->label_first + index; + char* last = child->label_last; + assert(last > first); + assert(child->first); - child->children = (ZixStrindexNode*)malloc(sizeof(ZixStrindexNode)); + child->children = (ZixStrindexNode*)malloc(sizeof(ZixStrindexNode)); - child->children[0].children = children; - child->children[0].num_children = num_children; - child->children[0].first = child->first; - child->children[0].label_first = first; - child->children[0].label_last = last; + child->children[0].children = children; + child->children[0].num_children = num_children; + child->children[0].first = child->first; + child->children[0].label_first = first; + child->children[0].label_last = last; - child->label_last = child->label_first + (index - 1); // chop end + child->label_last = child->label_first + (index - 1); // chop end - child->num_children = 1; + child->num_children = 1; } static ZixStatus strindex_insert(ZixStrindexNode* n, char* suffix_first, char* first, char* last) { - size_t child_i; - ZixStrindexNode* child; - assert(first <= last); - - if (strindex_find_edge(n, *first, &child_i)) { - char* label_first = n->children[child_i].label_first; - char* label_last = n->children[child_i].label_last; - size_t split_i = 0; - const size_t label_len = label_last - label_first + 1; - const size_t s_len = last - first + 1; - const size_t max_len = (s_len < label_len) ? s_len : label_len; - - while (split_i < max_len && first[split_i] == label_first[split_i]) { - ++split_i; - } - child = n->children + child_i; - - if (label_len < s_len) { - if (split_i == label_len) { - strindex_insert(child, suffix_first, first + label_len, last); - } else { - strindex_split_edge(child, split_i); - strindex_insert(child, suffix_first, first + split_i, last); - } - } else if ((label_len != split_i) && (label_len != s_len)) { - strindex_split_edge(child, split_i); - if (split_i != s_len) { - strindex_add_edge(child, suffix_first, first + split_i, last); - } - } - } else { - strindex_add_edge(n, suffix_first, first, last); - } - - return ZIX_STATUS_SUCCESS; + size_t child_i; + ZixStrindexNode* child; + assert(first <= last); + + if (strindex_find_edge(n, *first, &child_i)) { + char* label_first = n->children[child_i].label_first; + char* label_last = n->children[child_i].label_last; + size_t split_i = 0; + const size_t label_len = label_last - label_first + 1; + const size_t s_len = last - first + 1; + const size_t max_len = (s_len < label_len) ? s_len : label_len; + + while (split_i < max_len && first[split_i] == label_first[split_i]) { + ++split_i; + } + child = n->children + child_i; + + if (label_len < s_len) { + if (split_i == label_len) { + strindex_insert(child, suffix_first, first + label_len, last); + } else { + strindex_split_edge(child, split_i); + strindex_insert(child, suffix_first, first + split_i, last); + } + } else if ((label_len != split_i) && (label_len != s_len)) { + strindex_split_edge(child, split_i); + if (split_i != s_len) { + strindex_add_edge(child, suffix_first, first + split_i, last); + } + } + } else { + strindex_add_edge(n, suffix_first, first, last); + } + + return ZIX_STATUS_SUCCESS; } ZixStatus zix_strindex_find(ZixStrindex* strindex, const char* const str, char** match) { - const char* p = str; + const char* p = str; #ifndef NDEBUG - const char* orig_p = p; + const char* orig_p = p; #endif - ZixStrindexNode* n = strindex->root; - size_t child_i; - - *match = NULL; - - while (*p != '\0') { - size_t p_len = strlen(p); - if (strindex_find_edge(n, p[0], &child_i)) { - char* label_first = n->children[child_i].label_first; - char* label_last = n->children[child_i].label_last; - size_t label_len = label_last - label_first + 1; - size_t max_len = (p_len < label_len) ? p_len : label_len; - assert(child_i <= n->num_children); - assert(max_len > 0); - - /* Set match to the start of substring - (but may not actually be a complete match yet) - */ - if (*match == NULL) { - assert(p[0] == orig_p[0]); - assert(orig_p[0] == label_first[0]); - *match = n->children[child_i].first; - assert((*match)[0] == orig_p[0]); - } - - if (strncmp(p, label_first, max_len)) { - /* no match */ - *match = NULL; - return ZIX_STATUS_NOT_FOUND; - } - - if (p_len <= label_len) { - /* At the last node, match */ - *match = n->children[child_i].first; - assert(!strncmp(*match, orig_p, strlen(orig_p))); - return ZIX_STATUS_SUCCESS; - } - - if (strindex_is_leaf(n)) { - /* Hit leaf early, no match */ - return ZIX_STATUS_NOT_FOUND; - } - - /* Match at this node, continue search downwards (or match) */ - p += label_len; - n = &n->children[child_i]; - if (label_len >= p_len) { - assert(strstr(strindex->s, orig_p) != NULL); - assert(strncmp(orig_p, *match, max_len)); - return ZIX_STATUS_SUCCESS; - } - - } else { - assert(strstr(strindex->s, orig_p) == NULL); - return ZIX_STATUS_NOT_FOUND; - } - } - return ZIX_STATUS_NOT_FOUND; + ZixStrindexNode* n = strindex->root; + size_t child_i; + + *match = NULL; + + while (*p != '\0') { + size_t p_len = strlen(p); + if (strindex_find_edge(n, p[0], &child_i)) { + char* label_first = n->children[child_i].label_first; + char* label_last = n->children[child_i].label_last; + size_t label_len = label_last - label_first + 1; + size_t max_len = (p_len < label_len) ? p_len : label_len; + assert(child_i <= n->num_children); + assert(max_len > 0); + + /* Set match to the start of substring + (but may not actually be a complete match yet) + */ + if (*match == NULL) { + assert(p[0] == orig_p[0]); + assert(orig_p[0] == label_first[0]); + *match = n->children[child_i].first; + assert((*match)[0] == orig_p[0]); + } + + if (strncmp(p, label_first, max_len)) { + /* no match */ + *match = NULL; + return ZIX_STATUS_NOT_FOUND; + } + + if (p_len <= label_len) { + /* At the last node, match */ + *match = n->children[child_i].first; + assert(!strncmp(*match, orig_p, strlen(orig_p))); + return ZIX_STATUS_SUCCESS; + } + + if (strindex_is_leaf(n)) { + /* Hit leaf early, no match */ + return ZIX_STATUS_NOT_FOUND; + } + + /* Match at this node, continue search downwards (or match) */ + p += label_len; + n = &n->children[child_i]; + if (label_len >= p_len) { + assert(strstr(strindex->s, orig_p) != NULL); + assert(strncmp(orig_p, *match, max_len)); + return ZIX_STATUS_SUCCESS; + } + + } else { + assert(strstr(strindex->s, orig_p) == NULL); + return ZIX_STATUS_NOT_FOUND; + } + } + + return ZIX_STATUS_NOT_FOUND; } diff --git a/zix/strindex.h b/zix/strindex.h index ba95d81..beb4646 100644 --- a/zix/strindex.h +++ b/zix/strindex.h @@ -56,4 +56,4 @@ zix_strindex_find(ZixStrindex* strindex, const char* str, char** match); @} */ -#endif /* ZIX_STRINDEX_H */ +#endif /* ZIX_STRINDEX_H */ diff --git a/zix/thread.h b/zix/thread.h index 3989f13..8fa562d 100644 --- a/zix/thread.h +++ b/zix/thread.h @@ -20,10 +20,10 @@ #include "zix/common.h" #ifdef _WIN32 -# include <windows.h> +# include <windows.h> #else -# include <errno.h> -# include <pthread.h> +# include <errno.h> +# include <pthread.h> #endif #include <stddef.h> @@ -54,8 +54,8 @@ typedef pthread_t ZixThread; static inline ZixStatus zix_thread_create(ZixThread* thread, size_t stack_size, - void* (*function)(void*), - void* arg); + void* (*function)(void*), + void* arg); /** Join `thread` (block until `thread` exits). @@ -68,53 +68,54 @@ zix_thread_join(ZixThread thread, void** retval); static inline ZixStatus zix_thread_create(ZixThread* thread, size_t stack_size, - void* (*function)(void*), - void* arg) + void* (*function)(void*), + void* arg) { - *thread = CreateThread(NULL, stack_size, - (LPTHREAD_START_ROUTINE)function, arg, - 0, NULL); - return *thread ? ZIX_STATUS_SUCCESS : ZIX_STATUS_ERROR; + *thread = CreateThread( + NULL, stack_size, (LPTHREAD_START_ROUTINE)function, arg, 0, NULL); + return *thread ? ZIX_STATUS_SUCCESS : ZIX_STATUS_ERROR; } static inline ZixStatus zix_thread_join(ZixThread thread, void** retval) { - (void)retval; + (void)retval; - return WaitForSingleObject(thread, INFINITE) - ? ZIX_STATUS_SUCCESS : ZIX_STATUS_ERROR; + return WaitForSingleObject(thread, INFINITE) ? ZIX_STATUS_SUCCESS + : ZIX_STATUS_ERROR; } -#else /* !defined(_WIN32) */ +#else /* !defined(_WIN32) */ static inline ZixStatus zix_thread_create(ZixThread* thread, size_t stack_size, - void* (*function)(void*), - void* arg) + void* (*function)(void*), + void* arg) { - pthread_attr_t attr; - pthread_attr_init(&attr); - pthread_attr_setstacksize(&attr, stack_size); - - const int ret = pthread_create(thread, NULL, function, arg); - pthread_attr_destroy(&attr); - - switch (ret) { - case EAGAIN: return ZIX_STATUS_NO_MEM; - case EINVAL: return ZIX_STATUS_BAD_ARG; - case EPERM: return ZIX_STATUS_BAD_PERMS; - } - - return ret ? ZIX_STATUS_ERROR : ZIX_STATUS_SUCCESS; + pthread_attr_t attr; + pthread_attr_init(&attr); + pthread_attr_setstacksize(&attr, stack_size); + + const int ret = pthread_create(thread, NULL, function, arg); + pthread_attr_destroy(&attr); + + switch (ret) { + case EAGAIN: + return ZIX_STATUS_NO_MEM; + case EINVAL: + return ZIX_STATUS_BAD_ARG; + case EPERM: + return ZIX_STATUS_BAD_PERMS; + } + + return ret ? ZIX_STATUS_ERROR : ZIX_STATUS_SUCCESS; } static inline ZixStatus zix_thread_join(ZixThread thread, void** retval) { - return pthread_join(thread, retval) - ? ZIX_STATUS_ERROR : ZIX_STATUS_SUCCESS; + return pthread_join(thread, retval) ? ZIX_STATUS_ERROR : ZIX_STATUS_SUCCESS; } #endif @@ -125,7 +126,7 @@ zix_thread_join(ZixThread thread, void** retval) */ #ifdef __cplusplus -} /* extern "C" */ +} /* extern "C" */ #endif -#endif /* ZIX_THREAD_H */ +#endif /* ZIX_THREAD_H */ @@ -26,20 +26,20 @@ typedef struct ZixTreeNodeImpl ZixTreeNode; struct ZixTreeImpl { - ZixTreeNode* root; - ZixDestroyFunc destroy; - ZixComparator cmp; - void* cmp_data; - size_t size; - bool allow_duplicates; + ZixTreeNode* root; + ZixDestroyFunc destroy; + ZixComparator cmp; + void* cmp_data; + size_t size; + bool allow_duplicates; }; struct ZixTreeNodeImpl { - void* data; - struct ZixTreeNodeImpl* left; - struct ZixTreeNodeImpl* right; - struct ZixTreeNodeImpl* parent; - int_fast8_t balance; + void* data; + struct ZixTreeNodeImpl* left; + struct ZixTreeNodeImpl* right; + struct ZixTreeNodeImpl* parent; + int_fast8_t balance; }; #define MIN(a, b) (((a) < (b)) ? (a) : (b)) @@ -51,19 +51,19 @@ struct ZixTreeNodeImpl { // #define ZIX_TREE_HYPER_VERIFY 1 #if defined(ZIX_TREE_VERIFY) || defined(ZIX_TREE_HYPER_VERIFY) -# include "tree_debug.h" -# define ASSERT_BALANCE(n) assert(verify_balance(n)) +# include "tree_debug.h" +# define ASSERT_BALANCE(n) assert(verify_balance(n)) #else -# define ASSERT_BALANCE(n) +# define ASSERT_BALANCE(n) #endif #ifdef ZIX_TREE_DUMP -# include "tree_debug.h" -# define DUMP(t) zix_tree_print(t->root, 0) -# define DEBUG_PRINTF(fmt, ...) printf(fmt, __VA_ARGS__) +# include "tree_debug.h" +# define DUMP(t) zix_tree_print(t->root, 0) +# define DEBUG_PRINTF(fmt, ...) printf(fmt, __VA_ARGS__) #else -# define DUMP(t) -# define DEBUG_PRINTF(fmt, ...) +# define DUMP(t) +# define DEBUG_PRINTF(fmt, ...) #endif ZixTree* @@ -72,77 +72,79 @@ zix_tree_new(bool allow_duplicates, void* cmp_data, ZixDestroyFunc destroy) { - ZixTree* t = (ZixTree*)malloc(sizeof(ZixTree)); - t->root = NULL; - t->destroy = destroy; - t->cmp = cmp; - t->cmp_data = cmp_data; - t->size = 0; - t->allow_duplicates = allow_duplicates; - return t; + ZixTree* t = (ZixTree*)malloc(sizeof(ZixTree)); + t->root = NULL; + t->destroy = destroy; + t->cmp = cmp; + t->cmp_data = cmp_data; + t->size = 0; + t->allow_duplicates = allow_duplicates; + return t; } -ZIX_PRIVATE void +ZIX_PRIVATE +void zix_tree_free_rec(ZixTree* t, ZixTreeNode* n) { - if (n) { - zix_tree_free_rec(t, n->left); - zix_tree_free_rec(t, n->right); - if (t->destroy) { - t->destroy(n->data); - } - free(n); - } + if (n) { + zix_tree_free_rec(t, n->left); + zix_tree_free_rec(t, n->right); + if (t->destroy) { + t->destroy(n->data); + } + free(n); + } } void zix_tree_free(ZixTree* t) { - if (t) { - zix_tree_free_rec(t, t->root); - free(t); - } + if (t) { + zix_tree_free_rec(t, t->root); + free(t); + } } size_t zix_tree_size(const ZixTree* t) { - return t->size; + return t->size; } -ZIX_PRIVATE void +ZIX_PRIVATE +void rotate(ZixTreeNode* p, ZixTreeNode* q) { - assert(q->parent == p); - assert(p->left == q || p->right == q); - - q->parent = p->parent; - if (q->parent) { - if (q->parent->left == p) { - q->parent->left = q; - } else { - q->parent->right = q; - } - } - - if (p->right == q) { - // Rotate left - p->right = q->left; - q->left = p; - if (p->right) { - p->right->parent = p; - } - } else { - // Rotate right - assert(p->left == q); - p->left = q->right; - q->right = p; - if (p->left) { - p->left->parent = p; - } - } - - p->parent = q; + assert(q->parent == p); + assert(p->left == q || p->right == q); + + q->parent = p->parent; + if (q->parent) { + if (q->parent->left == p) { + q->parent->left = q; + } else { + q->parent->right = q; + } + } + + if (p->right == q) { + // Rotate left + p->right = q->left; + q->left = p; + if (p->right) { + p->right->parent = p; + } + } else { + // Rotate right + assert(p->left == q); + p->left = q->right; + q->right = p; + if (p->left) { + p->left->parent = p; + } + } + + p->parent = q; } /** @@ -154,27 +156,28 @@ rotate(ZixTreeNode* p, ZixTreeNode* q) * / \ / \ * B C A B */ -ZIX_PRIVATE ZixTreeNode* +ZIX_PRIVATE +ZixTreeNode* rotate_left(ZixTreeNode* p, int* height_change) { - ZixTreeNode* const q = p->right; - *height_change = (q->balance == 0) ? 0 : -1; + ZixTreeNode* const q = p->right; + *height_change = (q->balance == 0) ? 0 : -1; - DEBUG_PRINTF("LL %ld\n", (intptr_t)p->data); + DEBUG_PRINTF("LL %ld\n", (intptr_t)p->data); - assert(p->balance == 2); - assert(q->balance == 0 || q->balance == 1); + assert(p->balance == 2); + assert(q->balance == 0 || q->balance == 1); - rotate(p, q); + rotate(p, q); - // p->balance -= 1 + MAX(0, q->balance); - // q->balance -= 1 - MIN(0, p->balance); - --q->balance; - p->balance = -(q->balance); + // p->balance -= 1 + MAX(0, q->balance); + // q->balance -= 1 - MIN(0, p->balance); + --q->balance; + p->balance = -(q->balance); - ASSERT_BALANCE(p); - ASSERT_BALANCE(q); - return q; + ASSERT_BALANCE(p); + ASSERT_BALANCE(q); + return q; } /** @@ -187,27 +190,28 @@ rotate_left(ZixTreeNode* p, int* height_change) * A B B C * */ -ZIX_PRIVATE ZixTreeNode* +ZIX_PRIVATE +ZixTreeNode* rotate_right(ZixTreeNode* p, int* height_change) { - ZixTreeNode* const q = p->left; - *height_change = (q->balance == 0) ? 0 : -1; + ZixTreeNode* const q = p->left; + *height_change = (q->balance == 0) ? 0 : -1; - DEBUG_PRINTF("RR %ld\n", (intptr_t)p->data); + DEBUG_PRINTF("RR %ld\n", (intptr_t)p->data); - assert(p->balance == -2); - assert(q->balance == 0 || q->balance == -1); + assert(p->balance == -2); + assert(q->balance == 0 || q->balance == -1); - rotate(p, q); + rotate(p, q); - // p->balance += 1 - MIN(0, q->balance); - // q->balance += 1 + MAX(0, p->balance); - ++q->balance; - p->balance = -(q->balance); + // p->balance += 1 - MIN(0, q->balance); + // q->balance += 1 + MAX(0, p->balance); + ++q->balance; + p->balance = -(q->balance); - ASSERT_BALANCE(p); - ASSERT_BALANCE(q); - return q; + ASSERT_BALANCE(p); + ASSERT_BALANCE(q); + return q; } /** @@ -222,36 +226,40 @@ rotate_right(ZixTreeNode* p, int* height_change) * B C * */ -ZIX_PRIVATE ZixTreeNode* +ZIX_PRIVATE +ZixTreeNode* rotate_left_right(ZixTreeNode* p, int* height_change) { - ZixTreeNode* const q = p->left; - ZixTreeNode* const r = q->right; + ZixTreeNode* const q = p->left; + ZixTreeNode* const r = q->right; - assert(p->balance == -2); - assert(q->balance == 1); - assert(r->balance == -1 || r->balance == 0 || r->balance == 1); + assert(p->balance == -2); + assert(q->balance == 1); + assert(r->balance == -1 || r->balance == 0 || r->balance == 1); - DEBUG_PRINTF("LR %ld P: %2d Q: %2d R: %2d\n", - (intptr_t)p->data, p->balance, q->balance, r->balance); + DEBUG_PRINTF("LR %ld P: %2d Q: %2d R: %2d\n", + (intptr_t)p->data, + p->balance, + q->balance, + r->balance); - rotate(q, r); - rotate(p, r); + rotate(q, r); + rotate(p, r); - q->balance -= 1 + MAX(0, r->balance); - p->balance += 1 - MIN(MIN(0, r->balance) - 1, r->balance + q->balance); - // r->balance += MAX(0, p->balance) + MIN(0, q->balance); + q->balance -= 1 + MAX(0, r->balance); + p->balance += 1 - MIN(MIN(0, r->balance) - 1, r->balance + q->balance); + // r->balance += MAX(0, p->balance) + MIN(0, q->balance); - // p->balance = (p->left && p->right) ? -MIN(r->balance, 0) : 0; - // q->balance = - MAX(r->balance, 0); - r->balance = 0; + // p->balance = (p->left && p->right) ? -MIN(r->balance, 0) : 0; + // q->balance = - MAX(r->balance, 0); + r->balance = 0; - *height_change = -1; + *height_change = -1; - ASSERT_BALANCE(p); - ASSERT_BALANCE(q); - ASSERT_BALANCE(r); - return r; + ASSERT_BALANCE(p); + ASSERT_BALANCE(q); + ASSERT_BALANCE(r); + return r; } /** @@ -266,451 +274,462 @@ rotate_left_right(ZixTreeNode* p, int* height_change) * B C * */ -ZIX_PRIVATE ZixTreeNode* +ZIX_PRIVATE +ZixTreeNode* rotate_right_left(ZixTreeNode* p, int* height_change) { - ZixTreeNode* const q = p->right; - ZixTreeNode* const r = q->left; + ZixTreeNode* const q = p->right; + ZixTreeNode* const r = q->left; - assert(p->balance == 2); - assert(q->balance == -1); - assert(r->balance == -1 || r->balance == 0 || r->balance == 1); + assert(p->balance == 2); + assert(q->balance == -1); + assert(r->balance == -1 || r->balance == 0 || r->balance == 1); - DEBUG_PRINTF("RL %ld P: %2d Q: %2d R: %2d\n", - (intptr_t)p->data, p->balance, q->balance, r->balance); + DEBUG_PRINTF("RL %ld P: %2d Q: %2d R: %2d\n", + (intptr_t)p->data, + p->balance, + q->balance, + r->balance); - rotate(q, r); - rotate(p, r); + rotate(q, r); + rotate(p, r); - q->balance += 1 - MIN(0, r->balance); - p->balance -= 1 + MAX(MAX(0, r->balance) + 1, r->balance + q->balance); - // r->balance += MAX(0, q->balance) + MIN(0, p->balance); + q->balance += 1 - MIN(0, r->balance); + p->balance -= 1 + MAX(MAX(0, r->balance) + 1, r->balance + q->balance); + // r->balance += MAX(0, q->balance) + MIN(0, p->balance); - // p->balance = (p->left && p->right) ? -MAX(r->balance, 0) : 0; - // q->balance = - MIN(r->balance, 0); - r->balance = 0; - // assert(r->balance == 0); + // p->balance = (p->left && p->right) ? -MAX(r->balance, 0) : 0; + // q->balance = - MIN(r->balance, 0); + r->balance = 0; + // assert(r->balance == 0); - *height_change = -1; + *height_change = -1; - ASSERT_BALANCE(p); - ASSERT_BALANCE(q); - ASSERT_BALANCE(r); - return r; + ASSERT_BALANCE(p); + ASSERT_BALANCE(q); + ASSERT_BALANCE(r); + return r; } -ZIX_PRIVATE ZixTreeNode* +ZIX_PRIVATE +ZixTreeNode* zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change) { #ifdef ZIX_TREE_HYPER_VERIFY - const size_t old_height = height(node); + const size_t old_height = height(node); #endif - DEBUG_PRINTF("REBALANCE %ld (%d)\n", (intptr_t)node->data, node->balance); - *height_change = 0; - const bool is_root = !node->parent; - assert((is_root && t->root == node) || (!is_root && t->root != node)); - ZixTreeNode* replacement = node; - if (node->balance == -2) { - assert(node->left); - if (node->left->balance == 1) { - replacement = rotate_left_right(node, height_change); - } else { - replacement = rotate_right(node, height_change); - } - } else if (node->balance == 2) { - assert(node->right); - if (node->right->balance == -1) { - replacement = rotate_right_left(node, height_change); - } else { - replacement = rotate_left(node, height_change); - } - } - if (is_root) { - assert(!replacement->parent); - t->root = replacement; - } - DUMP(t); + DEBUG_PRINTF("REBALANCE %ld (%d)\n", (intptr_t)node->data, node->balance); + *height_change = 0; + const bool is_root = !node->parent; + assert((is_root && t->root == node) || (!is_root && t->root != node)); + ZixTreeNode* replacement = node; + if (node->balance == -2) { + assert(node->left); + if (node->left->balance == 1) { + replacement = rotate_left_right(node, height_change); + } else { + replacement = rotate_right(node, height_change); + } + } else if (node->balance == 2) { + assert(node->right); + if (node->right->balance == -1) { + replacement = rotate_right_left(node, height_change); + } else { + replacement = rotate_left(node, height_change); + } + } + if (is_root) { + assert(!replacement->parent); + t->root = replacement; + } + DUMP(t); #ifdef ZIX_TREE_HYPER_VERIFY - assert(old_height + *height_change == height(replacement)); + assert(old_height + *height_change == height(replacement)); #endif - return replacement; + return replacement; } ZixStatus zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti) { - DEBUG_PRINTF("**** INSERT %ld\n", (intptr_t)e); - int cmp = 0; - ZixTreeNode* n = t->root; - ZixTreeNode* p = NULL; - - // Find the parent p of e - while (n) { - p = n; - cmp = t->cmp(e, n->data, t->cmp_data); - if (cmp < 0) { - n = n->left; - } else if (cmp > 0 || t->allow_duplicates) { - n = n->right; - } else { - if (ti) { - *ti = n; - } - DEBUG_PRINTF("%ld EXISTS!\n", (intptr_t)e); - return ZIX_STATUS_EXISTS; - } - } - - // Allocate a new node n - if (!(n = (ZixTreeNode*)malloc(sizeof(ZixTreeNode)))) { - return ZIX_STATUS_NO_MEM; - } - memset(n, '\0', sizeof(ZixTreeNode)); - n->data = e; - n->balance = 0; - if (ti) { - *ti = n; - } - - bool p_height_increased = false; - - // Make p the parent of n - n->parent = p; - if (!p) { - t->root = n; - } else { - if (cmp < 0) { - assert(!p->left); - assert(p->balance == 0 || p->balance == 1); - p->left = n; - --p->balance; - p_height_increased = !p->right; - } else { - assert(!p->right); - assert(p->balance == 0 || p->balance == -1); - p->right = n; - ++p->balance; - p_height_increased = !p->left; - } - } - - DUMP(t); - - // Rebalance if necessary (at most 1 rotation) - assert(!p || p->balance == -1 || p->balance == 0 || p->balance == 1); - if (p && p_height_increased) { - int height_change = 0; - for (ZixTreeNode* i = p; i && i->parent; i = i->parent) { - if (i == i->parent->left) { - if (--i->parent->balance == -2) { - zix_tree_rebalance(t, i->parent, &height_change); - break; - } - } else { - assert(i == i->parent->right); - if (++i->parent->balance == 2) { - zix_tree_rebalance(t, i->parent, &height_change); - break; - } - } - - if (i->parent->balance == 0) { - break; - } - } - } - - DUMP(t); - - ++t->size; + DEBUG_PRINTF("**** INSERT %ld\n", (intptr_t)e); + int cmp = 0; + ZixTreeNode* n = t->root; + ZixTreeNode* p = NULL; + + // Find the parent p of e + while (n) { + p = n; + cmp = t->cmp(e, n->data, t->cmp_data); + if (cmp < 0) { + n = n->left; + } else if (cmp > 0 || t->allow_duplicates) { + n = n->right; + } else { + if (ti) { + *ti = n; + } + DEBUG_PRINTF("%ld EXISTS!\n", (intptr_t)e); + return ZIX_STATUS_EXISTS; + } + } + + // Allocate a new node n + if (!(n = (ZixTreeNode*)malloc(sizeof(ZixTreeNode)))) { + return ZIX_STATUS_NO_MEM; + } + memset(n, '\0', sizeof(ZixTreeNode)); + n->data = e; + n->balance = 0; + if (ti) { + *ti = n; + } + + bool p_height_increased = false; + + // Make p the parent of n + n->parent = p; + if (!p) { + t->root = n; + } else { + if (cmp < 0) { + assert(!p->left); + assert(p->balance == 0 || p->balance == 1); + p->left = n; + --p->balance; + p_height_increased = !p->right; + } else { + assert(!p->right); + assert(p->balance == 0 || p->balance == -1); + p->right = n; + ++p->balance; + p_height_increased = !p->left; + } + } + + DUMP(t); + + // Rebalance if necessary (at most 1 rotation) + assert(!p || p->balance == -1 || p->balance == 0 || p->balance == 1); + if (p && p_height_increased) { + int height_change = 0; + for (ZixTreeNode* i = p; i && i->parent; i = i->parent) { + if (i == i->parent->left) { + if (--i->parent->balance == -2) { + zix_tree_rebalance(t, i->parent, &height_change); + break; + } + } else { + assert(i == i->parent->right); + if (++i->parent->balance == 2) { + zix_tree_rebalance(t, i->parent, &height_change); + break; + } + } + + if (i->parent->balance == 0) { + break; + } + } + } + + DUMP(t); + + ++t->size; #ifdef ZIX_TREE_VERIFY - if (!verify(t, t->root)) { - return ZIX_STATUS_ERROR; - } + if (!verify(t, t->root)) { + return ZIX_STATUS_ERROR; + } #endif - return ZIX_STATUS_SUCCESS; + return ZIX_STATUS_SUCCESS; } ZixStatus zix_tree_remove(ZixTree* t, ZixTreeIter* ti) { - ZixTreeNode* const n = ti; - ZixTreeNode** pp = NULL; // parent pointer - ZixTreeNode* to_balance = n->parent; // lowest node to balance - int8_t d_balance = 0; // delta(balance) for n->parent - - DEBUG_PRINTF("*** REMOVE %ld\n", (intptr_t)n->data); - - if ((n == t->root) && !n->left && !n->right) { - t->root = NULL; - if (t->destroy) { - t->destroy(n->data); - } - free(n); - --t->size; - assert(t->size == 0); - return ZIX_STATUS_SUCCESS; - } - - // Set pp to the parent pointer to n, if applicable - if (n->parent) { - assert(n->parent->left == n || n->parent->right == n); - if (n->parent->left == n) { // n is left child - pp = &n->parent->left; - d_balance = 1; - } else { // n is right child - assert(n->parent->right == n); - pp = &n->parent->right; - d_balance = -1; - } - } - - assert(!pp || *pp == n); - - int height_change = 0; - if (!n->left && !n->right) { - // n is a leaf, just remove it - if (pp) { - *pp = NULL; - to_balance = n->parent; - height_change = (!n->parent->left && !n->parent->right) ? -1 : 0; - } - } else if (!n->left) { - // Replace n with right (only) child - if (pp) { - *pp = n->right; - to_balance = n->parent; - } else { - t->root = n->right; - } - n->right->parent = n->parent; - height_change = -1; - } else if (!n->right) { - // Replace n with left (only) child - if (pp) { - *pp = n->left; - to_balance = n->parent; - } else { - t->root = n->left; - } - n->left->parent = n->parent; - height_change = -1; - } else { - // Replace n with in-order successor (leftmost child of right subtree) - ZixTreeNode* replace = n->right; - while (replace->left) { - assert(replace->left->parent == replace); - replace = replace->left; - } - - // Remove replace from parent (replace_p) - if (replace->parent->left == replace) { - height_change = replace->parent->right ? 0 : -1; - d_balance = 1; - to_balance = replace->parent; - replace->parent->left = replace->right; - } else { - assert(replace->parent == n); - height_change = replace->parent->left ? 0 : -1; - d_balance = -1; - to_balance = replace->parent; - replace->parent->right = replace->right; - } - - if (to_balance == n) { - to_balance = replace; - } - - if (replace->right) { - replace->right->parent = replace->parent; - } - - replace->balance = n->balance; - - // Swap node to delete with replace - if (pp) { - *pp = replace; - } else { - assert(t->root == n); - t->root = replace; - } - replace->parent = n->parent; - replace->left = n->left; - n->left->parent = replace; - replace->right = n->right; - if (n->right) { - n->right->parent = replace; - } - - assert(!replace->parent - || replace->parent->left == replace - || replace->parent->right == replace); - } - - // Rebalance starting at to_balance upwards. - for (ZixTreeNode* i = to_balance; i; i = i->parent) { - i->balance += d_balance; - if (d_balance == 0 || i->balance == -1 || i->balance == 1) { - break; - } - - assert(i != n); - i = zix_tree_rebalance(t, i, &height_change); - if (i->balance == 0) { - height_change = -1; - } - - if (i->parent) { - if (i == i->parent->left) { - d_balance = (uint8_t)height_change * -1; - } else { - assert(i == i->parent->right); - d_balance = (uint8_t)height_change; - } - } - } - - DUMP(t); - - if (t->destroy) { - t->destroy(n->data); - } - free(n); - - --t->size; + ZixTreeNode* const n = ti; + ZixTreeNode** pp = NULL; // parent pointer + ZixTreeNode* to_balance = n->parent; // lowest node to balance + int8_t d_balance = 0; // delta(balance) for n->parent + + DEBUG_PRINTF("*** REMOVE %ld\n", (intptr_t)n->data); + + if ((n == t->root) && !n->left && !n->right) { + t->root = NULL; + if (t->destroy) { + t->destroy(n->data); + } + free(n); + --t->size; + assert(t->size == 0); + return ZIX_STATUS_SUCCESS; + } + + // Set pp to the parent pointer to n, if applicable + if (n->parent) { + assert(n->parent->left == n || n->parent->right == n); + if (n->parent->left == n) { // n is left child + pp = &n->parent->left; + d_balance = 1; + } else { // n is right child + assert(n->parent->right == n); + pp = &n->parent->right; + d_balance = -1; + } + } + + assert(!pp || *pp == n); + + int height_change = 0; + if (!n->left && !n->right) { + // n is a leaf, just remove it + if (pp) { + *pp = NULL; + to_balance = n->parent; + height_change = (!n->parent->left && !n->parent->right) ? -1 : 0; + } + + } else if (!n->left) { + // Replace n with right (only) child + if (pp) { + *pp = n->right; + to_balance = n->parent; + } else { + t->root = n->right; + } + n->right->parent = n->parent; + height_change = -1; + + } else if (!n->right) { + // Replace n with left (only) child + if (pp) { + *pp = n->left; + to_balance = n->parent; + } else { + t->root = n->left; + } + n->left->parent = n->parent; + height_change = -1; + + } else { + // Replace n with in-order successor (leftmost child of right subtree) + ZixTreeNode* replace = n->right; + while (replace->left) { + assert(replace->left->parent == replace); + replace = replace->left; + } + + // Remove replace from parent (replace_p) + if (replace->parent->left == replace) { + height_change = replace->parent->right ? 0 : -1; + d_balance = 1; + to_balance = replace->parent; + replace->parent->left = replace->right; + } else { + assert(replace->parent == n); + height_change = replace->parent->left ? 0 : -1; + d_balance = -1; + to_balance = replace->parent; + replace->parent->right = replace->right; + } + + if (to_balance == n) { + to_balance = replace; + } + + if (replace->right) { + replace->right->parent = replace->parent; + } + + replace->balance = n->balance; + + // Swap node to delete with replace + if (pp) { + *pp = replace; + } else { + assert(t->root == n); + t->root = replace; + } + + replace->parent = n->parent; + replace->left = n->left; + n->left->parent = replace; + replace->right = n->right; + if (n->right) { + n->right->parent = replace; + } + + assert(!replace->parent || replace->parent->left == replace || + replace->parent->right == replace); + } + + // Rebalance starting at to_balance upwards. + for (ZixTreeNode* i = to_balance; i; i = i->parent) { + i->balance += d_balance; + if (d_balance == 0 || i->balance == -1 || i->balance == 1) { + break; + } + + assert(i != n); + i = zix_tree_rebalance(t, i, &height_change); + if (i->balance == 0) { + height_change = -1; + } + + if (i->parent) { + if (i == i->parent->left) { + d_balance = (uint8_t)height_change * -1; + } else { + assert(i == i->parent->right); + d_balance = (uint8_t)height_change; + } + } + } + + DUMP(t); + + if (t->destroy) { + t->destroy(n->data); + } + free(n); + + --t->size; #ifdef ZIX_TREE_VERIFY - if (!verify(t, t->root)) { - return ZIX_STATUS_ERROR; - } + if (!verify(t, t->root)) { + return ZIX_STATUS_ERROR; + } #endif - return ZIX_STATUS_SUCCESS; + return ZIX_STATUS_SUCCESS; } ZixStatus zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti) { - ZixTreeNode* n = t->root; - while (n) { - const int cmp = t->cmp(e, n->data, t->cmp_data); - if (cmp == 0) { - break; - } - - if (cmp < 0) { - n = n->left; - } else { - n = n->right; - } - } - - *ti = n; - return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND; + ZixTreeNode* n = t->root; + while (n) { + const int cmp = t->cmp(e, n->data, t->cmp_data); + if (cmp == 0) { + break; + } + + if (cmp < 0) { + n = n->left; + } else { + n = n->right; + } + } + + *ti = n; + return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND; } void* zix_tree_get(const ZixTreeIter* ti) { - return ti ? ti->data : NULL; + return ti ? ti->data : NULL; } ZixTreeIter* zix_tree_begin(ZixTree* t) { - if (!t->root) { - return NULL; - } - - ZixTreeNode* n = t->root; - while (n->left) { - n = n->left; - } - return n; + if (!t->root) { + return NULL; + } + + ZixTreeNode* n = t->root; + while (n->left) { + n = n->left; + } + + return n; } ZixTreeIter* zix_tree_end(ZixTree* ZIX_UNUSED(t)) { - return NULL; + return NULL; } ZixTreeIter* zix_tree_rbegin(ZixTree* t) { - if (!t->root) { - return NULL; - } - - ZixTreeNode* n = t->root; - while (n->right) { - n = n->right; - } - return n; + if (!t->root) { + return NULL; + } + + ZixTreeNode* n = t->root; + while (n->right) { + n = n->right; + } + + return n; } ZixTreeIter* zix_tree_rend(ZixTree* ZIX_UNUSED(t)) { - return NULL; + return NULL; } bool zix_tree_iter_is_end(const ZixTreeIter* i) { - return !i; + return !i; } bool zix_tree_iter_is_rend(const ZixTreeIter* i) { - return !i; + return !i; } ZixTreeIter* zix_tree_iter_next(ZixTreeIter* i) { - if (!i) { - return NULL; - } - - if (i->right) { - i = i->right; - while (i->left) { - i = i->left; - } - } else { - while (i->parent && i->parent->right == i) { // i is a right child - i = i->parent; - } - - i = i->parent; - } - - return i; + if (!i) { + return NULL; + } + + if (i->right) { + i = i->right; + while (i->left) { + i = i->left; + } + } else { + while (i->parent && i->parent->right == i) { // i is a right child + i = i->parent; + } + + i = i->parent; + } + + return i; } ZixTreeIter* zix_tree_iter_prev(ZixTreeIter* i) { - if (!i) { - return NULL; - } - - if (i->left) { - i = i->left; - while (i->right) { - i = i->right; - } - } else { - while (i->parent && i->parent->left == i) { // i is a left child - i = i->parent; - } - - i = i->parent; - } - - return i; + if (!i) { + return NULL; + } + + if (i->left) { + i = i->left; + while (i->right) { + i = i->right; + } + + } else { + while (i->parent && i->parent->left == i) { // i is a left child + i = i->parent; + } + + i = i->parent; + } + + return i; } @@ -46,7 +46,8 @@ typedef struct ZixTreeNodeImpl ZixTreeIter; /** Create a new (empty) tree. */ -ZIX_API ZixTree* +ZIX_API +ZixTree* zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data, @@ -55,86 +56,100 @@ zix_tree_new(bool allow_duplicates, /** Free `t`. */ -ZIX_API void +ZIX_API +void zix_tree_free(ZixTree* t); /** Return the number of elements in `t`. */ -ZIX_PURE_API size_t +ZIX_PURE_API +size_t zix_tree_size(const ZixTree* t); /** Insert the element `e` into `t` and point `ti` at the new element. */ -ZIX_API ZixStatus +ZIX_API +ZixStatus zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti); /** Remove the item pointed at by `ti` from `t`. */ -ZIX_API ZixStatus +ZIX_API +ZixStatus zix_tree_remove(ZixTree* t, ZixTreeIter* ti); /** Set `ti` to an element equal to `e` in `t`. If no such item exists, `ti` is set to NULL. */ -ZIX_API ZixStatus +ZIX_API +ZixStatus zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti); /** Return the data associated with the given tree item. */ -ZIX_PURE_API void* +ZIX_PURE_API +void* zix_tree_get(const ZixTreeIter* ti); /** Return an iterator to the first (smallest) element in `t`. */ -ZIX_PURE_API ZixTreeIter* +ZIX_PURE_API +ZixTreeIter* zix_tree_begin(ZixTree* t); /** Return an iterator the the element one past the last element in `t`. */ -ZIX_CONST_API ZixTreeIter* +ZIX_CONST_API +ZixTreeIter* zix_tree_end(ZixTree* t); /** Return true iff `i` is an iterator to the end of its tree. */ -ZIX_CONST_API bool +ZIX_CONST_API +bool zix_tree_iter_is_end(const ZixTreeIter* i); /** Return an iterator to the last (largest) element in `t`. */ -ZIX_PURE_API ZixTreeIter* +ZIX_PURE_API +ZixTreeIter* zix_tree_rbegin(ZixTree* t); /** Return an iterator the the element one before the first element in `t`. */ -ZIX_CONST_API ZixTreeIter* +ZIX_CONST_API +ZixTreeIter* zix_tree_rend(ZixTree* t); /** Return true iff `i` is an iterator to the reverse end of its tree. */ -ZIX_CONST_API bool +ZIX_CONST_API +bool zix_tree_iter_is_rend(const ZixTreeIter* i); /** Return an iterator that points to the element one past `i`. */ -ZIX_PURE_API ZixTreeIter* +ZIX_PURE_API +ZixTreeIter* zix_tree_iter_next(ZixTreeIter* i); /** Return an iterator that points to the element one before `i`. */ -ZIX_PURE_API ZixTreeIter* +ZIX_PURE_API +ZixTreeIter* zix_tree_iter_prev(ZixTreeIter* i); /** @@ -143,7 +158,7 @@ zix_tree_iter_prev(ZixTreeIter* i); */ #ifdef __cplusplus -} /* extern "C" */ +} /* extern "C" */ #endif -#endif /* ZIX_TREE_H */ +#endif /* ZIX_TREE_H */ diff --git a/zix/tree_debug.h b/zix/tree_debug.h index ff9311e..68e37b6 100644 --- a/zix/tree_debug.h +++ b/zix/tree_debug.h @@ -23,20 +23,22 @@ static void zix_tree_print(ZixTreeNode* node, int level) { - if (node) { - if (!node->parent) { - printf("{{{\n"); - } - zix_tree_print(node->right, level + 1); - for (int i = 0; i < level; i++) { - printf(" "); - } - printf("%ld.%d\n", (intptr_t)node->data, node->balance); - zix_tree_print(node->left, level + 1); - if (!node->parent) { - printf("}}}\n"); - } - } + if (node) { + if (!node->parent) { + printf("{{{\n"); + } + + zix_tree_print(node->right, level + 1); + for (int i = 0; i < level; i++) { + printf(" "); + } + + printf("%ld.%d\n", (intptr_t)node->data, node->balance); + zix_tree_print(node->left, level + 1); + if (!node->parent) { + printf("}}}\n"); + } + } } #endif @@ -44,11 +46,11 @@ zix_tree_print(ZixTreeNode* node, int level) static size_t height(ZixTreeNode* n) { - if (!n) { - return 0; - } else { - return 1 + MAX(height(n->left), height(n->right)); - } + if (!n) { + return 0; + } else { + return 1 + MAX(height(n->left), height(n->right)); + } } #endif @@ -56,47 +58,59 @@ height(ZixTreeNode* n) static bool verify_balance(ZixTreeNode* n) { - if (!n) { - return true; - } - - if (n->balance < -2 || n->balance > 2) { - fprintf(stderr, "Balance out of range : %ld (balance %d)\n", - (intptr_t)n->data, n->balance); - return false; - } - - if (n->balance < 0 && !n->left) { - fprintf(stderr, "Bad balance : %ld (balance %d) has no left child\n", - (intptr_t)n->data, n->balance); - return false; - } - - if (n->balance > 0 && !n->right) { - fprintf(stderr, "Bad balance : %ld (balance %d) has no right child\n", - (intptr_t)n->data, n->balance); - return false; - } - - if (n->balance != 0 && !n->left && !n->right) { - fprintf(stderr, "Bad balance : %ld (balance %d) has no children\n", - (intptr_t)n->data, n->balance); - return false; - } - -#ifdef ZIX_TREE_HYPER_VERIFY - const intptr_t left_height = (intptr_t)height(n->left); - const intptr_t right_height = (intptr_t)height(n->right); - if (n->balance != right_height - left_height) { - fprintf(stderr, "Bad balance at %ld: h_r (%" PRIdPTR ")" - "- l_h (%" PRIdPTR ") != %d\n", - (intptr_t)n->data, right_height, left_height, n->balance); - assert(false); - return false; - } -#endif - - return true; + if (!n) { + return true; + } + + if (n->balance < -2 || n->balance > 2) { + fprintf(stderr, + "Balance out of range : %ld (balance %d)\n", + (intptr_t)n->data, + n->balance); + return false; + } + + if (n->balance < 0 && !n->left) { + fprintf(stderr, + "Bad balance : %ld (balance %d) has no left child\n", + (intptr_t)n->data, + n->balance); + return false; + } + + if (n->balance > 0 && !n->right) { + fprintf(stderr, + "Bad balance : %ld (balance %d) has no right child\n", + (intptr_t)n->data, + n->balance); + return false; + } + + if (n->balance != 0 && !n->left && !n->right) { + fprintf(stderr, + "Bad balance : %ld (balance %d) has no children\n", + (intptr_t)n->data, + n->balance); + return false; + } + +# ifdef ZIX_TREE_HYPER_VERIFY + const intptr_t left_height = (intptr_t)height(n->left); + const intptr_t right_height = (intptr_t)height(n->right); + if (n->balance != right_height - left_height) { + fprintf(stderr, + "Bad balance at %ld: h_r (%" PRIdPTR ")" + "- l_h (%" PRIdPTR ") != %d\n", + (intptr_t)n->data, + right_height, + left_height, + n->balance); + assert(false); + return false; + } +# endif + + return true; } #endif @@ -104,54 +118,58 @@ verify_balance(ZixTreeNode* n) static bool verify(ZixTree* t, ZixTreeNode* n) { - if (!n) { - return true; - } - - if (n->parent) { - if ((n->parent->left != n) && (n->parent->right != n)) { - fprintf(stderr, "Corrupt child/parent pointers\n"); - return false; - } - } - - if (n->left) { - if (t->cmp(n->left->data, n->data, t->cmp_data) > 0) { - fprintf(stderr, "Bad order: %" PRIdPTR " with left child\n", - (intptr_t)n->data); - fprintf(stderr, "%p ? %p\n", (void*)n, (void*)n->left); - fprintf(stderr, "%" PRIdPTR " ? %" PRIdPTR "\n", (intptr_t)n->data, - (intptr_t)n->left->data); - return false; - } - if (!verify(t, n->left)) { - return false; - } - } - - if (n->right) { - if (t->cmp(n->right->data, n->data, t->cmp_data) < 0) { - fprintf(stderr, "Bad order: %" PRIdPTR " with right child\n", - (intptr_t)n->data); - return false; - } - if (!verify(t, n->right)) { - return false; - } - } - - if (!verify_balance(n)) { - return false; - } - - if (n->balance <= -2 || n->balance >= 2) { - fprintf(stderr, "Imbalance: %p (balance %d)\n", - (void*)n, n->balance); - return false; - } - - return true; + if (!n) { + return true; + } + + if (n->parent) { + if ((n->parent->left != n) && (n->parent->right != n)) { + fprintf(stderr, "Corrupt child/parent pointers\n"); + return false; + } + } + + if (n->left) { + if (t->cmp(n->left->data, n->data, t->cmp_data) > 0) { + fprintf( + stderr, "Bad order: %" PRIdPTR " with left child\n", (intptr_t)n->data); + fprintf(stderr, "%p ? %p\n", (void*)n, (void*)n->left); + fprintf(stderr, + "%" PRIdPTR " ? %" PRIdPTR "\n", + (intptr_t)n->data, + (intptr_t)n->left->data); + return false; + } + + if (!verify(t, n->left)) { + return false; + } + } + + if (n->right) { + if (t->cmp(n->right->data, n->data, t->cmp_data) < 0) { + fprintf(stderr, + "Bad order: %" PRIdPTR " with right child\n", + (intptr_t)n->data); + return false; + } + + if (!verify(t, n->right)) { + return false; + } + } + + if (!verify_balance(n)) { + return false; + } + + if (n->balance <= -2 || n->balance >= 2) { + fprintf(stderr, "Imbalance: %p (balance %d)\n", (void*)n, n->balance); + return false; + } + + return true; } #endif -#endif // ZIX_TREE_DEBUG_H +#endif // ZIX_TREE_DEBUG_H @@ -32,4 +32,4 @@ @} */ -#endif /* ZIX_ZIX_H */ +#endif /* ZIX_ZIX_H */ |