First commit

Signed-off-by: Mattias Andrée <maandree@kth.se>

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;
+}