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

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

/* Written by Philip Hazel, starting November 1991 */
/* This file last modified: September 2008 */

/* Store Management Routines */

#include "pmwhdr.h"


/* 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;
  unsigned int 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 = 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(int bytesize)
{
int newlength;
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. */

bytesize = (bytesize + 2*sizeof(storestr) - 1) & (-(int)sizeof(storestr));

#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(1, 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;
unsigned int 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];
if (store_itemspace < size + sizeof(b_Jumpstr))
  {
  b_Jumpstr *j = (b_Jumpstr *)store_itemptr;
  bstr *newbuff = store_Xget(store_item_unit);

  j->type = b_Jump;
  j->next = (bstr *)((uschar *)newbuff - sizeof(b_Jumpstr));

  store_itemptr = newbuff;
  store_itemspace = store_item_unit;
  main_storestaves += sizeof(b_Jumpstr);
  }

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(2, 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(3, 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 */
