aboutsummaryrefslogtreecommitdiffstats
path: root/test.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--test.c118
1 files changed, 118 insertions, 0 deletions
diff --git a/test.c b/test.c
new file mode 100644
index 0000000..f38bb99
--- /dev/null
+++ b/test.c
@@ -0,0 +1,118 @@
+#define _GNU_SOURCE
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#include "binary-multisearch.h"
+
+
+static struct binary_multisearch_stack_entry stack[16];
+static ssize_t result[1 << 16];
+static short int sought[1 << 16];
+static short int list[1 << 16];
+static size_t sought_count;
+static size_t list_count;
+
+
+static int
+cmp(const void *a, const void *b, void *data)
+{
+ const short int *x = a, *y = b;
+ (void) data;
+ return *x < *y ? -1 : *x > *y;
+}
+
+static short int
+random16(short int mask)
+{
+ return (short int)((((rand() & 255) << 8) | (rand() & 255)) & mask);
+}
+
+static void
+fill_random16(short int arr[], size_t n, short int mask)
+{
+ while (n--)
+ arr[n] = random16(mask);
+}
+
+static size_t
+uniq(short int arr[], size_t n)
+{
+ size_t r, w = (n > 0);
+ for (r = 1; r < n; r++)
+ if (arr[r] != arr[r - 1])
+ arr[w++] = arr[r];
+ return w;
+}
+
+static void
+test(size_t sn, size_t ln, short int mask)
+{
+ size_t i, p;
+
+ sought_count = sn;
+ list_count = ln;
+
+ fill_random16(sought, sought_count, mask);
+ fill_random16(list, list_count, mask);
+ qsort_r(sought, sought_count, sizeof(*sought), cmp, NULL);
+ qsort_r(list, list_count, sizeof(*list), cmp, NULL);
+ sought_count = uniq(sought, sought_count);
+
+ for (i = 0; i < sought_count; i++)
+ result[i] = SIZE_MAX / 2;
+
+ binary_multisearch(sought, sought_count, sizeof(*sought), list, list_count,
+ sizeof(*list), cmp, NULL, binary_search, stack, result);
+
+ for (i = 0; i < sought_count; i++) {
+ if (list_count == 0) {
+ if (result[i] != -1)
+ exit(1);
+ continue;
+ }
+ if (result[i] >= (ssize_t)list_count) {
+ exit(2);
+ }
+ if (result[i] >= 0) {
+ if (list[result[i]] != sought[i])
+ exit(3);
+ continue;
+ }
+ p = (size_t)(-result[i] - 1);
+ if (p > list_count) {
+ exit(4);
+ }
+ if (p == list_count) {
+ if (list[p - 1] >= sought[i])
+ exit(5);
+ continue;
+ }
+ if (list[p] <= sought[i])
+ exit(6);
+ if (p && list[p - 1] >= sought[i])
+ exit(7);
+ }
+}
+
+int
+main(void)
+{
+ size_t i, j;
+ short int mask;
+
+ srand((unsigned)time(NULL));
+
+ for (i = 1; i <= 16; i++) {
+ mask = (short int)(((size_t)1 << i) - 1);
+ test(0, 0, mask);
+ test(0, 10, mask);
+ test(10, 0, mask);
+ for (j = 0; j < 100; j++) {
+ test((size_t)(unsigned short int)random16(mask) + 1,
+ (size_t)(unsigned short int)random16(mask) + 1, mask);
+ }
+ }
+
+ return 0;
+}