Introduction
This is my first attempt to mess with memory allocation using C and create something close to a python dictionary. Coming from a high level programming language like Python or Java, I am not really used to correctly handling low level code. I tried to follow C conventions/style but I can tell I already failed that since I lack the discipline required.
About the Implementation
This is a fixed sized hash-table combined with a linked list. So in case of a collision I just try to append a node at the same index. The methods implemented are :
hset: sets key + valuehget: gets value based on keyhdel: deletes key + value based on keydisplay: displays the whole table (mostly for debugging)
Code
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASH_TABLE_SIZE 255
#define DEBUG_HASH_INDEX 0 // for debugging with predictable indexes
typedef struct HashItem HashItem;
struct HashItem {
char * key;
char * value;
HashItem * tail;
};
void freeNode(struct HashItem * node);
void initialize_hash_table(HashItem * hash_table[]) {
for (int i=0; i<HASH_TABLE_SIZE; i++) {
hash_table[i] = NULL;
}
}
unsigned long get_hash_index(char *str) {
if (DEBUG_HASH_INDEX) return 4; // https://xkcd.com/221/
// http://www.cse.yorku.ca/~oz/hash.html
unsigned long hash = 5381;
int c;
while ((c = *str++))
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash % HASH_TABLE_SIZE;
}
char * hget(HashItem * hash_table[], char * key) {
unsigned long idx = get_hash_index(key);
struct HashItem * node = hash_table[idx];
while (node != NULL) {
if (strcmp(key, node->key) == 0){
// if it has the same key we update the value
return node->value;
}
node = node->tail;
}
return NULL;
}
void Hdel(HashItem * hash_table[], char * key) {
unsigned long idx = get_hash_index(key);
struct HashItem * head = hash_table[idx];
if (strcmp(key, head->key) == 0){
// if it has the same key we update the value
if (head->tail != NULL){
hash_table[idx] = head->tail;
} else {
hash_table[idx] = NULL;
}
freeNode(head);
return;
}
}
void hset(HashItem * hash_table[], char * key, char * value) {
unsigned long idx = get_hash_index(key);
if (hash_table[idx] == NULL) {
// idx is empty
struct HashItem * new_pair = (struct HashItem*) malloc(sizeof(HashItem));
new_pair->key = key;
new_pair->value = value;
new_pair->tail = NULL;
hash_table[idx] = new_pair;
} else {
// idx is not empty
if (strcmp(key, hash_table[idx]->key) == 0){
// if it has the same key we update the value
hash_table[idx]->value = value;
} else {
// we insert it in the tail
struct HashItem * node = hash_table[idx];
while (1) {
if (node->tail == NULL) {
struct HashItem * new_pair = (struct HashItem*) malloc(sizeof(HashItem));
new_pair->key = key;
new_pair->value = value;
new_pair->tail = NULL;
node->tail = new_pair;
break;
}
if (strcmp(key, node->tail->key) == 0) {
node->tail->value = value;
break;
}
node = node->tail;
} // end while
} // end else
}
}
void display(HashItem * hash_table[]) {
// displays the key/values alongside their idx
struct HashItem * node;
int inner;
for (int idx = 0; idx < HASH_TABLE_SIZE; idx++) {
if (hash_table[idx] != NULL) {
printf("DISP idx: %d/0 | key: %s | value: %s\n", idx, hash_table[idx]->key, hash_table[idx]->value);
node = hash_table[idx]->tail;
inner = 1;
while (node != NULL) {
printf("DISP idx: %d/%d | key: %s | value: %s\n", idx, inner, node->key, node->value);
inner++;
node = node->tail;
}
}
}
}
void freeNode(struct HashItem * node) {
free(node->key);
free(node->value);
free(node);
node = NULL;
}
void freeInnerNodes(struct HashItem * node) {
if (node == NULL) return;
if (node->tail != NULL) freeInnerNodes(node->tail);
printf("FREE | key: %s | value: %s\n", node->key, node->value);
freeNode(node);
}
void freeHashTable(HashItem * hash_table[]) {
for (int idx = 0; idx < HASH_TABLE_SIZE; idx++) {
if (hash_table[idx] != NULL) {
freeInnerNodes(hash_table[idx]);
}
}
}
static char *rand_string(char *str, size_t size) {
const char charset[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJK...";
if (size) {
--size;
for (size_t n = 0; n < size; n++) {
int key = rand() % (int) (sizeof charset - 1);
str[n] = charset[key];
}
str[size] = '\0';
}
return str;
}
char* rand_string_alloc(size_t size) {
char *s = malloc(size + 1);
if (s) {
rand_string(s, size);
}
return s;
}
int main() {
struct HashItem* HASH_TABLE[HASH_TABLE_SIZE];
char * randkey = rand_string_alloc(12);
initialize_hash_table(HASH_TABLE);
hset(HASH_TABLE, randkey, rand_string_alloc(12));
for (int i = 0; i < 5; i++) {
hset(HASH_TABLE, rand_string_alloc(12), rand_string_alloc(12));
}
display(HASH_TABLE);
Hdel(HASH_TABLE, randkey);
display(HASH_TABLE);
freeHashTable(HASH_TABLE);
return 0;
}
