Some time ago I tried to make a generic linked list in pure C (no external libraries, only the C standard library) using void*s here. Building on top of that and with the same restrictions, I'm now making a hash table.
hashtable.h:
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include <stdbool.h>
#include <stddef.h>
#include "linkedlist.h"
typedef enum HashtableErrorCodes {
HTERR_NONE,
HTERR_NOTHIS,
HTERR_BADALLOC,
HTERR_NOSUCHVALUE,
HTERR_DUPENT
} HashtableErrorCodes;
typedef struct Hashtable Hashtable;
typedef struct HashtableEntry HashtableEntry;
struct HashtableEntry {
void *key;
void *data;
};
struct Hashtable {
Hashtable *this;
LinkedList **data;
size_t capacity;
void (*destructor)(Hashtable *this);
size_t (*hasher)(void *key, size_t maxIndex);
bool (*keyComparer)(void *a, void *b);
void (*keyDestroyer)(void *key);
void (*dataDestroyer)(void *data);
/**
* Inserts data to the hashtable. Takes a pointer to a key and a pointer to the data to be inserted.
*
* @param this Similar to C++'s implicit this parameter in class non-static functions.
* @param key A pointer to the key to identify the data in the future.
* @param data A pointer to the data to be stored.
*
* @returns HTERR_NONE if successful. HTERR_BADALLOC if space allocation to store the data failed.
*/
HashtableErrorCodes (*add)(Hashtable *this, void *const key, void *const data);
/**
* Finds previously inserted data. Takes a pointer to the key used when inserting the data. Outputs the data via a
* pointer to a pointer to the data.
*
* @param this Similar to C++'s implicit this parameter in class non-static functions.
* @param key A pointer to the key used when inserting the data.
* @param data An output pointer that may point to a pointer to the previously inserted data.
*
* @returns HTERR_NONE if the data was found. HTERR_NOSUCHVALUE if no entry under the given key was found, in which
* case the output pointer will be set to NULL.
*/
HashtableErrorCodes (*find)(Hashtable *const this, void *const key, void **const data);
/**
* Removes previously inserted data. Takes a pointer to the key used when inserting the data. If successful, will
* also deallocate the removed data and the key used to store it.
*
* @param this Similar to C++'s implicit this parameter in class non-static functions.
* @param key A pointer to the key used when inserting the data.
*
* @returns HTERR_NONE if the data was successfully deleted. HTERR_NOSUCHVALUE if no entry under the given key was
* found.
*/
HashtableErrorCodes (*remove)(Hashtable *const this, void *key);
/**
* Clears the hash table. All data will be deallocated by the key and data destroyer function provided during the
* hash table's creation.
*
* @param this Similar to C++'s implicit this parameter in class non-static functions.
*
* @returns None
*/
void (*clear)(Hashtable *const this);
};
/**
* Creates a hashtable. Takes a size. Optionally takes a hasher function to customize how indexes are allocated, a key
* comparer function to customize how key equality is evaluated, and a key and data destroyer function to enable complex
* deallocation sequences beyond a simple call to free (e.g., deallocating struct members) during data removal.
*
* @param capacity Specifies the capacity of the hashtable. Overflow will be stored as additional elements in a linked
* list.
* @param hasher A function to hash keys during data entry into the hashtable. Must return an index less than the value
* of capacity.
* @param keyComparer A function to compare the equality of keys.
* @param keyDestroyer A function to deallocate the key during data removal.
* @param dataDestroyer A function to deallocate data during data removal.
*
* @returns Returns a pointer to a Hashtable if successful, otherwise returns a NULL pointer.
*/
Hashtable *newHashtable(const size_t capacity,
size_t (*const hasher)(void *const key, const size_t maxIndex),
bool (*keyComparer)(void *const a, void *const b),
void (*keyDestroyer)(void *key),
void (*dataDesroyer)(void *data));
/**
* Deletes a hashtable. Takes a pointer to a hashtable. All data in the hash table will be deallocated by the data destroyer
* function provided during the hash table's creation.
*
* @param table A pointer to a pointer to the hashtable to be deleted.
* @returns None
*/
void deleteHashtable(Hashtable *const table);
HashtableEntry *newHashtableEntry(void *const key, void *const data);
#endif
hashtable.c:
#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include "hashtable.h"
#include "linkedlist.h"
void ht_default_destructor(Hashtable *const this) {
if (this == NULL) return;
for (size_t i = 0; i < this->capacity; i++) {
deleteLinkedList(this->data[i]);
this->data[i] = NULL;
}
}
size_t ht_default_hasher(void *const key, const size_t capacity) {
size_t *const castedKey = (size_t *const) key;
return *castedKey % capacity;
}
bool ht_default_keyComparer(void *const a, void *const b) {
size_t *const castedA = (size_t *const) a;
size_t *const castedB = (size_t *const) b;
return castedA == castedB;
}
void ht_default_keyDestroyer(void *key) {
free(key);
}
void ht_default_dataDestroyer(void *data) {
HashtableEntry *castedData = (HashtableEntry *) data;
free(castedData->data);
free(castedData);
}
HashtableErrorCodes ht_default_add(Hashtable *const this, void *const key, void *const data) {
if (this == NULL) return HTERR_NOTHIS;
const size_t index = this->hasher(key, this->capacity);
if (this->data[index] == NULL) {
LinkedList *const list = newLinkedList(NULL, this->dataDestroyer);
if (list == NULL) return HTERR_BADALLOC;
this->data[index] = list;
}
HashtableEntry *const entry = newHashtableEntry(key, data);
if (entry == NULL) {
// Entry allocation might have failed, but the list is still good for next time so no need to clean up
return HTERR_BADALLOC;
}
const LinkedListErrors res = this->data[index]->addUnique(this->data[index]->this, entry);
if (res == LLERR_DUPENT) {
// This entry under this key already exists
return HTERR_DUPENT;
} else if (res != LLERR_NONE) {
// Something else went wrong, assume list failed to allocate node
return HTERR_BADALLOC;
}
return HTERR_NONE;
}
HashtableErrorCodes ht_default_find(Hashtable *const this, void *const key, void **const data) {
if (this == NULL) return HTERR_NOTHIS;
const size_t index = this->hasher(key, this->capacity);
LinkedList *const list = this->data[index];
if (list == NULL) {
*data = NULL;
return HTERR_NOSUCHVALUE;
}
LinkedListNode *node = list->head;
while (node != NULL) {
HashtableEntry *entry = node->data;
node = node->next;
if (entry != NULL) {
if (this->keyComparer(entry->key, key)) {
*data = entry->data;
return HTERR_NONE;
}
}
}
*data = NULL;
return HTERR_NOSUCHVALUE;
}
HashtableErrorCodes ht_default_remove(Hashtable *const this, void *key) {
if (this == NULL) return HTERR_NOTHIS;
const size_t htIndex = this->hasher(key, this->capacity);
LinkedList *const list = this->data[htIndex];
if (list == NULL) return HTERR_NOSUCHVALUE;
bool llFound = false;
size_t llIndex = 0;
LinkedListNode *node = list->head;
while (node != NULL) {
HashtableEntry *entry = node->data;
if (this->keyComparer(entry->key, key)) {
llFound = true;
break;
}
llIndex++;
node = node->next;
}
if (llFound) {
const LinkedListErrors res = list->removeByIndex(list->this, llIndex);
if (res != LLERR_NONE) {
// it probably didn't exist
return HTERR_NOSUCHVALUE;
}
return HTERR_NONE;
}
return HTERR_NOSUCHVALUE;
}
void ht_default_clear(Hashtable *const this) {
if (this == NULL) return;
for (size_t i = 0; i < this->capacity; i++) {
if (this->data[i] == NULL) continue;
deleteLinkedList(this->data[i]);
this->data[i] = NULL;
}
}
Hashtable *newHashtable(const size_t capacity,
size_t (*const hasher)(void *const key, const size_t maxIndex),
bool (*keyComparer)(void *const a, void *const b),
void (*keyDestroyer)(void *key),
void (*dataDestroyer)(void *data)) {
Hashtable *const ht = malloc(sizeof(*ht));
if (ht == NULL) return NULL;
ht->this = ht;
ht->destructor = ht_default_destructor;
ht->hasher = hasher != NULL ? hasher : ht_default_hasher;
ht->keyComparer = keyComparer != NULL ? keyComparer : ht_default_keyComparer;
ht->keyDestroyer = keyDestroyer != NULL ? keyDestroyer : ht_default_keyDestroyer;
ht->dataDestroyer = dataDestroyer != NULL ? dataDestroyer : ht_default_dataDestroyer;
ht->add = ht_default_add;
ht->find = ht_default_find;
ht->remove = ht_default_remove;
ht->clear = ht_default_clear;
ht->data = calloc(capacity, sizeof(*(ht->data)));
ht->capacity = capacity;
return ht;
}
void deleteHashtable(Hashtable *const table) {
if (table == NULL) return;
table->destructor(table->this);
}
HashtableEntry *newHashtableEntry(void *const key, void *const data) {
HashtableEntry *const entry = malloc(sizeof(*entry));
if (entry == NULL) return NULL;
entry->key = key;
entry->data = data;
return entry;
}
linkedlist.h (includes suggested improvements + more to accomodate hashtable's needs):
#include <stdbool.h>
#include <stddef.h>
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
typedef enum LinkedListErrors {
LLERR_NONE,
LLERR_NOTHIS,
LLERR_BADALLOC,
LLERR_NOSUCHVALUE,
LLERR_BADINDEX,
LLERR_DUPENT
} LinkedListErrors;
typedef struct LinkedList LinkedList;
typedef struct LinkedListNode LinkedListNode;
struct LinkedListNode {
LinkedListNode *next;
void *data;
};
struct LinkedList {
LinkedList *this;
LinkedListNode *head;
size_t size;
void (*destructor)(LinkedList *const this);
int (*dataComparer)(void *const a, void *const b);
void (*dataDestroyer)(void *const data);
/**
* Inserts data to the linked list at the tail end. Takes a pointer to the data to be inserted. Duplicate data may
* be inserted.
*
* @param this Similar to C++'s implicit this parameter in class non-static functions.
* @param data A pointer to the data to be inserted.
*
* @returns Returns LLERR_NONE if successful. LLERR_BADALLOC if space allocation to store the data failed.
*/
LinkedListErrors (*add)(LinkedList *const this, void *const data);
/**
* Similar to the regular add function. Duplicate data may not be inserted, however it is up to the caller to decide
* how the data should be treated should insertion fail. Data will not be deallocated if insertion fails.
*
* @param this Similar to C++'s implicit this parameter in class non-static functions.
* @param data A pointer to the data to be inserted.
*
* @returns Returns LLERR_NONE if successful. LLERR_BADALLOC if space allocation to store the data failed. LLERR_DUPENT
* if the data being inserted already exists.
*/
LinkedListErrors (*addUnique)(LinkedList *const this, void *const data);
/**
* Finds previously inserted data. Takes a filtering function. Outputs data via a pointer to a pointer to the data.
* Optionally writes the index at which the data is found to a pointer.
*
* @param this Similar to C++'s implicit this parameter in class non-static functions.
* @param comparer A filtering function.
* @param data An output pointer that may point to a pointer to the previously inserted data.
* @param index An output pointer that may point to a number indicating the index at which the data was found.
*
* @returns Returns LLERR_NONE if successful. LLERR_NOSUCHVALUE if the comparer function provided didn't find any
* matches, in which case the output data pointer will be set to NULL and the value pointed to by the output index
* pointer set to 0.
*/
LinkedListErrors (*find)(LinkedList *const this, bool (*comparer)(void *const data), void **const data, size_t *const index);
/**
* Removes previously inserted data. Takes an index.
*
* @param this Similar to C++'s implicit this parameter in class non-static functions.
* @param index The index of the data to be deleted. Must be a valid index.
*
* @returns Returns LLERR_NONE if successful. LLERR_BADINDEX if the index provided is invalid. LLERR_NOSUCHVALUE if
* no data was found under the given index.
*/
LinkedListErrors (*removeByIndex)(LinkedList *const this, const size_t index);
/**
* Removes previously inserted data. Takes a sample object which will be evaluated for equality by the data comparer
* function provided during the linked list's creation.
*
* @param this Similar to C++'s implicit this parameter in class non-static functions.
* @param object A pointer to the sample object.
*
* @returns Returns LLERR_NONE if successful. LLERR_NOSUCHVALUE if the sample object provided is not found to be
* equal to any object in the linked list by the data comparer function provided during the linked list's creation.
*/
LinkedListErrors (*removeByObject)(LinkedList *const this, void *const object);
/**
* Clears the linked list. All data will be deallocated by the data destroyer function provided during the linked
* list's creation.
*
* @param this Similar to C++'s implicit this parameter in class non-static functions.
*
* @returns None
*/
void (*clear)(LinkedList *const this);
};
/**
* Creates a linked list. Optionally takes a data comparer function to customize how data equality is evaluated and a
* data destroyer function to enable complex data deallocation sequences beyond a simple call to free on the data (e.g.,
* deallocating struct members) during data removal.
*
* @param dataComparer A function to compare the equality of data.
* @param dataDestroyer A function to deallocate data during data removal.
*
* @returns Returns a pointer to a linked list if successful, otherwise returns a NULL pointer.
*/
LinkedList *newLinkedList(int (*const dataComparer)(void *const a, void *const b), void (*const dataDestroyer)(void *data));
/**
* Deletes a linked list. Takes a pointer to a linked list. All data in the linked list will be deallocated by the data
* destroyer function provided during the linked list's creation.
*
* @param list A pointer to the linked list to be deleted.
*
* @returns None
*/
void deleteLinkedList(LinkedList *const list);
#endif
linkedlist.c:
#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>
#include "linkedlist.h"
void ll_default_destructor(LinkedList *const this) {
if (this == NULL) return;
LinkedListNode *node = this->head;
while (node != NULL) {
LinkedListNode *prev = node;
node = node->next;
this->dataDestroyer(prev->data);
free(prev);
}
this->head = NULL;
}
int ll_default_dataComparer(void *const a, void *const b) {
int *const castedA = (int *const) a;
int *const castedB = (int *const) b;
return (*castedA > *castedB) - (*castedA < *castedB);
}
void ll_default_dataDestroyer(void *const data) {
free(data);
}
LinkedListErrors ll_default_add(LinkedList *const this, void *const data, const bool unique) {
if (this == NULL) return LLERR_NOTHIS;
LinkedListNode *const newNode = malloc(sizeof(LinkedListNode));
if (newNode == NULL) return LLERR_BADALLOC;
newNode->next = NULL;
newNode->data = data;
LinkedListNode *prevNode = NULL;
LinkedListNode *currNode = this->head;
if (currNode == NULL) {
this->head = newNode;
} else {
while (currNode != NULL) {
if (unique) {
if (this->dataComparer(currNode->data, data) == 0) {
free(newNode);
return LLERR_DUPENT;
}
}
prevNode = currNode;
currNode = currNode->next;
}
prevNode->next = newNode;
}
this->size++;
return LLERR_NONE;
}
LinkedListErrors ll_default_addNonUnique(LinkedList *const this, void *const data) {
return ll_default_add(this, data, false);
}
LinkedListErrors ll_default_addUnique(LinkedList *const this, void *const data) {
return ll_default_add(this, data, true);
}
LinkedListErrors ll_default_find(LinkedList *const this, bool (*comparer)(void *const data), void **const data, size_t *const index) {
if (this == NULL) return LLERR_NOTHIS;
LinkedListNode *node = this->head;
size_t currentIndex = 0;
while (node != NULL) {
if (comparer(node->data)) {
if (data != NULL) *data = node->data;
if (index != NULL) *index = currentIndex;
return LLERR_NONE;
}
node = node->next;
currentIndex++;
}
if (data != NULL) *data = NULL;
if (index != NULL) *index = 0;
return LLERR_NOSUCHVALUE;
}
LinkedListErrors ll_default_removeByIndex(LinkedList *const this, const size_t index) {
if (this == NULL) return LLERR_NOTHIS;
if (index >= this->size) return LLERR_BADINDEX;
LinkedListNode *prevNode = NULL;
LinkedListNode *currNode = this->head;
for (size_t i = 0; i < index; i++) {
if (currNode == NULL) return LLERR_NOSUCHVALUE;
prevNode = currNode;
currNode = currNode->next;
}
if (prevNode != NULL) {
prevNode->next = currNode->next;
this->dataDestroyer(prevNode->data);
} else {
this->head = currNode->next;
}
free(prevNode);
this->size--;
return LLERR_NONE;
}
LinkedListErrors ll_default_removeByObject(LinkedList *const this, void *const object) {
if (this == NULL) return LLERR_NOTHIS;
LinkedListNode *prevNode = NULL;
LinkedListNode *currNode = this->head;
while (currNode != NULL) {
if (this->dataComparer(currNode->data, object) == 0) {
if (prevNode != NULL) {
prevNode->next = currNode->next;
this->dataDestroyer(currNode->data);
} else {
this->head = currNode->next;
}
free(currNode);
this->size--;
return LLERR_NONE;
}
prevNode = currNode;
currNode = currNode->next;
}
return LLERR_NOSUCHVALUE;
}
void ll_default_clear(LinkedList *const this) {
if (this == NULL) return;
LinkedListNode *prevNode = this->head;
LinkedListNode *currNode = this->head;
while (currNode != NULL) {
prevNode = currNode;
currNode = currNode->next;
this->dataDestroyer(prevNode->data);
free(prevNode);
}
this->head = NULL;
}
LinkedList *newLinkedList(int (*const dataComparer)(void *const a, void *const b), void (*const dataDestroyer)(void *data)) {
LinkedList *const list = malloc(sizeof(LinkedList));
if (list == NULL) return NULL;
list->this = list;
list->destructor = ll_default_destructor;
list->dataComparer = dataComparer != NULL ? dataComparer : ll_default_dataComparer;
list->dataDestroyer = dataDestroyer != NULL ? dataDestroyer : ll_default_dataDestroyer;
list->add = ll_default_addNonUnique;
list->addUnique = ll_default_addUnique;
list->find = ll_default_find;
list->removeByIndex = ll_default_removeByIndex;
list->removeByObject = ll_default_removeByObject;
list->clear = ll_default_clear;
list->head = NULL;
list->size = 0;
return list;
}
void deleteLinkedList(LinkedList *const list) {
if (list == NULL) return;
list->destructor(list->this);
}
main.c (testing code is not as rigorously written as the main hashtable code):
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hashtable.h"
typedef struct Pizza {
char *name;
char *flavor;
size_t size;
} Pizza;
Pizza *newPizza(char *name, char *flavor, size_t size) {
Pizza *p = malloc(sizeof(*p));
// p->name = malloc((strlen(name) + 1) * sizeof(*(p->name)));
// p->name = malloc(256);
// strcpy(p->name, name);
p->name = strdup(name);
// p->flavor = malloc(strlen(flavor) + 1 * sizeof(*(p->flavor)));
// p->flavor = malloc(256);
// strcpy(p->flavor, flavor);
p->flavor = strdup(flavor);
p->size = size;
return p;
}
size_t hash(void *key, size_t maxIndex) {
char *castedKey = (char *) key;
size_t len = strlen(castedKey);
size_t h = 0;
for (size_t i = 0; i < len; i++) h += castedKey[i];
h %= maxIndex;
return h;
}
bool keycompare(void *a, void *b) {
char *castedA = (char *) a;
char *castedB = (char *) b;
return strcmp(castedA, castedB) == 0;
}
void keynt(void *key) {
// stub, since our key is part of our data,
// which will be deallocated by the data
// destroyer
}
void datant(void *data) {
Pizza *castedData = (Pizza *) data;
free(castedData->name);
free(castedData->flavor);
free(castedData);
}
void printpizza(Pizza *p) {
if (p == NULL) printf("NULL\n"); else
printf("{ name: %s, flavor: %s, size: %zu }\n\n", p->name, p->flavor, p->size);
}
void printtable(Hashtable *ht) {
printf("[\n");
for (size_t i = 0; i < ht->capacity; i++) {
printf("\t%zu: [\n", i);
LinkedList *ll = ht->data[i];
if (ll == NULL) {
printf("\t\tNULL,\n");
} else {
LinkedListNode *node = ll->head;
while (node != NULL) {
HashtableEntry *hte = (HashtableEntry *) node->data;
Pizza *p = (Pizza *) hte->data;
printf("\t\t{\n\t\t\tname: %s,\n\t\t\tflavor: %s,\n\t\t\tsize: %zu\n\t\t},\n", p->name, p->flavor, p->size);
node = node->next;
}
}
printf("\t],\n\n");
}
printf("]\n\n");
}
int main(void) {
Hashtable *table = newHashtable(3, hash, keycompare, keynt, datant);
Pizza *p1 = newPizza("Pizzus Tinyeus", "Bland", 69);
table->add(table->this, p1->name, p1);
Pizza *p2 = newPizza("Pizzus Smallus", "Sour", 420);
table->add(table->this, p2->name, p2);
Pizza *p3 = newPizza("Pizzus Biggus", "Spicy", 42069);
table->add(table->this, p3->name, p3);
Pizza *p4 = newPizza("Pizzus Enormous", "Magic", 69420);
table->add(table->this, p4->name, p4);
// do we have all the pizzas?
printf("const pizzas = ");
printtable(table);
// can we insert a duplicate pizza?
HashtableErrorCodes err = table->add(table->this, p4->name, p4);
printf("err = %d\n\n", err);
printf("const pizzasagain = ");
printtable(table);
// can we find a pizza?
Pizza *p;
table->find(table->this, "Pizzus Biggus", &p);
printf("const pizza = ");
printpizza(p);
// can we delete a pizza?
table->remove(table->this, "Pizzus Enormous");
printf("const pizzasyetagain = ");
printtable(table);
// can we delete everything?
table->clear(table->this);
printf("const nopizzas = ");
printtable(table);
// not sure how to assert it's really gone with no leaks but at least it doesn't crash
deleteHashtable(table->this);
return 0;
}
Output of testing code as generated by ./main > res.txt:
const pizzas = [
0: [
{
name: Pizzus Tinyeus,
flavor: Bland,
size: 69
},
{
name: Pizzus Biggus,
flavor: Spicy,
size: 42069
},
],
1: [
{
name: Pizzus Enormous,
flavor: Magic,
size: 69420
},
],
2: [
{
name: Pizzus Smallus,
flavor: Sour,
size: 420
},
],
]
err = 4
const pizzasagain = [
0: [
{
name: Pizzus Tinyeus,
flavor: Bland,
size: 69
},
{
name: Pizzus Biggus,
flavor: Spicy,
size: 42069
},
],
1: [
{
name: Pizzus Enormous,
flavor: Magic,
size: 69420
},
],
2: [
{
name: Pizzus Smallus,
flavor: Sour,
size: 420
},
],
]
const pizza = { name: Pizzus Biggus, flavor: Spicy, size: 42069 }
const pizzasyetagain = [
0: [
{
name: Pizzus Tinyeus,
flavor: Bland,
size: 69
},
{
name: Pizzus Biggus,
flavor: Spicy,
size: 42069
},
],
1: [
],
2: [
{
name: Pizzus Smallus,
flavor: Sour,
size: 420
},
],
]
const nopizzas = [
0: [
NULL,
],
1: [
NULL,
],
2: [
NULL,
],
]
The linked list part is included as a dependency, the main part I'm looking for a review for is the hashtable itself (I'll post a separate request for the improved linked list).
This time around I've identified a few of my own concerns while writing this:
The original linked list interface was rather unusable to implement the hashtable. After a few moments of scratching my head I concluded it was easier / faster to access the list myself rather than use its API, however, is there anything I can do to salvage it? The API is good enough for generic usage, however not very good to use as a base for other data structures, such as this hashtable.
One of the suggestions given for my linked list was to use
constwhere possible. Have I over/under done it here? Are there places where there could beconstand yet I left it out or vice versa?
Thank you for your time.
PS: Functions with comments in the header files are what I consider to be the "public APIs", while those without I consider "internal functions".
