/* fastheap.c */

/* Copyright 1997 by Eberhard Mattes <mattes@azu.informatik.uni-stuttgart.de>
   Donated to the public domain.  No warranty.

   1997-07-22 Initial version */

#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include "libemfw.h"
#include "fastheap.h"

extern void *xmalloc (size_t);

typedef struct fastheap_header header;

/* Initialize a fast heap.  Allocate at least CHUNK_SIZE bytes
   (including the header) for automatically added chunks. */

void fastheap_init (fastheap *heap, size_t chunk_size)
{
  DEBUG_ASSERT (heap != NULL);
  heap->first = heap->cur = NULL;
  heap->add = &heap->first;
  heap->chunk_size = chunk_size;
  heap->cur_avail = 0; heap->cur_ptr = NULL;
}

/* Add a chunk to a fast heap.  SIZE includes the header.  In a future
   version, we might want to record whether the chunk is allocated
   statically or dynamically. */

static void add_chunk (fastheap *heap, void *buffer, size_t size)
{
  header *chunk = (header *)buffer;
  chunk->next = NULL;
  DEBUG_ASSERT (size >= sizeof (header));
  chunk->size = size - sizeof (header);
  DEBUG_ASSERT (heap->add != NULL);
  *heap->add = chunk; heap->add = &chunk->next;
}

/* Add a static chunk to a fast heap.  The buffer pointed to by BUFFER
   must be properly aligned for `header'.  Hint: use a
   union to force the buffer to be aligned properly. */

void fastheap_add_static (fastheap *heap, void *buffer, size_t size)
{
  /* A chunk cannot be smaller than its header.  Moreover, there's no
     point in adding small static chunks. */

  DEBUG_ASSERT (heap != NULL);
  DEBUG_ASSERT (buffer != NULL);
  if (size >= 2 * sizeof (header))
    add_chunk (heap, buffer, size);
}

/* Reset a fast heap.  Memory allocation will restart from the first
   chunk.  Note that chunks won't be deallocated, the heap never
   shrinks!  */

void fastheap_reset (fastheap *heap)
{
  DEBUG_ASSERT (heap != NULL);
  heap->cur = NULL;
  heap->cur_avail = 0; heap->cur_ptr = NULL;
}

/* Select the chunk pointed to by CHUNK as `current chunk'.  It is
   assumed that the `next' and `size' members of the chunk header are
   correctly initialized, that is, that the chunk was added by
   add_chunk(). */

static void select_chunk (fastheap *heap, header *chunk)
{
  DEBUG_ASSERT (heap != NULL);
  DEBUG_ASSERT (chunk != NULL);
  heap->cur = chunk;
  heap->cur_ptr = (char *)chunk + sizeof (header);
  heap->cur_avail = chunk->size;
}

/* And now for the heart of the fast heap implementation.  The
   fastheap_alloc() macro calls this helper function if there's not
   enough space in the current chunk (or if there is no current
   chunk). */

void *fastheap_alloc1 (fastheap *heap, size_t size)
{
  void *p;
  size_t chunk_size;
  header *chunk;

  /* First, just try again to allocate from the current chunk, in case
     someone calls this function directly. */

  DEBUG_ASSERT (heap != NULL);
  DEBUG_ASSERT (heap->cur == NULL || heap->cur_avail <= heap->cur->size);
  if (size < heap->cur_avail)
    goto simple;

  /* If there's no current chunk (this happens after initializing or
     resetting), try to use the first chunk if there is any. */

  if (heap->cur == NULL && heap->first != NULL)
    {
      select_chunk (heap, heap->first);
      if (size < heap->cur_avail)
	goto simple;
    }

  /* Move on to the next chunk if there is any. */

  if (heap->cur != NULL && heap->cur->next != NULL)
    {
      select_chunk (heap, heap->cur->next);
      if (size < heap->cur_avail)
	goto simple;
    }

  /* We need a new chunk.  Allocate and add one. */

  DEBUG_ASSERT (size < UINT_MAX - sizeof (header)); /* Assume size_t >= int */
  chunk_size = size + sizeof (header);
  if (chunk_size < heap->chunk_size)
    chunk_size = heap->chunk_size;
  chunk = (header *)xmalloc (chunk_size);
  DEBUG_ASSERT (chunk != NULL);
  add_chunk (heap, chunk, chunk_size);
  select_chunk (heap, chunk);

  /* There is guaranteed to be enough space in the current chunk. */

simple:
  DEBUG_ASSERT (heap->cur_avail >= size);
  DEBUG_ASSERT (heap->cur != NULL);
  DEBUG_ASSERT (heap->cur_avail <= heap->cur->size);
  DEBUG_ASSERT (heap->cur_ptr + heap->cur_avail
		== (char *)heap->cur + sizeof (header) + heap->cur->size);
  heap->cur_avail -= size;
  p = heap->cur_ptr;
  heap->cur_ptr += size;
  return p;
}

/* Create on the fastheap pointed to by HEAP a duplicate of the array
   of N characters pointed to by S. */

void *fastheap_memdup (fastheap *heap, const void *s, size_t n)
{
  void *p;

  DEBUG_ASSERT (heap != NULL);
  DEBUG_ASSERT (s != NULL);
  p = fastheap_alloc (heap, n);
  DEBUG_ASSERT (p != NULL);
  memcpy (p, s, n);
  return p;
}

/* Create on the fastheap pointed to by HEAP a duplicate of the array
   of N characters pointed to by S.  The duplicate will be
   null-terminated. */

char *fastheap_strndup (fastheap *heap, const char *s, size_t n)
{
  char *p;

  DEBUG_ASSERT (heap != NULL);
  DEBUG_ASSERT (s != NULL);
  p = fastheap_alloc (heap, n + 1);
  DEBUG_ASSERT (p != NULL);
  memcpy (p, s, n);
  p[n] = 0;
  return p;
}

#ifndef NDEBUG

/* This function is defined only if DEBUG_ASSERT() is not disabled.
   If NDEBUG is defined, there's no point in this function as
   DEBUG_ASSERT() would be a no-op.  This happens when compiling
   fastheap.c with NDEBUG undefined and the application with NDEBUG
   defined.  We want to get a linker error in that case. */

void fastheap_alloc_assert (fastheap *heap)
{
  DEBUG_ASSERT (heap != NULL);
  if (heap->cur == NULL)
    DEBUG_ASSERT (heap->cur_avail == 0);
  else
    {
      DEBUG_ASSERT (heap->cur_avail <= heap->cur->size);
      DEBUG_ASSERT (heap->cur_ptr + heap->cur_avail
		    == (char *)heap->cur + sizeof (header) + heap->cur->size);
    }
}

#endif