Add hash_helper.h for custom dynamic hash tables
authorBarret Rhoden <brho@cs.berkeley.edu>
Tue, 1 Nov 2016 00:25:21 +0000 (20:25 -0400)
committerBarret Rhoden <brho@cs.berkeley.edu>
Tue, 29 Nov 2016 16:27:40 +0000 (11:27 -0500)
The full-fledged dynamic hashtable.c doesn't work for a lot of code that
needs more control over its hash table.  For instance, the arena
allocator needs fine-grained control over allocations and a node's list
membership.

This header is a few building-block helpers that allow you to build your
own dynamically resized hash table.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
kern/include/hash_helper.h [new file with mode: 0644]

diff --git a/kern/include/hash_helper.h b/kern/include/hash_helper.h
new file mode 100644 (file)
index 0000000..c31c9a7
--- /dev/null
@@ -0,0 +1,57 @@
+/* Copyright (c) 2016 Google Inc
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * Helper structs and funcs for making a dynamically-sized hash table. */
+
+#pragma once
+
+struct hash_helper {
+       unsigned int                            nr_hash_lists;
+       unsigned int                            nr_hash_bits;
+       size_t                                          nr_items;
+       size_t                                          load_limit;
+};
+
+#define HASH_MAX_LOAD_FACTOR(size) ((size * 13) / 20)
+#define HASH_INIT_NR_BITS 6
+#define HASH_MAX_NR_BITS 31
+#define HASH_INIT_SZ (1 << HASH_INIT_NR_BITS)
+
+static inline bool hash_needs_more(struct hash_helper *hh)
+{
+       if (hh->nr_hash_bits == HASH_MAX_NR_BITS)
+               return FALSE;
+       return hh->nr_items > hh->load_limit;
+}
+
+/* Only call when you know we need more (i.e., bits < 31). */
+static inline unsigned int hash_next_nr_lists(struct hash_helper *hh)
+{
+       return 1 << (hh->nr_hash_bits + 1);
+}
+
+/* Only call when you know we need more (i.e., bits < 31). */
+static inline void hash_incr_nr_lists(struct hash_helper *hh)
+{
+       hh->nr_hash_bits++;
+       hh->nr_hash_lists = 1 << hh->nr_hash_bits;
+}
+
+static inline void hash_set_load_limit(struct hash_helper *hh, size_t lim)
+{
+       hh->load_limit = lim;
+}
+
+static inline void hash_reset_load_limit(struct hash_helper *hh)
+{
+       hh->load_limit = HASH_MAX_LOAD_FACTOR(hh->nr_hash_lists);
+}
+
+static inline void hash_init_hh(struct hash_helper *hh)
+{
+       hh->nr_hash_lists = HASH_INIT_SZ;
+       hh->nr_hash_bits = HASH_INIT_NR_BITS;
+       hh->nr_items = 0;
+       hash_reset_load_limit(hh);
+}