1 /*
2 * Copyright (c) 2004-2007 The Trustees of Indiana University and Indiana
3 * University Research and Technology
4 * Corporation. All rights reserved.
5 * Copyright (c) 2004-2005 The University of Tennessee and The University
6 * of Tennessee Research Foundation. All rights
7 * reserved.
8 * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart,
9 * University of Stuttgart. All rights reserved.
10 * Copyright (c) 2004-2005 The Regents of the University of California.
11 * All rights reserved.
12 * Copyright (c) 2015-2017 Intel, Inc. All rights reserved.
13 * Copyright (c) 2015-2016 Research Organization for Information Science
14 * and Technology (RIST). All rights reserved.
15 * Copyright (c) 2016 Mellanox Technologies, Inc.
16 * All rights reserved.
17 *
18 * $COPYRIGHT$
19 *
20 * Additional copyrights may follow
21 *
22 * $HEADER$
23 *
24 */
25
26 /** @file
27 *
28 * A hash table that may be indexed with either fixed length
29 * (e.g. uint32_t/uint64_t) or arbitrary size binary key
30 * values. However, only one key type may be used in a given table
31 * concurrently.
32 */
33
34 #ifndef PMIX_HASH_TABLE_H
35 #define PMIX_HASH_TABLE_H
36
37 #include <src/include/pmix_config.h>
38 #include <src/include/prefetch.h>
39
40 #ifdef HAVE_STDINT_H
41 #include <stdint.h>
42 #endif
43
44 #include "src/class/pmix_list.h"
45
46 #include <pmix_common.h>
47
48 BEGIN_C_DECLS
49
50 PMIX_EXPORT PMIX_CLASS_DECLARATION(pmix_hash_table_t);
51
52 struct pmix_hash_table_t
53 {
54 pmix_object_t super; /**< subclass of pmix_object_t */
55 struct pmix_hash_element_t * ht_table; /**< table of elements (opaque to users) */
56 size_t ht_capacity; /**< allocated size (capacity) of table */
57 size_t ht_size; /**< number of extant entries */
58 size_t ht_growth_trigger; /**< size hits this and table is grown */
59 int ht_density_numer, ht_density_denom; /**< max allowed density of table */
60 int ht_growth_numer, ht_growth_denom; /**< growth factor when grown */
61 const struct pmix_hash_type_methods_t * ht_type_methods;
62 };
63 typedef struct pmix_hash_table_t pmix_hash_table_t;
64
65
66
67 /**
68 * Initializes the table size, must be called before using
69 * the table.
70 *
71 * @param table The input hash table (IN).
72 * @param size The size of the table, which will be rounded up
73 * (if required) to the next highest power of two (IN).
74 * @return PMIX error code.
75 *
76 */
77
78 PMIX_EXPORT int pmix_hash_table_init(pmix_hash_table_t* ht, size_t table_size);
79
80 /* this could be the new init if people wanted a more general API */
81 PMIX_EXPORT int pmix_hash_table_init2(pmix_hash_table_t* ht, size_t estimated_max_size,
82 int density_numer, int density_denom,
83 int growth_numer, int growth_denom);
84
85 /**
86 * Returns the number of elements currently stored in the table.
87 *
88 * @param table The input hash table (IN).
89 * @return The number of elements in the table.
90 *
91 */
92
93 static inline size_t pmix_hash_table_get_size(pmix_hash_table_t *ht)
94 {
95 return ht->ht_size;
96 }
97
98 /**
99 * Remove all elements from the table.
100 *
101 * @param table The input hash table (IN).
102 * @return PMIX return code.
103 *
104 */
105
106 PMIX_EXPORT int pmix_hash_table_remove_all(pmix_hash_table_t *ht);
107
108 /**
109 * Retrieve value via uint32_t key.
110 *
111 * @param table The input hash table (IN).
112 * @param key The input key (IN).
113 * @param ptr The value associated with the key
114 * @return integer return code:
115 * - PMIX_SUCCESS if key was found
116 * - PMIX_ERR_NOT_FOUND if key was not found
117 * - PMIX_ERROR other error
118 *
119 */
120
121 PMIX_EXPORT int pmix_hash_table_get_value_uint32(pmix_hash_table_t* table, uint32_t key,
122 void** ptr);
123
124 /**
125 * Set value based on uint32_t key.
126 *
127 * @param table The input hash table (IN).
128 * @param key The input key (IN).
129 * @param value The value to be associated with the key (IN).
130 * @return PMIX return code.
131 *
132 */
133
134 PMIX_EXPORT int pmix_hash_table_set_value_uint32(pmix_hash_table_t* table, uint32_t key, void* value);
135
136 /**
137 * Remove value based on uint32_t key.
138 *
139 * @param table The input hash table (IN).
140 * @param key The input key (IN).
141 * @return PMIX return code.
142 *
143 */
144
145 PMIX_EXPORT int pmix_hash_table_remove_value_uint32(pmix_hash_table_t* table, uint32_t key);
146
147 /**
148 * Retrieve value via uint64_t key.
149 *
150 * @param table The input hash table (IN).
151 * @param key The input key (IN).
152 * @param ptr The value associated with the key
153 * @return integer return code:
154 * - PMIX_SUCCESS if key was found
155 * - PMIX_ERR_NOT_FOUND if key was not found
156 * - PMIX_ERROR other error
157 *
158 */
159
160 PMIX_EXPORT int pmix_hash_table_get_value_uint64(pmix_hash_table_t *table, uint64_t key,
161 void **ptr);
162
163 /**
164 * Set value based on uint64_t key.
165 *
166 * @param table The input hash table (IN).
167 * @param key The input key (IN).
168 * @param value The value to be associated with the key (IN).
169 * @return PMIX return code.
170 *
171 */
172
173 PMIX_EXPORT int pmix_hash_table_set_value_uint64(pmix_hash_table_t *table, uint64_t key, void* value);
174
175 /**
176 * Remove value based on uint64_t key.
177 *
178 * @param table The input hash table (IN).
179 * @param key The input key (IN).
180 * @return PMIX return code.
181 *
182 */
183
184 PMIX_EXPORT int pmix_hash_table_remove_value_uint64(pmix_hash_table_t *table, uint64_t key);
185
186 /**
187 * Retrieve value via arbitrary length binary key.
188 *
189 * @param table The input hash table (IN).
190 * @param key The input key (IN).
191 * @param ptr The value associated with the key
192 * @return integer return code:
193 * - PMIX_SUCCESS if key was found
194 * - PMIX_ERR_NOT_FOUND if key was not found
195 * - PMIX_ERROR other error
196 *
197 */
198
199 PMIX_EXPORT int pmix_hash_table_get_value_ptr(pmix_hash_table_t *table, const void* key,
200 size_t keylen, void **ptr);
201
202 /**
203 * Set value based on arbitrary length binary key.
204 *
205 * @param table The input hash table (IN).
206 * @param key The input key (IN).
207 * @param value The value to be associated with the key (IN).
208 * @return PMIX return code.
209 *
210 */
211
212 PMIX_EXPORT int pmix_hash_table_set_value_ptr(pmix_hash_table_t *table, const void* key, size_t keylen, void* value);
213
214 /**
215 * Remove value based on arbitrary length binary key.
216 *
217 * @param table The input hash table (IN).
218 * @param key The input key (IN).
219 * @return PMIX return code.
220 *
221 */
222
223 PMIX_EXPORT int pmix_hash_table_remove_value_ptr(pmix_hash_table_t *table, const void* key, size_t keylen);
224
225
226 /** The following functions are only for allowing iterating through
227 the hash table. The calls return along with a key, a pointer to
228 the hash node with the current key, so that subsequent calls do
229 not have to traverse all over again to the key (although it may
230 just be a simple thing - to go to the array element and then
231 traverse through the individual list). But lets take out this
232 inefficiency too. This is similar to having an STL iterator in
233 functionality */
234
235 /**
236 * Get the first 32 bit key from the hash table, which can be used later to
237 * get the next key
238 * @param table The hash table pointer (IN)
239 * @param key The first key (OUT)
240 * @param value The value corresponding to this key (OUT)
241 * @param node The pointer to the hash table internal node which stores
242 * the key-value pair (this is required for subsequent calls
243 * to get_next_key) (OUT)
244 * @return PMIX error code
245 *
246 */
247
248 PMIX_EXPORT int pmix_hash_table_get_first_key_uint32(pmix_hash_table_t *table, uint32_t *key,
249 void **value, void **node);
250
251
252 /**
253 * Get the next 32 bit key from the hash table, knowing the current key
254 * @param table The hash table pointer (IN)
255 * @param key The key (OUT)
256 * @param value The value corresponding to this key (OUT)
257 * @param in_node The node pointer from previous call to either get_first
258 or get_next (IN)
259 * @param out_node The pointer to the hash table internal node which stores
260 * the key-value pair (this is required for subsequent calls
261 * to get_next_key) (OUT)
262 * @return PMIX error code
263 *
264 */
265
266 PMIX_EXPORT int pmix_hash_table_get_next_key_uint32(pmix_hash_table_t *table, uint32_t *key,
267 void **value, void *in_node,
268 void **out_node);
269
270
271 /**
272 * Get the first 64 key from the hash table, which can be used later to
273 * get the next key
274 * @param table The hash table pointer (IN)
275 * @param key The first key (OUT)
276 * @param value The value corresponding to this key (OUT)
277 * @param node The pointer to the hash table internal node which stores
278 * the key-value pair (this is required for subsequent calls
279 * to get_next_key) (OUT)
280 * @return PMIX error code
281 *
282 */
283
284 PMIX_EXPORT int pmix_hash_table_get_first_key_uint64(pmix_hash_table_t *table, uint64_t *key,
285 void **value, void **node);
286
287
288 /**
289 * Get the next 64 bit key from the hash table, knowing the current key
290 * @param table The hash table pointer (IN)
291 * @param key The key (OUT)
292 * @param value The value corresponding to this key (OUT)
293 * @param in_node The node pointer from previous call to either get_first
294 or get_next (IN)
295 * @param out_node The pointer to the hash table internal node which stores
296 * the key-value pair (this is required for subsequent calls
297 * to get_next_key) (OUT)
298 * @return PMIX error code
299 *
300 */
301
302 PMIX_EXPORT int pmix_hash_table_get_next_key_uint64(pmix_hash_table_t *table, uint64_t *key,
303 void **value, void *in_node,
304 void **out_node);
305
306
307 /**
308 * Get the first ptr bit key from the hash table, which can be used later to
309 * get the next key
310 * @param table The hash table pointer (IN)
311 * @param key The first key (OUT)
312 * @param key_size The first key size (OUT)
313 * @param value The value corresponding to this key (OUT)
314 * @param node The pointer to the hash table internal node which stores
315 * the key-value pair (this is required for subsequent calls
316 * to get_next_key) (OUT)
317 * @return PMIX error code
318 *
319 */
320
321 PMIX_EXPORT int pmix_hash_table_get_first_key_ptr(pmix_hash_table_t *table, void* *key,
322 size_t *key_size, void **value, void **node);
323
324
325 /**
326 * Get the next ptr bit key from the hash table, knowing the current key
327 * @param table The hash table pointer (IN)
328 * @param key The key (OUT)
329 * @param key_size The key size (OUT)
330 * @param value The value corresponding to this key (OUT)
331 * @param in_node The node pointer from previous call to either get_first
332 or get_next (IN)
333 * @param out_node The pointer to the hash table internal node which stores
334 * the key-value pair (this is required for subsequent calls
335 * to get_next_key) (OUT)
336 * @return PMIX error code
337 *
338 */
339
340 PMIX_EXPORT int pmix_hash_table_get_next_key_ptr(pmix_hash_table_t *table, void* *key,
341 size_t *key_size, void **value,
342 void *in_node, void **out_node);
343
344
345 /**
346 * @brief Returns next power-of-two of the given value.
347 *
348 * @param value The integer value to return power of 2
349 *
350 * @returns The next power of two
351 *
352 * WARNING: *NO* error checking is performed. This is meant to be a
353 * fast inline function.
354 * Using __builtin_clz (count-leading-zeros) uses 4 cycles instead of 77
355 * compared to the loop-version (on Intel Nehalem -- with icc-12.1.0 -O2).
356 */
357 static inline int pmix_next_poweroftwo(int value)
358 {
359 int power2;
360
361 #if PMIX_C_HAVE_BUILTIN_CLZ
362 if (PMIX_UNLIKELY (0 == value)) {
363 return 1;
364 }
365 power2 = 1 << (8 * sizeof (int) - __builtin_clz(value));
366 #else
367 for (power2 = 1; value > 0; value >>= 1, power2 <<= 1) /* empty */;
368 #endif
369
370 return power2;
371 }
372
373
374 /**
375 * Loop over a hash table.
376 *
377 * @param[in] key Key for each item
378 * @param[in] type Type of key (ui32|ui64|ptr)
379 * @param[in] value Storage for each item
380 * @param[in] ht Hash table to iterate over
381 *
382 * This macro provides a simple way to loop over the items in a pmix_hash_table_t. It
383 * is not safe to call pmix_hash_table_remove* from within the loop.
384 *
385 * Example Usage:
386 *
387 * uint64_t key;
388 * void * value;
389 * PMIX_HASH_TABLE_FOREACH(key, uint64, value, ht) {
390 * do_something(key, value);
391 * }
392 */
393 #define PMIX_HASH_TABLE_FOREACH(key, type, value, ht) \
394 for (void *_nptr=NULL; \
395 PMIX_SUCCESS == pmix_hash_table_get_next_key_##type(ht, &key, (void **)&value, _nptr, &_nptr);)
396
397 END_C_DECLS
398
399 #endif /* PMIX_HASH_TABLE_H */