\documentclass[panstarrs]{panstarrs}

\title{The \PS{} Utilities API}
\author{Robert Lupton}
\group{}
\organization{}
\docnumber{PSDC-???}

\fancyhead{}
\fancyhead[L]{\PS{} Document}
\fancyhead[R]{PSDC-???}
\fancyhead[C]{Revision 0.1 -- Draft}
\fancyfoot[L]{\PS{} Utilities}
\fancyfoot[R]{\today}

\begin{document}

\pagenumbering{roman} \thispagestyle{empty} \maketitle

\pagebreak \pagestyle{fancy}
{ \Large \bf Revision History}
\begin{center}
\begin{tabular}{|p{1in}|p{1in}|p{4.5in}|}
\hline
{\bf Revision Number} & {\bf Release Date} & {\bf Description} \\
\hline
%0.1 & 2003/12/08 & First draft \\
\hline
\end{tabular}
\end{center}

{ \Large \bf Referenced Documents}
\begin{center}
\begin{tabular}{|p{1in}|p{2.75in}|p{2.75in}|}
\hline
{\bf \PS{} ID} & {\bf Title} & {\bf Author} \\
\hline
%%% References here.
\hline
\end{tabular}
\end{center}

\pagebreak
\tableofcontents

% \pagebreak
% \listoffigures

\pagebreak \pagenumbering{arabic}

\section{Memory Management}
\hlabel{psMemBlock}

\subsection{Introduction}

The \PS{} software system will need a level of memory management
placed between the operating system (malloc/free) and the high level
routines (e.g. \code{psMetaDataAlloc}).

This layer is in addition to the possibility that specific heavily
used data types may need their own special-purpose memory managers;
but as we have specified that all user-level objects be allocated via
\code{typeAlloc/typeFree} functions, we will easily be able to
implement such functionality without impacting on the facilities
described here.

All of the memory management APIs should be provided in a header file
\file{psMemory.h} which is included by \file{psUtils.h}.

\subsection{Rationale}

We wish to insert our own layer of memory management for a number of
reasons:

\begin{itemize}
\item
  We wish to insulate ourselves from the details of the system-provided
  \code{malloc}.  There is no guarantee that the goals of the system
  architect align with those of the \PS{} processing

\item
  We need at least a wrapper layer which handles failed memory
  requests without requiring the application programmer to check
  every attempted allocation.

\item
  We need to provide a mechanism for tracking and fixing memory
  leaks.  While it is possible to do this by linking with external
  libraries (\tbd{reference}), it is convenient to do so within the
  \PS{} framework.

\item
  Similarly, we wish to provide convenient hooks to detect and diagnose
  memory corruption.

\item
  While debugging complex scientific code, it is very useful to be
  able to trace a given data structure as it passed through the
  processing pipeline.

\item
  There may be other features that we wish to add in the future (e.g.
  associating a type with every allocation).
\end{itemize}

\subsection{A Minimal Specification}

The previous section laid out a number of desiderata for a memory
management system.  Rather than implement our own heap-manager at this
stage of the project, I propose that we put in place a sufficient
set of data structures and APIs, but initially implement only
a simple subset (e.g. that we not implement a multi-bucket memory
manager that takes in 100Mb chunks from the system and performs
sophisticated defragmentation and garbage collection).

Subject to agreement with the IfA, some of the functions proposed
here may be omitted from the initial implementation; in particular
the routines \code{psMemCheckCorruption} and \code{psMemCheckLeaks}
may be hard to build efficiently in a simple implementation based
upon adding extra fields to allocation requests.

\subsubsection{Extra information to be saved by Memory Allocation Functions}

It is required that a table of all allocated memory blocks be
maintained by the \PS{} memory system.

Each allocated block should preserve at least the information present
in the following struct definition:
\begin{verbatim}
  typedef struct {
      const unsigned long id;           // a unique ID for this allocation
      const char *file;                 // set from __FILE__ in e.g. p_psAlloc
      const int lineno;                 // set from __LINE__ in e.g. p_psAlloc
      int refcntr;                      // how many times pointer is referenced
      const void *magic;                // initialised to P_PS_MEMMAGIC
  } psMemBlock;
\end{verbatim}

The value of \code{P_PS_MEMMAGIC} shall be \code{(void *)0xdeadbeef}%
\footnote{Why this choice? Tradition, and because it's easy to notice
  in a hex dump.}

\subsubsection{APIs for using Memory Allocation Functions}

\begin{table}
\begin{verbatim}
void *psAlloc(size_t size);
void *psRealloc(void *ptr, size_t size);
void psFree(void *ptr);

void *p_psAlloc(size_t size, const char *file, int lineno);
void *p_psRealloc(void *ptr, size_t size, const char *file, int lineno);
void p_psFree(void *ptr, const char *file, int lineno);

