skiplist implementation in C

skiplist.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <assert.h>
#include <sys/time.h>

// storage format
// [off][size]

static const size_t DBF_HEADER_OFF = 0;
static const size_t DBF_FREE_OFF = 64;
static const size_t DBF_FREE_BLOCK_SIZE = 600;
static const size_t DBF_FREE_PTR_SIZE = 8;
static const size_t DBF_FREE_BLOCK_HEAD_SIZE = 16;
static const size_t DBF_STORE_BLOCK_HEAD_SIZE = 16;
static const size_t FREEBLOCK_SPACE = DBF_FREE_BLOCK_SIZE - DBF_FREE_BLOCK_HEAD_SIZE;
static const size_t FREEBLOCK_SLOTS = FREEBLOCK_SPACE / DBF_FREE_PTR_SIZE;
static const size_t DBF_LIST_OFF = DBF_FREE_OFF + DBF_FREE_BLOCK_SIZE;
static const char DB_INIT_WBLOCK[DBF_FREE_OFF] = {'\0'};

uint64_t _fp_alloc_at_end(FILE* fp, size_t size) {
	char* zero_buf = calloc(1, size);
	fseek(fp, 0, SEEK_END);
	uint64_t off = ftell(fp);
	fwrite(zero_buf, size, 1, fp);
	free(zero_buf);
	return off;
}

struct free_pg {
	uint64_t offset;
	uint64_t obj_size;
	char data[DBF_FREE_BLOCK_SIZE];
	struct free_pg* next;
};

uint64_t free_pg_alloc(struct free_pg* pg, FILE* fp, uint64_t size) {
	if (pg->obj_size < size) {
		return 0;
	}
	uint64_t* ptr = (uint64_t*)pg->data;
	size_t slot_start = 2;
	const size_t slots_end = FREEBLOCK_SLOTS + slot_start;
	for (; slot_start < slots_end; ++slot_start) {
		if (ptr[slot_start] != 0) {
			uint64_t slot_claim = 0;
			fseek(fp, pg->offset + (sizeof(uint64_t) * slot_start), SEEK_SET);
			fwrite(&slot_claim, sizeof(slot_claim), 1, fp);
			uint64_t my_slot = ptr[slot_start];
			ptr[slot_start] = 0;
			return my_slot;
		}
	}
	return 0;
}

void free_pg_write_next_offset(struct free_pg* pg, FILE* fp, uint64_t n_off) {
	uint64_t* writer = (uint64_t*)pg->data;
	writer[0] = n_off;
	fseek(fp, pg->offset, SEEK_SET);
	fwrite(&n_off, sizeof(n_off), 1, fp);
}

void free_pg_write_page(struct free_pg* pg, FILE* fp) {
	fseek(fp, pg->offset, SEEK_SET);
	fwrite(pg->data, DBF_FREE_BLOCK_SIZE, 1, fp);
}

struct free_mgr {
	struct free_pg* pages;
	struct free_pg* last_page;
};

void free_mgr_from_file(struct free_mgr* mgr, FILE* fp, uint64_t start_off) {
	struct free_pg* pglst = calloc(1, sizeof(struct free_pg));
	pglst->offset = start_off;
	struct free_pg* ptr = pglst;
	fseek(fp, start_off, SEEK_SET);
	fread(pglst->data, DBF_FREE_BLOCK_SIZE, 1, fp);
	uint64_t* reader = (uint64_t*)pglst->data;
	pglst->obj_size = reader[1];
	mgr->last_page = ptr;
	while (reader[0] != 0) {
		struct free_pg* pgnew = calloc(1, sizeof(struct free_pg));
		pgnew->offset = reader[0];
		fseek(fp, reader[0], SEEK_SET);
		fread(pgnew->data, DBF_FREE_BLOCK_SIZE, 1, fp);
		ptr->next = pgnew;
		ptr = ptr->next;
		reader = (uint64_t*)ptr->data;
		ptr->obj_size = reader[1];
		mgr->last_page = ptr;
	}
	mgr->pages = pglst;
}

void free_mgr_add_block(struct free_mgr* mgr, FILE* fp, size_t store_size) {
	size_t total_obj_space = store_size * FREEBLOCK_SLOTS;
	size_t total_alloc_space = total_obj_space + DBF_FREE_BLOCK_SIZE;
	uint64_t new_off = _fp_alloc_at_end(fp, total_alloc_space);
	uint64_t store_off = new_off + DBF_FREE_BLOCK_SIZE;
	uint64_t store_end = store_off + total_obj_space;
	struct free_pg* new_pg = calloc(1, sizeof(struct free_pg));
	uint64_t* writer = (uint64_t*)new_pg->data;
	// todo need to set up next ptrs of pages
	new_pg->offset = new_off;
	new_pg->obj_size = store_size;
	writer[0] = 0;
	writer[1] = new_pg->obj_size;
	free_pg_write_next_offset(mgr->last_page, fp, new_pg->offset);
	writer += 2;
	while (store_off != store_end) {
		//printf("off %llu , end %llu\n", store_off, store_end);
		*writer++ = store_off;
		store_off += store_size;
	}
	mgr->last_page->next = new_pg;
	mgr->last_page = new_pg;
	free_pg_write_page(new_pg, fp);
}

