131 lines
2.7 KiB
C
131 lines
2.7 KiB
C
// implementation of a hashtable
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
#include "hashtable.h"
|
|
|
|
|
|
/**
|
|
* @brief Hash function for hashtable
|
|
*
|
|
* This function takes a string key and calculates a hash value.
|
|
* The hash value is used to determine the index in the hashtable
|
|
* where the key-value pair should be stored.
|
|
*
|
|
* @param key The string key to hash
|
|
* @return The calculated hash value
|
|
*/
|
|
static unsigned int hash(const char *key)
|
|
{
|
|
unsigned int hash = 0; // Initialize hash value to 0
|
|
|
|
// Iterate over each character in the key string
|
|
while (*key)
|
|
{
|
|
// Calculate the hash value by multiplying the current hash value
|
|
// with 32 (2^5) and subtracting the current hash value. Then add the
|
|
// ASCII value of the current character.
|
|
hash = (hash << 5) - hash + *key++;
|
|
}
|
|
|
|
// Return the calculated hash value
|
|
return hash;
|
|
}
|
|
|
|
/**
|
|
* @brief Create a new hashtable
|
|
*
|
|
* This function creates a new hashtable with the specified size.
|
|
* It initializes the table with NULL entries.
|
|
*
|
|
* @param size The size of the hashtable
|
|
* @return A pointer to the newly created hashtable
|
|
*/
|
|
hashtable *hashtable_new(int size)
|
|
{
|
|
// Allocate memory for the hashtable
|
|
hashtable *h = malloc(sizeof(hashtable));
|
|
|
|
// Set the size of the hashtable
|
|
h->size = size;
|
|
|
|
// Allocate memory for the entry pointers
|
|
h->table = malloc(sizeof(entry *) * size);
|
|
|
|
// Initialize all entries to NULL
|
|
for (int i = 0; i < size; i++)
|
|
{
|
|
h->table[i] = NULL;
|
|
}
|
|
|
|
// Return the newly created hashtable
|
|
return h;
|
|
}
|
|
|
|
|
|
// hashtable_insert
|
|
void hashtable_insert(hashtable *h, const char *key, void *value) {
|
|
|
|
// Calculate the index using the hash function
|
|
int index = hash(key) % h->size;
|
|
|
|
// Create a new entry
|
|
entry *e = malloc(sizeof(entry));
|
|
e->key = key;
|
|
e->value = value;
|
|
e->next = NULL;
|
|
|
|
// Insert the entry at the beginning of the linked list
|
|
e->next = h->table[index];
|
|
h->table[index] = e;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
// hashtable_lookup
|
|
void *hashtable_lookup(hashtable *h, const char *key) {
|
|
|
|
// Calculate the index using the hash function
|
|
int index = hash(key) % h->size;
|
|
|
|
// Traverse the linked list at the index
|
|
entry *e = h->table[index];
|
|
while (e != NULL) {
|
|
if (strcmp(e->key, key) == 0) {
|
|
return e->value;
|
|
}
|
|
e = e->next;
|
|
}
|
|
|
|
// Return NULL if the key is not found
|
|
return NULL;
|
|
}
|
|
|
|
|
|
// hashtable_remove
|
|
void hashtable_remove(hashtable *h, const char *key) {
|
|
|
|
// Calculate the index using the hash function
|
|
int index = hash(key) % h->size;
|
|
|
|
// Traverse the linked list at the index
|
|
entry *e = h->table[index];
|
|
entry *prev = NULL;
|
|
while (e != NULL) {
|
|
if (strcmp(e->key, key) == 0) {
|
|
if (prev == NULL) {
|
|
h->table[index] = e->next;
|
|
} else {
|
|
prev->next = e->next;
|
|
}
|
|
free(e);
|
|
return;
|
|
}
|
|
prev = e;
|
|
e = e->next;
|
|
}
|
|
}
|