aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--example_use.c135
-rw-r--r--hashtable.c502
-rw-r--r--hashtable.h109
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);