uint64_t free_mgr_alloc(struct free_mgr* mgr, FILE* fp, uint64_t size) {
	struct free_pg* pgptr = mgr->pages;
	while (pgptr != NULL) {
		uint64_t result = free_pg_alloc(pgptr, fp, size);
		if (result != 0) {
			return result;
		}
		pgptr = pgptr->next;
	}
	free_mgr_add_block(mgr, fp, size);
	return free_mgr_alloc(mgr, fp, size);
}

void free_mgr_del(struct free_mgr* mgr) {
	struct free_pg* ptr = mgr->pages;
	while (ptr != NULL) {
		struct free_pg* tmp = ptr->next;
		free(ptr);
		ptr = tmp;
	}
}

struct dbfile {
	FILE* fp;
	struct free_mgr fmgr;
};

int dbfile_create(struct dbfile* dbf, const char* fpath) {
	dbf->fp = fopen(fpath, "wb+");
	if (dbf->fp == NULL) {
		return 0;
	}
	fwrite(DB_INIT_WBLOCK, sizeof(DB_INIT_WBLOCK), 1, dbf->fp);
	char fbuf[DBF_FREE_BLOCK_SIZE] = {'\0'};
	uint64_t* writer = (uint64_t*)fbuf;
	writer[0] = 0; // one block for now.
	writer[1] = 0; // dummy block, todo fix
	fwrite(fbuf, sizeof(fbuf), 1, dbf->fp);
	char sbuf[DBF_STORE_BLOCK_HEAD_SIZE] = {'\0'};
	fwrite(sbuf, sizeof(sbuf), 1, dbf->fp);
	free_mgr_from_file(&(dbf->fmgr), dbf->fp, DBF_FREE_OFF);
	// some advisor scheme here, 
	free_mgr_add_block(&(dbf->fmgr), dbf->fp, 256);
	return 1;
}

// the root node of the skiplist is always the dummy start node in the file.

uint64_t dbfile_save_kvpair(struct dbfile* dbf, 
	                        const void* kdata, 
	                        size_t klen, 
	                        const void* vdata, 
	                        size_t vlen,
	                        uint64_t after_node) {
	size_t total_size = klen + vlen + DBF_STORE_BLOCK_HEAD_SIZE;
	uint64_t alloc_res = free_mgr_alloc(&(dbf->fmgr), dbf->fp, total_size);
	fseek(dbf->fp, after_node, SEEK_SET);
	fwrite(&alloc_res, sizeof(alloc_res), 1, dbf->fp);
	uint64_t head[2] = {0, total_size};
	fseek(dbf->fp, alloc_res, SEEK_SET);
	fwrite(head, sizeof(head), 1, dbf->fp);
	fwrite(kdata, klen, 1, dbf->fp);
	fwrite(vdata, vlen, 1, dbf->fp);
	return alloc_res;
}

void dbfile_close(struct dbfile* dbf) {
	free_mgr_del(&(dbf->fmgr));
	fclose(dbf->fp);
}

static uint64_t get_time_stamp() {
    struct timeval tv;
    gettimeofday(&tv,NULL);
    return tv.tv_sec*(uint64_t)1000000+tv.tv_usec;
}

static size_t random_levels() {
	size_t total = 1;
	while (rand() % 2) {
		++total;
	}
	return total;
}

struct object {
	void* data;
	size_t len;
	uint64_t file_off;
};

struct kvpair {
	struct object key;
	struct object value;
};

static struct kvpair ROOT_PAIR;

struct kvpair* kvpair_create(const void* keydata, size_t keylen, const void* valdata, size_t vallen) {
	struct kvpair* pair = calloc(1, sizeof(struct kvpair));
	pair->key.len = keylen;
	pair->value.len = vallen;
	pair->key.data = keydata == NULL ? NULL : malloc(keylen);
	pair->value.data = valdata == NULL ? NULL : malloc(vallen);
	if(keydata != NULL) memcpy(pair->key.data, keydata, keylen);
	if(valdata != NULL) memcpy(pair->value.data, valdata, vallen);
	return pair;
}

