Skip to main content
Be Bitwise
CCapstone: Key-Value Store

Designing the KV Store

For this capstone, you're building a key-value store in C. String keys mapped to string values, with disk persistence and a CLI for poking at the running thing.

What We Are Building

The finished program will support these commands:

text
> SET name Alice
OK
> GET name
Alice
> DEL name
OK
> GET name
(nil)
> SAVE
Saved 0 entries to disk
> QUIT

Architecture

The system has three layers:

  1. Hash Table - the in-memory data structure for fast key-value lookups
  2. Persistence Layer - reads and writes the table to a file on disk
  3. Command Interface - parses user input and dispatches to the right operation

Here's how a line of input travels through them, and who owns each piece of memory along the way:

The parser can reuse its input buffer for the next line the moment ht_set returns, because the table has taken its own copies. That one rule is what the Memory Ownership section below pins down.

Data Structures

The core of the system is a hash table with separate chaining:

c
#define TABLE_SIZE 256
typedef struct Entry {
char *key;
char *value;
struct Entry *next; // for collision chaining
} Entry;
typedef struct {
Entry *buckets[TABLE_SIZE];
int count;
} HashTable;

Each bucket holds a linked list of entries. Two keys colliding into the same bucket? They get chained together.

Key Concept

This capstone combines almost everything from the C track: pointers for the linked list, malloc/free for dynamic allocation, structs for data organisation, file I/O for persistence, and string handling throughout. If any of these feel unfamiliar, revisit the earlier modules.

API Design

Before writing code, define the interface:

c
HashTable *ht_create(void);
void ht_destroy(HashTable *ht);
int ht_set(HashTable *ht, const char *key, const char *value);
char *ht_get(HashTable *ht, const char *key);
int ht_delete(HashTable *ht, const char *key);
int ht_save(HashTable *ht, const char *filename);
int ht_load(HashTable *ht, const char *filename);

Each function owns one job. ht_create allocates. ht_destroy frees the lot. Everything else operates on a live table. Think of it as a class with methods, only without the class.

Memory Ownership Rules

Decide up front who owns what:

  • The hash table owns all keys and values (it strdup()s them on SET)
  • ht_get() returns a pointer to the table's copy (caller must not free it)
  • ht_delete() and ht_destroy() free all owned memory

Pin those rules down now and you'll dodge the classic double-free and use-after-free traps later.