1*33b1fccfSAndroid Build Coastguard Worker // SPDX-License-Identifier: GPL-2.0
2*33b1fccfSAndroid Build Coastguard Worker /*
3*33b1fccfSAndroid Build Coastguard Worker * Copied from https://github.com/git/git.git
4*33b1fccfSAndroid Build Coastguard Worker * Generic implementation of hash-based key value mappings.
5*33b1fccfSAndroid Build Coastguard Worker */
6*33b1fccfSAndroid Build Coastguard Worker #include "erofs/hashmap.h"
7*33b1fccfSAndroid Build Coastguard Worker
8*33b1fccfSAndroid Build Coastguard Worker #define FNV32_BASE ((unsigned int)0x811c9dc5)
9*33b1fccfSAndroid Build Coastguard Worker #define FNV32_PRIME ((unsigned int)0x01000193)
10*33b1fccfSAndroid Build Coastguard Worker
strhash(const char * str)11*33b1fccfSAndroid Build Coastguard Worker unsigned int strhash(const char *str)
12*33b1fccfSAndroid Build Coastguard Worker {
13*33b1fccfSAndroid Build Coastguard Worker unsigned int c, hash = FNV32_BASE;
14*33b1fccfSAndroid Build Coastguard Worker
15*33b1fccfSAndroid Build Coastguard Worker while ((c = (unsigned char)*str++))
16*33b1fccfSAndroid Build Coastguard Worker hash = (hash * FNV32_PRIME) ^ c;
17*33b1fccfSAndroid Build Coastguard Worker return hash;
18*33b1fccfSAndroid Build Coastguard Worker }
19*33b1fccfSAndroid Build Coastguard Worker
strihash(const char * str)20*33b1fccfSAndroid Build Coastguard Worker unsigned int strihash(const char *str)
21*33b1fccfSAndroid Build Coastguard Worker {
22*33b1fccfSAndroid Build Coastguard Worker unsigned int c, hash = FNV32_BASE;
23*33b1fccfSAndroid Build Coastguard Worker
24*33b1fccfSAndroid Build Coastguard Worker while ((c = (unsigned char)*str++)) {
25*33b1fccfSAndroid Build Coastguard Worker if (c >= 'a' && c <= 'z')
26*33b1fccfSAndroid Build Coastguard Worker c -= 'a' - 'A';
27*33b1fccfSAndroid Build Coastguard Worker hash = (hash * FNV32_PRIME) ^ c;
28*33b1fccfSAndroid Build Coastguard Worker }
29*33b1fccfSAndroid Build Coastguard Worker return hash;
30*33b1fccfSAndroid Build Coastguard Worker }
31*33b1fccfSAndroid Build Coastguard Worker
memhash(const void * buf,size_t len)32*33b1fccfSAndroid Build Coastguard Worker unsigned int memhash(const void *buf, size_t len)
33*33b1fccfSAndroid Build Coastguard Worker {
34*33b1fccfSAndroid Build Coastguard Worker unsigned int hash = FNV32_BASE;
35*33b1fccfSAndroid Build Coastguard Worker unsigned char *ucbuf = (unsigned char *)buf;
36*33b1fccfSAndroid Build Coastguard Worker
37*33b1fccfSAndroid Build Coastguard Worker while (len--) {
38*33b1fccfSAndroid Build Coastguard Worker unsigned int c = *ucbuf++;
39*33b1fccfSAndroid Build Coastguard Worker
40*33b1fccfSAndroid Build Coastguard Worker hash = (hash * FNV32_PRIME) ^ c;
41*33b1fccfSAndroid Build Coastguard Worker }
42*33b1fccfSAndroid Build Coastguard Worker return hash;
43*33b1fccfSAndroid Build Coastguard Worker }
44*33b1fccfSAndroid Build Coastguard Worker
memihash(const void * buf,size_t len)45*33b1fccfSAndroid Build Coastguard Worker unsigned int memihash(const void *buf, size_t len)
46*33b1fccfSAndroid Build Coastguard Worker {
47*33b1fccfSAndroid Build Coastguard Worker unsigned int hash = FNV32_BASE;
48*33b1fccfSAndroid Build Coastguard Worker unsigned char *ucbuf = (unsigned char *)buf;
49*33b1fccfSAndroid Build Coastguard Worker
50*33b1fccfSAndroid Build Coastguard Worker while (len--) {
51*33b1fccfSAndroid Build Coastguard Worker unsigned int c = *ucbuf++;
52*33b1fccfSAndroid Build Coastguard Worker
53*33b1fccfSAndroid Build Coastguard Worker if (c >= 'a' && c <= 'z')
54*33b1fccfSAndroid Build Coastguard Worker c -= 'a' - 'A';
55*33b1fccfSAndroid Build Coastguard Worker hash = (hash * FNV32_PRIME) ^ c;
56*33b1fccfSAndroid Build Coastguard Worker }
57*33b1fccfSAndroid Build Coastguard Worker return hash;
58*33b1fccfSAndroid Build Coastguard Worker }
59*33b1fccfSAndroid Build Coastguard Worker
60*33b1fccfSAndroid Build Coastguard Worker #define HASHMAP_INITIAL_SIZE 64
61*33b1fccfSAndroid Build Coastguard Worker /* grow / shrink by 2^2 */
62*33b1fccfSAndroid Build Coastguard Worker #define HASHMAP_RESIZE_BITS 2
63*33b1fccfSAndroid Build Coastguard Worker /* load factor in percent */
64*33b1fccfSAndroid Build Coastguard Worker #define HASHMAP_LOAD_FACTOR 80
65*33b1fccfSAndroid Build Coastguard Worker
alloc_table(struct hashmap * map,unsigned int size)66*33b1fccfSAndroid Build Coastguard Worker static void alloc_table(struct hashmap *map, unsigned int size)
67*33b1fccfSAndroid Build Coastguard Worker {
68*33b1fccfSAndroid Build Coastguard Worker map->tablesize = size;
69*33b1fccfSAndroid Build Coastguard Worker map->table = calloc(size, sizeof(struct hashmap_entry *));
70*33b1fccfSAndroid Build Coastguard Worker BUG_ON(!map->table);
71*33b1fccfSAndroid Build Coastguard Worker
72*33b1fccfSAndroid Build Coastguard Worker /* calculate resize thresholds for new size */
73*33b1fccfSAndroid Build Coastguard Worker map->grow_at = (unsigned int)((uint64_t)size * HASHMAP_LOAD_FACTOR / 100);
74*33b1fccfSAndroid Build Coastguard Worker if (size <= HASHMAP_INITIAL_SIZE)
75*33b1fccfSAndroid Build Coastguard Worker map->shrink_at = 0;
76*33b1fccfSAndroid Build Coastguard Worker else
77*33b1fccfSAndroid Build Coastguard Worker /*
78*33b1fccfSAndroid Build Coastguard Worker * The shrink-threshold must be slightly smaller than
79*33b1fccfSAndroid Build Coastguard Worker * (grow-threshold / resize-factor) to prevent erratic resizing,
80*33b1fccfSAndroid Build Coastguard Worker * thus we divide by (resize-factor + 1).
81*33b1fccfSAndroid Build Coastguard Worker */
82*33b1fccfSAndroid Build Coastguard Worker map->shrink_at = map->grow_at / ((1 << HASHMAP_RESIZE_BITS) + 1);
83*33b1fccfSAndroid Build Coastguard Worker }
84*33b1fccfSAndroid Build Coastguard Worker
entry_equals(const struct hashmap * map,const struct hashmap_entry * e1,const struct hashmap_entry * e2,const void * keydata)85*33b1fccfSAndroid Build Coastguard Worker static inline int entry_equals(const struct hashmap *map,
86*33b1fccfSAndroid Build Coastguard Worker const struct hashmap_entry *e1,
87*33b1fccfSAndroid Build Coastguard Worker const struct hashmap_entry *e2,
88*33b1fccfSAndroid Build Coastguard Worker const void *keydata)
89*33b1fccfSAndroid Build Coastguard Worker {
90*33b1fccfSAndroid Build Coastguard Worker return (e1 == e2) || (e1->hash == e2->hash && !map->cmpfn(e1, e2, keydata));
91*33b1fccfSAndroid Build Coastguard Worker }
92*33b1fccfSAndroid Build Coastguard Worker
bucket(const struct hashmap * map,const struct hashmap_entry * key)93*33b1fccfSAndroid Build Coastguard Worker static inline unsigned int bucket(const struct hashmap *map,
94*33b1fccfSAndroid Build Coastguard Worker const struct hashmap_entry *key)
95*33b1fccfSAndroid Build Coastguard Worker {
96*33b1fccfSAndroid Build Coastguard Worker return key->hash & (map->tablesize - 1);
97*33b1fccfSAndroid Build Coastguard Worker }
98*33b1fccfSAndroid Build Coastguard Worker
rehash(struct hashmap * map,unsigned int newsize)99*33b1fccfSAndroid Build Coastguard Worker static void rehash(struct hashmap *map, unsigned int newsize)
100*33b1fccfSAndroid Build Coastguard Worker {
101*33b1fccfSAndroid Build Coastguard Worker unsigned int i, oldsize = map->tablesize;
102*33b1fccfSAndroid Build Coastguard Worker struct hashmap_entry **oldtable = map->table;
103*33b1fccfSAndroid Build Coastguard Worker
104*33b1fccfSAndroid Build Coastguard Worker alloc_table(map, newsize);
105*33b1fccfSAndroid Build Coastguard Worker for (i = 0; i < oldsize; i++) {
106*33b1fccfSAndroid Build Coastguard Worker struct hashmap_entry *e = oldtable[i];
107*33b1fccfSAndroid Build Coastguard Worker
108*33b1fccfSAndroid Build Coastguard Worker while (e) {
109*33b1fccfSAndroid Build Coastguard Worker struct hashmap_entry *next = e->next;
110*33b1fccfSAndroid Build Coastguard Worker unsigned int b = bucket(map, e);
111*33b1fccfSAndroid Build Coastguard Worker
112*33b1fccfSAndroid Build Coastguard Worker e->next = map->table[b];
113*33b1fccfSAndroid Build Coastguard Worker map->table[b] = e;
114*33b1fccfSAndroid Build Coastguard Worker e = next;
115*33b1fccfSAndroid Build Coastguard Worker }
116*33b1fccfSAndroid Build Coastguard Worker }
117*33b1fccfSAndroid Build Coastguard Worker free(oldtable);
118*33b1fccfSAndroid Build Coastguard Worker }
119*33b1fccfSAndroid Build Coastguard Worker
find_entry_ptr(const struct hashmap * map,const struct hashmap_entry * key,const void * keydata)120*33b1fccfSAndroid Build Coastguard Worker static inline struct hashmap_entry **find_entry_ptr(const struct hashmap *map,
121*33b1fccfSAndroid Build Coastguard Worker const struct hashmap_entry *key,
122*33b1fccfSAndroid Build Coastguard Worker const void *keydata)
123*33b1fccfSAndroid Build Coastguard Worker {
124*33b1fccfSAndroid Build Coastguard Worker struct hashmap_entry **e = &map->table[bucket(map, key)];
125*33b1fccfSAndroid Build Coastguard Worker
126*33b1fccfSAndroid Build Coastguard Worker while (*e && !entry_equals(map, *e, key, keydata))
127*33b1fccfSAndroid Build Coastguard Worker e = &(*e)->next;
128*33b1fccfSAndroid Build Coastguard Worker return e;
129*33b1fccfSAndroid Build Coastguard Worker }
130*33b1fccfSAndroid Build Coastguard Worker
always_equal(const void * unused1,const void * unused2,const void * unused3)131*33b1fccfSAndroid Build Coastguard Worker static int always_equal(const void *unused1, const void *unused2, const void *unused3)
132*33b1fccfSAndroid Build Coastguard Worker {
133*33b1fccfSAndroid Build Coastguard Worker return 0;
134*33b1fccfSAndroid Build Coastguard Worker }
135*33b1fccfSAndroid Build Coastguard Worker
hashmap_init(struct hashmap * map,hashmap_cmp_fn equals_function,size_t initial_size)136*33b1fccfSAndroid Build Coastguard Worker void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,
137*33b1fccfSAndroid Build Coastguard Worker size_t initial_size)
138*33b1fccfSAndroid Build Coastguard Worker {
139*33b1fccfSAndroid Build Coastguard Worker unsigned int size = HASHMAP_INITIAL_SIZE;
140*33b1fccfSAndroid Build Coastguard Worker
141*33b1fccfSAndroid Build Coastguard Worker map->size = 0;
142*33b1fccfSAndroid Build Coastguard Worker map->cmpfn = equals_function ? equals_function : always_equal;
143*33b1fccfSAndroid Build Coastguard Worker
144*33b1fccfSAndroid Build Coastguard Worker /* calculate initial table size and allocate the table */
145*33b1fccfSAndroid Build Coastguard Worker initial_size = (unsigned int)((uint64_t)initial_size * 100
146*33b1fccfSAndroid Build Coastguard Worker / HASHMAP_LOAD_FACTOR);
147*33b1fccfSAndroid Build Coastguard Worker while (initial_size > size)
148*33b1fccfSAndroid Build Coastguard Worker size <<= HASHMAP_RESIZE_BITS;
149*33b1fccfSAndroid Build Coastguard Worker alloc_table(map, size);
150*33b1fccfSAndroid Build Coastguard Worker }
151*33b1fccfSAndroid Build Coastguard Worker
hashmap_free(struct hashmap * map)152*33b1fccfSAndroid Build Coastguard Worker int hashmap_free(struct hashmap *map)
153*33b1fccfSAndroid Build Coastguard Worker {
154*33b1fccfSAndroid Build Coastguard Worker if (map && map->table) {
155*33b1fccfSAndroid Build Coastguard Worker struct hashmap_iter iter;
156*33b1fccfSAndroid Build Coastguard Worker struct hashmap_entry *e;
157*33b1fccfSAndroid Build Coastguard Worker
158*33b1fccfSAndroid Build Coastguard Worker hashmap_iter_init(map, &iter);
159*33b1fccfSAndroid Build Coastguard Worker e = hashmap_iter_next(&iter);
160*33b1fccfSAndroid Build Coastguard Worker if (e)
161*33b1fccfSAndroid Build Coastguard Worker return -EBUSY;
162*33b1fccfSAndroid Build Coastguard Worker
163*33b1fccfSAndroid Build Coastguard Worker free(map->table);
164*33b1fccfSAndroid Build Coastguard Worker memset(map, 0, sizeof(*map));
165*33b1fccfSAndroid Build Coastguard Worker }
166*33b1fccfSAndroid Build Coastguard Worker return 0;
167*33b1fccfSAndroid Build Coastguard Worker }
168*33b1fccfSAndroid Build Coastguard Worker
hashmap_get(const struct hashmap * map,const void * key,const void * keydata)169*33b1fccfSAndroid Build Coastguard Worker void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)
170*33b1fccfSAndroid Build Coastguard Worker {
171*33b1fccfSAndroid Build Coastguard Worker return *find_entry_ptr(map, key, keydata);
172*33b1fccfSAndroid Build Coastguard Worker }
173*33b1fccfSAndroid Build Coastguard Worker
hashmap_get_next(const struct hashmap * map,const void * entry)174*33b1fccfSAndroid Build Coastguard Worker void *hashmap_get_next(const struct hashmap *map, const void *entry)
175*33b1fccfSAndroid Build Coastguard Worker {
176*33b1fccfSAndroid Build Coastguard Worker struct hashmap_entry *e = ((struct hashmap_entry *)entry)->next;
177*33b1fccfSAndroid Build Coastguard Worker
178*33b1fccfSAndroid Build Coastguard Worker for (; e; e = e->next)
179*33b1fccfSAndroid Build Coastguard Worker if (entry_equals(map, entry, e, NULL))
180*33b1fccfSAndroid Build Coastguard Worker return e;
181*33b1fccfSAndroid Build Coastguard Worker return NULL;
182*33b1fccfSAndroid Build Coastguard Worker }
183*33b1fccfSAndroid Build Coastguard Worker
hashmap_add(struct hashmap * map,void * entry)184*33b1fccfSAndroid Build Coastguard Worker void hashmap_add(struct hashmap *map, void *entry)
185*33b1fccfSAndroid Build Coastguard Worker {
186*33b1fccfSAndroid Build Coastguard Worker unsigned int b = bucket(map, entry);
187*33b1fccfSAndroid Build Coastguard Worker
188*33b1fccfSAndroid Build Coastguard Worker /* add entry */
189*33b1fccfSAndroid Build Coastguard Worker ((struct hashmap_entry *)entry)->next = map->table[b];
190*33b1fccfSAndroid Build Coastguard Worker map->table[b] = entry;
191*33b1fccfSAndroid Build Coastguard Worker
192*33b1fccfSAndroid Build Coastguard Worker /* fix size and rehash if appropriate */
193*33b1fccfSAndroid Build Coastguard Worker map->size++;
194*33b1fccfSAndroid Build Coastguard Worker if (map->size > map->grow_at)
195*33b1fccfSAndroid Build Coastguard Worker rehash(map, map->tablesize << HASHMAP_RESIZE_BITS);
196*33b1fccfSAndroid Build Coastguard Worker }
197*33b1fccfSAndroid Build Coastguard Worker
hashmap_remove(struct hashmap * map,const void * entry)198*33b1fccfSAndroid Build Coastguard Worker void *hashmap_remove(struct hashmap *map, const void *entry)
199*33b1fccfSAndroid Build Coastguard Worker {
200*33b1fccfSAndroid Build Coastguard Worker struct hashmap_entry *old;
201*33b1fccfSAndroid Build Coastguard Worker struct hashmap_entry **e = &map->table[bucket(map, entry)];
202*33b1fccfSAndroid Build Coastguard Worker
203*33b1fccfSAndroid Build Coastguard Worker while (*e && *e != entry)
204*33b1fccfSAndroid Build Coastguard Worker e = &(*e)->next;
205*33b1fccfSAndroid Build Coastguard Worker
206*33b1fccfSAndroid Build Coastguard Worker if (!*e)
207*33b1fccfSAndroid Build Coastguard Worker return NULL;
208*33b1fccfSAndroid Build Coastguard Worker
209*33b1fccfSAndroid Build Coastguard Worker /* remove existing entry */
210*33b1fccfSAndroid Build Coastguard Worker old = *e;
211*33b1fccfSAndroid Build Coastguard Worker *e = old->next;
212*33b1fccfSAndroid Build Coastguard Worker old->next = NULL;
213*33b1fccfSAndroid Build Coastguard Worker
214*33b1fccfSAndroid Build Coastguard Worker /* fix size and rehash if appropriate */
215*33b1fccfSAndroid Build Coastguard Worker map->size--;
216*33b1fccfSAndroid Build Coastguard Worker if (map->size < map->shrink_at)
217*33b1fccfSAndroid Build Coastguard Worker rehash(map, map->tablesize >> HASHMAP_RESIZE_BITS);
218*33b1fccfSAndroid Build Coastguard Worker return old;
219*33b1fccfSAndroid Build Coastguard Worker }
220*33b1fccfSAndroid Build Coastguard Worker
hashmap_iter_init(struct hashmap * map,struct hashmap_iter * iter)221*33b1fccfSAndroid Build Coastguard Worker void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)
222*33b1fccfSAndroid Build Coastguard Worker {
223*33b1fccfSAndroid Build Coastguard Worker iter->map = map;
224*33b1fccfSAndroid Build Coastguard Worker iter->tablepos = 0;
225*33b1fccfSAndroid Build Coastguard Worker iter->next = NULL;
226*33b1fccfSAndroid Build Coastguard Worker }
227*33b1fccfSAndroid Build Coastguard Worker
hashmap_iter_next(struct hashmap_iter * iter)228*33b1fccfSAndroid Build Coastguard Worker void *hashmap_iter_next(struct hashmap_iter *iter)
229*33b1fccfSAndroid Build Coastguard Worker {
230*33b1fccfSAndroid Build Coastguard Worker struct hashmap_entry *current = iter->next;
231*33b1fccfSAndroid Build Coastguard Worker
232*33b1fccfSAndroid Build Coastguard Worker for (;;) {
233*33b1fccfSAndroid Build Coastguard Worker if (current) {
234*33b1fccfSAndroid Build Coastguard Worker iter->next = current->next;
235*33b1fccfSAndroid Build Coastguard Worker return current;
236*33b1fccfSAndroid Build Coastguard Worker }
237*33b1fccfSAndroid Build Coastguard Worker
238*33b1fccfSAndroid Build Coastguard Worker if (iter->tablepos >= iter->map->tablesize)
239*33b1fccfSAndroid Build Coastguard Worker return NULL;
240*33b1fccfSAndroid Build Coastguard Worker
241*33b1fccfSAndroid Build Coastguard Worker current = iter->map->table[iter->tablepos++];
242*33b1fccfSAndroid Build Coastguard Worker }
243*33b1fccfSAndroid Build Coastguard Worker }
244*33b1fccfSAndroid Build Coastguard Worker
245*33b1fccfSAndroid Build Coastguard Worker struct pool_entry {
246*33b1fccfSAndroid Build Coastguard Worker struct hashmap_entry ent;
247*33b1fccfSAndroid Build Coastguard Worker size_t len;
248*33b1fccfSAndroid Build Coastguard Worker unsigned char data[FLEX_ARRAY];
249*33b1fccfSAndroid Build Coastguard Worker };
250*33b1fccfSAndroid Build Coastguard Worker
pool_entry_cmp(const struct pool_entry * e1,const struct pool_entry * e2,const unsigned char * keydata)251*33b1fccfSAndroid Build Coastguard Worker static int pool_entry_cmp(const struct pool_entry *e1,
252*33b1fccfSAndroid Build Coastguard Worker const struct pool_entry *e2,
253*33b1fccfSAndroid Build Coastguard Worker const unsigned char *keydata)
254*33b1fccfSAndroid Build Coastguard Worker {
255*33b1fccfSAndroid Build Coastguard Worker return e1->data != keydata &&
256*33b1fccfSAndroid Build Coastguard Worker (e1->len != e2->len || memcmp(e1->data, keydata, e1->len));
257*33b1fccfSAndroid Build Coastguard Worker }
258*33b1fccfSAndroid Build Coastguard Worker
memintern(const void * data,size_t len)259*33b1fccfSAndroid Build Coastguard Worker const void *memintern(const void *data, size_t len)
260*33b1fccfSAndroid Build Coastguard Worker {
261*33b1fccfSAndroid Build Coastguard Worker static struct hashmap map;
262*33b1fccfSAndroid Build Coastguard Worker struct pool_entry key, *e;
263*33b1fccfSAndroid Build Coastguard Worker
264*33b1fccfSAndroid Build Coastguard Worker /* initialize string pool hashmap */
265*33b1fccfSAndroid Build Coastguard Worker if (!map.tablesize)
266*33b1fccfSAndroid Build Coastguard Worker hashmap_init(&map, (hashmap_cmp_fn)pool_entry_cmp, 0);
267*33b1fccfSAndroid Build Coastguard Worker
268*33b1fccfSAndroid Build Coastguard Worker /* lookup interned string in pool */
269*33b1fccfSAndroid Build Coastguard Worker hashmap_entry_init(&key, memhash(data, len));
270*33b1fccfSAndroid Build Coastguard Worker key.len = len;
271*33b1fccfSAndroid Build Coastguard Worker e = hashmap_get(&map, &key, data);
272*33b1fccfSAndroid Build Coastguard Worker if (!e) {
273*33b1fccfSAndroid Build Coastguard Worker /* not found: create it */
274*33b1fccfSAndroid Build Coastguard Worker FLEX_ALLOC_MEM(e, data, data, len);
275*33b1fccfSAndroid Build Coastguard Worker hashmap_entry_init(e, key.ent.hash);
276*33b1fccfSAndroid Build Coastguard Worker e->len = len;
277*33b1fccfSAndroid Build Coastguard Worker hashmap_add(&map, e);
278*33b1fccfSAndroid Build Coastguard Worker }
279*33b1fccfSAndroid Build Coastguard Worker return e->data;
280*33b1fccfSAndroid Build Coastguard Worker }
281