uint64_t kvpair_get_offset(const struct kvpair* pair) {
	if (pair == &ROOT_PAIR) {
		return 0;
	}
	return pair->key.file_off - DBF_STORE_BLOCK_HEAD_SIZE;
}

void kvpair_save_context(struct dbfile* dbf, struct kvpair* target, const struct kvpair* after) {
	uint64_t after_off = kvpair_get_offset(after);
	uint64_t save_result = dbfile_save_kvpair(dbf, target->key.data, target->key.len, target->value.data, target->value.len, after_off);
	uint64_t key_result = save_result + DBF_STORE_BLOCK_HEAD_SIZE;
	uint64_t val_result = key_result + target->key.len;
	target->key.file_off = key_result;
	target->value.file_off = val_result;
}

void kvpair_del(struct kvpair* pair) {
	if (pair == &ROOT_PAIR) {
		return;
	}
	if (pair->key.data != NULL)
		free(pair->key.data);
	if (pair->value.data != NULL)
		free(pair->value.data);
	free(pair);
}

enum kvpair_cmp {
	KVP_LT,
	KVP_EQ,
	KVP_GT
};

int kvpair_lt(const struct kvpair* lhs, const struct kvpair* rhs) {
	const struct kvpair* shorter = lhs->key.len < rhs->key.len ? lhs : rhs;
	int result = memcmp(lhs->key.data, rhs->key.data, shorter->key.len);
	return (result == 0 && shorter == lhs) || result < 0;
}

int kvpair_gt(const struct kvpair* lhs, const struct kvpair* rhs) {
	return kvpair_lt(rhs, lhs);
}

int kvpair_eq(const struct kvpair* lhs, const struct kvpair* rhs) {
	return lhs->key.len != rhs->key.len ? 0 : (memcmp(lhs->key.data, rhs->key.data, lhs->key.len) == 0);
}

enum kvpair_cmp kvpair_lt_eq_gt(const struct kvpair* lhs, const struct kvpair* rhs) {
	if (kvpair_eq(lhs, rhs)) {
		return KVP_EQ;
	} else if (kvpair_lt(lhs, rhs)) {
		return KVP_LT;
	} else {
		return KVP_GT;
	}
}


enum node_path {
	INIT_PATH = 0,
	MOVE_ACROSS,
	MOVE_BELOW,
	INSERT_AT,
	FIND_AT,
	REMOVE_AT,
	PATH_END
};

struct skipnode {
	struct kvpair* pair;
	struct skipnode* up;
	struct skipnode* across;
	struct skipnode* below;
};

struct skipnode* skipnode_new(void) {
	return calloc(1, sizeof(struct skipnode));
}

struct skipnode* skipnode_new_root(void) {
	struct skipnode* node = calloc(1, sizeof(struct skipnode));
	node->pair = &ROOT_PAIR;
	return node;
}

struct skipnode* skipnode_make_with_level(struct kvpair* pair, size_t levels) {
	struct skipnode* base = skipnode_new();
	base->pair = pair;
	struct skipnode* cur = base;
	while (--levels) {
		struct skipnode* newnode = skipnode_new();
		newnode->pair = pair;
		cur->below = newnode;
		newnode->up = cur;
		cur = newnode;
	}
	return cur;
}

void skipnode_print_addrs(const struct skipnode* node) {
	unsigned counter = 0;
	while (node != NULL) {
		printf("ADDR CHK: %d %p\n", counter++, node);
		node = node->up;
	}
	puts("---ADDR END-----");
}

enum node_path skipnode_check_insert(const struct skipnode* lhs, const struct skipnode* rhs, struct skipnode** next) {
	struct skipnode* below_ptr = lhs->below;
	struct skipnode* across_ptr = lhs->across;

	if (across_ptr) {
		if (kvpair_lt(across_ptr->pair, rhs->pair)) {
			*next = across_ptr;
			return MOVE_ACROSS;
		} else {
			if (below_ptr) {
				*next = below_ptr;
				return MOVE_BELOW;
			} else {
				*next = across_ptr; // This is just the observed value we should use
				return INSERT_AT;
			}
		}
	} else {
		if (below_ptr) {
			*next = below_ptr;
			return MOVE_BELOW;
		} else {
			*next = NULL;
			return INSERT_AT;
		}
	}
}

enum node_path skipnode_check_remove(const struct skipnode* lhs, const struct kvpair* pair, struct skipnode** next) {
	struct skipnode* below_ptr = lhs->below;
	struct skipnode* across_ptr = lhs->across;

