epub_miniz_alloc.c

Go to the documentation of this file.

 
#include "epub_miniz_alloc.h"
 
#include <stddef.h>
#include <stdint.h>
#include <string.h>
 
#include "ra8_attributes.h"

typedef struct {
  size_t size;    
  size_t is_free; 
} priv_blk_t;

typedef enum : size_t {
  k_priv_hdr_bytes = ((sizeof(priv_blk_t) + alignof(max_align_t) - 1U) / alignof(max_align_t)) *
                     alignof(max_align_t), 
  k_priv_align     = alignof(max_align_t), 
  k_priv_walk_max =
    k_epub_miniz_pool_bytes / (k_priv_hdr_bytes + alignof(max_align_t)), 
  k_priv_blk_free = 1U,                                                  
  k_priv_blk_used = 0U,                                                  
} priv_alloc_const_t;
 
static_assert((k_epub_miniz_pool_bytes % alignof(max_align_t)) == 0U,
              "miniz workspace size must be a whole number of aligned cells");
static_assert(sizeof(epub_miniz_workspace_t) == k_epub_miniz_pool_bytes,
              "public miniz workspace must have exact advertised capacity");

RA8_INTERNAL
static uintptr_t internal_pointer_address(const void* pointer)
{
  uintptr_t address = 0U;
  static_assert(sizeof(address) == sizeof(pointer), "uintptr_t must represent object pointers");
  (void)memcpy((void*)&address, (const void*)&pointer, sizeof(address));
  return address;
}

RA8_INTERNAL
static bool internal_ready(const epub_miniz_arena_t* arena)
{
  if (arena == nullptr) {
    return false;
  }
  if (arena->initialized != 1U) {
    return false;
  }
  if (arena->base == nullptr) {
    return false;
  }
  if (arena->capacity != (size_t)k_epub_miniz_pool_bytes) {
    return false;
  }
  return (internal_pointer_address(arena->base) % alignof(max_align_t)) == 0U;
}

RA8_INTERNAL
static priv_blk_t* internal_cell_at(const epub_miniz_arena_t* arena, size_t off)
{
  void* const cell = &arena->base[off];
  return (priv_blk_t*)cell;
}

RA8_INTERNAL
static uint8_t* internal_end(const epub_miniz_arena_t* arena)
{
  return &arena->base[arena->capacity];
}

RA8_INTERNAL
static uint8_t* internal_payload(priv_blk_t* block)
{
  return &((uint8_t*)block)[(size_t)k_priv_hdr_bytes];
}

RA8_INTERNAL
static priv_blk_t* internal_header(const epub_miniz_arena_t* arena, void* address)
{
  const uintptr_t payload = internal_pointer_address(address);
  const uintptr_t base    = internal_pointer_address(arena->base);
  return internal_cell_at(arena, (size_t)(payload - base) - (size_t)k_priv_hdr_bytes);
}

RA8_INTERNAL
static priv_blk_t* internal_next(const epub_miniz_arena_t* arena, priv_blk_t* block)
{
  const uintptr_t end  = internal_pointer_address(&internal_payload(block)[block->size]);
  const uintptr_t base = internal_pointer_address(arena->base);
  return internal_cell_at(arena, (size_t)(end - base));
}

RA8_INTERNAL
static bool internal_in_pool(const epub_miniz_arena_t* arena, const void* address)
{
  if (!internal_ready(arena)) {
    return false;
  }
  const uintptr_t value = internal_pointer_address(address);
  const uintptr_t base  = internal_pointer_address(arena->base);
  const uintptr_t first = base + (uintptr_t)k_priv_hdr_bytes;
  const uintptr_t end   = base + (uintptr_t)arena->capacity;
  return (value >= first) && (value < end);
}

RA8_INTERNAL
static size_t internal_align_up(size_t bytes)
{
  const size_t mask = (size_t)k_priv_align - 1U;
  return (bytes + mask) & ~mask;
}

RA8_INTERNAL
static bool internal_request_bytes(size_t items, size_t size, size_t* out_bytes)
{
  if ((size != 0U) && (items > (SIZE_MAX / size))) {
    return false;
  }
  const size_t bytes = items * size;
  if (bytes > (size_t)k_epub_miniz_pool_bytes) {
    return false;
  }
  *out_bytes = bytes;
  return true;
}

RA8_INTERNAL
static void internal_split(const epub_miniz_arena_t* arena, priv_blk_t* block, size_t need)
{
  const size_t remainder_min = (size_t)k_priv_hdr_bytes + (size_t)k_priv_align;
  if ((block->size - need) < remainder_min) {
    return;
  }
  const uint8_t* const payload   = internal_payload(block);
  const uintptr_t      rem_addr  = internal_pointer_address(payload) + need;
  const uintptr_t      base      = internal_pointer_address(arena->base);
  priv_blk_t* const    remainder = internal_cell_at(arena, (size_t)(rem_addr - base));
  remainder->size                = block->size - need - (size_t)k_priv_hdr_bytes;
  remainder->is_free             = (size_t)k_priv_blk_free;
  block->size                    = need;
}

