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 *)
  73       CALLOC(UTIL_BITMASK_INITIAL_WORDS, sizeof(util_bitmask_word));
  74    if (!bm->words) {
  75       FREE(bm);
  76       return NULL;
  77    }
  78
  79    bm->size = UTIL_BITMASK_INITIAL_WORDS * UTIL_BITMASK_BITS_PER_WORD;
  80    bm->filled = 0;
  81
  82    return bm;
  83 }
  84
  85
  86 /**
  87  * Resize the bitmask if necessary
  88  */
  89 static inline boolean
  90 util_bitmask_resize(struct util_bitmask *bm,
  91                     unsigned minimum_index)
  92 {
  93    const unsigned minimum_size = minimum_index + 1;
  94    unsigned new_size;
  95    util_bitmask_word *new_words;
  96
  97    /* Check integer overflow */
  98    if (!minimum_size)
  99       return FALSE;
 100
 101    if (bm->size >= minimum_size)
 102       return TRUE;
 103
 104    assert(bm->size % UTIL_BITMASK_BITS_PER_WORD == 0);
 105    new_size = bm->size;
 106    while (new_size < minimum_size) {
 107       new_size *= 2;
 108       /* Check integer overflow */
 109       if (new_size < bm->size)
 110          return FALSE;
 111    }
 112    assert(new_size);
 113    assert(new_size % UTIL_BITMASK_BITS_PER_WORD == 0);
 114
 115    new_words = (util_bitmask_word *)
 116       REALLOC((void *)bm->words,
 117               bm->size / UTIL_BITMASK_BITS_PER_BYTE,
 118               new_size / UTIL_BITMASK_BITS_PER_BYTE);
 119    if (!new_words)
 120       return FALSE;
 121
 122    memset(new_words + bm->size/UTIL_BITMASK_BITS_PER_WORD,
 123           0,
 124           (new_size - bm->size)/UTIL_BITMASK_BITS_PER_BYTE);
 125
 126    bm->size = new_size;
 127    bm->words = new_words;
 128
 129    return TRUE;
 130 }
 131
 132
 133 /**
 134  * Check if we can increment the filled counter.
 135  */
 136 static inline void
 137 util_bitmask_filled_set(struct util_bitmask *bm,
 138                         unsigned index)
 139 {
 140    assert(bm->filled <= bm->size);
 141    assert(index < bm->size);
 142
 143    if (index == bm->filled) {
 144       ++bm->filled;
 145       assert(bm->filled <= bm->size);
 146    }
 147 }
 148
 149
 150 /**
 151  * Check if we need to decrement the filled counter.
 152  */
 153 static inline void
 154 util_bitmask_filled_unset(struct util_bitmask *bm,
 155                           unsigned index)
 156 {
 157    assert(bm->filled <= bm->size);
 158    assert(index < bm->size);
 159
 160    if (index < bm->filled)
 161       bm->filled = index;
 162 }
 163
 164
 165 unsigned
 166 util_bitmask_add(struct util_bitmask *bm)
 167 {
 168    unsigned word;
 169    unsigned bit;
 170    util_bitmask_word mask;
 171
 172    assert(bm);
 173
 174    /* linear search for an empty index, starting at filled position */
 175    word = bm->filled / UTIL_BITMASK_BITS_PER_WORD;
 176    bit  = bm->filled % UTIL_BITMASK_BITS_PER_WORD;
 177    mask = 1 << bit;
 178    while (word < bm->size / UTIL_BITMASK_BITS_PER_WORD) {
 179       while (bit < UTIL_BITMASK_BITS_PER_WORD) {
 180          if (!(bm->words[word] & mask))
 181             goto found;
 182          ++bm->filled;
 183          ++bit;
 184          mask <<= 1;
 185       }
 186       ++word;
 187       bit = 0;
 188       mask = 1;
 189    }
 190 found:
 191
 192    /* grow the bitmask if necessary */
 193    if (!util_bitmask_resize(bm, bm->filled))
 194       return UTIL_BITMASK_INVALID_INDEX;
 195
 196    assert(!(bm->words[word] & mask));
 197    bm->words[word] |= mask;
 198
 199    return bm->filled++;
 200 }
 201
 202
 203 unsigned
 204 util_bitmask_set(struct util_bitmask *bm,
 205                  unsigned index)
 206 {
 207    unsigned word;
 208    unsigned bit;
 209    util_bitmask_word mask;
 210
 211    assert(bm);
 212
 213    /* grow the bitmask if necessary */
 214    if (!util_bitmask_resize(bm, index))
 215       return UTIL_BITMASK_INVALID_INDEX;
 216
 217    word = index / UTIL_BITMASK_BITS_PER_WORD;
 218    bit  = index % UTIL_BITMASK_BITS_PER_WORD;
 219    mask = 1 << bit;
 220
 221    bm->words[word] |= mask;
 222
 223    util_bitmask_filled_set(bm, index);
 224
 225    return index;
 226 }
 227
 228
 229 void
 230 util_bitmask_clear(struct util_bitmask *bm,
 231                    unsigned index)
 232 {
 233    unsigned word;
 234    unsigned bit;
 235    util_bitmask_word mask;
 236
 237    assert(bm);
 238
 239    if (index >= bm->size)
 240       return;
 241
 242    word = index / UTIL_BITMASK_BITS_PER_WORD;
 243    bit  = index % UTIL_BITMASK_BITS_PER_WORD;
 244    mask = 1 << bit;
 245
 246    bm->words[word] &= ~mask;
 247
 248    util_bitmask_filled_unset(bm, index);
 249 }
 250
 251
 252 boolean
 253 util_bitmask_get(struct util_bitmask *bm,
 254                  unsigned index)
 255 {
 256    const unsigned word = index / UTIL_BITMASK_BITS_PER_WORD;
 257    const unsigned bit  = index % UTIL_BITMASK_BITS_PER_WORD;
 258    const util_bitmask_word mask = 1 << bit;
 259
 260    assert(bm);
 261
 262    if (index < bm->filled) {
 263       assert(bm->words[word] & mask);
 264       return TRUE;
 265    }
 266
 267    if (index >= bm->size)
 268       return FALSE;
 269
 270    if (bm->words[word] & mask) {
 271       util_bitmask_filled_set(bm, index);
 272       return TRUE;
 273    }
 274    else
 275       return FALSE;
 276 }
 277
 278
 279 unsigned
 280 util_bitmask_get_next_index(struct util_bitmask *bm,
 281                             unsigned index)
 282 {
 283    unsigned word = index / UTIL_BITMASK_BITS_PER_WORD;
 284    unsigned bit  = index % UTIL_BITMASK_BITS_PER_WORD;
 285    util_bitmask_word mask = 1 << bit;
 286
 287    if (index < bm->filled) {
 288       assert(bm->words[word] & mask);
 289       return index;
 290    }
 291
 292    if (index >= bm->size) {
 293       return UTIL_BITMASK_INVALID_INDEX;
 294    }
 295
 296    /* Do a linear search */
 297    while (word < bm->size / UTIL_BITMASK_BITS_PER_WORD) {
 298       while (bit < UTIL_BITMASK_BITS_PER_WORD) {
 299          if (bm->words[word] & mask) {
 300             if (index == bm->filled) {
 301                ++bm->filled;
 302                assert(bm->filled <= bm->size);
 303             }
 304             return index;
 305          }
 306          ++index;
 307          ++bit;
 308          mask <<= 1;
 309       }
 310       ++word;
 311       bit = 0;
 312       mask = 1;
 313    }
 314
 315    return UTIL_BITMASK_INVALID_INDEX;
 316 }
 317
 318
 319 unsigned
 320 util_bitmask_get_first_index(struct util_bitmask *bm)
 321 {
 322    return util_bitmask_get_next_index(bm, 0);
 323 }
 324
 325
 326 void
 327 util_bitmask_destroy(struct util_bitmask *bm)
 328 {
 329    if (bm) {
 330       FREE(bm->words);
 331       FREE(bm);
 332    }
 333 }