typestar

hash_index.c in C

A word index built on a chained hash table, with counts and a clean teardown.

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

#define BUCKETS 32

typedef struct Entry {
    char *word;
    int count;
    struct Entry *next;
} Entry;

typedef struct {
    Entry *buckets[BUCKETS];
    size_t unique;
} Index;

static size_t hash(const char *key) {
    size_t h = 5381;
    for (const char *p = key; *p != '\0'; p++) {
        h = h * 33u + (unsigned char) *p;
    }
    return h % BUCKETS;
}

static int index_add(Index *ix, const char *word) {
    size_t slot = hash(word);
    for (Entry *e = ix->buckets[slot]; e != NULL; e = e->next) {
        if (strcmp(e->word, word) == 0) {
            e->count++;
            return 1;
        }
    }

    Entry *entry = malloc(sizeof *entry);
    if (entry == NULL) {
        return 0;
    }
    size_t n = strlen(word) + 1;
    entry->word = malloc(n);
    if (entry->word == NULL) {
        free(entry);
        return 0;
    }
    memcpy(entry->word, word, n);
    entry->count = 1;
    entry->next = ix->buckets[slot];
    ix->buckets[slot] = entry;
    ix->unique++;
    return 1;
}

static void index_free(Index *ix) {
    for (size_t i = 0; i < BUCKETS; i++) {
        Entry *e = ix->buckets[i];
        while (e != NULL) {
            Entry *next = e->next;
            free(e->word);
            free(e);
            e = next;
        }
        ix->buckets[i] = NULL;
    }
    ix->unique = 0;
}

int main(void) {
    Index ix;
    memset(&ix, 0, sizeof ix);

    char text[] = "the quick brown fox the lazy dog the end";
    for (char *word = strtok(text, " "); word; word = strtok(NULL, " ")) {
        if (!index_add(&ix, word)) {
            fprintf(stderr, "out of memory\n");
            index_free(&ix);
            return 1;
        }
    }

    printf("%zu unique words\n", ix.unique);
    for (size_t i = 0; i < BUCKETS; i++) {
        for (Entry *e = ix.buckets[i]; e != NULL; e = e->next) {
            if (e->count > 1) {
                printf("%-8s %d\n", e->word, e->count);
            }
        }
    }

    index_free(&ix);
    return 0;
}

How it works

  1. The table owns its keys, so every entry is freed at the end.
  2. Chains keep collisions together in one bucket.
  3. The report walks every bucket to find the busiest words.

Keywords and builtins used here

The run, in numbers

Lines
91
Characters to type
1632
Tokens
571
Three-star pace
105 tpm

At the three-star pace of 105 tokens a minute, this run takes about 326 seconds.

Type this snippet

Step 2 of 2 in Encore, step 20 of 20 in Data structures & algorithms.

← Previous