]>
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; | |
0607e100 | 42 | unsigned disallow_rehash : 1; |
6a364ced KB |
43 | }; |
44 | ||
45 | struct hashmap_iter { | |
46 | struct hashmap *map; | |
47 | struct hashmap_entry *next; | |
48 | unsigned int tablepos; | |
49 | }; | |
50 | ||
51 | /* hashmap functions */ | |
52 | ||
53 | extern void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, | |
54 | size_t initial_size); | |
55 | extern void hashmap_free(struct hashmap *map, int free_entries); | |
56 | ||
57 | /* hashmap_entry functions */ | |
58 | ||
b6aad994 | 59 | static inline void hashmap_entry_init(void *entry, unsigned int hash) |
6a364ced KB |
60 | { |
61 | struct hashmap_entry *e = entry; | |
62 | e->hash = hash; | |
63 | e->next = NULL; | |
64 | } | |
65 | extern void *hashmap_get(const struct hashmap *map, const void *key, | |
66 | const void *keydata); | |
67 | extern void *hashmap_get_next(const struct hashmap *map, const void *entry); | |
68 | extern void hashmap_add(struct hashmap *map, void *entry); | |
69 | extern void *hashmap_put(struct hashmap *map, void *entry); | |
70 | extern void *hashmap_remove(struct hashmap *map, const void *key, | |
71 | const void *keydata); | |
72 | ||
ab73a9d1 KB |
73 | static inline void *hashmap_get_from_hash(const struct hashmap *map, |
74 | unsigned int hash, const void *keydata) | |
75 | { | |
76 | struct hashmap_entry key; | |
77 | hashmap_entry_init(&key, hash); | |
78 | return hashmap_get(map, &key, keydata); | |
79 | } | |
80 | ||
0607e100 JH |
81 | int hashmap_bucket(const struct hashmap *map, unsigned int hash); |
82 | ||
83 | /* | |
84 | * Disallow/allow rehashing of the hashmap. | |
85 | * This is useful if the caller knows that the hashmap | |
86 | * needs multi-threaded access. The caller is still | |
87 | * required to guard/lock searches and inserts in a | |
88 | * manner appropriate to their usage. This simply | |
89 | * prevents the table from being unexpectedly re-mapped. | |
90 | * | |
91 | * If is up to the caller to ensure that the hashmap is | |
92 | * initialized to a reasonable size to prevent poor | |
93 | * performance. | |
94 | * | |
95 | * When value=1, prevent future rehashes on adds and deleted. | |
96 | * When value=0, allow future rehahses. This DOES NOT force | |
97 | * a rehash now. | |
98 | */ | |
99 | static inline void hashmap_disallow_rehash(struct hashmap *map, unsigned value) | |
100 | { | |
101 | map->disallow_rehash = value; | |
102 | } | |
103 | ||
6a364ced KB |
104 | /* hashmap_iter functions */ |
105 | ||
106 | extern void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter); | |
107 | extern void *hashmap_iter_next(struct hashmap_iter *iter); | |
108 | static inline void *hashmap_iter_first(struct hashmap *map, | |
109 | struct hashmap_iter *iter) | |
110 | { | |
111 | hashmap_iter_init(map, iter); | |
112 | return hashmap_iter_next(iter); | |
113 | } | |
114 | ||
7b64d42d KB |
115 | /* string interning */ |
116 | ||
117 | extern const void *memintern(const void *data, size_t len); | |
118 | static inline const char *strintern(const char *string) | |
119 | { | |
120 | return memintern(string, strlen(string)); | |
121 | } | |
122 | ||
6a364ced | 123 | #endif |