Merge commit 'refs/top-bases/t/misc/blob_plain-charset' into t/misc/blob_plain-charset
[git/gitweb.git] / hashmap.h
blobab7958ae333bcc635ba2ac8e40ee8aa6d8814ab4
1 #ifndef HASHMAP_H
2 #define HASHMAP_H
4 /*
5 * Generic implementation of hash-based key-value mappings.
6 * See Documentation/technical/api-hashmap.txt.
7 */
9 /* FNV-1 functions */
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);
16 static inline unsigned int sha1hash(const unsigned char *sha1)
19 * Equivalent to 'return *(unsigned int *)sha1;', but safe on
20 * platforms that don't support unaligned reads.
22 unsigned int hash;
23 memcpy(&hash, sha1, sizeof(hash));
24 return hash;
27 /* data structures */
29 struct hashmap_entry {
30 struct hashmap_entry *next;
31 unsigned int hash;
34 typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key,
35 const void *keydata);
37 struct hashmap {
38 struct hashmap_entry **table;
39 hashmap_cmp_fn cmpfn;
40 unsigned int size, tablesize, grow_at, shrink_at;
43 struct hashmap_iter {
44 struct hashmap *map;
45 struct hashmap_entry *next;
46 unsigned int tablepos;
49 /* hashmap functions */
51 extern void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,
52 size_t initial_size);
53 extern void hashmap_free(struct hashmap *map, int free_entries);
55 /* hashmap_entry functions */
57 static inline void hashmap_entry_init(void *entry, unsigned int hash)
59 struct hashmap_entry *e = entry;
60 e->hash = hash;
61 e->next = NULL;
63 extern void *hashmap_get(const struct hashmap *map, const void *key,
64 const void *keydata);
65 extern void *hashmap_get_next(const struct hashmap *map, const void *entry);
66 extern void hashmap_add(struct hashmap *map, void *entry);
67 extern void *hashmap_put(struct hashmap *map, void *entry);
68 extern void *hashmap_remove(struct hashmap *map, const void *key,
69 const void *keydata);
71 static inline void *hashmap_get_from_hash(const struct hashmap *map,
72 unsigned int hash, const void *keydata)
74 struct hashmap_entry key;
75 hashmap_entry_init(&key, hash);
76 return hashmap_get(map, &key, keydata);
79 /* hashmap_iter functions */
81 extern void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);
82 extern void *hashmap_iter_next(struct hashmap_iter *iter);
83 static inline void *hashmap_iter_first(struct hashmap *map,
84 struct hashmap_iter *iter)
86 hashmap_iter_init(map, iter);
87 return hashmap_iter_next(iter);
90 /* string interning */
92 extern const void *memintern(const void *data, size_t len);
93 static inline const char *strintern(const char *string)
95 return memintern(string, strlen(string));
98 #endif