corned-beef/corned_beef.h

#include <fcntl.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <unistd.h>

/* We're going to have three kinds of pages in our hash table: the
 * first is the 'index', which we'll have exactly one of. It will
 * contain the roots to a bunch of linked lists, each one corresponding
 * to a hash bucket, and a field to keep track of where the next
 * free page is. I'm not including any operations to delete keys or
 * values, so that number will increase strictly. */
typedef struct {
	size_t list_head[0xff];
	size_t next_free_page;
} cb_index;

/* An intermediate node contains a key, a pointer to the next node in
 * the list, and a pointer to the corresponding value page. The 'next'
 * field will be zero to indicate that we're at the end of a list, and
 * otherwise it'll be an index into the on-disk file, pointing to a
 * particular page.
*/
typedef struct {
	size_t next;
	size_t val_page;
	char key[];
} cb_node;

/* The thirst kind of page is a 'value', which needs no pointers, and
 * will be entirely given to a single string. This is all ridiculously
 * inefficient: pages are quite large, and we're not doing anything to
 * pack pages. It's entirely possible we'll have a hash table like
 *   {'a': 'x', 'b': 'y'}
 * which would involve a total of five pages with mostly empty space.
 */

/* Our 'handle' just contains the file descriptor and the index page
 * that we've mapped from the underlying file. */
typedef struct {
	int file;
	cb_index* idx;
} cb_handle;

/* Our hash function is bad. No, really. */
unsigned char very_bad_hash(char* input);

/* Functions for opening/initializing a handle and closing one. */
cb_handle corned_beef_open(char* filename);
void corned_beef_close(cb_handle handle);

/* Functions for initializing a hash table, looking up a key, and
 * inserting a value with a key. */
int corned_beef_init(cb_handle handle);
int corned_beef_lookup(cb_handle handle, char* key);
int corned_beef_insert(cb_handle handle, char* key, char* val);