diff options
Diffstat (limited to 'test')
| -rw-r--r-- | test/hashtable.c | 334 | ||||
| -rw-r--r-- | test/main.c | 7 | ||||
| -rw-r--r-- | test/test_framework.h | 4 |
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) |