hash.h
Right off the bat, a few questionable practices with your declarations in this file
ht_insert(...)
TableEntry_t *ht_insert(HashTable_t *ht, char *k, char *v);
Why does this return a TableEntry_t? This is exposing an implemetation detail which the user of your hashtable has no business knowing about. Either return a HashTable_t or nothing at all.
ht_free(...)
void ht_free(HashTable_t *ht);
Without first looking at your implementation, I highly doubt this will work. A pointer to a heap object cannot be freed safely if you don't pass the pointer as a reference.
Let me clarify that last point. If you have a pointer, the safest way to free that pointer with a function is to do the following:
void my_lovely_free(void** ptr) {
free(*ptr);
*ptr = NULL; // explicitly set to NULL
}
...
void *ptr = ...
my_lovely_free(&ptr);
...
// In main ptr is now pointing to null
Otherwise if you do not explicitly set the pointer to null, it has potential of being reused and this could lead to the foreboding Segmentation fault or thrashing of the stack. You have been warned.
ht_index(...)
/* retrive value from key */
char *ht_index(HashTable_t *ht, char *k);
Why is this method called ht_index. That name in no way gives so much as a hint as to what this method does. Use the more conventional names such as ht_get or ht_retrieve. Anything less cryptic than ht_index will do.
In closing, you are exposing too much of your implementation details in this header file. A perfectly reasonable header will be something like:
struct HashTable_t;
struct TableEntry_t;
// function headers...
hash.c
HashTable_t *ht_create(size_t size) {...}
ht->tab is declared as struct TableEntry **tab;. This means it is a pointer to a pointer. i.e. if you wanted this to be an array of size pointers, the proper way to do so would be:
ht->tab = malloc(sizeof(*ht->tab) * size)
This has created an array of size TableEntry_t *, i.e if size happened to be 5, this is now an array of 5 TableEntry_t pointers.
What have you have done instead?
if ((ht->tab = malloc(sizeof(TableEntry_t) * size)) == NULL)
Means you have declared an array of 1 pointer to an array of size TableEntry_t's. i.e. you have declared an array containing a single pointer and this pointer points to an array of size TableEntry_t's. This may or may not be what you intended, so let's move on and see if that's correct.
And... we didn't have to go far to see that it was indeed not what you had intended.
int i;
for (i = 0; i < size; i++)
ht->tab[i] = NULL;
ht->size = size;
Here it seems you now want to initialize the pointers to null, and you are going through all size of them. This should have caused the program to crash. Did you not test this?
I must admit this last part bothered me quite a bit that it did not crash, even after testing it, but I finally realized C was just letting you live in oblivion. It had given you a loaded gun (as always) and you have just gleefully shot yourself in the foot. For a real test, try compiling and running this code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VEC_SIZE 8
int main(void)
{
char **vector = malloc(sizeof (char) * VEC_SIZE);
if (vector == NULL) {
puts("Could not allocate memory for program");
exit(EXIT_FAILURE);
}
int a;
for (a = 0; a < VEC_SIZE; a++) {
vector[a] = NULL;
}
for (a = 0; a < VEC_SIZE; a++) {
vector[a] = malloc(sizeof *vector[a] * 10);
strncpy(vector[a], "racecar", 10);
}
for (a = 0; a < VEC_SIZE; a++) {
printf("%s\n", vector[a]);
}
}
Hint: It doesn't end well. Fix your memory allocations
unsigned hash(HashTable_t *ht, char *s) {...}
Just one comment.
If it's a hash, it should be hashing and returning the value of the hash, not doing a modulos of the size of the hashtable.
Change this:
return hashval % ht->size; to return hashval;
The hashing itself is fine for such a small project. If you want it to be used on a grander scale, I would recommend finding one that quickly reaches avalanche.
When I first wanted to implement a hashtable, I had used this the tutorial on eternally confuzzled (back when the site was good ol' sky blue), so take a look at the hashing section and see if you can come up with a stronger hash function.
TableEntry_t *new(char *k, char *v) {...}
With regards to your use of strdup, according to cppreference,
As all functions from Dynamic Memory TS, strdup is only guaranteed to
be available if STDC_ALLOC_LIB is defined by the implementation
and if the user defines STDC_WANT_LIB_EXT2 to the integer constant
1 before including string.h.
So the fact that it is available means that something else had defined those mentioned macros, and you may or may not be aware of this. It could be that you are using a unix system in which case, it may be part of the unix standard library, but this not guaranteed to be the case on other platforms.
I guess the lesson here would be to use discretion when using the standard library extensions. Make sure you know which ones are part of the standard and which aren't.
TableEntry_t *ht_insert(HashTable_t *ht, char *k, char *v) {...}
I spot a potential candidate for memory leaks:
else
{
free(te->val);
if ((te->val = strdup(v)) == NULL)
return NULL;
}
So you want to return NULL if strdup failed to allocate memory for one measly string value? This is a bad idea!
Note the return type of this method. This means it is quite possible for someone to do something like:
my_ht = ht_insert(my_ht, "bob", "dad");
If NULL is returned, the user has lost the pointer to the original hashtable and you can no longer free that memory.
Moreover if the strdup function fails, and this function returns NULL, and the user is not careful to check for null (and neither does your function), the next time this function is called, it will result in a seg fault.
A much safer way of doing this is to understand why strdup would fail in the first place. Is it because it ran out of memory? In which case, you should exit the program because there is no more memory. In C++, you would throw some sort of exception.
In any case, this function should always return a live object or make it a void function. Returning null when the user expects a hashtable is not good programming style.
void te_free(TableEntry_t *te) {...}
As I mentioned previously, TableEntry_t should not be part of the public interface of this hashtable implementation and likewise neither should this function.
With regards to your recursive freeing, the method you use is quite eager. What I mean by this is that it quickly incurs stack frames when freeing this linked list-like structure. There is no need to recursively try to free the last one first (unless your implementation requires it, then you should be using a doubly linked list). If you still want to use recursion and are not satisfied with the solution provided by @Austin Hastings's answer, then here is a less eager recursive method:
void te_free(TableEntry_t **te)
{
TableEntry_t *next = NULL, *ptr = *te;
if (ptr != NULL)
{
next = ptr->next;
free(ptr->key);
free(ptr->val);
free(ptr);
*te = NULL;
}
te_free(&next);
}
This method is less eager AND safer. Note the NULL check on te. In the case where te is NULL, this method will not segfault, whereas your previous implementation will.
void ht_free(HashTable_t *ht) {...}
I already flagged this method in the beginning, so I won't bother doing it again. To illustrate what I meant, try running this code and observe what happens when memory is freed correctly vs when it is not:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VEC_SIZE 8
void my_free(char **vector, const unsigned size) {
int a;
for (a = 0; a < size; a++) {
free(vector[a]);
}
free(vector);
}
void my_better_free(char ***vector, const unsigned size) {
int a;
char **temp = *vector;
for (a = 0; a < size; a++) {
free(temp[a]);
}
free(*vector);
*vector = NULL;
}
int main(void)
{
char **vector = malloc(sizeof (*vector) * VEC_SIZE);
if (vector == NULL) {
puts("Could not allocate memory for program");
exit(EXIT_FAILURE);
}
int a;
for (a = 0; a < VEC_SIZE; a++) {
vector[a] = NULL;
}
for (a = 0; a < VEC_SIZE; a++) {
vector[a] = malloc(sizeof *vector[a] * 10);
strncpy(vector[a], "racecar", 10);
}
for (a = 0; a < VEC_SIZE; a++) {
printf("%s\n", vector[a]);
}
my_free(vector, VEC_SIZE);
vector[1] = malloc(sizeof *vector[1] * 10); // <- THIS!!!
puts("BOOOO!! Memory overwritten");
// my_better_free(&vector, VEC_SIZE);
// vector[1] = malloc(sizeof *vector[1] * 10); // Never!!
// puts("This never happened");
exit(EXIT_SUCCESS);
}
Remove comments on the those last three comments, and see how a freeing method should have worked.
Read why explicitly setting the freed pointer to null, here.
HashTable_t *ht_resize(HashTable_t *oht, size_t size) {...}
In light of the memory thing I mentioned, this method should take HashTable_t **oht.
Again, this should not return NULL. Just as in the case of ht_insert, it should either free memory and exit if the program runs out of memory, or it should take a pointer to a heap allocated hash table (type HashTable_t **oht). This will enable it to reassign the pointer without having to return it.
Conclusion
This has been a delight to review. Not only because I was able to find a lot of mistakes, but also because of the learning opportunity it gave to myself and hopefully to you.
When programming with C, you cannot just willy-nilly throw in whatever you want to make the program work. A perfectly working and compiling C program does not mean a perfectly safe C program. Be aware that programming with C is like handling a loaded gun without the safety on, at the most inconvenient time, you fingers might graze the trigger and it's game over.
Pay attention to your memory because that's where your program lives and does it's work, so it is important not to leave garbage memory lying around as that can really affect your program in the long run.
If you have any questions, leave a comment.
Addendum
For additional practice, try any of the following:
- Implement automatic resizing and load factor. Load factor is a ratio of the hashtable current size to it's capacity. For example a load factor of 80% means that when the hashtable is 80% full, the automatic resizing kicks in and resizes the hashtable by doubling it's size.
- This one is a bit of a stretch. Make the hashtable thread safe. By this I mean, if two threads were to attempt to store a new key-value pair in the hashtable, are you able to find a solution that will allow both threads to make their modifications without getting in trouble? If one inserts and the table is in the process of resizing while another tries to insert...what would be the outcome?
