1  /*
   2   * \brief  Allocator using bitmaps
   3   * \author Alexander Boettcher
   4   * \author Stefan Kalkowski
   5   * \date   2012-06-14
   6   */
   7  
   8  /*
   9   * Copyright (C) 2012-2013 Genode Labs GmbH
  10   *
  11   * This file is part of the Genode OS framework, which is distributed
  12   * under the terms of the GNU General Public License version 2.
  13   */
  14  
  15  #ifndef _INCLUDE__UTIL__BIT_ARRAY_H_
  16  #define _INCLUDE__UTIL__BIT_ARRAY_H_
  17  
  18  #include <util/string.h>
  19  #include <base/exception.h>
  20  #include <base/stdint.h>
  21  
  22  namespace Genode {
  23     
  24     class Bit_array_base;
  25     template <unsigned> class Bit_array;
  26  }
  27  
  28  
  29  class Genode::Bit_array_base
  30  {
  31     public:
  32  
  33        class Invalid_bit_count    : public Exception {};
  34        class Invalid_index_access : public Exception {};
  35        class Invalid_clear        : public Exception {};
  36        class Invalid_set          : public Exception {};
  37  
  38     private:
  39  
  40        enum {
  41           BITS_PER_BYTE = 8UL,
  42           BITS_PER_WORD = sizeof(addr_t) * BITS_PER_BYTE
  43        };
  44  
  45        unsigned _bit_cnt;
  46        unsigned _word_cnt;
  47        addr_t  *_words;
  48  
  49        addr_t _word(addr_t index) const {
  50           return index / BITS_PER_WORD; }
  51  
  52        void _check_range(addr_t const index,
  53                          addr_t const width) const
  54        {
  55           if ((index >= _word_cnt * BITS_PER_WORD) ||
  56               width > _word_cnt * BITS_PER_WORD ||
  57               _word_cnt * BITS_PER_WORD - width < index)
  58              throw Invalid_index_access();
  59        }
  60  
  61        addr_t _mask(addr_t const index, addr_t const width,
  62                     addr_t &rest) const
  63        {
  64           addr_t const shift = index - _word(index) * BITS_PER_WORD;
  65  
  66           rest = width + shift > BITS_PER_WORD ?
  67                  width + shift - BITS_PER_WORD : 0;
  68  
  69           return (width >= BITS_PER_WORD) ? ~0UL << shift
  70                                           : ((1UL << width) - 1) << shift;
  71        }
  72  
  73        void _set(addr_t index, addr_t width, bool free)
  74        {
  75           _check_range(index, width);
  76  
  77           addr_t rest, word, mask;
  78           do {
  79              word = _word(index);
  80              mask = _mask(index, width, rest);
  81  
  82              if (free) {
  83                 if ((_words[word] & mask) != mask)
  84                    throw Invalid_clear();
  85                 _words[word] &= ~mask;
  86              } else {
  87                 if (_words[word] & mask)
  88                    throw Invalid_set();
  89                 _words[word] |= mask;
  90              }
  91  
  92              index = (_word(index) + 1) * BITS_PER_WORD;
  93              width = rest;
  94           } while (rest);
  95        }
  96  
  97     public:
  98  
  99        Bit_array_base(unsigned bits, addr_t *addr, bool clear)
 100        : _bit_cnt(bits),
 101          _word_cnt(_bit_cnt / BITS_PER_WORD),
 102          _words(addr)
 103        {
 104           if (!bits || bits % BITS_PER_WORD) throw Invalid_bit_count();
 105  
 106           if (clear) memset(_words, 0, sizeof(addr_t)*_word_cnt);
 107        }
 108  
 109        /**
 110         * Return true if at least one bit is set between
 111         * index until index + width - 1
 112         */
 113        bool get(addr_t index, addr_t width) const
 114        {
 115           _check_range(index, width);
 116  
 117           bool used = false;
 118           addr_t rest, mask;
 119           do {
 120              mask  = _mask(index, width, rest);
 121              used  = _words[_word(index)] & mask;
 122              index = (_word(index) + 1) * BITS_PER_WORD;
 123              width = rest;
 124           } while (!used && rest);
 125  
 126           return used;
 127        }
 128  
 129        void set(addr_t const index, addr_t const width) {
 130           _set(index, width, false); }
 131  
 132        void clear(addr_t const index, addr_t const width) {
 133           _set(index, width, true); }
 134  };
 135  
 136  
 137  template <unsigned BITS>
 138  class Genode::Bit_array : public Bit_array_base
 139  {
 140     private:
 141  
 142        static constexpr size_t _WORDS = BITS / BITS_PER_WORD;
 143  
 144        static_assert(BITS % BITS_PER_WORD == 0,
 145                      "Count of bits need to be word aligned!");
 146  
 147        addr_t _array[_WORDS];
 148  
 149     public:
 150  
 151        Bit_array() : Bit_array_base(BITS, _array, true) { }
 152  };
 153  
 154  #endif /* _INCLUDE__UTIL__BIT_ARRAY_H_ */