Home | History | Annotate | Download | only in util
      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 (at) 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 
    329