]>
Commit | Line | Data |
---|---|---|
6a364ced KB |
1 | #ifndef HASHMAP_H |
2 | #define HASHMAP_H | |
3 | ||
4 | /* | |
5 | * Generic implementation of hash-based key-value mappings. | |
6 | * See Documentation/technical/api-hashmap.txt. | |
7 | */ | |
8 | ||
9 | /* FNV-1 functions */ | |
10 | ||
11 | extern unsigned int strhash(const char *buf); | |
12 | extern unsigned int strihash(const char *buf); | |
13 | extern unsigned int memhash(const void *buf, size_t len); | |
14 | extern unsigned int memihash(const void *buf, size_t len); | |
f75619bd | 15 | extern unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len); |
6a364ced | 16 | |
039dc71a KB |
17 | static inline unsigned int sha1hash(const unsigned char *sha1) |
18 | { | |
19 | /* | |
20 | * Equivalent to 'return *(unsigned int *)sha1;', but safe on | |
21 | * platforms that don't support unaligned reads. | |
22 | */ | |
23 | unsigned int hash; | |
24 | memcpy(&hash, sha1, sizeof(hash)); | |
25 | return hash; | |
26 | } | |
27 | ||
6a364ced KB |
28 | /* data structures */ |
29 | ||
30 | struct hashmap_entry { | |
31 | struct hashmap_entry *next; | |
32 | unsigned int hash; | |
33 | }; | |
34 | ||
7663cdc8 SB |
35 | typedef int (*hashmap_cmp_fn)(const void *hashmap_cmp_fn_data, |
36 | const void *entry, const void *entry_or_key, | |
37 | const void *keydata); | |
6a364ced KB |
38 | |
39 | struct hashmap { | |
40 | struct hashmap_entry **table; | |
41 | hashmap_cmp_fn cmpfn; | |
7663cdc8 | 42 | const void *cmpfn_data; |
6a364ced | 43 | unsigned int size, tablesize, grow_at, shrink_at; |
0607e100 | 44 | unsigned disallow_rehash : 1; |
6a364ced KB |
45 | }; |
46 | ||
47 | struct hashmap_iter { | |
48 | struct hashmap *map; | |
49 | struct hashmap_entry *next; | |
50 | unsigned int tablepos; | |
51 | }; | |
52 | ||
53 | /* hashmap functions */ | |
54 | ||
7663cdc8 SB |
55 | extern void hashmap_init(struct hashmap *map, |
56 | hashmap_cmp_fn equals_function, | |
57 | const void *equals_function_data, | |
58 | size_t initial_size); | |
6a364ced KB |
59 | extern void hashmap_free(struct hashmap *map, int free_entries); |
60 | ||
61 | /* hashmap_entry functions */ | |
62 | ||
b6aad994 | 63 | static inline void hashmap_entry_init(void *entry, unsigned int hash) |
6a364ced KB |
64 | { |
65 | struct hashmap_entry *e = entry; | |
66 | e->hash = hash; | |
67 | e->next = NULL; | |
68 | } | |
69 | extern void *hashmap_get(const struct hashmap *map, const void *key, | |
70 | const void *keydata); | |
71 | extern void *hashmap_get_next(const struct hashmap *map, const void *entry); | |
72 | extern void hashmap_add(struct hashmap *map, void *entry); | |
73 | extern void *hashmap_put(struct hashmap *map, void *entry); | |
74 | extern void *hashmap_remove(struct hashmap *map, const void *key, | |
75 | const void *keydata); | |
76 | ||
ab73a9d1 KB |
77 | static inline void *hashmap_get_from_hash(const struct hashmap *map, |
78 | unsigned int hash, const void *keydata) | |
79 | { | |
80 | struct hashmap_entry key; | |
81 | hashmap_entry_init(&key, hash); | |
82 | return hashmap_get(map, &key, keydata); | |
83 | } | |
84 | ||
0607e100 JH |
85 | int hashmap_bucket(const struct hashmap *map, unsigned int hash); |
86 | ||
87 | /* | |
88 | * Disallow/allow rehashing of the hashmap. | |
89 | * This is useful if the caller knows that the hashmap | |
90 | * needs multi-threaded access. The caller is still | |
91 | * required to guard/lock searches and inserts in a | |
92 | * manner appropriate to their usage. This simply | |
93 | * prevents the table from being unexpectedly re-mapped. | |
94 | * | |
95 | * If is up to the caller to ensure that the hashmap is | |
96 | * initialized to a reasonable size to prevent poor | |
97 | * performance. | |
98 | * | |
99 | * When value=1, prevent future rehashes on adds and deleted. | |
100 | * When value=0, allow future rehahses. This DOES NOT force | |
101 | * a rehash now. | |
102 | */ | |
103 | static inline void hashmap_disallow_rehash(struct hashmap *map, unsigned value) | |
104 | { | |
105 | map->disallow_rehash = value; | |
106 | } | |
107 | ||
6a364ced KB |
108 | /* hashmap_iter functions */ |
109 | ||
110 | extern void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter); | |
111 | extern void *hashmap_iter_next(struct hashmap_iter *iter); | |
112 | static inline void *hashmap_iter_first(struct hashmap *map, | |
113 | struct hashmap_iter *iter) | |
114 | { | |
115 | hashmap_iter_init(map, iter); | |
116 | return hashmap_iter_next(iter); | |
117 | } | |
118 | ||
7b64d42d KB |
119 | /* string interning */ |
120 | ||
121 | extern const void *memintern(const void *data, size_t len); | |
122 | static inline const char *strintern(const char *string) | |
123 | { | |
124 | return memintern(string, strlen(string)); | |
125 | } | |
126 | ||
6a364ced | 127 | #endif |