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 void hashmap_free(struct hashmap *map, int free_entries);
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_put(struct hashmap *map, void *entry);
79 void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata);
80
hashmap_get_from_hash(const struct hashmap * map,unsigned int hash,const void * keydata)81 static inline void *hashmap_get_from_hash(const struct hashmap *map,
82 unsigned int hash,
83 const void *keydata)
84 {
85 struct hashmap_entry key;
86
87 hashmap_entry_init(&key, hash);
88 return hashmap_get(map, &key, keydata);
89 }
90
91 /* hashmap_iter functions */
92 void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);
93 void *hashmap_iter_next(struct hashmap_iter *iter);
hashmap_iter_first(struct hashmap * map,struct hashmap_iter * iter)94 static inline void *hashmap_iter_first(struct hashmap *map,
95 struct hashmap_iter *iter)
96 {
97 hashmap_iter_init(map, iter);
98 return hashmap_iter_next(iter);
99 }
100
101 /* string interning */
102 const void *memintern(const void *data, size_t len);
strintern(const char * string)103 static inline const char *strintern(const char *string)
104 {
105 return memintern(string, strlen(string));
106 }
107
108 #ifdef __cplusplus
109 }
110 #endif
111
112 #endif
113