Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  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.  
  329.