	if (across_ptr) {
		if (kvpair_lt(across_ptr->pair, pair)) {
			*next = across_ptr;
			return MOVE_ACROSS;
		} else if (kvpair_eq(across_ptr->pair, pair)) {
			*next = below_ptr;
			return REMOVE_AT;
		} else {
			if (below_ptr) {
				*next = below_ptr;
				return MOVE_BELOW;
			} else {
				*next = NULL;
				return PATH_END; // same as not found for del or find
			}
		}
	} else {
		if (below_ptr) {
			*next = below_ptr;
			return MOVE_BELOW;
		} else {
			*next = NULL;
			return PATH_END;
		}
	}
}

enum node_path skipnode_check_find(const struct skipnode* lhs, const struct kvpair* pair, struct skipnode** next) {
	struct skipnode* below_ptr = lhs->below;
	struct skipnode* across_ptr = lhs->across;

	if (across_ptr) {
		if (kvpair_lt(across_ptr->pair, pair)) {
			*next = across_ptr;
			return MOVE_ACROSS;
		} else if (kvpair_eq(across_ptr->pair, pair)) {
			*next = across_ptr;
			return FIND_AT;
		} else {
			if (below_ptr) {
				*next = below_ptr;
				return MOVE_BELOW;
			} else {
				*next = NULL;
				return PATH_END; // same as not found for del or find
			}
		}
	} else {
		if (below_ptr) {
			*next = below_ptr;
			return MOVE_BELOW;
		} else {
			*next = NULL;
			return PATH_END;
		}
	}
}

void skipnode_del(struct skipnode* skip) {
	struct skipnode* upper = skip->up;
	struct skipnode* down = skip->below;
	free(skip);
	while (upper != NULL) {
		struct skipnode* tmp_up = upper;
		upper = upper->up;
		free(tmp_up);
	}
	while (down != NULL) {
		struct skipnode* tmp_down = down;
		down = down->below;
		free(tmp_down);
	}
}

struct skiplist {
	size_t list_height;
	struct skipnode* root;
	struct skipnode* root_bottom;
};

struct skiplist* skiplist_new(void) {
	struct skiplist* list = calloc(1, sizeof(struct skiplist));
	list->list_height = 1;
	list->root = skipnode_new_root();
	list->root_bottom = list->root;
	return list;
}

void skiplist_print_addr(const struct skiplist* list) {
	struct skipnode* cur = list->root_bottom;
	while (cur != NULL) {
		skipnode_print_addrs(cur);
		cur = cur->across;
	}
}

void skiplist_del(struct skiplist* list, int del_pairs) {
	struct skipnode* cur = list->root_bottom;
	while (cur != NULL) {
		if (cur->pair != &ROOT_PAIR && del_pairs) {
			kvpair_del(cur->pair);
		}
		struct skipnode* tmpn = cur->across;
		skipnode_del(cur);
		cur = tmpn;
	}
	free(list);
}

void skiplist_extend_root(struct skiplist* list, size_t n) {
	while (n--) {
		struct skipnode* node = skipnode_new_root();
		node->below = list->root;
		list->root->up = node;
		list->root = node;
		list->list_height += 1;
	}
}

void skiplist_insert_attach_right(struct skipnode* inserted) {
	struct skipnode* right = inserted->across;
	if (right == NULL)
		return;
	while (inserted != NULL && right != NULL) {
		if (right->up == NULL) {
			right = right->across;
			continue;
		} else {
			right = right->up;
		}
		inserted = inserted->up;
		if (inserted != NULL) {
			inserted->across = right;
		}
	}
}

void skiplist_insert_attach_left(struct skipnode* inserted, struct skipnode** edges, size_t edge_count) {
	struct skipnode* cur = inserted->up;
	// The edges here could be higher than the inserted node
	// we must not try to connect those, or we crash
	while (edge_count-- && cur != NULL) {
		edges[edge_count]->across = cur;
		cur = cur->up;
	}
}

size_t skiplist_insert(struct skiplist* list, struct kvpair* pair, struct dbfile* dbf) {
	size_t num_levels = random_levels();
	if (list->list_height < num_levels)
		skiplist_extend_root(list, num_levels - list->list_height);
	struct skipnode**  edges = calloc(list->list_height, sizeof(struct skipnode*));
	size_t edge_i = 0;
	struct skipnode* toinsert = skipnode_make_with_level(pair, num_levels);
	struct skipnode* next = NULL;
	struct skipnode* cur = list->root;
	while (cur != NULL) {
		enum node_path outcome = skipnode_check_insert(cur, toinsert, &next);
		switch (outcome) {
		case MOVE_ACROSS:
			cur = next;
			break;
		case MOVE_BELOW:
			// preserve edges
			edges[edge_i++] = cur;
			cur = next;
			break;
		case INSERT_AT:
			// core insert point
			toinsert->across = cur->across;
			cur->across = toinsert;
			if (dbf != NULL) {
				// disk point
				kvpair_save_context(dbf, toinsert->pair, cur->pair);
			}
			// todo attach levels
			skiplist_insert_attach_left(toinsert, edges, edge_i);
			skiplist_insert_attach_right(toinsert);
			free(edges);
			return num_levels;
		default:
			fprintf(stderr, "Unhandled case for insert %d\n", outcome);
			assert(0);
		}
	}
	free(edges);
	return 0;
}

