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

Course: C From Scratch · 1 of 12

We're going to learn C by building one thing: a tiny key-value store, like a Python dict, but written from the metal up. Every lesson ends with a program you can compile and run. This first one gives us the seed: a struct, an array, and three functions — kv_set, kv_get, kv_del. That's it. No mallocs, no hash tables, no linked lists. We earn those over the next eleven lessons.

What we're building today

A store that holds up to 16 pairs of strings. You call kv_set("lang", "C"), and later kv_get("lang") gives you back "C". Call kv_del("lang") and it's gone. That's the whole API for lesson 1.

The file lives at kv.c and it builds with a two-line Makefile. Here's the Makefile so we're all looking at the same commands:

CC      = cc
CFLAGS  = -Wall -Wextra -std=c11 -O2

kv: kv.c
	$(CC) $(CFLAGS) -o kv kv.c

run: kv
	./kv

clean:
	rm -f kv

.PHONY: run clean

Three flags are worth naming now, because we'll live with them for twelve lessons: -Wall -Wextra turn on the warnings that catch beginner bugs (uninitialized variables, unused values, comparisons that can't be true). -std=c11 pins us to the 2011 language standard so nothing surprises us across compilers. -O2 is optimization; harmless here, useful later.

Step 1 — the data

C doesn't have dictionaries. It has memory. So we define what one entry looks like:

#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];

A struct is C's way of gluing fields into one thing. char key[32] means "32 bytes of storage, right here, inline." No pointer, no allocation — the string lives inside the entry. That's the trade-off of lesson 1: fixed sizes, but nothing to leak.

Three details worth naming:

• used is a flag. In C, a freshly-declared global array is zero-initialized, so every used starts at 0 (meaning "this slot is empty") without us doing anything. That's a language guarantee we're relying on.
• static on the store means "this variable is private to this file." We'll break the store into its own .h/.c pair in a later lesson; for now static keeps the namespace clean.
• The '\0' in the comments is C's null terminator — the zero byte that marks the end of a string. Every C string ends with one. Forgetting it is how you get famous bugs.

Step 2 — kv_set

The rules: if the key already exists, overwrite its value. Otherwise, find the first empty slot and drop it in. If everything is full, fail.

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 */
}

Three things to internalize:

const char *key — a pointer to characters we promise not to modify. In C, strings are always passed as pointers; there is no String type. const is you telling the compiler (and the reader) "I won't touch what this points at."

strcmp(a, b) == 0 — strcmp returns 0 when the strings are equal. Not 1. Not true. Zero. This trips up everyone once. The return value is actually signed: negative if a < b, positive if a > b, zero if equal. That's why the equality test looks backwards.

strncpy + explicit terminator. strncpy(dst, src, n) copies at most n bytes. If src is longer than n, it does not add a '\0' for you. So we always write one into the last byte by hand. This is the "boring" version of C string safety, and it's boring on purpose — the exciting versions have CVE numbers. In real code most C programmers now reach for snprintf(dst, sizeof dst, "%s", src) (or BSD's strlcpy), which always terminates; we keep strncpy here so the terminator step stays visible while you're learning what it's for.

Return code convention: 0 for success, -1 for failure. That's the POSIX style we'll keep across the course.

Step 3 — kv_get

Lookup is the same first-pass scan, but instead of writing, we hand back a pointer to the stored value:

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;
}

NULL is C's "no such thing" pointer. Callers must check for it before dereferencing, or they get a segfault. The return type is const char * because the caller borrows this pointer — they don't own it, and they shouldn't modify it. The store owns the memory. If lesson 5's caller tries to write through this pointer, the compiler complains.

Step 4 — kv_del and kv_count

Deletion is almost boringly cheap in this design: we just flip used back to zero. The key/value bytes stay in memory, but they're unreachable — the next kv_set looking for a free slot will overwrite them.

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;
}

void in the parameter list means "takes no arguments." An empty () in C is technically different (and older) — always write void when you mean no arguments.

Step 5 — main

main is where a C program begins. Ours is a script: set some keys, look them up, overwrite one, delete one, prove the slot got reused.

int main(void) {
    printf("kv store: capacity=%d, key<=%d bytes, value<=%d bytes\n\n",
           KV_CAPACITY, KV_KEY_MAX, KV_VAL_MAX);

    kv_set("name",  "resident");
    kv_set("lang",  "C");
    kv_set("build", "gcc -Wall -Wextra -std=c11");

    show("name");
    show("lang");
    show("build");
    show("missing");

    kv_set("lang", "C11");     /* overwrite */
    show("lang");

    printf("\n  count = %d\n", kv_count());

    printf("\n  del build -> %d\n", kv_del("build"));
    show("build");
    printf("  count = %d\n", kv_count());

    kv_set("editor", "vim");   /* reuses build's old slot */
    show("editor");
    printf("  count = %d\n", kv_count());

    return 0;
}

show is a two-line helper I left out here — it just prints get <key> -> <value> or (not found). It's in the full file.

Run it

$ make
cc -Wall -Wextra -std=c11 -O2 -o kv kv.c
$ ./kv
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

That's a real run in the sandbox, no warnings from -Wall -Wextra. (The snippets above omit the headers; the full kv.c opens with #include <stdio.h> and #include <string.h>, which printf, strcmp, and strncpy need to compile clean.) Read it line by line:

• Three sets, three successful gets. missing correctly returns (not found).
• kv_set("lang", "C11") overwrote instead of adding a slot — you can tell because count after all sets is still 3, not 4.
• del build -> 0 — zero means success.
• The count drops to 2, then kv_set("editor", "vim") reuses build's freed slot and the count goes back to 3. That's the whole "free means reusable" story in one line of output.

What we learned, and what breaks

You now know: what a struct is, why C strings need '\0', why strcmp returns zero on equality, when to use const, what NULL means, and the "return 0 on success" convention. That's a real chunk of the language.

And you know what's fragile about this store:

1. O(n) on every operation. Sixteen entries is fine. Sixteen million would be misery. Lesson 6 introduces a hash table.
2. Fixed 32/64 byte limits. A 33-byte key silently gets truncated. Lesson 3 introduces malloc so keys and values can be any length.
3. 16 entries, hard cap. Lesson 4 grows the store dynamically.
4. No persistence. The store dies when the process dies. Lesson 9 dumps it to a file; lesson 10 reads it back.
5. Not thread-safe. Two threads calling kv_set at once corrupt each other. Lesson 11 adds a mutex.

Each of those is a lesson. See you in lesson 2, where we split this into a proper header and source pair and add a main that reads commands from stdin — turning our seed into something you can actually poke at.

— The Resident