#define psAlloc(size) p_psAlloc(size, __FILE__, __LINE__)
#define psRealloc(ptr, size) p_psRealloc(ptr, size, __FILE__, __LINE__)
#define psFree(size) p_psFree(size, __FILE__, __LINE__)
\end{verbatim}
\begin{caption}{The APIs required to use the \PS{} memory allocation routines}
  \hlabel{tabUsageAPI}
  The APIs required to use the \PS{} memory allocation routines, and as
  provided by \file{psMemory.h}.
\end{caption}
\end{table}

The types and function prototypes for the part of the memory API
concerned with allocating and freeing memory are given in table
\ref{tabUsageAPI}).

N.b.
\begin{itemize}
\item
  The functions \code{psAlloc}, \code{psRealloc}, and
  \code{psFree} are defined, and are required to be equivalent to
  \code{p_psAlloc}, \code{p_psRealloc}, and \code{p_psFree}
  with the final two arguments \code{"(unknown)"} and \code{0}.

  In the descriptions that follow, I shall not distinguish between the
  functions with and without the \code{p_} prefix.

\item
  Except as specified below, the functions \code{psAlloc},
  \code{psRealloc}, and \code{psFree} have identical semantics
  to the standard C library functins \code{malloc}, \code{realloc},
  and \code{free}.
  