struct skipnode* skiplist_find(struct skiplist* list, const struct kvpair* pair) {
	struct skipnode* next = NULL;
	struct skipnode* cur = list->root;
	enum node_path outcome = INIT_PATH;
	while (outcome != PATH_END) {
		outcome = skipnode_check_find(cur, pair, &next);
		switch (outcome) {
		case MOVE_ACROSS:
			cur = next;
			break;
		case MOVE_BELOW:
			cur = next;
			break;
		case FIND_AT:
			return next;
		case PATH_END:
			break;
		default:
			fprintf(stderr, "Unhandled case for find %d\n", outcome);
			assert(0);
		}
	}
	return NULL;
}

struct skipnode* skiplist_remove(struct skiplist* list, const struct kvpair* pair) {
	struct skipnode* next = NULL;
	struct skipnode* cur = list->root;
	struct skipnode* cached = NULL;
	enum node_path outcome = INIT_PATH;
	while (cur != NULL && outcome != PATH_END) {
		outcome = skipnode_check_remove(cur, pair, &next);
		switch (outcome) {
		case MOVE_ACROSS:
			cur = next;
			break;
		case MOVE_BELOW:
			cur = next;
			break;
		case REMOVE_AT:
			cached = cur->across;
			cur->across = cur->across->across;
			cur = next;
			break;
		case PATH_END:
			break;
		default:
			fprintf(stderr, "Unhandled case for remove %d\n", outcome);
			assert(0);
		}
	}
	return cached;
}

// Tests start here -------- //

static void checkCondition(int cond, const char* express, unsigned lineno) {
	if (!cond) {
		fprintf(stderr, "FAIL %s line %u\n", express, lineno);
	}
}

#define CHECKIT(cond) checkCondition(cond, #cond, __LINE__)

static void test_pair_lt(void) {
	static const char* key1 = "foo";
	static const char* key2 = "food";
	static const char* key3 = "dood";
	static const char* val = "bar";

	struct kvpair* pair1 = kvpair_create(key1, strlen(key1), val, strlen(val));
	struct kvpair* pair1_dup = kvpair_create(key1, strlen(key1), val, strlen(val));
	struct kvpair* pair2 = kvpair_create(key2, strlen(key2), val, strlen(val));
	struct kvpair* pair3 = kvpair_create(key3, strlen(key3), val, strlen(val));

	CHECKIT(!kvpair_lt(pair1, pair1_dup));
	CHECKIT(kvpair_lt(pair1, pair2));
	CHECKIT(kvpair_lt(pair3, pair2));
	CHECKIT(kvpair_lt(pair3, pair1));

	kvpair_del(pair1);
	kvpair_del(pair1_dup);
	kvpair_del(pair2);
	kvpair_del(pair3);
}

static void test_pair_gt(void) {
	static const char* key1 = "foo";
	static const char* key2 = "food";
	static const char* key3 = "dood";
	static const char* val = "bar";

	struct kvpair* pair1 = kvpair_create(key1, strlen(key1), val, strlen(val));
	struct kvpair* pair1_dup = kvpair_create(key1, strlen(key1), val, strlen(val));
	struct kvpair* pair2 = kvpair_create(key2, strlen(key2), val, strlen(val));
	struct kvpair* pair3 = kvpair_create(key3, strlen(key3), val, strlen(val));

	CHECKIT(!kvpair_gt(pair1, pair1_dup));
	CHECKIT(kvpair_gt(pair2, pair1));
	CHECKIT(kvpair_gt(pair2, pair3));
	CHECKIT(kvpair_gt(pair1, pair3));

	kvpair_del(pair1);
	kvpair_del(pair1_dup);
	kvpair_del(pair2);
	kvpair_del(pair3);
}

static void test_skipnode_make_levels(void) {
	static const char* key1 = "foo";
	static const char* val = "bar";
	struct kvpair* pair1 = kvpair_create(key1, strlen(key1), val, strlen(val));
	struct skipnode* skip1 = skipnode_make_with_level(pair1, 4);

	CHECKIT(skip1->up != NULL);
	CHECKIT(skip1->up->below == skip1);
	CHECKIT(skip1->pair == skip1->up->pair);

	skipnode_del(skip1);
	kvpair_del(pair1);
}

