bballoc.h

// This code is Public Domain

// General information:
//  Thread safety: none, wrap in a mutex or something
//  Allocator type: combination of freelist and bitmap allocator

// Usage:
//  include bballoc.h in every file that uses functionality from the library.
//  define bballoc_implementation in EXACTLY one of the files.

#ifndef bballoc__h
#define bballoc__h

#ifdef __cplusplus
  #define bb_extern extern "c"
#elif
  #define bb_extern extern
#endif

#ifndef bb_assert
  #include<assert.h>
  #define bb_assert assert
#endif

union bb__block typedef bb__block;
union bb__block {
  struct {
    bb__block *prev;
    bb__block *next;
  };
  size_t num_blocks;
};

struct bb_allocator typedef bb_allocator;
struct bb_allocator {
  unsigned char *bitmap;
  bb__block *blocks;
  size_t bitmap_size;
  size_t block_size;
  size_t nblocks;
  bb__block *head;
};

// block_sz must be greater or equal to 16 and be a power of two
bb_extern void bballoc__init(bb_allocator *a, size_t size, void *buffer, size_t block_sz);

bb_extern void *bballoc(size_t size);
bb_extern void bbfree(void *ptr);



#ifdef bballoc_implementation

static inline int bb__is_pot(size_t s)
{
  return (s&(s-1))==0;
}

static inline size_t bb__alignf(size_t s, size_t a)
{
  assert(bb__is_pot(a));
  return (s+a-1) & ~(a-1);
}

static inline size_t bb__alignb(size_t s, size_t a)
{
  assert(bb__is_pot(a));
  return s & ~(a-1);
}

static inline size_t bb__index_from_block(bb__allocator *a, bb__block *b)
{
  size_t offset = (size_t)b - (size_t)a->blocks;
  size_t i = offset / a->block_size;
  return i;
}

static void bb__unlink_blocks(bb__allocator *a, size_t index, size_t num)
{
  bb__block *this_ptr_means_its_relinked = (bb__block *)(NULL)+1;

  size_t i = index;

  for(size_t i = index; i != index+num; ++i ) {
    bb__block *block     = &a->blocks[i];

    if(block->prev == this_ptr_means_its_relinked) continue;

    bb__block *leftmost  = block;
    bb__block *leftright = block;

    size_t left_index;
    do {
      bb__block *saved = leftmost;
      leftmost = leftmost->prev;
      left_index = bb__index_from_block(leftmost);
      saved->prev = this_ptr_means_its_relinked;
    } while(leftmost != NULL && index <= leftmost && leftmost < index+num);

    size_t right_index;
    do {
      bb__block *saved = rightmost;
      rightmost = rightmost->next;
      right_index = bb__index_from_block(rightmost);
      saved->prev = this_ptr_means_its_relinked;
    } while(rightmost != NULL && index <= rightmost && rightmost < index+num);

    if(leftmost != NULL)  leftmost->next = rightmost;
    if(rightmost != NULL) rightmost->prev = leftmost;
  }
}

void bballoc__init(bb_allocator *a, size_t size, void *buffer, size_t block_sz)
{
  assert(buffer != NULL);
  assert(block_sz >= 16);
  assert(bb__is_pot(block_sz));
  
  // Calculate size of bitmap and remaining space
  // (math shit)
  size_t bitmap_sz = size / (1+8*block_sz);
  size_t remain_sz = size % (1+8*block_sz);
  size_t nblocks   = bitmap_sz * 8;
  size_t blocks_sz = nblocks * block_sz;

  unsigned char *bitmap =  (unsigned char *)buffer;
  unsigned char *blocks = (bb__block *)((unsigned char *)buffer + bitmap_sz);

  // Initialize free list
  size_t i = nblocks;
  bb__block *next_free = NULL;
  do {
    bb__block *block = &blocks[nblocks];
    
    block->next = next_free;
    if(next_free != NULL) next_free->prev = block;

    next_free = block;
  } while(i != 0);

  a->head = next_free;

  // Initialize bitmap
  for(size_t i = 0; i != bitmap_sz; ++i) {
    bitmap[i] = 0;
  }

  a->bitmap = bitmap;
  a->blocks = blocks;
  a->bitmap_size = bitmap_sz;
  a->block_size = block_sz;
  a->nblocks = nblocks;
}

bb_extern void *bballoc(bb_allocator *a, size_t size)
{
  void *allocated_memory = NULL;

  // Calculate required number of blocks
  size_t rounded_size = alignf(size, a->block_size);
  size_t blocks_req = 1 + rounded_size/a->block_size;

  bb__block *start = a->head;
  while(start != NULL) {
    size_t index = bb__index_from_block(a, start);

    // Check whether the next blocks_req indices are free
    int free = 1;
    for(size_t i = index; i != index+blocks_req; ++i) {
      int entry = (int)i/8;
      int bit = (int)i%8;
      int mask = 1<<bit;
      if((a->bitmap[entry] & mask) == mask) {
        free = 0;
        break;
      }
    }

    // Found
    if(free) {
      bb__unlink_blocks(a, index, blocks_req);

      bb__block *control = a->blocks[index];
      allocated_memory = (void *)(control+1);

      // Mark these as occupied in the bitmap
      for(size_t i = index; i != index+blocks_req; ++i) {
        int entry = (int)i/8;
        int bit = (int)i%8;
        int mask = 1<<bit;
        a->bitmap[entry] |= mask;
      }

      control->num_blocks = blocks_req;
      break;
    }

    start = start->next;
  }

  return allocated_memory;
}

bb_extern void bbfree(bb__allocator *a, void *ptr)
{
  assert(a->blocks < ptr && ptr <= a->blocks+a->nblocks);
  bb__block *control = (bb__block *)ptr - 1;

  bb__block *last = a->head->next;
  bb__block *prev = a->head;
  bb__block *cur = control;

  size_t nblocks = control->num_blocks;
  for(size_t i = 0; i != nblocks; ++i) {
    prev->next = cur;
    cur->prev = prev;
    prev = cur;

    cur += 1;
  }

  // Mark the blocks as free in the bitmap
  for(size_t i = index; i != index+blocks_req; ++i) {
    int entry = (int)i/8;
    int bit = (int)i%8;
    int mask = 1<<bit;
    a->bitmap[entry] &= ~mask;
  }

  cur->next = last;
  if(last != NULL) last->prev = cur;
}

#endif // bballoc_implementation
#endif // bballoc__h