Iterable hashtable implementation in C

Question

I'm just finished my version of iterable hashtable. I want to review code in general (code style, data structures, remarks about the algorithms) and I have some questions:

1. I don't know how to implement errors in return-value way. So, I chose way when we contain error flag variable in struct. Is it correct?
2. What functions are missing in interface? Maybe pop() or something like this?
3. Where do I need includind headers like stddef.h or string.h? (e.g. I don't use functions from string.h in my header, do I need include it in htable.h?)

htable.h:

#ifndef HTABLE_H
#define HTABLE_H
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdbool.h>

typedef struct node_t {
    void* el;
    struct node_t* nextp;
} node_t;

typedef enum hterror_t {
    HTE_OK,
    HTE_MEM_EXHAUST,
    HTE_REMOVE,
    HTE_TOTAL
} hterror_t;

typedef struct index_t index_t;

enum { HTABLE_SIZE = 8191 };
typedef struct htable_t {
    node_t*    table[HTABLE_SIZE];
    index_t*   indexes;
    hterror_t  err_f;

    uint32_t   (*hash)(void *);
    int32_t    (*cmp)(void *, void *);
} htable_t;

htable_t*  htable_create(uint32_t (*hash)(void *), int32_t (*cmp)(void *, void *));
node_t*    htable_lookup(htable_t* ht, void* el, bool create);
void       htable_remove(htable_t* ht, void* el);
void       htable_foreach(htable_t* ht, void (*fn)(node_t *, void *), void *arg);
void       htable_destroy(htable_t* ht);

#endif // HTABLE_H

htable.c:

#include "htable.h"

typedef struct index_t {
    size_t index;
    struct index_t* nextp;
} index_t;

htable_t* htable_create(uint32_t (*hash)(void *), int32_t (*cmp)(void *, void *))
{
    htable_t* htable = malloc(sizeof(htable_t));
    if (htable == NULL)
        return NULL;

    memset(htable->table, 0, sizeof(htable->table[0]) * HTABLE_SIZE);
    htable->indexes = NULL;
    htable->err_f   = HTE_OK;
    htable->hash    = hash;
    htable->cmp     = cmp;

    return htable;
}

node_t* htable_lookup(htable_t* ht, void* el, bool create)
{
    node_t*   tmp;
    uint32_t  h;

    h = ht->hash(el) % HTABLE_SIZE;
    for (tmp = ht->table[h]; tmp != NULL; tmp = tmp->nextp)
        if (ht->cmp(tmp->el, el) == 0)
            return tmp;

    if (create) {
        if (ht->table[h] == NULL) { /* if there's no node for hash h */
            index_t* ni = malloc(sizeof(index_t));
            if (ni == NULL) {
                ht->err_f = HTE_MEM_EXHAUST;
                return NULL;
            }
            ni->index = h;
            ni->nextp = ht->indexes;
            ht->indexes = ni;
        }

        node_t* newnode = malloc(sizeof(node_t));
        if (newnode == NULL) {
            ht->err_f = HTE_MEM_EXHAUST;
            return NULL;
        }
        newnode->el = el;
        newnode->nextp = ht->table[h];
        ht->table[h] = newnode;
    }

    return tmp;
}

void htable_remove(htable_t* ht, void* el)
{
    node_t*  p, * prev;
    uint32_t h;

    h = ht->hash(el) % HTABLE_SIZE;

    prev = NULL;
    for (p = ht->table[h]; p != NULL; p = p->nextp) {
        if (ht->cmp(p->el, el) == 0) {
            if (prev == NULL)
                ht->table[h] = p->nextp;
            else
                prev->nextp = p->nextp;
            free(p);
            return ;
        }
        prev = p;
    }

    ht->err_f = HTE_REMOVE;
}

void htable_foreach(htable_t* ht,
                    void (*fn)(node_t *, void *), void *arg)
{
    index_t* prev, * p;
    node_t*  cur_n;

    prev = NULL;
    for (p = ht->indexes; p != NULL; p = p->nextp) {
        if (ht->table[p->index] == NULL) {
            if (prev == NULL) {
                ht->indexes = p->nextp;
                free(p);
                p = ht->indexes;
            } else {
                prev->nextp = p->nextp;
                free(p);
                p = prev;
            }
        }

        for (cur_n = ht->table[p->index]; cur_n != NULL; cur_n = cur_n->nextp)
            fn(cur_n, arg);
    }
}

void htable_destroy(htable_t* ht)
{
    index_t* buf_i;

    for (; ht->indexes != NULL; ht->indexes = buf_i) {
        buf_i = ht->indexes->nextp;
        if (ht->table[ht->indexes->index] != NULL) {
            node_t* buf_n;
            for (; ht->table[ht->indexes->index] != NULL; ht->table[ht->indexes->index] = buf_n) {
                buf_n = ht->table[ht->indexes->index]->nextp;
                free(ht->table[ht->indexes->index]);
            }
        }

        free(ht->indexes);
    }

    free(ht);
}

Simple usage of htable:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>
#include "htable.h"

/* ihash and icmp are needed for construct htable */
uint32_t ihash(void* y)
{
    uint32_t x = *(uint32_t *) y;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x =  (x >> 16) ^ x;
    return x;
}

int32_t icmp(void* a, void* b)
{
    return *(int *) a - *(int *) b;
}

/* icopy, ifree and iprint are not necessary */
void* icopy(void* i)
{
    int* _i = malloc(sizeof(int));
    if (_i == NULL)
        return NULL;
    *_i = *(int *) i;

    return _i;
}

void ifree(node_t* n, void* arg)
{
    (void) arg;
    if (n->el != NULL)
        free(n->el);
}

void iprint(node_t* np, void* arg)
{
    printf((char *) arg, (np == NULL) ? 0 : *(int *) np->el);
}

int main()
{
    htable_t* ht = htable_create(ihash, icmp);
    for (int i = 0; i < 255; ++i)
        htable_lookup(ht, icopy(&i), true);

    int k = 12;
    iprint(htable_lookup(ht, &k, false), "lookup: %d\n");
    ifree(htable_lookup(ht, &k, false), NULL);
    htable_remove(ht, &k);
    iprint(htable_lookup(ht, &k, false), "lookup: %d\n"); /* returns NULL */
    htable_foreach(ht, iprint, "foreach: %d\n");
    htable_foreach(ht, ifree, NULL); /* freeing memory that we allocated from the loop above */
    htable_destroy(ht);

    return 0;
}

Answer 1

• Combining lookup and insertion functionality in one function looks like an unnecessary violation of SRP. I strongly recommend to separate them.

• Keeping the error inside the structure is indeed questionable. Notice that once you split lookup and insert, return errcode; becomes natural: every function besides insert would just return an error code, and insert would return NULL on failure.

  If you still want to keep the error flag, you should at least clear it in the beginning of any function which may set it, and provide a function to check it. As of now, the client must directly access ht->err_f, which breaks the encapsulation.

• Speaking of encapsulation, the standard practice is to forward declare typedef struct htable_t htable_t; in the htable.h, and define it in htable.c. The client has no business knowing how exactly the table is organized.

• htable_foreach apparently attempts to compact the list of indices. It is a very strange place to do so. Removing an index is more natural in htable_remove. Meanwhile, I am not sure what benefits does the list of indices provide.