data_structures

data structures in C
Log | Files | Refs | Feed | README

commit 69cf82cae5f7e73a97ef4aea1284dc69a68fb65f
parent 56c78bb47536f4ead8e34a55e09194fac0c1dd21
Author: Jenny Doe <tng@soykaf.me>
Date:   Sat, 23 Mar 2019 19:36:41 +0100

added: hash_tables

Diffstat:
Ahash_table.c | 122+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ahash_table.h | 39+++++++++++++++++++++++++++++++++++++++
Ahash_table_test.c | 70++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 231 insertions(+), 0 deletions(-)

diff --git a/hash_table.c b/hash_table.c @@ -0,0 +1,122 @@ +#include <stdlib.h> +#include <string.h> + +#include "hash_table.h" + +#define NULL ((void *)0) + +int +hash_table_init(Hash_Table * ht, + unsigned int (*hash_key) (const Hash_Table *, const char *), + unsigned int size) +{ + ht->size = size; + ht->population = 0; + ht->hash_key = hash_key; + ht->buckets = malloc(sizeof(Bucket) * ht->size); + if (ht->buckets == NULL) + return (1); + for (unsigned int i = 0; i < ht->size; i++) { + ht->buckets[i].size = 0; + ht->buckets[i].head = NULL; + } + return (0); +} + +void +hash_table_destroy(Hash_Table * ht) +{ + for (unsigned int i = 0; i < ht->size; i++) { + + Key_Value *kv; + while ((kv = ht->buckets[i].head) != NULL) { + free((void *)kv->unhashed_key); + ht->buckets[i].head = kv->next; + ht->buckets[i].size--; + free(kv); + } + + } + + free(ht->buckets); + + return; +} + +int +hash_table_insert(Hash_Table * ht, const char *key, int value) +{ + int hashed_key = ht->hash_key(ht, key); + + Key_Value *kv = malloc(sizeof(Key_Value)); + if (kv == NULL) + return (1); + + kv->unhashed_key = strdup(key); + if (kv->unhashed_key == NULL) + return (1); + + kv->value = value; + kv->next = ht->buckets[hashed_key].head; + + ht->population++; + ht->buckets[hashed_key].head = kv; + ht->buckets[hashed_key].size++; + + return (0); +} + +int +hash_table_get(const Hash_Table * ht, const char *key) +{ + int hashed_key = ht->hash_key(ht, key); + + if (ht->buckets[hashed_key].size == 0) + return 0; + + if (ht->buckets[hashed_key].size == 1) + return ht->buckets[hashed_key].head->value; + + else { + Key_Value *kv = ht->buckets[hashed_key].head; + while (kv != NULL) { + if (strcmp(key, kv->unhashed_key) == 0) { + return kv->value; + } + kv = kv->next; + } + return 0; + } + + return 0; +} + +Hash_Table * +hash_table_dup(const Hash_Table * ht2, + unsigned int (*hash_key) (const Hash_Table *, const char *), + unsigned int size) +{ + Hash_Table *ht = malloc(sizeof(Hash_Table)); + if (ht == NULL) + goto end; + + if (hash_table_init(ht, hash_key, size) != 0) { + free(ht); + return NULL; + } + + if (ht2 == NULL) + goto end; + + for (int i = 0; i < ht2->size; i++) { + Key_Value *kv = ht2->buckets[i].head; + while (kv != NULL) { + if (hash_table_insert(ht, kv->unhashed_key, kv->value) != 0) + goto end; /* compare sizes to verify */ + kv = kv->next; + } + } + +end: + return ht; +} diff --git a/hash_table.h b/hash_table.h @@ -0,0 +1,39 @@ +#pragma once + +struct Key_Value_ { + const char *unhashed_key; + int value; + + struct Key_Value_ *next; +}; +typedef struct Key_Value_ Key_Value; + +typedef struct { + unsigned int size; + Key_Value *head; +} Bucket; + +typedef struct Hash_Table_ { + unsigned int size; + unsigned int population; + unsigned int (*hash_key) (const struct Hash_Table_ *, + const char *); + Bucket *buckets; +} +typedef struct Hash_Table_ Hash_Table; + +int +hash_table_init(Hash_Table *, + unsigned int (*) (const Hash_Table *, const char *), + unsigned int); + +void hash_table_destroy(Hash_Table *); + +int hash_table_insert(Hash_Table *, const char *, int); + +int hash_table_get(const Hash_Table *, const char *); + +Hash_Table * +hash_table_dup(const Hash_Table *, + unsigned int (*) (const Hash_Table *, const char *), + unsigned int); diff --git a/hash_table_test.c b/hash_table_test.c @@ -0,0 +1,70 @@ +#include <stdio.h> +#include <stdlib.h> + +#include "hash_table.h" + +#define ht_dup hash_table_dup +#define ht_insert hash_table_insert +#define ht_get hash_table_get +#define ht_destroy hash_table_destroy + +unsigned int +hash(const Hash_Table *ht, const char *key) +{ + int hash = 0; + + for (int i = 0; key[i] != '\0'; i++) { + hash += key[i]; + hash = hash % ht->size; + } + + return hash; +} + +int +main(void) +{ + int exit_code = 0; + + Hash_Table *small_table = ht_dup(NULL, hash, 5); + if (small_table == NULL) { + fprintf(stderr, "Failed to allocate memory!\n"); + exit_code = 1; + goto end; + } + + ht_insert(small_table, "foo", 67); + ht_insert(small_table, "oof", 99); /* collision */ + ht_insert(small_table, "bar", 34); + + printf("foo = %d\n", ht_get(small_table, "foo")); + printf("oof = %d\n", ht_get(small_table, "oof")); + printf("bar = %d\n", ht_get(small_table, "bar")); + printf("404 = %d\n", ht_get(small_table, "404")); + + Hash_Table *big_table = hash_table_dup(small_table, hash, 130); + if (big_table == NULL) { + fprintf(stderr, "Failed to allocate memory!\n"); + exit_code = 1; + goto end; + } + + printf("foo = %d\n", ht_get(big_table, "foo")); + printf("oof = %d\n", ht_get(big_table, "oof")); + printf("bar = %d\n", ht_get(big_table, "bar")); + printf("404 = %d\n", ht_get(big_table, "404")); + + +end: + if (big_table != NULL) { + ht_destroy(big_table); + free(big_table); + } + + if (small_table != NULL) { + ht_destroy(small_table); + free(small_table); + } + + return exit_code; +}