diff options
| -rw-r--r-- | example_use.c | 135 | ||||
| -rw-r--r-- | hashtable.c | 502 | ||||
| -rw-r--r-- | hashtable.h | 109 |
3 files changed, 746 insertions, 0 deletions
diff --git a/example_use.c b/example_use.c new file mode 100644 index 0000000..bbd2433 --- /dev/null +++ b/example_use.c @@ -0,0 +1,135 @@ +// I didn't take the effort to clean up this file as I did with +// hashtable.c and hashtable.h. It's not really important, tho. +// Instead of this "console hashtable" I should make some test cases +// (which I probably won't be motivated enough to do anyway). + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "hashtable.h" + +void print_pair(const char *key, const char *val, void *dummy){ + printf("key: %s val: %s\n", key, val); +} + +void free_pair(void *key, void *val, void *dummy){ + free(key); + free(val); +} + +int main(int argc, char **argv){ + hashtable_t ht; + if (ht_string_init(&ht)) // HT_NO_MEM + { + fprintf(stderr, "ERROR, couldn't allocate memory!\n"); + exit(-1); + } + + char buf[100]; + + while (scanf("%99s", buf) != EOF) { + if (!strcmp(buf, "add")) { + if (scanf("%99s", buf) == EOF) break; + + size_t len = strlen(buf) + 1; + char *key = malloc(len); + if (key == NULL) { + fprintf(stderr, "ERROR, couldn't allocate memory!\n"); + exit(1); + } + + memcpy(key, buf, len); + + if (scanf("%99s", buf) == EOF) { + free(key); + break; + } + + len = strlen(buf) + 1; + char *val = malloc(len); + if (val == NULL) { + free(key); + fprintf(stderr, "ERROR, couldn't allocate memory!\n"); + exit(1); + } + + memcpy(val, buf, len); + + switch (ht_add(&ht, key, val)) + { + case HT_OK: + break; + case HT_NO_MEM: + fprintf(stderr, "ERROR, couldn't allocate memory!\n"); + free(key); free(val); + exit(1); + default: // case HT_KEY_PRESENT + printf("Key already present!\n"); + } + } + else if (!strcmp(buf, "set")) { + if (scanf("%99s", buf) == EOF) break; + + size_t len = strlen(buf) + 1; + char *key = malloc(len); + if (key == NULL) { + fprintf(stderr, "ERROR, couldn't allocate memory!\n"); + exit(1); + } + + memcpy(key, buf, len); + + if (scanf("%99s", buf) == EOF) break; + + len = strlen(buf) + 1; + char *val = malloc(len); + if (val == NULL) { + free(key); + fprintf(stderr, "ERROR, couldn't allocate memory!\n"); + exit(1); + } + + memcpy(val, buf, len); + + void *oldkey = NULL, *oldval = NULL; + if (ht_set(&ht, key, val, &oldkey, &oldval) != 0) { + free(key); free(val); + + fprintf(stderr, "ERROR, couldn't allocate memory!\n"); + exit(1); + } + + if (oldval != NULL) { + printf("Replaced: %s\n", (char*) oldval); + free(oldval); free(oldkey); + } + } + else if (!strcmp(buf, "get")) { + if (scanf("%99s", buf) == EOF) break; + + void *val; + if (ht_get(&ht, buf, NULL, &val)) + printf("No such entry!\n"); + else printf("%s\n", (char*) val); + } + else if (!strcmp(buf, "rem")) { + if (scanf("%99s", buf) == EOF) break; + + void *storedkey, *val; + if (ht_rem(&ht, buf, &storedkey, &val)) + printf("No such entry!\n"); + else { + printf("%s\n", (char*) val); + free(val); free(storedkey); + } + } + else if(!strcmp(buf, "entries")) printf("%zu\n", ht.entries); + else if(!strcmp(buf, "print")) + ht_map(&ht, NULL, (void (*)(void*, void*, void*)) &print_pair); + else printf("I have no idea what you're talking about...\n"); + } + + ht_map_destroy(&ht, NULL, + (void (*)(void*, void*, void*)) &free_pair); +} diff --git a/hashtable.c b/hashtable.c new file mode 100644 index 0000000..c2dc582 --- /dev/null +++ b/hashtable.c @@ -0,0 +1,502 @@ +// GENERAL INFO + +// You might want to read the beginning of hashtable.h first. + +// In some places "rehashing" and in other ones "resizing" seemed to +// be the right word to use. They mean more or less the same. + +// Functions starting with ht_ are part of the API. Internal functions +// are declared static. I also made some of them inline (either +// because they were extremely short or only called from 1 place). + +// Hashtable size is always a power of 2. + +// When the hashtable is ¾ full, a new, 2x bigger table is allocated +// and whenever one of 4 basic operations (adding, removing, setting, +// getting) occurs, 4 slots are being rehashed from old table into 8 +// slots in new table. Similarly, when hashtable is ¼ full, a new, +// 2x smaller table is allocated and each of subsequent operations +// rehashes 8 entries from old table into 4 in new table. +// This mechanism has been made lazier: getting and removing don't +// trigger growing of ht even if it's 3/4 full. Similarly, getting, +// setting and adding don't trigger shrinking. +// Once resizing is triggered, however, any of the operations will +// contribute to rehashing. Even if, for example, the operation is +// ADD and the table is being shrinked. +// This means, that if we have a hashtable of size n which is ¾ full +// and growing is triggered, then each subsequent call to +// ht_{add,rem,get,set}() rehashes some entries and, depending on +// how frequently and how successfully each of these 4 funcs was +// called, at the end of resizing we get a size 2n hashtable which is +// between ¼ and ½ full. Similarly, if shrinking of a ¼ full +// hashtable of size n is triggered, then after some operations we +// get a size ½n hashtable, that is somewhere between ¼ and ¾ full. +// One can see now, that we always keep the hashtable between ¼ and ¾ +// full (with the exception of a minimal size one, that can be empty). + +#include "hashtable.h" + +#include <stdlib.h> +#include <string.h> +#include <stdio.h> +#include <stdbool.h> + +// We won't shrink hashtable below this size. Newly created one will +// be this big. +#define MIN_SIZE 32 + +// Special value of ht->rehashing_position. +#define NOT_REHASHING ((ssize_t) -1) + +// Those are possible return values of do_resizing_related_stuff() +// and rehash_some_entries() (which only returns the first 2). +#define REHASHING_IN_PROGRESS 0 +#define REHASHING_NOT_IN_PROGRESS 1 +#define REHASHING_NO_MEM 2 + +enum op + { + GET, + ADD, + SET, + REM, + }; + +int ht_init(hashtable_t *ht, + size_t (*hash)(void *key), + int (*cmp)(void *key1, void *key2)) +{ + if (!(ht->tab = calloc(MIN_SIZE, sizeof(struct ht_node**)))) + return HT_NO_MEM; + + ht->tab_size = MIN_SIZE; + ht->rehashing_position = NOT_REHASHING; + ht->entries = 0; + ht->hashfunc = hash; + ht->cmpfunc = cmp; + + return HT_OK; +} + +// First come some utilities :) + +static inline size_t min(size_t n1, size_t n2) +{ + return n1 < n2 ? n1 : n2; +} + +static inline size_t hash2(size_t n) +{ + // I found this "hash improver" on the internet. + n ^= (n >> 20) ^ (n >> 12); + return n ^ (n >> 7) ^ (n >> 4); +} + +// Below are 2 list-handling utility functions. +static inline struct ht_node *join_lists(struct ht_node *l1, + struct ht_node *l2) +{ + if (!l1) return l2; + if (!l2) return l1; + + struct ht_node *l1_last; + + for (l1_last = l1; l1_last->next; l1_last = l1_last->next); + + // Append l2 to the end of l1. + l1_last->next = l2; + + // For convenience return the first element of the resulting list. + return l1; +} + + +static inline void push(struct ht_node *node, struct ht_node **list) +{ + node->next = *list; + *list = node; +} + +// The following 2 rehash_* functions are helpers of +// rehash_some_entries(). +// This func rehashes 1 chain of entries in tab[] +// into 2 chains in newtab[]. +static inline void rehash_position_growing(hashtable_t *ht) +{ + // There are 2 possible new positions of an entry in a 2x bigger ht. + struct ht_node *list0 = NULL, *list1 = NULL; + + size_t old_position = ht->rehashing_position, + new_position0 = old_position, + new_position1 = old_position | ht->tab_size; + + struct ht_node *pair = ht->tab[old_position], *next_pair; + + while (pair) + { + next_pair = pair->next; + + size_t new_position = hash2(ht->hashfunc(pair->key)) + & (ht->new_size - 1); + + push(pair, new_position == new_position1 ? &list1 : &list0); + + pair = next_pair; + } + + ht->newtab[new_position0] = list0; + ht->newtab[new_position1] = list1; + + ht->rehashing_position++; +} + +// This func rehashes 2 chains of entries in tab[] +// into 1 chain in newtab[]. +static inline void rehash_2positions_shrinking(hashtable_t *ht) +{ + size_t new_position = ht->rehashing_position, + old_position0 = new_position, + old_position1 = new_position | ht->new_size; + + ht->newtab[new_position] = join_lists(ht->tab[old_position0], + ht->tab[old_position1]); + + ht->rehashing_position++; +} + +// Rehashes 4(8) positions from tab to newtab. If those were the last +// enetries to rehash, the function takes care of everything +// (like deallocating old tab) and returns REHASHING_NOT_IN_PROGRESS. +// Otherwise, returns REHASHING_IN_PROGRESS. +// Caller must make sure rehashing was started b4 calling this func. +static int rehash_some_entries(hashtable_t *ht) +{ + int rehashes_left = 4; + + if (ht->new_size > ht->tab_size) // growing ht + { + while(rehashes_left--) rehash_position_growing(ht); + if (ht->rehashing_position != ht->tab_size) + return REHASHING_IN_PROGRESS; + } + else // shrinking ht + { + while(rehashes_left--) rehash_2positions_shrinking(ht); + if (ht->rehashing_position != ht->new_size) + return REHASHING_IN_PROGRESS; + } + + // rehashing finishes + ht->rehashing_position = NOT_REHASHING; + ht->tab_size = ht->new_size; + free(ht->tab); + ht->tab = ht->newtab; + + return REHASHING_NOT_IN_PROGRESS; +} + +static inline bool resizing_taking_place(hashtable_t *ht) +{ + return !(ht->rehashing_position == NOT_REHASHING); +} + +void ht_finish_resizing(hashtable_t *ht) +{ + if (resizing_taking_place(ht)) + while (rehash_some_entries(ht) == REHASHING_IN_PROGRESS); +} + +static inline bool needs_growing(hashtable_t *ht) +{ + return ht->entries == 3 * ht->tab_size / 4; +} + +static inline bool needs_shrinking(hashtable_t *ht) +{ + return ht->tab_size > MIN_SIZE + && ht->entries == ht->tab_size / 4; +} + +// Each of hashtable operations (add, set, rem, get) should also +// attempt to do part of resizing. This way resizing operation +// which is O(n) is distributed among many hashtable accesses +// each of them still being O(1). Without this the the amortized +// complexity of ht accesses would still be O(1), but a single access +// would sometimes be O(n). +// Other function that adds, sets, gets or removes sth from ht uses +// this one to do this "part of resizing" mentioned above. +// This func returns REHASHING_NO_MEM on failed malloc (won't happen +// for GET operation) and REHASHING_(NOT_)IN_PROGRESS otherwise. +static inline int do_resizing_related_stuff(hashtable_t *ht, + void *key, enum op op) +{ + bool resizing = resizing_taking_place(ht); + + if (!resizing) + { + size_t new_size; + + switch (op) + { + case GET: + goto dont_start_resizing; + case ADD: + case SET: + if (needs_growing(ht)) + new_size = ht->tab_size * 2; + else + goto dont_start_resizing; + break; + default: // case REM + if (needs_shrinking(ht)) + new_size = ht->tab_size / 2; + else + goto dont_start_resizing; + } + + struct ht_node **newtab; + if (!(newtab = malloc(new_size * sizeof(struct ht_node*)))) + return REHASHING_NO_MEM; + + ht->newtab = newtab; + ht->new_size = new_size; + ht->rehashing_position = 0; + + resizing = true; + } + + dont_start_resizing: + + return resizing ? + rehash_some_entries(ht) : REHASHING_NOT_IN_PROGRESS; +} + +// This is a chaining hashtable, so each element in the array (table) +// is actually a list of entries. All operations (adding, removing, +// etc.) need to find the right list of entries (here called "bucket") +// for a given key first, so it makes sense to do it in a separate +// function. The bucket may be in tab or newtab if resizing is taking +// place. Being informed by the caller if resizing is in progress, +// this func does not need to check for it itself. +static inline struct ht_node **find_bucket(hashtable_t *ht, void *key, + bool resizing_in_progress) +{ + size_t hash = hash2(ht->hashfunc(key)), + destination_tab_size, position; + + struct ht_node **destination_tab; + + if (resizing_in_progress) + // Here we must check whether our key's bucket is still + // in ht->tab or already rehashed to ht->newtab. + { + size_t smaller_tab_size = min(ht->tab_size, ht->new_size), + smaller_tab_position = hash & (smaller_tab_size - 1); + + if (smaller_tab_position < ht->rehashing_position) + { + destination_tab = ht->newtab; + destination_tab_size = ht->new_size; + } + else + { + destination_tab = ht->tab; + destination_tab_size = ht->tab_size; + } + } + else + // In this case we know, we're working on ht->tab and not newtab. + { + destination_tab = ht->tab; + destination_tab_size = ht->tab_size; + } + + position = hash & (destination_tab_size - 1); + return &destination_tab[position]; +} + +// Operations of adding, removing, etc. all work on list of entries +// (bucket) to wchich key hashes and they have some common logic, so +// it made sense to make a single function, that does the right +// operation based on an enum passed to it. +static inline int +perform_operation_on_bucket(hashtable_t *ht, struct ht_node **bucket, + void *key, void *val, + void **keyptr, void **valptr, + enum op op) +{ + for (struct ht_node **pairptr = bucket, *pair = *pairptr; + pair; + pairptr = &pair->next, pair = pair->next) + + if (!ht->cmpfunc(key, pair->key)) + { + if (op == ADD) + return HT_KEY_PRESENT; + + if (keyptr) *keyptr = pair->key; + if (valptr) *valptr = pair->val; + + switch (op) + { + case GET: + { + return HT_OK; + } + case SET: + { + pair->key = key; + pair->val = val; + return HT_OK; + } + default: // case REM + { + *pairptr = pair->next; + free(pair); + ht->entries--; + return HT_OK; + } + } + } + + if (op == GET || op == REM) + return HT_KEY_ABSENT; + + // op == ADD || op == SET + + struct ht_node *new_pair = malloc(sizeof(struct ht_node)); + if (!new_pair) + return HT_NO_MEM; + + *new_pair = (struct ht_node) {.key = key, .val = val}; + push(new_pair, bucket); + ht->entries++; + + return HT_OK; +} + +// Generic function for performing of adding, removing, setting and +// getting. +static int perform_operation(hashtable_t *ht, void *key, void *val, + void **keyptr, void **valptr, enum op op) +{ + bool resizing_in_progress; + + switch (do_resizing_related_stuff(ht, key, op)) + { + case REHASHING_IN_PROGRESS: + resizing_in_progress = true; + break; + case REHASHING_NOT_IN_PROGRESS: + resizing_in_progress = false; + break; + default: // case REHASHING_NO_MEM + return HT_NO_MEM; + } + + struct ht_node **bucket = + find_bucket(ht, key, resizing_in_progress); + + return perform_operation_on_bucket(ht, bucket, key, val, + keyptr, valptr, op); +} + +// The 4 functions below are the main part of the API. +int ht_get(hashtable_t *ht, void *key, + void **storedkey, void **val) +{ + return perform_operation(ht, key, NULL, storedkey, val, GET); +} + +int ht_add(hashtable_t *ht, void *key, void *val) +{ + return perform_operation(ht, key, val, NULL, NULL, ADD); +} + +int ht_set(hashtable_t *ht, void *key, void *val, + void **oldkey, void **oldval) +{ + return perform_operation(ht, key, val, oldkey, oldval, SET); +} + +int ht_rem(hashtable_t *ht, void *key, + void **storedkey, void **val) +{ + return perform_operation(ht, key, NULL, storedkey, val, REM); +} + +// As mentioned in hashtable.h, this func does not deallocate keys +// nor vals. One could use ht_map() to free() them before calling this +// func. +void ht_destroy(hashtable_t *ht) +{ + if (!ht->entries) return; + ht_finish_resizing(ht); + + struct ht_node **tab = ht->tab; + + for (ssize_t position = ht->tab_size - 1; + position >= 0; position--) + { + struct ht_node *pair = tab[position], *nextpair; + + while (pair) + { + nextpair = pair->next; + free(pair); + pair = nextpair; + } + } + + free(ht->tab); +} + +void ht_map(hashtable_t *ht, void *arg, + void (*mapfunc)(void *key, void *val, void *arg)) +{ + if (!ht->entries) return; + ht_finish_resizing(ht); + + struct ht_node **tab = ht->tab; + + for (ssize_t position = ht->tab_size - 1; + position >= 0; position--) + + for (struct ht_node *pair = tab[position]; + pair; pair = pair->next) + + mapfunc(pair->key, pair->val, arg); +} + +void ht_map_destroy(hashtable_t *ht, void *arg, + void (*mapfunc)(void *key, void *val, void *arg)) +{ + // If mapfunc() deallocates keys, then the next 2 lines require + // assumption on ht_destroy(), that it doesn't call ht->hashfunc() + // or ht->cmpfunc() on keys. + ht_map(ht, arg, mapfunc); + ht_destroy(ht); +} + +// These 2 functions are for easy making of hashtable with strings as +// keys. +size_t ht_string_hash(const char *key) +{ + size_t i = 0, hash = (size_t) 0xa1bad2dead3beef4; + + do + { + char shift = ((unsigned char) key[i]) % sizeof(size_t); + hash += ((hash >> shift) | (hash << (sizeof(size_t) - shift))) + ^ key[i]; + } + while (key[i++]); + + return hash; +} + +int ht_string_init(hashtable_t *ht) +{ + return ht_init(ht, (size_t (*)(void*)) &ht_string_hash, + (int (*)(void*, void*)) &strcmp); +} diff --git a/hashtable.h b/hashtable.h new file mode 100644 index 0000000..9c04c4c --- /dev/null +++ b/hashtable.h @@ -0,0 +1,109 @@ +// This is a separate chaining hashtable for general use. It's not +// universal: it uses malloc() and free(), so it requires a standard +// library to function and it's for single-threaded use only. It does, +// however, have one advantage: it rehashes automatically, both when +// it grows in size and when it shrinks, while retaining O(1) access +// time. A normal hashtable with rehashing would have amortized O(1) +// access time, but there would be single access with O(n) time +// complexity for each rehashing. In this hashtable, rehashing is done +// in parts. For example, a ht_add(), aside from adding an entry, +// might also rehash 4 other entries from old table to the new one and +// leave the rest unrehashed. +// Of course, it is assumed that a good hash function is provided +// by the programmer. If not, accesses may still degenerate to O(n). + +#include <sys/types.h> // for ssize_t + +// These are possible retrn values of some ht_ functions (see below). +#define HT_OK 0 +#define HT_NO_MEM -1 +#define HT_KEY_PRESENT -2 +#define HT_KEY_ABSENT -3 + +// Struct used to store the pair. Implementation detail. +struct ht_node +{ + void *key; + void *val; + struct ht_node *next; +}; + +typedef struct +{ + // All members are considered implementation details, except for + // "entries", which can be read, but should not be modified by + // external code. + size_t entries; + + // tab[] is where entries (chains of entries) are stored. + // When rehashing, newtab[] is also used. + struct ht_node **tab, **newtab; + + // sizes of tab[] and newtab[], obviously + size_t tab_size, new_size; + + size_t (*hashfunc)(void* key); + int (*cmpfunc)(void* key1, void *key2); + + // When no rehashing is taking place, rehashing_position is -1 + // (#define'd as NOT_REHASHING in hashtable.c). At any other time, + // rehashing_position is the lowest not yet rehashed position in + // the smaller table. + ssize_t rehashing_position; +} hashtable_t; + +// All int functions return 0 (#define'd as HT_OK) on success and in +// case of failure they return error codes, as described below. + +// May fail with HT_NO_MEM. +int ht_init(hashtable_t *ht, + size_t (*hash)(void* key), + int (*cmp)(void* key1, void *key2)); + +// May fail with HT_NO_MEM and HT_KEY_PRESENT. +int ht_add(hashtable_t *ht, void *key, void *val); + +// May fail with HT_NO_MEM. If key was not yet present in hashtable, +// *oldkey and *oldval are not modified. Otherwise, just-replaced pair +// is stored in them. +int ht_set(hashtable_t *ht, void *key, void *val, + void **oldkey, void **oldval); + +// If present, the looked for pair is stored in *storedkey and *val. +// Otherwise, they're not modified and HT_KEY_ABSENT is returned. +// storedkey and/or val can be NULL. +int ht_get(hashtable_t *ht, void *key, void **storedkey, void **val); + +// Works like the above but also removes the pair from ht if found. +int ht_rem(hashtable_t *ht, void *key, void **storedkey, void **val); + +// De-initializes the hashtable freeing all it's structures. +// The programmer is responsible for freeing keys and values if they +// were allocated from the heap (see ht_map_destroy() below). +void ht_destroy(hashtable_t *ht); + +// Calls ht_finish_resizing(), then maps through ht. +void ht_map(hashtable_t *ht, void *arg, + void (*mapfunc)(void *key, void *val, void *arg)); + +// It might be tempting to use ht_map() to free() all keys and values +// stored in ht and then call ht_destroy(). If you think about it, +// ht_map() would leave hashtable in a broken state - with keys being +// deallocated. Depending on the implementation, ht_destroy() could +// cope with that, but we'd rather not guarrantee anything, so here's +// another function just for that - mapping through entries and +// destroying the hashtable immediately after, explicitly allowing +// the mapping function to dealocate keys. +void ht_map_destroy(hashtable_t *ht, void *arg, + void (*mapfunc)(void *key, void *val, void *arg)); + +// If hashtable is in the process of being rehashed, this function +// processes it to the end. Otherwise - it does nothing. +void ht_finish_resizing(hashtable_t *ht); + +// Included, since strings are commonly used as keys +size_t ht_string_hash(const char *key); + +// May fail with HT_NO_MEM. Initializes ht for use with string keys +// (using ht_string_hash() and strcmp()). +int ht_string_init(hashtable_t *ht); |