5
\$\begingroup\$

To gain a broader insight in things many (high-level language) programmers nowadays take for granted, I decided to study some of the more basic ways of storing data in memory. I wrote a program which stores dynamic sized (integer) arrays in a chained hash table. A possible application could be the indexing of lines on which words appear in a given text file to be parsed (I could then 'ask' the program on which lines, f.e. the word 'banana' appears in the parsed text). I designed the program so that I can pass different hash functions and compare their performance later on.

Anyway, my code is working perfectly as I want it to. However, I feel like it's necessary to get fundamental data structures such as hash tables and dynamic sized arrays right, so that's why I am posting my code here.

array.c

/* A dynamic array is implmented to keep track of line numbers in text. */
struct array {
    size_t size;
    size_t capacity;
    int* contents;
};


/* Initializes a dynamic array and allocates its desired memory. */
struct array* array_init(unsigned long initial_capacity) {
    struct array* a = malloc(sizeof(struct array));
    if(a == NULL) {
        // Initialization failed.
        return NULL;
    }

    a->contents = malloc(sizeof(int) * initial_capacity);

    // If initial_capacity is zero, contents would always be NULL.
    if(a->contents == NULL && initial_capacity > 0) {
        free(a);
        return NULL;
    }

    a->size = 0;
    a->capacity = initial_capacity;

    return a;
}

/* Releases memory used by given array. */
void array_cleanup(struct array *a) {
    if(a) {
        if(a->contents) {
            free(a->contents);
        }

        free(a);
    }
}

/* Returns element at given position in given array. */
int array_get(struct array *a, unsigned long index) {
    if(!a) {
        return -1;
    }
    // As an unsigned long has been given, no need to check for negatives.
    if(index > a->capacity - 1) {
        return -1;
    }

    return a->contents[index];
}

/* Appends element at given index in array after resizing array if needed. */
int array_append(struct array *a, int elem) {
    if(!a) {
        return 1;
    }

    if(a->capacity < a->size+1) {
        // Resizing array by reallocating memory for twice more values.
        if(a->capacity == 0) {
            // If array length is zero, just change capacity to one.
            a->capacity = 1;
        } else {
            // Double array size.
            a->capacity *= 2;
        }

        void *largerContents = realloc(a->contents, sizeof(int) * a->capacity);
        if(largerContents == NULL) {
            return 1;
        }

        a->contents = largerContents;
    }

    a->contents[a->size] = elem;
    a->size++;
    return 0;
}

/* Returns number of elements currently stored in given array. */
unsigned long array_size(struct array *a) {
    return a->size;
}

hash_table.c

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

#include "hash_table.h"
#include "array.h"

/* Table structure used to store relevant data for a hash table. */
struct table {
    // The (simple) array used to index the table
    struct node **array;
    // The function used for computing the hash values in this table
    unsigned long (*hash_func)(unsigned char *);
    // Maximum load factor after which the table array should be resized
    double max_load;
    // Capacity of the array used to index the table
    unsigned long capacity;
    // Current number of elements stored in the table
    unsigned long load;
};

/* Node structure used by elements of chain in hash table entries. */
struct node {
    // The string of characters that is the key for this node
    char *key;
    // A resizing array, containing the all the integer values for this key
    struct array *value;
    // Next pointer
    struct node *next;
};

/* Initializes hash table and returns the pointer, returns NULL on failure. */
struct table *table_init(unsigned long capacity, double max_load,
                            unsigned long (*hash_func)(unsigned char *)) {
    if(max_load <= 0) {
        return NULL;
    }

    struct table* t = malloc(sizeof(struct table));
    if(t == NULL) {
        // Initialization failed.
        return NULL;
    }

    t->array = (struct node**) malloc(sizeof(struct node*) * capacity);

    if(t->array == NULL) {
        free(t);
        return NULL;
    }

    for(int i=0;i<(int) capacity;i++) {
        t->array[i] = NULL;
    }

    t->max_load = max_load;
    t->capacity = capacity;
    t->hash_func = hash_func;
    t->load = 0;

    return t;
}

/* Walks through given linked list (chain) and returns dynamic array of
   integers upon finding correct key. Returns NULL otherwise. */
