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:
> SET name AliceOK> GET nameAlice> DEL nameOK> GET name(nil)> SAVESaved 0 entries to disk> QUITArchitecture
The system has three layers:
- Hash Table - the in-memory data structure for fast key-value lookups
- Persistence Layer - reads and writes the table to a file on disk
- 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:
#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.
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:
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()andht_destroy()free all owned memory
Pin those rules down now and you'll dodge the classic double-free and use-after-free traps later.