static void test_skiplist_insert_attach_right(void) {
	static const char* key1 = "foo";
	static const char* val = "bar";
	struct kvpair* pair1 = kvpair_create(key1, strlen(key1), val, strlen(val));
	struct skipnode* skip1 = skipnode_make_with_level(pair1, 4);
	struct skipnode* skip2 = skipnode_make_with_level(pair1, 2);
	struct skipnode* skip3 = skipnode_make_with_level(pair1, 3);

	skiplist_insert_attach_right(skip1); // test for unattached
	CHECKIT(skip1->across == NULL);

	skip1->across = skip2;
	skip2->across = skip3;
	skip2->up->across = skip3->up;

	skiplist_insert_attach_right(skip1);

	CHECKIT(skip1->up->across == skip2->up);
	CHECKIT(skip1->up->up->across != NULL);
	CHECKIT(skip1->up->up->across == skip3->up->up);
	CHECKIT(skip1->up->up->up->across == NULL);

	skipnode_del(skip1);
	skipnode_del(skip2);
	skipnode_del(skip3);
	kvpair_del(pair1);
}

static void test_skiplist_insert_attach_left(void) {
	static const char* key1 = "foo";
	static const char* val = "bar";
	struct kvpair* pair1 = kvpair_create(key1, strlen(key1), val, strlen(val));
	struct skipnode* skip1 = skipnode_make_with_level(pair1, 3);
	struct skipnode* skip2 = skipnode_make_with_level(pair1, 1);
	struct skipnode* skip3 = skipnode_make_with_level(pair1, 1);
	struct skipnode* skip4 = skipnode_make_with_level(pair1, 1);
	struct skipnode* skip5 = skipnode_make_with_level(pair1, 1);
	// extra to check for short case
	struct skipnode* edges[4] = {skip4, skip5, skip2, skip3};

	skiplist_insert_attach_left(skip1, edges, 4);
	CHECKIT(skip3->across != NULL);
	CHECKIT(skip3->across == skip1->up);
	CHECKIT(skip2->across != NULL);
	CHECKIT(skip2->across == skip1->up->up);
	CHECKIT(skip5->across == NULL);
	CHECKIT(skip4->across == NULL);

	skipnode_del(skip1);
	skipnode_del(skip2);
	skipnode_del(skip3);
	skipnode_del(skip4);
	skipnode_del(skip5);
	kvpair_del(pair1);
}

static void test_skiplist_insert_base(void) {
	static const char* key1 = "foo";
	static const char* key2 = "doo";
	static const char* val = "bar";
	struct kvpair* pair1 = kvpair_create(key1, strlen(key1), val, strlen(val));
	struct kvpair* pair2 = kvpair_create(key2, strlen(key2), val, strlen(val));
	struct skiplist* list = skiplist_new();
	size_t levels1 = skiplist_insert(list, pair1, NULL);
	CHECKIT(levels1 > 0);
	CHECKIT(list->list_height >= levels1);
	CHECKIT(list->root_bottom->across != NULL);
	CHECKIT(list->root_bottom->across->pair == pair1);

	size_t levels2 = skiplist_insert(list, pair2, NULL);
	CHECKIT(levels2 > 0);
	CHECKIT(list->list_height >= levels2);
	CHECKIT(list->root_bottom->across->pair == pair2);
	CHECKIT(list->root_bottom->across->across->pair == pair1);
	CHECKIT(list->root_bottom->across->across->across == NULL);

	//kvpair_del(pair1);
	//kvpair_del(pair2);
	skiplist_del(list, 1);
}

static void test_skiplist_find_base(void) {
	static const char* key1 = "foo";
	static const char* key2 = "doo";
	static const char* key3 = "boston";
	static const char* val = "bar";
	struct kvpair* pair1 = kvpair_create(key1, strlen(key1), val, strlen(val));
	struct kvpair* pair2 = kvpair_create(key2, strlen(key2), val, strlen(val));
	struct kvpair* pair1_finder = kvpair_create(key1, strlen(key1), NULL, 0);
	struct kvpair* pair2_finder = kvpair_create(key2, strlen(key2), NULL, 0);
	struct kvpair* pair3_finder = kvpair_create(key3, strlen(key3), NULL, 0);
	struct skiplist* list = skiplist_new();
	size_t levels1 = skiplist_insert(list, pair1, NULL);
	size_t levels2 = skiplist_insert(list, pair2, NULL);
	//skiplist_print_addr(list);
	struct skipnode* found1 = skiplist_find(list, pair1_finder);
	CHECKIT(found1 != NULL);
	CHECKIT(kvpair_eq(found1->pair, pair1_finder));

	struct skipnode* found2 = skiplist_find(list, pair2_finder);
	CHECKIT(found2 != NULL);
	CHECKIT(kvpair_eq(found2->pair, pair2_finder));

	struct skipnode* found3 = skiplist_find(list, pair3_finder);
	CHECKIT(found3 == NULL);

	kvpair_del(pair1_finder);
	kvpair_del(pair2_finder);
	kvpair_del(pair3_finder);
	skiplist_del(list, 1);
}

