path: root/test/hashtable.c

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "test_framework.h"
#include "../hashtable.h"


static const int NUM_RUNS = 100;
static const int NUM_OPERATIONS_PER_RUN = 10000;


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) {
	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;
}