]> git.ozlabs.org Git - ccan/blob - ccan/hashtable/hashtable.c
web: make sure to include symlinks in tarballs
[ccan] / ccan / hashtable / hashtable.c
1 #include <ccan/hashtable/hashtable.h>
2 #include <stdint.h>
3 #include <stdlib.h>
4 #include <assert.h>
5
6 /* This means a struct hashtable takes at least 512 bytes / 1k (32/64 bits). */
7 #define HASHTABLE_BASE_BITS 7
8
9 /* We use 0x1 as deleted marker. */
10 #define HASHTABLE_DELETED ((void *)0x1)
11
12 /* Number of redundant bits in a pointer. */
13 #define PTR_STEAL_BITS 3
14
15 static inline uintptr_t get_extra_ptr_bits(const void *p)
16 {
17         return (uintptr_t)p & (((uintptr_t)1 << PTR_STEAL_BITS)-1);
18 }
19
20 static inline void *get_raw_ptr(const void *p)
21 {
22         return (void *)((uintptr_t)p & ~(((uintptr_t)1 << PTR_STEAL_BITS)-1));
23 }
24
25 static inline void *make_ptr(const void *p, uintptr_t bits)
26 {
27         return (void *)((uintptr_t)p | bits);
28 }
29
30 struct hashtable {
31         unsigned long (*rehash)(const void *elem, void *priv);
32         void *priv;
33         unsigned int bits;
34         unsigned long elems, max;
35         void **table;
36 };
37
38 static inline bool ptr_is_valid(const void *e)
39 {
40         return e > HASHTABLE_DELETED;
41 }
42
43 struct hashtable *hashtable_new(unsigned long (*rehash)(const void *elem,
44                                                         void *priv),
45                                 void *priv)
46 {
47         struct hashtable *ht = malloc(sizeof(struct hashtable));
48         if (ht) {
49                 ht->bits = HASHTABLE_BASE_BITS;
50                 ht->rehash = rehash;
51                 ht->priv = priv;
52                 ht->elems = 0;
53                 ht->max = (1 << ht->bits) * 3 / 4;
54                 ht->table = calloc(1 << ht->bits, sizeof(void *));
55                 if (!ht->table) {
56                         free(ht);
57                         ht = NULL;
58                 }
59         }
60         return ht;
61 }
62
63 void hashtable_free(struct hashtable *ht)
64 {
65         free(ht->table);
66         free(ht);
67 }
68
69 static unsigned long hash_bucket(const struct hashtable *ht,
70                                  unsigned long h, unsigned long *ptrbits)
71 {
72         *ptrbits = (h >> ht->bits) & (((uintptr_t)1 << PTR_STEAL_BITS)-1);
73         return h & ((1 << ht->bits)-1);
74 }
75
76 /* This does not expand the hash table, that's up to caller. */
77 static void ht_add(struct hashtable *ht, const void *new, unsigned long h)
78 {
79         unsigned long i, h2;
80
81         i = hash_bucket(ht, h, &h2);
82
83         while (ptr_is_valid(ht->table[i])) {
84                 i = (i + 1) & ((1 << ht->bits)-1);
85         }
86         ht->table[i] = make_ptr(new, h2);
87 }
88
89 static bool double_table(struct hashtable *ht)
90 {
91         unsigned int i;
92         size_t oldnum = (size_t)1 << ht->bits;
93         void **oldtable, *e;
94
95         oldtable = ht->table;
96         ht->table = calloc(1 << (ht->bits+1), sizeof(void *));
97         if (!ht->table) {
98                 ht->table = oldtable;
99                 return false;
100         }
101         ht->bits++;
102         ht->max *= 2;
103
104         for (i = 0; i < oldnum; i++) {
105                 if (ptr_is_valid(e = oldtable[i])) {
106                         e = get_raw_ptr(e);
107                         ht_add(ht, e, ht->rehash(e, ht->priv));
108                 }
109         }
110         free(oldtable);
111         return true;
112 }
113
114 bool hashtable_add(struct hashtable *ht, unsigned long hash, const void *p)
115 {
116         if (ht->elems+1 > ht->max && !double_table(ht))
117                 return false;
118         ht->elems++;
119         assert(p);
120         assert(((uintptr_t)p & (((uintptr_t)1 << PTR_STEAL_BITS)-1)) == 0);
121         ht_add(ht, p, hash);
122         return true;
123 }
124
125 /* Find bucket for an element. */
126 static size_t ht_find(struct hashtable *ht,
127                       unsigned long hash,
128                       bool (*cmp)(const void *htelem, void *cmpdata),
129                       void *cmpdata)
130 {
131         void *e;
132         unsigned long i, h2;
133
134         i = hash_bucket(ht, hash, &h2);
135
136         while ((e = ht->table[i]) != NULL) {
137                 if (e != HASHTABLE_DELETED
138                     && h2 == get_extra_ptr_bits(e)
139                     && cmp(get_raw_ptr(ht->table[i]), cmpdata))
140                         return i;
141                 i = (i + 1) & ((1 << ht->bits)-1);
142         }
143         return (size_t)-1;
144 }
145
146
147 /* If every one of the following buckets are DELETED (up to the next unused
148    one), we can actually mark them all unused. */
149 static void delete_run(struct hashtable *ht, unsigned int num)
150 {
151         unsigned int i, last = num + 1;
152
153         while (ht->table[last & ((1 << ht->bits)-1)]) {
154                 if (ptr_is_valid(ht->table[last & ((1 << ht->bits)-1)]))
155                         return;
156                 last++;
157         }
158         for (i = num; i < last; i++)
159                 ht->table[i & ((1 << ht->bits)-1)] = NULL;
160 }
161
162 void *hashtable_find(struct hashtable *ht,
163                      unsigned long hash,
164                      bool (*cmp)(const void *htelem, void *cmpdata),
165                      void *cmpdata)
166 {
167         size_t i = ht_find(ht, hash, cmp, cmpdata);
168         if (i != (size_t)-1)
169                 return get_raw_ptr(ht->table[i]);
170         return NULL;
171 }
172
173 static bool ptr_cmp(const void *htelem, void *cmpdata)
174 {
175         return htelem == cmpdata;
176 }
177
178 bool hashtable_del(struct hashtable *ht, unsigned long hash, const void *p)
179 {
180         size_t i = ht_find(ht, hash, ptr_cmp, (void *)p);
181         if (i == (size_t)-1)
182                 return false;
183
184         ht->elems--;
185         ht->table[i] = HASHTABLE_DELETED;
186         delete_run(ht, i);
187         return true;
188 }
189
190 void _hashtable_traverse(struct hashtable *ht,
191                          bool (*cb)(void *p, void *cbarg),
192                          void *cbarg)
193 {
194         size_t i;
195
196         for (i = 0; i < (1 << ht->bits); i++) {
197                 if (ptr_is_valid(ht->table[i]))
198                         if (cb(get_raw_ptr(ht->table[i]), cbarg))
199                                 return;
200         }
201 }