1 /* Copyright 2012-present Facebook, Inc.
2 * Licensed under the Apache License, Version 2.0 */
3
4 #ifndef WATCHMAN_HASH_H
5 #define WATCHMAN_HASH_H
6
7 #ifdef __cplusplus
8 extern "C" {
9 #endif
10
11 struct watchman_hash_table;
12 typedef struct watchman_hash_table w_ht_t;
13
14 /* hash table key/value data type, large enough to hold a pointer
15 * or a 64-bit value */
16 typedef int64_t w_ht_val_t;
17
18 /* safely represent a pointer value as a value stored in the
19 * hash table for both 32- and 64-bit systems */
w_ht_ptr_val(const void * ptr)20 static inline w_ht_val_t w_ht_ptr_val(const void *ptr) {
21 return (w_ht_val_t)(intptr_t)ptr;
22 }
23
24 /* safely represent a hash table value as a pointer value
25 * for both 32- and 64-bit systems */
w_ht_val_ptr(w_ht_val_t val)26 static inline void *w_ht_val_ptr(w_ht_val_t val) {
27 return (void*)(intptr_t)val;
28 }
29
30 /* copies a key. If NULL, simply does a bit copy, but you
31 * can provide an implementation that manages a refcount */
32 typedef w_ht_val_t (*w_hash_table_copy_t)(w_ht_val_t key);
33
34 /* deletes a key. If NULL, simply NOPs, but you can
35 * provide an implementation that manages a refcount */
36 typedef void (*w_hash_table_delete_t)(w_ht_val_t key);
37
38 /* compares a key for equality. If NULL, simply does
39 * a bit compare */
40 typedef bool (*w_hash_table_equal_t)(w_ht_val_t a, w_ht_val_t b);
41
42 /* computes the hash value of a key. If NULL, simply
43 * takes the bit value truncated to 32-bits */
44 typedef uint32_t (*w_hash_table_hash_t)(w_ht_val_t key);
45
46 struct watchman_hash_funcs {
47 w_hash_table_copy_t copy_key;
48 w_hash_table_delete_t del_key;
49 w_hash_table_equal_t equal_key;
50 w_hash_table_hash_t hash_key;
51 w_hash_table_copy_t copy_val;
52 w_hash_table_delete_t del_val;
53 };
54
55 /* create a new hash table.
56 * size_hint is used to pre-allocate the number of buckets
57 * and is useful to reduce realloc() traffic if you know
58 * how big the table is going to be at creation time. */
59 w_ht_t *w_ht_new(uint32_t size_hint, const struct watchman_hash_funcs *funcs);
60
61 /* Destroy a hash table and free all associated resources */
62 void w_ht_free(w_ht_t *ht);
63
64 /* free all the entries but preserve the table size */
65 void w_ht_free_entries(w_ht_t *ht);
66
67 /* equivalent to calling w_ht_insert with replace=false */
68 bool w_ht_set(w_ht_t *ht, w_ht_val_t key, w_ht_val_t value);
69
70 /* equivalent to calling w_ht_insert with replace=true */
71 bool w_ht_replace(w_ht_t *ht, w_ht_val_t key, w_ht_val_t value);
72
73 /* set the value associated with the specified key.
74 * If the element exists already, and replace==false,
75 * returns false and leaves the table unmodified.
76 *
77 * If copy_key is defined, we'll invoke it on the key value IFF we
78 * create a new element in the hash table. If the element already
79 * existed, we'll preserve the key from the prior insert.
80 *
81 * If we're replacing an existing value and del_val is defined,
82 * we'll invoke it on the value that is already present in the table,
83 *
84 * If copy_val is defined, we'll invoke it on the value IFF we
85 * create a new element in the hash table.
86 */
87 bool w_ht_insert(w_ht_t *ht, w_ht_val_t key, w_ht_val_t value, bool replace);
88
89 /* Looks up the value associated with key and returns it.
90 * Returns 0 if there was no matching value.
91 *
92 * If you need to distinguish between no value and the value 0,
93 * use w_ht_lookup instead.
94 *
95 * This function will NOT invoke copy_val on the returned value.
96 */
97 w_ht_val_t w_ht_get(w_ht_t *ht, w_ht_val_t key);
98
99 /* Looks up the value associated with key.
100 * If found, stores the value into *VAL.
101 * If copy==true and copy_val is defined, then it is invoked on the value
102 * prior to storing it to *VAL.
103 * Returns true if the value was found, false otherwise.
104 */
105 bool w_ht_lookup(w_ht_t *ht, w_ht_val_t key, w_ht_val_t *val, bool copy);
106
107 /* Deletes the value associated with key.
108 * If del_val is defined, it is invoked on the value stored in the table.
109 * If del_key is defined, it is invoked on the key stored in the table.
110 * Returns true if the element was present in the table, false otherwise.
111 *
112 * Do not call this function while iteration is in progress.
113 * See w_ht_iter_del().
114 */
115 bool w_ht_del(w_ht_t *ht, w_ht_val_t key);
116
117 /* Returns the number of elements stored in the table */
118 uint32_t w_ht_size(w_ht_t *ht);
119 /* Returns the number of buckets for diagnostic purposes */
120 uint32_t w_ht_num_buckets(w_ht_t *ht);
121
122 typedef struct {
123 w_ht_val_t key;
124 w_ht_val_t value;
125 /* the members following this point are opaque */
126 uint32_t slot;
127 void *ptr;
128 } w_ht_iter_t;
129
130 /* Begin iterating the contents of the hash table.
131 * Usage is:
132 * if (w_ht_first(ht, &iter)) do {
133 * } while (w_ht_next(ht, &iter));
134 *
135 * You may read the contents of iter.key and iter.value.
136 * Note that these expose the raw values stored in the table;
137 * they are not copies managed by the copy_key or copy_val
138 * functions.
139 *
140 * Returns true if iterator holds a value key/value.
141 * Returns false otherwise, indicating that the table is
142 * either NULL or has no contents.
143 *
144 * It is not safe to call w_ht_del() while traversing
145 * the hash table with this function; use w_ht_iter_del()
146 * instead.
147 */
148 bool w_ht_first(w_ht_t *ht, w_ht_iter_t *iter);
149
150 /* Advance to the next element in the table.
151 * Returns false if there are no more elements.
152 * See w_ht_first() for more information */
153 bool w_ht_next(w_ht_t *ht, w_ht_iter_t *iter);
154
155 /* Deletes the value associated with the current
156 * iterator position and updates the iterator
157 * so that the next call to w_ht_next() will see
158 * the next value.
159 * Returns true if successful, false if the iterator
160 * was invalid */
161 bool w_ht_iter_del(w_ht_t *ht, w_ht_iter_t *iter);
162
163
164 /* helper functions for constructing hash tables with string keys */
165 w_ht_val_t w_ht_string_copy(w_ht_val_t val);
166 void w_ht_string_del(w_ht_val_t val);
167 bool w_ht_string_equal(w_ht_val_t a, w_ht_val_t b);
168 uint32_t w_ht_string_hash(w_ht_val_t val);
169
170 /* if you're building a hash table that uses w_string_t as keys,
171 * then you can use w_ht_string_funcs as the second parameter
172 * to w_ht_new to safely reference the keys as the table is updated.
173 */
174 extern const struct watchman_hash_funcs w_ht_string_funcs;
175
176 /* if you're building a hash table that uses w_string_t as values,
177 * then you can use w_ht_string_val_funcs as the second parameter
178 * to w_ht_new to safely reference the values as the table is updated.
179 */
180 extern const struct watchman_hash_funcs w_ht_string_val_funcs;
181
182 /* if you're building a dictionary of string => string,
183 * then you can use w_ht_dict_funcs as the second parameter
184 * to w_ht_new to safely reference the keys and values as the
185 * table is updated
186 */
187 extern const struct watchman_hash_funcs w_ht_dict_funcs;
188
189
190 #ifdef __cplusplus
191 }
192 #endif
193
194 #endif
195
196 /* vim:ts=2:sw=2:et:
197 */
198