6
\$\begingroup\$

This implementation resolves collisions using linked-lists. The hash function is from K&R but can be easily changed to more effective one.

hash.c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "hash.h"

/* creates hashtable */
/* NOTE: dynamically allocated, remember to ht_free() */
HashTable_t *ht_create(size_t size)
{
    HashTable_t *ht = NULL;
    if ((ht = malloc(sizeof(HashTable_t))) == NULL)
        return NULL;
    /* allocate ht's table */
    if ((ht->tab = malloc(sizeof(TableEntry_t) * size)) == NULL)
        return NULL;
    /* null-initialize table */
    int i;
    for (i = 0; i < size; i++)
        ht->tab[i] = NULL;
    ht->size = size;
    return ht;
}

/* creates hash for a hashtab */
unsigned hash(HashTable_t *ht, char *s)
{
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31 * hashval;
    return hashval % ht->size;
}

/* creates a key-val pair */
TableEntry_t *new(char *k, char *v)
{
    TableEntry_t *te = NULL;
    if ((te = malloc(sizeof(TableEntry_t))) == NULL)
        return NULL;
    if ((te->key = strdup(k)) == NULL)
        return NULL;
    if ((te->val = strdup(v)) == NULL)
        return NULL;
    te->next = NULL;
    return te;
}

TableEntry_t *lookup(HashTable_t *ht, char *k)
{
    TableEntry_t *te;
    /* step through linked list */
    for (te = ht->tab[hash(ht, k)]; te != NULL; te = te->next)
        if (strcmp(te->key, k) == 0)
            return te; /* found */
    return NULL; /* not found */
}

/* inserts the key-val pair */
TableEntry_t *ht_insert(HashTable_t *ht, char *k, char *v)
{
    TableEntry_t *te;
    /* unique entry */
    if ((te = lookup(ht, k)) == NULL)
    {
        te = new(k, v);
        unsigned hashval = hash(ht, k);
        /* insert at beginning of linked list */
        te->next = ht->tab[hashval]; 
        ht->tab[hashval] = te;
    }
    /* replace val of previous entry */
    else
    {
        free(te->val);
        if ((te->val = strdup(v)) == NULL)
            return NULL;
    }
    return te;
}

/* retrive value from key */
char *ht_index(HashTable_t *ht, char *k)
{
    TableEntry_t *te;
    if ((te = lookup(ht, k)) == NULL)
        return NULL;
    return te->val;
}

/* recursively frees table entriy chains, starting with last one added */
void te_free(TableEntry_t *te)
{
    if (te->next != NULL) 
    {
        te_free(te->next);
        free(te->next);
    }
    free(te->key);
    free(te->val);
}

/* frees hashtable created from ht_create() */
void ht_free(HashTable_t *ht)
{
    int i;
    for (i = 0; i < ht->size; i++)
        if (ht->tab[i] != NULL)
            te_free(ht->tab[i]);
    free(ht);
}

/* resizes hashtable, returns new hashtable and frees old*/
HashTable_t *ht_resize(HashTable_t *oht, size_t size)
{
    HashTable_t *nht; /* new hashtable */
    nht = ht_create(size);
    /* rehash */
    int i;
    TableEntry_t *te;
    /* loop through hashtable */
    for (i = 0; i < oht->size; i++)
        /* loop through linked list */
        for (te = oht->tab[i]; te != NULL; te = te->next)
            if (ht_insert(nht, te->key, te->val) == NULL)
                return NULL;
    ht_free(oht);
    return nht;
}

hash.h:

/* a hash-table implementation in c */
/*
hashing algorithm: hashval = *s + 31 * hashval
resolves collisions using linked lists
*/

#ifndef HASH
#define HASH

typedef struct TableEntry /* hashtab entry */
{
    struct TableEntry *next;
    char *key;
    char *val;
} TableEntry_t;

typedef struct HashTable
{
    size_t size;
    struct TableEntry **tab;
} HashTable_t;

/* inserts the key-val pair */
TableEntry_t *ht_insert(HashTable_t *ht, char *k, char *v);

/* creates hashtable */
/* NOTE: dynamically allocated, remember to ht_free() */
HashTable_t *ht_create(size_t size);

/* frees hashtable created from ht_create() */
void ht_free(HashTable_t *ht);

/* retrive value from key */
char *ht_index(HashTable_t *ht, char *k);

/* resizes hashtable, returns new hashtable and frees old*/
HashTable_t *ht_resize(HashTable_t *oht, size_t size);

#endif

main.c (if you wanted to test):

#include <stdio.h>

#include "hash.h"

