tiny_map.c

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

#define CAPACITY 4096

typedef struct Entry {
    char*         key;
    void*         value;
    struct Entry* next;
} Entry;

Entry* entries[CAPACITY];

unsigned _hash(char* key) {
    unsigned hash;
    for (hash = 0; *key != 0; key++)
        hash = *key + 31 * hash;
    return hash % CAPACITY;
}

void* get(char* key) {
    Entry* entry;
    for (entry = entries[_hash(key)]; entry; entry = entry->next)
        if (!strcmp(key, entry->key))
            return entry->value;
    return 0;
}

void put(char* key, void* value) {
    Entry* entry;
    unsigned hash = _hash(key);
    for (entry = entries[hash]; entry; entry = entry->next)
        if (!strcmp(key, entry->key))
        {
            entry->value = value;
            return;
        }
    entry = (Entry*) malloc(sizeof(Entry));
    entry->key = key;
    entry->value = value;
    entry->next = entries[hash];
    entries[hash] = entry;
}

#include <stdio.h>

void main()
{
    int i;
    printf("put\n");
    for (i = 0; i < 2000; ++i)
    {
        char* key = malloc(32);
        sprintf(key, "%d", i);
        put(key, (void*) (i * 10));
    }
    printf("get\n");
    printf("%d\n", (int) get("1234"));
}

This hash map is good enough for one off apps.

But terrible enough for reusability:

entry = (Entry*) malloc(sizeof(Entry)); // Line 38

void _free(Entry* entry) { // This is insanity
    if (entry->next)
        _free(entry->next);
    free(entry);
}

void clear() {
    int i;
    for (i = 0; i < CAPACITY; ++i)
        if (entries[i]) {
            _free(entries[i]);
            entries[i] = 0;
        }
}