aboutsummaryrefslogtreecommitdiff
path: root/test
diff options
context:
space:
mode:
Diffstat (limited to 'test')
-rw-r--r--test/hashtable.c334
-rw-r--r--test/main.c7
-rw-r--r--test/test_framework.h4
3 files changed, 338 insertions, 7 deletions
diff --git a/test/hashtable.c b/test/hashtable.c
index cfb2d9d..ea6217c 100644
--- a/test/hashtable.c
+++ b/test/hashtable.c
@@ -1,8 +1,338 @@
+#include <stdio.h>
+#include <string.h>
+#include <assert.h>
#include "test_framework.h"
+#include "../global.h"
+#include "../hashtable.h"
+static const int NUM_RUNS = 1000;
+static const int NUM_OPERATIONS_PER_RUN = 100000;
+
+
+struct pair {
+ u64 key;
+ void *value;
+};
+
+struct mock {
+ struct pair *pairs;
+ size_t cap, len;
+};
+
+static struct mock* m_alloc(void) {
+ struct mock *ht = malloc(1, struct mock);
+ ht->cap = 16;
+ ht->len = 0;
+ ht->pairs = malloc(ht->cap, struct pair);
+ return ht;
+}
+
+static void m_free(struct mock *ht) {
+ free(ht->pairs);
+ free(ht);
+}
+
+// Returns NULL if key is not present in the table.
+static void* m_find(const struct mock *ht, u64 key) {
+ for (size_t i = 0; i < ht->len; i++) {
+ if (ht->pairs[i].key == key) return ht->pairs[i].value;
+ }
+ return NULL;
+}
+
+static void m_insert(struct mock *ht, u64 key, void *value) {
+ assert(value != NULL);
+ for (size_t i = 0; i < ht->len; i++) {
+ if (ht->pairs[i].key == key) {
+ ht->pairs[i].value = value;
+ return;
+ }
+ }
+
+ if (ht->len == ht->cap) {
+ ht->cap *= 2;
+ ht->pairs = realloc(ht->pairs, ht->cap, struct pair);
+ }
+ ht->pairs[ht->len++] = (struct pair){key, value};
+}
+
+// Does nothing if the key is not present in the table.
+static void m_delete(struct mock *ht, u64 key) {
+ for (size_t i = 0; i < ht->len; i++) {
+ if (ht->pairs[i].key == key) {
+ if (i < ht->len - 1) ht->pairs[i] = ht->pairs[ht->len - 1];
+ ht->len--;
+ break;
+ }
+ }
+}
+
+
+static u64 gen_key(void) {
+ return random();
+}
+
+static u64 gen_existing_key(const struct mock *m) {
+ const size_t index = random() % m->len;
+ return m->pairs[index].key;
+}
+
+static u64 gen_nonexistent_key(const struct mock *m) {
+ u64 key;
+ do key = gen_key(); while (m_find(m, key) != NULL);
+ return key;
+}
+
+static void* gen_value(void) {
+ // Ensure that the key is not NULL
+ return (void*)random() + 8;
+}
+
+struct operation {
+ int type;
+ u64 key;
+ void *value;
+};
+
+struct oplog {
+ struct operation *log;
+ size_t num;
+};
+
+
+static int perform_operation(
+ struct hashtable *ht, struct mock *m, const struct operation *oper) {
+
+ switch (oper->type) {
+ case 0: // insert key
+ ht_insert(ht, oper->key, oper->value);
+ m_insert(m, oper->key, oper->value);
+ break;
+
+ case 1: // find existing key
+ case 2: // find nonexistent key
+ if (ht_find(ht, oper->key) != m_find(m, oper->key)) return 1;
+ break;
+
+ case 3: // delete existing key
+ case 4: // delete nonexistent key
+ ht_delete(ht, oper->key);
+ m_delete(m, oper->key);
+ break;
+ }
+
+ return 0;
+}
+
+static int gen_perform_operations(
+ struct hashtable *ht, struct mock *m, struct oplog *oplog) {
+
+ for (size_t i = 0; i < NUM_OPERATIONS_PER_RUN; i++) {
+ const int op = (random() % 6) % 5; // not uniform but I don't care
+ oplog->num = i + 1;
+ oplog->log[i].type = op;
+
+ switch (op) {
+ case 0: { // insert key
+ const u64 key = oplog->log[i].key = gen_key();
+ void *const value = oplog->log[i].value = gen_value();
+ ht_insert(ht, key, value);
+ m_insert(m, key, value);
+ break;
+ }
+
+ case 1: { // find existing key
+ if (m->len == 0) { i--; continue; }
+ const u64 key = oplog->log[i].key = gen_existing_key(m);
+ EXPECTRET(1, ht_find(ht, key) == m_find(m, key));
+ break;
+ }
+
+ case 2: { // find nonexistent key
+ const u64 key = oplog->log[i].key = gen_nonexistent_key(m);
+ EXPECTRET(1, ht_find(ht, key) == NULL);
+ break;
+ }
+
+ case 3: { // delete existing key
+ if (m->len == 0) { i--; continue; }
+ const u64 key = oplog->log[i].key = gen_existing_key(m);
+ ht_delete(ht, key);
+ m_delete(m, key);
+ break;
+ }
+
+ case 4: { // delete nonexistent key
+ const u64 key = oplog->log[i].key = gen_nonexistent_key(m);
+ ht_delete(ht, key);
+ break;
+ }
+ }
+ }
+
+ return 0;
+}
+
+static void print_oplog(const struct oplog *oplog, bool verbose) {
+ printf("Note: hashtable oplog: ");
+ for (size_t i = 0; i < oplog->num; i++) {
+ putchar("IFfDd"[oplog->log[i].type]);
+ if (verbose) {
+ printf("(%" PRIi64 ")", oplog->log[i].key);
+ }
+ }
+ putchar('\n');
+}
+
+static int rerun_log(const struct oplog *oplog) {
+ struct hashtable *const ht = ht_alloc();
+ struct mock *const m = m_alloc();
+ int ret;
+ for (size_t i = 0; i < oplog->num; i++) {
+ ret = perform_operation(ht, m, &oplog->log[i]);
+ if (ret != 0) break;
+ }
+ ht_free(ht);
+ m_free(m);
+ return ret;
+}
+
+static void swap_oplog(struct oplog *oplog1, struct oplog *oplog2) {
+ const struct oplog tmp = *oplog1;
+ *oplog1 = *oplog2;
+ *oplog2 = tmp;
+}
+
+static void minimise_log(struct oplog *oplog) {
+ if (rerun_log(oplog) == 0) return;
+
+ printf("Note: minimising oplog, this may take a while\n");
+
+ struct oplog oplog2;
+ oplog2.num = oplog->num;
+ oplog2.log = malloc(NUM_OPERATIONS_PER_RUN, struct operation);
+ memcpy(oplog2.log, oplog->log, oplog->num * sizeof(struct operation));
+
+ // Replace delete_nonexistent with find_nonexistent
+ for (size_t i = 0; i < oplog2.num; i++) {
+ if (oplog2.log[i].type == 4) oplog2.log[i].type = 2;
+ }
+ if (rerun_log(&oplog2) == 0) { free(oplog2.log); return; }
+ swap_oplog(oplog, &oplog2);
+ oplog2.num = 0;
+
+ // Remove find_nonexistent
+ for (size_t i = 0; i < oplog->num; i++) {
+ if (oplog->log[i].type != 2) oplog2.log[oplog2.num++] = oplog->log[i];
+ }
+ if (rerun_log(&oplog2) == 0) { free(oplog2.log); return; }
+ swap_oplog(oplog, &oplog2);
+ oplog2.num = 0;
+
+ // Remove inconsequential insert/delete pairs
+ size_t *indexbuf = malloc(NUM_OPERATIONS_PER_RUN, size_t);
+ for (size_t inserti = 0; inserti < oplog->num; inserti++) {
+ if (oplog->log[inserti].type != 0) continue;
+ const u64 key = oplog->log[inserti].key;
+
+ indexbuf[0] = inserti;
+ size_t indexbuflen = 1;
+
+ size_t deletei;
+ for (deletei = inserti + 1; deletei < oplog->num; deletei++) {
+ if (oplog->log[deletei].type == 1 && oplog->log[deletei].key == key) {
+ indexbuf[indexbuflen++] = deletei;
+ }
+ if (oplog->log[deletei].type == 3 && oplog->log[deletei].key == key) {
+ break;
+ }
+ }
+ if (deletei < oplog->num) {
+ indexbuf[indexbuflen++] = deletei;
+ }
+
+ // Copy operations without those in indexbuf
+ for (size_t i = 0, ii = 0; i < oplog->num; i++) {
+ if (ii < indexbuflen && i == indexbuf[ii]) { ii++; continue; }
+ oplog2.log[oplog2.num++] = oplog->log[i];
+ }
+
+ // If we still error, commit removals
+ if (rerun_log(&oplog2) != 0) {
+ swap_oplog(oplog, &oplog2);
+ inserti--; // we removed the insert, so move one back
+ }
+
+ oplog2.num = 0;
+ }
+ free(indexbuf);
+
+ // Remove non-final finds
+ size_t final_find_idx = 0;
+ for (size_t i = oplog->num - 1; i > 0; i--) {
+ if (oplog->log[i].type == 1) {
+ final_find_idx = i;
+ break;
+ }
+ }
+ for (size_t i = 0; i < oplog->num; i++) {
+ if (oplog->log[i].type == 1 && i < final_find_idx) continue;
+ oplog2.log[oplog2.num++] = oplog->log[i];
+ }
+ if (rerun_log(&oplog2) == 0) { free(oplog2.log); return; }
+ swap_oplog(oplog, &oplog2);
+ oplog2.num = 0;
+
+ // Make keys smaller; note, afterwards "existing" is not true anymore for D's and F's
+ for (size_t modulus = 2; modulus <= 100; modulus++) {
+ oplog2.num = oplog->num;
+ memcpy(oplog2.log, oplog->log, oplog->num * sizeof(struct operation));
+ for (size_t i = 0; i < oplog2.num; i++) {
+ oplog2.log[i].key %= modulus;
+ }
+ if (rerun_log(&oplog2) != 0) {
+ swap_oplog(oplog, &oplog2);
+ break;
+ }
+ }
+
+ free(oplog2.log);
+ return;
+}
+
DEFINE_TEST(hashtable) {
- EXPECT(1);
- EXPECT(0);
+ int ret = 0;
+ struct oplog oplog;
+ oplog.log = malloc(NUM_OPERATIONS_PER_RUN, struct operation);
+ oplog.num = 0;
+
+ for (size_t i = 0; i < NUM_RUNS; i++) {
+ struct hashtable *const ht = ht_alloc();
+ struct mock *const m = m_alloc();
+
+ ret = gen_perform_operations(ht, m, &oplog);
+
+ ht_free(ht);
+ m_free(m);
+
+ if (ret != 0) {
+ print_oplog(&oplog, false);
+ minimise_log(&oplog);
+ print_oplog(&oplog, true);
+ break;
+ }
+ }
+
+ free(oplog.log);
+
+ return ret;
+}
+
+DEFINE_TEST(hashtable_unit1) {
+ struct hashtable *ht = ht_alloc();
+ ht_insert(ht, 0, (void*)123);
+ ht_insert(ht, 0, (void*)456);
+ EXPECT(ht_find(ht, 0) == (void*)456);
return 0;
}
diff --git a/test/main.c b/test/main.c
index ebfe3da..5c0656c 100644
--- a/test/main.c
+++ b/test/main.c
@@ -27,9 +27,9 @@ static void report_failure(const char *name, clock_t taken) {
#define RUN_TEST(name) do { \
atomic_flag_clear(&test_framework_assertion_failed); \
- clock_t start_ = clock(); \
- int ret_ = TEST(name)(); \
- clock_t diff_ = clock() - start_; \
+ const clock_t start_ = clock(); \
+ const int ret_ = TEST(name)(); \
+ const clock_t diff_ = clock() - start_; \
if (ret_ == 0 && !atomic_flag_test_and_set(&test_framework_assertion_failed)) { \
report_success(STR(name), diff_); \
} else { \
@@ -39,6 +39,7 @@ static void report_failure(const char *name, clock_t taken) {
} while (0)
static int run_tests(void) {
+ RUN_TEST(hashtable_unit1);
RUN_TEST(hashtable);
return 0;
}
diff --git a/test/test_framework.h b/test/test_framework.h
index 7ab4816..327de00 100644
--- a/test/test_framework.h
+++ b/test/test_framework.h
@@ -17,9 +17,9 @@ void test_report_error(
if (!(cond_)) test_report_error("EXPECT", #cond_, __FILE__, __LINE__); \
} while (0)
-#define EXPECTRET(cond_, ret_) do { \
+#define EXPECTRET(ret_, cond_) do { \
if (!(cond_)) { \
test_report_error("EXPECT", #cond_, __FILE__, __LINE__); \
return (ret_); \
} \
- }
+ } while (0)
generated by cgit v1.2.3-70-g09d2 (git 2.47.0) at 2024-11-22 03:08:22 +0100