int main(void)
{
    HashTable_t *ht = ht_create(101);

    ht_insert(ht, "john", "employee");
    ht_insert(ht, "alex", "mom");
    ht_insert(ht, "riley", "boss");
    ht_insert(ht, "sam", "dad");

    printf("%s\n", ht_index(ht, "john"));
    printf("%s\n", ht_index(ht, "alex"));
    printf("%s\n", ht_index(ht, "riley"));
    printf("%s\n", ht_index(ht, "sam"));

    ht = ht_resize(ht, 201);

    printf("%s\n", ht_index(ht, "john"));
    printf("%s\n", ht_index(ht, "alex"));
    printf("%s\n", ht_index(ht, "riley"));
    printf("%s\n", ht_index(ht, "sam"));

    ht_free(ht);
}
\$\endgroup\$
  • \$\begingroup\$ What are your goals of this review? General comments? Something specific? \$\endgroup\$ – chux Sep 19 '17 at 2:32
5
\$\begingroup\$
  1. Probably the biggest pitfall I see is the question of ownership. As the code is written, you call strdup on both the key and value when you insert them in the new function. (By the way: you leak memory if strdup returns NULL.)

    That makes the ownership clear, but it forces a copy of both the key and value, and doesn't allow the user to do easy updates. I would suggest not trying to duplicate the value part at all. I would further suggest making that a void * pointer rather than a char * - the current implementation is too tied to the string -> string model.

    You might keep your own copy of the key - that makes sense if you are reading keys from a file buffer where the memory is likely to be re-used. Again, though, I would suggest pushing the ownership issue onto the user: let them call strdup for you, or take responsibility for interning the strings, or whatever.

  2. You recompute the hash during resize operations. As your hash functions grows more powerful, this gets more expensive. I'd suggest storing the hash value in the key record, and not doing any hashing during resize - just compute the stored hash value modulo the new table size.

  3. Your type names are a mix of Pascal case and the C _t suffix. I'd suggest that you pick one: either use hashtable_t or HashTable as your type name.

  4. Further, why not include the pointer in the type definition? Instead of declaring HashTable *ht; it would be easier to declare HashTable ht; and let the type be opaque.

  5. You are leaking names into the outside. The various table-entry functions should definitely be prefixed with te_ (new, hash, and lookup). Ideally, they should be declared static and completely hidden from outside access.

  6. Consider storing your hash/key/value entries in a simple dynamic array. You can then create a separate array of shorts or ints (depending on size) to serve as your hash space. You would hash into the hash space, then use that to find an index into the main table of entries. This lets you store the entries in insertion order (which can be useful), and lets you access the hash space using open addressing with a fairly high degree of locality. (You could even use unsigned char indexes in your hash space, if you felt there were enough use cases for small tables. Keep in mind that the size of the index is determined by the number of entries, not the size of the hash space: you could have 1024 buckets with < 256 entries and still use uchar indexes - damn few collisions, too, I'd bet.)

  7. I really think you need a better hashing function. In order to prepare for this, you should probably treat your key as a memory block, instead of as a string: pass a start-pointer and a size to the hash function.

  8. Next, you might consider using a much stronger hash. Even a cryptographic hash. If you are caching your hash values, you'll never have to call it again on a key, and at some point the probability of a collision gets very close to zero (this is how Mercurial identifies changesets, for example).

Update:

Here's the leaking function:

TableEntry_t *new(char *k, char *v)
{
    TableEntry_t *te = NULL;
    if ((te = malloc(sizeof(TableEntry_t))) == NULL)
        return NULL;
    if ((te->key = strdup(k)) == NULL)
        return NULL;
    if ((te->val = strdup(v)) == NULL)
        return NULL;
    te->next = NULL;
    return te;
}

Now, suppose that the expression (te->val = strdup(v)) == NULL evaluates as true.

In that case, you have your te pointing to allocated memory; you have te->key pointing to allocated memory; and you have te->next pointing to uninitialized memory.

Ignoring my suggestion to completely rewrite this part (#6), I would suggest rewriting this using calloc. Yes, it's possible to manage the zeros on your own for a structure this small, but why bother?

Something like this:

if ((te = calloc(1, sizeof *te)) == NULL
    || (te->key = strdup(k)) == NULL 
    || (te->val = strdup(v)) == NULL) 
{
    te_free(te);
    return NULL;
}

return te;

You will need to amend te_free to actually free the entry, and to get rid of that pesky recursion (which exposes you to a stack overflow attack). The current version never frees the te pointer, for some reason:

void te_free(TableEntry_t *te)
{
    if (te->next != NULL) 
    {
        te_free(te->next);
        free(te->next);
    }
    free(te->key);
    free(te->val);
}

Instead, use a loop and consume the entries from the front:

TableEntry_t *next;

while (te != NULL) 
{
    next = te->next;
    free(te->key);
    free(te->val);
    free(te);
    te = next;
}
\$\endgroup\$
  • \$\begingroup\$ On no. 5, about including the pointer in the type definition, I actually think it's bad practice to hide the pointer in the type. The rest are definitely things I will consider. \$\endgroup\$ – David Tran Sep 19 '17 at 11:13
  • \$\begingroup\$ Also, how can I avoid memory leakage from strdup()? I already error-check for NULL, how am I supposed to free the pointer if strdup() returns NULL? \$\endgroup\$ – David Tran Sep 19 '17 at 11:22
  • \$\begingroup\$ The problem is that you have three allocations, but if strdup returns NULL you immediately return NULL. This means, if strdup failed on your third alloc, you are leaking the first two allocations. You need to free the entry and any allocated elements - call te_free, except that has bugs in it, too. So rewrite te_free and call that if strdup fails in te_new. \$\endgroup\$ – Austin Hastings Sep 19 '17 at 12:56
  • \$\begingroup\$ What bugs do te_free have? \$\endgroup\$ – David Tran Sep 19 '17 at 13:01
  • \$\begingroup\$ te_free never frees the te pointer. \$\endgroup\$ – Austin Hastings Sep 19 '17 at 13:12
3
\$\begingroup\$

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?
\$\endgroup\$
  • \$\begingroup\$ Thanks for the in-depth review, I understand most of it but not quite clear on the te_free() function. Why do I need to pass a pointer to the pointer? After all each use of the pointer in the function is dereferenced anyways, can't I just pass the pointer itself? \$\endgroup\$ – David Tran Sep 19 '17 at 22:30
  • 1
    \$\begingroup\$ @DavidTran, the whole point is that the pointer needs to be set to NULL inside the free method. This cannot be done if the pointer is passed by value. Remember that in C, everything is passed by value including pointers, and the value of a pointer is the memory address of the object it points to. Therefore, to set the value of a pointer (i.e. the memory address referring to the object) to NULL, one needs to change the value of the pointer and this cannot be done when it is simply passed by value to a function. We need to pass a reference to it via another pointer. \$\endgroup\$ – smac89 Sep 20 '17 at 4:40
  • \$\begingroup\$ Makes sense. Does that mean I should set all my other pointers to NULL after they've been freed as well? \$\endgroup\$ – David Tran Sep 20 '17 at 13:23
  • \$\begingroup\$ @DavidTran, as a general rule of thumb, whenever you free memory for a pointer, ensure that pointer cannot be used to modify anything at that memory address by setting the pointer value to NULL. It is just safe practice and lets you catch bugs that might eventually creep in without your knowledge. Notice how when you run that last program, it does not crash even though the pointer has been freed, but when the pointer is explicitly set to NULL (the commented code), you see the program will quickly exit when something is written to that memory. \$\endgroup\$ – smac89 Sep 20 '17 at 15:12
  • \$\begingroup\$ Very good point about TableEntry_t should not be in the hash.h file. User code does not need to see that. \$\endgroup\$ – chux Sep 20 '17 at 19:38
2
\$\begingroup\$

Hopefully new points not fully covered by the good 2 prior reviews.


1 Rather than types HashTable..., functions ht_....() and file names hash...., use a common prefix.

2 Instead of allocating to the size of a type, allocate to the size of the referenced pointer. p = malloc(sizeof *p * n). It is easier to code correctly, review and maintain.

// ht->tab = malloc(sizeof(TableEntry_t) * size)
ht->tab = malloc(sizeof *(ht->tab) * size)

3 No need for struct TableEntry definition in hash.h, just declare it and defined this private type in hash.c

// hash.h
typedef struct TableEntry TableEntry_t;

// hash.c
typedef struct TableEntry {
  struct TableEntry *next;
  char *key;
  char *val;
} TableEntry_t;

4 ht_insert() could simply return a bool to indicate success.

5 ht_resize() lacks memory allocation failure test.

6 free(NULL) is OK code. Recommend that ht_free(NULL) also follow that idiom and not seg-fault like it does now. Simple use a if (ht) { existing body }

7 Code is not tolerant of size == 0. If code had a large array of hash tables, it is easy to want those tables of minimal size (0). Then re-size once they get going.

// if ((ht = malloc(sizeof(HashTable_t))) == NULL)
if ((ht = malloc(sizeof(HashTable_t))) == NULL && size > 0)
    return NULL;

8 Weak mixing types and width - best to use size_t for array sizing/indexing.

... size_t size
// int i;
// for (i = 0; i < size; i++)
for (size_t i = 0; i < size; i++)
    ht->tab[i] = NULL;

9 I realize this is C code, yet is is not to hard to avoid C++ keywords like new. As this function is not used outside hash.c, it should be static.

// TableEntry_t *new(char *k, char *v)
static TableEntry_t *ht_new(char *k, char *v)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.