Skip to content

Instantly share code, notes, and snippets.

@akharrou

akharrou/hashtable.c

Last active December 1, 2018 09:56
Show Gist options
  • Save akharrou/408ceb6d39ce9cf1515359f93a0d6063 to your computer and use it in GitHub Desktop.
Save akharrou/408ceb6d39ce9cf1515359f93a0d6063 to your computer and use it in GitHub Desktop.
Download ZIP
Simple Hash Table Implementation in C
Raw
hashtable.c
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
// ======================================================================= //
// HASH TABLE FUNCTION LIBRARY //
// ======================================================================= //
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
/* * * * * * * * * * * *
========================
HASH TABLE HEADER
========================
* * * * * * * * * * * */
#ifndef FT_HASHTABLE_H
# define FT_HASHTABLE_H
# define HASHCODE(key, buckets) (hash(key, ft_strlen(key)) % buckets)
# define MIN_LOAD_FACTOR 0.0
# define MAX_LOAD_FACTOR 0.7
typedef struct s_entry
{
char *key;
void *value;
struct s_entry *successor;
} t_entry;
typedef struct s_hashtable
{
unsigned int entries;
unsigned int num_buckets;
t_entry **bucket_list;
} t_hashtable;
t_hashtable *hashtable_alloc_table(unsigned int size);
t_hashtable *hashtable_realloc_table(t_hashtable **table);
t_hashtable *hashtable_dealloc_table(t_hashtable **table);
t_entry *hashtable_fetch_entry(t_hashtable *table, char *key);
int hashtable_insert_entry(t_hashtable **table, char *key,
void *value);
int hashtable_delete_entry(t_hashtable **table, char *key);
int hashtable_rehash_entry(t_hashtable **table_to,
t_entry **entry);
int hashtable_rehash_table(t_hashtable **table_from,
t_hashtable **table_to);
int hashtable_destroy_table(t_hashtable **table);
int hashtable_check_load_factor(t_hashtable **table);
t_entry *ft_entry_create(char *key, void *value);
void ft_entry_free(t_entry **entry);
void ft_bucket_free(t_entry **head);
#endif
/* — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
DEPENDENCIES: malloc() , <stdlib.h>
ft_find_next_prime()
DESCRIPTION: Creates/allocates an empty hash table of size 'size'
and then some (inorder to get to the nearest prime
number).
RETURN VALUES: If successful, returns a pointer to the
hash table. If an error occurs the function
will return a NULL pointer.
SEARCH TAGS: ft hashtable_alloc_table ft hashtable_create_table
ft ht_alloc_table ft ht_create_table
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — */
t_hashtable *hashtable_alloc_table(unsigned int size)
{
t_hashtable *table;
unsigned int i;
if (size < 1)
return (NULL);
if (!(table = malloc(sizeof(t_hashtable))))
return (NULL);
size = (unsigned int)ft_find_next_prime(size);
if (!(table->bucket_list =
malloc(sizeof(t_entry*) * size)))
{
return (NULL);
}
table->num_buckets = size;
table->entries = 0;
i = 0;
while (i < size)
(table->bucket_list)[i++] = NULL;
return (table);
}
/* — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
DEPENDENCIES: hashtable_check_load_factor()
ft_entry_create()
ft_strlen()
HASHCODE()
DESCRIPTION: Inserts a key-value pair into the hash table.
RETURN VALUES: If successful, returns 0; otherwise -1.
SEARCH TAGS: ft hashtable_insert_data ft hashtable_add_entry
ft ht_insert_data ft ht_add_entry
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — */
int hashtable_insert_entry(t_hashtable **table, char *key,
void *value)
{
t_entry *entry;
unsigned int index;
if (table && *table && key && value)
{
if (hashtable_check_load_factor(table) == -1)
return (-1);
if (!(entry = ft_entry_create(key, value)))
return (-1);
index = HASHCODE(key, (*table)->num_buckets);
entry->successor = ((*table)->bucket_list)[index];
((*table)->bucket_list)[index] = entry;
(*table)->entries += 1;
return (0);
}
return (-1);
}
/* — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
DEPENDENCIES: ft_strcmp()
ft_strlen()
HASHCODE()
DESCRIPTION: Finds and returns (retrieves) an entry.
RETURN VALUES: If the entry is found, a pointer to the entry is
returned; otherwise a NULL pointer is returned.
SEARCH TAGS: ft hashtable_fetch_entry ft hashtable_fetch_data
ft hashtable_find_entry ft hashtable_lookup_entry
ft ht_fetch_entry ft ht_fetch_data
ft ht_find_entry ft ht_lookup_entry
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — */
t_entry *hashtable_fetch_entry(t_hashtable *table, char *key)
{
t_entry *cur_entry;
unsigned int index;
if (table && key)
{
index = HASHCODE(key, table->num_buckets);
cur_entry = (table->bucket_list)[index];
while (cur_entry)
{
if (ft_strcmp(cur_entry->key, key) == 0)
return (cur_entry);
cur_entry = cur_entry->successor;
}
}
return (NULL);
}
/* — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
DEPENDENCIES: ft_entry_free()
ft_strcmp()
ft_strlen()
HASHCODE()
DESCRIPTION: Finds and deletes/frees an entry in the hash
table.
RETURN VALUES: If the entry is found, and is successfully
deleted/free'd, the function returns 0;
otherwise the function returns -1.
SEARCH TAGS: ft hashtable_delete_data ft ht_delete_data
ft hashtable_delete_entry ft ht_delete_entry
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — */
int hashtable_delete_entry(t_hashtable **table, char *key)
{
t_entry *prev_entry;
t_entry *cur_entry;
unsigned int index;
if (table && key)
{
index = HASHCODE(key, (*table)->num_buckets);
cur_entry = ((*table)->bucket_list)[index];
while (cur_entry)
{
if (ft_strcmp(cur_entry->key, key) == 0)
{
if (cur_entry == ((*table)->bucket_list)[index])
((*table)->bucket_list)[index] = cur_entry->successor;
else
prev_entry->successor = cur_entry->successor;
ft_entry_free(&cur_entry);
(*table)->entries -= 1;
return (0);
}
prev_entry = cur_entry;
cur_entry = cur_entry->successor;
}
}
return (-1);
}
/* — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
DEPENDENCIES: free() , <stdlib.h>
ft_bucket_free()
DESCRIPTION: Deletes/frees the entire hash table
and all the entries contained in it.
RETURN VALUES: If successful returns 0; otherwise -1.
SEARCH TAGS: ft hashtable_destroy ft ht_destroy
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — */
int hashtable_destroy_table(t_hashtable **table)
{
unsigned int i;
if (table)
{
if (*table)
{
if ((*table)->bucket_list)
{
i = 0;
while (i < (*table)->num_buckets)
{
if (((*table)->bucket_list)[i])
ft_bucket_free(&((*table)->bucket_list)[i]);
i++;
}
free((*table)->bucket_list);
(*table)->bucket_list = NULL;
}
free(*table);
(*table) = NULL;
}
return (0);
}
return (-1);
}
/* — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
DEPENDENCIES: hashtable_realloc_table()
hashtable_dealloc_table()
MAX_LOAD_FACTOR
MIN_LOAD_FACTOR
DESCRIPTION: Checks that the current load factor is
neither greater than nor smaller than
the desired max load factor and desired
minimum load factor respectively.
If either is the case, a procedure to
realloc (grow) or dealloc (shrink) the
table will ensue.
If neither is the case, nothing happens.
RETURN VALUES: If nothing happens, or a successful
reallocation or deallocation happens,
0 is returned. If an error occurs -1
is returned.
SEARCH TAGS: ft hashtable_check_load_factor ft ht_check_load_factor
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — */
int hashtable_check_load_factor(t_hashtable **table)
{
if (table && *table)
{
if ((float)(*table)->entries / (float)(*table)->num_buckets
> MAX_LOAD_FACTOR)
{
if (!(*table = hashtable_realloc_table(table)))
return (-1);
return (0);
}
if ((float)(*table)->entries / (float)(*table)->num_buckets
< MIN_LOAD_FACTOR)
{
if (!(*table = hashtable_dealloc_table(table)))
return (-1);
return (0);
}
else
{
return (0);
}
}
return (-1);
}
/* — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
DEPENDENCIES: free() , <stdlib.h>
hashtable_alloc_table()
hashtable_rehash_table()
hashtable_destroy_table()
DESCRIPTION: Grows the hash table by half and then some
(inorder to get to the nearest prime number).
RETURN VALUES: If successful returns a pointer to the grown
hash table. Otherwise, if an error occurs the
function returns a NULL pointer.
SEARCH TAGS: ft hashtable_realloc_table ft ht_realloc_table
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — */
t_hashtable *hashtable_realloc_table(t_hashtable **table)
{
t_hashtable *new_table;
if (table && *table)
{
new_table = hashtable_alloc_table((*table)->num_buckets * 2);
if (new_table == NULL)
return (NULL);
if (hashtable_rehash_table(table, &new_table) == -1)
return (NULL);
hashtable_destroy_table(table);
return (new_table);
}
return (NULL);
}
/* — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
DEPENDENCIES: free() , <stdlib.h>
hashtable_alloc_table()
hashtable_rehash_table()
hashtable_destroy_table()
DESCRIPTION: Shrinks the hash table by half and then some
(inorder to get to the nearest prime number).
RETURN VALUES: If successful returns a pointer to the shrunk
hash table. Otherwise, if an error occurs the
function returns a NULL pointer.
SEARCH TAGS: ft hashtable_dealloc_table ft ht_dealloc_table
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — */
t_hashtable *hashtable_dealloc_table(t_hashtable **table)
{
t_hashtable *new_table;
if (table && *table)
{
if ((*table)->num_buckets > 1)
{
new_table = hashtable_alloc_table((*table)->num_buckets / 2);
if (new_table == NULL)
return (NULL);
if (hashtable_rehash_table(table, &new_table) == -1)
return (NULL);
hashtable_destroy_table(table);
return (new_table);
}
return (*table);
}
return (NULL);
}
/* — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
DEPENDENCIES: ft_strlen()
HASHCODE()
DESCRIPTION: Rehashs one entry in the 'table_to' hashtable.
RETURN VALUES: If successful returns 0; otherwise -1.
SEARCH TAGS: ft hashtable_rehash_entry ft ht_rehash_entry
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — */
int hashtable_rehash_entry(t_hashtable **table_to, t_entry **entry)
{
unsigned int index;
if (table_to && *table_to && entry && *entry)
{
index = HASHCODE((*entry)->key, (*table_to)->num_buckets);
(*entry)->successor = ((*table_to)->bucket_list)[index];
((*table_to)->bucket_list)[index] = (*entry);
(*table_to)->entries += 1;
return (0);
}
return (-1);
}
/* — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
DEPENDENCIES: hashtable_rehash_entry()
DESCRIPTION: Rehashs all the entries in the hashtable
'table_from' into the hashtable 'table_to'.
RETURN VALUES: If successful returns 0; otherwise -1.
SEARCH TAGS: ft hashtable_rehash_table ft ht_rehash_table
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — */
int hashtable_rehash_table(t_hashtable **table_from,
t_hashtable **table_to)
{
t_entry *cur_entry;
t_entry *temp;
unsigned int i;
if (table_from && *table_from && table_to && *table_to)
{
i = 0;
while (i < (*table_from)->num_buckets)
{
if (((*table_from)->bucket_list)[i])
{
cur_entry = ((*table_from)->bucket_list)[i];
while (cur_entry)
{
temp = cur_entry->successor;
if (hashtable_rehash_entry(table_to, &cur_entry) == -1)
return (-1);
cur_entry = temp;
}
((*table_from)->bucket_list)[i] = NULL;
}
i++;
}
}
return (((*table_to)->entries == (*table_from)->entries) ? 0 : -1);
}
/* — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
DEPENDENCIES: malloc() , <stdlib.h>
ft_strdup()
DESCRIPTION: Takes a key and a value and creates an entry out
of them.
NOTE: 'value' MUST have previously been
allocated, otherwise in the free'ing of
an entry, you WILL get a 'bad free' error.
RETURN VALUES: If successful, the function returns a pointer
to the new entry; if an error occurs, it returns
a NULL pointer.
SEARCH TAGS: ft entry_create ft create_entry
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — */
t_entry *ft_entry_create(char *key, void *value)
{
t_entry *new_entry;
if (key && value)
{
if (!(new_entry = malloc(sizeof(t_entry))))
return (NULL);
new_entry->key = ft_strdup(key);
new_entry->value = value;
new_entry->successor = NULL;
return (new_entry);
}
return (NULL);
}
/* — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
DEPENDENCIES: free() , <stdlib.h>
DESCRIPTION: Deletes/frees an entry (this is for use with entries that
have members that were allocated only).
NOTE: if 'entry->value' was not allocated somewhere in
the code, you WILL get a 'bad free' error.
RETURN VALUES: none.
SEARCH TAGS: ft entry_free ft free_entry
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — */
void ft_entry_free(t_entry **entry)
{
if (entry && *entry)
{
if ((*entry)->key)
free((*entry)->key);
if ((*entry)->value)
free((*entry)->value);
free(*entry);
(*entry) = NULL;
}
}
/* — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
DEPENDENCIES: ft_entry_free()
DESCRIPTION: Deletes/frees the entire bucket (linked
list).
RETURN VALUES: none.
SEARCH TAGS: ft bucket_free ft free_bucket
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — */
void ft_bucket_free(t_entry **head)
{
t_entry *temp;
if (head)
{
while (*head)
{
temp = (*head);
(*head) = (*head)->successor;
ft_entry_free(&temp);
}
}
}
Raw
utils.c
/* ===============================================================
UTILIY FUNCTIONS
=============================================================== */
#include <stdlib.h>
/* reproduction of the standard library strlen() function */
int ft_strlen(char *str)
{
int i;
i = 0;
while (str[i])
++i;
return (i);
}
/* reproduction of the standard library strcmp() function */
int ft_strcmp(char *s1, char *s2)
{
unsigned int i;
i = 0;
while (s1[i] == s2[i] && s1[i] && s2[i])
i++;
return (s1[i] - s2[i]);
}
/* reproduction of the standard library strdup() function */
char *ft_strdup(char *src)
{
int i;
char *dest;
i = 0;
while (src[i])
i++;
if (!(dest = malloc(i + 1)))
return (0);
i = 0;
while (src[i])
{
dest[i] = src[i];
i++;
}
dest[i] = '\0';
return (dest);
}
/* checks whether the number 'nb' is a prime number */
int ft_is_prime(int nb)
{
long i;
long result;
if (nb < 2)
return (0);
if (nb == 2 || nb == 3 || nb == 5 || nb == 7)
return (1);
if (nb % 2 == 0 || nb % 3 == 0 || nb % 5 == 0 || nb % 7 == 0)
return (0);
i = 11;
while ((result = i * i) < nb)
{
if (nb % i == 0 || result > 2147483647)
return (0);
i += 2;
}
return (1);
}
/* returns the next prime number or itself if it is a prime number */
int ft_find_next_prime(int nb)
{
if (nb < 2)
return (2);
if (nb == 2)
return (nb);
if (nb % 2 == 0)
nb++;
while (!ft_is_prime(nb))
nb += 2;
return (nb);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment