src/system/kernel/util/Bitmap.cpp

   1 /*
   2  * Copyright 2013 Haiku, Inc. All rights reserved.
   3  * Distributed under the terms of the MIT License.
   4  *
   5  * Authors:
   6  *              Paweł Dziepak, pdziepak@quarnos.org
   7  */
   8
   9
  10 #include <util/Bitmap.h>
  11
  12 #include <new>
  13
  14 #include <string.h>
  15
  16 #include <util/BitUtils.h>
  17
  18
  19 const int Bitmap::kBitsPerElement = sizeof(addr_t) * 8;
  20
  21
  22 Bitmap::Bitmap(int bitCount)
  23         :
  24         fInitStatus(B_OK),
  25         fElementsCount(0),
  26         fSize(bitCount)
  27 {
  28         int count = fSize + kBitsPerElement - 1;
  29         count /= kBitsPerElement;
  30
  31         fBits = new(std::nothrow) addr_t[count];
  32         if (fBits == NULL) {
  33                 fSize = 0;
  34                 fInitStatus = B_NO_MEMORY;
  35         }
  36
  37         fElementsCount = count;
  38         memset(fBits, 0, sizeof(addr_t) * count);
  39 }
  40
  41
  42 Bitmap::~Bitmap()
  43 {
  44         delete[] fBits;
  45 }
  46
  47
  48 int
  49 Bitmap::GetHighestSet() const
  50 {
  51         int i = fElementsCount - 1;
  52         while (i >= 0 && fBits[i] == 0)
  53                 i--;
  54
  55         if (i < 0)
  56                 return -1;
  57
  58         STATIC_ASSERT(sizeof(addr_t) == sizeof(uint64)
  59                 || sizeof(addr_t) == sizeof(uint32));
  60         if (sizeof(addr_t) == sizeof(uint32))
  61                 return log2(fBits[i]) + i * kBitsPerElement;
  62
  63         uint32 v = (uint64)fBits[i] >> 32;
  64         if (v != 0)
  65                 return log2(v) + sizeof(uint32) * 8 + i * kBitsPerElement;
  66         return log2(fBits[i]) + i * kBitsPerElement;
  67 }
  68