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 = index / UTIL_BITMASK_BITS_PER_WORD;
 202    unsigned bit  = index % UTIL_BITMASK_BITS_PER_WORD;
 203    util_bitmask_word mask = 1 << bit;
 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    bm->words[word] |= mask;
 212
 213    util_bitmask_filled_set(bm, index);
 214
 215    return index;
 216 }
 217
 218
 219 void
 220 util_bitmask_clear(struct util_bitmask *bm,
 221                    unsigned index)
 222 {
 223    unsigned word = index / UTIL_BITMASK_BITS_PER_WORD;
 224    unsigned bit  = index % UTIL_BITMASK_BITS_PER_WORD;
 225    util_bitmask_word mask = 1 << bit;
 226
 227    assert(bm);
 228
 229    if(index >= bm->size)
 230       return;
 231
 232    bm->words[word] &= ~mask;
 233
 234    util_bitmask_filled_unset(bm, index);
 235 }
 236
 237
 238 boolean
 239 util_bitmask_get(struct util_bitmask *bm,
 240                  unsigned index)
 241 {
 242    unsigned word = index / UTIL_BITMASK_BITS_PER_WORD;
 243    unsigned bit  = index % UTIL_BITMASK_BITS_PER_WORD;
 244    util_bitmask_word mask = 1 << bit;
 245
 246    assert(bm);
 247
 248    if(index < bm->filled) {
 249       assert(bm->words[word] & mask);
 250       return TRUE;
 251    }
 252
 253    if(index > bm->size)
 254       return FALSE;
 255
 256    if(bm->words[word] & mask) {
 257       util_bitmask_filled_set(bm, index);
 258       return TRUE;
 259    }
 260    else
 261       return FALSE;
 262 }
 263
 264
 265 unsigned
 266 util_bitmask_get_next_index(struct util_bitmask *bm,
 267                             unsigned index)
 268 {
 269    unsigned word = index / UTIL_BITMASK_BITS_PER_WORD;
 270    unsigned bit  = index % UTIL_BITMASK_BITS_PER_WORD;
 271    util_bitmask_word mask = 1 << bit;
 272
 273    if(index < bm->filled) {
 274       assert(bm->words[word] & mask);
 275       return index;
 276    }
 277
 278    if(index >= bm->size) {
 279       return UTIL_BITMASK_INVALID_INDEX;
 280    }
 281
 282    /* Do a linear search */
 283    while(word < bm->size / UTIL_BITMASK_BITS_PER_WORD) {
 284       while(bit < UTIL_BITMASK_BITS_PER_WORD) {
 285          if(bm->words[word] & mask) {
 286             if(index == bm->filled) {
 287                ++bm->filled;
 288                assert(bm->filled <= bm->size);
 289             }
 290             return index;
 291          }
 292          ++index;
 293          ++bit;
 294          mask <<= 1;
 295       }
 296       ++word;
 297       bit = 0;
 298       mask = 1;
 299    }
 300
 301    return UTIL_BITMASK_INVALID_INDEX;
 302 }
 303
 304
 305 unsigned
 306 util_bitmask_get_first_index(struct util_bitmask *bm)
 307 {
 308    return util_bitmask_get_next_index(bm, 0);
 309 }
 310
 311
 312 void
 313 util_bitmask_destroy(struct util_bitmask *bm)
 314 {
 315    assert(bm);
 316
 317    FREE(bm->words);
 318    FREE(bm);
 319 }
 320