hashtable.c

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

// no actual pointer should have this value, due to alignment
static void* DELETED = (void*)1;

static int TABLE_SIZE = 701;

static int hash(int key) {
    return key % TABLE_SIZE;
}

static int hash2(int key) {
    return 1 + key % (TABLE_SIZE - 1);
}

typedef struct {
    int key;
    void* value;
} entry;

entry** ht_create() {
    entry** table = malloc(sizeof(entry*) * TABLE_SIZE);
    memset(table, 0, sizeof(entry*) * TABLE_SIZE);
    return table;
}

bool ht_put(entry** table, int key, void* value) {
    int start = hash(key);
    int idx = start;
    int second_hash = hash2(key);
    int i = 0;
    do {
        if (table[idx] == NULL) {
            table[idx] = malloc(sizeof(entry));
            table[idx]->key = key;
            table[idx]->value = value;
            return true;
        }
        else if (table[idx] != DELETED && table[idx]->key == key) {
            table[idx]->value = value;
            return true;
        }
    }
    while((idx = (start + second_hash * ++i) % TABLE_SIZE) != start);
    return false;
}

bool ht_get(entry** table, int key, void** value) {
    int start = hash(key);
    int idx = start;
    int second_hash = hash2(key);
    int i = 0;
    do {
        if (table[idx] == NULL) {
            return false;
        }
        else if (table[idx] != DELETED && table[idx]->key == key) {
            *value = table[idx]->value;
            return true;
        }
    }
    while((idx = (start + second_hash * ++i) % TABLE_SIZE) != start);
    return false;
}

bool ht_del(entry** table, int key) {
    int start = hash(key);
    int idx = start;
    int second_hash = hash2(key);
    int i = 0;
    do {
        if (table[idx]->key == key) {
            free(table[idx]);
            table[idx] = DELETED;
            return true;
        }
    }
    while((idx = (start + second_hash * ++i) % TABLE_SIZE) != start);
    return false;
}

int main() {
    entry** table = ht_create();
    assert(ht_put(table, 1234, (void*)5));
    assert(ht_put(table, 1234, (void*)5));
    assert(ht_put(table, 1234 + 701, (void*)6));

    long result;
    assert(ht_get(table, 1234, (void*)&result));
    assert(result == 5);
    assert(ht_get(table, 1234 + 701, (void*)&result));
    assert(result == 6);

    assert(ht_del(table, 1234));
    assert(ht_get(table, 1234, (void*)&result) != true);
    assert(ht_get(table, 1234 + 701, (void*)&result));
    assert(result == 6);
    return 0;
}