An Introduction to Imperative Programming

typedef int (*eq_t)(void* p, void* q);
typedef int (*hash_fct_t)(void* key);

typedef struct entry_t {
    void* key;
    struct entry_t* next;
} entry_t;

typedef struct {
    unsigned size;          // # of keys in the table
    unsigned table_length;  // length of the hash table
    float max_load_factor;  // the maximal load factor
    hash_fct_t h;           // the hash function.
    entry_t** table;        // an array of singly-linked entry lists
} chaining_hashtable_t;

/// This function searches for a key 
/// in a hash tab with separate chaining.
/// @param ht The hash table
/// @param key The key to search for
/// @param hash The hash function value for key
/// @param eq A function to compare two keys for equality
/// @param insert The address of a pointer to an entry_t pointer.
///               There, we will put the address of the pointer
///               where the new collision chain entry should be
///               appended in the case where we insert a new key.
int hash_chain_search(chaining_hashtable_t* ht, void* key,
                      eq_t equals, entry_t*** insert) {
    unsigned bucket = ht->h(key) % ht->table_length;  // compute h_m
    *insert = ht->table + bucket;       
    for (entry_t* e = ht->table[bucket]; e != NULL; e = e->next) {
        if (equals(e->key, key))
            return 1;
        *insert = &e->next;
    }
    return 0;
}

/// Insert into a hash table with separate chaining.
int hash_chain_insert(chaining_hashtable_t* ht, void* key, eq_t equals) {
    entry_t** insert;
    int found = hash_chain_search(ht, key, equals, &insert);
    if (found) {
        // the hash table did not change
        return 0;
    }
    // The search function sets insert to the address of 
    // the last next pointer in the collision chain
    assert (*insert == NULL);
    // here, we know that the element is not in the table
    // so we allocate a new list entry
    entry_t* e = malloc(sizeof(*e));
    // initialize the entry
    e->next = NULL;
    e->key = key;
    // and append it to the collision chain
    *insert = e; 
    ++ht->size;
    return 1;
}

int hash_chain_insert_resize(chaining_hashtable_t* ht, void* key, eq_t eq) {
    if (ht->size > ht->max_load_factor * ht->table_length) {
        ht->table_length *= 2;
        assert (ht->size < ht->max_load_factor * ht->table_length);
        entry_t** old_table = ht->table;
        // allocate new table and initialize to 0
        ht->table = calloc(ht->table_length, sizeof(ht->table[0]));
        // go over old hash table and add each element to new table
        rehash_table(ht, old_table);
        // free old table
        free(old_table);
    }

    return hash_chain_insert(ht, key, eq);
}

typedef struct {
    unsigned size;
    unsigned table_length;
    float max_load_factor;
    hash_fct_t h;
    void** table;
} open_addr_hashtable_t;

int open_addr_hashtable_search(open_addr_hashtable_t* ht, 
                               void *key, eq_t equals) {
    for (unsigned i = 0; i < ht->table_length; i++) {
        // call probing function to compute bucket 
        // of collision chain entry
        unsigned bucket = h_prime(ht->h(key), i);  
        void* k = ht->table[bucket];
        if (k == NULL || equals(k, key))
            return bucket;
    }