]>
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 | ||
35 | typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key, | |
36 | const void *keydata); | |
37 | ||
38 | struct hashmap { | |
39 | struct hashmap_entry **table; | |
40 | hashmap_cmp_fn cmpfn; | |
41 | unsigned int size, tablesize, grow_at, shrink_at; | |
42 | }; | |
43 | ||
44 | struct hashmap_iter { | |
45 | struct hashmap *map; | |
46 | struct hashmap_entry *next; | |
47 | unsigned int tablepos; | |
48 | }; | |
49 | ||
50 | /* hashmap functions */ | |
51 | ||
52 | extern void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, | |
53 | size_t initial_size); | |
54 | extern void hashmap_free(struct hashmap *map, int free_entries); | |
55 | ||
56 | /* hashmap_entry functions */ | |
57 | ||
b6aad994 | 58 | static inline void hashmap_entry_init(void *entry, unsigned int hash) |
6a364ced KB |
59 | { |
60 | struct hashmap_entry *e = entry; | |
61 | e->hash = hash; | |
62 | e->next = NULL; | |
63 | } | |
64 | extern void *hashmap_get(const struct hashmap *map, const void *key, | |
65 | const void *keydata); | |
66 | extern void *hashmap_get_next(const struct hashmap *map, const void *entry); | |
67 | extern void hashmap_add(struct hashmap *map, void *entry); | |
68 | extern void *hashmap_put(struct hashmap *map, void *entry); | |
69 | extern void *hashmap_remove(struct hashmap *map, const void *key, | |
70 | const void *keydata); | |
71 | ||
ab73a9d1 KB |
72 | static inline void *hashmap_get_from_hash(const struct hashmap *map, |
73 | unsigned int hash, const void *keydata) | |
74 | { | |
75 | struct hashmap_entry key; | |
76 | hashmap_entry_init(&key, hash); | |
77 | return hashmap_get(map, &key, keydata); | |
78 | } | |
79 | ||
6a364ced KB |
80 | /* hashmap_iter functions */ |
81 | ||
82 | extern void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter); | |
83 | extern void *hashmap_iter_next(struct hashmap_iter *iter); | |
84 | static inline void *hashmap_iter_first(struct hashmap *map, | |
85 | struct hashmap_iter *iter) | |
86 | { | |
87 | hashmap_iter_init(map, iter); | |
88 | return hashmap_iter_next(iter); | |
89 | } | |
90 | ||
7b64d42d KB |
91 | /* string interning */ |
92 | ||
93 | extern const void *memintern(const void *data, size_t len); | |
94 | static inline const char *strintern(const char *string) | |
95 | { | |
96 | return memintern(string, strlen(string)); | |
97 | } | |
98 | ||
6a364ced | 99 | #endif |