summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--benchmark/.clang-tidy4
-rw-r--r--benchmark/dict_bench.c16
-rw-r--r--benchmark/tree_bench.c18
-rw-r--r--test/.clang-tidy2
-rw-r--r--test/btree_test.c19
-rw-r--r--test/sorted_array_test.c17
-rw-r--r--test/test_data.h59
-rw-r--r--test/tree_test.c17
8 files changed, 83 insertions, 69 deletions
diff --git a/benchmark/.clang-tidy b/benchmark/.clang-tidy
index 06febc0..2c16e13 100644
--- a/benchmark/.clang-tidy
+++ b/benchmark/.clang-tidy
@@ -7,10 +7,6 @@ Checks: >
-bugprone-suspicious-string-compare,
-cert-dcl37-c,
-cert-dcl51-cpp,
- -cert-msc30-c,
- -cert-msc32-c,
- -cert-msc50-cpp,
- -cert-msc51-cpp,
-clang-analyzer-security.insecureAPI.DeprecatedOrUnsafeBufferHandling,
-hicpp-multiway-paths-covered,
-llvm-header-guard,
diff --git a/benchmark/dict_bench.c b/benchmark/dict_bench.c
index 4a82a8f..4a77257 100644
--- a/benchmark/dict_bench.c
+++ b/benchmark/dict_bench.c
@@ -39,6 +39,16 @@ typedef struct {
size_t len;
} ZixChunk;
+/// Linear Congruential Generator for making random 64-bit integers
+static inline uint64_t
+lcg64(const uint64_t i)
+{
+ static const uint64_t a = 6364136223846793005ull;
+ static const uint64_t c = 1ull;
+
+ return (a * i) + c;
+}
+
static uint32_t
zix_chunk_hash(const ZixChunk* const chunk)
{
@@ -151,10 +161,9 @@ main(int argc, char** argv)
// 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;
+ const size_t index = lcg64(seed + i) % 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]);
@@ -163,10 +172,9 @@ main(int argc, char** argv)
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 size_t index = lcg64(seed + i) % n;
const ZixChunk key = {strings[index], lengths[index] + 1};
const ZixChunk* match = NULL;
if (!(match = (const ZixChunk*)zix_hash_find(zhash, &key))) {
diff --git a/benchmark/tree_bench.c b/benchmark/tree_bench.c
index bd274b1..9e399ba 100644
--- a/benchmark/tree_bench.c
+++ b/benchmark/tree_bench.c
@@ -17,6 +17,8 @@
#include "bench.h"
#include "warnings.h"
+#include "../test/test_data.h"
+
#include "zix/btree.h"
#include "zix/common.h"
#include "zix/tree.h"
@@ -35,22 +37,6 @@ ZIX_RESTORE_WARNINGS
// #define BENCH_SORTED_ARRAY 1
-// Return a pseudo-pseudo-pseudo-random-ish integer with no duplicates
-static size_t
-unique_rand(size_t i)
-{
- i ^= 0x5CA1AB1Eu; // 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
- }
-
- 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))
{
diff --git a/test/.clang-tidy b/test/.clang-tidy
index 9424c6a..036a68c 100644
--- a/test/.clang-tidy
+++ b/test/.clang-tidy
@@ -8,8 +8,6 @@ Checks: >
-bugprone-suspicious-string-compare,
-cert-dcl37-c,
-cert-dcl51-cpp,
- -cert-msc30-c,
- -cert-msc50-cpp,
-clang-analyzer-security.insecureAPI.DeprecatedOrUnsafeBufferHandling,
-cppcoreguidelines-avoid-non-const-global-variables,
-google-readability-casting,
diff --git a/test/btree_test.c b/test/btree_test.c
index ccb0cbc..5184392 100644
--- a/test/btree_test.c
+++ b/test/btree_test.c
@@ -18,6 +18,7 @@
#include "zix/btree.h"
+#include "test_data.h"
#include "test_malloc.h"
#include "zix/common.h"
@@ -32,22 +33,6 @@
static bool expect_failure = false;
-// Return a pseudo-pseudo-pseudo-random-ish integer with no duplicates
-static uintptr_t
-unique_rand(size_t i)
-{
- 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
- }
-
- const uint64_t residue = ((uint64_t)i * i) % prime;
- return (uintptr_t)((i <= prime / 2) ? residue : prime - residue);
-}
-
static int
int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data))
{
@@ -413,7 +398,7 @@ stress(const unsigned test_num, const 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);
+ r = ith_elem(test_num, n_elems, unique_rand(e) % n_elems);
uintptr_t removed = 0;
ZixStatus rst = zix_btree_remove(t, (void*)r, (void**)&removed, &next);
diff --git a/test/sorted_array_test.c b/test/sorted_array_test.c
index 9256118..cc87619 100644
--- a/test/sorted_array_test.c
+++ b/test/sorted_array_test.c
@@ -14,6 +14,8 @@
OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
+#include "test_data.h"
+
#include "zix/common.h"
#include "zix/sorted_array.h"
@@ -45,7 +47,7 @@ ith_elem(unsigned test_num, unsigned n_elems, unsigned i)
return n_elems - i; // Decreasing (worse case)
case 2:
default:
- return rand() % 100; // Random
+ return lcg64(seed + i) % 100u; // Pseudo-random
}
}
@@ -64,8 +66,6 @@ stress(unsigned test_num, unsigned n_elems)
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);
@@ -84,8 +84,6 @@ stress(unsigned test_num, unsigned n_elems)
}
}
- srand(seed);
-
// Search for all elements
for (unsigned i = 0; i < n_elems; ++i) {
r = ith_elem(test_num, n_elems, i);
@@ -103,8 +101,6 @@ stress(unsigned test_num, unsigned n_elems)
}
}
- srand(seed);
-
// Iterate over all elements
unsigned i = 0;
intptr_t last = -1;
@@ -137,8 +133,6 @@ stress(unsigned test_num, unsigned n_elems)
return test_fail();
}
- srand(seed);
-
// Iterate over all elements by index
last = -1;
for (i = 0; i < zix_sorted_array_size(t); ++i) {
@@ -156,8 +150,6 @@ stress(unsigned test_num, unsigned n_elems)
last = iter_data;
}
- srand(seed);
-
// Delete all elements
for (unsigned e = 0; e < n_elems; e++) {
r = ith_elem(test_num, n_elems, e);
@@ -205,7 +197,8 @@ main(int argc, char** argv)
return 1;
}
- printf("Running %u tests with %u elements (seed %u)\n", n_tests, n_elems, seed);
+ printf(
+ "Running %u tests with %u elements (seed %u)\n", n_tests, n_elems, seed);
for (unsigned i = 0; i < n_tests; ++i) {
printf(".");
diff --git a/test/test_data.h b/test/test_data.h
new file mode 100644
index 0000000..9c9a51d
--- /dev/null
+++ b/test/test_data.h
@@ -0,0 +1,59 @@
+/*
+ Copyright 2011-2021 David Robillard <d@drobilla.net>
+
+ Permission to use, copy, modify, and/or distribute this software for any
+ purpose with or without fee is hereby granted, provided that the above
+ copyright notice and this permission notice appear in all copies.
+
+ THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#ifndef ZIX_TEST_DATA_H
+#define ZIX_TEST_DATA_H
+
+#include <stddef.h>
+#include <stdint.h>
+
+/// Linear Congruential Generator for making random 32-bit integers
+static inline uint32_t
+lcg32(const uint32_t i)
+{
+ static const uint32_t a = 134775813u;
+ static const uint32_t c = 1u;
+
+ return (a * i) + c;
+}
+
+/// Linear Congruential Generator for making random 64-bit integers
+static inline uint64_t
+lcg64(const uint64_t i)
+{
+ static const uint64_t a = 6364136223846793005ull;
+ static const uint64_t c = 1ull;
+
+ return (a * i) + c;
+}
+
+/// Return a pseudo-pseudo-pseudo-random-ish integer with no duplicates
+static inline size_t
+unique_rand(size_t i)
+{
+ i ^= 0x5CA1AB1Eu; // Juggle bits to avoid linear clumps
+
+ // Largest prime < 2^32 which satisfies (2^32 = 3 mod 4)
+ static const size_t prime = 4294967291u;
+ 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;
+}
+
+#endif // ZIX_TEST_DATA_H
diff --git a/test/tree_test.c b/test/tree_test.c
index eb0eddc..4b044a1 100644
--- a/test/tree_test.c
+++ b/test/tree_test.c
@@ -14,9 +14,10 @@
OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
-#include "zix/tree.h"
+#include "test_data.h"
#include "zix/common.h"
+#include "zix/tree.h"
#include <inttypes.h>
#include <stdbool.h>
@@ -46,7 +47,7 @@ ith_elem(unsigned test_num, size_t n_elems, size_t i)
return n_elems - i; // Decreasing (worse case)
case 2:
default:
- return rand() % 100; // Random
+ return lcg64(seed + i) % 100; // Random
}
}
@@ -63,8 +64,6 @@ stress(unsigned test_num, size_t n_elems)
ZixTreeIter* ti = NULL;
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);
@@ -91,8 +90,6 @@ stress(unsigned test_num, 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);
@@ -109,8 +106,6 @@ stress(unsigned test_num, size_t n_elems)
}
}
- srand(seed);
-
// Iterate over all elements
size_t i = 0;
intptr_t last = -1;
@@ -134,8 +129,6 @@ stress(unsigned test_num, size_t n_elems)
return test_fail();
}
- srand(seed);
-
// Iterate over all elements backwards
i = 0;
last = INTPTR_MAX;
@@ -152,8 +145,6 @@ stress(unsigned test_num, size_t n_elems)
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);
@@ -174,8 +165,6 @@ stress(unsigned test_num, size_t n_elems)
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);
generated by cgit v1.2.1 (git 2.18.0) at 2024-06-26 18:18:38 +0000