diff options
Diffstat (limited to 'bitmap.h')
-rw-r--r-- | bitmap.h | 112 |
1 files changed, 112 insertions, 0 deletions
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 <jon@jonsantmyer.com> + * + * 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 <stdint.h> +#include <stddef.h> +#include <stdbool.h> + +/*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 |