opal/class/opal_pointer

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

DEFINITIONS
