path: root/bitmap.c

#include "bitmap.h"

#define BITMAP_MASK_FULL (~((bmcell_t)0))

#define BITMAP_CELL_SIZE (sizeof(bmcell_t) * 8)
#define BITMAP_CELL_SHIFT 6
#define BITMAP_SUBCELL_SHIFT 3

#define BITMAP_TEST(map, i) (map[i >> BITMAP_CELL_SHIFT] & (((bmcell_t)1) << i))
#define BITMAP_SET(map, i)  (map[i >> BITMAP_CELL_SHIFT] |= (((bmcell_t)1) << i))
#define BITMAP_USET(map, i) (map[i >> BITMAP_CELL_SHIFT] &= ~(((bmcell_t)1) << i))

void
bmvl_setup(struct bitmap_vl *bm, size_t bits)
{
    bm->head.length = bm->head.bits_free = bits;
    bm->head.last_free = 0;
    for(size_t i = 0; i < (bits / BITMAP_BITS_PER_CELL); i++) {
        bm->cells[i] = 0;
    }
}

bool 
__bm_test(bmcell_t *cells, size_t i)
{
    return BITMAP_TEST(cells, i) != 0;
}

bm_signed_t
__bm_take(struct bitmap_head *head, bmcell_t *cells)
{
    /*Definitely OOM*/
    if(head->bits_free == 0) return -1;
    /*If last_free is already free, we can just return that*/
    if(BITMAP_TEST(cells, head->last_free) == 0) {
        BITMAP_SET(cells, head->last_free);
        return head->last_free++;
    }

    /*Search all cells after last_free if last_free was taken. 
     * It could mean we're OOM, or that we've missed a gap somewhere*/
    for(size_t cell = (head->last_free >> BITMAP_CELL_SHIFT);
            cell < (head->length >> BITMAP_CELL_SHIFT);
            cell++)
    {
        /*A full bitmask means that every bit in the cell is taken*/
        if(cells[cell] == BITMAP_MASK_FULL) continue;

        /*We sub-divide the search into bytes, so that we can take advantage
         * of mask searches*/
        uint8_t *subcells = (uint8_t*)(&cells[cell]);
        for(uint8_t subcell = 0; subcell < 8; subcell++) {
            /*If the byte is full, we search the next byte*/
            if(subcells[subcell] == 0xFF) continue;
            /*A per-bit search is necessary to find the exact free bit*/
            for(uint8_t bit = 0; bit < 8; bit++) {
                if(subcells[subcell] & (1 << bit)) continue;
                /*Mark the bit as taken*/
                subcells[subcell] |= ((bmcell_t)1 << bit);

                /*Because we're operating on pow2, we can use bitshifts to
                 * simplify 2^x.
                 * Since subcell and bit can only be 1-7, we can OR it into
                 * the shifted cell value*/
                head->last_free =
                    (cell << BITMAP_CELL_SHIFT) |
                    (subcell << BITMAP_SUBCELL_SHIFT) |
                    bit;
                /*This returns the last_free, then increments so that the next
                 * call can (possibly) get a free value*/
                head->bits_free--;
                return head->last_free++;
            }
        }
    }
    /*Getting here means the bitmap couldn't find a free bit and we are
     * presumably OOM*/
    return -1;
}

