opal/mca/pmix/pmix4x/pmix/src/class/pmix_hash

/* [<][>][^][v][top][bottom][index][help] */
This source file includes following definitions.
pmix_hash_table_construct
pmix_hash_table_destruct
pmix_hash_round_capacity_up
pmix_hash_table_init2
pmix_hash_table_init
pmix_hash_table_remove_all
pmix_hash_grow
pmix_hash_table_remove_elt_at
pmix_hash_hash_elt_uint32
pmix_hash_table_get_value_uint32
pmix_hash_table_set_value_uint32
pmix_hash_table_remove_value_uint32
pmix_hash_hash_elt_uint64
pmix_hash_table_get_value_uint64
pmix_hash_table_set_value_uint64
pmix_hash_table_remove_value_uint64
pmix_hash_hash_key_ptr
pmix_hash_destruct_elt_ptr
pmix_hash_hash_elt_ptr
pmix_hash_table_get_value_ptr
pmix_hash_table_set_value_ptr
pmix_hash_table_remove_value_ptr
pmix_hash_table_get_next_elt
pmix_hash_table_get_first_key_uint32
pmix_hash_table_get_next_key_uint32
pmix_hash_table_get_first_key_ptr
pmix_hash_table_get_next_key_ptr
pmix_hash_table_get_first_key_uint64
pmix_hash_table_get_next_key_uint64
   1 /*
   2  * Copyright (c) 2004-2005 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 Research Organization for Information Science
  13  *                         and Technology (RIST). All rights reserved.
  14  * Copyright (c) 2014-2015 Intel, Inc. All rights reserved
  15  * $COPYRIGHT$
  16  *
  17  * Additional copyrights may follow
  18  *
  19  * $HEADER$
  20  */
  21 
  22 #include <src/include/pmix_config.h>
  23 
  24 #include <string.h>
  25 #include <stdlib.h>
  26 
  27 #include "src/util/output.h"
  28 #include "src/util/crc.h"
  29 #include "src/class/pmix_list.h"
  30 #include "src/class/pmix_hash_table.h"
  31 
  32 #include "include/pmix_common.h"
  33 
  34 /*
  35  * pmix_hash_table_t
  36  */
  37 
  38 #define HASH_MULTIPLIER 31
  39 
  40 /*
  41  * Define the structs that are opaque in the .h
  42  */
  43 
  44 struct pmix_hash_element_t {
  45     int         valid;          /* whether this element is valid */
  46     union {                     /* the key, in its various forms */
  47         uint32_t        u32;
  48         uint64_t        u64;
  49         struct {
  50             const void * key;
  51             size_t      key_size;
  52         }       ptr;
  53     }           key;
  54     void *      value;          /* the value */
  55 };
  56 typedef struct pmix_hash_element_t pmix_hash_element_t;
  57 
  58 struct pmix_hash_type_methods_t {
  59     /* Frees any storage associated with the element
  60      * The value is not owned by the hash table
  61      * The key,key_size of pointer keys is
  62      */
  63     void        (*elt_destructor)(pmix_hash_element_t * elt);
  64     /* Hash the key of the element -- for growing and adjusting-after-removal */
  65     uint64_t    (*hash_elt)(pmix_hash_element_t * elt);
  66 };
  67 
  68 /* interact with the class-like mechanism */
  69 
  70 static void pmix_hash_table_construct(pmix_hash_table_t* ht);
  71 static void pmix_hash_table_destruct(pmix_hash_table_t* ht);
  72 
  73 PMIX_CLASS_INSTANCE(
  74     pmix_hash_table_t,
  75     pmix_object_t,
  76     pmix_hash_table_construct,
  77     pmix_hash_table_destruct
  78 );
  79 
  80 static void
  81 pmix_hash_table_construct(pmix_hash_table_t* ht)
  82 {
  83   ht->ht_table = NULL;
  84   ht->ht_capacity = ht->ht_size = ht->ht_growth_trigger = 0;
  85   ht->ht_density_numer = ht->ht_density_denom = 0;
  86   ht->ht_growth_numer = ht->ht_growth_denom = 0;
  87   ht->ht_type_methods = NULL;
  88 }
  89 
  90 static void
  91 pmix_hash_table_destruct(pmix_hash_table_t* ht)
  92 {
  93     pmix_hash_table_remove_all(ht);
  94     free(ht->ht_table);
  95 }
  96 
  97 /*
  98  * Init, etc
  99  */
 100 
 101 static size_t
 102 pmix_hash_round_capacity_up(size_t capacity)
 103 {
 104     /* round up to (1 mod 30) */
 105     return ((capacity+29)/30*30 + 1);
 106 }
 107 
 108 /* this could be the new init if people wanted a more general API */
 109 /* (that's why it isn't static) */
 110 int                             /* PMIX_ return code */
 111 pmix_hash_table_init2(pmix_hash_table_t* ht, size_t estimated_max_size,
 112                       int density_numer, int density_denom,
 113                       int growth_numer, int growth_denom)
 114 {
 115     size_t est_capacity = estimated_max_size * density_denom / density_numer;
 116     size_t capacity = pmix_hash_round_capacity_up(est_capacity);
 117     ht->ht_table = (pmix_hash_element_t*) calloc(capacity, sizeof(pmix_hash_element_t));
 118     if (NULL == ht->ht_table) {
 119         return PMIX_ERR_OUT_OF_RESOURCE;
 120     }
 121     ht->ht_capacity       = capacity;
 122     ht->ht_density_numer  = density_numer;
 123     ht->ht_density_denom  = density_denom;
 124     ht->ht_growth_numer   = growth_numer;
 125     ht->ht_growth_denom   = growth_denom;
 126     ht->ht_growth_trigger = capacity * density_numer / density_denom;
 127     ht->ht_type_methods   = NULL;
 128     return PMIX_SUCCESS;
 129 }
 130 
 131 int                             /* PMIX_ return code */
 132 pmix_hash_table_init(pmix_hash_table_t* ht, size_t table_size)
 133 {
 134     /* default to density of 1/2 and growth of 2/1 */
 135     return pmix_hash_table_init2(ht, table_size, 1, 2, 2, 1);
 136 }
 137 
 138 int                             /* PMIX_ return code */
 139 pmix_hash_table_remove_all(pmix_hash_table_t* ht)
 140 {
 141     size_t ii;
 142     for (ii = 0; ii < ht->ht_capacity; ii += 1) {
 143         pmix_hash_element_t * elt = &ht->ht_table[ii];
 144         if (elt->valid && ht->ht_type_methods && ht->ht_type_methods->elt_destructor) {
 145             ht->ht_type_methods->elt_destructor(elt);
 146         }
 147         elt->valid = 0;
 148         elt->value = NULL;
 149     }
 150     ht->ht_size = 0;
 151     /* the tests reuse the hash table for different types after removing all */
 152     /* so we should allow that by forgetting what type it used to be */
 153     ht->ht_type_methods = NULL;
 154     return PMIX_SUCCESS;
 155 }
 156 
 157 static int                      /* PMIX_ return code */
 158 pmix_hash_grow(pmix_hash_table_t * ht)
 159 {
 160     size_t jj, ii;
 161     pmix_hash_element_t* old_table;
 162     pmix_hash_element_t* new_table;
 163     size_t old_capacity;
 164     size_t new_capacity;
 165 
 166     old_table    = ht->ht_table;
 167     old_capacity = ht->ht_capacity;
 168 
 169     new_capacity = old_capacity * ht->ht_growth_numer / ht->ht_growth_denom;
 170     new_capacity = pmix_hash_round_capacity_up(new_capacity);
 171 
 172     new_table    = (pmix_hash_element_t*) calloc(new_capacity, sizeof(new_table[0]));
 173     if (NULL == new_table) {
 174         return PMIX_ERR_OUT_OF_RESOURCE;
 175     }
 176 
 177     /* for each element of the old table (indexed by jj), insert it
 178        into the new table (indexed by ii), using the hash_elt method
 179        to generically hash an element, then modulo the new capacity,
 180        and using struct-assignment to copy an old element into its
 181        place int he new table.  The hash table never owns the value,
 182        and in the case of ptr keys the old dlements will be blindly
 183        deleted, so we still own the ptr key storage, just in the new
 184        table now */
 185     for (jj = 0; jj < old_capacity; jj += 1) {
 186         pmix_hash_element_t * old_elt;
 187         pmix_hash_element_t * new_elt;
 188         old_elt =  &old_table[jj];
 189         if (old_elt->valid) {
 190             for (ii = (ht->ht_type_methods->hash_elt(old_elt)%new_capacity); ; ii += 1) {
 191                 if (ii == new_capacity) { ii = 0; }
 192                 new_elt = &new_table[ii];
 193                 if (! new_elt->valid) {
 194                     *new_elt = *old_elt;
 195                     break;
 196                 }
 197             }
 198         }
 199     }
 200     /* update with the new, free the old, return */
 201     ht->ht_table = new_table;
 202     ht->ht_capacity = new_capacity;
 203     ht->ht_growth_trigger = new_capacity * ht->ht_density_numer / ht->ht_density_denom;
 204     free(old_table);
 205     return PMIX_SUCCESS;
 206 }
 207 
 208 /* one of the removal functions has determined which element should be
 209    removed.  With the help of the type methods this can be generic.
 210    The important thing is to rehash any valid elements immediately
 211    following the element-being-removed */
 212 static int                      /* PMIX_ return code */
 213 pmix_hash_table_remove_elt_at(pmix_hash_table_t * ht, size_t ii)
 214 {
 215     size_t jj, capacity = ht->ht_capacity;
 216     pmix_hash_element_t* elts = ht->ht_table;
 217     pmix_hash_element_t * elt;
 218 
 219     elt = &elts[ii];
 220 
 221     if (! elt->valid) {
 222         /* huh?  removing a not-valid element? */
 223         return PMIX_ERROR;
 224     }
 225 
 226     elt->valid = 0;
 227     if (ht->ht_type_methods->elt_destructor) {
 228         ht->ht_type_methods->elt_destructor(elt);
 229     }
 230 
 231     /* need to possibly re-insert followers because of the now-gap */
 232     /* E.g., XYyAaCbz.  (where upper is ideal, lower is not)
 233      * remove A
 234      * leaving XYy.aCbz. and we need to reconsider aCbz
 235      * first a gets reinserted where it wants to be: XYya.Cbz.
 236      * next  C doesn't move:                         XYya.Cbz.
 237      * then  b gets put where it wants to be:        XYyabC.z.
 238      * then  z moves down a little:                  XYyabCz..
 239      * then  . means we're done
 240      */
 241     for (ii = ii+1; ; ii += 1) { /* scan immediately following elements */
 242         if (ii == capacity) { ii = 0; }
 243         elt = &elts[ii];
 244         if (! elt->valid) {
 245             break;              /* done */
 246         }
 247         /* rehash it and move it if necessary */
 248         for (jj = ht->ht_type_methods->hash_elt(elt)%capacity; ; jj += 1) {
 249             if (jj == capacity) { jj = 0; }
 250             if (jj == ii) {
 251                 /* already in place, either ideal or best-for-now */
 252                 break;
 253             } else if (! elts[jj].valid) {
 254                 /* move it down, and invaildate where it came from */
 255                 elts[jj] = elts[ii];
 256                 elts[ii].valid = 0;
 257                 break;
 258             } else {
 259                 /* still need to find its place */
 260             }
 261         }
 262     }
 263     ht->ht_size -= 1;
 264     return PMIX_SUCCESS;
 265 }
 266 
 267 
 268 /***************************************************************************/
 269 
 270 static uint64_t
 271 pmix_hash_hash_elt_uint32(pmix_hash_element_t * elt)
 272 {
 273   return elt->key.u32;
 274 }
 275 
 276 static const struct pmix_hash_type_methods_t
 277 pmix_hash_type_methods_uint32 = {
 278     NULL,
 279     pmix_hash_hash_elt_uint32
 280 };
 281 
 282 int                             /* PMIX_ return code */
 283 pmix_hash_table_get_value_uint32(pmix_hash_table_t* ht, uint32_t key, void * *value)
 284 {
 285     size_t ii, capacity = ht->ht_capacity;
 286     pmix_hash_element_t * elt;
 287 
 288 #if PMIX_ENABLE_DEBUG
 289     if(capacity == 0) {
 290         pmix_output(0, "pmix_hash_table_get_value_uint32:"
 291                     "pmix_hash_table_init() has not been called");
 292         return PMIX_ERROR;
 293     }
 294     if (NULL != ht->ht_type_methods &&
 295         &pmix_hash_type_methods_uint32 != ht->ht_type_methods) {
 296         pmix_output(0, "pmix_hash_table_get_value_uint32:"
 297                     "hash table is for a different key type");
 298             return PMIX_ERROR;
 299     }
 300 #endif
 301 
 302     ht->ht_type_methods = &pmix_hash_type_methods_uint32;
 303     for (ii = key%capacity; ; ii += 1) {
 304         if (ii == capacity) { ii = 0; }
 305         elt = &ht->ht_table[ii];
 306         if (! elt->valid) {
 307             return PMIX_ERR_NOT_FOUND;
 308         } else if (elt->key.u32 == key) {
 309             *value = elt->value;
 310             return PMIX_SUCCESS;
 311         } else {
 312             /* keey looking */
 313         }
 314     }
 315 
 316 }
 317 
 318 int                             /* PMIX_ return code */
 319 pmix_hash_table_set_value_uint32(pmix_hash_table_t * ht, uint32_t key, void * value)
 320 {
 321     int rc;
 322     size_t ii, capacity = ht->ht_capacity;
 323     pmix_hash_element_t * elt;
 324 
 325 #if PMIX_ENABLE_DEBUG
 326     if(capacity == 0) {
 327         pmix_output(0, "pmix_hash_table_set_value_uint32:"
 328                    "pmix_hash_table_init() has not been called");
 329         return PMIX_ERR_BAD_PARAM;
 330     }
 331     if (NULL != ht->ht_type_methods &&
 332         &pmix_hash_type_methods_uint32 != ht->ht_type_methods) {
 333         pmix_output(0, "pmix_hash_table_set_value_uint32:"
 334                     "hash table is for a different key type");
 335             return PMIX_ERROR;
 336     }
 337 #endif
 338 
 339     ht->ht_type_methods = &pmix_hash_type_methods_uint32;
 340     for (ii = key%capacity; ; ii += 1) {
 341         if (ii == capacity) { ii = 0; }
 342         elt = &ht->ht_table[ii];
 343         if (! elt->valid) {
 344             /* new entry */
 345             elt->key.u32 = key;
 346             elt->value = value;
 347             elt->valid = 1;
 348             ht->ht_size += 1;
 349             if (ht->ht_size >= ht->ht_growth_trigger) {
 350                 if (PMIX_SUCCESS != (rc = pmix_hash_grow(ht))) {
 351                     return rc;
 352                 }
 353             }
 354             return PMIX_SUCCESS;
 355         } else if (elt->key.u32 == key) {
 356             /* replace existing element */
 357             elt->value = value;
 358             return PMIX_SUCCESS;
 359         } else {
 360             /* keep looking */
 361         }
 362     }
 363 }
 364 
 365 int
 366 pmix_hash_table_remove_value_uint32(pmix_hash_table_t * ht, uint32_t key)
 367 {
 368     size_t ii, capacity = ht->ht_capacity;
 369 
 370 #if PMIX_ENABLE_DEBUG
 371     if(capacity == 0) {
 372         pmix_output(0, "pmix_hash_table_get_value_uint32:"
 373                     "pmix_hash_table_init() has not been called");
 374         return PMIX_ERROR;
 375     }
 376     if (NULL != ht->ht_type_methods &&
 377         &pmix_hash_type_methods_uint32 != ht->ht_type_methods) {
 378         pmix_output(0, "pmix_hash_table_remove_value_uint32:"
 379                     "hash table is for a different key type");
 380             return PMIX_ERROR;
 381     }
 382 #endif
 383 
 384     ht->ht_type_methods = &pmix_hash_type_methods_uint32;
 385     for (ii = key%capacity; ; ii += 1) {
 386         pmix_hash_element_t * elt;
 387         if (ii == capacity) ii = 0;
 388         elt = &ht->ht_table[ii];
 389         if (! elt->valid) {
 390             return PMIX_ERR_NOT_FOUND;
 391         } else if (elt->key.u32 == key) {
 392             return pmix_hash_table_remove_elt_at(ht, ii);
 393         } else {
 394             /* keep looking */
 395         }
 396     }
 397 }
 398 
 399 
 400 /***************************************************************************/
 401 
 402 
 403 static uint64_t
 404 pmix_hash_hash_elt_uint64(pmix_hash_element_t * elt)
 405 {
 406   return elt->key.u64;
 407 }
 408 
 409 static const struct pmix_hash_type_methods_t
 410 pmix_hash_type_methods_uint64 = {
 411     NULL,
 412     pmix_hash_hash_elt_uint64
 413 };
 414 
 415 int                             /* PMIX_ return code */
 416 pmix_hash_table_get_value_uint64(pmix_hash_table_t * ht, uint64_t key, void * *value)
 417 {
 418     size_t ii;
 419     size_t capacity = ht->ht_capacity;
 420     pmix_hash_element_t * elt;
 421 
 422 #if PMIX_ENABLE_DEBUG
 423     if(capacity == 0) {
 424         pmix_output(0, "pmix_hash_table_get_value_uint64:"
 425                    "pmix_hash_table_init() has not been called");
 426         return PMIX_ERROR;
 427     }
 428     if (NULL != ht->ht_type_methods &&
 429         &pmix_hash_type_methods_uint64 != ht->ht_type_methods) {
 430         pmix_output(0, "pmix_hash_table_get_value_uint64:"
 431                     "hash table is for a different key type");
 432             return PMIX_ERROR;
 433     }
 434 #endif
 435 
 436     ht->ht_type_methods = &pmix_hash_type_methods_uint64;
 437     for (ii = key%capacity; ; ii += 1) {
 438         if (ii == capacity) { ii = 0; }
 439         elt = &ht->ht_table[ii];
 440         if (! elt->valid) {
 441             return PMIX_ERR_NOT_FOUND;
 442         } else if (elt->key.u64 == key) {
 443             *value = elt->value;
 444             return PMIX_SUCCESS;
 445         } else {
 446             /* keep looking */
 447         }
 448     }
 449 
 450 }
 451 
 452 int                             /* PMIX_ return code */
 453 pmix_hash_table_set_value_uint64(pmix_hash_table_t * ht, uint64_t key, void * value)
 454 {
 455     int rc;
 456     size_t ii, capacity = ht->ht_capacity;
 457     pmix_hash_element_t * elt;
 458 
 459 #if PMIX_ENABLE_DEBUG
 460     if(capacity == 0) {
 461         pmix_output(0, "pmix_hash_table_set_value_uint64:"
 462                    "pmix_hash_table_init() has not been called");
 463         return PMIX_ERR_BAD_PARAM;
 464     }
 465     if (NULL != ht->ht_type_methods &&
 466         &pmix_hash_type_methods_uint64 != ht->ht_type_methods) {
 467         pmix_output(0, "pmix_hash_table_set_value_uint64:"
 468                     "hash table is for a different key type");
 469             return PMIX_ERROR;
 470     }
 471 #endif
 472 
 473     ht->ht_type_methods = &pmix_hash_type_methods_uint64;
 474     for (ii = key%capacity; ; ii += 1) {
 475         if (ii == capacity) { ii = 0; }
 476         elt = &ht->ht_table[ii];
 477         if (! elt->valid) {
 478             /* new entry */
 479             elt->key.u64 = key;
 480             elt->value = value;
 481             elt->valid = 1;
 482             ht->ht_size += 1;
 483             if (ht->ht_size >= ht->ht_growth_trigger) {
 484                 if (PMIX_SUCCESS != (rc = pmix_hash_grow(ht))) {
 485                     return rc;
 486                 }
 487             }
 488             return PMIX_SUCCESS;
 489         } else if (elt->key.u64 == key) {
 490             elt->value = value;
 491             return PMIX_SUCCESS;
 492         } else {
 493             /* keep looking */
 494         }
 495     }
 496 }
 497 
 498 
 499 int                             /* PMIX_ return code */
 500 pmix_hash_table_remove_value_uint64(pmix_hash_table_t * ht, uint64_t key)
 501 {
 502     size_t ii, capacity = ht->ht_capacity;
 503 
 504 #if PMIX_ENABLE_DEBUG
 505     if(capacity == 0) {
 506         pmix_output(0, "pmix_hash_table_get_value_uint64:"
 507                     "pmix_hash_table_init() has not been called");
 508         return PMIX_ERROR;
 509     }
 510     if (NULL != ht->ht_type_methods &&
 511         &pmix_hash_type_methods_uint64 != ht->ht_type_methods) {
 512         pmix_output(0, "pmix_hash_table_remove_value_uint64:"
 513                     "hash table is for a different key type");
 514             return PMIX_ERROR;
 515     }
 516 #endif
 517 
 518     ht->ht_type_methods = &pmix_hash_type_methods_uint64;
 519     for (ii = key%capacity; ; ii += 1) {
 520         pmix_hash_element_t * elt;
 521         if (ii == capacity) { ii = 0; }
 522         elt = &ht->ht_table[ii];
 523         if (! elt->valid) {
 524             return PMIX_ERR_NOT_FOUND;
 525         } else if (elt->key.u64 == key) {
 526             return pmix_hash_table_remove_elt_at(ht, ii);
 527         } else {
 528             /* keep looking */
 529         }
 530     }
 531 }
 532 
 533 
 534 /***************************************************************************/
 535 
 536 /* helper function used in several places */
 537 static uint64_t
 538 pmix_hash_hash_key_ptr(const void * key, size_t key_size)
 539 {
 540     uint64_t hash;
 541     const unsigned char *scanner;
 542     size_t ii;
 543 
 544     hash = 0;
 545     scanner = (const unsigned char *)key;
 546     for (ii = 0; ii < key_size; ii += 1) {
 547         hash = HASH_MULTIPLIER*hash + *scanner++;
 548     }
 549     return hash;
 550 }
 551 
 552 /* ptr methods */
 553 
 554 static void
 555 pmix_hash_destruct_elt_ptr(pmix_hash_element_t * elt)
 556 {
 557     elt->key.ptr.key_size = 0;
 558     void * key = (void *) elt->key.ptr.key; /* cast away const so we can free it */
 559     if (NULL != key) {
 560         elt->key.ptr.key = NULL;
 561         free(key);
 562     }
 563 }
 564 
 565 static uint64_t
 566 pmix_hash_hash_elt_ptr(pmix_hash_element_t * elt)
 567 {
 568     return pmix_hash_hash_key_ptr(elt->key.ptr.key, elt->key.ptr.key_size);
 569 }
 570 
 571 static const struct pmix_hash_type_methods_t
 572 pmix_hash_type_methods_ptr = {
 573     pmix_hash_destruct_elt_ptr,
 574     pmix_hash_hash_elt_ptr
 575 };
 576 
 577 int                             /* PMIX_ return code */
 578 pmix_hash_table_get_value_ptr(pmix_hash_table_t * ht,
 579                               const void * key, size_t key_size,
 580                               void * *value)
 581 {
 582     size_t ii, capacity = ht->ht_capacity;
 583     pmix_hash_element_t * elt;
 584 
 585 #if PMIX_ENABLE_DEBUG
 586     if(capacity == 0) {
 587         pmix_output(0, "pmix_hash_table_get_value_ptr:"
 588                    "pmix_hash_table_init() has not been called");
 589         return PMIX_ERROR;
 590     }
 591     if (NULL != ht->ht_type_methods &&
 592         &pmix_hash_type_methods_ptr != ht->ht_type_methods) {
 593         pmix_output(0, "pmix_hash_table_get_value_ptr:"
 594                     "hash table is for a different key type");
 595             return PMIX_ERROR;
 596     }
 597 #endif
 598 
 599     ht->ht_type_methods = &pmix_hash_type_methods_ptr;
 600     for (ii = pmix_hash_hash_key_ptr(key, key_size)%capacity; ; ii += 1) {
 601         if (ii == capacity) { ii = 0; }
 602         elt = &ht->ht_table[ii];
 603         if (! elt->valid) {
 604             return PMIX_ERR_NOT_FOUND;
 605         } else if (elt->key.ptr.key_size == key_size &&
 606                    0 == memcmp(elt->key.ptr.key, key, key_size)) {
 607             *value = elt->value;
 608             return PMIX_SUCCESS;
 609         } else {
 610             /* keep going */
 611         }
 612     }
 613 }
 614 
 615 int                             /* PMIX_ return code */
 616 pmix_hash_table_set_value_ptr(pmix_hash_table_t * ht,
 617                               const void * key, size_t key_size,
 618                               void * value)
 619 {
 620     int rc;
 621     size_t ii, capacity = ht->ht_capacity;
 622     pmix_hash_element_t * elt;
 623 
 624 #if PMIX_ENABLE_DEBUG
 625     if(capacity == 0) {
 626         pmix_output(0, "pmix_hash_table_set_value_ptr:"
 627                    "pmix_hash_table_init() has not been called");
 628         return PMIX_ERR_BAD_PARAM;
 629     }
 630     if (NULL != ht->ht_type_methods &&
 631         &pmix_hash_type_methods_ptr != ht->ht_type_methods) {
 632         pmix_output(0, "pmix_hash_table_set_value_ptr:"
 633                     "hash table is for a different key type");
 634             return PMIX_ERROR;
 635     }
 636 #endif
 637 
 638     ht->ht_type_methods = &pmix_hash_type_methods_ptr;
 639     for (ii = pmix_hash_hash_key_ptr(key, key_size)%capacity; ; ii += 1) {
 640         if (ii == capacity) { ii = 0; }
 641         elt = &ht->ht_table[ii];
 642         if (! elt->valid) {
 643             /* new entry */
 644             void * key_local = malloc(key_size);
 645             memcpy(key_local, key, key_size);
 646             elt->key.ptr.key      = key_local;
 647             elt->key.ptr.key_size = key_size;
 648             elt->value = value;
 649             elt->valid = 1;
 650             ht->ht_size += 1;
 651             if (ht->ht_size >= ht->ht_growth_trigger) {
 652                 if (PMIX_SUCCESS != (rc = pmix_hash_grow(ht))) {
 653                     return rc;
 654                 }
 655             }
 656             return PMIX_SUCCESS;
 657         } else if (elt->key.ptr.key_size == key_size &&
 658                    0 == memcmp(elt->key.ptr.key, key, key_size)) {
 659             /* replace existing value */
 660             elt->value = value;
 661             return PMIX_SUCCESS;
 662         } else {
 663             /* keep looking */
 664         }
 665     }
 666 }
 667 
 668 int                             /* PMIX_ return code */
 669 pmix_hash_table_remove_value_ptr(pmix_hash_table_t * ht,
 670                                  const void * key, size_t key_size)
 671 {
 672     size_t ii, capacity = ht->ht_capacity;
 673 
 674 #if PMIX_ENABLE_DEBUG
 675     if(capacity == 0) {
 676         pmix_output(0, "pmix_hash_table_get_value_ptr:"
 677                     "pmix_hash_table_init() has not been called");
 678         return PMIX_ERROR;
 679     }
 680     if (NULL != ht->ht_type_methods &&
 681         &pmix_hash_type_methods_ptr != ht->ht_type_methods) {
 682         pmix_output(0, "pmix_hash_table_remove_value_ptr:"
 683                     "hash table is for a different key type");
 684             return PMIX_ERROR;
 685     }
 686 #endif
 687 
 688     ht->ht_type_methods = &pmix_hash_type_methods_ptr;
 689     for (ii = pmix_hash_hash_key_ptr(key, key_size)%capacity; ; ii += 1) {
 690         pmix_hash_element_t * elt;
 691         if (ii == capacity) { ii = 0; }
 692         elt = &ht->ht_table[ii];
 693         if (! elt->valid) {
 694             return PMIX_ERR_NOT_FOUND;
 695         } else if (elt->key.ptr.key_size == key_size &&
 696                    0 == memcmp(elt->key.ptr.key, key, key_size)) {
 697             return pmix_hash_table_remove_elt_at(ht, ii);
 698         } else {
 699             /* keep looking */
 700         }
 701     }
 702 }
 703 
 704 /***************************************************************************/
 705 /* Traversals */
 706 
 707 static int                      /* PMIX_ return code */
 708 pmix_hash_table_get_next_elt(pmix_hash_table_t *ht,
 709                              pmix_hash_element_t * prev_elt, /* NULL means find first */
 710                              pmix_hash_element_t * *next_elt)
 711 {
 712   pmix_hash_element_t* elts = ht->ht_table;
 713   size_t ii, capacity = ht->ht_capacity;
 714 
 715   for (ii = (NULL == prev_elt ? 0 : (prev_elt-elts)+1); ii < capacity; ii += 1) {
 716     pmix_hash_element_t * elt = &elts[ii];
 717     if (elt->valid) {
 718       *next_elt = elt;
 719       return PMIX_SUCCESS;
 720     }
 721   }
 722   return PMIX_ERROR;
 723 }
 724 
 725 int                             /* PMIX_ return code */
 726 pmix_hash_table_get_first_key_uint32(pmix_hash_table_t * ht,
 727                                      uint32_t *key, void * *value,
 728                                      void * *node)
 729 {
 730   return pmix_hash_table_get_next_key_uint32(ht, key, value, NULL, node);
 731 }
 732 
 733 int                             /* PMIX_ return code */
 734 pmix_hash_table_get_next_key_uint32(pmix_hash_table_t * ht,
 735                                     uint32_t *key, void * *value,
 736                                     void * in_node, void * *out_node)
 737 {
 738   pmix_hash_element_t * elt;
 739   if (PMIX_SUCCESS == pmix_hash_table_get_next_elt(ht, (pmix_hash_element_t *) in_node, &elt)) {
 740     *key       = elt->key.u32;
 741     *value     = elt->value;
 742     *out_node  = elt;
 743     return PMIX_SUCCESS;
 744   }
 745   return PMIX_ERROR;
 746 }
 747 
 748 int                             /* PMIX_ return code */
 749 pmix_hash_table_get_first_key_ptr(pmix_hash_table_t * ht,
 750                                   void * *key, size_t *key_size, void * *value,
 751                                   void * *node)
 752 {
 753   return pmix_hash_table_get_next_key_ptr(ht, key, key_size, value, NULL, node);
 754 }
 755 
 756 int                             /* PMIX_ return code */
 757 pmix_hash_table_get_next_key_ptr(pmix_hash_table_t * ht,
 758                                  void * *key, size_t *key_size, void * *value,
 759                                  void * in_node, void * *out_node)
 760 {
 761   pmix_hash_element_t * elt;
 762   if (PMIX_SUCCESS == pmix_hash_table_get_next_elt(ht, (pmix_hash_element_t *) in_node, &elt)) {
 763     *key       = (void *)elt->key.ptr.key;
 764     *key_size  = elt->key.ptr.key_size;
 765     *value     = elt->value;
 766     *out_node  = elt;
 767     return PMIX_SUCCESS;
 768   }
 769   return PMIX_ERROR;
 770 }
 771 
 772 int                             /* PMIX_ return code */
 773 pmix_hash_table_get_first_key_uint64(pmix_hash_table_t * ht,
 774                                      uint64_t *key, void * *value,
 775                                      void * *node)
 776 {
 777   return pmix_hash_table_get_next_key_uint64(ht, key, value, NULL, node);
 778 }
 779 
 780 int                             /* PMIX_ return code */
 781 pmix_hash_table_get_next_key_uint64(pmix_hash_table_t * ht,
 782                                     uint64_t *key, void * *value,
 783                                     void * in_node, void * *out_node)
 784 {
 785   pmix_hash_element_t * elt;
 786   if (PMIX_SUCCESS == pmix_hash_table_get_next_elt(ht, (pmix_hash_element_t *) in_node, &elt)) {
 787     *key       = elt->key.u64;
 788     *value     = elt->value;
 789     *out_node  = elt;
 790     return PMIX_SUCCESS;
 791   }
 792   return PMIX_ERROR;
 793 }
 794 
 795 /* there was/is no traversal for the ptr case; it would go here */
 796 /* interact with the class-like mechanism */
/* [<][>][^][v][top][bottom][index][help] */
root/opal/mca/pmix/pmix4x/pmix/src/class/pmix_hash_table.c

DEFINITIONS
