Hash table OOP implementation in C

Question

To brush up my C I decided to do some OOP programming in C. I have never tested this before, but I was curious to try it since seeing an example of it a while ago. I decided to implement a simple hash table. My first approach was to give each instance of the object its own methods, i.e. pointers to functions, but this felt meaningless because they could not be used for more than shared state (without giving the methods a self reference). Instead I decided that each "object" should only hold the private state and use normal functions.

Here follows a usage of the "class", main.c:

#include <stdio.h>
#include "hashtable.h"

int main(int argc, char *argv[]) {

    HashTable ht = newHashTable(65535);

    HashTable_put(ht, "1", "two");
    HashTable_put(ht, "2", "three");
    HashTable_put(ht, "3", "five");
    HashTable_put(ht, "4", "seven");
    HashTable_put(ht, "5", "eleven");
    HashTable_put(ht, "6", "thirteen");
    HashTable_put(ht, "7", "seventeen");

    HashTable_remove(ht, "1");
    HashTable_remove(ht, "2");
    HashTable_remove(ht, "6");
    HashTable_remove(ht, "7");

    HashTable_put(ht, "3", "not allowed");

    printf("%s\n", HashTable_get(ht, "1"));
    printf("%s\n", HashTable_get(ht, "2"));
    printf("%s\n", HashTable_get(ht, "3"));
    printf("%s\n", HashTable_get(ht, "4"));
    printf("%s\n", HashTable_get(ht, "5"));
    printf("%s\n", HashTable_get(ht, "6"));
    printf("%s\n", HashTable_get(ht, "7"));

    printf("size: %d\n", HashTable_size(ht));   

    freeHashTable(&ht);

    return 0;
}

And the header hashtable.h:

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include <stdbool.h>

typedef struct hashtable *HashTable;

// Create, destory
HashTable newHashTable(int);
void freeHashTable(HashTable *);

// Public methods
int HashTable_buckets(HashTable);
const char *HashTable_get(HashTable, char *);
bool HashTable_put(HashTable, char *, char *);
bool HashTable_remove(HashTable, char *);
int HashTable_size(HashTable);

#endif

And lastly the actual implementation, i.e. hashtable.c:

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

struct entry {
    char *key;
    char *value;
    struct entry *next;
};

struct hashtable {
    int buckets;
    int size;
    struct entry **table;
};

typedef struct entry *Entry;

static unsigned long djb2_hash(char *);
static void free_bucket(Entry *);
static void free_entry(Entry *);

//-----------------------------------------------------------------------------
// Create, destory
//-----------------------------------------------------------------------------

HashTable newHashTable(int buckets) {
    HashTable ht = malloc(sizeof(struct hashtable));
    ht->table = malloc(buckets * sizeof(struct entry *));
    for (int i = 0; i < buckets; i++) {
        ht->table[i] = NULL;
    }
    ht->buckets = buckets;
    ht->size = 0;
    return ht;
}

void freeHashTable(HashTable *thisPtr) {
    for (int i = 0; i < (*thisPtr)->buckets; i++) {
        free_bucket(&(*thisPtr)->table[i]);
    }
    free((*thisPtr)->table);
    (*thisPtr)->table = NULL;
    free(*thisPtr);
    *thisPtr = NULL;
}

//-----------------------------------------------------------------------------
// Public methods
//-----------------------------------------------------------------------------

int HashTable_buckets(HashTable this) {
    return this->buckets;
}

const char *HashTable_get(HashTable this, char *key) {
    Entry e;
    int b = djb2_hash(key) % this->buckets;
    for (e = this->table[b]; e != NULL; e = e->next) {
        if (strcmp(e->key, key) == 0) {
            return e->value;
        }
    }
    return NULL;
}

bool HashTable_put(HashTable this, char *key, char *value) {
    Entry *ePtr;
    int b = djb2_hash(key) % this->buckets;
    for (ePtr = &this->table[b]; *ePtr != NULL; ePtr = &(*ePtr)->next) {
        if (strcmp((*ePtr)->key, key) == 0) {
            return false;
        }
    }
    *ePtr = malloc(sizeof(struct entry));
    (*ePtr)->key = strdup(key);
    (*ePtr)->value = strdup(value);
    (*ePtr)->next = NULL;
    this->size++;
    return true;
}

bool HashTable_remove(HashTable this, char *key) {
    Entry *ePtr, next;
    int b = djb2_hash(key) % this->buckets;
    for (ePtr = &this->table[b]; *ePtr != NULL; ePtr = &(*ePtr)->next) {
        if (strcmp((*ePtr)->key, key) == 0) {
            next = (*ePtr)->next;
            free_entry(ePtr);
            *ePtr = next;
            this->size--;
            return true;
        }
    }
    return false;
}

int HashTable_size(HashTable this) {
    return this->size;
}

//-----------------------------------------------------------------------------
// Private methods
//-----------------------------------------------------------------------------