struct array *chain_find_value(struct node *n, char *key) {
    if(!n) {
        return NULL;
    }

    // If while statement is true, strings are NOT identical.
    while(strcmp(n->key, key)) {
        if(n->next) {
            n = n->next;
        } else {
            return NULL;
        }
    }

    return n->value;
}

/* Walks through given linked list (chain) and returns node before
   the node associated with a given key using a given node. Returns
   actual node if first node in list. */
struct node *chain_find_keynode(struct node *n, char *key) {
    if(!n) {
        return NULL;
    }

    if(!strcmp(n->key, key)) {
        // Returns actual node associated with key.
        return n;
    }

    struct node *oldNode;

    while(strcmp(n->key, key)) {
        if(n->next) {
            oldNode = n;
            n = n->next;
        } else {
            return NULL;
        }
    }

    return oldNode;
}

/* Returns a pointer to the last linked node of a given node. */
struct node *last_node(struct node *n) {
    if(!n) {
        return NULL;
    }

    while(n->next) {
        n = n->next;
    }

    return n;
}

/* Returns current average load of hash table. */
double current_load(struct table *t) {
    return (double) t->load/(double) t->capacity;
}

/* Adds a node to the chain of a table entry, returns the pointer. */
struct node *init_node(char *key, int value) {
    struct node *n = malloc(sizeof(struct node));
    if(!n) {
        return NULL;
    }

    struct array *array = array_init(1);
    if(array_append(array, value) == 1) {
        return NULL;
    }

    n->key = malloc(sizeof(char) * (strlen(key) + 1));
    if(!n->key) {
        free(n);
        return NULL;
    }
    memcpy(n->key, key, sizeof(char) * (strlen(key) + 1));

    //n->key = keyDup;
    n->value = array;
    n->next = NULL;

    return n;
}

/* Calculates array key and links node to chain. */
int link_node(struct node **a, unsigned long capacity, char *key, int value,
                unsigned long (*hash_func)(unsigned char *)) {
    unsigned long nodesArrayKey = hash_func((unsigned char*) key) % capacity;
    struct node *firstNode = a[nodesArrayKey];

    if(firstNode) {
        struct array *array = chain_find_value(firstNode, key);

        if(array) {
            // Key already exists, append value to array
            array_append(array, value);
        } else {
            struct node *lastNode = last_node(firstNode);
            struct node *newNode = init_node(key, value);

            if(!newNode)
            {
                return 1;
            }

            lastNode->next = newNode;
        }
    } else {
        struct node *newNode = init_node(key, value);

        if(!newNode)
        {
            return 1;
        }

        a[nodesArrayKey] = newNode;
    }

    return 0;
}

/* Rehashes all values in hash table. */
void resize_table(struct table *t) {
    unsigned long oldCapacity = t->capacity;
    struct node **newArray;

    if(t->capacity == 0) {
        t->capacity = 1;
    } else {
        t->capacity *= 2;
    }

    newArray = (struct node**) malloc(sizeof(struct node*) * t->capacity);
    if(newArray == NULL) {
        return;
    }

    for(int k=0;k<(int) t->capacity;k++) {
        newArray[k] = NULL;
    }


    // Re-arranging old values
    for(unsigned long i=0;i<oldCapacity;i++) {
        struct node *n = t->array[i];
        struct node *nodeToDelete;

        // Traversing through whole linked list
        while(n) {
            nodeToDelete = n;

            for(unsigned long j=0;j<array_size(n->value);j++) {
                link_node(newArray, t->capacity, n->key,
                            array_get(n->value, j), t->hash_func);
            }

            array_cleanup(n->value);
            n = n->next;
            free(nodeToDelete->key);
            free(nodeToDelete);
        }
    }

    free(t->array);
    t->array = newArray;
}

/* Inserts a given pair of key and value in a given hash table. Keeps
   table load below or equal to max load of table. */
int table_insert(struct table *t, char *key, int value) {
    if(!t) {
        return 1;
    }

    if(current_load(t) >= t->max_load) {
        // Resizing hash table first, to reduce load.
        resize_table(t);
    }

    link_node(t->array, t->capacity, key, value, t->hash_func);

    t->load++;

    return 0;
}

