/*
* Copyright (c) 2006 Jakub Jermar
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* - The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/** @addtogroup kernel_generic_adt
* @{
*/
/**
* @file
* @brief Implementation of bitmap ADT.
*
* This file implements bitmap ADT and provides functions for
* setting and clearing ranges of bits and for finding ranges
* of unset bits.
*/
#include <adt/bitmap.h>
#include <align.h>
#include <assert.h>
#include <macros.h>
#include <typedefs.h>
#define ALL_ONES 0xff
#define ALL_ZEROES 0x00
/** Unchecked version of bitmap_get()
*
* This version of bitmap_get() does not do any boundary checks.
*
* @param bitmap Bitmap to access.
* @param element Element to access.
*
* @return Bit value of the element in the bitmap.
*
*/
static unsigned int bitmap_get_fast(bitmap_t *bitmap, size_t element)
{
size_t byte = element / BITMAP_ELEMENT;
uint8_t mask = 1 << (element & BITMAP_REMAINER);
return !!((bitmap->bits)[byte] & mask);
}
/** Get bitmap size
*
* Return the size (in bytes) required for the bitmap.
*
* @param elements Number bits stored in bitmap.
*
* @return Size (in bytes) required for the bitmap.
*
*/
size_t bitmap_size(size_t elements)
{
size_t size = elements / BITMAP_ELEMENT;
if ((elements % BITMAP_ELEMENT) != 0)
size++;
return size;
}
/** Initialize bitmap.
*
* No portion of the bitmap is set or cleared by this function.
*
* @param bitmap Bitmap structure.
* @param elements Number of bits stored in bitmap.
* @param data Address of the memory used to hold the map.
* The optional 2nd level bitmap follows the 1st
* level bitmap.
*
*/
void bitmap_initialize(bitmap_t *bitmap, size_t elements, void *data)
{
bitmap->elements = elements;
bitmap->bits = (uint8_t *) data;
bitmap->next_fit = 0;
}
/** Set range of bits.
*
* @param bitmap Bitmap structure.
* @param start Starting bit.
* @param count Number of bits to set.
*
*/
void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t count)
{
assert(start + count <= bitmap->elements);
if (count == 0)
return;
size_t start_byte = start / BITMAP_ELEMENT;
size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT);
/* Leading unaligned bits */
size_t lub = min(aligned_start - start, count);
/* Aligned middle bits */
size_t amb = (count > lub) ? (count - lub) : 0;
/* Trailing aligned bits */
size_t tab = amb % BITMAP_ELEMENT;
if (start + count < aligned_start) {
/* Set bits in the middle of byte. */
bitmap->bits[start_byte] |=
((1 << lub) - 1) << (start & BITMAP_REMAINER);
return;
}
if (lub) {
/* Make sure to set any leading unaligned bits. */
bitmap->bits[start_byte] |=
~((1 << (BITMAP_ELEMENT - lub)) - 1);
}
size_t i;
for (i = 0; i < amb / BITMAP_ELEMENT; i++) {
/* The middle bits can be set byte by byte. */
bitmap->bits[aligned_start / BITMAP_ELEMENT + i] =
ALL_ONES;
}
if (tab) {
/* Make sure to set any trailing aligned bits. */
bitmap->bits[aligned_start / BITMAP_ELEMENT + i] |=
(1 << tab) - 1;
}
}
/** Clear range of bits.
*
* @param bitmap Bitmap structure.
* @param start Starting bit.
* @param count Number of bits to clear.
*
*/
void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t count)
{
assert(start + count <= bitmap->elements);
if (count == 0)
return;
size_t start_byte = start / BITMAP_ELEMENT;
size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT);
/* Leading unaligned bits */
size_t lub = min(aligned_start - start, count);
/* Aligned middle bits */
size_t amb = (count > lub) ? (count - lub) : 0;
/* Trailing aligned bits */
size_t tab = amb % BITMAP_ELEMENT;
if (start + count < aligned_start) {
/* Set bits in the middle of byte */
bitmap->bits[start_byte] &=
~(((1 << lub) - 1) << (start & BITMAP_REMAINER));
return;
}
if (lub) {
/* Make sure to clear any leading unaligned bits. */
bitmap->bits[start_byte] &=
(1 << (BITMAP_ELEMENT - lub)) - 1;
}
size_t i;
for (i = 0; i < amb / BITMAP_ELEMENT; i++) {
/* The middle bits can be cleared byte by byte. */
bitmap->bits[aligned_start / BITMAP_ELEMENT + i] =
ALL_ZEROES;
}
if (tab) {
/* Make sure to clear any trailing aligned bits. */
bitmap->bits[aligned_start / BITMAP_ELEMENT + i] &=
~((1 << tab) - 1);
}
bitmap->next_fit = start_byte;
}
/** Copy portion of one bitmap into another bitmap.
*
* @param dst Destination bitmap.
* @param src Source bitmap.
* @param count Number of bits to copy.
*
*/
void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t count)
{
assert(count <= dst->elements);
assert(count <= src->elements);
size_t i;
for (i = 0; i < count / BITMAP_ELEMENT; i++)
dst->bits[i] = src->bits[i];
if (count % BITMAP_ELEMENT) {
bitmap_clear_range(dst, i * BITMAP_ELEMENT,
count % BITMAP_ELEMENT);
dst->bits[i] |= src->bits[i] &
((1 << (count % BITMAP_ELEMENT)) - 1);
}
}
static int constraint_satisfy(size_t index, size_t base, size_t constraint)
{
return (((base + index) & constraint) == 0);
}
/** Find a continuous zero bit range
*
* Find a continuous zero bit range in the bitmap. The address
* computed as the sum of the index of the first zero bit and
* the base argument needs to be compliant with the constraint
* (those bits that are set in the constraint cannot be set in
* the address).
*
* If the index argument is non-NULL, the continuous zero range
* is set and the index of the first bit is stored to index.
* Otherwise the bitmap stays untouched.
*
* @param bitmap Bitmap structure.
* @param count Number of continuous zero bits to find.
* @param base Address of the first bit in the bitmap.
* @param prefered Prefered address to start searching from.
* @param constraint Constraint for the address of the first zero bit.
* @param index Place to store the index of the first zero
* bit. Can be NULL (in which case the bitmap
* is not modified).
*
* @return Non-zero if a continuous range of zero bits satisfying
* the constraint has been found.
* @return Zero otherwise.
*
*/
bool bitmap_allocate_range(bitmap_t *bitmap, size_t count, size_t base,
size_t prefered, size_t constraint, size_t *index)
{
if (count == 0)
return false;
size_t size = bitmap_size(bitmap->elements);
size_t next_fit = bitmap->next_fit;
/*
* Adjust the next-fit value according to the address
* the caller prefers to start the search at.
*/
if ((prefered > base) && (prefered < base + bitmap->elements)) {
size_t prefered_fit = (prefered - base) / BITMAP_ELEMENT;
if (prefered_fit > next_fit)
next_fit = prefered_fit;
}
for (size_t pos = 0; pos < size; pos++) {
size_t byte = (next_fit + pos) % size;
/* Skip if the current byte has all bits set */
if (bitmap->bits[byte] == ALL_ONES)
continue;
size_t byte_bit = byte * BITMAP_ELEMENT;
for (size_t bit = 0; bit < BITMAP_ELEMENT; bit++) {
size_t i = byte_bit + bit;
if (i >= bitmap->elements)
break;
if (!constraint_satisfy(i, base, constraint))
continue;
if (!bitmap_get_fast(bitmap, i)) {
size_t continuous = 1;
for (size_t j = 1; j < count; j++) {
if ((i + j < bitmap->elements) &&
(!bitmap_get_fast(bitmap, i + j)))
continuous++;
else
break;
}
if (continuous == count) {
if (index != NULL) {
bitmap_set_range(bitmap, i, count);
bitmap->next_fit = i / BITMAP_ELEMENT;
*index = i;
}
return true;
} else
i += continuous;
}
}
}
return false;
}
/** @}
*/