\section{Pools}
It's not always clear what a C compiler does when a program calls \verb|free|. 
A compiler may create lots of temporary storage and we would like a reasonably
efficient way of reclaiming it.  If most of the temporary objects have the same
size then we can just maintain a {\em free list} to hold the disposed objects.  
An extension of this idea, useful when the objects cover a range of sizes, is to
use an array of free lists.  When we want to create storage for an object we index
into the free-list array using the size of the object as index.  Clearly this involves
placing a bound on the size of object we can allocate using this method.  The
bound is defined by the constant \verb|MAX_POOL_SIZE|.  For larger objects we just 
call \verb|malloc| directly.  The intention is that we will use pools to 
allocate structures, where the size is known at compile time.  Other 
dynamically allocated objects, such as strings, will use \verb|malloc|.  
One of the big advantages of using pools, rather than a direct call to 
\verb|malloc|, is that we can detect storage leaks more readily.

@d Pool definitions @{ 
#define MAX_POOL_SIZE 100
@| MAX_POOL_SIZE @}

Each entry in a free-list is chained to the next one.  We use the type \verb|link|
for such chains.

\label{td_link}
@d Pool definitions @{ 
typedef struct link { struct link* next; } *link;
@| link @}

The roots of the free lists are held in the array \verb|pool|.

@d Pool externs @{extern link pool[]; @}
@d Pool data @{link pool[MAX_POOL_SIZE+1]; @| pool @}

All of the entries in the free-list attached to \verb|pool[|$i$\verb|]| are of
size $i$.  We attach the type \verb|link| to them to allow easy chaining, but 
their actual size will usually be bigger than this.  Of course this raises the 
question of what happens when the actual size is smaller than the size of a
\verb|link| structure.  We take steps to ensure this cannot happen.

To create some storage we use the \verb|new| macro.  This takes the type of
the object to create as argument and returns a pointer to some new storage.
It does this by checking the appropriate pool to see if it is non-empty.  If
it is it just has to unlink the first entry in the list and return this.  If
it is empty then it calls the function \verb|extend_pool| to create some more
storage.  The macro is a bit messy because we have to use a temporary variable
to hold the head of the list while we unlink it.  We can't declare
temporaries local to an expression, and so we use the \verb|pool_temp| global
for this purpose.

@d Pool definitions @{ 
#define new(type_name) \
  ((pool[sizeof(type_name)]) \
   ? (pool_temp = pool[sizeof(type_name)], \
      pool[sizeof(type_name)] = pool[sizeof(type_name)]->next, \
      (type_name *) pool_temp) \
   :  (type_name *) extend_pool(sizeof(type_name))) 
@| new @}

@d Pool externs @{extern link pool_temp; @}
@d Pool data @{link pool_temp; @| pool_temp @}

To free the storage associated with an object pointer we use the macro 
\verb|dispose|.  This just chains the object to the appropriate free list.

@d Pool definitions @{ 
#define dispose(object) \
  { ((link)object)->next = pool[sizeof(*object)]; \
    pool[sizeof(*object)] = (link)object; }
@}

Suppose we want some storage and the appropriate free list is empty.  We could 
just call \verb|malloc| but this would be inefficient.  It is better to allocate
storage for a whole bunch of these objects in one go, on the assumption that more
will be needed later.  But how many to allocate?  The choice could depend on
the size of the object, but for simplicity we just use the constant 
\verb|NELEM| for all sizes.

@d Pool code @{ 
#define NELEM 100
@| NELEM @}

We allocate storage for \verb|NELEM| objects of the required size and link them
together before returning the first one to the caller.  We have to be a bit 
careful if the size of the object is smaller than a \verb|link| object (i.e. 
less than four bytes).  This is unlikely to occur very frequently, and in the rare
cases where it does we just allocate storage as if the object was four bytes long.
This wastes space, but the objects couldn't be chained together otherwise.

@d Pool externs @{extern void *extend_pool(int n); @}

\label{fn_extend_pool}
@d Pool code @{ 
void *extend_pool(int n)
{ int esize; char *start, *last, *p;
  esize = (n < 4) ? 4 : n;
  if ((pool[n] = malloc(NELEM * esize)) == 0) {
    @< Report memory exhausted and exit @> }
  allocated_pool[n] += NELEM * esize;
  start = (char *)pool[n];
  last  = &start[(NELEM-1)*esize];
  for (p = start; p<last; p+=esize) ((link)p)->next = (link)(p+esize);
  ((link)last)->next = NULL;
  pool[n] = pool[n]->next;
  return(start);
} @| extend_pool @}

It's sometimes useful to get a feel for how much storage is being 
allocated and recycled.  We keep track of the amount of pool data 
allocated using the array \verb|allocated_pool|.   

@d Pool data @{int allocated_pool[MAX_POOL_SIZE+1]; @| allocated_pool @}

The function \verb|pool_statistics| prints out a summary of the total 
amount of storage allocated, and the amount currently in use, for each 
pool.

@d Pool externs @{extern void pool_statistics(); @}

\label{fn_pool_statistics}
@D Pool code @{ 
void pool_statistics()
{
  int i, on_list, in_use; link p;
  printf("Pool statistics: in use / total (%%)\n");
  for (i=1; i <= MAX_POOL_SIZE; i++) {
    if (allocated_pool[i] == 0) continue; /* Skip unused entries */
    p = pool[i]; on_list = 0;
    while (p) { on_list += i; p = p->next; }
    in_use = allocated_pool[i] - on_list;
    printf("%3d: %5d /%5d (%2d%%)\n", i, in_use, allocated_pool[i],
           100 * in_use / allocated_pool[i]);
  }
} @| pool_statistics @}
     

If the program runs out of memory we just stop.
@d Report memory exhausted and exit @{
error("Fatal error", "Memory exhausted\n"); @}


The implementation of pools is held in the files \verb|pool.h| and \verb|pool.c|.

@O code/pool.h @{@< Copyright message @>
#ifndef _POOL_H
#define _POOL_H
@< Pool definitions @> 
@< Pool externs @>
#endif
@}

@d Makefile dependencies @{ 
pool.c: occam.h pool.h @}

@d Occam object files @{ pool.o @}

@O code/pool.c @{@< Standard \OCCAM\ includes @>
#include "occam.h"
#include "pool.h"
@< Pool data @>
@< Pool code @> 
@}