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 */