What CS50 finally taught me about C

CS50's speller problem set is where pointers actually became real for me, not the lecture that introduces them. It's also the pset that kept me up two nights past when I meant to be done with it, so this one's got some history.

I'd used Python for years by that point (a Django CRM, a bunch of scrapers, bookbot from boot.dev) without ever needing to think about memory as a thing I managed myself. Python just doesn't ask you to. C asks you immediately, and speller is the assignment that makes you actually answer.

the pset, roughly

Load a dictionary of about 143 thousand words into a hash table, using linked lists for collisions, then spell-check a text file against it fast enough that check50 doesn't time out. The starter code gives you the header file with the function signatures: load, check, hash, size, unload. Everything else, you build.

typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

A linked list of these, one per hash bucket. The first time I actually needed to understand that next isn't a copy of the next node, it's the address of it, was the moment the lecture's whiteboard diagrams turned into something I could reason about instead of just nod along to.

my first hash function, which was bad on purpose without meaning to be

CS50 tells you upfront that the hash function is where speed lives or dies, and I did not take that seriously the first time through.

unsigned int hash(const char *word)
{
    return tolower(word[0]) % N;
}

First letter of the word, modulo the table size. It compiled. It even ran correctly, in the sense that check still returned the right answer for every word. It just took about forty seconds to load and check a real dictionary, which check50 does not consider a passing time.

what that actually meant

Twenty-six letters spread across however many buckets I'd set N to meant every bucket held thousands of words in one long linked list, and looking up a word meant walking that whole list, one node at a time, comparing strings. A hash table is only fast if the hashing actually spreads words out. Mine was functionally just one giant linked list per starting letter, which is a worse version of the thing linked lists are supposed to help with.

the fix, and where the actual bug still was

I switched to a real string hash, the kind that mixes every character in instead of just the first one.

unsigned int hash(const char *word)
{
    unsigned int h = 0;
    for (int i = 0; word[i] != '\0'; i++)
    {
        h = (h * 31) + tolower(word[i]);
    }
    return h % N;
}

Load time dropped from forty seconds to under two. That part felt great. What didn't feel great was the segfault this introduced in load(), which I hadn't touched, on the exact same dictionary that had worked fine an hour earlier.

where it actually broke

node *n = malloc(sizeof(node));
strcpy(n->word, word);
n->next = table[index];
table[index] = n;

Looked fine. Ran fine on the small dictionary. valgrind (which CS50 makes you actually use, not just mention in a lecture) told me exactly what was wrong once I ran it against the big one.

==12345== Invalid write of size 1
==12345==    at 0x1091A2: load (dictionary.c:47)
==12345==  Address 0x0 is not stack'd, malloc'd or (recently) free'd

I wasn't checking malloc's return value, and on the big dictionary, deep enough into a run, one allocation actually failed. With the bad hash function this had never surfaced, because everything was so slow that memory pressure never built up the same way before the test harness gave up waiting. The faster hash function meant more allocations happened in less time, which meant I actually hit the failure case my old, slower, worse code had been accidentally hiding from me the whole time.

One if (n == NULL) return false; fixed it. The bug wasn't really about pointers at all. It was about assuming a function that can fail will always succeed, because it did the first fifty times I ran it, and making the rest of the program faster is exactly the kind of change that can expose a bug that was always there.

the second bug, in a completely different function

unload() is supposed to walk every bucket and free every node. Mine looked, to me, completely correct:

bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        node *cursor = table[i];
        while (cursor != NULL)
        {
            free(cursor);
            cursor = cursor->next;
        }
    }
    return true;
}

valgrind again, patient as ever:

==12345== Invalid read of size 8
==12345==    at 0x109310: unload (dictionary.c:63)
==12345==  Address 0x51fc0a0 is 0 bytes inside a block of size 24 free'd

Read-after-free. I was freeing cursor, then immediately reading cursor->next from memory I'd just told the allocator it could reuse. On this specific run it happened to still hold the right value, right up until it occasionally didn't, which is exactly the kind of bug that passes locally and fails somewhere else for no reason you can see. The fix was saving the next pointer before freeing the current node, not after.

node *cursor = table[i];
while (cursor != NULL)
{
    node *next = cursor->next;
    free(cursor);
    cursor = next;
}

Two bugs, same pset, same root cause underneath both: I kept using a pointer's value after the moment it stopped being safe to trust, once because a function I called could fail silently, once because I'd already told the system that memory was free to reuse. C doesn't stop you from doing either. It just eventually shows you, at a time and place of its choosing, usually not the line where the actual mistake was made.

a smaller aside, since staying up on this pset deserves one honest tangent

Somewhere around 1am on the second night I got convinced the dictionary file itself was corrupted, because a specific run kept behaving differently from an identical-looking previous run. It wasn't the file. It was that malloc failure being probabilistic under memory pressure, not deterministic, so the exact same input didn't always trigger it depending on what else the machine happened to be doing. I spent a genuinely embarrassing amount of time diffing a dictionary file against itself before I accepted the bug was in my code, not the data.

what actually stuck

Not the syntax. The rule: every pointer is either pointing somewhere real, or it's NULL, or it's garbage, and C will never tell you which one, so you have to. Python quietly protects you from ever having to think about that. C hands you the whole responsibility and mostly gets out of the way, including the responsibility of not reading memory the instant after you've freed it.

what I'd do differently on the next pset

Run valgrind from the very first working version, not just once something breaks. Both bugs here were sitting in code that looked fine and passed casual testing for a while before actually surfacing. Waiting for a crash to go looking for the tool that would have caught it earlier is a habit I'd like to unlearn before it costs me more than one late night.

I still don't fully trust my own pointer arithmetic on arrays. That's a problem for a later pset.