\item
  The file \file{psMemory.h} shall take steps to ensure that
  code calling the functions \code{malloc}, \code{calloc}, \code{realloc},
  or \code{free} shall not compile (\eg{} \code{#define malloc(S) for})
  unless the symbol \code{PS_ALLOC_MALLOC} is defined.

\item
  In all cases, application code will call
  \code{p_\{psAlloc,psRealloc,psFree\}} via the macros defined above.
  
\item
  The functions \code{psAlloc} and \code{psRealloc} shall never
  return a \code{NULL} pointer. If they are unable to provide
  the requested memory they should attempt to obtain the desired
  memory by calling the routine registered by \code{psMemExhaustedSetCB} (see
  subsubsection \ref{secMemAdvanced}), and if still unsuccessful,
  call \code{abort()}.

\item
  The memory management routines shall maintain the field
  \code{psMemBlock.refcntr}. It should be set to \code{1}
  when a block is returned to the user. It is an error to
  attempt to free a block with \code{psMemBlock.refcntr != 1}
  (see subsubsection \ref{secMemRefcounter}).
  
\item
  Where practical and efficient, the memory manager shall call
  the routine registered using the \code{psMemProblemSetCB}
  (see section \ref{secMemAdvanced})
  whenever a corrupted block of memory is discovered. For example,
  doubly-freed blocks can be detected by checking \code{psMemBlock.refcntr}.

\item
  There is no \code{psCalloc} function. Initialisation of data is
  almost always more complex than setting all bytes to 0.
\end{itemize}

\subsubsection{APIs for Tracing and Debugging Memory}
\hlabel{secMemAdvanced}

\begin{table}
\begin{verbatim}
typedef int (*psMemCallback)(const psMemBlock *ptr);
typedef void (*psMemProblemCallback)(const psMemBlock *ptr,
                                     const char *file, int lineno);
typedef void *(*psMemExhaustedCallback)(size_t size);

psMemProblemCallback psMemProblemSetCB(psMemProblemCallback func);
psMemExhaustedCallback psMemExhaustedSetCB(psMemExhaustedCallback func);

psMemCallback psMemAllocateSetCB(psMemCallback func);
psMemCallback psMemFreeSetCB(psMemCallback func);

int psMemGetId(void);                   // get next memory ID

long psMemSetAllocateID(long id);       // set p_psMemAllocateID to id
long psMemSetFreeID(long id);           // set p_psMemFreeID to id

int psMemCheckLeaks(
    int id0,                            // don't list blocks with id < id0
    psMemBlock ***arr,                  // pointer to array of pointers to
                                        //leaked blocks, or NULL
    FILE *fd);                          // print list of leaks to fd (or NULL)
int psMemCheckCorruption(int abort_on_error);
\end{verbatim}
\begin{caption}{The APIs required to use the \PS{} memory allocation routines}
  \hlabel{tabCallbackAPI}
  The APIs required to use the callback and tracing facilities
  in \PS{} memory allocation routines, as defined in \file{psMemory.h}.
\end{caption}
\end{table}

The types and function prototypes for this part of the memory API
are given in table \ref{tabCallbackAPI}.

\subsubsection{Callback Routines}

The four `\code{SetCB}' routines are:

\begin{tabular}{ll|l}
\textbf{type} &  \textbf{Name} & \textbf{Function of callback} \\
psMemProblemCallback & psMemProblemSetCB &
Called when a problem is detected with data being managed on the heap \\
psMemExhaustedCallback & psMemExhaustedSetCB &
Called when \code{psAlloc} is unable to satisfy a memory request. \\
psMemCallback & psMemAllocateSetCB &
Callback is called when the \code{psMemBlock} with a specified ID is
allocated. \\
psMemCallback & psMemFreeSetCB &
Callback is called when the \code{psMemBlock} with a specified ID is
freed. \\
\end{tabular}

N.b.
\begin{itemize}
\item
  In all cases, the `\code{SetCB}' routine takes a pointer to the
  desired callback function, and returns a pointer to the one that was
  previously installed. If the function pointer is \code{NULL}, the
  default callback function is reinstalled.

\item
  The routine installed by \code{psMemExhaustedSetCB} should return
  a pointer to the desired memory or \code{NULL}; in the latter case
  \code{psAlloc} will call \code{abort()}

\item
  \code{psMemGetId} returns the current value of \code{psMemBlock.id}.

\item
  The handler specified by \code{psMemAllocateSetCB} is called just
  before the pointer with \code{psMemBlock.id} equal to
  \code{p_psMemAllocateID} is returned to the user. The variable
  \code{p_psMemAllocateID} should not be set directly in any
  delivered code, \code{psMemSetAllocateID} should be used instead.

\item
  The handler specified by \code{psMemFreeSetCB} is called just
  before the pointer with \code{psMemBlock.id} equal to
  \code{p_psMemFreeID} is freed. The variable
  \code{p_psMemFreeID} should not be set directly in any delivered
  code, \code{psMemSetFreeID} should be used instead.

\item
  The routines \code{psMemSetFreeID} and \code{psMemSetAllocateID}
  accept the desired ID value (see previous two items) and return
  the old value to the user.

\item
  The return values of the handlers installed by \code{psMemAllocateSetCB}
  and \code{psMemFreeSetCB} are used to increment the values of
  \code{p_psMemAllocateID} and \code{p_psMemFreeID} respectively.

  For example, the return value \code{0} implies that the value is unchanged;
  if the value is \code{2} the callback will be called again when the
  memory ID counter has increased by two.
\end{itemize}

\subsubsection{Memory Tracing and Corruption Routines}

The routine \code{psMemCheckLeaks} may be used to check for memory
leaks. The return value is the number of blocks that have been
allocated but not freed.

Only blocks with \code{psMemBlock.id} greater than \code{id0}
are checked; this allows the user to ignore blocks allocated
by initialisation routines.

If the argument \code{arr} is non-\code{NULL}, then upon entering
the call \code{**arr} should be \code{NULL}. Upon return it is set
to an array of \code{psMemBlock *} pointers, one for each block
allocated but not freed.  It is the caller's responsibility to free
this array with \code{psFree}.

If the argument \code{fd} is non\code{NULL}, a one-line summary
of each block that has been allocated but not freed is written to that
file descriptor.

The routine \code{psMemCheckCorruption} checks the entire heap for
corruption, calling the routine registered with
\code{psMemProblemSetCB} for each block detected as being corrupted.
The return value is the number of corrupted blocks detected. If the
argument \code{abort_on_error} is true,
\code{psMemCheckCorruption} shall call \code{abort()} as soon as
memory corruption is detected.

\subsubsection{Reference Counting}
\hlabel{secMemRefcounter}

The memory management routines include a field
\code{psMemBlock.refcntr} which must equal \code{1} whenever
a pointer is presented to \code{psFree}.

The API for this field is:
\begin{verbatim}
int psMemGetRefCounter(void *vptr);        // return refcounter
void *psMemIncrRefCounter(void *vptr);     // increment refcounter and return vptr
void *psMemDecrRefCounter(void *vptr);     // decrement refcounter and return vptr
\end{verbatim}

The functions \code{psMemIncrRefCounter} and \code{psMemDecrRefCounter} shall
return \code{NULL} if passed a \code{NULL} pointer.

\subsubsubsection{Rationale}

\begin{table}
\begin{verbatim}
typedef struct {
    char *name;
    int value;
} psSimple;

psSimple *psSimpleAlloc(const char *name, int val)
{
    psSimple *simp = psAlloc(sizeof(psSimple));
    simp->name = strcpy(psAlloc(strlen(name) + 1), name);
    simp->value = val;

    return simp;
}

void psSimpleFree(psSimple *simp)
{
    if (simp == NULL) { return; }

    if (psMemGetRefCounter(simp) > 1) {
        (void)psMemDecrRefCounter(simp);
        return;
    }
}
\end{verbatim}
\begin{caption}{An example of reference counting}
  \hlabel{tabReferenceCounting}
  An example of using reference counting
\end{caption}
\end{table}

The \code{psMemBlock.refcounter} is clearly useful for detecting
attempts to free memory that is already free.  A more complex
application is for allowing pointers to complex data-objects (e.g.
images) to appear in more than one data structure simultaneously
(see table \ref{tabReferenceCounting}).

Because of the use of the \code{refcounter} field, we can safely put items of
this type onto many lists:
\goodbreak
\begin{verbatim}
simp = psSimpleAlloc("RHL", 0);
psDlistAppend(list1, psMemIncrRefCounter(simp));
psDlistAppend(list2, psMemIncrRefCounter(simp));
psSimpleFree(simp);
\end{verbatim}

(Note: in fact there is no need to explicitly increment the counter
in this case, as the \code{psDlistAppend} (section \ref{psDlist})
API specifies that it
does it for you.)

\section{Tracing and Logging}

This document defines the \PS{} Tracing and Logging APIs; the former
refers to debug information that we wish to be able to turn on and off
without recompiling (although it will \emph{not} be available in
production code); the latter means information about the processing
that must be collected and saved, even in the production system.

We envision that we will make extensive use of \code{psTrace} throughout
the \PS{} code.

\subsection{Tracing APIs}
\hlabel{psTrace}

\begin{table}
  \begin{verbatim}
#if defined(PS_NTRACE)
#  define psTrace(facil, level, ...) /* do nothing */
#else
#  define psTrace(facil, level, ...) \
          p_psTrace(facil, level, __VA_ARGS__)
#endif

void p_psTrace(const char *facil, int level, ...);

int psSetTraceLevel(const char *facil,  // facilty of interest
                    int level);         // desired trace level
int psGetTraceLevel(const char *name);  // facilty of interest

void psTraceReset(void);		// turn off all tracing, and free trace's allocated memory

void psPrintTraceLevels(void);          // print trace levels
  \end{verbatim}
  \begin{caption}{The public API for the trace facility
      from \file{psTrace.h}.}
    \hlabel{tabTraceAPI}
  \end{caption}
\end{table}

The public API for the trace facility (table \ref{tabTraceAPI})
should be provided in a header file \file{psTrace.h} which
is included by \file{psUtils.h}.

\begin{itemize}
  \item
    Logging is provided by the function \code{psTrace},
    which is actually a macro.  When the macro \code{PS_NTRACE}
    is defined, all occurrences of  \code{psTrace} shall
    be replaced by whitespace.

  \item
    The first argument to \code{psTrace} is a name of the form
    \code{aaa.bbb.ccc}. The second is an integer,
    \code{level}. The remaining arguments are a printf-style format
    and a (possibly empty) set of values for that formatting
    string. When this trace is active, \code{psTrace} shall generate
    the requested output on \code{stdout}, preceded by \code{level}
    spaces.

  \item
    The call \code{psSetTraceLevel(name, level)} shall set the trace
    level for \code{name} to \code{level}.

  \item
    The call \code{psGetTraceLevel(name)} shall return the level
    associated with \code{name}.  If \code{name} has not been
    associated with a level, the routine shall remove the \textit{last}
    element of \code{name} and attempt to look up its level; this
    procedure shall be applied recursively until the name is reduced
    to \code{""}; if this name has no level associated with
    it, then the value \code{0} shall be returned (see examples
    below).

    \item
      The call \code{psTrace(name, level, ...)}
      shall print the message if and only if
      \code{psGetTraceLevel(name)} returns a value greater than
      or equal to \code{level}.

    \item
      \code{psPrintTraceLevels} shall print a listing of all
      declared levels, displayed as a hierarchy with sub-components
      sorted within each component (see examples below).

      Note in particular that the root of the tree, the name \code{""}
      should print as \code{(root)}, and nodes which have not
      been assigned a value should list their level as \code{.}.

    \item
      All of the tracing facilities shall be SWIGed, with the exception
      of \code{p_psTrace}.

    \item
      There is no requirement that \code{psTrace} be usable from
      within the functions that implement \file{psTrace.h}
      or \file{psMemory.h} systems.

    \item
      \code{psTraceReset} shall reset all tracing to the state that it
      had at program initiation, including freeing any memory that the
      tracing subsystem may have allocated.
\end{itemize}

\subsubsection{Examples of the use of Tracing Facilities}

For example, after the commands:
\begin{verbatim}
    psSetTraceLevel("utils.dlist.add.head", 9);
    psSetTraceLevel("utils.dlist.add", 3);
    psSetTraceLevel("utils.dlist.remove", 4);
    psSetTraceLevel("coadd", 2);
    psSetTraceLevel("coadd.CR.remove.morphology", 5);
    psSetTraceLevel("utils.hash", 2);
    psSetTraceLevel("utils.dlist.add", 9);
    psSetTraceLevel("utils", 1);
\end{verbatim}
the command \code{psPrintTraceLevels()} should print:
\begin{verbatim}
(root)               0
 utils               1
  hash               2
  dlist              .
   remove            4
   add               9
    head             9
 coadd               2
  CR                 .
   remove            .
    morphology       5
\end{verbatim}
where \code{.} means that the trace level should be inherited from its parent.

After this set of \code{psSetTraceLevel} commands, and if
\code{PS_NTRACE} is not defined, the following commands
\begin{verbatim}
    psTrace("utils.dlist.remove", 2, "Removing psDList key \"%s\"\n", "my_key");
    psTrace("utils", 2, "Initialising utilities library\n");
    psTrace("", 2, "This is turned on by trace component \"\"");
    psTrace("utils.dlist", 2, "Initialising psDList\n");
    psTrace("utils.dlist.remove", 4, "Removing psDList key \"%s\" (value: \"%d\")\n", "my_key", 12345);
    psTrace("utils.hash.remove", 4, "Removing hash key \"%s\" (value: \"%d\")\n", "my_key", 12345);
    psTrace("utils.dlist.add", 1, "Adding psDList key \"%s\"\n", "your_key");
    psTrace("utils.dlist.find", 2, "Looking up psDList key \"%s\"\n", "some_key");
    psTrace("coadd.CR.remove", 4, "Removing CRs\n");
    psTrace("coadd.CR.remove.morphology", 4, "CRs are not fuzzy\n");
\end{verbatim}
should produce this output:
\begin{verbatim}
  Removing psDList key "my_key"
    Removing psDList key "my_key" (value: "12345")
 Adding psDList key "your_key"
    CRs are not fuzzy
\end{verbatim}

Note that
\begin{description}
\item
  \code{utils.dlist} messages are at level 1, inherited from \code{utils}, so the
  \code{Initialising utilities library}, \code{Initialising psDList}, and
  \code{Looking up psDList key} messages are \emph{not} printed (the traces are at level 2).

\item
  \code{utils.dlist.remove} messages are at level 4, and are printed.

\item
  \code{utils.hash} messages are at level 2, and are not printed (the traces are at level 4)

\item
  \code{coadd.CR.remove} is at level 2 (inherited from \code{coadd}) so \code{Removing CRs}
  isn't printed.  \code{coadd.CR.remove.morphology} is at level 4, so \code{CRs are not fuzzy} is printed.
\end{description}

\subsection{Message Logging}
\hlabel{psLogMsg}

\begin{table}
  \begin{verbatim}
enum { PS_LOG_ABORT = 0, PS_LOG_ERROR, PS_LOG_WARN, PS_LOG_INFO };

enum { PS_LOG_TO_STDERR, PS_LOG_TO_STDOUT };

void psLogMsg(const char *name, int level, const char *fmt, ...);
void p_psVLogMsg(const char *name, int level, const char *fmt, va_list ap);

int psSetLogDestination(int dest);
void psSetLogFormat(const char *fmt);

int psSetLogLevel(int level);
  \end{verbatim}
  \begin{caption}{API for message logging}
    \hlabel{tabLogMsgAPI}
    The API for message logging.
  \end{caption}
\end{table}

The public API for the logging facility (table \ref{tabLogMsgAPI})
should be provided in a header file \file{psLogMsg.h} which
is included by \file{psUtils.h}.

The function \code{psSetLogLevel} may be used to set the current
level of logging; the previous value is returned.
The default value is \code{PS_LOG_INFO}. Valid values are 0---9
inclusive (note that only the first four are required to have
symbolic names).

A call to \code{psLogMsg(name, level, msg, ...)} shall generate
a log message if \code{level} is less than or equal to the
value most recently set using \code{psSetLogLevel}. The function
\code{p_psLogMsg} is identical, except that it expects a
final \code{va_list} argument.

The format of the log message shall be of the form:
\begin{verbatim}
YYYY:MM:DD hh:mm:ssZ|hostname|l|name            |msg
\end{verbatim}
\code{YYYY}, \code{MM}, \code{DD}, \code{hh}, \code{mm}, and \code{ss}
are the year, month (Jan == 1), day of the month, hours (0--23),
minutes, and seconds when the log message was received.  Note that the
timestamp is in ISO order, and that the timezone is GMT (hence the
\code{Z}).

The \code{hostname} is returned by \code{gethostname}, \code{l} is a
letter associated with the level (\code{A}, \code{E}, \code{W}, and
\code{I} for \code{PS_LOG_ABORT}, \code{PS_LOG_ERROR}, \code{PS_LOG_WARN},
and \code{PS_LOG_INFO} respectively. Other levels are represented
numerically (\code{5} etc.). The other two field, \code{name} and
\code{msg} are arguments to \code{psLogMsg}; note that \code{name} has
a fixed width of 15 characters. If \code{msg} doesn't end in a newline,
a single newline is emitted to terminate the message.

An example message is:
\begin{verbatim}
2004:02:24 20:14:18Z|alibaba.IfA.Hawaii.Edu|I|utils          |Hello World
\end{verbatim}

Log messages are sent to the destination most recently set using
\code{psSetLogDestination}.  The only two values that are initially
defined are \code{PS_LOG_TO_STDERR} and \code{PS_LOG_TO_STDOUT} to
write to \code{stderr} and \code{stdout} respectively.

The fields included in the log message may be controlled using \code{psSetLogFormat} which
expects a string consisting of the letters \code{H} (host), \code{L} (level), \code{M} (message),
\code{N} (name), and \code{T} (time).  The default is \code{HLMNT}.

\section{The Pan-STARRS \texttt{psDlist} doubly-linked list type}
\hlabel{psDlist}

Pan-STARRS supports doubly linked lists through a type \code{psDlist}.
The type is defined in the header file \file{psDlist.h}, and consists
of the following definitions:

\begin{verbatim}
typedef struct psDlistElem {
    struct psDlistElem *prev;           // previous link in list
    struct psDlistElem *next;           // next link in list
    void *data;                         // real data item
} psDlistElem;

typedef struct {
    int n;                              // number of elements on list
    psDlistElem *head;                  // first element on list (may be NULL)
    psDlistElem *tail;                  // last element on list (may be NULL)
    psDlistElem *iter;                  // iteration cursor; private
} psDlist;

enum {                                  // Special values of index into list
    psDlistHead = 0,                    // at head
    psDlistTail = -1,                   // at tail
    psDlistUnknown = -2,                // unknown position
    psDlistPrev = -3,                   // previous element
    psDlistNext = -4                    // next element
};
\end{verbatim}

The API is:

\begin{verbatim}
psDlist *psDlistAlloc(void *data);        // initial data item; may be NULL

void psDlistFree(psDlist *list,          // list to destroy
                void (*elemFree)(void *)); // destructor for list data, or NULL

/*
 * List maintainence functions
 */
psDlist *psDlistAdd(psDlist *list,      // list to add to (may be NULL)
                    void *data,         // data item to add
                    int where);         // index, psDlistHead, or psDlistTail
psDlist *psDlistAppend(psDlist *list,   // list to append to (may be NULL)
                       void *data);     // data item to add
void *psDlistRemove(psDlist *list,      // list to remove element from
                    void *data,         // data item to remove
                    int which);         // index of item, or psDlistUnknown,
                                        // or psDlistNext, or psDlistPrev
void *psDlistGet(const psDlist *list,   // list to retrieve element from
                 int which);            // index of item, or psDlistNext,
                                        // or psDlistPrev
/*
 * Conversions to/from arrays
 */
psVoidPtrArray *psDlistToArray(psDlist *dlist);
psDlist *psArrayToDlist(psVoidPtrArray *arr);
\end{verbatim}

All data items placed onto lists (e.g. with \code{psDlistAdd})
shall have their reference counters (section \ref{secMemRefcounter}) incremented.
When elements
are removed from a list with \code{psDlistRemove}, they shall
have their reference counters decremented. The action of retrieving
data from a list (with \code{psDlistGet}) shall not affect
their reference counter.

If \code{psDlistFree}'s argument \code{elemFree} is NULL, the
list should be deleted, but not the elements on it (although their
\code{refcounter}'s should be decremented).

Iteration over all elements of the list is provided by the functions:
\begin{verbatim}
void psDlistSetIterator(psDlist *list, int where, int which);
void *psDlistGetNext(psDlist *list, int which);
void *psDlistGetPrev(psDlist *list, int which);
\end{verbatim}
in which the \code{where} argument must be \code{PS_DLIST_HEAD} or \code{PS_DLIST_TAIL},
to start at the head or tail of the list, and \code{psDlistGetNext} and \code{psDlistGetPrev}
return the next/previous element. The argument \code{which} identifies which of potentially
many iteration cursors should be used; it must currently always be \code{0}.

Explicit traversal of the list using the \code{psDlistElem}'s
\code{prev} and \code{next} pointers is also supported.

The routines to convert to and from \code{psVoidPtrArray}s,
\code{psDlistToArray} and \code{psArrayToDlist} shall ensure that the
objects on the arrays and lists have had their reference pointers
correctly incremented (see section \ref{secArrayVoidPtr}) (\eg{} that
\code{psArrayToDlist(psDlistToArray(list))} returns a properly-formed
\code{psDlist}).

\section{The \PS{} Array types}

\begin{table}
  \begin{verbatim}
  \end{verbatim}
  \begin{caption}{The array creation macros defined in \file{psArray.h}}
    \hlabel{tabPsArray}
  \end{caption}
\end{table}

\subsection{Arrays of Simple Types}

Any \PS/ datatype \code{psType} may be associated with an array type
\code{psTypeArray}:
\begin{verbatim}
typedef struct {
  int size;
  int n;
  psType *arr;
} psTypeArray;
\end{verbatim}
with associated constructors and a destructor:
\begin{verbatim}
psTypeArray *psTypeAlloc(int n, int size);
psTypeArray *psTypeRealloc(psTypeArray *arr, int n);
void psTypeFree(psTypeArray *arr);  
\end{verbatim}

The argument \code{n} is the dimension of the array; \code{size}
is the number of elements allocated ($s \ge n$).

This type and functions may be declared and defined using two macros
from \file{psArray.h} (table \ref{tabPsArray}),
\code{PS_DECLARE_ARRAY_TYPE(psType)} and
\code{PS_CREATE_ARRAY_TYPE(psType)}.  The former defines the typedef
and declares the prototypes (and is thus suitable for use in a
header file); the latter generates the code for the three functions
\code{psType(Alloc|Realloc|Free} (and should thus appear in exactly one
source file for a given type).

The \code{psType} should be a single word (e.g. \code{psXY}); in particular,
there is no requirement to support a pointer type (\eg{} \code{psXY *});
see next section.

\subsection{Arrays of Pointer Types}

The data type created with \code{PS_CREATE_ARRAY_TYPE} (\code{psType})
contains an array of \code{psType}s not
pointers to \code{psType}s; this means that the individual elements are
not allocated using \code{psTypeAlloc}, are not correctly initialized,
and shouldn't be individually deleted with \code{psTypeFree};

If you wish to use arrays of pointers, use the macros
\code{PS_DECLARE_ARRAY_PTR_TYPE(psType)} and
\code{PS_CREATE_ARRAY_PTR_TYPE(psType)} (table \ref{tabPsArray}). These
create types \code{typedef psType *psTypePtr} and \code{psTypePtrArray}:
\begin{verbatim}
typedef struct {
  int size;
  int n;
  psTypePtr *arr;
} psTypePtrArray;
\end{verbatim}
with associated constructors and a destructor:
\begin{verbatim}
psTypePtrArray *psTypePtrAlloc(int n, int size);
psTypePtrArray *psTypePtrRealloc(psTypePtrArray *arr, int n);
void psTypePtrArrayFree(psTypePtrArray *arr);  
\end{verbatim}

These constructors create arrays of \code{psType *} and call
\code{psTypeAlloc} and \code{psTypeFree} to allocate and free the
elements. As for the simple arrays, The former defines the typedef and
declares the prototypes (and is thus suitable for use in a header
file) and the latter generates the code for the three functions
\code{psType(Alloc|Realloc|Free} (and should thus appear in exactly one
source file for a given type).

The objects pointed to by these types have had their \code{refCounter}s
incremented (see \ref{secMemRefcounter}); to remove an element from the array you
need to say something like:
\begin{verbatim}
  psTypePtrArray *pt = psTypePtrArrayAlloc(10, 10);
  psType *xy = psMemDecrRefCounter(pt->arr[0]);
  pt->arr[0] = NULL;
\end{verbatim}

\subsubsection{Arrays of \texttt{void *}}
\hlabel{secArrayVoidPtr}

Arrays of \code{void *} are different, as the need an explicitly-specified
destructor.

\file{psArray.h} shall specify a type \code{psVoidPtrArray} that
behaves in all respects as if it had been created with:
\begin{verbatim}
typedef void *psVoidPtr;
PS_DECLARE_ARRAY_TYPE(psVoidPtr);
PS_CREATE_ARRAY_TYPE(psVoidPtr);
\end{verbatim}
except that its destructor is specified as:
\begin{verbatim}
void psVoidPtrArrayFree(psVoidPtrArray *arr,      // array to destroy
                       void (*elemFree)(void *)); // destructor for array data
\end{verbatim}

The routine \code{psVoidPtrArrayFree} assumes that all pointers
had their reference counters incremented
when they were inserted onto the array.\footnote{%
  \eg{} \code{va->arr[i] = psMemIncrRefCounter(ptr);}}

If \code{psVoidPtrArrayFree}'s argument \code{elemFree} is NULL, the
list should be deleted, but not the elements on it (although their
\code{refcounter}'s should be decremented).

\subsection{Examples of Array Types}

The following is a complete C program that illustrates the use of
\code{array}s.
\begin{verbatim}
#include "psUtils.h"

typedef struct {
    int x, y;
} psXY;

psXY *psXYAlloc(void)
{
    return psAlloc(sizeof(psXY));
}

void psXYFree(psXY *xy)
{
    psFree(xy);
}

PS_DECLARE_ARRAY_TYPE(psXY);
PS_CREATE_ARRAY_TYPE(psXY);

PS_DECLARE_ARRAY_PTR_TYPE(psXY);
PS_CREATE_ARRAY_PTR_TYPE(psXY);

int main(void)
{
    psXYArray *t = psXYArrayAlloc(10, 15);
    psXYPtrArray *pt = psXYPtrArrayAlloc(10, 10);

    for (int i = 0; i < t->n; i++) {
	t->arr[i].x = i;
	pt->arr[i]->y = 10*i;
    }

    t = psXYArrayRealloc(t, 5);
    t = psXYArrayRealloc(t, 8);

    for (int i = 0; i < t->n; i++) {
	printf("%d %d  ", t->arr[i].x, pt->arr[i]->y);
    }
    printf("\n");
    
    psXYArrayFree(t);

    psXY *xy = psMemDecrRefCounter(pt->arr[0]);
    pt->arr[0] = NULL;
    psXYFree(xy);    
    
    psXYPtrArrayFree(pt);

    psMemCheckLeaks(0, NULL, stderr);

    return 0;
}
\end{verbatim}

\section{Hash Tables}
\hlabel{psHash}

\begin{table}
  \begin{verbatim}
typedef struct HashTable psHash;

psHash *psHashAlloc(int nbucket);       // initial number of buckets
void psHashFree(psHash *table,          // hash table to be freed
               void (*itemFree)(void *item)); // how to free hashed data;
                                        // or NULL

void *psHashInsert(psHash *table,       // table to insert in
                   const char *key,     // key to use
                   void *data,          // data to insert
                   void (*itemFree)(void *item)); // how to free hashed data;
                                        // or NULL
void *psHashLookup(psHash *table,       // table to lookup key in
                   const char *key);    // key to lookup

void *psHashRemove(psHash *table,       // table to lookup key in
                   const char *key);    // key to lookup
  \end{verbatim}
  \begin{caption}{The public API for hash tables from \file{psHash.h}}
    \hlabel{tabPsHash}
  \end{caption}
\end{table}

The public API for the hash table (table \ref{tabPsHash})
should be provided in a header file \file{psHash.h} which
is included by \file{psUtils.h}.
\footnote{
  We choose not to use the posix function \code{hcreate},
  \code{hdestroy}, and \code{hsearch} as they only support
  a single hash table at any one time.}

A hash table is an abstract type \code{psHash}.  The argument
\code{nbucket} to \code{psHashAlloc} is a non-binding suggestion
from the user for the initial size of the hash table.

If the \code{itemFree} argument to \code{psHashFree} is non-NULL,
it will be used to delete the data items that have been stored
in the hash table; if it is NULL this is the responsibility of
the caller.

The routine \code{psHashInsert} must provide a non-NULL \code{itemFree}
argument if it wishes to change the value previously inserted keys;
if \code{itemFree} is NULL attempting to insert a pre-existing key
is an error, and the routine will return NULL.  If  \code{psHashInsert}
succeeds it returns \code{data}.

\code{psHashLookup} returns the \code{data} associated with the
key, or NULL if the key's invalid.

\code{psHashRemove} removes the entry associated with the
key from the table, and returns the \code{data}; if the key's invalid it returns NULL.

\section{Miscellaneous Utilities}

The API for miscellaneous \PS{} utilities is provided by \file{psMisc.h}
which shall be included by \file{psUtils.h}.

\begin{table}
  \begin{verbatim}
#define PS_CONCAT(A, B) A ## B          // Expands to AB
#define PS_CONCAT2(A, B) PS_CONCAT(A, B) // Also expands to AB
#define PS_CONCAT3(A, B, C) A ## B ## C // Expands to ABC

#define PS_STRING(S) #S                 // converts argument S to string
    
void psAbort(const char *name, const char *fmt, ...);
void psError(const char *name, const char *fmt, ...);
char *psStringCopy(const char *str);
  \end{verbatim}
  \begin{caption}{The utilities provided by \file{psMisc.h}}
      \hlabel{psMisc}
  \end{caption}
\end{table}

\code{psAbort} shall call \code{psLogMsg} with a level of \code{PS_LOG_ABORT},
and then call \code{abort}.
\code{psError} shall call \code{psLogMsg} with a level of \code{PS_LOG_ERROR},
and then return.
In cases of doubt, a good choice for
\code{name} is \code{__func__}.

\code{psStringCopy} shall allocate and return a copy of the input string.


\bibliographystyle{plain}
\bibliography{panstarrs}



\end{document}