static void test_skiplist_remove_base(void) {
	static const char* key1 = "foo";
	static const char* key2 = "doo";
	static const char* key3 = "boston";
	static const char* val = "bar";
	struct kvpair* pair1 = kvpair_create(key1, strlen(key1), val, strlen(val));
	struct kvpair* pair2 = kvpair_create(key2, strlen(key2), val, strlen(val));
	struct kvpair* pair1_finder = kvpair_create(key1, strlen(key1), NULL, 0);
	struct kvpair* pair2_finder = kvpair_create(key2, strlen(key2), NULL, 0);
	struct kvpair* pair3_finder = kvpair_create(key3, strlen(key3), NULL, 0);
	struct skiplist* list = skiplist_new();
	size_t levels1 = skiplist_insert(list, pair1, NULL);
	size_t levels2 = skiplist_insert(list, pair2, NULL);

	struct skipnode* removed2 = skiplist_remove(list, pair2_finder);
	CHECKIT(list->root_bottom->across != NULL);
	CHECKIT(kvpair_eq(list->root_bottom->across->pair, pair1_finder));
	CHECKIT(kvpair_eq(removed2->pair, pair2_finder));

	struct skipnode* removed3 = skiplist_remove(list, pair3_finder);
	CHECKIT(removed3 == NULL);
	CHECKIT(kvpair_eq(list->root_bottom->across->pair, pair1_finder));

	struct skipnode* removed1 = skiplist_remove(list, pair1_finder);
	CHECKIT(kvpair_eq(removed1->pair, pair1_finder));
	CHECKIT(list->root_bottom->across == NULL);

	kvpair_del(pair1_finder);
	kvpair_del(pair2_finder);
	kvpair_del(pair3_finder);
	kvpair_del(pair1);
	kvpair_del(pair2);
	skipnode_del(removed1);
	skipnode_del(removed2);
	skiplist_del(list, 1);
}

static void test_freemgr_from_file(void) {
	FILE* tfp = tmpfile();
	char buf[DBF_FREE_BLOCK_SIZE] = {'\0'};
	uint64_t* writer = (uint64_t*)buf;
	writer[0] = DBF_FREE_BLOCK_SIZE;
	fwrite(buf, sizeof(buf), 1, tfp);
	writer[0] = 0; // end
	fwrite(buf, sizeof(buf), 1, tfp);
	rewind(tfp);
	struct free_mgr mgr;
	mgr.pages = NULL;
	free_mgr_from_file(&mgr, tfp, 0);
	CHECKIT(mgr.pages != NULL);
	CHECKIT(mgr.pages->next != NULL);
	CHECKIT(mgr.pages->offset == 0);
	CHECKIT(mgr.pages->next->next == NULL);
	CHECKIT(mgr.pages->next->offset == DBF_FREE_BLOCK_SIZE);
	free_mgr_del(&mgr);
	fclose(tfp);
}

static void test_freemgr_add_block(void) {
	FILE* tfp = tmpfile();
	char buf[DBF_FREE_BLOCK_SIZE] = {'\0'};
	uint64_t* writer = (uint64_t*)buf;
	writer[0] = DBF_FREE_BLOCK_SIZE;
	fwrite(buf, sizeof(buf), 1, tfp);
	writer[0] = 0; // end
	fwrite(buf, sizeof(buf), 1, tfp);
	rewind(tfp);
	struct free_mgr mgr;
	free_mgr_from_file(&mgr, tfp, 0);
	struct free_pg* cur = mgr.pages;
	struct free_pg* last = mgr.last_page;
	free_mgr_add_block(&mgr, tfp, 96);
	uint64_t last_page_off = mgr.last_page->offset;
	uint64_t last_page_size = mgr.last_page->obj_size;
	CHECKIT(mgr.pages == cur);
	CHECKIT(mgr.last_page != last);
	CHECKIT(mgr.last_page->offset > last->offset);
	uint64_t* reader = (uint64_t*)mgr.last_page->data;
	CHECKIT(reader[0] == 0);
	CHECKIT(reader[1] == 96);
	free_mgr_del(&mgr);

	rewind(tfp);
	struct free_mgr mgr2;
	free_mgr_from_file(&mgr2, tfp, 0);
	CHECKIT(mgr2.pages != mgr2.last_page);
	CHECKIT(mgr2.last_page->offset == last_page_off);
	CHECKIT(mgr2.last_page->obj_size == last_page_size);
	free_mgr_del(&mgr2);
	fclose(tfp);
}

