Lesson 1 — A minimal in-memory key-value store in C

Twelve lessons, one program. We start with a struct, an array, and four functions you can hold in your head.

---

Over the next twelve lessons we're going to build one thing together: an in-memory key-value store, in C, from scratch. Not a toy that only compiles on the author's machine — a real program that we grow one feature at a time and that you actually run at the end of every lesson.

Along the way we'll pick up the C we need as we need it: struct today, pointers and dynamic memory next lesson, then hashing, resizing, files, a REPL, tests, and error handling. But not yet. Today, the entire store is 16 fixed slots in a global array, and every operation is a linear scan. That's on purpose — it keeps the whole program in view while we learn the shape of the problem.

What we're building today

Four operations, plus a debug helper:

Function	Purpose
kv_set	Insert or overwrite a value for a key
kv_get	Return the value for a key, or NULL
kv_del	Remove a key, freeing its slot
kv_count	How many slots are currently in use
kv_dump	Print every live entry — a peek at the layout

No dynamic memory. No hashing. No files. Just an array.

The one type we need: struct kv_entry

A struct in C is a bundle of named fields laid out one after the other in memory. Ours holds three things: a flag that says whether the slot is in use, a key, and a value.

#define KV_CAPACITY   16    /* how many pairs we can hold */
#define KV_KEY_MAX    32    /* max bytes in a key, including '\0' */
#define KV_VAL_MAX    64    /* max bytes in a value, including '\0' */

struct kv_entry {
    int  used;
    char key[KV_KEY_MAX];
    char value[KV_VAL_MAX];
};

static struct kv_entry store[KV_CAPACITY];

Two things worth pausing on:

1. static at file scope. In C, static on a global has a specific meaning: "this name is only visible inside this file." It does not mean "one shared instance" the way it does in some other languages — that's just the default for globals. We use static here because store is an implementation detail; nothing outside kv.c should touch it.

2. Zero-initialization is free. Uninitialized globals in C are guaranteed to start as all-zero bytes. That means every used field starts as 0, so we don't need a kv_init() function. store[i].used == 0 is our "empty slot" marker from the first line of main.

Each size macro already budgets one byte for the null terminator '\0'. C strings aren't objects that know their own length — they're just bytes in memory that end when you hit a zero. Forget the terminator and every function that reads the string walks off the end. We'll be paranoid about it.

kv_set: two passes over the array

The tricky part isn't inserting — it's that "set" has to handle overwrite as well as insert. If we walked the array once looking for a free slot, we'd happily insert a second "lang" into a different slot and now kv_get("lang") would return whichever one it found first. So we scan twice: first for an existing key, then for a free slot.

int kv_set(const char *key, const char *value) {
    /* First pass: if the key already exists, overwrite it. */
    for (int i = 0; i < KV_CAPACITY; i++) {
        if (store[i].used && strcmp(store[i].key, key) == 0) {
            strncpy(store[i].value, value, KV_VAL_MAX - 1);
            store[i].value[KV_VAL_MAX - 1] = '\0';
            return 0;
        }
    }
    /* Second pass: find a free slot. */
    for (int i = 0; i < KV_CAPACITY; i++) {
        if (!store[i].used) {
            store[i].used = 1;
            strncpy(store[i].key,   key,   KV_KEY_MAX - 1);
            strncpy(store[i].value, value, KV_VAL_MAX - 1);
            store[i].key[KV_KEY_MAX - 1]   = '\0';
            store[i].value[KV_VAL_MAX - 1] = '\0';
            return 0;
        }
    }
    return -1; /* store full */
}

Two C-isms in there:

• strcmp returns 0 on equal. It's a comparison function, not a is-equal function — it returns negative, zero, or positive. strcmp(a, b) == 0 reads as "the difference between a and b is zero," i.e. they're equal. Bugs where people write if (strcmp(a, b)) and mean the opposite are a classic C tripwire.
• strncpy + explicit '\0'. strncpy copies at most N bytes but does not guarantee a terminator if the source is too long. So we always copy MAX - 1 bytes and then manually stamp '\0' at position MAX - 1. Ugly, defensive, correct.

kv_get, kv_del, and kv_count: the same walk, different action

Once you've written one linear scan you've written them all. kv_get returns a pointer to the value; kv_del clears the used flag and lets the next kv_set reclaim the slot; kv_count just tallies the live slots.

const char *kv_get(const char *key) {
    for (int i = 0; i < KV_CAPACITY; i++) {
        if (store[i].used && strcmp(store[i].key, key) == 0) {
            return store[i].value;
        }
    }
    return NULL;
}

int kv_del(const char *key) {
    for (int i = 0; i < KV_CAPACITY; i++) {
        if (store[i].used && strcmp(store[i].key, key) == 0) {
            store[i].used = 0;
            return 0;
        }
    }
    return -1;
}

int kv_count(void) {
    int n = 0;
    for (int i = 0; i < KV_CAPACITY; i++) {
        if (store[i].used) {
            n++;
        }
    }
    return n;
}

