/*************************************************
*    The PMW Music Typesetter - 3rd incarnation  *
*************************************************/

/* Copyright (c) Philip Hazel, 1991 - 2020 */

/* Written by Philip Hazel, starting November 1991 */
/* This file last modified: April 2020 */

/* Store Management Routines */

#include "pmwhdr.h"

/* If this is defined, every staff item is in a separate block, testing the
code for jumping between blocks. */

// #define DEBUGJUMP 1

/* If this is defined, memory sanity checks are done. */

// #define sanity

/* Store is taken from the system in blocks whose minimum size is parameterized
here. Then it is carved up into smaller blocks, as needed. It may be that
Unix-like systems could do this efficiently enough with malloc/free these days,
but this approach dates back to times when that was a performance hit. */

#define store_allocation_unit    32*1024

/* Musical data is packed into blocks whose size is parameterized here. */

#define store_item_unit           8*1000

/* Free queue entries contain a pointer to the next entry and their length, in
a storestr at the start. Allocated blocks also have a storestr at their start,
but only the length field is set. We used just to have an int at the start, but
this doesn't work on 64-bit systems, because we need to return correctly
aligned blocks. */

typedef struct storestr {
  struct storestr *next;
  usint length;
} storestr;



/*************************************************
*                  Static data                   *
*************************************************/

#ifdef trace
static FILE *tracefile = NULL;
#endif

/* An anchoring free queue block - the queue is searched from the next block on
the chain. */

static storestr  store_freequeue = { NULL, sizeof(storestr) };

/* An anchoring item buffer, just large enough to hold a b_Jump, which will be
inserted when the first real item is required. */

static b_Jumpstr store_bstrbase;
static bstr *store_itemptr = (bstr *)(&store_bstrbase);  /* Next item */
static int   store_itemspace = ROUND(sizeof(b_Jumpstr)); /* Space left */



/*************************************************
*             Trace logging                      *
*************************************************/

/* This function is used for debugging memory handling by tracing gets and
frees etc.

Arguments:
  s           a string to print
  a           an address to print
  b           a number to print

Returns:      nothing
*/

#ifdef trace
static void
do_trace(char *s, void *a, int b)
{
if (tracefile == NULL) tracefile = fopen("storetrace", "w");
fprintf(tracefile, "%s %8p %8d\n", s, a, b);
}
#endif


/*************************************************
*         Free queue sanity check                *
*************************************************/

/* This function is used for debugging memory handling by checking the sanity
of the free queue. The check is just that the chaining is valid.

Arguments:  none
Returns:    nothing
*/

#ifdef sanity
static
void store_freequeuecheck(void)
{
storestr *p = store_freequeue.next;
while (p != NULL) p = p->next;
}
#endif


/*************************************************
*               Get block                        *
*************************************************/

/* This function gets a new block of memory, searching the free queue first for
something that is big enough. If not, it gets a new large block, and starts to
carve it up. If it can't get any more store, it returns NULL.

Argument:   the size required, in bytes
Returns:    pointer to usable store (after an initial storestr), or NULL
*/

void *
store_get(usint bytesize)
{
int newlength;
usint strsize = (usint)sizeof(storestr);
storestr *newblock;
storestr *previous = &store_freequeue;
storestr *p = store_freequeue.next;

/* Add space for one storestr to hold the length (and a pointer when the block
is freed), then round up to a multiple of storestrs. Use (~strsize + 1) rather
than -strsize because strsize is unsigned. */

bytesize = (bytesize + 2*strsize - 1) & (~strsize + 1);

#ifdef sanity
store_freequeuecheck();
#endif

/* Keep statistics */

main_storetotal += bytesize;

/* Search free queue for a block that is big enough */

while(p != NULL)
  {
  if (bytesize <= p->length)
    {    /* found suitable block */
    int leftover = p->length - bytesize;
    if (leftover == 0)
      {  /* block used completely */
      previous->next = p->next;
      }
    else
      {  /* use bottom of block */
      storestr *remains = p + bytesize/sizeof(storestr);
      remains->length = leftover;
      previous->next = remains;
      remains->next = p->next;
      p->length = bytesize;
      }
    #ifdef sanity
    store_freequeuecheck();
    #endif
    #ifdef trace
    do_trace("get ", p, bytesize);
    #endif

    return (void *)(p + 1);    /* leave leading stavestr "hidden" */
    }
  else
    {    /* try next block */
    previous = p;
    p = p->next;
    }
  }

/* No block long enough has been found. Get a new big block and recurse. */

main_storetotal -= bytesize;  /* correction */
newlength = (bytesize > store_allocation_unit)?
  bytesize : store_allocation_unit;

newblock = malloc(newlength);
if (newblock == NULL) return NULL;

#ifdef trace
do_trace("GET ", newblock, newlength);
#endif

newblock->length = newlength;                 /* Set block length */
main_storetotal += newlength;                 /* Pretend it's allocated */
store_free(newblock + 1);                     /* Add to free queue */
return store_get(bytesize-sizeof(storestr));  /* Try again */
}


