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;
}

• pacmaninbw: Could you please include code that calls these functions so that we can perform a better review?

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.

• oss: Thank you for the answer! I saw this method (when we putting insert and lookup in one function) in book "The Practice of Programming" (c.2, p.56). Now I understand that way that used in the book is intended for concrete data, and not for abstract data.t. I remove indices in foreach() function because I think it will be faster to remove items like this, rather than going through the list every time when we calling remove(). Also, if you don't need to iterate over the table, you'll never remove indieces, except the call function destroy(). Correct me if I'm wrong. Thanks!
• chux: SRP acronym deserves definition/link
• oss: I think he meant The Single Responsibility Principle from SOLID