/* Returns the array of all inserted integer values for the specified key. 
   Returns NULL if the key is not present in the table. */
struct array *table_lookup(struct table *t, char *key) {
    if(!t) {
        return NULL;
    }

    unsigned long nodesArrayKey = t->hash_func((unsigned char*) key) % t->capacity;

    return chain_find_value(t->array[nodesArrayKey], key);
}

/* Deletes key-entry from hash table. */
int table_delete(struct table *t, char *key) {
    if(!t) {
        return 1;
    }

    unsigned long nodesArrayKey = t->hash_func((unsigned char*) key) % t->capacity;
    struct node *firstNode = t->array[nodesArrayKey];

    if(!firstNode) {
        return 1;
    }

    struct node *impactNode = chain_find_keynode(firstNode, key);
    if(!impactNode) {
        return 1;
    }

    if(!strcmp(impactNode->key, key)) {
        // Node is the first element in linked list.
        if(impactNode->next) {
            t->array[nodesArrayKey] = impactNode->next;
        } else {
            t->array[nodesArrayKey] = NULL;
        }

        array_cleanup(impactNode->value);
        free(impactNode->key);
        free(impactNode);
    } else {
        struct node *nodeToDelete = impactNode->next;
        if(nodeToDelete->next) {
            impactNode->next = nodeToDelete->next;
        } else {
            impactNode->next = NULL;
        }

        array_cleanup(nodeToDelete->value);
        free(nodeToDelete->key);
        free(nodeToDelete);
    }

    return 0;
}

/* Cleans up hash-table associated memory. */
void table_cleanup(struct table *t) {
    for(unsigned long i=0;i<t->capacity;i++) {
        if(t->array[i]) {
            struct node *n = t->array[i];
            struct node *nodeToDelete;

            // Traversing through linked list.
            while(n) {
                nodeToDelete = n;
                array_cleanup(n->value);
                n = n->next;
                free(nodeToDelete->key);
                free(nodeToDelete);
            }
        }
    }

    free(t->array);
    free(t);
}

Extreme thanks to anyone interested in reviewing this piece of code for me.

\$\endgroup\$
  • \$\begingroup\$ Damiaan, welcome to Codereview. Looks like good code, for something like this a little example or some test code is always helpful to get people started. You do have test code ? ;) \$\endgroup\$ – Harald Scheirich Apr 16 at 12:41
3
\$\begingroup\$

This is a noble goal -- you will learn (and perhaps already have learned) a lot about higher level languages by diving a layer deeper.

Here are my thoughts as I read your code. I hope you don't mind my stream of consciousness format.

Project Layout

  • Did you put the declarations in headers? It's definitely a good idea. I don't see any includes, so I'm a bit suspicious. Also, headers have a lot of gotchas, so it might be good to review them.

Struct Declaration

  • Why not typedef struct { ... } array? I think that makes types easier to work with.

  • How about changing the name contents to data? I think this would make your naming more consistent with C++ vector. This would satisfy the principle of least surprise in my subjective opinion.

  • In C, it is sometimes helpful to store void* as your datatype. That way, users can store simple types (like ints) in the void*, but they can also store pointers to larger types. This allows composition e.g. storing an array of arrays. But this can be trickier for the users.

  • Your comment is about a use case rather than what is going on. I think you don't really need a comment at all. At most, you might say // currently used in line_number.c - Damiaan, 21/4/2019.

  • (nitpick) Put the data first. If data is first, and I want to get the 5th element from an array *a, then all the compiler needs to do is dereference and add. Otherwise, it has to add, dereference, and add again. Probably size should be next and then capacity following the general guideline that frequently used items should go first.