/*************************************************
*     Get store, failing if none available       *
*************************************************/

/* This function gives a hard error if no store is available. In these days of
gigabyte memories, failure is a remote possibility.

Argument:  size of block required
Returns:   pointer to useable portion of the block
*/

void *
store_Xget(int bytesize)
{
void *yield = store_get(bytesize);
if (yield == NULL) error_moan(ERR1, bytesize);  /* Hard */
return yield;
}


/*************************************************
*      Copy store, failing if no store           *
*************************************************/

/* This function makes a copy of a block of store.

Argument:  the block to copy ) in both cases, the usable pointers
Returns:   the new block     )
*/

void *
store_copy(void *p)
{
storestr *pp = (storestr *)p - 1;
usint length = pp->length - sizeof(storestr);
void *yield = store_Xget(length);
memcpy(yield, p, length);
return yield;
}


/*************************************************
*        Copy string, failing if no store        *
*************************************************/

/* This function copies a C string into a new block of store.

Argument:  the string
Returns:   pointer to the copy
*/

uschar *
store_copystring(uschar *s)
{
uschar *yield = store_Xget(Ustrlen(s)+1);
Ustrcpy(yield, s);
return yield;
}


/*************************************************
*         Yield address of next staff item       *
*************************************************/

/* This is used to initialize the bar index and on other occasions when we want
to know what the next item address will be without actually setting the item
up. There always is a next item available.

Arguments:  none
Returns:    pointer to the next item
*/

void *
store_nextitem(void)
{
return store_itemptr;
}


/*************************************************
*               Get a staff item                 *
*************************************************/

/* Staff items come from the staff item block, packed in together. When the
block is used up, we put in an adjustment item to the next one. There is always
one next item available. The size depends on the type.

Argument:  the item type
Returns:   pointer to the next item, with type initialized
*/

void
*store_getitem(int type)
{
void *yield;
int size = length_table[type];
#ifndef DEBUGJUMP
if (store_itemspace < size + length_table[b_Jump])
#endif
  {
  b_Jumpstr *j = (b_Jumpstr *)store_itemptr;
  bstr *newbuff = store_Xget(store_item_unit);

  j->type = b_Jump;
  j->next = (bstr *)((uschar *)newbuff - length_table[b_Jump]);

  store_itemptr = newbuff;
  store_itemspace = store_item_unit;
  main_storestaves += length_table[b_Jump];
  }

store_itemptr->type = type;
yield = (void *)store_itemptr;

store_itemptr = (bstr *)((uschar *)store_itemptr + size);
store_itemspace -= size;
main_storestaves += size;
return yield;
}


/*************************************************
*           Free a chunk of store                *
*************************************************/

/* The length is in the storestr precedes the address that the client was
given. The freed block is put onto the free chain, possibly amalgamated with a
block that is already there.

Argument:   the client (usable) address
Returns:    nothing
*/

void
store_free(void *address)
{
storestr *previous = &store_freequeue;
storestr *this = previous->next;
storestr *start = ((storestr *)address) - 1;
storestr *end = start + start->length/sizeof(storestr);

main_storetotal -= start->length;

#ifdef sanity
store_freequeuecheck();
#endif

#ifdef trace
do_trace("free", start, start->length);
#endif

/* Find where to insert */

while (this != NULL)
  {
  if (start < this) break;
  previous = this;
  this = previous->next;
  }

/* Insert */

previous->next = start;
start->next = this;

/* Check for overlap with next */

if (end > this && this != NULL)
  error_moan(ERR2, start, start->length, this);  /* Hard */

/* Check for contiguity with next */

if (end == this)
  {
  start->next = this->next;
  start->length += this->length;
  }

/* Check for overlap/contiguity with previous */

if (previous != &store_freequeue)
  {
  storestr *prevend = previous + previous->length/sizeof(storestr);
  if (prevend > start)
    error_moan(ERR3, previous, previous->length, start);  /* Hard */

  if (prevend == start)
    {
    previous->next = start->next;
    previous->length += start->length;
    }
  }

#ifdef sanity
store_freequeuecheck();
#endif
}

/* End of store.c */