Created
January 17, 2021 03:03
-
-
Save oschonrock/d0540347a5a6739a24c4648e724a3e96 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdbool.h> | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
typedef char* ht_key_t; | |
typedef int ht_value_t; | |
// key => value plus pointer to next item for hash collisions | |
typedef struct HashTableItem HashTableItem; | |
struct HashTableItem { | |
ht_key_t key; | |
ht_value_t value; | |
HashTableItem* next; | |
}; | |
// Contains an array of pointers to HashTableItems | |
typedef struct HashTable { | |
HashTableItem** items; | |
size_t size; | |
size_t count; // could be used for rehashing in future | |
} HashTable; | |
// Creates a pointer to a new hash table item | |
HashTableItem* ht_create_item(ht_key_t key, ht_value_t value) { | |
HashTableItem* item = malloc(sizeof *item); | |
item->key = strdup(key); | |
item->value = value; | |
item->next = NULL; | |
return item; | |
} | |
// Creates a new HashTable | |
HashTable* ht_create(size_t size) { | |
HashTable* table = malloc(sizeof *table); | |
table->size = size; | |
table->count = 0; | |
table->items = calloc(table->size, sizeof *table->items); // NOLINT sizeof ptr | |
return table; | |
} | |
// Frees an item | |
void ht_free_item(HashTableItem* item) { | |
free(item->key); | |
free(item); | |
} | |
// Frees the whole hashtable | |
void ht_free(HashTable* table) { | |
// Frees the table | |
for (size_t i = 0; i < table->size; i++) { | |
HashTableItem* item = table->items[i]; | |
while (item) { | |
HashTableItem* next = item->next; | |
ht_free_item(item); | |
item = next; | |
} | |
} | |
free(table->items); | |
free(table); | |
} | |
size_t hash_function(HashTable* table, const char* str) { | |
size_t sum = 0; | |
for (size_t j = 0; str[j]; ++j) sum += str[j]; | |
return sum % table->size; | |
} | |
// Inserts (or updates if exists) an item | |
void ht_insert(HashTable* table, ht_key_t key, ht_value_t value) { | |
HashTableItem** slot = &table->items[hash_function(table, key)]; | |
HashTableItem* item = *slot; | |
if (!item) table->count++; // HashTable accounting (while will not run) | |
while (item) { | |
if (strcmp(item->key, key) == 0) { | |
item->value = value; // exists, update value | |
return; | |
} | |
slot = &item->next; | |
item = *slot; | |
} | |
*slot = ht_create_item(key, value); | |
} | |
// Deletes an item from the table | |
void ht_delete(HashTable* table, ht_key_t key) { | |
HashTableItem** slot = &table->items[hash_function(table, key)]; | |
HashTableItem* item = *slot; | |
bool is_direct_slot = true; | |
while (item) { | |
if (strcmp(item->key, key) == 0) { | |
*slot = item->next; // remove item from linked list | |
ht_free_item(item); | |
if (is_direct_slot) --table->count; // HashTable accounting | |
return; | |
} | |
slot = &item->next; | |
item = *slot; | |
is_direct_slot = false; | |
} | |
} | |
// Searches the key in the hashtable | |
// and returns NULL if it doesn't exist | |
HashTableItem* ht_search(HashTable* table, ht_key_t key) { | |
HashTableItem* item = table->items[hash_function(table, key)]; | |
while (item) { | |
if (strcmp(item->key, key) == 0) return item; | |
item = item->next; | |
} | |
return NULL; | |
} | |
void ht_print(HashTable* table) { | |
printf("\n---- Hash Table ---\n"); | |
for (size_t i = 0; i < table->size; i++) { | |
printf("@%zu: ", i); | |
HashTableItem* item = table->items[i]; | |
while (item) { | |
printf("%s => %d | ", item->key, item->value); | |
item = item->next; | |
} | |
printf("\n"); | |
} | |
printf("-------------------\n"); | |
} | |
void ht_print_search(HashTable* table, ht_key_t key) { | |
HashTableItem* val; | |
if ((val = ht_search(table, key)) == NULL) { | |
printf("Key:%s does not exist\n", key); | |
return; | |
} | |
printf("Key:%s => %d\n", key, val->value); | |
} | |
int main() { | |
HashTable* ht = ht_create(3); | |
ht_insert(ht, "1", 10); | |
ht_insert(ht, "2", 20); | |
ht_insert(ht, "Hel3", 30); | |
ht_insert(ht, "Cau4", 40); | |
ht_insert(ht, "Cau6", 60); | |
ht_print_search(ht, "1"); | |
ht_print_search(ht, "2"); | |
ht_print_search(ht, "3"); | |
ht_print_search(ht, "Hel3"); | |
ht_print_search(ht, "Cau4"); | |
ht_insert(ht, "Cau4", 61); // update | |
ht_print_search(ht, "Cau4"); | |
ht_print(ht); | |
ht_delete(ht, "Hel3"); | |
ht_delete(ht, "Cau6"); | |
ht_delete(ht, "1"); | |
ht_print(ht); | |
ht_free(ht); | |
return 0; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thanks for your interest, there is a more up to date version here:
https://github.com/oschonrock/cproj/blob/main/src/hashtable.c