static void test_freepg_alloc(void) {
	FILE* tfp = tmpfile();
	char buf[DBF_FREE_BLOCK_SIZE] = {'\0'};
	uint64_t* writer = (uint64_t*)buf;
	writer[0] = 0; // end
	writer[1] = 64; // size
	writer[2] = 7583;
	writer[3] = 4533;
	fwrite(buf, sizeof(buf), 1, tfp);
	rewind(tfp);
	// load
	struct free_mgr mgr;
	free_mgr_from_file(&mgr, tfp, 0);
	uint64_t result = free_pg_alloc(mgr.pages, tfp, 63);
	CHECKIT(result == 7583);
	CHECKIT(free_pg_alloc(mgr.pages, tfp, 500) == 0);
	CHECKIT(free_pg_alloc(mgr.pages, tfp, 63) == 4533);
	CHECKIT(free_pg_alloc(mgr.pages, tfp, 63) == 0); // no more slots
	free_mgr_del(&mgr);
	fclose(tfp);
}

static void test_freemgr_alloc(void) {
	FILE* tfp = tmpfile();
	char buf[DBF_FREE_BLOCK_SIZE] = {'\0'};
	uint64_t* writer = (uint64_t*)buf;
	writer[0] = DBF_FREE_BLOCK_SIZE; // has next
	writer[1] = 64; // size
	writer[2] = 7583;
	writer[3] = 4533;
	fwrite(buf, sizeof(buf), 1, tfp);
	memset(buf, 0, sizeof(buf));

	writer[0] = 0; // end
	writer[1] = 256;
	writer[2] = 67583;
	fwrite(buf, sizeof(buf), 1, tfp);
	rewind(tfp);

	// load
	struct free_mgr mgr;
	free_mgr_from_file(&mgr, tfp, 0);
	uint64_t result = free_mgr_alloc(&mgr, tfp, 63);
	CHECKIT(result == 7583);
	CHECKIT(free_mgr_alloc(&mgr, tfp, 200) == 67583);
	CHECKIT(free_mgr_alloc(&mgr, tfp, 1024) != 0);
	CHECKIT(mgr.last_page->obj_size == 1024);
	free_mgr_del(&mgr);
	fclose(tfp);
}

static void perftest_insert_find(void) {
	static const size_t test_max = 100000;
	static const char* fname = "foobar666.db";
	struct dbfile dbf;
	dbfile_create(&dbf, fname);
	puts("Created db file!");
	size_t data_point = 278;
	size_t value = 1300;
	struct skiplist* list = skiplist_new();
	uint64_t one = get_time_stamp();
	while (data_point < test_max) {
		struct kvpair* to_insert = kvpair_create(&data_point, sizeof(data_point), &value, sizeof(value));
		skiplist_insert(list, to_insert, &dbf);
		++data_point;
	}
	uint64_t two = get_time_stamp();
	printf("insert test took %llu us\n", two - one);
	size_t adder = 0;
	data_point = 278;
	struct kvpair* to_lookup = kvpair_create(&data_point, sizeof(data_point), NULL, 0);
	uint64_t three = get_time_stamp();
	while (data_point < test_max) {
		adder += (size_t)skiplist_find(list, to_lookup);
		++data_point;
		*((size_t*)to_lookup->key.data) = data_point;
	}
	uint64_t four = get_time_stamp();
	printf("find test took %llu us, adder %zu\n", four - three, adder);
	kvpair_del(to_lookup);
	skiplist_del(list, 1);
	dbfile_close(&dbf);
	remove(fname);
}

int main(int argc, char const *argv[])
{
	srand(time(NULL));
	test_pair_lt();
	test_pair_gt();
	test_skipnode_make_levels();
	test_skiplist_insert_attach_right();
	test_skiplist_insert_attach_left();
	test_skiplist_insert_base();
	test_skiplist_find_base();
	test_skiplist_remove_base();
	test_freemgr_from_file();
	test_freemgr_add_block();
	test_freepg_alloc();
	test_freemgr_alloc();

	// perf tests
	if (argc == 2 && strcmp(argv[1], "perf") == 0) {
		perftest_insert_find();
	}
	return 0;
}