website

hash_table.c (4753B)

---

 /* hash_table.c */
 #include <stdlib.h>
 #include <string.h>
 #include <stdio.h>
 #include "hash_table.h"
 
 /* Hash Table Data Structure */
 struct hash_table {
     struct hash_table_entry **entries;
     int size;
     hash_table_cmp_fn cmp;
     hash_table_hash_fn hash;
     hash_table_dtor dtor;
 };
 
 /* Hash Table Entry Data Structure */
 struct hash_table_entry {
     void *key;
     void *value;
     struct hash_table_entry *next;
 };
 
 
 hash_table_t *hash_table_create(int size, hash_table_cmp_fn cmp, hash_table_hash_fn hash, hash_table_dtor dtor) {
     /* Allocate and Initialize Hash Table */
     hash_table_t *table = malloc(sizeof(struct hash_table));
     if (!table) {
         fprintf(stderr, "Error: Out of memory, could not allocate hash table\n");
         exit(EXIT_FAILURE);
     }
     table->entries = calloc(size, sizeof(struct hash_table_entry *));
     if (!table->entries) {
         fprintf(stderr, "Error: Out of memory, could not allocate hash table entries\n");
         free(table);
         exit(EXIT_FAILURE);
     }
     table->size = size;
     table->cmp = cmp;
     table->hash = hash;
     table->dtor = dtor;
 
     return table;
 }
 
 void hash_table_destroy(hash_table_t *table) {
     if (!table) return;
     /* Destroy Entries */
     for (int i = 0; i < table->size; i++) {
         struct hash_table_entry *entry = table->entries[i];
         while (entry) {
             struct hash_table_entry *next = entry->next;
             if (table->dtor) {
                 table->dtor(entry->key, 1);
                 table->dtor(entry->value, 0);
             }
             free(entry);
             entry = next;
         }
     }
 
     free(table->entries);
     free(table);
 }
 
 void *hash_table_get(const hash_table_t *table, const void *key) {
     if (!table || !key) return NULL;
     /* Get Entry By Hash */
     unsigned int hash = table->hash(key) % table->size;
     struct hash_table_entry *entry = table->entries[hash];
 
     /* Loop Through Entries and Return Value if Match */
     while (entry) {
         if (table->cmp(entry->key, key) == 0) {
             return entry->value;
         }
         entry = entry->next;
     }
 
     return NULL;
 }
 
 void hash_table_put(hash_table_t *table, void *key, void *value) {
     if (!table || !key) return;
     /* Get Entry By Hash */
     unsigned int hash = table->hash(key) % table->size;
     struct hash_table_entry *entry = table->entries[hash];
 
     /* Loop Through Entries and Replace Value if Key Matches */
     while (entry) {
         if (table->cmp(entry->key, key) == 0) {
             if (table->dtor) table->dtor(entry->value, 0);
             entry->value = value;
             return;
         }
         entry = entry->next;
     }
 
     /* Allocate New Entry if No Match */
     struct hash_table_entry *new_entry = malloc(sizeof(struct hash_table_entry));
     if (!new_entry) {
         fprintf(stderr, "Error: Out of memory, could not allocate hash table entry\n");
         exit(EXIT_FAILURE);
     }
     new_entry->key = key;
     new_entry->value = value;
     new_entry->next = table->entries[hash];
     table->entries[hash] = new_entry;
 
 }
 
 void hash_table_remove(hash_table_t *table, const void *key) {
     if (!table || !key) return;
     /* Get Entry By Hash */
     unsigned int hash = table->hash(key) % table->size;
     struct hash_table_entry *entry = table->entries[hash];
 
     /* Loop Through Entries and Remove Entry if Key Matches */
     struct hash_table_entry *prev = NULL;
     while (entry) {
         if (table->cmp(entry->key, key) == 0) {
             if (prev)
                 prev->next = entry->next;
             else
                 table->entries[hash] = entry->next;
             
             if (table->dtor) {
                 table->dtor(entry->key, 1);
                 table->dtor(entry->value, 0);
             }
             free(entry);
             return;
         }
         prev = entry;
         entry = entry->next;
     }
 
 }
 
 #ifdef TEST_HASH_TABLE
 #include <assert.h>
 
 static int string_cmp(const void *key1, const void *key2) {
     return strcmp((const char *)key1, (const char *)key2);
 }
 
 static unsigned int string_hash(const void *key) {
     unsigned int hash = 5381;
     const unsigned char *str = key;
     int c;
 
     while ((c = *str++))
     {
         hash = ((hash << 5) + hash) + c;
     }
 
     return hash;
 }
 
 int main(void) {
     hash_table_t *table = hash_table_create(16, string_cmp, string_hash, NULL);
     assert(table != NULL);
 
     hash_table_put(table, "foo", "bar");
     hash_table_put(table, "foo", "baz");
     assert(strcmp((const char *)hash_table_get(table, "foo"), "baz") == 0);
 
     hash_table_remove(table, "foo");
     assert(hash_table_get(table, "foo") == NULL);
 
     hash_table_destroy(table);
     printf("All tests passed!\n");
     return 0;
 }
 #endif