/* fastheap.h */

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

   1997-07-22 Initial version */

/* This code implements a fast heap for memory allocation.  There are
   several restrictions: Objects cannot be deallocated (however, the
   entire fast heap can be reset to the empty state), no alignment is
   guaranteed, there might be quite a lot of overhead for allocating
   big objects (fragmentation), a fast heap never shrinks.  On the
   other hand, it probably cannot be done faster.

   A fast heap is implemented as a single linked list of chunks.
   Allocation is always done from the `current chunk'; if there's not
   enough space left in that chunk, we move on to the next one,
   creating one if necessary.

   The fast heap implementation uses xmalloc() for obtaining memory;
   therefore, the process will be terminated when we run out of
   memory. */

/* Each chunk starts with an instance of this structure.  The bytes
   following this structure are available for allocation. */

struct fastheap_header
{
  struct fastheap_header *next;	/* Pointer to next chunk */
  size_t size;			/* Size excluding header */
};

/* This structure controls one fast heap. */

typedef struct
{
  struct fastheap_header *first; /* The head of the linked list */
  struct fastheap_header *cur;	 /* Pointer to current chunk, or NULL */
  struct fastheap_header **add;	 /* Add new chunk here */
  size_t chunk_size;		 /* Minimum chunk size, including header */
  size_t cur_avail;		 /* Amount of free space in current chunk */
  char *cur_ptr;		 /* Pointer to free space in current chunk */
} fastheap;

void fastheap_init (fastheap *, size_t);
void fastheap_add_static (fastheap *, void *, size_t);
void fastheap_reset (fastheap *);
void *fastheap_memdup (fastheap *, const void *, size_t);
char *fastheap_strndup (fastheap *, const char *, size_t);
void *fastheap_alloc1 (fastheap *, size_t);
void fastheap_alloc_assert (fastheap *);

/* fastheap_alloc() never returns a NULL pointer (this is also true
   for SZ==0). Note: We waste one character per chunk in order to make
   the case of SZ==0 faster (note that we use "<" instead of "<=" for
   comparing SZ to CUR_AVAIL. */

#define fastheap_alloc(hp,sz) ( FASTHEAP_ALLOC_ASSERT (hp), \
  ((size_t)(sz) < (hp)->cur_avail \
   ? (hp)->cur_avail -= (sz), (hp)->cur_ptr += (sz), (hp)->cur_ptr - (sz) \
   : fastheap_alloc1 ((hp), (sz))))

#ifdef NDEBUG
#define FASTHEAP_ALLOC_ASSERT(hp) ((void)0)
#else
#define FASTHEAP_ALLOC_ASSERT(hp) fastheap_alloc_assert(hp)
#endif