array_init

  • initial_capacity should be size_t (and const).

  • Always cast the return value of malloc before assignment. That way, you'll get a compiler warning if you mess up (or at least, you have a shot at getting a warning). It looks OK here, but it's a good habit to get into.

  • I would have expected array_init to take a pointer as its first argument. That way the caller can choose where the array struct lives. I think the caller should be able to do that, since after all, the caller owns the array and is responsible for keeping it between calls to your API. Also, that frees up the return value to potentially have more specific information. This is contentious though -- many C libraries do what you've done.

  • "If initial_capacity is zero, contents would always be NULL." This is not guaranteed. It's implementation defined. I don't think this would cause any problems for your code, but the comment is misleading.

  • Functions that do multiple allocations in C are really easy to get wrong. One common pattern is to use a goto chain. Declare your variables at the top of the function, then list their cleanups in the reverse order that you initialize. On each failure, goto the cleanup after the one for the variable that failed. e.g.

    T *a, *b;
    
    if (NULL == (a = (T*)malloc(sizeof(T)))) { goto failure_a; }
    if (NULL == (b = (T*)malloc(sizeof(T)))) { goto failure_b; }
    
    ...
    
    free(b);
    
    failure_b:
    free(a);
    
    failure_a:
    
    return 1;
    

The advantage of a goto chain is that you don't have to repeate the cleanups at each possible failure. It can make a big difference when you have lots of initializations.

Another tip -- in C, return is often the cause of bugs. This is especially true for ex-C++/similar programmers who expect cleanup to be automatic. A nice feature of the goto chain is it minimizes the number of return statements to think about.

array_cleanup

  • I know free accepts NULL, but that's not always the best route. I would assert(a). Other examples of cleanup functions that don't have to do null checks are pthread_mutex_destroy and fclose. In general in C, there is a philosophy that the programmer is right and the computer will do what s/he says or die trying. So if the programmer says array_cleanup, then do your darnest to cleanup the array.

  • if (a->contents) is superfluous as free checks that anyway.

  • I know what you mean by the init/cleanup naming convention, but I prefer init/destroy (as in pthread_mutex_[init|destroy]) or create/destroy. cleanup doesn't imply destroy to me -- I may want to cleanup a memory arena for example, but that doesn't mean I'm done using it.

array_get

  • The array could be const. If not, I would expect the return the value to be something mutable like a ptr to a value.

  • index should be size_t const.

  • It's completely horrible to return -1. What if the element I stored is -1? Are you saying I cannot store -1, but I should pass an int? This needs to change. One option is errno. Another option is returning the element by ptr.

  • The NULL checks... again, I would assert.

  • index > a->capacity - 1 should be !(index < a->capacity) IMO. In my personal style, I like to say if (!(...)) when checking if something went wrong. That way, (...) is the condition I want to be true. This is just a personal preference though. Also, it's bad practice to compare different types, so be sure to make them both size_t.

  • You could make the capacity check an assertion too. If you make both of these checks into assertions, then the whole function will turn into just one instruction when compiled without assertions. This means you'll be quicker. Also, you won't have those nasty return -1s.

array_append

  • elem should be const.

  • The NULL check could be an assert.

  • Why does array_append return 1 for an error but array_get returns -1? Either get serious and return specific error codes, or always return the same value. Fix array_get first, then see whether this still needs to change.

  • In this function, there is the concept of an old size and a new size. I think it would be clearer to make newsize a variable, and then at the end set size = newsize; currently, you increment size in two places.

  • Like malloc, you should cast the return value of realloc before assignment. But it looks like you called it correctly -- nice job. Many beginners do p = realloc(p, size) which is a mistake.

  • In array_init and here in array_append, you have special cases for 0 == capacity. However, a zero capacity array is pretty useless. I propose that you assert(0 < capacity) in array_init and in array_append. Then it's the caller's responsibility to ensure that the array is allowed to have more tan 0 elements. As a side note, since you don't do anything like SSO, maybe you should have a higher minimum capcacity... e.g. 4 or 8? That way you avoid reallocing so often for small arrays. Would depend on benchmarks.

  • You might consider growing by 1.5 instead of 2. This is highly contentious but worth looking into: https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md. Again, benchmark.

array_size

  • The array should be const.

  • This function should return size_t.

