diff options
Diffstat (limited to 'hashtbl.c')
| -rw-r--r-- | hashtbl.c | 228 |
1 files changed, 228 insertions, 0 deletions
diff --git a/hashtbl.c b/hashtbl.c new file mode 100644 index 0000000..f26a8dd --- /dev/null +++ b/hashtbl.c @@ -0,0 +1,228 @@ +/* hashtbl.c + * + * Hash Table + * + */ + +#include "hashtbl.h" +#include "hashfuncs.h" + +char *strdup(const char *s) +{ + char *b; + if (!(b = malloc(strlen(s) + 1))) + return NULL; + strcpy(b, s); + + return b; +} + +HASHTBL *hashtbl_create(size_t size, unsigned int (*hashfunc)(const char *)) +{ + HASHTBL *hashtbl; + + if (!(hashtbl = malloc(sizeof(HASHTBL)))) + return NULL; + + /* pointer array of nodes */ + if (!(hashtbl->nodes = calloc(size, sizeof(struct hashnode_s*)))) + { + free(hashtbl); + return NULL; + } + + hashtbl->size = size; + + if (hashfunc) + hashtbl->hashfunc = hashfunc; + else + hashtbl->hashfunc = aphash; + + return hashtbl; +} + +void hashtbl_destroy(HASHTBL *hashtbl) +{ + size_t n; + struct hashnode_s *node, *oldnode; + + for (n = 0; n<hashtbl->size; ++n) { + node = hashtbl->nodes[n]; + while (node) { + free(node->key); + oldnode = node; + node = node->next; + free(oldnode); + } + } + free(hashtbl->nodes); + free(hashtbl); +} + +int hashtbl_insert(HASHTBL *hashtbl, const char *key, void *data) +{ + struct hashnode_s *head; + size_t hash = hashtbl->hashfunc(key) % hashtbl->size; + +/* fprintf(stderr, "hashtbl_insert() key = %s, hash = %d, data = %s\n", key, hash, (char*)data); */ + + head = hashtbl->nodes[hash]; + while (head) + { + if (!strcmp(head->key, key)) + { + /* update the data in currently existing node */ + head->data = data; + return 0; + } + + head = head->next; + } + + /* if we get here, it means that this is the first node at particular index + * or we are appending new node to the end of the linked list */ + if (!(head = malloc(sizeof(struct hashnode_s)))) + return -1; + + if (!(head->key = strdup(key))) + { + free(head); + return -1; + } + + head->data = data; + head->next = hashtbl->nodes[hash]; + + /* update head ptr */ + hashtbl->nodes[hash] = head; + + return 0; +} + +int hashtbl_remove(HASHTBL *hashtbl, const char *key) +{ + struct hashnode_s *node, *prevnode = NULL; + size_t hash = hashtbl->hashfunc(key) % hashtbl->size; + + node = hashtbl->nodes[hash]; + while (node) + { + if (!strcmp(node->key, key)) + { + free(node->key); + if (prevnode) + prevnode->next = node->next; + else + hashtbl->nodes[hash] = node->next; + + free(node); + + return 0; + } + + prevnode = node; + node = node->next; + } + + return -1; +} + + +void *hashtbl_get(HASHTBL *hashtbl, const char *key) +{ + struct hashnode_s *head; + size_t hash = hashtbl->hashfunc(key) % hashtbl->size; + +/* fprintf(stderr, "hashtbl_get() key = %s, hash = %d\n", key, hash);*/ + + head = hashtbl->nodes[hash]; + while (head) + { + /* return data only when keys match */ + if (!strcmp(head->key, key)) + return head->data; + + head = head->next; + } + + return NULL; +} + +int hashtbl_resize(HASHTBL *hashtbl, size_t size) +{ + HASHTBL newtbl; + size_t n; + struct hashnode_s *node,*next; + + newtbl.size = size; + newtbl.hashfunc = hashtbl->hashfunc; + + if (!(newtbl.nodes = calloc(size, sizeof(struct hashnode_s*)))) return -1; + + for (n = 0; n<hashtbl->size; ++n) { + for (node = hashtbl->nodes[n]; node; node = next) { + next = node->next; + hashtbl_insert(&newtbl, node->key, node->data); + hashtbl_remove(hashtbl, node->key); + + } + } + + free(hashtbl->nodes); + hashtbl->size = newtbl.size; + hashtbl->nodes = newtbl.nodes; + + return 0; +} + +int main(void) +{ + char *key = "abcdefghijklmnopqrstuvwxyz1234567890"; + + (void) printf("Hash Functions\n"); + (void) printf("Key: %s\n\n", key); + (void) printf("ASCII default hash function value: %u\n", defaulthash(key)); + (void) printf("RS hash function value: %u\n", rshash(key)); + (void) printf("JS hash function value: %u\n", jshash(key)); + (void) printf("PJW hash function value: %u\n", pjwhash(key)); + (void) printf("ELF hash function value: %u\n", elfhash(key)); + (void) printf("BKDR hash function value: %u\n", bkdrhash(key)); + (void) printf("SDBM hash function value: %u\n", sdbmhash(key)); + (void) printf("DJB hash function value: %u\n", djbhash(key)); + (void) printf("DEK hash function value: %u\n", dekhash(key)); + (void) printf("BP hash function value: %u\n", bphash(key)); + (void) printf("FNV hash function value: %u\n", fnvhash(key)); + (void) printf("AP hash function value: %u\n", aphash(key)); + (void) puts(""); + + HASHTBL *hashtbl; + char *italy, *spain; + + hashtbl = hashtbl_create(16, NULL); + if (hashtbl == NULL) + { + fprintf(stderr, "error: hashtbl_create() failed\n"); + exit(-1); + } + + hashtbl_insert(hashtbl, "France", "Paris"); + hashtbl_insert(hashtbl, "England", "London"); + hashtbl_insert(hashtbl, "Sweden", "Stockholm"); + hashtbl_insert(hashtbl, "Germany", "Berlin"); + hashtbl_insert(hashtbl, "Norway", "Oslo"); + hashtbl_insert(hashtbl, "Italy", "Rome"); + hashtbl_insert(hashtbl, "Spain", "Madrid"); + hashtbl_insert(hashtbl, "Estonia", "Tallinn"); + hashtbl_insert(hashtbl, "Netherlands", "Amsterdam"); + hashtbl_insert(hashtbl, "Ireland", "Dublin"); + + italy = hashtbl_get(hashtbl, "Italy"); + (void) printf("Italy: %s\n", italy ? italy : ""); + spain = hashtbl_get(hashtbl, "Spain"); + (void) printf("Spain: %s\n", spain ? spain : ""); + + hashtbl_destroy(hashtbl); + + return 0; +} + |