1 /* SPDX-License-Identifier: GPL-2.0 */
2 #ifndef __EROFS_HASHMAP_H
3 #define __EROFS_HASHMAP_H
4
5 #ifdef __cplusplus
6 extern "C"
7 {
8 #endif
9
10 /* Copied from https://github.com/git/git.git */
11 #include <stdio.h>
12 #include <stdlib.h>
13 #include <string.h>
14
15 #include "flex-array.h"
16
17 /*
18 * Generic implementation of hash-based key-value mappings.
19 * See Documentation/technical/api-hashmap.txt.
20 */
21
22 /* FNV-1 functions */
23 unsigned int strhash(const char *str);
24 unsigned int strihash(const char *str);
25 unsigned int memhash(const void *buf, size_t len);
26 unsigned int memihash(const void *buf, size_t len);
27
sha1hash(const unsigned char * sha1)28 static inline unsigned int sha1hash(const unsigned char *sha1)
29 {
30 /*
31 * Equivalent to 'return *(unsigned int *)sha1;', but safe on
32 * platforms that don't support unaligned reads.
33 */
34 unsigned int hash;
35
36 memcpy(&hash, sha1, sizeof(hash));
37 return hash;
38 }
39
40 /* data structures */
41 struct hashmap_entry {
42 struct hashmap_entry *next;
43 unsigned int hash;
44 };
45
46 typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key,
47 const void *keydata);
48
49 struct hashmap {
50 struct hashmap_entry **table;
51 hashmap_cmp_fn cmpfn;
52 unsigned int size, tablesize, grow_at, shrink_at;
53 };
54
55 struct hashmap_iter {
56 struct hashmap *map;
57 struct hashmap_entry *next;
58 unsigned int tablepos;
59 };
60
61 /* hashmap functions */
62 void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,
63 size_t initial_size);
64 int hashmap_free(struct hashmap *map);
65
66 /* hashmap_entry functions */
hashmap_entry_init(void * entry,unsigned int hash)67 static inline void hashmap_entry_init(void *entry, unsigned int hash)
68 {
69 struct hashmap_entry *e = entry;
70
71 e->hash = hash;
72 e->next = NULL;
73 }
74
75 void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata);
76 void *hashmap_get_next(const struct hashmap *map, const void *entry);
77 void hashmap_add(struct hashmap *map, void *entry);
78 void *hashmap_remove(struct hashmap *map, const void *key);
79
hashmap_get_from_hash(const struct hashmap * map,unsigned int hash,const void * keydata)80 static inline void *hashmap_get_from_hash(const struct hashmap *map,
81 unsigned int hash,
82 const void *keydata)
83 {
84 struct hashmap_entry key;
85
86 hashmap_entry_init(&key, hash);
87 return hashmap_get(map, &key, keydata);
88 }
89
90 /* hashmap_iter functions */
91 void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);
92 void *hashmap_iter_next(struct hashmap_iter *iter);
hashmap_iter_first(struct hashmap * map,struct hashmap_iter * iter)93 static inline void *hashmap_iter_first(struct hashmap *map,
94 struct hashmap_iter *iter)
95 {
96 hashmap_iter_init(map, iter);
97 return hashmap_iter_next(iter);
98 }
99
hashmap_disable_shrink(struct hashmap * map)100 static inline void hashmap_disable_shrink(struct hashmap * map)
101 {
102 map->shrink_at = 0;
103 }
104 /* string interning */
105 const void *memintern(const void *data, size_t len);
strintern(const char * string)106 static inline const char *strintern(const char *string)
107 {
108 return memintern(string, strlen(string));
109 }
110
111 #ifdef __cplusplus
112 }
113 #endif
114
115 #endif
116