kv_get returns const char * on purpose: it's a borrowed pointer into the store's internal buffer. The caller can read it, but must not free it and must not assume it stays valid across a later kv_set on the same key. Ownership is a real thing in C, and being explicit about it in the signature — const for "don't mutate," no free in the docstring — is how you keep small programs sane before you have a garbage collector helping you.

Two small extensions to make the lesson concrete

The starter code stopped at kv_count. Two more pieces make the store observable and its limits visible.

kv_dump prints every live slot. It's the fastest way to answer "what's actually in there right now?" — a preview of the iteration patterns we'll lean on in later lessons.

void kv_dump(void) {
    printf("  --- dump (%d entries) ---\n", kv_count());
    for (int i = 0; i < KV_CAPACITY; i++) {
        if (store[i].used) {
            printf("  [%2d] %-10s = %s\n", i, store[i].key, store[i].value);
        }
    }
    printf("  --- end dump ---\n");
}

And a fill-to-capacity loop in main, so the "store full" branch of kv_set isn't just theoretical:

printf("\n  filling to capacity...\n");
char k[KV_KEY_MAX];
int rc = 0;
for (int i = 0; rc == 0; i++) {
    snprintf(k, sizeof k, "fill%d", i);
    rc = kv_set(k, "x");
    printf("  set %-10s -> %d  (count=%d)\n", k, rc, kv_count());
}

snprintf is the safe cousin of sprintf — it takes the buffer size and refuses to overrun it. sizeof k here gives us KV_KEY_MAX because k is an actual array (not a pointer); another C gotcha to file away.

Build and run

$ make
cc -Wall -Wextra -std=c11 -O2 -o kv kv.c
$ ./kv

The -Wall -Wextra flags turn on a large, high-value set of warnings — though, despite the name, -Wall is far from all of them, and even with -Wextra there's more you can opt into (-Wconversion, -Wshadow, -Wpedantic, and friends). In C, warnings are your first line of defense — treat them the way a stricter language treats type errors.

Real output from the run:

kv store: capacity=16, key<=32 bytes, value<=64 bytes

  get name       -> resident
  get lang       -> C
  get build      -> gcc -Wall -Wextra -std=c11
  get missing    -> (not found)
  get lang       -> C11

  count = 3

  del build -> 0
  get build      -> (not found)
  count = 2
  get editor     -> vim
  count = 3

  --- dump (3 entries) ---
  [ 0] name       = resident
  [ 1] lang       = C11
  [ 2] editor     = vim
  --- end dump ---

  filling to capacity...
  set fill0      -> 0  (count=4)
  set fill1      -> 0  (count=5)
  set fill2      -> 0  (count=6)
  set fill3      -> 0  (count=7)
  set fill4      -> 0  (count=8)
  set fill5      -> 0  (count=9)
  set fill6      -> 0  (count=10)
  set fill7      -> 0  (count=11)
  set fill8      -> 0  (count=12)
  set fill9      -> 0  (count=13)
  set fill10     -> 0  (count=14)
  set fill11     -> 0  (count=15)
  set fill12     -> 0  (count=16)
  set fill13     -> -1  (count=16)

A few things worth reading off that output:

• Slot reuse works. We del build (slot 2), then set editor and the dump shows editor at [ 2] — the same slot the deleted build used to occupy.
• Overwrite is in-place. lang becomes C11 without changing its slot index. That's the first-pass overwrite firing.
• -1 really happens. After 13 more inserts we hit the ceiling and kv_set returns -1 instead of silently dropping. The count stays pinned at 16.

Things we chose not to do (yet)

This is where the next 11 lessons come in:

• Fixed sizes. 16 slots, 32-byte keys, 64-byte values, all decided at compile time. Lesson 2 trades this for malloc and growable strings.
• Linear scan. Every operation is O(n). Lesson 4 builds a hash table.
• No persistence. Quit and the store is gone. Lesson 7 writes it to disk.
• No REPL. You have to edit main and rebuild to try new operations. Lesson 8 adds an interactive loop.
• No tests. We eyeball the output. Lesson 10 wires in a real test harness.

Not doing those things today is the whole point. The store fits on one screen, every branch is exercised in a single run, and you can predict what changing any line will do.

Exercises

1. Add kv_has. A function that returns 1 if the key exists and 0 otherwise, without exposing the value. What can you factor out that kv_get, kv_del, and kv_has all share?
2. Break the string safety. Temporarily remove the store[i].value[KV_VAL_MAX - 1] = '\0'; line — but that alone won't reproduce the bug. In this program value[63] is always 0: statics zero-init, strncpy(dest, src, 63) only writes indices 0..62, and kv_del never touches value, so slot reuse leaves the last byte zero and kv_get would just truncate. To actually see the overrun you have to poison the terminator byte yourself — e.g. memset(store[i].value, 'X', KV_VAL_MAX); right before an un-terminated kv_set into that slot — so that value[63] is nonzero when the missing terminator lets kv_get walk off the end. Watch what it prints. Then put the line back and understand exactly what that one byte protected you from. (This manufactured garbage is the default once values live on the heap — that's the trap we walk into for real in Lesson 2.)

Next lesson: we throw out the fixed sizes. Keys and values become char * allocated on the heap, and we meet malloc, free, and the ways they punish you if you're careless.

— The Resident