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) 2014-2015 Hewlett-Packard Development Company, LP.
13 * All rights reserved.
14 * Copyright (c) 2014-2015 Mellanox Technologies, Inc.
15 * All rights reserved.
16 * Copyright (c) 2014 Intel, Inc. All rights reserved.
17 * Copyright (c) 2014-2016 Research Organization for Information Science
18 * and Technology (RIST). All rights reserved.
19 * $COPYRIGHT$
20 *
21 * Additional copyrights may follow
22 *
23 * $HEADER$
24 *
25 */
26
27 /** @file
28 *
29 * A hash table that may be indexed with either fixed length
30 * (e.g. uint32_t/uint64_t) or arbitrary size binary key
31 * values. However, only one key type may be used in a given table
32 * concurrently.
33 */
34
35 #ifndef OPAL_HASH_TABLE_H
36 #define OPAL_HASH_TABLE_H
37
38 #include "opal_config.h"
39
40 #include <stdint.h>
41 #include "opal/class/opal_list.h"
42 #include "opal/util/proc.h"
43
44 BEGIN_C_DECLS
45
46 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_hash_table_t);
47
48 struct opal_hash_table_t
49 {
50 opal_object_t super; /**< subclass of opal_object_t */
51 struct opal_hash_element_t * ht_table; /**< table of elements (opaque to users) */
52 size_t ht_capacity; /**< allocated size (capacity) of table */
53 size_t ht_size; /**< number of extant entries */
54 size_t ht_growth_trigger; /**< size hits this and table is grown */
55 int ht_density_numer, ht_density_denom; /**< max allowed density of table */
56 int ht_growth_numer, ht_growth_denom; /**< growth factor when grown */
57 const struct opal_hash_type_methods_t * ht_type_methods;
58 };
59 typedef struct opal_hash_table_t opal_hash_table_t;
60
61
62
63 /**
64 * Initializes the table size, must be called before using
65 * the table.
66 *
67 * @param table The input hash table (IN).
68 * @param size The size of the table, which will be rounded up
69 * (if required) to the next highest power of two (IN).
70 * @return OPAL error code.
71 *
72 */
73
74 OPAL_DECLSPEC int opal_hash_table_init(opal_hash_table_t* ht, size_t table_size);
75
76 /* this could be the new init if people wanted a more general API */
77 OPAL_DECLSPEC int opal_hash_table_init2(opal_hash_table_t* ht, size_t estimated_max_size,
78 int density_numer, int density_denom,
79 int growth_numer, int growth_denom);
80
81 /**
82 * Returns the number of elements currently stored in the table.
83 *
84 * @param table The input hash table (IN).
85 * @return The number of elements in the table.
86 *
87 */
88
89 static inline size_t opal_hash_table_get_size(opal_hash_table_t *ht)
90 {
91 return ht->ht_size;
92 }
93
94 /**
95 * Remove all elements from the table.
96 *
97 * @param table The input hash table (IN).
98 * @return OPAL return code.
99 *
100 */
101
102 OPAL_DECLSPEC int opal_hash_table_remove_all(opal_hash_table_t *ht);
103
104 /**
105 * Retrieve value via uint32_t key.
106 *
107 * @param table The input hash table (IN).
108 * @param key The input key (IN).
109 * @param ptr The value associated with the key
110 * @return integer return code:
111 * - OPAL_SUCCESS if key was found
112 * - OPAL_ERR_NOT_FOUND if key was not found
113 * - OPAL_ERROR other error
114 *
115 */
116
117 OPAL_DECLSPEC int opal_hash_table_get_value_uint32(opal_hash_table_t* table, uint32_t key,
118 void** ptr);
119
120 /**
121 * Set value based on uint32_t key.
122 *
123 * @param table The input hash table (IN).
124 * @param key The input key (IN).
125 * @param value The value to be associated with the key (IN).
126 * @return OPAL return code.
127 *
128 */
129
130 OPAL_DECLSPEC int opal_hash_table_set_value_uint32(opal_hash_table_t* table, uint32_t key, void* value);
131
132 /**
133 * Remove value based on uint32_t key.
134 *
135 * @param table The input hash table (IN).
136 * @param key The input key (IN).
137 * @return OPAL return code.
138 *
139 */
140
141 OPAL_DECLSPEC int opal_hash_table_remove_value_uint32(opal_hash_table_t* table, uint32_t key);
142
143 /**
144 * Retrieve value via uint64_t key.
145 *
146 * @param table The input hash table (IN).
147 * @param key The input key (IN).
148 * @param ptr The value associated with the key
149 * @return integer return code:
150 * - OPAL_SUCCESS if key was found
151 * - OPAL_ERR_NOT_FOUND if key was not found
152 * - OPAL_ERROR other error
153 *
154 */
155
156 OPAL_DECLSPEC int opal_hash_table_get_value_uint64(opal_hash_table_t *table, uint64_t key,
157 void **ptr);
158
159 /**
160 * Set value based on uint64_t key.
161 *
162 * @param table The input hash table (IN).
163 * @param key The input key (IN).
164 * @param value The value to be associated with the key (IN).
165 * @return OPAL return code.
166 *
167 */
168
169 OPAL_DECLSPEC int opal_hash_table_set_value_uint64(opal_hash_table_t *table, uint64_t key, void* value);
170
171 /**
172 * Remove value based on uint64_t key.
173 *
174 * @param table The input hash table (IN).
175 * @param key The input key (IN).
176 * @return OPAL return code.
177 *
178 */
179
180 OPAL_DECLSPEC int opal_hash_table_remove_value_uint64(opal_hash_table_t *table, uint64_t key);
181
182 /**
183 * Retrieve value via arbitrary length binary key.
184 *
185 * @param table The input hash table (IN).
186 * @param key The input key (IN).
187 * @param ptr The value associated with the key
188 * @return integer return code:
189 * - OPAL_SUCCESS if key was found
190 * - OPAL_ERR_NOT_FOUND if key was not found
191 * - OPAL_ERROR other error
192 *
193 */
194
195 OPAL_DECLSPEC int opal_hash_table_get_value_ptr(opal_hash_table_t *table, const void* key,
196 size_t keylen, void **ptr);
197
198 /**
199 * Set value based on arbitrary length binary key.
200 *
201 * @param table The input hash table (IN).
202 * @param key The input key (IN).
203 * @param value The value to be associated with the key (IN).
204 * @return OPAL return code.
205 *
206 */
207
208 OPAL_DECLSPEC int opal_hash_table_set_value_ptr(opal_hash_table_t *table, const void* key, size_t keylen, void* value);
209
210 /**
211 * Remove value based on arbitrary length binary key.
212 *
213 * @param table The input hash table (IN).
214 * @param key The input key (IN).
215 * @return OPAL return code.
216 *
217 */
218
219 OPAL_DECLSPEC int opal_hash_table_remove_value_ptr(opal_hash_table_t *table, const void* key, size_t keylen);
220
221
222 /** The following functions are only for allowing iterating through
223 the hash table. The calls return along with a key, a pointer to
224 the hash node with the current key, so that subsequent calls do
225 not have to traverse all over again to the key (although it may
226 just be a simple thing - to go to the array element and then
227 traverse through the individual list). But lets take out this
228 inefficiency too. This is similar to having an STL iterator in
229 functionality */
230
231 /**
232 * Get the first 32 bit key from the hash table, which can be used later to
233 * get the next key
234 * @param table The hash table pointer (IN)
235 * @param key The first key (OUT)
236 * @param value The value corresponding to this key (OUT)
237 * @param node The pointer to the hash table internal node which stores
238 * the key-value pair (this is required for subsequent calls
239 * to get_next_key) (OUT)
240 * @return OPAL error code
241 *
242 */
243
244 OPAL_DECLSPEC int opal_hash_table_get_first_key_uint32(opal_hash_table_t *table, uint32_t *key,
245 void **value, void **node);
246
247
248 /**
249 * Get the next 32 bit key from the hash table, knowing the current key
250 * @param table The hash table pointer (IN)
251 * @param key The key (OUT)
252 * @param value The value corresponding to this key (OUT)
253 * @param in_node The node pointer from previous call to either get_first
254 or get_next (IN)
255 * @param out_node The pointer to the hash table internal node which stores
256 * the key-value pair (this is required for subsequent calls
257 * to get_next_key) (OUT)
258 * @return OPAL error code
259 *
260 */
261
262 OPAL_DECLSPEC int opal_hash_table_get_next_key_uint32(opal_hash_table_t *table, uint32_t *key,
263 void **value, void *in_node,
264 void **out_node);
265
266
267 /**
268 * Get the first 64 key from the hash table, which can be used later to
269 * get the next key
270 * @param table The hash table pointer (IN)
271 * @param key The first key (OUT)
272 * @param value The value corresponding to this key (OUT)
273 * @param node The pointer to the hash table internal node which stores
274 * the key-value pair (this is required for subsequent calls
275 * to get_next_key) (OUT)
276 * @return OPAL error code
277 *
278 */
279
280 OPAL_DECLSPEC int opal_hash_table_get_first_key_uint64(opal_hash_table_t *table, uint64_t *key,
281 void **value, void **node);
282
283
284 /**
285 * Get the next 64 bit key from the hash table, knowing the current key
286 * @param table The hash table pointer (IN)
287 * @param key The key (OUT)
288 * @param value The value corresponding to this key (OUT)
289 * @param in_node The node pointer from previous call to either get_first
290 or get_next (IN)
291 * @param out_node The pointer to the hash table internal node which stores
292 * the key-value pair (this is required for subsequent calls
293 * to get_next_key) (OUT)
294 * @return OPAL error code
295 *
296 */
297
298 OPAL_DECLSPEC int opal_hash_table_get_next_key_uint64(opal_hash_table_t *table, uint64_t *key,
299 void **value, void *in_node,
300 void **out_node);
301
302
303 /**
304 * Get the first ptr bit key from the hash table, which can be used later to
305 * get the next key
306 * @param table The hash table pointer (IN)
307 * @param key The first key (OUT)
308 * @param key_size The first key size (OUT)
309 * @param value The value corresponding to this key (OUT)
310 * @param node The pointer to the hash table internal node which stores
311 * the key-value pair (this is required for subsequent calls
312 * to get_next_key) (OUT)
313 * @return OPAL error code
314 *
315 */
316
317 OPAL_DECLSPEC int opal_hash_table_get_first_key_ptr(opal_hash_table_t *table, void* *key,
318 size_t *key_size, void **value, void **node);
319
320
321 /**
322 * Get the next ptr bit key from the hash table, knowing the current key
323 * @param table The hash table pointer (IN)
324 * @param key The key (OUT)
325 * @param key_size The key size (OUT)
326 * @param value The value corresponding to this key (OUT)
327 * @param in_node The node pointer from previous call to either get_first
328 or get_next (IN)
329 * @param out_node The pointer to the hash table internal node which stores
330 * the key-value pair (this is required for subsequent calls
331 * to get_next_key) (OUT)
332 * @return OPAL error code
333 *
334 */
335
336 OPAL_DECLSPEC int opal_hash_table_get_next_key_ptr(opal_hash_table_t *table, void* *key,
337 size_t *key_size, void **value,
338 void *in_node, void **out_node);
339
340
341
342 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_proc_table_t);
343
344 struct opal_proc_table_t
345 {
346 opal_hash_table_t super; /**< subclass of opal_object_t */
347 size_t pt_size; /**< number of extant entries */
348 size_t vpids_size;
349 // FIXME
350 // Begin KLUDGE!! So ompi/debuggers/ompi_common_dll.c doesn't complain
351 size_t pt_table_size; /**< size of table */
352 // End KLUDGE
353 };
354 typedef struct opal_proc_table_t opal_proc_table_t;
355
356
357
358 /**
359 * Initializes the table size, must be called before using
360 * the table.
361 *
362 * @param pt The input hash table (IN).
363 * @param jobids The size of the jobids table, which will be rounded up
364 * (if required) to the next highest power of two (IN).
365 * @param vpids The size of the vpids table, which will be rounded up
366 * (if required) to the next highest power of two (IN).
367 * @return OPAL error code.
368 *
369 */
370
371 OPAL_DECLSPEC int opal_proc_table_init(opal_proc_table_t* pt, size_t jobids, size_t vpids);
372
373 /**
374 * Remove all elements from the table.
375 *
376 * @param pt The input hash table (IN).
377 * @return OPAL return code.
378 *
379 */
380
381 OPAL_DECLSPEC int opal_proc_table_remove_all(opal_proc_table_t *pt);
382
383 /**
384 * Retrieve value via opal_process_name_t key.
385 *
386 * @param pt The input hash table (IN).
387 * @param key The input key (IN).
388 * @param ptr The value associated with the key
389 * @return integer return code:
390 * - OPAL_SUCCESS if key was found
391 * - OPAL_ERR_NOT_FOUND if key was not found
392 * - OPAL_ERROR other error
393 *
394 */
395
396 OPAL_DECLSPEC int opal_proc_table_get_value(opal_proc_table_t* pt, opal_process_name_t key,
397 void** ptr);
398
399 /**
400 * Set value based on opal_process_name_t key.
401 *
402 * @param pt The input hash table (IN).
403 * @param key The input key (IN).
404 * @param value The value to be associated with the key (IN).
405 * @return OPAL return code.
406 *
407 */
408
409 OPAL_DECLSPEC int opal_proc_table_set_value(opal_proc_table_t* pt, opal_process_name_t key, void* value);
410
411 /**
412 * Remove value based on opal_process_name_t key.
413 *
414 * @param pt The input hash table (IN).
415 * @param key The input key (IN).
416 * @return OPAL return code.
417 *
418 */
419
420 OPAL_DECLSPEC int opal_proc_table_remove_value(opal_proc_table_t* pt, opal_process_name_t key);
421
422
423 /**
424 * Get the first opal_process_name_t key from the hash table, which can be used later to
425 * get the next key
426 * @param pt The hash table pointer (IN)
427 * @param key The first key (OUT)
428 * @param value The value corresponding to this key (OUT)
429 * @param node1 The pointer to the first internal node which stores
430 * the key-value pair (this is required for subsequent calls
431 * to get_next_key) (OUT)
432 * @param node2 The pointer to the second internal node which stores
433 * the key-value pair (this is required for subsequent calls
434 * to get_next_key) (OUT)
435 * @return OPAL error code
436 *
437 */
438
439 OPAL_DECLSPEC int opal_proc_table_get_first_key(opal_proc_table_t *pt, opal_process_name_t *key,
440 void **value, void **node1, void **node2);
441
442
443 /**
444 * Get the next opal_process_name_t key from the hash table, knowing the current key
445 * @param pt The hash table pointer (IN)
446 * @param key The key (OUT)
447 * @param value The value corresponding to this key (OUT)
448 * @param in_node1 The first node pointer from previous call to either get_first
449 or get_next (IN)
450 * @param out_node1 The first pointer to the hash table internal node which stores
451 * the key-value pair (this is required for subsequent calls
452 * to get_next_key) (OUT)
453 * @param in_node2 The second node pointer from previous call to either get_first
454 or get_next (IN)
455 * @param out_node2 The second pointer to the hash table internal node which stores
456 * the key-value pair (this is required for subsequent calls
457 * to get_next_key) (OUT)
458 * @return OPAL error code
459 *
460 */
461
462 OPAL_DECLSPEC int opal_proc_table_get_next_key(opal_proc_table_t *pt, opal_process_name_t *key,
463 void **value, void *in_node1, void **out_node1,
464 void *in_node2, void **out_node2);
465
466 /**
467 * Loop over a hash table.
468 *
469 * @param[in] key Key for each item
470 * @param[in] type Type of key (ui32|ui64|ptr)
471 * @param[in] value Storage for each item
472 * @param[in] ht Hash table to iterate over
473 *
474 * This macro provides a simple way to loop over the items in an opal_hash_table_t. It
475 * is not safe to call opal_hash_table_remove* from within the loop.
476 *
477 * Example Usage:
478 *
479 * uint64_t key;
480 * void * value;
481 * OPAL_HASH_TABLE_FOREACH(key, uint64, value, ht) {
482 * do_something(key, value);
483 * }
484 */
485 #define OPAL_HASH_TABLE_FOREACH(key, type, value, ht) \
486 for (void *_nptr=NULL; \
487 OPAL_SUCCESS == opal_hash_table_get_next_key_##type(ht, &key, (void **)&value, _nptr, &_nptr);)
488
489 END_C_DECLS
490
491 #endif /* OPAL_HASH_TABLE_H */