src/gallium/auxiliary/util/u_bitmask.c

   1 /**************************************************************************
   2  *
   3  * Copyright 2009 VMware, Inc.
   4  * All Rights Reserved.
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sub license, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice (including the
  15  * next paragraph) shall be included in all copies or substantial portions
  16  * of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  19  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
  21  * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
  22  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  23  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  24  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  **************************************************************************/
  27
  28 /**
  29  * @file
  30  * Generic bitmask implementation.
  31  *
  32  * @author Jose Fonseca <jfonseca@vmware.com>
  33  */
  34
  35
  36 #include "pipe/p_compiler.h"
  37 #include "util/u_debug.h"
  38
  39 #include "util/u_memory.h"
  40 #include "util/u_bitmask.h"
  41
  42
  43 typedef uint32_t util_bitmask_word;
  44
  45
  46 #define UTIL_BITMASK_INITIAL_WORDS 16
  47 #define UTIL_BITMASK_BITS_PER_BYTE 8
  48 #define UTIL_BITMASK_BITS_PER_WORD (sizeof(util_bitmask_word) * UTIL_BITMASK_BITS_PER_BYTE)
  49
  50
  51 struct util_bitmask
  52 {
  53    util_bitmask_word *words;
  54
  55    /** Number of bits we can currently hold */
  56    unsigned size;
  57
  58    /** Number of consecutive bits set at the start of the bitmask */
  59    unsigned filled;
  60 };
  61
  62
  63 struct util_bitmask *
  64 util_bitmask_create(void)
  65 {
  66    struct util_bitmask *bm;
  67
  68    bm = MALLOC_STRUCT(util_bitmask);
  69    if(!bm)
  70       return NULL;
  71
  72    bm->words = (util_bitmask_word *)CALLOC(UTIL_BITMASK_INITIAL_WORDS, sizeof(util_bitmask_word));
  73    if(!bm->words) {
  74       FREE(bm);
  75       return NULL;
  76    }
  77
  78    bm->size = UTIL_BITMASK_INITIAL_WORDS * UTIL_BITMASK_BITS_PER_WORD;
  79    bm->filled = 0;
  80
  81    return bm;
  82 }
  83
  84
  85 /**
  86  * Resize the bitmask if necessary
  87  */
  88 static INLINE boolean
  89 util_bitmask_resize(struct util_bitmask *bm,
  90                     unsigned minimum_index)
  91 {
  92    unsigned minimum_size = minimum_index + 1;
  93    unsigned new_size;
  94    util_bitmask_word *new_words;
  95
  96    /* Check integer overflow */
  97    if(!minimum_size)
  98       return FALSE;
  99
 100    if(bm->size >= minimum_size)
 101       return TRUE;
 102
 103    assert(bm->size % UTIL_BITMASK_BITS_PER_WORD == 0);
 104    new_size = bm->size;
 105    while(new_size < minimum_size) {
 106       new_size *= 2;
 107       /* Check integer overflow */
 108       if(new_size < bm->size)
 109          return FALSE;
 110    }
 111    assert(new_size);
 112    assert(new_size % UTIL_BITMASK_BITS_PER_WORD == 0);
 113
 114    new_words = (util_bitmask_word *)REALLOC((void *)bm->words,
 115                                             bm->size / UTIL_BITMASK_BITS_PER_BYTE,
 116                                             new_size / UTIL_BITMASK_BITS_PER_BYTE);
 117    if(!new_words)
 118       return FALSE;
 119
 120    memset(new_words + bm->size/UTIL_BITMASK_BITS_PER_WORD,
 121           0,
 122           (new_size - bm->size)/UTIL_BITMASK_BITS_PER_BYTE);
 123
 124    bm->size = new_size;
 125    bm->words = new_words;
 126
 127    return TRUE;
 128 }
 129
 130
 131 /**
 132  * Lazily update the filled.
 133  */
 134 static INLINE void
 135 util_bitmask_filled_set(struct util_bitmask *bm,
 136                         unsigned index)
 137 {
 138    assert(bm->filled <= bm->size);
 139    assert(index < bm->size);
 140
 141    if(index == bm->filled) {
 142       ++bm->filled;
 143       assert(bm->filled <= bm->size);
 144    }
 145 }
 146
 147 static INLINE void
 148 util_bitmask_filled_unset(struct util_bitmask *bm,
 149                           unsigned index)
 150 {
 151    assert(bm->filled <= bm->size);
 152    assert(index < bm->size);
 153
 154    if(index < bm->filled)
 155       bm->filled = index;
 156 }
 157
 158
 159 unsigned
 160 util_bitmask_add(struct util_bitmask *bm)
 161 {
 162    unsigned word;
 163    unsigned bit;
 164    util_bitmask_word mask;
 165
 166    assert(bm);
 167
 168    /* linear search for an empty index */
 169    word = bm->filled / UTIL_BITMASK_BITS_PER_WORD;
 170    bit  = bm->filled % UTIL_BITMASK_BITS_PER_WORD;
 171    mask = 1 << bit;
 172    while(word < bm->size / UTIL_BITMASK_BITS_PER_WORD) {
 173       while(bit < UTIL_BITMASK_BITS_PER_WORD) {
 174          if(!(bm->words[word] & mask))
 175             goto found;
 176          ++bm->filled;
 177          ++bit;
 178          mask <<= 1;
 179       }
 180       ++word;
 181       bit = 0;
 182       mask = 1;
 183    }
 184 found:
 185
 186    /* grow the bitmask if necessary */
 187    if(!util_bitmask_resize(bm, bm->filled))
 188       return UTIL_BITMASK_INVALID_INDEX;
 189
 190    assert(!(bm->words[word] & mask));
 191    bm->words[word] |= mask;
 192
 193    return bm->filled++;
 194 }
 195
 196
 197 unsigned
 198 util_bitmask_set(struct util_bitmask *bm,
 199                  unsigned index)
 200 {
 201    unsigned word;
 202    unsigned bit;
 203    util_bitmask_word mask;
 204
 205    assert(bm);
 206
 207    /* grow the bitmask if necessary */
 208    if(!util_bitmask_resize(bm, index))
 209       return UTIL_BITMASK_INVALID_INDEX;
 210
 211    word = index / UTIL_BITMASK_BITS_PER_WORD;
 212    bit  = index % UTIL_BITMASK_BITS_PER_WORD;
 213    mask = 1 << bit;
 214
 215    bm->words[word] |= mask;
 216
 217    util_bitmask_filled_set(bm, index);
 218
 219    return index;
 220 }
 221
 222
 223 void
 224 util_bitmask_clear(struct util_bitmask *bm,
 225                    unsigned index)
 226 {
 227    unsigned word;
 228    unsigned bit;
 229    util_bitmask_word mask;
 230
 231    assert(bm);
 232
 233    if(index >= bm->size)
 234       return;
 235
 236    word = index / UTIL_BITMASK_BITS_PER_WORD;
 237    bit  = index % UTIL_BITMASK_BITS_PER_WORD;
 238    mask = 1 << bit;
 239
 240    bm->words[word] &= ~mask;
 241
 242    util_bitmask_filled_unset(bm, index);
 243 }
 244
 245
 246 boolean
 247 util_bitmask_get(struct util_bitmask *bm,
 248                  unsigned index)
 249 {
 250    unsigned word = index / UTIL_BITMASK_BITS_PER_WORD;
 251    unsigned bit  = index % UTIL_BITMASK_BITS_PER_WORD;
 252    util_bitmask_word mask = 1 << bit;
 253
 254    assert(bm);
 255
 256    if(index < bm->filled) {
 257       assert(bm->words[word] & mask);
 258       return TRUE;
 259    }
 260
 261    if(index >= bm->size)
 262       return FALSE;
 263
 264    if(bm->words[word] & mask) {
 265       util_bitmask_filled_set(bm, index);
 266       return TRUE;
 267    }
 268    else
 269       return FALSE;
 270 }
 271
 272
 273 unsigned
 274 util_bitmask_get_next_index(struct util_bitmask *bm,
 275                             unsigned index)
 276 {
 277    unsigned word = index / UTIL_BITMASK_BITS_PER_WORD;
 278    unsigned bit  = index % UTIL_BITMASK_BITS_PER_WORD;
 279    util_bitmask_word mask = 1 << bit;
 280
 281    if(index < bm->filled) {
 282       assert(bm->words[word] & mask);
 283       return index;
 284    }
 285
 286    if(index >= bm->size) {
 287       return UTIL_BITMASK_INVALID_INDEX;
 288    }
 289
 290    /* Do a linear search */
 291    while(word < bm->size / UTIL_BITMASK_BITS_PER_WORD) {
 292       while(bit < UTIL_BITMASK_BITS_PER_WORD) {
 293          if(bm->words[word] & mask) {
 294             if(index == bm->filled) {
 295                ++bm->filled;
 296                assert(bm->filled <= bm->size);
 297             }
 298             return index;
 299          }
 300          ++index;
 301          ++bit;
 302          mask <<= 1;
 303       }
 304       ++word;
 305       bit = 0;
 306       mask = 1;
 307    }
 308
 309    return UTIL_BITMASK_INVALID_INDEX;
 310 }
 311
 312
 313 unsigned
 314 util_bitmask_get_first_index(struct util_bitmask *bm)
 315 {
 316    return util_bitmask_get_next_index(bm, 0);
 317 }
 318
 319
 320 void
 321 util_bitmask_destroy(struct util_bitmask *bm)
 322 {
 323    assert(bm);
 324
 325    FREE(bm->words);
 326    FREE(bm);
 327 }
 328