1 #include <ccan/htable/htable.h>
2 #include <ccan/compiler/compiler.h>
9 /* This means a struct htable takes at least 512 bytes / 1k (32/64 bits). */
10 #define HTABLE_BASE_BITS 7
12 /* We use 0x1 as deleted marker. */
13 #define HTABLE_DELETED (0x1)
16 size_t (*rehash
)(const void *elem
, void *priv
);
19 size_t elems
, deleted
, max
, max_with_deleted
;
20 /* These are the bits which are the same in all pointers. */
21 uintptr_t common_mask
, common_bits
;
22 uintptr_t perfect_bit
;
26 /* We clear out the bits which are always the same, and put metadata there. */
27 static inline uintptr_t get_extra_ptr_bits(const struct htable
*ht
,
30 return e
& ht
->common_mask
;
33 static inline void *get_raw_ptr(const struct htable
*ht
, uintptr_t e
)
35 return (void *)((e
& ~ht
->common_mask
) | ht
->common_bits
);
38 static inline uintptr_t make_hval(const struct htable
*ht
,
39 const void *p
, uintptr_t bits
)
41 return ((uintptr_t)p
& ~ht
->common_mask
) | bits
;
44 static inline bool entry_is_valid(uintptr_t e
)
46 return e
> HTABLE_DELETED
;
49 static inline uintptr_t get_hash_ptr_bits(const struct htable
*ht
,
52 /* Shuffling the extra bits (as specified in mask) down the
53 * end is quite expensive. But the lower bits are redundant, so
54 * we fold the value first. */
55 return (hash
^ (hash
>> ht
->bits
))
56 & ht
->common_mask
& ~ht
->perfect_bit
;
59 struct htable
*htable_new(size_t (*rehash
)(const void *elem
, void *priv
),
62 struct htable
*ht
= malloc(sizeof(struct htable
));
64 ht
->bits
= HTABLE_BASE_BITS
;
69 ht
->max
= ((size_t)1 << ht
->bits
) * 3 / 4;
70 ht
->max_with_deleted
= ((size_t)1 << ht
->bits
) * 9 / 10;
71 /* This guarantees we enter update_common first add. */
75 ht
->table
= calloc(1 << ht
->bits
, sizeof(uintptr_t));
84 void htable_free(const struct htable
*ht
)
86 free((void *)ht
->table
);
90 static size_t hash_bucket(const struct htable
*ht
, size_t h
)
92 return h
& ((1 << ht
->bits
)-1);
95 static void *htable_val(const struct htable
*ht
,
96 struct htable_iter
*i
, size_t hash
, uintptr_t perfect
)
98 uintptr_t h2
= get_hash_ptr_bits(ht
, hash
) | perfect
;
100 while (ht
->table
[i
->off
]) {
101 if (ht
->table
[i
->off
] != HTABLE_DELETED
) {
102 if (get_extra_ptr_bits(ht
, ht
->table
[i
->off
]) == h2
)
103 return get_raw_ptr(ht
, ht
->table
[i
->off
]);
105 i
->off
= (i
->off
+ 1) & ((1 << ht
->bits
)-1);
111 void *htable_firstval(const struct htable
*ht
,
112 struct htable_iter
*i
, size_t hash
)
114 i
->off
= hash_bucket(ht
, hash
);
115 return htable_val(ht
, i
, hash
, ht
->perfect_bit
);
118 void *htable_nextval(const struct htable
*ht
,
119 struct htable_iter
*i
, size_t hash
)
121 i
->off
= (i
->off
+ 1) & ((1 << ht
->bits
)-1);
122 return htable_val(ht
, i
, hash
, 0);
125 void *htable_first(const struct htable
*ht
, struct htable_iter
*i
)
127 for (i
->off
= 0; i
->off
< (size_t)1 << ht
->bits
; i
->off
++) {
128 if (entry_is_valid(ht
->table
[i
->off
]))
129 return get_raw_ptr(ht
, ht
->table
[i
->off
]);
134 void *htable_next(const struct htable
*ht
, struct htable_iter
*i
)
136 for (i
->off
++; i
->off
< (size_t)1 << ht
->bits
; i
->off
++) {
137 if (entry_is_valid(ht
->table
[i
->off
]))
138 return get_raw_ptr(ht
, ht
->table
[i
->off
]);
143 /* This does not expand the hash table, that's up to caller. */
144 static void ht_add(struct htable
*ht
, const void *new, size_t h
)
147 uintptr_t perfect
= ht
->perfect_bit
;
149 i
= hash_bucket(ht
, h
);
151 while (entry_is_valid(ht
->table
[i
])) {
153 i
= (i
+ 1) & ((1 << ht
->bits
)-1);
155 ht
->table
[i
] = make_hval(ht
, new, get_hash_ptr_bits(ht
, h
)|perfect
);
158 static COLD
bool double_table(struct htable
*ht
)
161 size_t oldnum
= (size_t)1 << ht
->bits
;
162 uintptr_t *oldtable
, e
;
164 oldtable
= ht
->table
;
165 ht
->table
= calloc(1 << (ht
->bits
+1), sizeof(size_t));
167 ht
->table
= oldtable
;
172 ht
->max_with_deleted
*= 2;
174 /* If we lost our "perfect bit", get it back now. */
175 if (!ht
->perfect_bit
&& ht
->common_mask
) {
176 for (i
= 0; i
< sizeof(ht
->common_mask
) * CHAR_BIT
; i
++) {
177 if (ht
->common_mask
& ((size_t)1 << i
)) {
178 ht
->perfect_bit
= (size_t)1 << i
;
184 for (i
= 0; i
< oldnum
; i
++) {
185 if (entry_is_valid(e
= oldtable
[i
])) {
186 void *p
= get_raw_ptr(ht
, e
);
187 ht_add(ht
, p
, ht
->rehash(p
, ht
->priv
));
195 static COLD
void rehash_table(struct htable
*ht
)
200 /* Beware wrap cases: we need to start from first empty bucket. */
201 for (start
= 0; ht
->table
[start
]; start
++);
203 for (i
= 0; i
< (size_t)1 << ht
->bits
; i
++) {
204 size_t h
= (i
+ start
) & ((1 << ht
->bits
)-1);
208 if (e
== HTABLE_DELETED
)
210 else if (!(e
& ht
->perfect_bit
)) {
211 void *p
= get_raw_ptr(ht
, e
);
213 ht_add(ht
, p
, ht
->rehash(p
, ht
->priv
));
219 /* We stole some bits, now we need to put them back... */
220 static COLD
void update_common(struct htable
*ht
, const void *p
)
223 uintptr_t maskdiff
, bitsdiff
;
225 if (ht
->elems
== 0) {
226 ht
->common_mask
= -1;
227 ht
->common_bits
= (uintptr_t)p
;
232 /* Find bits which are unequal to old common set. */
233 maskdiff
= ht
->common_bits
^ ((uintptr_t)p
& ht
->common_mask
);
235 /* These are the bits which go there in existing entries. */
236 bitsdiff
= ht
->common_bits
& maskdiff
;
238 for (i
= 0; i
< (size_t)1 << ht
->bits
; i
++) {
239 if (!entry_is_valid(ht
->table
[i
]))
241 /* Clear the bits no longer in the mask, set them as
243 ht
->table
[i
] &= ~maskdiff
;
244 ht
->table
[i
] |= bitsdiff
;
247 /* Take away those bits from our mask, bits and perfect bit. */
248 ht
->common_mask
&= ~maskdiff
;
249 ht
->common_bits
&= ~maskdiff
;
250 ht
->perfect_bit
&= ~maskdiff
;
253 bool htable_add(struct htable
*ht
, size_t hash
, const void *p
)
255 if (ht
->elems
+1 > ht
->max
&& !double_table(ht
))
257 if (ht
->elems
+1 + ht
->deleted
> ht
->max_with_deleted
)
260 if (((uintptr_t)p
& ht
->common_mask
) != ht
->common_bits
)
261 update_common(ht
, p
);
268 bool htable_del(struct htable
*ht
, size_t h
, const void *p
)
270 struct htable_iter i
;
273 for (c
= htable_firstval(ht
,&i
,h
); c
; c
= htable_nextval(ht
,&i
,h
)) {
275 htable_delval(ht
, &i
);
282 void htable_delval(struct htable
*ht
, struct htable_iter
*i
)
284 assert(i
->off
< (size_t)1 << ht
->bits
);
285 assert(entry_is_valid(ht
->table
[i
->off
]));
288 ht
->table
[i
->off
] = HTABLE_DELETED
;