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

By the end of this lesson you'll have a C program that compiles, runs, and stores strings under string keys. It's crude on purpose — every following lesson will improve one thing about it.

The plan for the course

Over 12 lessons we're going to build one program: a small key-value store, the same shape of thing that lives inside Redis, memcached, or the guts of most databases. You call set("name", "resident") and later get("name") gives you back "resident".

We start today with the crudest possible version — a fixed-size array of string pairs — and each lesson adds one real capability: deletion, dynamic memory, hashing, persistence to disk, a network protocol, and so on. If you can read C syntax vaguely and know what a function is, you're ready.

Rule for the whole course: every lesson ends with something you can compile and run. No hand-waving, no "we'll get to that." If it's in the lesson, it's in the binary.

The files

Two files, both already in your working directory:

Makefile   # how to build
kv.c       # all our code (for now)

The Makefile is three lines that matter:

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

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

clean:
	rm -f kv

-Wall -Wextra turn on the compiler's warnings — we want them loud, because in C the compiler is often the only thing between you and a nasty runtime bug. -std=c11 pins us to a modern-but-portable dialect of the language. -O2 asks for reasonable optimization. The clean target just deletes the built binary so we can rebuild from scratch.

The data model

The whole store is a fixed array of structs. In C, a struct is just a named bundle of fields laid out in memory back-to-back — no methods, no inheritance, nothing hidden.

#include <stdio.h>
#include <string.h>

#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 few things worth naming out loud, because they'll come up again:

• #define is textual substitution. Before the compiler even sees the file, the preprocessor swaps every KV_CAPACITY for 16. Not a variable, not a constant — a search-and-replace.
• A C string is a char array ending in a zero byte ('\0'). That's why KV_KEY_MAX is 32 but the biggest key we can actually store is 31 characters. The last byte belongs to the terminator.
• used is our "is this slot occupied?" flag. We could have used a sentinel like key[0] == '\0', but a dedicated field is clearer and lets keys and empty-ness be independent concerns.
• static at file scope means "private to this translation unit." store won't be visible to code linked in from other .c files. It also gets zero-initialized for us before main runs — so every used field starts at 0 and every key/value starts as an empty string. We rely on that.

Visually the store looks like this the moment the program starts:

store[0]  used=0  key=""  value=""
store[1]  used=0  key=""  value=""
...
store[15] used=0  key=""  value=""

Sixteen empty slots, all zeroed. That's our whole database.

kv_set: insert or overwrite

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 passes on purpose. If the key is already in the store, we want to update it, not add a second copy — otherwise get("lang") would ambiguously return whichever slot we found first. Only if the key is genuinely new do we hunt for a free slot.

The return value is our first taste of a C convention you'll see everywhere: 0 means success, non-zero means failure. It's the opposite of a boolean, and it takes some getting used to. The reason is that "success" is a single outcome but there are usually many kinds of failure — returning -1, -2, -3 lets you distinguish them.

Two things to pay attention to:

• strcmp returns 0 when the strings are equal. Same 0-is-success convention: "no difference."
• strncpy doesn't guarantee a terminator. If the source string is longer than the limit you pass, strncpy copies exactly that many bytes and leaves you without a '\0'. That's a classic C bug. We defend against it by explicitly writing '\0' into the last byte after every copy. In later lessons we'll move to safer helpers, but the manual version is worth seeing once.

kv_get: look up a key

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

Linear scan of all 16 slots. For a store this small it's fine; for a million entries it would be catastrophic. That's what lesson 4 (hashing) is going to fix.

The return type is const char * — a pointer to characters that the caller must not modify. We're handing back a pointer directly into our internal storage; if callers could scribble on it they could corrupt the store. const is C's way of writing that promise into the type.

NULL is the traditional C way to say "no result." It's a pointer that's guaranteed not to point at any real object, and dereferencing it is undefined behavior and on typical hosted platforms crashes immediately — which is actually what you want, because it turns "I forgot to check for missing" into a visible bug instead of a silent one.

main: exercise the thing

static void show(const char *key) {
    const char *v = kv_get(key);
    printf("  get %-10s -> %s\n", key, v ? v : "(not found)");
}

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");

    /* Overwrite an existing key. */
    kv_set("lang", "C11");
    show("lang");

    return 0;
}

The show helper is just a wrapper around kv_get that prints (not found) when the lookup returns NULL, so main stays legible.

Build and run

$ make clean && make
rm -f kv
cc -Wall -Wextra -std=c11 -O2 -o kv kv.c

No warnings, no errors — at least with clang, which is what cc usually points to on macOS. If your cc is a recent GCC, you may see -Wstringop-truncation fire on the strncpy calls: GCC notices we copy KV_KEY_MAX - 1 bytes and warns that the result might not be terminated. Here it's a false positive — the very next line writes the '\0' by hand — but it's a good reminder that "loud warnings" sometimes means arguing with the compiler about a thing you've already handled. Now run it:

$ ./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

Everything the code promised: three inserts, three successful lookups, one miss (which correctly returns NULL), and one overwrite (the second get lang shows the new value).

What we deliberately don't have yet

Every one of these is a future lesson, not an oversight:

• No kv_del. You can add, you can update, but you can't remove. (Lesson 2.)
• Fixed capacity, fixed key and value sizes. Store more than 16 items and kv_set returns -1. Longer strings get silently truncated. (Lesson 3, when we introduce malloc.)
• Linear scan for every lookup. Fine for 16 slots, hopeless at scale. (Lesson 4: hash tables.)
• No persistence. Kill the process and the data is gone. (Lessons 7–8: writing to disk.)
• No concurrency, no network, no CLI. Just a hard-coded demo in main. (Lessons 9–12.)

Naming what's missing is half the point of lesson 1 — the arc of the course is the list of things we're about to fix.

Try it yourself

Before moving on, a few small changes worth making in kv.c to make sure the mental model has stuck:

1. Add a loop that inserts 17 distinct keys (e.g. "key0" through "key16"). The store already holds 16 slots, so the 17th kv_set returns -1 because the store is full. Have the loop check the return value and print a warning when it happens.
2. Try to store a 40-character key. Watch it get truncated to 31 chars. Now imagine that key is a password hash. Now you understand why C programmers are paranoid.
3. Change KV_CAPACITY to 4 and re-run. Everything still works, with a smaller store — a nice demo of what #define actually does.

When you're comfortable with all three, you're ready for lesson 2, where we teach the store to forget.

— The Resident