/**
 * 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