EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2025-02-22 10:47:20
0001 /* 0002 * Copyright (c) 2004-2007 The Trustees of Indiana University and Indiana 0003 * University Research and Technology 0004 * Corporation. All rights reserved. 0005 * Copyright (c) 2004-2005 The University of Tennessee and The University 0006 * of Tennessee Research Foundation. All rights 0007 * reserved. 0008 * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart, 0009 * University of Stuttgart. All rights reserved. 0010 * Copyright (c) 2004-2005 The Regents of the University of California. 0011 * All rights reserved. 0012 * Copyright (c) 2015-2020 Intel, Inc. All rights reserved. 0013 * Copyright (c) 2015-2016 Research Organization for Information Science 0014 * and Technology (RIST). All rights reserved. 0015 * Copyright (c) 2016 Mellanox Technologies, Inc. 0016 * All rights reserved. 0017 * Copyright (c) 2022 Triad National Security, LLC. All rights reserved. 0018 * 0019 * Copyright (c) 2021-2022 Nanook Consulting. All rights reserved. 0020 * $COPYRIGHT$ 0021 * 0022 * Additional copyrights may follow 0023 * 0024 * $HEADER$ 0025 * 0026 */ 0027 0028 /** @file 0029 * 0030 * A hash table that may be indexed with either fixed length 0031 * (e.g. uint32_t/uint64_t) or arbitrary size binary key 0032 * values. However, only one key type may be used in a given table 0033 * concurrently. 0034 */ 0035 0036 #ifndef PMIX_HASH_TABLE_H 0037 #define PMIX_HASH_TABLE_H 0038 0039 #include "src/include/pmix_config.h" 0040 #include "src/include/pmix_prefetch.h" 0041 0042 #ifdef HAVE_STDINT_H 0043 # include <stdint.h> 0044 #endif 0045 0046 #include "src/class/pmix_list.h" 0047 0048 #include "pmix_common.h" 0049 0050 BEGIN_C_DECLS 0051 0052 PMIX_EXPORT PMIX_CLASS_DECLARATION(pmix_hash_table_t); 0053 0054 struct pmix_hash_table_t { 0055 pmix_object_t super; /**< subclass of pmix_object_t */ 0056 const char *ht_label; /**< label for debugging */ 0057 struct pmix_hash_element_t *ht_table; /**< table of elements (opaque to users) */ 0058 size_t ht_capacity; /**< allocated size (capacity) of table */ 0059 size_t ht_size; /**< number of extant entries */ 0060 size_t ht_growth_trigger; /**< size hits this and table is grown */ 0061 int ht_density_numer, ht_density_denom; /**< max allowed density of table */ 0062 int ht_growth_numer, ht_growth_denom; /**< growth factor when grown */ 0063 const struct pmix_hash_type_methods_t *ht_type_methods; 0064 }; 0065 typedef struct pmix_hash_table_t pmix_hash_table_t; 0066 0067 #define PMIX_HASH_TABLE_STATIC_INIT \ 0068 { \ 0069 .super = PMIX_OBJ_STATIC_INIT(pmix_object_t), \ 0070 .ht_label = NULL, \ 0071 .ht_table = NULL, \ 0072 .ht_capacity = 0, \ 0073 .ht_size = 0, \ 0074 .ht_growth_trigger = 0, \ 0075 .ht_density_numer = 0, \ 0076 .ht_density_denom = 0, \ 0077 .ht_growth_numer = 0, \ 0078 .ht_growth_denom = 0, \ 0079 .ht_type_methods = NULL \ 0080 } 0081 /** 0082 * Initializes the table size, must be called before using 0083 * the table. 0084 * 0085 * @param table The input hash table (IN). 0086 * @param size The size of the table, which will be rounded up 0087 * (if required) to the next highest power of two (IN). 0088 * @return PMIX error code. 0089 * 0090 */ 0091 0092 PMIX_EXPORT int pmix_hash_table_init(pmix_hash_table_t *ht, size_t table_size); 0093 0094 /* this could be the new init if people wanted a more general API */ 0095 PMIX_EXPORT int pmix_hash_table_init2(pmix_hash_table_t *ht, size_t estimated_max_size, 0096 int density_numer, int density_denom, int growth_numer, 0097 int growth_denom); 0098 0099 /** 0100 * Returns the number of elements currently stored in the table. 0101 * 0102 * @param table The input hash table (IN). 0103 * @return The number of elements in the table. 0104 * 0105 */ 0106 0107 static inline size_t pmix_hash_table_get_size(pmix_hash_table_t *ht) 0108 { 0109 return ht->ht_size; 0110 } 0111 0112 /** 0113 * Remove all elements from the table. 0114 * 0115 * @param table The input hash table (IN). 0116 * @return PMIX return code. 0117 * 0118 */ 0119 0120 PMIX_EXPORT int pmix_hash_table_remove_all(pmix_hash_table_t *ht); 0121 0122 /** 0123 * Retrieve value via uint32_t key. 0124 * 0125 * @param table The input hash table (IN). 0126 * @param key The input key (IN). 0127 * @param ptr The value associated with the key 0128 * @return integer return code: 0129 * - PMIX_SUCCESS if key was found 0130 * - PMIX_ERR_NOT_FOUND if key was not found 0131 * - PMIX_ERROR other error 0132 * 0133 */ 0134 0135 PMIX_EXPORT int pmix_hash_table_get_value_uint32(pmix_hash_table_t *table, uint32_t key, 0136 void **ptr); 0137 0138 /** 0139 * Set value based on uint32_t key. 0140 * 0141 * @param table The input hash table (IN). 0142 * @param key The input key (IN). 0143 * @param value The value to be associated with the key (IN). 0144 * @return PMIX return code. 0145 * 0146 */ 0147 0148 PMIX_EXPORT int pmix_hash_table_set_value_uint32(pmix_hash_table_t *table, uint32_t key, 0149 void *value); 0150 0151 /** 0152 * Remove value based on uint32_t key. 0153 * 0154 * @param table The input hash table (IN). 0155 * @param key The input key (IN). 0156 * @return PMIX return code. 0157 * 0158 */ 0159 0160 PMIX_EXPORT int pmix_hash_table_remove_value_uint32(pmix_hash_table_t *table, uint32_t key); 0161 0162 /** 0163 * Retrieve value via uint64_t key. 0164 * 0165 * @param table The input hash table (IN). 0166 * @param key The input key (IN). 0167 * @param ptr The value associated with the key 0168 * @return integer return code: 0169 * - PMIX_SUCCESS if key was found 0170 * - PMIX_ERR_NOT_FOUND if key was not found 0171 * - PMIX_ERROR other error 0172 * 0173 */ 0174 0175 PMIX_EXPORT int pmix_hash_table_get_value_uint64(pmix_hash_table_t *table, uint64_t key, 0176 void **ptr); 0177 0178 /** 0179 * Set value based on uint64_t key. 0180 * 0181 * @param table The input hash table (IN). 0182 * @param key The input key (IN). 0183 * @param value The value to be associated with the key (IN). 0184 * @return PMIX return code. 0185 * 0186 */ 0187 0188 PMIX_EXPORT int pmix_hash_table_set_value_uint64(pmix_hash_table_t *table, uint64_t key, 0189 void *value); 0190 0191 /** 0192 * Remove value based on uint64_t key. 0193 * 0194 * @param table The input hash table (IN). 0195 * @param key The input key (IN). 0196 * @return PMIX return code. 0197 * 0198 */ 0199 0200 PMIX_EXPORT int pmix_hash_table_remove_value_uint64(pmix_hash_table_t *table, uint64_t key); 0201 0202 /** 0203 * Retrieve value via arbitrary length binary key. 0204 * 0205 * @param table The input hash table (IN). 0206 * @param key The input key (IN). 0207 * @param ptr The value associated with the key 0208 * @return integer return code: 0209 * - PMIX_SUCCESS if key was found 0210 * - PMIX_ERR_NOT_FOUND if key was not found 0211 * - PMIX_ERROR other error 0212 * 0213 */ 0214 0215 PMIX_EXPORT int pmix_hash_table_get_value_ptr(pmix_hash_table_t *table, const void *key, 0216 size_t keylen, void **ptr); 0217 0218 /** 0219 * Set value based on arbitrary length binary key. 0220 * 0221 * @param table The input hash table (IN). 0222 * @param key The input key (IN). 0223 * @param value The value to be associated with the key (IN). 0224 * @return PMIX return code. 0225 * 0226 */ 0227 0228 PMIX_EXPORT int pmix_hash_table_set_value_ptr(pmix_hash_table_t *table, const void *key, 0229 size_t keylen, void *value); 0230 0231 /** 0232 * Remove value based on arbitrary length binary key. 0233 * 0234 * @param table The input hash table (IN). 0235 * @param key The input key (IN). 0236 * @return PMIX return code. 0237 * 0238 */ 0239 0240 PMIX_EXPORT int pmix_hash_table_remove_value_ptr(pmix_hash_table_t *table, const void *key, 0241 size_t keylen); 0242 0243 /** The following functions are only for allowing iterating through 0244 the hash table. The calls return along with a key, a pointer to 0245 the hash node with the current key, so that subsequent calls do 0246 not have to traverse all over again to the key (although it may 0247 just be a simple thing - to go to the array element and then 0248 traverse through the individual list). But lets take out this 0249 inefficiency too. This is similar to having an STL iterator in 0250 functionality */ 0251 0252 /** 0253 * Get the first 32 bit key from the hash table, which can be used later to 0254 * get the next key 0255 * @param table The hash table pointer (IN) 0256 * @param key The first key (OUT) 0257 * @param value The value corresponding to this key (OUT) 0258 * @param node The pointer to the hash table internal node which stores 0259 * the key-value pair (this is required for subsequent calls 0260 * to get_next_key) (OUT) 0261 * @return PMIX error code 0262 * 0263 */ 0264 0265 PMIX_EXPORT int pmix_hash_table_get_first_key_uint32(pmix_hash_table_t *table, uint32_t *key, 0266 void **value, void **node); 0267 0268 /** 0269 * Get the next 32 bit key from the hash table, knowing the current key 0270 * @param table The hash table pointer (IN) 0271 * @param key The key (OUT) 0272 * @param value The value corresponding to this key (OUT) 0273 * @param in_node The node pointer from previous call to either get_first 0274 or get_next (IN) 0275 * @param out_node The pointer to the hash table internal node which stores 0276 * the key-value pair (this is required for subsequent calls 0277 * to get_next_key) (OUT) 0278 * @return PMIX error code 0279 * 0280 */ 0281 0282 PMIX_EXPORT int pmix_hash_table_get_next_key_uint32(pmix_hash_table_t *table, uint32_t *key, 0283 void **value, void *in_node, void **out_node); 0284 0285 /** 0286 * Get the first 64 key from the hash table, which can be used later to 0287 * get the next key 0288 * @param table The hash table pointer (IN) 0289 * @param key The first key (OUT) 0290 * @param value The value corresponding to this key (OUT) 0291 * @param node The pointer to the hash table internal node which stores 0292 * the key-value pair (this is required for subsequent calls 0293 * to get_next_key) (OUT) 0294 * @return PMIX error code 0295 * 0296 */ 0297 0298 PMIX_EXPORT int pmix_hash_table_get_first_key_uint64(pmix_hash_table_t *table, uint64_t *key, 0299 void **value, void **node); 0300 0301 /** 0302 * Get the next 64 bit key from the hash table, knowing the current key 0303 * @param table The hash table pointer (IN) 0304 * @param key The key (OUT) 0305 * @param value The value corresponding to this key (OUT) 0306 * @param in_node The node pointer from previous call to either get_first 0307 or get_next (IN) 0308 * @param out_node The pointer to the hash table internal node which stores 0309 * the key-value pair (this is required for subsequent calls 0310 * to get_next_key) (OUT) 0311 * @return PMIX error code 0312 * 0313 */ 0314 0315 PMIX_EXPORT int pmix_hash_table_get_next_key_uint64(pmix_hash_table_t *table, uint64_t *key, 0316 void **value, void *in_node, void **out_node); 0317 0318 /** 0319 * Get the first ptr bit key from the hash table, which can be used later to 0320 * get the next key 0321 * @param table The hash table pointer (IN) 0322 * @param key The first key (OUT) 0323 * @param key_size The first key size (OUT) 0324 * @param value The value corresponding to this key (OUT) 0325 * @param node The pointer to the hash table internal node which stores 0326 * the key-value pair (this is required for subsequent calls 0327 * to get_next_key) (OUT) 0328 * @return PMIX error code 0329 * 0330 */ 0331 0332 PMIX_EXPORT int pmix_hash_table_get_first_key_ptr(pmix_hash_table_t *table, void **key, 0333 size_t *key_size, void **value, void **node); 0334 0335 /** 0336 * Get the next ptr bit key from the hash table, knowing the current key 0337 * @param table The hash table pointer (IN) 0338 * @param key The key (OUT) 0339 * @param key_size The key size (OUT) 0340 * @param value The value corresponding to this key (OUT) 0341 * @param in_node The node pointer from previous call to either get_first 0342 or get_next (IN) 0343 * @param out_node The pointer to the hash table internal node which stores 0344 * the key-value pair (this is required for subsequent calls 0345 * to get_next_key) (OUT) 0346 * @return PMIX error code 0347 * 0348 */ 0349 0350 PMIX_EXPORT int pmix_hash_table_get_next_key_ptr(pmix_hash_table_t *table, void **key, 0351 size_t *key_size, void **value, void *in_node, 0352 void **out_node); 0353 0354 /** 0355 * Returns the size of the opaque pmix_hash_element_t structure. Note that this 0356 * only returns the size of the structure itself and does not capture the size 0357 * of data that are stored within an element. 0358 */ 0359 PMIX_EXPORT size_t 0360 pmix_hash_table_sizeof_hash_element(void); 0361 0362 /** 0363 * @brief Returns next power-of-two of the given value. 0364 * 0365 * @param value The integer value to return power of 2 0366 * 0367 * @returns The next power of two 0368 * 0369 * WARNING: *NO* error checking is performed. This is meant to be a 0370 * fast inline function. 0371 * Using __builtin_clz (count-leading-zeros) uses 4 cycles instead of 77 0372 * compared to the loop-version (on Intel Nehalem -- with icc-12.1.0 -O2). 0373 */ 0374 static inline int pmix_next_poweroftwo(int value) 0375 { 0376 int power2; 0377 0378 #if PMIX_C_HAVE_BUILTIN_CLZ 0379 if (PMIX_UNLIKELY(0 == value)) { 0380 return 1; 0381 } 0382 power2 = 1 << (8 * sizeof(int) - __builtin_clz(value)); 0383 #else 0384 for (power2 = 1; value > 0; value >>= 1, power2 <<= 1) /* empty */ 0385 ; 0386 #endif 0387 0388 return power2; 0389 } 0390 0391 /** 0392 * Loop over a hash table. 0393 * 0394 * @param[in] key Key for each item 0395 * @param[in] type Type of key (ui32|ui64|ptr) 0396 * @param[in] value Storage for each item 0397 * @param[in] ht Hash table to iterate over 0398 * 0399 * This macro provides a simple way to loop over the items in a pmix_hash_table_t. It 0400 * is not safe to call pmix_hash_table_remove* from within the loop. 0401 * 0402 * Example Usage: 0403 * 0404 * uint64_t key; 0405 * void * value; 0406 * PMIX_HASH_TABLE_FOREACH(key, uint64, value, ht) { 0407 * do_something(key, value); 0408 * } 0409 */ 0410 #define PMIX_HASH_TABLE_FOREACH(key, type, value, ht) \ 0411 for (void *_nptr = NULL; \ 0412 PMIX_SUCCESS \ 0413 == pmix_hash_table_get_next_key_##type(ht, &key, (void **) &value, _nptr, &_nptr);) 0414 0415 #define PMIX_HASH_TABLE_FOREACH_PTR(key, value, ht, body) \ 0416 { \ 0417 size_t key_size_; \ 0418 for (void *_nptr = NULL; \ 0419 PMIX_SUCCESS \ 0420 == pmix_hash_table_get_next_key_ptr(ht, &key, &key_size_, (void **) &value, _nptr, \ 0421 &_nptr);) \ 0422 body \ 0423 } 0424 0425 END_C_DECLS 0426 0427 #endif /* PMIX_HASH_TABLE_H */
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|