ExtensibleBitmap.cc

/*
 * Copyright (c) 2008-2014, Pedigree Developers
 *
 * Please see the CONTRIB file in the root of the source tree for a full
 * list of contributors.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
 
#include "pedigree/kernel/utilities/ExtensibleBitmap.h"
#include "pedigree/kernel/utilities/utility.h"
 
ExtensibleBitmap::ExtensibleBitmap()
    : m_StaticMap(0),
      m_pDynamicMap(0),
      m_DynamicMapSize(0),
      m_nMaxBit(0),
      m_nFirstSetBit(~0U),
      m_nFirstClearBit(0),
      m_nLastSetBit(~0U),
      m_nLastClearBit(0) {}
 
ExtensibleBitmap::ExtensibleBitmap(const ExtensibleBitmap& other)
    : m_StaticMap(other.m_StaticMap),
      m_pDynamicMap(0),
      m_DynamicMapSize(other.m_DynamicMapSize),
      m_nMaxBit(other.m_nMaxBit),
      m_nFirstSetBit(other.m_nFirstSetBit),
      m_nFirstClearBit(other.m_nFirstClearBit),
      m_nLastSetBit(other.m_nLastSetBit),
      m_nLastClearBit(other.m_nLastClearBit) {
  if (m_DynamicMapSize) {
    m_pDynamicMap = new uint8_t[m_DynamicMapSize];
    MemoryCopy(m_pDynamicMap, other.m_pDynamicMap, m_DynamicMapSize);
  }
}
 
ExtensibleBitmap& ExtensibleBitmap::operator=(const ExtensibleBitmap& other) {
  if (this == &other) {
    return *this;
  }
 
  m_StaticMap = other.m_StaticMap;
 
  if (m_DynamicMapSize < other.m_DynamicMapSize) {
    uint8_t* pMap = new uint8_t[other.m_DynamicMapSize];
    delete[] m_pDynamicMap;
    m_pDynamicMap = pMap;
    m_DynamicMapSize = other.m_DynamicMapSize;
  }
 
  if (other.m_DynamicMapSize) {
    MemoryCopy(m_pDynamicMap, other.m_pDynamicMap, other.m_DynamicMapSize);
  } else if (m_pDynamicMap) {
    ByteSet(m_pDynamicMap, 0, m_DynamicMapSize);
  }
  m_nMaxBit = other.m_nMaxBit;
  m_nFirstSetBit = other.m_nFirstSetBit;
  m_nFirstClearBit = other.m_nFirstClearBit;
  m_nLastSetBit = other.m_nLastSetBit;
  m_nLastClearBit = other.m_nLastClearBit;
 
  return *this;
}
 
ExtensibleBitmap::~ExtensibleBitmap() {
  if (m_pDynamicMap)
    delete[] m_pDynamicMap;
}
 
void ExtensibleBitmap::set(size_t n) {
  // Check if the bit we'll set becomes the first set bit
  if ((n < m_nFirstSetBit) || (m_nFirstSetBit == ~0U))
    m_nFirstSetBit = n;
  // Check if the bit we'll set becomes the last set bit
  if ((n > m_nLastSetBit) || (m_nLastSetBit == ~0U))
    m_nLastSetBit = n;
  // Check if the bit we'll set replaces the first clear bit
  if (n == m_nFirstClearBit) {
    do {
      m_nFirstClearBit++;
    } while (test(m_nFirstClearBit));
  }
 
  /*if(n == m_nLastClearBit)
  {
      for(size_t i = n;i;i--)
      {
          if(!test(i))
          {
              m_nLastClearBit = i;
              break;
          }
      }
  }*/
 
  if (n < sizeof(uintptr_t) * 8) {
    m_StaticMap |= (1UL << n);
    return;
  }
 
  n -= sizeof(uintptr_t) * 8;
 
  // Check we have enough space to handle the bit.
  if (n / 8 >= m_DynamicMapSize) {
    // Double the size of the map to avoid so many allocations/copies/zeroes
    // ... unless the bit itself is well beyond that range!
    size_t sz = max(n / 8 + 8, m_DynamicMapSize * 2);
    uint8_t* pMap = new uint8_t[sz];
    uint8_t* oldMap = m_pDynamicMap;
    if (m_DynamicMapSize && oldMap) {
      MemoryCopy(pMap, oldMap, m_DynamicMapSize);
    }
    // zero out the rest of the new memory now
    ByteSet(pMap + m_DynamicMapSize, 0, sz - m_DynamicMapSize);
    m_pDynamicMap = pMap;
    if (oldMap) {
      delete[] oldMap;
    }
    m_DynamicMapSize = sz;
  }
 
  m_pDynamicMap[n / 8] |= (1UL << (n % 8));
  if (n > m_nMaxBit)
    m_nMaxBit = n;
}
 
void ExtensibleBitmap::clear(size_t n) {
  if (!test(n)) {
    return;
  }
 
  if (n < sizeof(uintptr_t) * 8) {
    m_StaticMap &= ~(1UL << n);
  } else {
    const size_t dynamicBit = n - sizeof(uintptr_t) * 8;
    m_pDynamicMap[dynamicBit / 8] &= ~(1UL << (dynamicBit % 8));
  }
 
  // Check if the bit we'll clear becomes the first clear bit
  if (n < m_nFirstClearBit) {
    m_nFirstClearBit = n;
  }
  // Check if the bit we'll clear replaces the first set bit
  if (n == m_nFirstSetBit) {
    m_nFirstSetBit = ~0U;
    for (size_t i = n + 1; i <= m_nLastSetBit; ++i) {
      if (test(i)) {
        m_nFirstSetBit = i;
        break;
      }
    }
  }
  // Check if the bit we'll clear replaces the last set bit
  if (n == m_nLastSetBit) {
    m_nLastSetBit = ~0U;
    for (size_t i = n; i > 0;) {
      --i;
      if (test(i)) {
        m_nLastSetBit = i;
        break;
      }
    }
  }
}
 
bool ExtensibleBitmap::test(size_t n) const {
  if (n < sizeof(uintptr_t) * 8)
    return (m_StaticMap & (1UL << n));
 
  n -= sizeof(uintptr_t) * 8;
 
  // If its outside the range of possible set bits, it must be clear.
  if (n > m_nMaxBit || !m_pDynamicMap)
    return false;
  return (m_pDynamicMap[n / 8] & (1UL << (n % 8)));
}