1 /* Licensed under LGPLv2+ - see LICENSE file for details */
2 #include <ccan/htable/htable.h>
3 #include <ccan/compiler/compiler.h>
9 /* We use 0x1 as deleted marker. */
10 #define HTABLE_DELETED (0x1)
12 /* We clear out the bits which are always the same, and put metadata there. */
13 static inline uintptr_t get_extra_ptr_bits(const struct htable
*ht
,
16 return e
& ht
->common_mask
;
19 static inline void *get_raw_ptr(const struct htable
*ht
, uintptr_t e
)
21 return (void *)((e
& ~ht
->common_mask
) | ht
->common_bits
);
24 static inline uintptr_t make_hval(const struct htable
*ht
,
25 const void *p
, uintptr_t bits
)
27 return ((uintptr_t)p
& ~ht
->common_mask
) | bits
;
30 static inline bool entry_is_valid(uintptr_t e
)
32 return e
> HTABLE_DELETED
;
35 static inline uintptr_t get_hash_ptr_bits(const struct htable
*ht
,
38 /* Shuffling the extra bits (as specified in mask) down the
39 * end is quite expensive. But the lower bits are redundant, so
40 * we fold the value first. */
41 return (hash
^ (hash
>> ht
->bits
))
42 & ht
->common_mask
& ~ht
->perfect_bit
;
45 void htable_init(struct htable
*ht
,
46 size_t (*rehash
)(const void *elem
, void *priv
), void *priv
)
54 ht
->max_with_deleted
= 0;
55 /* This guarantees we enter update_common first add. */
59 /* Dummy table until first insert. */
60 ht
->table
= &ht
->perfect_bit
;
63 void htable_clear(struct htable
*ht
)
65 if (ht
->table
!= &ht
->perfect_bit
)
66 free((void *)ht
->table
);
67 htable_init(ht
, ht
->rehash
, ht
->priv
);
70 static size_t hash_bucket(const struct htable
*ht
, size_t h
)
72 return h
& ((1 << ht
->bits
)-1);
75 static void *htable_val(const struct htable
*ht
,
76 struct htable_iter
*i
, size_t hash
, uintptr_t perfect
)
78 uintptr_t h2
= get_hash_ptr_bits(ht
, hash
) | perfect
;
80 while (ht
->table
[i
->off
]) {
81 if (ht
->table
[i
->off
] != HTABLE_DELETED
) {
82 if (get_extra_ptr_bits(ht
, ht
->table
[i
->off
]) == h2
)
83 return get_raw_ptr(ht
, ht
->table
[i
->off
]);
85 i
->off
= (i
->off
+ 1) & ((1 << ht
->bits
)-1);
91 void *htable_firstval(const struct htable
*ht
,
92 struct htable_iter
*i
, size_t hash
)
94 i
->off
= hash_bucket(ht
, hash
);
95 return htable_val(ht
, i
, hash
, ht
->perfect_bit
);
98 void *htable_nextval(const struct htable
*ht
,
99 struct htable_iter
*i
, size_t hash
)
101 i
->off
= (i
->off
+ 1) & ((1 << ht
->bits
)-1);
102 return htable_val(ht
, i
, hash
, 0);
105 void *htable_first(const struct htable
*ht
, struct htable_iter
*i
)
107 for (i
->off
= 0; i
->off
< (size_t)1 << ht
->bits
; i
->off
++) {
108 if (entry_is_valid(ht
->table
[i
->off
]))
109 return get_raw_ptr(ht
, ht
->table
[i
->off
]);
114 void *htable_next(const struct htable
*ht
, struct htable_iter
*i
)
116 for (i
->off
++; i
->off
< (size_t)1 << ht
->bits
; i
->off
++) {
117 if (entry_is_valid(ht
->table
[i
->off
]))
118 return get_raw_ptr(ht
, ht
->table
[i
->off
]);
123 /* This does not expand the hash table, that's up to caller. */
124 static void ht_add(struct htable
*ht
, const void *new, size_t h
)
127 uintptr_t perfect
= ht
->perfect_bit
;
129 i
= hash_bucket(ht
, h
);
131 while (entry_is_valid(ht
->table
[i
])) {
133 i
= (i
+ 1) & ((1 << ht
->bits
)-1);
135 ht
->table
[i
] = make_hval(ht
, new, get_hash_ptr_bits(ht
, h
)|perfect
);
138 static COLD
bool double_table(struct htable
*ht
)
141 size_t oldnum
= (size_t)1 << ht
->bits
;
142 uintptr_t *oldtable
, e
;
144 oldtable
= ht
->table
;
145 ht
->table
= calloc(1 << (ht
->bits
+1), sizeof(size_t));
147 ht
->table
= oldtable
;
151 ht
->max
= ((size_t)3 << ht
->bits
) / 4;
152 ht
->max_with_deleted
= ((size_t)9 << ht
->bits
) / 10;
154 /* If we lost our "perfect bit", get it back now. */
155 if (!ht
->perfect_bit
&& ht
->common_mask
) {
156 for (i
= 0; i
< sizeof(ht
->common_mask
) * CHAR_BIT
; i
++) {
157 if (ht
->common_mask
& ((size_t)1 << i
)) {
158 ht
->perfect_bit
= (size_t)1 << i
;
164 if (oldtable
!= &ht
->perfect_bit
) {
165 for (i
= 0; i
< oldnum
; i
++) {
166 if (entry_is_valid(e
= oldtable
[i
])) {
167 void *p
= get_raw_ptr(ht
, e
);
168 ht_add(ht
, p
, ht
->rehash(p
, ht
->priv
));
177 static COLD
void rehash_table(struct htable
*ht
)
182 /* Beware wrap cases: we need to start from first empty bucket. */
183 for (start
= 0; ht
->table
[start
]; start
++);
185 for (i
= 0; i
< (size_t)1 << ht
->bits
; i
++) {
186 size_t h
= (i
+ start
) & ((1 << ht
->bits
)-1);
190 if (e
== HTABLE_DELETED
)
192 else if (!(e
& ht
->perfect_bit
)) {
193 void *p
= get_raw_ptr(ht
, e
);
195 ht_add(ht
, p
, ht
->rehash(p
, ht
->priv
));
201 /* We stole some bits, now we need to put them back... */
202 static COLD
void update_common(struct htable
*ht
, const void *p
)
205 uintptr_t maskdiff
, bitsdiff
;
207 if (ht
->elems
== 0) {
208 ht
->common_mask
= -1;
209 ht
->common_bits
= (uintptr_t)p
;
214 /* Find bits which are unequal to old common set. */
215 maskdiff
= ht
->common_bits
^ ((uintptr_t)p
& ht
->common_mask
);
217 /* These are the bits which go there in existing entries. */
218 bitsdiff
= ht
->common_bits
& maskdiff
;
220 for (i
= 0; i
< (size_t)1 << ht
->bits
; i
++) {
221 if (!entry_is_valid(ht
->table
[i
]))
223 /* Clear the bits no longer in the mask, set them as
225 ht
->table
[i
] &= ~maskdiff
;
226 ht
->table
[i
] |= bitsdiff
;
229 /* Take away those bits from our mask, bits and perfect bit. */
230 ht
->common_mask
&= ~maskdiff
;
231 ht
->common_bits
&= ~maskdiff
;
232 ht
->perfect_bit
&= ~maskdiff
;
235 bool htable_add(struct htable
*ht
, size_t hash
, const void *p
)
237 if (ht
->elems
+1 > ht
->max
&& !double_table(ht
))
239 if (ht
->elems
+1 + ht
->deleted
> ht
->max_with_deleted
)
242 if (((uintptr_t)p
& ht
->common_mask
) != ht
->common_bits
)
243 update_common(ht
, p
);
250 bool htable_del(struct htable
*ht
, size_t h
, const void *p
)
252 struct htable_iter i
;
255 for (c
= htable_firstval(ht
,&i
,h
); c
; c
= htable_nextval(ht
,&i
,h
)) {
257 htable_delval(ht
, &i
);
264 void htable_delval(struct htable
*ht
, struct htable_iter
*i
)
266 assert(i
->off
< (size_t)1 << ht
->bits
);
267 assert(entry_is_valid(ht
->table
[i
->off
]));
270 ht
->table
[i
->off
] = HTABLE_DELETED
;