opal/mca/pmix/pmix4x/pmix/src/class/pmix_pointer

/* [<][>][^][v][top][bottom][index][help] */
This source file includes following definitions.
pmix_pointer_array_construct
pmix_pointer_array_destruct
pmix_pointer_array_validate
pmix_pointer_array_init
pmix_pointer_array_add
pmix_pointer_array_set_item
pmix_pointer_array_test_and_set_item
pmix_pointer_array_set_size
grow_table
   1 /* -*- Mode: C; c-basic-offset:4 ; -*- */
   2 /*
   3  * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
   4  *                         University Research and Technology
   5  *                         Corporation.  All rights reserved.
   6  * Copyright (c) 2004-2017 The University of Tennessee and The University
   7  *                         of Tennessee Research Foundation.  All rights
   8  *                         reserved.
   9  * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart,
  10  *                         University of Stuttgart.  All rights reserved.
  11  * Copyright (c) 2004-2005 The Regents of the University of California.
  12  *                         All rights reserved.
  13  * Copyright (c) 2017      Intel, Inc. All rights reserved.
  14  * $COPYRIGHT$
  15  *
  16  * Additional copyrights may follow
  17  *
  18  * $HEADER$
  19  */
  20 
  21 #include "pmix_config.h"
  22 #include "pmix_common.h"
  23 
  24 #include <stdlib.h>
  25 #include <stdio.h>
  26 #include <assert.h>
  27 
  28 #include "src/class/pmix_pointer_array.h"
  29 #include "src/util/output.h"
  30 
  31 static void pmix_pointer_array_construct(pmix_pointer_array_t *);
  32 static void pmix_pointer_array_destruct(pmix_pointer_array_t *);
  33 static bool grow_table(pmix_pointer_array_t *table, int at_least);
  34 
  35 PMIX_CLASS_INSTANCE(pmix_pointer_array_t, pmix_object_t,
  36                     pmix_pointer_array_construct,
  37                     pmix_pointer_array_destruct);
  38 
  39 /*
  40  * pmix_pointer_array constructor
  41  */
  42 static void pmix_pointer_array_construct(pmix_pointer_array_t *array)
  43 {
  44     array->lowest_free = 0;
  45     array->number_free = 0;
  46     array->size = 0;
  47     array->max_size = INT_MAX;
  48     array->block_size = 8;
  49     array->free_bits = NULL;
  50     array->addr = NULL;
  51 }
  52 
  53 /*
  54  * pmix_pointer_array destructor
  55  */
  56 static void pmix_pointer_array_destruct(pmix_pointer_array_t *array)
  57 {
  58     /* free table */
  59     if( NULL != array->free_bits) {
  60         free(array->free_bits);
  61         array->free_bits = NULL;
  62     }
  63     if( NULL != array->addr ) {
  64         free(array->addr);
  65         array->addr = NULL;
  66     }
  67 
  68     array->size = 0;
  69 
  70 }
  71 
  72 #define TYPE_ELEM_COUNT(TYPE, CAP) (((CAP) + 8 * sizeof(TYPE) - 1) / (8 * sizeof(TYPE)))
  73 
  74 /**
  75  * Translate an index position into the free bits array into 2 values, the
  76  * index of the element and the index of the bit position.
  77  */
  78 #define GET_BIT_POS(IDX, BIDX, PIDX)                                    \
  79     do {                                                                \
  80         uint32_t __idx = (uint32_t)(IDX);                               \
  81         (BIDX) = (__idx / (8 * sizeof(uint64_t)));                      \
  82         (PIDX) = (__idx % (8 * sizeof(uint64_t)));                      \
  83     } while(0)
  84 
  85 /**
  86  * A classical find first zero bit (ffs) on a large array. It checks starting
  87  * from the indicated position until it finds a zero bit. If SET is true,
  88  * the bit is set. The position of the bit is returned in store.
  89  *
  90  * According to Section 6.4.4.1 of the C standard we don't need to prepend a type
  91  * indicator to constants (the type is inferred by the compiler according to
  92  * the number of bits necessary to represent it).
  93  */
  94 #define FIND_FIRST_ZERO(START_IDX, STORE)                               \
  95     do {                                                                \
  96         uint32_t __b_idx, __b_pos;                                      \
  97         if( 0 == table->number_free ) {                                 \
  98             (STORE) = table->size;                                      \
  99             break;                                                      \
 100         }                                                               \
 101         GET_BIT_POS((START_IDX), __b_idx, __b_pos);                     \
 102         for (; table->free_bits[__b_idx] == 0xFFFFFFFFFFFFFFFFu; __b_idx++); \
 103         assert(__b_idx < (uint32_t)table->size);                        \
 104         uint64_t __check_value = table->free_bits[__b_idx];             \
 105         __b_pos = 0;                                                    \
 106                                                                         \
 107         if( 0x00000000FFFFFFFFu == (__check_value & 0x00000000FFFFFFFFu) ) { \
 108             __check_value >>= 32; __b_pos += 32;                        \
 109         }                                                               \
 110         if( 0x000000000000FFFFu == (__check_value & 0x000000000000FFFFu) ) { \
 111             __check_value >>= 16; __b_pos += 16;                        \
 112         }                                                               \
 113         if( 0x00000000000000FFu == (__check_value & 0x00000000000000FFu) ) { \
 114             __check_value >>= 8; __b_pos += 8;                          \
 115         }                                                               \
 116         if( 0x000000000000000Fu == (__check_value & 0x000000000000000Fu) ) { \
 117             __check_value >>= 4; __b_pos += 4;                          \
 118         }                                                               \
 119         if( 0x0000000000000003u == (__check_value & 0x0000000000000003u) ) { \
 120             __check_value >>= 2; __b_pos += 2;                          \
 121         }                                                               \
 122         if( 0x0000000000000001u == (__check_value & 0x0000000000000001u) ) { \
 123             __b_pos += 1;                                               \
 124         }                                                               \
 125         (STORE) = (__b_idx * 8 * sizeof(uint64_t)) + __b_pos;           \
 126     } while(0)
 127 
 128 /**
 129  * Set the IDX bit in the free_bits array. The bit should be previously unset.
 130  */
 131 #define SET_BIT(IDX)                                                    \
 132     do {                                                                \
 133         uint32_t __b_idx, __b_pos;                                      \
 134         GET_BIT_POS((IDX), __b_idx, __b_pos);                           \
 135         assert( 0 == (table->free_bits[__b_idx] & (((uint64_t)1) << __b_pos))); \
 136         table->free_bits[__b_idx] |= (((uint64_t)1) << __b_pos);        \
 137     } while(0)
 138 
 139 /**
 140  * Unset the IDX bit in the free_bits array. The bit should be previously set.
 141  */
 142 #define UNSET_BIT(IDX)                                                  \
 143     do {                                                                \
 144         uint32_t __b_idx, __b_pos;                                      \
 145         GET_BIT_POS((IDX), __b_idx, __b_pos);                           \
 146         assert( (table->free_bits[__b_idx] & (((uint64_t)1) << __b_pos))); \
 147         table->free_bits[__b_idx] ^= (((uint64_t)1) << __b_pos);        \
 148     } while(0)
 149 
 150 #if 0
 151 /**
 152  * Validate the pointer array by making sure that the elements and
 153  * the free bits array are in sync. It also check that the number
 154  * of remaining free element is consistent.
 155  */
 156 static void pmix_pointer_array_validate(pmix_pointer_array_t *array)
 157 {
 158     int i, cnt = 0;
 159     uint32_t b_idx, p_idx;
 160 
 161     for( i = 0; i < array->size; i++ ) {
 162         GET_BIT_POS(i, b_idx, p_idx);
 163         if( NULL == array->addr[i] ) {
 164             cnt++;
 165             assert( 0 == (array->free_bits[b_idx] & (((uint64_t)1) << p_idx)) );
 166         } else {
 167             assert( 0 != (array->free_bits[b_idx] & (((uint64_t)1) << p_idx)) );
 168         }
 169     }
 170     assert(cnt == array->number_free);
 171 }
 172 #endif
 173 
 174 /**
 175  * initialize an array object
 176  */
 177 int pmix_pointer_array_init(pmix_pointer_array_t* array,
 178                             int initial_allocation,
 179                             int max_size, int block_size)
 180 {
 181     size_t num_bytes;
 182 
 183     /* check for errors */
 184     if (NULL == array || max_size < block_size) {
 185         return PMIX_ERR_BAD_PARAM;
 186     }
 187 
 188     array->max_size = max_size;
 189     array->block_size = (0 == block_size ? 8 : block_size);
 190     array->lowest_free = 0;
 191 
 192     num_bytes = (0 < initial_allocation ? initial_allocation : block_size);
 193 
 194     /* Allocate and set the array to NULL */
 195     array->addr = (void **)calloc(num_bytes, sizeof(void*));
 196     if (NULL == array->addr) { /* out of memory */
 197         return PMIX_ERR_OUT_OF_RESOURCE;
 198     }
 199     array->free_bits = (uint64_t*)calloc(TYPE_ELEM_COUNT(uint64_t, num_bytes), sizeof(uint64_t));
 200     if (NULL == array->free_bits) {  /* out of memory */
 201         free(array->addr);
 202         array->addr = NULL;
 203         return PMIX_ERR_OUT_OF_RESOURCE;
 204     }
 205     array->number_free = num_bytes;
 206     array->size = num_bytes;
 207 
 208     return PMIX_SUCCESS;
 209 }
 210 
 211 /**
 212  * add a pointer to dynamic pointer table
 213  *
 214  * @param table Pointer to pmix_pointer_array_t object (IN)
 215  * @param ptr Pointer to be added to table    (IN)
 216  *
 217  * @return Array index where ptr is inserted or PMIX_ERROR if it fails
 218  */
 219 int pmix_pointer_array_add(pmix_pointer_array_t *table, void *ptr)
 220 {
 221     int index = table->size + 1;
 222 
 223     if (table->number_free == 0) {
 224         /* need to grow table */
 225         if (!grow_table(table, index) ) {
 226             return PMIX_ERR_OUT_OF_RESOURCE;
 227         }
 228     }
 229 
 230     assert( (table->addr != NULL) && (table->size > 0) );
 231     assert( (table->lowest_free >= 0) && (table->lowest_free < table->size) );
 232     assert( (table->number_free > 0) && (table->number_free <= table->size) );
 233 
 234     /*
 235      * add pointer to table, and return the index
 236      */
 237 
 238     index = table->lowest_free;
 239     assert(NULL == table->addr[index]);
 240     table->addr[index] = ptr;
 241     table->number_free--;
 242     SET_BIT(index);
 243     if (table->number_free > 0) {
 244         FIND_FIRST_ZERO(index, table->lowest_free);
 245     } else {
 246         table->lowest_free = table->size;
 247     }
 248 
 249 #if 0
 250     pmix_pointer_array_validate(table);
 251 #endif
 252     return index;
 253 }
 254 
 255 /**
 256  * Set the value of the dynamic array at a specified location.
 257  *
 258  *
 259  * @param table Pointer to pmix_pointer_array_t object (IN)
 260  * @param ptr Pointer to be added to table    (IN)
 261  *
 262  * @return Error code
 263  *
 264  * Assumption: NULL element is free element.
 265  */
 266 int pmix_pointer_array_set_item(pmix_pointer_array_t *table, int index,
 267                                 void * value)
 268 {
 269     assert(table != NULL);
 270 
 271     if (PMIX_UNLIKELY(0 > index)) {
 272         return PMIX_ERROR;
 273     }
 274 
 275     /* expand table if required to set a specific index */
 276 
 277     if (table->size <= index) {
 278         if (!grow_table(table, index)) {
 279             return PMIX_ERROR;
 280         }
 281     }
 282     assert(table->size > index);
 283     /* mark element as free, if NULL element */
 284     if( NULL == value ) {
 285         if( NULL != table->addr[index] ) {
 286             if (index < table->lowest_free) {
 287                 table->lowest_free = index;
 288             }
 289             table->number_free++;
 290             UNSET_BIT(index);
 291         }
 292     } else {
 293         if (NULL == table->addr[index]) {
 294             table->number_free--;
 295             SET_BIT(index);
 296             /* Reset lowest_free if required */
 297             if ( index == table->lowest_free ) {
 298                 FIND_FIRST_ZERO(index, table->lowest_free);
 299             }
 300         } else {
 301             assert( index != table->lowest_free );
 302         }
 303     }
 304     table->addr[index] = value;
 305 
 306 #if 0
 307     pmix_pointer_array_validate(table);
 308     pmix_output(0,"pmix_pointer_array_set_item: OUT: "
 309                 " table %p (size %ld, lowest free %ld, number free %ld)"
 310                 " addr[%d] = %p\n",
 311                 table, table->size, table->lowest_free, table->number_free,
 312                 index, table->addr[index]);
 313 #endif
 314 
 315     return PMIX_SUCCESS;
 316 }
 317 
 318 /**
 319  * Test whether a certain element is already in use. If not yet
 320  * in use, reserve it.
 321  *
 322  * @param array Pointer to array (IN)
 323  * @param index Index of element to be tested (IN)
 324  * @param value New value to be set at element index (IN)
 325  *
 326  * @return true/false True if element could be reserved
 327  *                    False if element could not be reserved (e.g.in use).
 328  *
 329  * In contrary to array_set, this function does not allow to overwrite
 330  * a value, unless the previous value is NULL ( equiv. to free ).
 331  */
 332 bool pmix_pointer_array_test_and_set_item (pmix_pointer_array_t *table,
 333                                            int index, void *value)
 334 {
 335     assert(table != NULL);
 336     assert(index >= 0);
 337 
 338 #if 0
 339     pmix_output(0,"pmix_pointer_array_test_and_set_item: IN:  "
 340                " table %p (size %ld, lowest free %ld, number free %ld)"
 341                " addr[%d] = %p\n",
 342                table, table->size, table->lowest_free, table->number_free,
 343                index, table->addr[index]);
 344 #endif
 345 
 346     /* expand table if required to set a specific index */
 347     if ( index < table->size && table->addr[index] != NULL ) {
 348         /* This element is already in use */
 349         return false;
 350     }
 351 
 352     /* Do we need to grow the table? */
 353 
 354     if (table->size <= index) {
 355         if (!grow_table(table, index)) {
 356             return false;
 357         }
 358     }
 359 
 360     /*
 361      * allow a specific index to be changed.
 362      */
 363     assert(NULL == table->addr[index]);
 364     table->addr[index] = value;
 365     table->number_free--;
 366     SET_BIT(index);
 367     /* Reset lowest_free if required */
 368     if( table->number_free > 0 ) {
 369         if ( index == table->lowest_free ) {
 370             FIND_FIRST_ZERO(index, table->lowest_free);
 371         }
 372     } else {
 373         table->lowest_free = table->size;
 374     }
 375 
 376 #if 0
 377     pmix_pointer_array_validate(table);
 378     pmix_output(0,"pmix_pointer_array_test_and_set_item: OUT: "
 379                " table %p (size %ld, lowest free %ld, number free %ld)"
 380                " addr[%d] = %p\n",
 381                table, table->size, table->lowest_free, table->number_free,
 382                index, table->addr[index]);
 383 #endif
 384 
 385     return true;
 386 }
 387 
 388 int pmix_pointer_array_set_size(pmix_pointer_array_t *array, int new_size)
 389 {
 390     if(new_size > array->size) {
 391         if (!grow_table(array, new_size)) {
 392             return PMIX_ERROR;
 393         }
 394     }
 395     return PMIX_SUCCESS;
 396 }
 397 
 398 static bool grow_table(pmix_pointer_array_t *table, int at_least)
 399 {
 400     int i, new_size, new_size_int;
 401     void *p;
 402 
 403     new_size = table->block_size * ((at_least + 1 + table->block_size - 1) / table->block_size);
 404     if( new_size >= table->max_size ) {
 405         new_size = table->max_size;
 406         if( at_least >= table->max_size ) {
 407             return false;
 408         }
 409     }
 410 
 411     p = (void **) realloc(table->addr, new_size * sizeof(void *));
 412     if (NULL == p) {
 413         return false;
 414     }
 415 
 416     table->number_free += (new_size - table->size);
 417     table->addr = (void**)p;
 418     for (i = table->size; i < new_size; ++i) {
 419         table->addr[i] = NULL;
 420     }
 421     new_size_int = TYPE_ELEM_COUNT(uint64_t, new_size);
 422     if( (int)(TYPE_ELEM_COUNT(uint64_t, table->size)) != new_size_int ) {
 423         p = (uint64_t*)realloc(table->free_bits, new_size_int * sizeof(uint64_t));
 424         if (NULL == p) {
 425             return false;
 426         }
 427         table->free_bits = (uint64_t*)p;
 428         for (i = TYPE_ELEM_COUNT(uint64_t, table->size);
 429              i < new_size_int; i++ ) {
 430             table->free_bits[i] = 0;
 431         }
 432     }
 433     table->size = new_size;
 434 #if 0
 435     pmix_output(0, "grow_table %p to %d (max_size %d, block %d, number_free %d)\n",
 436                 (void*)table, table->size, table->max_size, table->block_size, table->number_free);
 437 #endif
 438     return true;
 439 }
/* [<][>][^][v][top][bottom][index][help] */
root/opal/mca/pmix/pmix4x/pmix/src/class/pmix_pointer_array.c

DEFINITIONS
