opal/class/opal_hash

/* [<][>][^][v][top][bottom][index][help] */
This source file includes following definitions.
opal_hash_table_construct
opal_hash_table_destruct
opal_hash_round_capacity_up
opal_hash_table_init2
opal_hash_table_init
opal_hash_table_remove_all
opal_hash_grow
opal_hash_table_remove_elt_at
opal_hash_hash_elt_uint32
opal_hash_table_get_value_uint32
opal_hash_table_set_value_uint32
opal_hash_table_remove_value_uint32
opal_hash_hash_elt_uint64
opal_hash_table_get_value_uint64
opal_hash_table_set_value_uint64
opal_hash_table_remove_value_uint64
opal_hash_hash_key_ptr
opal_hash_destruct_elt_ptr
opal_hash_hash_elt_ptr
opal_hash_table_get_value_ptr
opal_hash_table_set_value_ptr
opal_hash_table_remove_value_ptr
opal_hash_table_get_next_elt
opal_hash_table_get_first_key_uint32
opal_hash_table_get_next_key_uint32
opal_hash_table_get_first_key_ptr
opal_hash_table_get_next_key_ptr
opal_hash_table_get_first_key_uint64
opal_hash_table_get_next_key_uint64
opal_proc_table_construct
opal_proc_table_destruct
opal_proc_table_init
opal_proc_table_remove_all
opal_proc_table_get_value
opal_proc_table_set_value
opal_proc_table_remove_value
opal_proc_table_get_first_key
opal_proc_table_get_next_key
   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 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      Research Organization for Information Science
  17  *                         and Technology (RIST). All rights reserved.
  18  * $COPYRIGHT$
  19  *
  20  * Additional copyrights may follow
  21  *
  22  * $HEADER$
  23  */
  24 
  25 #include "opal_config.h"
  26 
  27 #include <string.h>
  28 #include <stdlib.h>
  29 
  30 #include "opal/util/output.h"
  31 #include "opal/class/opal_hash_table.h"
  32 #include "opal/constants.h"
  33 
  34 /*
  35  * opal_hash_table_t
  36  *
  37  * Sketch: [Contributed by David Linden of Hewlett-Packard]
  38  *
  39  * This has been found to be good for search and insert and
  40  * (seldom-)remove, all with probablistic O(1) time.  Having a good
  41  * distribution of the hash indices is important, so even if you know
  42  * the keys distribute well under a mask, that micro-optimization
  43  * isn't worth doing.
  44  *
  45  * One aspect is that the concept of buckets and elements is
  46  * unified. The buckets aka elements are in a single array, each
  47  * element having a valid flag.  The key hashes to a keyhash, the
  48  * keyhash determines the first index to probe.  Missing probes search
  49  * forward (wrapping) until the key is found or an invalid entry is
  50  * found.
  51  *
  52  * One parameter of the hash table is a maximum density, which must be
  53  * less than 1, expressed a numerator and denominator.  1/2 seems to
  54  * work well.  A density less than 1 ensures the search will stop
  55  * because searching will eventually find an invalid element.  At
  56  * maximum density, assuming random usage of the elements, the
  57  * expected search length is 1/(1-density); for a density of 1/2, this
  58  * is 2.
  59  *
  60  * I believe this blinded bucket/element scheme is actually more
  61  * storage-efficient than a bucket having a linear list of elements.
  62  * It is certainly better on the cache.
  63  *
  64  * Another parameter is the growth factor, another ratio, greater than
  65  * 1, expressed as a numerator and denominator.  2/1 seems to work
  66  * well.  When the hash table reaches maximum density, it is grown by
  67  * the growth factor (thus reducing the density).  Growing requires
  68  * rehashing and reinserting existing elements.  It turns out this
  69  * keeps insertion at O(1): multiplies the coefficient by
  70  * growth/(growth-1); for a growth of 2/1 this is 2.
  71  *
  72  * The key is hashed to a keyhash.  The keyhash determines the first
  73  * index to probe by using the remainder of the keyhash by the table's
  74  * 'capacity.'  The capacity is not a power of 2.  (Keys that vary
  75  * only in the high 32 bits of a 64 bit key would always colide with a
  76  * power-of-2 capacity.)  Rather, the capacity is arranged not to be a
  77  * multiple of 2, 3 or 5.  A potential capacity is rounded up to be (1
  78  * mod 30).
  79  *
  80  * Removing a key is the most involved operation.  It is necessary to
  81  * rehash any valid elements immediately after the removed element,
  82  * because some (perhaps all) of those elements would normally hash
  83  * lower if the removed key were never there.  This remains O(1); the
  84  * implementation just needs to be a little careful.
  85  *
  86  */
  87 
  88 #define HASH_MULTIPLIER 31
  89 
  90 /*
  91  * Define the structs that are opaque in the .h
  92  */
  93 
  94 struct opal_hash_element_t {
  95     int         valid;          /* whether this element is valid */
  96     union {                     /* the key, in its various forms */
  97         uint32_t        u32;
  98         uint64_t        u64;
  99         struct {
 100             const void * key;
 101             size_t      key_size;
 102         }       ptr;
 103     }           key;
 104     void *      value;          /* the value */
 105 };
 106 typedef struct opal_hash_element_t opal_hash_element_t;
 107 
 108 struct opal_hash_type_methods_t {
 109     /* Frees any storage associated with the element
 110      * The value is not owned by the hash table
 111      * The key,key_size of pointer keys is
 112      */
 113     void        (*elt_destructor)(opal_hash_element_t * elt);
 114     /* Hash the key of the element -- for growing and adjusting-after-removal */
 115     uint64_t    (*hash_elt)(opal_hash_element_t * elt);
 116 };
 117 
 118 /* interact with the class-like mechanism */
 119 
 120 static void opal_hash_table_construct(opal_hash_table_t* ht);
 121 static void opal_hash_table_destruct(opal_hash_table_t* ht);
 122 
 123 OBJ_CLASS_INSTANCE(
 124     opal_hash_table_t,
 125     opal_object_t,
 126     opal_hash_table_construct,
 127     opal_hash_table_destruct
 128 );
 129 
 130 static void
 131 opal_hash_table_construct(opal_hash_table_t* ht)
 132 {
 133   ht->ht_table = NULL;
 134   ht->ht_capacity = ht->ht_size = ht->ht_growth_trigger = 0;
 135   ht->ht_density_numer = ht->ht_density_denom = 0;
 136   ht->ht_growth_numer = ht->ht_growth_denom = 0;
 137   ht->ht_type_methods = NULL;
 138 }
 139 
 140 static void
 141 opal_hash_table_destruct(opal_hash_table_t* ht)
 142 {
 143     opal_hash_table_remove_all(ht);
 144     free(ht->ht_table);
 145 }
 146 
 147 /*
 148  * Init, etc
 149  */
 150 
 151 static size_t
 152 opal_hash_round_capacity_up(size_t capacity)
 153 {
 154     /* round up to (1 mod 30) */
 155     return ((capacity+29)/30*30 + 1);
 156 }
 157 
 158 /* this could be the new init if people wanted a more general API */
 159 /* (that's why it isn't static) */
 160 int                             /* OPAL_ return code */
 161 opal_hash_table_init2(opal_hash_table_t* ht, size_t estimated_max_size,
 162                       int density_numer, int density_denom,
 163                       int growth_numer, int growth_denom)
 164 {
 165     size_t est_capacity = estimated_max_size * density_denom / density_numer;
 166     size_t capacity = opal_hash_round_capacity_up(est_capacity);
 167     ht->ht_table = (opal_hash_element_t*) calloc(capacity, sizeof(opal_hash_element_t));
 168     if (NULL == ht->ht_table) {
 169         return OPAL_ERR_OUT_OF_RESOURCE;
 170     }
 171     ht->ht_capacity       = capacity;
 172     ht->ht_density_numer  = density_numer;
 173     ht->ht_density_denom  = density_denom;
 174     ht->ht_growth_numer   = growth_numer;
 175     ht->ht_growth_denom   = growth_denom;
 176     ht->ht_growth_trigger = capacity * density_numer / density_denom;
 177     ht->ht_type_methods   = NULL;
 178     return OPAL_SUCCESS;
 179 }
 180 
 181 int                             /* OPAL_ return code */
 182 opal_hash_table_init(opal_hash_table_t* ht, size_t table_size)
 183 {
 184     /* default to density of 1/2 and growth of 2/1 */
 185     return opal_hash_table_init2(ht, table_size, 1, 2, 2, 1);
 186 }
 187 
 188 int                             /* OPAL_ return code */
 189 opal_hash_table_remove_all(opal_hash_table_t* ht)
 190 {
 191     size_t ii;
 192     for (ii = 0; ii < ht->ht_capacity; ii += 1) {
 193         opal_hash_element_t * elt = &ht->ht_table[ii];
 194         if (elt->valid && ht->ht_type_methods && ht->ht_type_methods->elt_destructor) {
 195             ht->ht_type_methods->elt_destructor(elt);
 196         }
 197         elt->valid = 0;
 198         elt->value = NULL;
 199     }
 200     ht->ht_size = 0;
 201     /* the tests reuse the hash table for different types after removing all */
 202     /* so we should allow that by forgetting what type it used to be */
 203     ht->ht_type_methods = NULL;
 204     return OPAL_SUCCESS;
 205 }
 206 
 207 static int                      /* OPAL_ return code */
 208 opal_hash_grow(opal_hash_table_t * ht)
 209 {
 210     size_t jj, ii;
 211     opal_hash_element_t* old_table;
 212     opal_hash_element_t* new_table;
 213     size_t old_capacity;
 214     size_t new_capacity;
 215 
 216     old_table    = ht->ht_table;
 217     old_capacity = ht->ht_capacity;
 218 
 219     new_capacity = old_capacity * ht->ht_growth_numer / ht->ht_growth_denom;
 220     new_capacity = opal_hash_round_capacity_up(new_capacity);
 221 
 222     new_table    = (opal_hash_element_t*) calloc(new_capacity, sizeof(new_table[0]));
 223     if (NULL == new_table) {
 224         return OPAL_ERR_OUT_OF_RESOURCE;
 225     }
 226 
 227     /* for each element of the old table (indexed by jj), insert it
 228        into the new table (indexed by ii), using the hash_elt method
 229        to generically hash an element, then modulo the new capacity,
 230        and using struct-assignment to copy an old element into its
 231        place int he new table.  The hash table never owns the value,
 232        and in the case of ptr keys the old dlements will be blindly
 233        deleted, so we still own the ptr key storage, just in the new
 234        table now */
 235     for (jj = 0; jj < old_capacity; jj += 1) {
 236         opal_hash_element_t * old_elt;
 237         opal_hash_element_t * new_elt;
 238         old_elt =  &old_table[jj];
 239         if (old_elt->valid) {
 240             for (ii = (ht->ht_type_methods->hash_elt(old_elt)%new_capacity); ; ii += 1) {
 241                 if (ii == new_capacity) { ii = 0; }
 242                 new_elt = &new_table[ii];
 243                 if (! new_elt->valid) {
 244                     *new_elt = *old_elt;
 245                     break;
 246                 }
 247             }
 248         }
 249     }
 250     /* update with the new, free the old, return */
 251     ht->ht_table = new_table;
 252     ht->ht_capacity = new_capacity;
 253     ht->ht_growth_trigger = new_capacity * ht->ht_density_numer / ht->ht_density_denom;
 254     free(old_table);
 255     return OPAL_SUCCESS;
 256 }
 257 
 258 /* one of the removal functions has determined which element should be
 259    removed.  With the help of the type methods this can be generic.
 260    The important thing is to rehash any valid elements immediately
 261    following the element-being-removed */
 262 static int                      /* OPAL_ return code */
 263 opal_hash_table_remove_elt_at(opal_hash_table_t * ht, size_t ii)
 264 {
 265     size_t jj, capacity = ht->ht_capacity;
 266     opal_hash_element_t* elts = ht->ht_table;
 267     opal_hash_element_t * elt;
 268 
 269     elt = &elts[ii];
 270 
 271     if (! elt->valid) {
 272         /* huh?  removing a not-valid element? */
 273         return OPAL_ERROR;
 274     }
 275 
 276     elt->valid = 0;
 277     if (ht->ht_type_methods->elt_destructor) {
 278         ht->ht_type_methods->elt_destructor(elt);
 279     }
 280 
 281     /* need to possibly re-insert followers because of the now-gap */
 282     /* E.g., XYyAaCbz.  (where upper is ideal, lower is not)
 283      * remove A
 284      * leaving XYy.aCbz. and we need to reconsider aCbz
 285      * first a gets reinserted where it wants to be: XYya.Cbz.
 286      * next  C doesn't move:                         XYya.Cbz.
 287      * then  b gets put where it wants to be:        XYyabC.z.
 288      * then  z moves down a little:                  XYyabCz..
 289      * then  . means we're done
 290      */
 291     for (ii = ii+1; ; ii += 1) { /* scan immediately following elements */
 292         if (ii == capacity) { ii = 0; }
 293         elt = &elts[ii];
 294         if (! elt->valid) {
 295             break;              /* done */
 296         }
 297         /* rehash it and move it if necessary */
 298         for (jj = ht->ht_type_methods->hash_elt(elt)%capacity; ; jj += 1) {
 299             if (jj == capacity) { jj = 0; }
 300             if (jj == ii) {
 301                 /* already in place, either ideal or best-for-now */
 302                 break;
 303             } else if (! elts[jj].valid) {
 304                 /* move it down, and invaildate where it came from */
 305                 elts[jj] = elts[ii];
 306                 elts[ii].valid = 0;
 307                 break;
 308             } else {
 309                 /* still need to find its place */
 310             }
 311         }
 312     }
 313     ht->ht_size -= 1;
 314     return OPAL_SUCCESS;
 315 }
 316 
 317 
 318 /***************************************************************************/
 319 
 320 static uint64_t
 321 opal_hash_hash_elt_uint32(opal_hash_element_t * elt)
 322 {
 323   return elt->key.u32;
 324 }
 325 
 326 static const struct opal_hash_type_methods_t
 327 opal_hash_type_methods_uint32 = {
 328     NULL,
 329     opal_hash_hash_elt_uint32
 330 };
 331 
 332 int                             /* OPAL_ return code */
 333 opal_hash_table_get_value_uint32(opal_hash_table_t* ht, uint32_t key, void * *value)
 334 {
 335     size_t ii, capacity = ht->ht_capacity;
 336     opal_hash_element_t * elt;
 337 
 338 #if OPAL_ENABLE_DEBUG
 339     if(capacity == 0) {
 340         opal_output(0, "opal_hash_table_get_value_uint32:"
 341                     "opal_hash_table_init() has not been called");
 342         return OPAL_ERROR;
 343     }
 344     if (NULL != ht->ht_type_methods &&
 345         &opal_hash_type_methods_uint32 != ht->ht_type_methods) {
 346         opal_output(0, "opal_hash_table_get_value_uint32:"
 347                     "hash table is for a different key type");
 348             return OPAL_ERROR;
 349     }
 350 #endif
 351 
 352     ht->ht_type_methods = &opal_hash_type_methods_uint32;
 353     for (ii = key%capacity; ; ii += 1) {
 354         if (ii == capacity) { ii = 0; }
 355         elt = &ht->ht_table[ii];
 356         if (! elt->valid) {
 357             return OPAL_ERR_NOT_FOUND;
 358         } else if (elt->key.u32 == key) {
 359             *value = elt->value;
 360             return OPAL_SUCCESS;
 361         } else {
 362             /* keey looking */
 363         }
 364     }
 365 
 366 }
 367 
 368 int                             /* OPAL_ return code */
 369 opal_hash_table_set_value_uint32(opal_hash_table_t * ht, uint32_t key, void * value)
 370 {
 371     int rc;
 372     size_t ii, capacity = ht->ht_capacity;
 373     opal_hash_element_t * elt;
 374 
 375 #if OPAL_ENABLE_DEBUG
 376     if(capacity == 0) {
 377         opal_output(0, "opal_hash_table_set_value_uint32:"
 378                    "opal_hash_table_init() has not been called");
 379         return OPAL_ERR_BAD_PARAM;
 380     }
 381     if (NULL != ht->ht_type_methods &&
 382         &opal_hash_type_methods_uint32 != ht->ht_type_methods) {
 383         opal_output(0, "opal_hash_table_set_value_uint32:"
 384                     "hash table is for a different key type");
 385             return OPAL_ERROR;
 386     }
 387 #endif
 388 
 389     ht->ht_type_methods = &opal_hash_type_methods_uint32;
 390     for (ii = key%capacity; ; ii += 1) {
 391         if (ii == capacity) { ii = 0; }
 392         elt = &ht->ht_table[ii];
 393         if (! elt->valid) {
 394             /* new entry */
 395             elt->key.u32 = key;
 396             elt->value = value;
 397             elt->valid = 1;
 398             ht->ht_size += 1;
 399             if (ht->ht_size >= ht->ht_growth_trigger) {
 400                 if (OPAL_SUCCESS != (rc = opal_hash_grow(ht))) {
 401                     return rc;
 402                 }
 403             }
 404             return OPAL_SUCCESS;
 405         } else if (elt->key.u32 == key) {
 406             /* replace existing element */
 407             elt->value = value;
 408             return OPAL_SUCCESS;
 409         } else {
 410             /* keep looking */
 411         }
 412     }
 413 }
 414 
 415 int
 416 opal_hash_table_remove_value_uint32(opal_hash_table_t * ht, uint32_t key)
 417 {
 418     size_t ii, capacity = ht->ht_capacity;
 419 
 420 #if OPAL_ENABLE_DEBUG
 421     if(capacity == 0) {
 422         opal_output(0, "opal_hash_table_get_value_uint32:"
 423                     "opal_hash_table_init() has not been called");
 424         return OPAL_ERROR;
 425     }
 426     if (NULL != ht->ht_type_methods &&
 427         &opal_hash_type_methods_uint32 != ht->ht_type_methods) {
 428         opal_output(0, "opal_hash_table_remove_value_uint32:"
 429                     "hash table is for a different key type");
 430             return OPAL_ERROR;
 431     }
 432 #endif
 433 
 434     ht->ht_type_methods = &opal_hash_type_methods_uint32;
 435     for (ii = key%capacity; ; ii += 1) {
 436         opal_hash_element_t * elt;
 437         if (ii == capacity) ii = 0;
 438         elt = &ht->ht_table[ii];
 439         if (! elt->valid) {
 440             return OPAL_ERR_NOT_FOUND;
 441         } else if (elt->key.u32 == key) {
 442             return opal_hash_table_remove_elt_at(ht, ii);
 443         } else {
 444             /* keep looking */
 445         }
 446     }
 447 }
 448 
 449 
 450 /***************************************************************************/
 451 
 452 
 453 static uint64_t
 454 opal_hash_hash_elt_uint64(opal_hash_element_t * elt)
 455 {
 456   return elt->key.u64;
 457 }
 458 
 459 static const struct opal_hash_type_methods_t
 460 opal_hash_type_methods_uint64 = {
 461     NULL,
 462     opal_hash_hash_elt_uint64
 463 };
 464 
 465 int                             /* OPAL_ return code */
 466 opal_hash_table_get_value_uint64(opal_hash_table_t * ht, uint64_t key, void * *value)
 467 {
 468     size_t ii;
 469     size_t capacity = ht->ht_capacity;
 470     opal_hash_element_t * elt;
 471 
 472 #if OPAL_ENABLE_DEBUG
 473     if(capacity == 0) {
 474         opal_output(0, "opal_hash_table_get_value_uint64:"
 475                    "opal_hash_table_init() has not been called");
 476         return OPAL_ERROR;
 477     }
 478     if (NULL != ht->ht_type_methods &&
 479         &opal_hash_type_methods_uint64 != ht->ht_type_methods) {
 480         opal_output(0, "opal_hash_table_get_value_uint64:"
 481                     "hash table is for a different key type");
 482             return OPAL_ERROR;
 483     }
 484 #endif
 485 
 486     ht->ht_type_methods = &opal_hash_type_methods_uint64;
 487     for (ii = key%capacity; ; ii += 1) {
 488         if (ii == capacity) { ii = 0; }
 489         elt = &ht->ht_table[ii];
 490         if (! elt->valid) {
 491             return OPAL_ERR_NOT_FOUND;
 492         } else if (elt->key.u64 == key) {
 493             *value = elt->value;
 494             return OPAL_SUCCESS;
 495         } else {
 496             /* keep looking */
 497         }
 498     }
 499 
 500 }
 501 
 502 int                             /* OPAL_ return code */
 503 opal_hash_table_set_value_uint64(opal_hash_table_t * ht, uint64_t key, void * value)
 504 {
 505     int rc;
 506     size_t ii, capacity = ht->ht_capacity;
 507     opal_hash_element_t * elt;
 508 
 509 #if OPAL_ENABLE_DEBUG
 510     if(capacity == 0) {
 511         opal_output(0, "opal_hash_table_set_value_uint64:"
 512                    "opal_hash_table_init() has not been called");
 513         return OPAL_ERR_BAD_PARAM;
 514     }
 515     if (NULL != ht->ht_type_methods &&
 516         &opal_hash_type_methods_uint64 != ht->ht_type_methods) {
 517         opal_output(0, "opal_hash_table_set_value_uint64:"
 518                     "hash table is for a different key type");
 519             return OPAL_ERROR;
 520     }
 521 #endif
 522 
 523     ht->ht_type_methods = &opal_hash_type_methods_uint64;
 524     for (ii = key%capacity; ; ii += 1) {
 525         if (ii == capacity) { ii = 0; }
 526         elt = &ht->ht_table[ii];
 527         if (! elt->valid) {
 528             /* new entry */
 529             elt->key.u64 = key;
 530             elt->value = value;
 531             elt->valid = 1;
 532             ht->ht_size += 1;
 533             if (ht->ht_size >= ht->ht_growth_trigger) {
 534                 if (OPAL_SUCCESS != (rc = opal_hash_grow(ht))) {
 535                     return rc;
 536                 }
 537             }
 538             return OPAL_SUCCESS;
 539         } else if (elt->key.u64 == key) {
 540             elt->value = value;
 541             return OPAL_SUCCESS;
 542         } else {
 543             /* keep looking */
 544         }
 545     }
 546 }
 547 
 548 
 549 int                             /* OPAL_ return code */
 550 opal_hash_table_remove_value_uint64(opal_hash_table_t * ht, uint64_t key)
 551 {
 552     size_t ii, capacity = ht->ht_capacity;
 553 
 554 #if OPAL_ENABLE_DEBUG
 555     if(capacity == 0) {
 556         opal_output(0, "opal_hash_table_get_value_uint64:"
 557                     "opal_hash_table_init() has not been called");
 558         return OPAL_ERROR;
 559     }
 560     if (NULL != ht->ht_type_methods &&
 561         &opal_hash_type_methods_uint64 != ht->ht_type_methods) {
 562         opal_output(0, "opal_hash_table_remove_value_uint64:"
 563                     "hash table is for a different key type");
 564             return OPAL_ERROR;
 565     }
 566 #endif
 567 
 568     ht->ht_type_methods = &opal_hash_type_methods_uint64;
 569     for (ii = key%capacity; ; ii += 1) {
 570         opal_hash_element_t * elt;
 571         if (ii == capacity) { ii = 0; }
 572         elt = &ht->ht_table[ii];
 573         if (! elt->valid) {
 574             return OPAL_ERR_NOT_FOUND;
 575         } else if (elt->key.u64 == key) {
 576             return opal_hash_table_remove_elt_at(ht, ii);
 577         } else {
 578             /* keep looking */
 579         }
 580     }
 581 }
 582 
 583 
 584 /***************************************************************************/
 585 
 586 /* helper function used in several places */
 587 static uint64_t
 588 opal_hash_hash_key_ptr(const void * key, size_t key_size)
 589 {
 590     uint64_t hash;
 591     const unsigned char *scanner;
 592     size_t ii;
 593 
 594     hash = 0;
 595     scanner = (const unsigned char *)key;
 596     for (ii = 0; ii < key_size; ii += 1) {
 597         hash = HASH_MULTIPLIER*hash + *scanner++;
 598     }
 599     return hash;
 600 }
 601 
 602 /* ptr methods */
 603 
 604 static void
 605 opal_hash_destruct_elt_ptr(opal_hash_element_t * elt)
 606 {
 607     elt->key.ptr.key_size = 0;
 608     void * key = (void *) elt->key.ptr.key; /* cast away const so we can free it */
 609     if (NULL != key) {
 610         elt->key.ptr.key = NULL;
 611         free(key);
 612     }
 613 }
 614 
 615 static uint64_t
 616 opal_hash_hash_elt_ptr(opal_hash_element_t * elt)
 617 {
 618     return opal_hash_hash_key_ptr(elt->key.ptr.key, elt->key.ptr.key_size);
 619 }
 620 
 621 static const struct opal_hash_type_methods_t
 622 opal_hash_type_methods_ptr = {
 623     opal_hash_destruct_elt_ptr,
 624     opal_hash_hash_elt_ptr
 625 };
 626 
 627 int                             /* OPAL_ return code */
 628 opal_hash_table_get_value_ptr(opal_hash_table_t * ht,
 629                               const void * key, size_t key_size,
 630                               void * *value)
 631 {
 632     size_t ii, capacity = ht->ht_capacity;
 633     opal_hash_element_t * elt;
 634 
 635 #if OPAL_ENABLE_DEBUG
 636     if(capacity == 0) {
 637         opal_output(0, "opal_hash_table_get_value_ptr:"
 638                    "opal_hash_table_init() has not been called");
 639         return OPAL_ERROR;
 640     }
 641     if (NULL != ht->ht_type_methods &&
 642         &opal_hash_type_methods_ptr != ht->ht_type_methods) {
 643         opal_output(0, "opal_hash_table_get_value_ptr:"
 644                     "hash table is for a different key type");
 645             return OPAL_ERROR;
 646     }
 647 #endif
 648 
 649     ht->ht_type_methods = &opal_hash_type_methods_ptr;
 650     for (ii = opal_hash_hash_key_ptr(key, key_size)%capacity; ; ii += 1) {
 651         if (ii == capacity) { ii = 0; }
 652         elt = &ht->ht_table[ii];
 653         if (! elt->valid) {
 654             return OPAL_ERR_NOT_FOUND;
 655         } else if (elt->key.ptr.key_size == key_size &&
 656                    0 == memcmp(elt->key.ptr.key, key, key_size)) {
 657             *value = elt->value;
 658             return OPAL_SUCCESS;
 659         } else {
 660             /* keep going */
 661         }
 662     }
 663 }
 664 
 665 int                             /* OPAL_ return code */
 666 opal_hash_table_set_value_ptr(opal_hash_table_t * ht,
 667                               const void * key, size_t key_size,
 668                               void * value)
 669 {
 670     int rc;
 671     size_t ii, capacity = ht->ht_capacity;
 672     opal_hash_element_t * elt;
 673 
 674 #if OPAL_ENABLE_DEBUG
 675     if(capacity == 0) {
 676         opal_output(0, "opal_hash_table_set_value_ptr:"
 677                    "opal_hash_table_init() has not been called");
 678         return OPAL_ERR_BAD_PARAM;
 679     }
 680     if (NULL != ht->ht_type_methods &&
 681         &opal_hash_type_methods_ptr != ht->ht_type_methods) {
 682         opal_output(0, "opal_hash_table_set_value_ptr:"
 683                     "hash table is for a different key type");
 684             return OPAL_ERROR;
 685     }
 686 #endif
 687 
 688     ht->ht_type_methods = &opal_hash_type_methods_ptr;
 689     for (ii = opal_hash_hash_key_ptr(key, key_size)%capacity; ; ii += 1) {
 690         if (ii == capacity) { ii = 0; }
 691         elt = &ht->ht_table[ii];
 692         if (! elt->valid) {
 693             /* new entry */
 694             void * key_local = malloc(key_size);
 695             memcpy(key_local, key, key_size);
 696             elt->key.ptr.key      = key_local;
 697             elt->key.ptr.key_size = key_size;
 698             elt->value = value;
 699             elt->valid = 1;
 700             ht->ht_size += 1;
 701             if (ht->ht_size >= ht->ht_growth_trigger) {
 702                 if (OPAL_SUCCESS != (rc = opal_hash_grow(ht))) {
 703                     return rc;
 704                 }
 705             }
 706             return OPAL_SUCCESS;
 707         } else if (elt->key.ptr.key_size == key_size &&
 708                    0 == memcmp(elt->key.ptr.key, key, key_size)) {
 709             /* replace existing value */
 710             elt->value = value;
 711             return OPAL_SUCCESS;
 712         } else {
 713             /* keep looking */
 714         }
 715     }
 716 }
 717 
 718 int                             /* OPAL_ return code */
 719 opal_hash_table_remove_value_ptr(opal_hash_table_t * ht,
 720                                  const void * key, size_t key_size)
 721 {
 722     size_t ii, capacity = ht->ht_capacity;
 723 
 724 #if OPAL_ENABLE_DEBUG
 725     if(capacity == 0) {
 726         opal_output(0, "opal_hash_table_get_value_ptr:"
 727                     "opal_hash_table_init() has not been called");
 728         return OPAL_ERROR;
 729     }
 730     if (NULL != ht->ht_type_methods &&
 731         &opal_hash_type_methods_ptr != ht->ht_type_methods) {
 732         opal_output(0, "opal_hash_table_remove_value_ptr:"
 733                     "hash table is for a different key type");
 734             return OPAL_ERROR;
 735     }
 736 #endif
 737 
 738     ht->ht_type_methods = &opal_hash_type_methods_ptr;
 739     for (ii = opal_hash_hash_key_ptr(key, key_size)%capacity; ; ii += 1) {
 740         opal_hash_element_t * elt;
 741         if (ii == capacity) { ii = 0; }
 742         elt = &ht->ht_table[ii];
 743         if (! elt->valid) {
 744             return OPAL_ERR_NOT_FOUND;
 745         } else if (elt->key.ptr.key_size == key_size &&
 746                    0 == memcmp(elt->key.ptr.key, key, key_size)) {
 747             return opal_hash_table_remove_elt_at(ht, ii);
 748         } else {
 749             /* keep looking */
 750         }
 751     }
 752 }
 753 
 754 /***************************************************************************/
 755 /* Traversals */
 756 
 757 static int                      /* OPAL_ return code */
 758 opal_hash_table_get_next_elt(opal_hash_table_t *ht,
 759                              opal_hash_element_t * prev_elt, /* NULL means find first */
 760                              opal_hash_element_t * *next_elt)
 761 {
 762   opal_hash_element_t* elts = ht->ht_table;
 763   size_t ii, capacity = ht->ht_capacity;
 764 
 765   for (ii = (NULL == prev_elt ? 0 : (prev_elt-elts)+1); ii < capacity; ii += 1) {
 766     opal_hash_element_t * elt = &elts[ii];
 767     if (elt->valid) {
 768       *next_elt = elt;
 769       return OPAL_SUCCESS;
 770     }
 771   }
 772   return OPAL_ERROR;
 773 }
 774 
 775 int                             /* OPAL_ return code */
 776 opal_hash_table_get_first_key_uint32(opal_hash_table_t * ht,
 777                                      uint32_t *key, void * *value,
 778                                      void * *node)
 779 {
 780   return opal_hash_table_get_next_key_uint32(ht, key, value, NULL, node);
 781 }
 782 
 783 int                             /* OPAL_ return code */
 784 opal_hash_table_get_next_key_uint32(opal_hash_table_t * ht,
 785                                     uint32_t *key, void * *value,
 786                                     void * in_node, void * *out_node)
 787 {
 788   opal_hash_element_t * elt;
 789   if (OPAL_SUCCESS == opal_hash_table_get_next_elt(ht, (opal_hash_element_t *) in_node, &elt)) {
 790     *key       = elt->key.u32;
 791     *value     = elt->value;
 792     *out_node  = elt;
 793     return OPAL_SUCCESS;
 794   }
 795   return OPAL_ERROR;
 796 }
 797 
 798 int                             /* OPAL_ return code */
 799 opal_hash_table_get_first_key_ptr(opal_hash_table_t * ht,
 800                                   void * *key, size_t *key_size, void * *value,
 801                                   void * *node)
 802 {
 803   return opal_hash_table_get_next_key_ptr(ht, key, key_size, value, NULL, node);
 804 }
 805 
 806 int                             /* OPAL_ return code */
 807 opal_hash_table_get_next_key_ptr(opal_hash_table_t * ht,
 808                                  void * *key, size_t *key_size, void * *value,
 809                                  void * in_node, void * *out_node)
 810 {
 811   opal_hash_element_t * elt;
 812   if (OPAL_SUCCESS == opal_hash_table_get_next_elt(ht, (opal_hash_element_t *) in_node, &elt)) {
 813     *key       = (void *)elt->key.ptr.key;
 814     *key_size  = elt->key.ptr.key_size;
 815     *value     = elt->value;
 816     *out_node  = elt;
 817     return OPAL_SUCCESS;
 818   }
 819   return OPAL_ERROR;
 820 }
 821 
 822 int                             /* OPAL_ return code */
 823 opal_hash_table_get_first_key_uint64(opal_hash_table_t * ht,
 824                                      uint64_t *key, void * *value,
 825                                      void * *node)
 826 {
 827   return opal_hash_table_get_next_key_uint64(ht, key, value, NULL, node);
 828 }
 829 
 830 int                             /* OPAL_ return code */
 831 opal_hash_table_get_next_key_uint64(opal_hash_table_t * ht,
 832                                     uint64_t *key, void * *value,
 833                                     void * in_node, void * *out_node)
 834 {
 835   opal_hash_element_t * elt;
 836   if (OPAL_SUCCESS == opal_hash_table_get_next_elt(ht, (opal_hash_element_t *) in_node, &elt)) {
 837     *key       = elt->key.u64;
 838     *value     = elt->value;
 839     *out_node  = elt;
 840     return OPAL_SUCCESS;
 841   }
 842   return OPAL_ERROR;
 843 }
 844 
 845 /* there was/is no traversal for the ptr case; it would go here */
 846 /* interact with the class-like mechanism */
 847 
 848 static void opal_proc_table_construct(opal_proc_table_t* pt);
 849 static void opal_proc_table_destruct(opal_proc_table_t* pt);
 850 
 851 OBJ_CLASS_INSTANCE(
 852     opal_proc_table_t,
 853     opal_hash_table_t,
 854     opal_proc_table_construct,
 855     opal_proc_table_destruct
 856 );
 857 
 858 static void
 859 opal_proc_table_construct(opal_proc_table_t* pt)
 860 {
 861   pt->pt_size = 0;
 862 }
 863 
 864 static void
 865 opal_proc_table_destruct(opal_proc_table_t* pt)
 866 {
 867 }
 868 
 869 /*
 870  * Init, etc
 871  */
 872 
 873 int opal_proc_table_init(opal_proc_table_t* pt, size_t jobids, size_t vpids) {
 874     int rc;
 875     if (OPAL_SUCCESS != (rc=opal_hash_table_init(&pt->super, jobids))) {
 876         return rc;
 877     }
 878     pt->vpids_size = vpids;
 879     return OPAL_SUCCESS;
 880 }
 881 
 882 int opal_proc_table_remove_all(opal_proc_table_t *pt) {
 883     int rc;
 884     opal_hash_table_t * vpids;
 885     uint32_t jobid;
 886     void * node;
 887 
 888     rc = opal_hash_table_get_first_key_uint32(&pt->super, &jobid, (void **)&vpids, &node);
 889 
 890     if (OPAL_SUCCESS == rc) {
 891         do {
 892             if (NULL != vpids) {
 893                 opal_hash_table_remove_all(vpids);
 894                 OBJ_RELEASE(vpids);
 895             }
 896             rc = opal_hash_table_get_next_key_uint32 (&pt->super, &jobid,
 897                                                (void **) &vpids, node, &node);
 898         } while (OPAL_SUCCESS == rc);
 899     }
 900 
 901     return rc;
 902 }
 903 
 904 int opal_proc_table_get_value(opal_proc_table_t* pt, opal_process_name_t key,
 905                               void** ptr) {
 906     int rc;
 907     opal_hash_table_t * vpids;
 908     rc = opal_hash_table_get_value_uint32(&pt->super, key.jobid, (void **)&vpids);
 909     if (rc != OPAL_SUCCESS) {
 910         return rc;
 911     }
 912     rc = opal_hash_table_get_value_uint32(vpids, key.vpid, ptr);
 913     return rc;
 914 }
 915 
 916 int opal_proc_table_set_value(opal_proc_table_t* pt, opal_process_name_t key, void* value) {
 917     int rc;
 918     opal_hash_table_t * vpids;
 919     rc = opal_hash_table_get_value_uint32(&pt->super, key.jobid, (void **)&vpids);
 920     if (rc != OPAL_SUCCESS) {
 921         vpids = OBJ_NEW(opal_hash_table_t);
 922         if (NULL == vpids) {
 923             return OPAL_ERR_OUT_OF_RESOURCE;
 924         }
 925         if (OPAL_SUCCESS != (rc=opal_hash_table_init(vpids, pt->vpids_size))) {
 926             OBJ_RELEASE(vpids);
 927             return rc;
 928         }
 929         if (OPAL_SUCCESS != (rc=opal_hash_table_set_value_uint32(&pt->super, key.jobid, vpids))) {
 930             OBJ_RELEASE(vpids);
 931             return rc;
 932         }
 933     }
 934     rc = opal_hash_table_set_value_uint32(vpids, key.vpid, value);
 935     return rc;
 936 }
 937 
 938 int opal_proc_table_remove_value(opal_proc_table_t* pt, opal_process_name_t key) {
 939     int rc;
 940     opal_hash_table_t * vpids;
 941     if (OPAL_SUCCESS != (rc=opal_hash_table_get_value_uint32(&pt->super, key.jobid, (void **)&vpids))) {
 942         return rc;
 943     }
 944     if (OPAL_SUCCESS == (rc=opal_hash_table_remove_value_uint32(vpids, key.vpid))) {
 945         if (0 == vpids->ht_size) {
 946             opal_hash_table_remove_value_uint32(&pt->super, key.jobid);
 947             OBJ_RELEASE(vpids);
 948         }
 949     }
 950     return rc;
 951 }
 952 
 953 int opal_proc_table_get_first_key(opal_proc_table_t *pt, opal_process_name_t *key,
 954                                   void **value, void **node1, void **node2) {
 955     int rc;
 956     uint32_t jobid, vpid;
 957     opal_hash_table_t * vpids;
 958     if (OPAL_SUCCESS != (rc=opal_hash_table_get_first_key_uint32(&pt->super, &jobid, (void **)&vpids, node1))) {
 959         return rc;
 960     }
 961     rc = opal_hash_table_get_first_key_uint32(vpids, &vpid, value, node2);
 962     if (OPAL_SUCCESS == rc) {
 963         key->jobid = jobid;
 964         key->vpid = vpid;
 965     }
 966     return rc;
 967 }
 968 
 969 int opal_proc_table_get_next_key(opal_proc_table_t *pt, opal_process_name_t *key,
 970                                  void **value, void *in_node1, void **out_node1,
 971                                  void *in_node2, void **out_node2) {
 972     int rc;
 973     uint32_t jobid = ((opal_hash_element_t *)in_node1)->key.u32;
 974     uint32_t vpid;
 975     opal_hash_table_t * vpids = ((opal_hash_element_t *)in_node1)->value;
 976 
 977     rc = opal_hash_table_get_next_key_uint32(vpids, &vpid, value, in_node2, out_node2);
 978     if (OPAL_SUCCESS == rc) {
 979         key->jobid = jobid;
 980         key->vpid = vpid;
 981         *out_node1 = in_node1;
 982         return rc;
 983     }
 984     if (OPAL_SUCCESS != (rc=opal_hash_table_get_next_key_uint32(&pt->super, &jobid, (void **)&vpids, in_node1, out_node1))) {
 985         return rc;
 986     }
 987     rc = opal_hash_table_get_first_key_uint32(vpids, &vpid, value, out_node2);
 988     if (OPAL_SUCCESS == rc) {
 989         key->jobid = jobid;
 990         key->vpid = vpid;
 991     }
 992     return rc;
 993 }
/* [<][>][^][v][top][bottom][index][help] */
root/opal/class/opal_hash_table.c

DEFINITIONS