static unsigned long djb2_hash(char *str) {
    unsigned long hash = 5381;
    unsigned char c;
    while ((c = *str++) != '\0') {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash;
}

static void free_bucket(Entry *ePtr) {
    if (*ePtr == NULL) {
        return;
    }
    free_bucket(&(*ePtr)->next);
    free_entry(ePtr);
}

static void free_entry(Entry *ePtr) {
    free((*ePtr)->key);
    free((*ePtr)->value);
    (*ePtr)->key = NULL;
    (*ePtr)->value = NULL;
    free(*ePtr);
    *ePtr = NULL;
}

Each hash table bucket, that is the content of table, is a pointer to its first entry (or NULL), and if more entries in a bucket they are chained as a linked list with a pointer in each entry to the next entry.

As you can see I tried to encapsulate the data field as much as possible. It would be very nice to get feedback on anything. I struggled some to get the freeing right, have only used malloc one time before, I have mostly done simple embedded programming in C before. I also put in effort to make the functions as concise as possible. Is this a good OOP implementation with C? Are there any other issues? If you want to run the code its available here with a compilation script. I'm aware of that it would be better if the the number of buckets was dynamic, so you could leave that feedback out.

Answer 1

1. Recommend to include "hashtable.h" in "hashtable.c" first as a test to insure "hashtable.h" does not rely on the .c file to include .h files prior.

   #include "hashtable.h"
   #include <stdio.h>
   #include <stdlib.h>
   #include <string.h>
   // #include "hashtable.h"
   

2. Really not a fan of using typedef to hide a pointer. In the end this is a style decision. In my experience, hidden pointer types are harder to debug as they tend to be surprising.

   // typedef struct hashtable *HashTable;
   typedef struct hashtable HashTable;
   
   // const char *HashTable_get(HashTable, char *);
   const char *HashTable_get(HashTable *, char *);
   

3. Naming convention inconsistency. Suggest below (spacing added for clarity here, not needed for code.)

   // HashTable newHashTable(int);
   // void      freeHashTable(HashTable *);
   HashTable    HashTable_new(int);
   void         HashTable_free(HashTable *);
   
   int          HashTable_buckets(HashTable);
   const char * HashTable_get(HashTable, char *);
   bool         HashTable_put(HashTable, char *, char *);
   

4. Use type size_t to index arrays. It really is the best type for arrays being not too wide nor too narrow. int may be insufficient.

   struct hashtable {
       // int buckets;
       // int size;
       size_t buckets;
       size_t size;
       struct entry **table;
   };
   

5. Functions that do not modify the "pointed to" data, should use const

   // int HashTable_size(HashTable);
   int HashTable_size(const HashTable);
   
   // or including above ideas
   size_t HashTable_size(const *HashTable);
   // bool HashTable_put(HashTable this, char *key, char *value)
   bool HashTable_put(const *HashTable this, const char *key, const char *value)
   

6. OP all ready knows "would be better if the the number of buckets was dynamic,". It is important to add that making the bucket size a prime number has performance benefits in that a prime makes a weak pre-hash function better.

7. Rather than allocate the size of a type, allocate to the size of the pointer's reference type. It is easier to maintain and less likely to be wrong.

   // ht = malloc(sizeof(struct hashtable));
   ht = malloc(sizeof *ht);
   

8. Check range of values, especially during debug. Consider debugging code where newHashTable(0) invoked a %0 in a latter call HashTable_get(). Another approach is preemptively adjust buckets

   HashTable newHashTable(int buckets) {
     assert(buckets > 0);
     // or 
     if (buckets <= 0) buckets = 1;
     ...
     ht->buckets = buckets;
   
   ...
   djb2_hash(key) % this->buckets;  // prevent % 0
   

9. Missing test. Tests never try a failed get().

   printf("%p\n", (void*) HashTable_get(ht, "x"));
   

10. I reserve C++ keywords in C. From time to time, it is useful to port C code to C++

    // HashTable this
    HashTable This
    

11. IMO, free_like() functions should be NULL tolerant like free(NULL). It does not cost much and is C-like.

    void freeHashTable(HashTable *thisPtr) {
      if (thisPtr == NULL) return;
    

12. Also, IMO, use freeHashTable(HashTable thisPtr). Do not pass the HT variable address. As able, keep the similar HT function signatures using the HT variable in a consistent manor.

13. Naming convention: filenames should match the case of the type, as able. IOWs HashTable.c and HashTable.h

14. No need to declare a variable until it is needed.

    // Entry next;
    ...
            // next = (*ePtr)->next;
            Entry next = (*ePtr)->next;
    

15. Design: "I also put in effort to make the functions as concise as possible." is a worthy goal, but the conciseness and cohesiveness of the functions/type declarations in the .h file trumps the implementation details - that is good OOP.

16. Hash performance. I see value in widening the pre-hash function to long long at little cost. If long long is a high cost, then code should use size_t, rather than unsigned long. Suggest *33 rather than ((hash << 5) + hash). Let the compiler optimize.

    static unsigned long long djb2_hash(char *str) {
      unsigned long long hash = 5381;
      unsigned char c;
      while ((c = *str++) != '\0') {
        hash = hash*33 + c;
      }
      return hash;
    }
    

Answer 2

Unnecessary recursion

I feel that free_bucket() should be made iterative instead of recursive. The problem with it being recursive is that the length of the list being freed is unbounded. So for example if you had 1 million entries in the list, you could end up overflowing your stack by recursing 1 million times. It is simple enough to use a for loop like the one in HashTable_remove() to do the same thing.