bm_signed_t
__bm_take_contig(struct bitmap_head *head, bmcell_t *cells, size_t l)
{
    /*If the bitmap doesn't have enough free bits for the span, it will never
     * have enough contiguous bits*/
    if(head->bits_free < l) return -1;
    /*Simul completion flag and utility value for calculating offsets for return
     * value*/
    size_t left = l;
    for(size_t cell = (head->last_free >> BITMAP_CELL_SHIFT);
            cell < (head->length >> BITMAP_CELL_SHIFT);
            cell++)
    {
        /*Return case for breakout when we find the contig span*/
        if(left == 0) break;
        /*If the bitmask is full, there won't be room to fit the requested span*/
        if(cells[cell] == BITMAP_MASK_FULL) {
            left = l;
            continue;
        }
        /*If the bitmask is 0, there are atleast BITMAP_CELL_SIZE contig bits
         * in the bitmap starting here*/
        if(cells[cell] == 0) {
            /*Only continue the loop if there aren't enough bits in this current
             * cell.*/
            if(left > BITMAP_CELL_SIZE) {
                left -= BITMAP_CELL_SIZE;
                continue;
            }
            /*Because there was room for the rest of the span, we can return
             * this address without worrying about fetching other bits.
             * The cell index is subtracted by the inverse of left*/
            head->last_free = 
                (cell << BITMAP_CELL_SHIFT) - (l - left);
            /*Mark left so that we break out of this loop and call the proper
             * return function*/
            left = 0;
            break;
        }
        /*Divide search into bytes for faster search of bmcell_t structure*/
        uint8_t *subcells = (uint8_t*)(&cells[cell]);
        for(uint8_t subcell = 0; subcell < 8; subcell++) {
            if(left == 0) break;
            /*Subcell is full, we refill left and stop searching this subcell*/
            if(subcells[subcell] == 0xFF) {
                left = l;
                continue;
            }
            /*Since the subcell is empty, there are atleast 8 contig bits*/
            if(subcells[subcell] == 0) {
                /*If we need more than 8 bits, we subtract 8 from left and
                 * continue*/
                if(left > 8) {
                    left -= 8;
                    continue;
                }
                /*Otherwise, we return the index of this particular subcell
                 * minus the inverse of left*/
                head->last_free = 
                    ((cell << BITMAP_CELL_SHIFT) |
                     (subcell << BITMAP_SUBCELL_SHIFT)) -
                    (l - left);
                /*Mark left for proper exit and return*/
                left = 0;
                break;
            }
            /*Search the entire subcell for free bits.*/
            for(uint8_t bit = 0; bit < 8; bit++) {
                /*When we find a taken bit, and there are still bits to fetch,
                 * then the block will never be contiguous and we need to
                 * start again*/
                if(subcells[subcell] & (1 << bit)) {
                    left = l;
                    continue;
                }
                left--;
                if(left == 0) {
                    /*When we have found all the bits we need, we return the
                     * index to the start of the contig span*/
                    head->last_free =
                        ((cell << BITMAP_CELL_SHIFT) |
                         (subcell << BITMAP_SUBCELL_SHIFT) |
                         bit) -
                        (l - left);
                    break;
                }
            }
        }
    }
    /*We didn't find a contiguous span. Either the bitmap is fragmented or
     * there's not enough free space to fit the span*/
    if(left != 0) return -1;

    /*Mark all of the bits in the span as taken*/
    for(size_t i = 0; i < l; i++) {
        BITMAP_SET(cells, (head->last_free + i));
    }
    /*Setup to return last_free, while incrementing last_free by l*/
    head->last_free += l;
    head->bits_free -= l;
    return head->last_free - l;
    
}

void
__bm_reserve(struct bitmap_head *head, bmcell_t *cells, size_t i)
{
    /*Take the bit at i and update the bits_free counter*/
    BITMAP_SET(cells, i);
    head->bits_free--;
}

void
__bm_reserve_contig(
        struct bitmap_head *head, 
        bmcell_t *cells, 
        size_t i, 
        size_t l)
{
    /*For every bit between i and i+l, mark as reserved*/
    head->bits_free -= l;
    for(; l != 0; l--, i++) {
        BITMAP_SET(cells, i);
    }
}

void
__bm_release(struct bitmap_head *head, bmcell_t *cells, size_t i)
{
    /*Release the bit at i, update last_free, and update the bits_free counter*/
    BITMAP_USET(cells, i);
    if(head->last_free > i) head->last_free = i;
    head->bits_free++;
}

void 
__bm_release_contig(
        struct bitmap_head *head, 
        bmcell_t *cells, 
        size_t i, 
        size_t l)
{
    /*Update the last_free and bits_free counters*/
    head->bits_free += i;
    if(head->last_free > i) head->last_free = i;
    /*For every bit between i and i+l, mark as free*/
    for(; l != 0; l--, i++) {
        BITMAP_USET(cells, i);
    }
}