RA8_INTERNAL
static void internal_coalesce(const epub_miniz_arena_t* arena)
{
  priv_blk_t* block = internal_cell_at(arena, 0U);
  for (size_t guard = 0U; guard < (size_t)k_priv_walk_max; ++guard) {
    if ((uint8_t*)block >= internal_end(arena)) {
      break;
    }
    if (block->is_free == (size_t)k_priv_blk_free) {
      priv_blk_t* next = internal_next(arena, block);
      while (((uint8_t*)next < internal_end(arena)) && (next->is_free == (size_t)k_priv_blk_free)) {
        block->size += (size_t)k_priv_hdr_bytes + next->size;
        next = internal_next(arena, block);
      }
    }
    block = internal_next(arena, block);
  }
}
 
ra8_err_t epub_miniz_arena_init(epub_miniz_arena_t* arena, void* workspace, size_t workspace_bytes)
{
  if ((arena == nullptr) || (workspace == nullptr)) {
    return k_ra8_err_null_ptr;
  }
  if (workspace_bytes < (size_t)k_epub_miniz_pool_bytes) {
    return k_ra8_err_invalid_size;
  }
  if ((internal_pointer_address(workspace) % alignof(max_align_t)) != 0U) {
    return k_ra8_err_invalid_arg;
  }
  const epub_miniz_arena_t next = {
    .base        = (uint8_t*)workspace,
    .capacity    = (size_t)k_epub_miniz_pool_bytes,
    .initialized = 1U,
  };
  priv_blk_t* const head = internal_cell_at(&next, 0U);
  head->size             = next.capacity - (size_t)k_priv_hdr_bytes;
  head->is_free          = (size_t)k_priv_blk_free;
  *arena                 = next;
  return k_ra8_ok;
}
 
void epub_miniz_arena_deinit(epub_miniz_arena_t* arena)
{
  if (arena != nullptr) {
    *arena = (epub_miniz_arena_t){};
  }
}
 
void* epub_miniz_alloc(void* opaque, size_t items, size_t size)
{
  epub_miniz_arena_t* const arena = (epub_miniz_arena_t*)opaque;
  if (!internal_ready(arena)) {
    return nullptr;
  }
  size_t bytes = 0U;
  if (!internal_request_bytes(items, size, &bytes)) {
    return nullptr;
  }
  size_t need = internal_align_up(bytes);
  if (need == 0U) {
    need = (size_t)k_priv_align;
  }
  priv_blk_t* block = internal_cell_at(arena, 0U);
  for (size_t guard = 0U; guard < (size_t)k_priv_walk_max; ++guard) {
    if ((uint8_t*)block >= internal_end(arena)) {
      break;
    }
    if ((block->is_free == (size_t)k_priv_blk_free) && (block->size >= need)) {
      internal_split(arena, block, need);
      block->is_free = (size_t)k_priv_blk_used;
      return internal_payload(block);
    }
    block = internal_next(arena, block);
  }
  return nullptr;
}
 
void epub_miniz_free(void* opaque, void* address)
{
  epub_miniz_arena_t* const arena = (epub_miniz_arena_t*)opaque;
  if ((address == nullptr) || !internal_in_pool(arena, address)) {
    return;
  }
  priv_blk_t* const block = internal_header(arena, address);
  block->is_free          = (size_t)k_priv_blk_free;
  internal_coalesce(arena);
}
 
void* epub_miniz_realloc(void* opaque, void* address, size_t items, size_t size)
{
  if (address == nullptr) {
    return epub_miniz_alloc(opaque, items, size);
  }
  epub_miniz_arena_t* const arena = (epub_miniz_arena_t*)opaque;
  if (!internal_in_pool(arena, address)) {
    return nullptr;
  }
  size_t bytes = 0U;
  if (!internal_request_bytes(items, size, &bytes)) {
    return nullptr;
  }
  const size_t need = internal_align_up(bytes);
  if (need == 0U) {
    epub_miniz_free(arena, address);
    return nullptr;
  }
  priv_blk_t* const block = internal_header(arena, address);
  if (block->size >= need) {
    return address;
  }
  void* const moved = epub_miniz_alloc(arena, items, size);
  if (moved == nullptr) {
    return nullptr;
  }
  (void)memcpy(moved, address, block->size);
  epub_miniz_free(arena, address);
  return moved;
}