Overall

  • What about array_set? array_erase? array_insert? If you wanted a more generally applicable array, then you should implement those (and more). But perhaps YAGNI.

  • This is very similar to a C++ vector. Perhaps because I often write C++, I think of vectors as variable sized arrays and of arrays as fixed size vectors. That's at least on reason to rename this to vector. Maybe you have other reasons to use array.

  • I didn't compile or test this, but it looks solid. Nice job.

  • For fun, you might try adding small value optimization. This would take care of your zero capacity issue and also speed up growth for very small arrays.

struct table

  • The name table is not specific enough. A table could be so many things. It could be a 3D object representing a dinner table. Or a lookup table. Or a timetable.

  • Again, typedef struct?

  • Why not declare node before table?

  • In an ideal world, hashtables wouldn't have hash functions or load factors. Therefore, unless you have a good reason to do otherwise, do not force users to customize the hash function or the load factor. Maybe don't allow users to customize these at all. This change will clarify your levels of abstraction, make your type smaller, and simplify the interface. Big wins.

It would be a different story if your hashtable supported different multiple types. Then you would need to pass in a hash function.

  • load should be called size.

  • Why are load and capacity unsigned long? size_t was the right type.

  • The comments here are clutter. It took me < 1s to read your struct array, but here I had to read every word.

    typedef struct {
        struct node** data;
        size_t size;
        size_t capacity;
    } hashtable;
    

So much simpler!

  • I guess you are using chaining to solve collisions? that might be worth commenting in the table. Otherwise I would expect node* instead of node**.

  • Note that if your array stored void* and your hashtable did linear probing, then you could have reused your array for the hash table and simply changed the interface functions. You might have needed to implement more function in the array, but so be it.

    typedef array_t hashtable_t;
    

Even simpler! But you'd want to comment about linear probing. This would be a big win because you wouldn't need to reimplement so much stuff.

  • As I read through the implementation, I realized this is really a map of keys to sets of values. I did not expect that, and I think it should be commented. I usually expect a hashtable to map each key to a single value. If I want multiple values, then I would expect to store a set as the value (which I might be able to do if the value were a void*).

The rest

  • A lot of the comments from the array also apply to the hash function (e.g. assert instead of if, use goto chains for complex failures, etc.).

  • This is getting long, so I'm going to sign off. Perhaps another user will finish the review.

  • You might enjoy reading this style guide: https://wiki.sei.cmu.edu/confluence/display/c/SEI+CERT+C+Coding+Standard

  • glib has these data structures (and many more) e.g. https://developer.gnome.org/glib/2.60/glib-Hash-Tables.html. Note that they agree with your implementation in a few key (pun intended) places e.g. passing the hash function to the constructor and returning a pointer from the creation routine. However, their hashtable operates on void* key and void* value, so they are more generic solutions. It's a shame the compiler cannot inline/remove these values even though it knows they will never change.

\$\endgroup\$
  • \$\begingroup\$ I extremely appreciate how you contributed so extensively. This is really helpful. A thousand times thanks! Just to comment on my strange error handling: since I wrote this specifically for storing (positive) integers which correspond to line numbers in a text (which can never be negative), I decided to return "-1" on array_get (for example), since then I would know it's an error and not a "real" return value. But you're right, it's better to make it more generally applicable. \$\endgroup\$ – Damiaan Reijnaers Apr 23 at 13:08
  • 1
    \$\begingroup\$ I'm glad it is helpful! next time you do something like that, you should comment gratuitously. or just dont do it \$\endgroup\$ – sudo rm -rf slash Apr 23 at 14:10
3
\$\begingroup\$

Performance improvement

A key attribute concerning hashing, capacity and doubling the table size *= 2: primes

The hash table index calculation has 2 stages: hash_func() and % capacity.

A poor or modest hash_func() is improved when modded by a prime. A prime will not harm a good hash function. Modding by a power-of-2 is the worst as it simply becomes a bit mask discarding many distinguishing bits from hash_func().

Better to use capacities that are primes in the % step.

Instead of capacity *= 2, form a table of "primes" just under a power of 2: static const size_t capacity[] = 0,1,3,7,13,31,61, ... near SIZE_MAX;.

Use a member .capacity index into that table and increment as needed.

struct array {
    size_t size;
    unsigned char capacity_index;  // Or some small type.
    int* contents;
};
\$\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.