From d4a155e13103216d50691a15b403f3112a42eb8e Mon Sep 17 00:00:00 2001 From: Jon Santmyer Date: Fri, 24 Jun 2022 10:06:20 -0400 Subject: Freestanding bitmap. Functions for individual and contiguous allocations, fills, and clears --- bitmap.c | 230 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ bitmap.h | 112 +++++++++++++++++++++++++++++++ 2 files changed, 342 insertions(+) create mode 100644 bitmap.c create mode 100644 bitmap.h diff --git a/bitmap.c b/bitmap.c new file mode 100644 index 0000000..cdc1b46 --- /dev/null +++ b/bitmap.c @@ -0,0 +1,230 @@ +#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); + } +} diff --git a/bitmap.h b/bitmap.h new file mode 100644 index 0000000..913f818 --- /dev/null +++ b/bitmap.h @@ -0,0 +1,112 @@ +/** + * bitmap.h + * Copyright (c) 2022 Jon Santmyer + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + * + * A freestanding implementation of a variable length bitmap. + * Depends on compiler provided header files + * stdint, stddef, stdbool + * + * Allocation for bitmap_vl is dependent on allocator implementation + * Static length bitmaps can be defined using this example + * + * struct bitmap_sl + * { + * struct bitmap_head head; + * bmcell_t cells[BITMAP_CELLS(n)]; + * }; + * where n is the number of bits you want in the bitmap + * To use said struct, you need to feed bmvl_setup with a cast pointer to + * bitmap_sl and the number of bits you have. + * + * For other bit systems, replace the type defined as + * bm_signed_t and bm_unsigned_t + * with an (u)int_t type of the proper bit length + * + * For using the bitmap, use the functions declared under #define blocks. + * The hidden functions are for genericising other bitmap types following + * the above format. + * + * bitmap_head contains a last_free variable which is used to accelerate the + * average allocation times. Instead of iterating through the entire map, the + * allocator can iterate from last_free until length. + * Most bm_take operations will be O(1) because last_free is assumed to mark an + * empty bit in the map + */ + +#ifndef BITMAP_H +#define BITMAP_H 1 + +#include +#include +#include + +/*Can be changed to int32_t/uint32_t for 32-bit systems*/ +typedef int64_t bm_signed_t; +typedef uint64_t bm_unsigned_t; +typedef bm_unsigned_t bmcell_t; + +struct bitmap_head +{ + size_t length; + size_t bits_free; + size_t last_free; +}; + +struct bitmap_vl +{ + struct bitmap_head head; + bmcell_t cells[]; +}; + +#define BITMAP_BITS_PER_CELL (8 * sizeof(bmcell_t)) +#define BITMAP_CELLS(bits) \ + ((bits + (BITMAP_BITS_PER_CELL - 1)) / (BITMAP_BITS_PER_CELL)) +#define BITMAP_LEN(bits) ((bits / 8) + (sizeof(struct bitmap_head))) + +/*Fills a bitmap struct with proper length, and status vars. Zeros the cells*/ +void bmvl_setup(struct bitmap_vl *bm, size_t bits); + +/*Check if bit in bitmap is taken*/ +bool __bm_test(bmcell_t *cells, size_t i); +#define bm_test(bitmap, i) __bm_test(bitmap->cells, i) + +/*Functions for taking free bits in the bitmap. Returns -1 if none are + * available. Returns the index of the (first) bit if a suitable range is found + */ +bm_signed_t __bm_take(struct bitmap_head *head, bmcell_t *cells); +bm_signed_t __bm_take_contig(struct bitmap_head *head, bmcell_t *cells, size_t l); +#define bm_take(bitmap) __bm_take(&bitmap->head, bitmap->cells) +#define bm_take_contig(bitmap, l) \ + __bm_take_contig(&bitmap->head, bitmap->cells, l) + +/* Fills the bit/bits at i. Runs until l if applicable */ +void __bm_reserve(struct bitmap_head *head, bmcell_t *cells, size_t i); +void __bm_reserve_contig(struct bitmap_head *head, bmcell_t *cells, size_t i, size_t l); +#define bm_reserve(bitmap, i) __bm_reserve(&bitmap->head, bitmap->cells, i) +#define bm_reserve_contig(bitmap, i, l) __bm_reserve_contig(&bitmap->head, bitmap->cells, i, l) + +/* Clears the bit/bits at i. Runs until l if applicable */ +void __bm_release(struct bitmap_head *head, bmcell_t *cells, size_t i); +void __bm_release_contig(struct bitmap_head *head, bmcell_t *cells, size_t i, size_t l); +#define bm_release(bitmap, i) __bm_release(&bitmap->head, bitmap->cells, i) +#define bm_release_contig(bitmap, i, l) __bm_release_contig(&bitmap->head, bitmap->cells, i, l) + +#endif -- cgit v1.2.1