root/opal/class/opal_bitmap.c

DEFINITIONS

1. opal_bitmap_construct
2. opal_bitmap_destruct
3. opal_bitmap_set_max_size
4. opal_bitmap_init
5. opal_bitmap_set_bit
6. opal_bitmap_clear_bit
7. opal_bitmap_is_set_bit
8. opal_bitmap_clear_all_bits
9. opal_bitmap_set_all_bits
10. opal_bitmap_find_and_set_first_unset_bit
11. opal_bitmap_bitwise_and_inplace
12. opal_bitmap_bitwise_or_inplace
13. opal_bitmap_bitwise_xor_inplace
14. opal_bitmap_are_different
15. opal_bitmap_get_string
16. opal_bitmap_num_unset_bits
17. opal_bitmap_num_set_bits
18. opal_bitmap_is_clear

   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-2014 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) 2007      Cisco Systems, Inc.  All rights reserved.
  13  * Copyright (c) 2010-2012 Oak Ridge National Labs.  All rights reserved.
  14  * Copyright (c) 2014      Intel, Inc. All rights reserved.
  15  * Copyright (c) 2015-2017 Research Organization for Information Science
  16  *                         and Technology (RIST). All rights reserved.
  17  * $COPYRIGHT$
  18  *
  19  * Additional copyrights may follow
  20  *
  21  * $HEADER$
  22  */
  23 
  24 #include "opal_config.h"
  25 
  26 #include <stdio.h>
  27 #include <limits.h>
  28 
  29 #include "opal/constants.h"
  30 #include "opal/class/opal_bitmap.h"
  31 
  32 /* The number of bits in the underlying type of the bitmap field
  33  * in the opal_bitmap_t struct
  34  */
  35 #define SIZE_OF_BASE_TYPE  64
  36 
  37 static void opal_bitmap_construct(opal_bitmap_t *bm);
  38 static void opal_bitmap_destruct(opal_bitmap_t *bm);
  39 
  40 OBJ_CLASS_INSTANCE(opal_bitmap_t, opal_object_t,
  41                    opal_bitmap_construct, opal_bitmap_destruct);
  42 
  43 
  44 static void
  45 opal_bitmap_construct(opal_bitmap_t *bm)
  46 {
  47     bm->bitmap = NULL;
  48     bm->array_size = 0;
  49     bm->max_size = INT_MAX;
  50 }
  51 
  52 
  53 static void
  54 opal_bitmap_destruct(opal_bitmap_t *bm)
  55 {
  56     if (NULL != bm->bitmap) {
  57         free(bm->bitmap);
  58         bm->bitmap = NULL;
  59     }
  60 }
  61 
  62 
  63 int opal_bitmap_set_max_size (opal_bitmap_t *bm, int max_size)
  64 {
  65     if (NULL == bm) {
  66         return OPAL_ERR_BAD_PARAM;
  67     }
  68 
  69     /*
  70      * Only if the caller wants to set the maximum size,
  71      * we set it (in numbers of bits!), otherwise it is
  72      * set to INT_MAX in the constructor.
  73      */
  74     bm->max_size = (int)(((size_t)max_size + SIZE_OF_BASE_TYPE - 1) / SIZE_OF_BASE_TYPE);
  75 
  76     return OPAL_SUCCESS;
  77 }
  78 
  79 
  80 int
  81 opal_bitmap_init(opal_bitmap_t *bm, int size)
  82 {
  83     /*
  84      * Only if the caller set the maximum size before initializing,
  85      * we test here (in numbers of bits!)
  86      * By default, the max size is INT_MAX, set in the constructor.
  87      */
  88     if ((size <= 0) || (NULL == bm) || (size > bm->max_size)) {
  89         return OPAL_ERR_BAD_PARAM;
  90     }
  91 
  92     bm->array_size = (int)(((size_t)size + SIZE_OF_BASE_TYPE - 1) / SIZE_OF_BASE_TYPE);
  93     if( NULL != bm->bitmap ) {
  94         free(bm->bitmap);
  95         if(bm->max_size < bm->array_size)
  96             bm->max_size = bm->array_size;
  97     }
  98     bm->bitmap = (uint64_t*) malloc(bm->array_size * sizeof(uint64_t));
  99     if (NULL == bm->bitmap) {
 100         return OPAL_ERR_OUT_OF_RESOURCE;
 101     }
 102 
 103     opal_bitmap_clear_all_bits(bm);
 104     return OPAL_SUCCESS;
 105 }
 106 
 107 
 108 int
 109 opal_bitmap_set_bit(opal_bitmap_t *bm, int bit)
 110 {
 111     int index, offset, new_size;
 112 
 113     if ((bit < 0) || (NULL == bm) || (bit > bm->max_size)) {
 114         return OPAL_ERR_BAD_PARAM;
 115     }
 116 
 117     index = bit / SIZE_OF_BASE_TYPE;
 118     offset = bit % SIZE_OF_BASE_TYPE;
 119 
 120     if (index >= bm->array_size) {
 121 
 122         /* We need to allocate more space for the bitmap, since we are
 123          out of range. We don't throw any error here, because this is
 124          valid and we simply expand the bitmap */
 125 
 126         new_size = index + 1;
 127         if( new_size > bm->max_size )
 128             new_size = bm->max_size;
 129 
 130         /* New size is just a multiple of the original size to fit in
 131          the index. */
 132         bm->bitmap = (uint64_t*)realloc(bm->bitmap, new_size*sizeof(uint64_t));
 133         if (NULL == bm->bitmap) {
 134             return OPAL_ERR_OUT_OF_RESOURCE;
 135         }
 136 
 137         /* zero out the new elements */
 138         memset(&bm->bitmap[bm->array_size], 0, (new_size - bm->array_size) * sizeof(uint64_t));
 139 
 140         /* Update the array_size */
 141         bm->array_size = new_size;
 142     }
 143 
 144     /* Now set the bit */
 145     bm->bitmap[index] |= (1UL << offset);
 146 
 147     return OPAL_SUCCESS;
 148 }
 149 
 150 
 151 int
 152 opal_bitmap_clear_bit(opal_bitmap_t *bm, int bit)
 153 {
 154     int index, offset;
 155 
 156     if ((bit < 0) || NULL == bm || (bit >= (bm->array_size * SIZE_OF_BASE_TYPE))) {
 157         return OPAL_ERR_BAD_PARAM;
 158     }
 159 
 160     index = bit / SIZE_OF_BASE_TYPE;
 161     offset = bit % SIZE_OF_BASE_TYPE;
 162 
 163     bm->bitmap[index] &= ~(1UL << offset);
 164     return OPAL_SUCCESS;
 165 }
 166 
 167 
 168 bool
 169 opal_bitmap_is_set_bit(opal_bitmap_t *bm, int bit)
 170 {
 171     int index, offset;
 172 
 173     if ((bit < 0) || NULL == bm || (bit >= (bm->array_size * SIZE_OF_BASE_TYPE))) {
 174         return false;
 175     }
 176 
 177     index = bit / SIZE_OF_BASE_TYPE;
 178     offset = bit % SIZE_OF_BASE_TYPE;
 179 
 180     if (0 != (bm->bitmap[index] & (1UL << offset))) {
 181         return true;
 182     }
 183 
 184     return false;
 185 }
 186 
 187 
 188 int
 189 opal_bitmap_clear_all_bits(opal_bitmap_t *bm)
 190 {
 191     if (NULL == bm) {
 192         return OPAL_ERR_BAD_PARAM;
 193     }
 194 
 195     memset(bm->bitmap, 0, bm->array_size * sizeof(uint64_t));
 196     return OPAL_SUCCESS;
 197 }
 198 
 199 
 200 int
 201 opal_bitmap_set_all_bits(opal_bitmap_t *bm)
 202 {
 203     if (NULL == bm) {
 204         return OPAL_ERR_BAD_PARAM;
 205     }
 206 
 207     memset(bm->bitmap, 0xff, bm->array_size * sizeof(uint64_t));
 208 
 209     return OPAL_SUCCESS;
 210 }
 211 
 212 
 213 int
 214 opal_bitmap_find_and_set_first_unset_bit(opal_bitmap_t *bm, int *position)
 215 {
 216     int i = 0;
 217     uint64_t temp, all_ones = 0xffffffffffffffffUL;
 218 
 219     if (NULL == bm) {
 220         return OPAL_ERR_BAD_PARAM;
 221     }
 222 
 223     /* Neglect all which don't have an unset bit */
 224     *position = 0;
 225     while((i < bm->array_size) && (bm->bitmap[i] == all_ones)) {
 226         ++i;
 227     }
 228 
 229     if (i == bm->array_size) {
 230         /* increase the bitmap size then */
 231         *position = bm->array_size * SIZE_OF_BASE_TYPE;
 232         return opal_bitmap_set_bit(bm, *position);
 233     }
 234 
 235     /* This one has an unset bit, find its bit number */
 236 
 237     temp = bm->bitmap[i];
 238     bm->bitmap[i] |= (bm->bitmap[i] + 1); /* Set the first zero bit */
 239     temp ^= bm->bitmap[i];  /* Compute the change: the first unset bit in the original number */
 240     while( !(temp & 0x1) ) {
 241         ++(*position);
 242         temp >>= 1;
 243     }
 244 
 245     (*position) += i * SIZE_OF_BASE_TYPE;
 246     return OPAL_SUCCESS;
 247 }
 248 
 249 int opal_bitmap_bitwise_and_inplace(opal_bitmap_t *dest, opal_bitmap_t *right)
 250 {
 251     int i;
 252 
 253     /*
 254      * Sanity check
 255      */
 256     if( NULL == dest || NULL == right ) {
 257         return OPAL_ERR_BAD_PARAM;
 258     }
 259     if( dest->array_size != right->array_size ) {
 260         return OPAL_ERR_BAD_PARAM;
 261     }
 262 
 263     /*
 264      * Bitwise AND
 265      */
 266     for(i = 0; i < dest->array_size; ++i) {
 267         dest->bitmap[i] &= right->bitmap[i];
 268     }
 269 
 270     return OPAL_SUCCESS;
 271 }
 272 
 273 int opal_bitmap_bitwise_or_inplace(opal_bitmap_t *dest, opal_bitmap_t *right)
 274 {
 275     int i;
 276 
 277     /*
 278      * Sanity check
 279      */
 280     if( NULL == dest || NULL == right ) {
 281         return OPAL_ERR_BAD_PARAM;
 282     }
 283     if( dest->array_size != right->array_size ) {
 284         return OPAL_ERR_BAD_PARAM;
 285     }
 286 
 287     /*
 288      * Bitwise OR
 289      */
 290     for(i = 0; i < dest->array_size; ++i) {
 291         dest->bitmap[i] |= right->bitmap[i];
 292     }
 293 
 294     return OPAL_SUCCESS;
 295 }
 296 
 297 int opal_bitmap_bitwise_xor_inplace(opal_bitmap_t *dest, opal_bitmap_t *right)
 298 {
 299     int i;
 300 
 301     /*
 302      * Sanity check
 303      */
 304     if( NULL == dest || NULL == right ) {
 305         return OPAL_ERR_BAD_PARAM;
 306     }
 307     if( dest->array_size != right->array_size ) {
 308         return OPAL_ERR_BAD_PARAM;
 309     }
 310 
 311     /*
 312      * Bitwise XOR
 313      */
 314     for(i = 0; i < dest->array_size; ++i) {
 315         dest->bitmap[i] ^= right->bitmap[i];
 316     }
 317 
 318     return OPAL_SUCCESS;
 319 }
 320 
 321 bool opal_bitmap_are_different(opal_bitmap_t *left, opal_bitmap_t *right)
 322 {
 323     int i;
 324 
 325     /*
 326      * Sanity check
 327      */
 328     if( NULL == left || NULL == right ) {
 329         return OPAL_ERR_BAD_PARAM;
 330     }
 331 
 332     if( opal_bitmap_size(left) != opal_bitmap_size(right) ) {
 333         return true;
 334     }
 335 
 336     /*
 337      * Direct comparison
 338      */
 339     for(i = 0; i < left->array_size; ++i) {
 340         if( left->bitmap[i] != right->bitmap[i] ) {
 341             return true;
 342         }
 343     }
 344 
 345     return false;
 346 }
 347 
 348 char * opal_bitmap_get_string(opal_bitmap_t *bitmap)
 349 {
 350     int i;
 351     char *bitmap_str = NULL;
 352 
 353     if( NULL == bitmap) {
 354         return NULL;
 355     }
 356 
 357     bitmap_str = malloc(bitmap->array_size * SIZE_OF_BASE_TYPE + 1);
 358     if (NULL == bitmap_str) {
 359         return NULL;
 360     }
 361     bitmap_str[bitmap->array_size * SIZE_OF_BASE_TYPE] = '\0';
 362 
 363     for( i = 0; i < (bitmap->array_size * SIZE_OF_BASE_TYPE); ++i) {
 364         if( opal_bitmap_is_set_bit(bitmap, i) ) {
 365             bitmap_str[i] = 'X';
 366         } else {
 367             bitmap_str[i] = '_';
 368         }
 369     }
 370 
 371     return bitmap_str;
 372 }
 373 
 374 int opal_bitmap_num_unset_bits(opal_bitmap_t *bm, int len)
 375 {
 376     return (len - opal_bitmap_num_set_bits(bm, len));
 377 }
 378 
 379 int opal_bitmap_num_set_bits(opal_bitmap_t *bm, int len)
 380 {
 381     int i, cnt = 0;
 382     uint64_t val;
 383 
 384 #if OPAL_ENABLE_DEBUG
 385     if ((len < 0) || NULL == bm || (len >= (bm->array_size * SIZE_OF_BASE_TYPE))) {
 386         return 0;
 387     }
 388 #endif
 389 
 390     for(i = 0; i < len; ++i) {
 391         if( 0 == (val = bm->bitmap[i]) ) continue;
 392         /*  Peter Wegner in CACM 3 (1960), 322. This method goes through as many
 393          *  iterations as there are set bits. */
 394         for( ; val; cnt++ ) {
 395             val &= val - 1;  /* clear the least significant bit set */
 396         }
 397     }
 398 
 399     return cnt;
 400 }
 401 
 402 bool opal_bitmap_is_clear(opal_bitmap_t *bm)
 403 {
 404     int i;
 405 
 406     for (i = 0; i < bm->array_size; ++i) {
 407         if (0 != bm->bitmap[i]) {
 408             return false;
 409         }
 410     }
 411     return true;
 412 }