sched: Slightly fix up tests/prov
[akaros.git] / kern / include / hash_helper.h
1 /* Copyright (c) 2016 Google Inc
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Helper structs and funcs for making a dynamically-sized hash table. */
6
7 #pragma once
8
9 struct hash_helper {
10         unsigned int                            nr_hash_lists;
11         unsigned int                            nr_hash_bits;
12         size_t                                          nr_items;
13         size_t                                          load_limit;
14 };
15
16 #define HASH_MAX_LOAD_FACTOR(size) ((size * 13) / 20)
17 #define HASH_INIT_NR_BITS 6
18 #define HASH_MAX_NR_BITS 31
19 #define HASH_INIT_SZ (1 << HASH_INIT_NR_BITS)
20
21 static inline bool hash_needs_more(struct hash_helper *hh)
22 {
23         if (hh->nr_hash_bits == HASH_MAX_NR_BITS)
24                 return FALSE;
25         return hh->nr_items > hh->load_limit;
26 }
27
28 /* Only call when you know we need more (i.e., bits < 31). */
29 static inline unsigned int hash_next_nr_lists(struct hash_helper *hh)
30 {
31         return 1 << (hh->nr_hash_bits + 1);
32 }
33
34 /* Only call when you know we need more (i.e., bits < 31). */
35 static inline void hash_incr_nr_lists(struct hash_helper *hh)
36 {
37         hh->nr_hash_bits++;
38         hh->nr_hash_lists = 1 << hh->nr_hash_bits;
39 }
40
41 static inline void hash_set_load_limit(struct hash_helper *hh, size_t lim)
42 {
43         hh->load_limit = lim;
44 }
45
46 static inline void hash_reset_load_limit(struct hash_helper *hh)
47 {
48         hh->load_limit = HASH_MAX_LOAD_FACTOR(hh->nr_hash_lists);
49 }
50
51 static inline void hash_init_hh(struct hash_helper *hh)
52 {
53         hh->nr_hash_lists = HASH_INIT_SZ;
54         hh->nr_hash_bits = HASH_INIT_NR_BITS;
55         hh->nr_items = 0;
56         hash_reset_load_limit(hh);
57 }