/*
This file is part of urlg.
urlg is free software: you can redistribute it and/or modify it under the terms
of the GNU General Public License as published by the Free Software Foundation,
either version 3 of the License, or (at your option) any later version. urlg is
distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the GNU General Public License for more details. You should have
received a copy of the GNU General Public License along with Foobar. If not, see
.
*/
#include "ht.h"
#include
#include
#include
struct node {
char *key;
void *val;
struct node *next;
};
struct hash_table {
struct node **vals;
int max_size;
int size;
int curr_index;
struct node *curr_node;
bool iterating;
};
static void rehash(ht_t *h, int newsize)
{
ht_t *new_h = ht_create(newsize);
ht_iter_init(h);
struct kvp kvp = ht_iter_next(h);
while (kvp.key) {
ht_insert(new_h, kvp.key, kvp.val);
kvp = ht_iter_next(h);
}
// only destroy vals if it isn't NULL
if (h->vals) {
// iterate through the hash values
for (int i = 0; i < h->max_size; ++i) {
// iterate through the linked list and remove the value
struct node *curr = h->vals[i];
struct node *prev;
while (curr) {
prev = curr;
curr = curr->next;
free(prev->key);
free(prev);
}
}
free(h->vals);
}
h->max_size = newsize;
h->vals = new_h->vals;
h->curr_index = 0;
h->curr_node = NULL;
h->iterating = false;
free(new_h);
}
static unsigned long djb2_hash(char *str)
{
unsigned long hash = 5381;
int c;
// hash * 33 + c
while ((c = *str++)) hash = ((hash << 5) + hash) + c;
return hash;
}
ht_t *ht_create(int max_size)
{
ht_t *h = malloc(sizeof(ht_t));
h->max_size = max_size;
h->size = 0;
h->vals = malloc(sizeof(struct node) * max_size);
h->curr_index = 0;
h->curr_node = NULL;
h->iterating = false;
return h;
}
void ht_destroy(ht_t *h)
{
// only destroy if h isn't NULL
if (h) {
// only destroy vals if it isn't NULL
if (h->vals) {
// iterate through the hash values
for (int i = 0; i < h->max_size; ++i) {
// iterate through the linked list and remove the value
struct node *curr = h->vals[i];
struct node *prev;
while (curr) {
prev = curr;
curr = curr->next;
free(prev->key);
free(prev);
}
}
free(h->vals);
}
free(h);
}
}
void *ht_find(ht_t *h, char *key)
{
unsigned int hash = djb2_hash(key) % h->max_size;
// exit early if hash isn't in table
if (!h->vals[hash])
return NULL;
// iterate through values stored at `hash`; exit early if found
struct node *curr = h->vals[hash];
while (curr) {
if (strcmp(key, curr->key) == 0)
return curr->val;
curr = curr->next;
}
return NULL;
}
void ht_insert(ht_t *h, char *key, void *val)
{
if (h->size > h->max_size * 0.75)
rehash(h, h->max_size * 2);
unsigned int hash = djb2_hash(key) % h->max_size;
// create a node
int len = strlen(key);
struct node *new = malloc(sizeof(struct node));
new->key = malloc(sizeof(char) * (len + 1));
for (int i = 0; i < len; ++i) {
new->key[i] = key[i];
}
new->key[len] = 0;
new->val = val;
// insert node at beginning of list
if (h->vals[hash]) {
new->next = h->vals[hash];
}
h->vals[hash] = new;
++(h->size);
}
void ht_delete(ht_t *h, char *key)
{
if (h->size < h->max_size * 0.25)
rehash(h, h->max_size * 0.5);
unsigned int hash = djb2_hash(key) % h->max_size;
if (!h->vals[hash])
return; // exit if the hash is not found
// remove the key from the front of the list if it's there
if (strcmp(key, h->vals[hash]->key) == 0) {
struct node *temp = h->vals[hash];
h->vals[hash] = h->vals[hash]->next;
free(temp->key);
free(temp);
} else {
// iterate through list and remove once a match is found
struct node *prev = h->vals[hash];
struct node *curr = h->vals[hash]->next;
while (curr) {
if (strcmp(key, curr->key) == 0) {
prev->next = curr->next;
free(curr->key);
free(curr);
return;
}
prev = curr;
curr = curr->next;
}
}
}
int ht_size(ht_t *h)
{
return h->size;
}
void ht_iter_init(ht_t *h)
{
h->curr_index = 0;
h->curr_node = h->vals[0];
}
struct kvp ht_iter_next(ht_t *h)
{
struct kvp out = {
.key = NULL,
.val = NULL,
};
// return NULL if we've reached the end
if (!h->curr_node && h->curr_index >= h->max_size)
return out;
// look for next index with node if current node is NULL
if (!h->curr_node) {
while (!h->curr_node) {
h->curr_node = h->vals[h->curr_index++];
if (h->curr_index >= h->max_size)
return out;
}
}
// get the value and move to the next node
out.key = h->curr_node->key;
out.val = h->curr_node->val;
h->curr_node = h->curr_node->next;
return out;
}