Context Navigation

← Previous Changeset
Next Changeset →

Changeset 4239

Timestamp:

Jun 13, 2005, 12:41:59 PM (21 years ago)

Author:

Paul Price

Message:

Reorganised

Location:

trunk/doc/pslib

Files:

: 2 edited

ChangeLogSDRS.tex (modified) (2 diffs)
psLibSDRS.tex (modified) (22 diffs)

Legend:

: Unmodified
: Added
: Removed

trunk/doc/pslib/ChangeLogSDRS.tex

-              r4208
+              r4239
 %%% $Id: ChangeLogSDRS.tex,v 1.135 2005-06-10 03:56:03 price Exp $
+%%% $Id: ChangeLogSDRS.tex,v 1.136 2005-06-13 22:41:59 price Exp $
 \subsection{Changes from version 00 to version 01}
 …
 \item Updating section on thread safety, and added \code{psMutex}.
 \item add \code{psFitsOpenFD()}
+\end{itemize}
+\item Removed example destructor function, since the current
+  implementation does not follow it, but achieves the same result.
+\item Reorganised document: collections and mathematical structures
+  are now separate sections; metadata, pixels lists and bit sets are
+  collections; type information goes into system utilities.
+\end{itemize}

trunk/doc/pslib/psLibSDRS.tex

-              r4208
+              r4239
 %%% $Id: psLibSDRS.tex,v 1.274 2005-06-10 03:56:03 price Exp $
+%%% $Id: psLibSDRS.tex,v 1.275 2005-06-13 22:41:59 price Exp $
 \documentclass[panstarrs,spec]{panstarrs}
 …
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \section{Introduction}
+\section{Introduction and policies}
 This document describes the Pan-STARRS Image Processing Pipeline (IPP)
 …
 memory management functions).
 \subsection{Conventions}
+\subsection{Angles}
 To maintain consistency throughout the library, angles shall be
 …
 \end{prototype}
+%
 The corresponding callbacks have the following form:
+The corresponding callback functions have the following form:
+%
 \begin{datatype}
 typedef psMemId (*psMemAllocCallback)(const psMemBlock *ptr);
+\end{datatype}
+typedef psMemId (*psMemFreeCallback)(const psMemBlock *ptr);
+\end{datatype}
+and are set with the following functions:
 \begin{prototype}
 psMemAllocCallback psMemAllocCallbackSet(psMemAllocCallback func);
-\end{prototype}
-\begin{datatype}
-typedef psMemId (*psMemFreeCallback)(const psMemBlock *ptr);
-\end{datatype}
-\begin{prototype}
 psMemFreeCallback psMemFreeCallbackSet(psMemFreeCallback func);
 psMemId psMemGetId(void);
 …
 corresponding constructors and destructors.  The destructors are
 private functions used only by the memory management system.
 Instances of, for example, \code{psMyType} should be constructed using
 \code{psMyTypeAlloc()} calls, and are destroyed using the basic
 \code{psFree} function, which calls \code{psMyTypeFree()} to free the
+Instances of, for example, \code{psSomeType} should be constructed using
+\code{psSomeTypeAlloc()} calls, and are destroyed using the basic
+\code{psFree} function, which calls \code{p_psSomeTypeFree()} to free the
 components of the structure, but leaves the task of freeing the
 structure to \code{psFree}.  The allocator will allocate the required
 …
 The existence of complicated structures which include pointers to
 other structures require that we lay out a rule regarding destructors
+(i.e., \code{psMyTypeFree}) and reference counters.  Simply put,
+\textit{the destructor for every structure should only call
+\code{psFree} if \code{refCounter == 1}; otherwise, it decrements the
+reference counter and returns.}  An example destructor is shown below:
+\filbreak
+\begin{verbatim}
+void psMyTypeFree(psMyType *myType)
+{
+    /* data is not defined */
+    if (psMemGetRefCounter(myType) < 1) {
+        return;
+    }
+    /* Only call psFree if reference counter is 1 */
+    if (psMemGetRefCounter(myType) == 1) {
+        psSubFree (myType->sub);
+        psFree(myType);
+        return;
+    }
+    /* Otherwise, decrement the reference counter only */
+    psMemDecrRefCounter(myType);
+}
+\end{verbatim}
+Note that the element of \code{myType}, \code{myType.sub} is
+explicitly freed with its associated destructor.  If this element
+points to a data block with multiple references, this call would only
+decrement the counter.
+\subsection{Conventions adopted}
+Only pointers allocated with the PSLib memory functions are compatible
+with the various PSLib container types (e.g., \code{psList,
+and reference counters.  Simply put, \textit{the destructor for every
+structure should only free the structure if the \code{refCounter ==
+}; otherwise, it decrements the reference counter and returns.}
+\subsubsection{Conventions adopted for pointers}
+Only pointers to memory allocated with the PSLib memory functions are
+compatible with the various PSLib container types (e.g., \code{psList,
 psMetadata}), because the functions working with the container types
 search for the attached \code{psMemBlock}.  If a pointer allocated
+with another memory system (e.g., the system \code{malloc}), or
+generated by offsetting from another pointer that was allocated with
+\code{psAlloc}, is used with PSLib, the PSLib functions would falsely
 determine that memory is corrupted, because of the missing
+search for the attached \code{psMemBlock}.  If a pointer to memory
+allocated with another memory system (e.g., the system \code{malloc}),
+or generated by offsetting from another pointer that was allocated
+with \code{psAlloc}, is used with PSLib, the PSLib functions would
+falsely determine that memory is corrupted, because of the missing
 \code{psMemBlock}.
 To pilot our way through the potential confusion, instead of calling
 all pointers (of unspecified type) a ``\code{void*}'', we adopt a
 convention, both in this document and in the source, of referring to a
+pointer that has a \code{psMemBlock} attached as a \code{psPtr}:
+convention, both in this document and to be used in the source, of
+referring to a pointer that has a \code{psMemBlock} attached as a
+\code{psPtr}:
 \begin{datatype}
 typedef void* psPtr;
 \end{dataType}
+\end{datatype}
 For the same reason, we also adopt a convention of referring to a string
 that has a \code{psMemBlock} attached as a \code{psString}:
 \begin{datatype}
 typedef char* psString;
 …
 \code{psStringCopy} or \code{psStringNCopy}).
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Threads}
+As pointed out earlier, PSLib makes no guarantees for thread-safety
+outside of the memory management functions.  Nevertheless, the following
+facilities are provided as a convenience to the user.
+Each of the data structures classified as a ``collection'' (i.e.,
+\code{psList, psHash, psMetadata, psArray, psPixels, psVector,
+psBitSet}) and \code{psImage} shall contain an additional member,
+\code{void *lock}, which provides a place for the user to carry around
+a mutex or semaphore.  This is provided so that the user doesn't have
+to pass around both the structure and a mutex, or wrap PSLib
+structures in their own thread-safe structures that contain a mutex.
+We also define the following conveniences:
+\begin{datatype}
+typedef struct {
+    pthread_mutex_t mutex;
+} psMutex;
+\end{datatype}
+\begin{prototype}
+psMutex *psMutexAlloc(void);
+bool psMutexLock(psMutex *mutex);
+bool psMutexUnlock(psMutex *mutex);
+\end{prototype}
+\code{psMutex} simply wraps a POSIX thread mutex (this is necessary in
+order to use the PS memory management system).
+\code{psMutexAlloc} shall allocate memory for a \code{psMutex}, and
+initialise the mutex.  \code{psMutexLock} shall lock the mutex in
+\code{thread}, and \code{psMutexUnlock} shall unlock the mutex in
+\code{thread}.  No distinction is made between read and write locks.
+These functions, in the interests of speed, should be implemented as
+preprocessor macros.
+These functions should only be defined if \code{_REENTRANT} is
+defined, and poisoned otherwise.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Tracing and Logging}
+This section 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 (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
+extensive use will be made of \code{psTrace} throughout the \PS{}
+code.
+\subsubsection{Tracing APIs}
+\hlabel{psTrace}
+A code-tracing facility should allow the programmer to place messages
+in the code which, when called, will print some useful information
+about the containing block of code.  Ideally, different messages may
+be specified to have different levels (of severity or interest).  For
+a given run of the program, the level of interest should be set to
+provide more or less feedback, depending on the needs of the
+programmer.  In a typical situation, low-level messages would be
+placed generously throughout the code, indicating the flow of the
+program.  Higher-level messages would be placed in a limited number of
+special locations, such as the start of major code segments or where a
+particularly unusual condition is met.  Top-level messages would be
+placed in code triggered under serious error conditions.  A normal run
+of the program would have the trace messages printed only for the
+top-level.  If the user needs to dig deeper into the code, the trace
+level should be set lower, and the more detailed messages could be
+examined.  In a case of a serious, poorly-understood problem with the
+code, the trace threshold would be placed to the bottom and the
+lowest-level step-by-step messages would be printed.
+The PSLib tracing facility provides the above functionality, along
+with the ability to assign different trace levels to messages from
+different software components.  Each trace message, when placed in the
+code, is assigned to be part of a specific tracing 'facility', defined
+in more detail below.  The trace level for that specific message is
+also set when the message is placed.  Each facility may have its trace
+level set independently.  Thus, it is possible to request detailed
+trace output for one facility while minimizing the verbosity of the
+trace output from the rest of the program.
+The trace facilities consist of a hierarchy of names.  A trace
+facility is defined by a string consisting of words separated by dots,
+with a hierarchy equivalent to that of UNIX directory names.  The
+top-level facility is simply \code{'.'} (one dot).  The next level
+would be \code{'.A'}, followed by \code{.A.B}, and so on.  The
+relationship is seen in two ways.  First, a facility inherits the
+trace level of its parent unless explicitly specified.  Second, the
+hierarchy is used to format the listing of the trace facilities so
+that they are easy to read.  The first of these rules provides a
+mechanism to define the default trace levels for any facility even if
+it has not been registered explicitly since all named facilities are
+implicitly children of the top level facility (\code{.}).  The second
+rule is simply an organizational technique to make the listing of
+facility information clear.  In specifying a facility, the leading
+dot shall be optional, as a convenience to the user.
+The API to place a trace message in the code, and simultaneously set
+its trace level and facility, is:
+%
+\begin{prototype}
+void psTrace(const char *facil, int level, const char *fmt,...);
+void psTraceV(const char *facil, int level, const char *fmt, va_list ap);
+\end{prototype}
+%
+where the \code{fmt} argument is a printf-style formatting code
+followed by possible arguments to that formatting statement, to be
+implemented using the \code{vprintf} functions.  This command
+specifies the name of the facility to which the message belongs
+(\code{facil}), the trace level for this message in that facility
+(\code{level}) and the message itself.  The \code{psTraceV} version of
+the command accepts a \code{va_list} argument list rather than a
+variable number of arguments.
+The trace level for any facility may be set at any time with the
+following function:
+%
+\begin{prototype}
+int psTraceSetLevel(const char *facil, int level);
+\end{prototype}
+%
+where \code{level} specifies the current trace level for the facility
+named by \code{facil}.  The currently defined trace level for a given
+facility may be determined by the function:
+%
+\begin{prototype}
+int psTraceGetLevel(const char *facil);
+\end{prototype}
+%
+which returns the trace level of the named facility following the
+rules specified above.  A specified trace message (identified by
+\code{psTrace}) must be printed if and only if
+\code{psTraceGetLevel(facil)} returns a value greater than or equal to
+the value of \code{level} for that message.  That is, a larger
+number for the trace level corresponds to lower-level statements, and
+hence is more verbose.
+PSLib includes a utility function for examining the current tracing
+levels of all facilities:
+%
+\begin{prototype}
+void psTracePrintLevels(void);
+\end{prototype}
+%
+This function prints the hierarchy of trace facilities along with the
+current trace level for each facility.  For example, a particular
+program may have a few facilities defined, along with their trace
+levels.  A call to \code{psTracePrintLevels} may produce a listing
+which appears as:
+\begin{verbatim}
+.                        0
+ .IPP                    0
+ .IPP.debias             1
+ .IPP.flatten            1
+  .IPP.flatten.divide    2
+  .IPP.object.findpeak   1
+  .IPP.object.getsky     1
+\end{verbatim}
+Considering the same program, the programmer might place a variety of
+trace messages throughout the \code{flatten} portion of the code with
+different types of messages, such as:
+%
+\begin{verbatim}
+psTrace("IPP.flatten", 2, "starting flatten function\n");
+psTrace("IPP.flatten", 0, "flat-field image is \%s\n", filename);
+psTrace("IPP.flatten.divide", 2, "doing the divide\n");
+psTrace("IPP.flatten.divide", 3, "trying the loop, i = \%d\n", i);
+psTrace("IPP.flatten.divide", 1, "got an invalid pixel value (NaN) at \%d,\%d\n");
+psTrace("IPP.flatten.divide", 2, "divide is done\n");
+\end{verbatim}
+%
+Under the trace levels set above, if the code actually reached each of
+these trace messages, the following messages would be printed:
+%
+\begin{verbatim}
+flat-field image is foo.fits
+  doing the divide
+  got an invalid pixel value (NaN) at 500,20
+  divide is done
+\end{verbatim}
+%
+while these two would not be printed because their facility level was
+too low:
+%
+\begin{verbatim}
+  starting flatten function
+   trying the loop, i = 0
+   trying the loop, i = 1
+   trying the loop, i = 2
+...
+\end{verbatim}
+%
+The availability of the tracing facility at run-time, must be decided
+at compilation: If the C pre-processor macro \code{PS_NO_TRACE} is
+defined, all trace code must be replaced by empty space so that none
+of the code is compiled.  This can be implemented via macro front-ends
+to private versions of the user APIs.  In addition, a function
+\code{bool psTraceReset(void)} will free memory used by \code{psTrace}
+functions, effectively resetting all trace levels to 0.
+The trace may optionally be written to a file or other output
+destination with \code{psTraceSetDestination}:
+\begin{prototype}
+void psTraceSetDestination(int fd);
+\end{prototype}
+If the \code{fd} is 0, then the trace is sent to standard output,
+otherwise it is sent to the specified file descriptor.  A call to
+\code{psTraceSetDestination} automatically closes the file descriptor.
+The corresponding function
+\begin{prototype}
+int psTraceGetDestination();
+\end{prototype}
+returns the current trace destination file descriptor.  If the
+destination has not been defined by the user, the descriptor for
+\code{stdout} is returned.
+The trace output format is controlled with the function:
+%
+\begin{prototype}
+bool psTraceSetFormat(const char *fmt);
+\end{prototype}
+%
+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{THLNM}, which produces trace messages in
+the form:
+\begin{verbatim}
+YYYY-MM-DD hh:mm:ssZ | hostname | L | name
+    The message goes here
+    and is indented by 4 spaces.
+\end{verbatim}
+where \code{YYYY}, \code{MM}, \code{DD}, \code{hh}, \code{mm}, and
+\code{ss} are the year, month (Jan is 01), day of the month, hours
+(0--23), minutes, and seconds when the trace 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 character 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 fields, \code{facil} and \code{msg}, are the
+arguments to \code{psTrace}.  The \code{msg} is placed on a new line
+(allowing the \code{name} to fill the rest of the previous line),
+with each line indented by 4 spaces.  An example message is:
+%
+\begin{verbatim}
+:02:24 20:14:18Z | alibaba.IfA.Hawaii.Edu | I | example.utils.helloWorld
+    Hello world,
+    it's me calling.
+\end{verbatim}
+%
+The possible order of the format entries is fixed and not determined
+by the order of the letters used in \code{psTraceSetFormat}.  Selecting
+an output format with fewer than the complete set of 5 entries simply
+removes those entries from the output messages.
+Specifying a \code{fmt} of \code{NULL} turns off logging (equivalent
+to calling \code{psLogSetDestination(PS_LOG_TO_NONE)}, whereas if the
+\code{fmt} is \code{""}, then the format reverts to the default.
+\subsubsection{Message Logging}
+\hlabel{psLogMsg}
+Message logging is similar in some respects to tracing.  Like trace
+messages, log messages are placed in the code at various locations to
+provide output describing the current state of the program.  Like
+the PSLib trace facility, a good log facility should have the
+capability of associating each message with an importance or severity
+level, and at any point, the level for which messages are actually
+printed should be set in a flexible manner.   Unlike trace messages,
+however, log messages are always part of the code and are available in
+the production version as well as in test versions.
+The PSLib logging facility does not include the extensive facility
+levels which are provided by the trace facility.  Less control over
+the granularity is needed for the log messages than for the trace
+messages.
+A log message is placed in the code with the command:
+%
+\begin{prototype}
+void psLogMsg(const char *name, int level, const char *fmt, ...);
+void psLogMsgV(const char *name, int level, const char *fmt, va_list ap);
+\end{prototype}
+where \code{name} is a word to describe the source of the message,
+\code{level} is the severity level of this message, and \code{fmt}
+is a printf-style formatting statement defining the actual message,
+and is followed by the arguments to the formatting code.  The second
+form, \code{psLogMsgV} is an equivalent command which takes a
+\code{va_list} argument.
+A log message may have any level specified in the range 0-9, though
+the first 4 levels are associated with symbolic names:
+%
+\begin{datatype}
+enum { PS_LOG_ABORT = 0, PS_LOG_ERROR, PS_LOG_WARN, PS_LOG_INFO };
+\end{datatype}
+%
+At any time, the program may set the current log level, the level
+above which log messages are ignored, using the function:
+%
+\begin{prototype}
+int psLogSetLevel(int level);
+\end{prototype}
+%
+This function returns the previous log level.  A specific message
+invoked with \code{psLogMsg} is only printed if its value of
+\code{level} is less than the current value set by
+\code{psLogSetLevel}.  The default log level is set to
+\code{PS_LOG_INFO}.
+Log messages are sent to the destination most recently set using:
+%
+\begin{prototype}
+bool psLogSetDestination(int fd);
+\end{prototype}
+%
+If the \code{fd} is 0, then the log is sent to standard output,
+otherwise it is sent to the specified file descriptor.  A call to
+\code{psLogSetDestination} automatically closes an open file
+descriptor.
+The corresponding function
+\begin{prototype}
+int psLogGetDestination();
+\end{prototype}
+returns the current log destination file descriptor.  If the
+destination has not been defined by the user, the descriptor for
+\code{stdout} is returned.
+The output format is controlled with the function:
+%
+\begin{prototype}
+bool psLogSetFormat(const char *fmt);
+\end{prototype}
+%
+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{THLNM}, which produces log messages in
+the form:
+\begin{verbatim}
+YYYY-MM-DD hh:mm:ssZ | hostname | L | name
+    The message goes here
+    and is indented by 4 spaces.
+\end{verbatim}
+where \code{YYYY}, \code{MM}, \code{DD}, \code{hh}, \code{mm}, and
+\code{ss} are the year, month (Jan is 01), 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 character 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 fields, \code{name} and \code{msg}, are the
+arguments to \code{psLogMsg}.  The \code{msg} is placed on a new line
+(allowing the \code{name} to fill the rest of the previous line),
+with each line indented by 4 spaces.  An example message is:
+%
+\begin{verbatim}
+:02:24 20:14:18Z | alibaba.IfA.Hawaii.Edu | I | example.utils.helloWorld
+    Hello world,
+    it's me calling.
+\end{verbatim}
+%
+The possible order of the format entries is fixed and not determined
+by the order of the letters used in \code{psLogSetFormat}.  Selecting
+an output format with fewer than the complete set of 5 entries simply
+removes those entries from the output messages.
+Specifying a \code{fmt} of \code{NULL} turns off logging (equivalent
+to calling \code{psLogSetDestination(PS_LOG_TO_NONE)}, whereas if the
+\code{fmt} is \code{""}, then the format reverts to the default.
+The following utility opens an output file descriptor for use by the
+trace and log facilities.
+\begin{prototype}
+int psMessageDestination (const char *dest);
+\end{prototype}
+%
+The destination string consists of a URL in the form
+\code{protocol:location}.  The \code{protocol} value may be
+\code{file}, to send the log to a local file named by the value of
+\code{location}.  Future expansion may allow the logger to send
+messages to an IP logger, with a protocol to be defined later.  Three
+other special values are allowed for the \code{dest} parameter
+(without specifying a protocol): \code{stderr} and \code{stdout},
+which return the file descriptors for \code{stderr} and \code{stdout}
+respectively, and \code{none} which returns the special descriptor to
+turn off logging.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Error Handling}
+\hlabel{errorStack}
+\PS{} errors must be raised using a function, \code{psError}, with the
+caller supplying a component name and error message.  It is desireable
+to be able to trace an error through the program so that the events
+that led to the error may be quickly and clearly identified.
+\code{psError} prints an error message and doesn't abort, but instead
+returns the error code.
+\begin{prototype}
+psErrorCode p_psError(const char *filename, unsigned int lineno, const char *func, psErrorCode code, bool new,
+                      const char *fmt, ...);
+\end{prototype}
+\begin{datatype}
+#define psError(code, new, fmt, ...) psError(__FILE__, __LINE__, __func__, code, new, fmt, __VA_ARGS__)
+\end{datatype}
+\code{psError} is a macro definition that allows the filename, line
+number and function name to be inputted to a private function,
+\code{p_psError}.  The \code{code} is an enumerated type which lists
+the possible \textit{classes} of errors (e.g. \code{PS_ERR_IO}) that
+\PS{} code can generate (see section \ref{psErrorCodes}). The
+\code{new} argument takes a boolean which, if \code{TRUE} specifies
+that the error was set initially at this location, and if \code{FALSE}
+specifies that an error was passed to this location.  Raising new
+error should clear the error stack.  The final required argument,
+\code{fmt}, is a \code{printf}-style format that is passed to
+\code{psLogMsgV} with code \code{PS_LOG_ERROR}, and component equal to
+the concatenation of the file name and the line number, separated by a
+colon.  The result of a call to \code{psError} must be to push an
+error onto a stack; this stack is cleared if \code{new} is true, or by
+a call to \code{psErrorClear}.
+The errors on the error stack are defined as the following:
+\begin{datatype}
+typedef struct {
+    char *name;                         ///< category of code that caused the error
+    psErrorCode code;                   ///< class of error (equivalent to errno)
+    char *msg;                          ///< the message associated with the error
+} psErr;
+\end{datatype}
+The last error reported is available from \code{psErrorLast}; if no
+errors are current, a non-\code{NULL} \code{psErr} must be returned
+with code \code{PS_ERR_NONE}.  Previous errors on the stack must be
+returned by \code{psErrorGet} (a value of \code{0} passed to
+\code{psErrorGet} is equivalent to a call to \code{psErrorLast}).
+The error stack may be completely cleared with \code{psErrorClear}.
+%
+\begin{prototype}
+unsigned int psErrorGetStackSize(void);
+const psErr *psErrorGet(int which);
+const psErr *psErrorLast(void);
+void psErrorClear(void);
+\end{prototype}
+\code{psErrorGetStackSize} shall return the number of errors on the
+stack.  The entire error stack may be printed to an open file
+descriptor by calling \code{psErrorStackPrint} (or
+\code{psErrorStackPrintV}); if and only if there are current errors,
+the printf-style string \code{fmt} is first printed to the file
+descriptor \code{fd}. In this printout, error codes must be replaced
+by their string equivalents as defined in the next section.  Note that
+these are also available in the \code{psErr} structure. The successive
+lines of the traceback should be indented by an additional space.
+\code{psErrorStackPrintV} must not invoke \code{va_end}.
+%
+\begin{prototype}
+void psErrorStackPrint(FILE *fd, const char *fmt, ...);
+void psErrorStackPrintV(FILE *fd, const char *fmt, va_list va);
+\end{prototype}
+Any \code{errorCode}s less then or equal to \code{PS_ERR_BASE} (see
+next section) must be taken to be valid values of \code{errno}, and
+\code{psErrorStackPrint} must print the value returned by
+\code{strerror} if such error codes are encountered.
+The routine \code{psErrorCodeString} returns the string associated
+with an error code:
+\begin{prototype}
+const char *psErrorCodeString(psErrorCode code);
+\end{prototype}
+\subsubsection{Error Codes}
+\hlabel{psErrorCodes}
+Both error codes for PSLib and error codes for projects that use PSLib
+may be registered.  In the former case, the error codes must be
+registered on initialisation, whereas in the latter case, they must be
+explicitly registered by the programmer.
+\paragraph{Registering error codes}
+PSLib and any project needed to use PSLib must define the necessary
+error codes and associated message strings.  An array of error codes
+may be registered with the PSLib error handler using the function:
+\begin{prototype}
+void psErrorRegister(const psErrorDescription *errors, psS32 nerror);
+\end{prototype}
+where the errors are represented internally as follows:
+\begin{datatype}
+typedef struct {
+    psErrorCode code;                  ///< An error code
+    const char *descrip;               ///< the associated description
+} psErrorDescription;
+\end{datatype}
+PSLib internal errors must be registered with the function
+\code{psErrorRegister}, which should be called as part of the
+program initialization to set up the error codes.  It is left to the
+external project to produce their own error registration functions
+which must also be called during initialization. There is a clear need
+to coordinate the choice of error numbers.  It is expected that error
+code ranges for different projects must be managed by the Project
+Office within Pan-STARRS.
+\paragraph{Error Codes for PSLib}
+For ease of maintenance, error codes for PSLib must be defined by an
+auxiliary file, conventionally named \file{psErrorCodes.dat}.  The
+format of this file must consist of a number of lines, each of the
+form:
+\begin{verbatim}
+NAME [ = value ][,] STRING
+\end{verbatim}
+where \code{[ = value]} and the comma are optional, and no spaces are
+significant except in the STRING.  Comments extend from \code{#} to
+the end of the line (except that a \code{\#} must be replaced by
+\code{#} and not taken to start a comment). For example,
+\begin{verbatim}
+#
+# This file is used to generate psErrorClasses.h
+#
+NONE = 0,               not an error; must be 0
+BASE = 256,             first value we use; should avoid errno conflicts
+UNKNOWN,                unknown error
+# This is a comment, and is ignored.
+IO,                     I/O error
+BADFREE,                bad argument to psFree()
+MEMORY_CORRUPTION,      memory corruption detected
+\end{verbatim}
+The values \code{NONE = 0} and {UNKNOWN} must be present.
+A script, called from the Makefiles, must generate two files,
+\file{psErrorCodes.h} and \file{psErrorCodes.c} from the input file
+\file{psErrorCodes.dat}.  \file{psErrorCodes.h} must define an
+enumerated type \code{psErrorCode} with elements \code{PS_ERR_NAME}
+and values as specified in \file{psErrorCodes.dat}, e.g.
+\begin{datatype}
+#if !defined(PS_ERROR_CODES_H)
+#define PS_ERROR_CODES_H
+typedef enum {
+    PS_ERR_NONE = 0,
+    PS_ERR_BASE = 256,
+    PS_ERR_UNKNOWN,
+    PS_ERR_IO,
+    PS_ERR_BADFREE,
+    PS_ERR_MEMORY_CORRUPTION,
+    PS_ERR_N_ERR_CLASSES,
+} psErrorCode;
+#endif
+\end{datatype}
+Any \code{errorCode}s less then or equal to \code{PS_ERR_BASE} must be
+taken to be valid values of \code{errno}.  \file{psErrorCodes.c} must
+define the necessary function to register the error codes.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Abort}
+\code{psAbort}, must call \code{psLogMsgV} with a level of
+\code{PS_LOG_ABORT}, and then call \code{abort}.
+\begin{prototype}
+void psAbort(const char *name, const char *fmt,...);
+\end{prototype}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\pagebreak
+\section{Basic Data Types and Collections}
+We require general data containers, so that associated values (e.g.\
+the elements of an array) may be connected as a whole.  We require the
+following types of containers:
+\begin{itemize}
+\item Arrays;
+\item Doubly-linked lists; and
+\item Hashes.
+\end{itemize}
+\subsection{Data Structure Type Information}
+Throughout PSLib, we require a variety of structures which correspond
+to different mathematical data concepts.  For example, we have a data
+structure which corresponds to one-dimensional arrays (vectors) of
+different data types (\code{int}, \code{float}, etc).  We also have a
+data structure which corresponds to two-dimensional arrays (images or
+matrices), again with different data types for the individual
+elements.
+A variety of functions perform operations which are equivalent for
+different data types of the same dimension, or may even be defined for
+different data types of different dimensions.  For example, if we
+write the operation $x + y$, the operation is clearly defined
+regardless of whether the operands $x$ and $y$ are both zero
+dimensional (single numbers), one dimensional (vectors), two
+dimensional (images), etc. It is even reasonable to define the meaning
+of such an operation if the data dimensions do not match: if $x$ is a
+scalar and $y$ is an image, the natural operation is to add the value
+of $x$ to every element of $y$; we can also define the meaning of the
+operation if $x$ is a vector and $y$ is a matrix.  Nor does it matter
+mathematically that the element data types match; the sum of a float
+and an integer is a well-defined quantity.  One constraint should be
+noted: the size of the elements in each dimension must match.  For
+example, if $x$ were a vector of 100 elements, but $y$ were a vector
+of 1000 elements, the meaning of the operation $x + y$ is unclear.
+This type of operation should be invalid and should generate an error.
+Given that some functions should be able to operate equivalently (or
+identically) on a wide range of data types, we define a mechanism
+which allows the C functions to accept a generic data type, and
+determine the type of the data on the basis of the data.
+Supported data types must be defined by a structure in which
+the first element is always of type \code{psType}:
+\begin{datatype}
+typedef struct {
+    psDimen dimen;                      ///< The dimensionality
+    psElemType type;                    ///< The type
+} psType;
+\end{datatype}
+where \code{psDimen dimen} defines the dimensionality of the data and
+\code{psElemType type} defines the data type of each element.  These
+two variable types are defined as:
+\begin{datatype}
+typedef enum {
+    PS_DIMEN_SCALAR,                    ///< Scalar
+    PS_DIMEN_VECTOR,                    ///< A vector
+    PS_DIMEN_TRANSV,                    ///< A transposed vector
+    PS_DIMEN_IMAGE,                     ///< An image (matrix)
+    PS_DIMEN_OTHER                      ///< Not supported for arithmetic
+} psDimen;
+\end{datatype}
+and
+\begin{datatype}
+typedef enum {
+    PS_TYPE_S8,                         ///< Character
+    PS_TYPE_S16,                        ///< Short integer
+    PS_TYPE_S32,                        ///< Integer
+    PS_TYPE_S64,                        ///< Long integer
+    PS_TYPE_U8,                         ///< Unsigned character
+    PS_TYPE_U16,                        ///< Unsigned short integer
+    PS_TYPE_U32,                        ///< Unsigned integer
+    PS_TYPE_U64,                        ///< Unsigned long integer
+    PS_TYPE_F32,                        ///< Floating point
+    PS_TYPE_F64,                        ///< Double-precision floating point
+    PS_TYPE_C32,                        ///< Complex numbers consisting of floats
+    PS_TYPE_C64,                        ///< Complex numbers consisting of doubles
+    PS_TYPE_BOOL                        ///< Boolean value
+} psElemType;
+\end{datatype}
+We discuss the application of \code{psType} in more detail in
+section~\ref{sec:arithmetic}.
+\subsection{Type checking}
+\subsubsection{Type information}
 Several of the collections contain data using a \code{void*} pointer.
 …
 the \code{ptr} matches the desired type, as determined from the
 registered deallocator function.  These functions may be implemented
 as macros if that is deemed convenient.
+as macros or inline functions if that is deemed convenient.
 \begin{prototype}
 …
 \end{prototype}
+\subsection{Simple Scalars}
+\tbd{Need to define psType.}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Threads}
+As pointed out earlier, PSLib makes no guarantees for thread-safety
+outside of the memory management functions.  Nevertheless, the following
+facilities are provided as a convenience to the user.
+Each of the data structures classified as a ``collection'' (i.e.,
+\code{psList, psHash, psMetadata, psArray, psPixels, psVector,
+psBitSet}) and \code{psImage} shall contain an additional member,
+\code{void *lock}, which provides a place for the user to carry around
+a mutex or semaphore.  This is provided so that the user doesn't have
+to pass around both the structure and a mutex, or wrap PSLib
+structures in their own thread-safe structures that contain a mutex.
+We also define the following conveniences:
+\begin{datatype}
+typedef struct {
+    pthread_mutex_t mutex;
+} psMutex;
+\end{datatype}
+\begin{prototype}
+psMutex *psMutexAlloc(void);
+bool psMutexLock(psMutex *mutex);
+bool psMutexUnlock(psMutex *mutex);
+\end{prototype}
+\code{psMutex} simply wraps a POSIX thread mutex (this is necessary in
+order to use the PS memory management system).
+\code{psMutexAlloc} shall allocate memory for a \code{psMutex}, and
+initialise the mutex.  \code{psMutexLock} shall lock the mutex in
+\code{thread}, and \code{psMutexUnlock} shall unlock the mutex in
+\code{thread}.
+These functions, in the interests of speed, should be implemented as
+preprocessor macros.
+These functions and the \code{void *lock} in the collection structures
+and  \code{psImage} should  only  be defined  if \code{_REENTRANT}  is
+defined; otherwise the functions should be poisoned.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Tracing and Logging}
+This section 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 (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
+extensive use will be made of \code{psTrace} throughout the \PS{}
+code.
+\subsubsection{Tracing APIs}
+\hlabel{psTrace}
+A code-tracing facility should allow the programmer to place messages
+in the code which, when called, will print some useful information
+about the containing block of code.  Ideally, different messages may
+be specified to have different levels (of severity or interest).  For
+a given run of the program, the level of interest should be set to
+provide more or less feedback, depending on the needs of the
+programmer.  In a typical situation, low-level messages would be
+placed generously throughout the code, indicating the flow of the
+program.  Higher-level messages would be placed in a limited number of
+special locations, such as the start of major code segments or where a
+particularly unusual condition is met.  Top-level messages would be
+placed in code triggered under serious error conditions.  A normal run
+of the program would have the trace messages printed only for the
+top-level.  If the user needs to dig deeper into the code, the trace
+level should be set lower, and the more detailed messages could be
+examined.  In a case of a serious, poorly-understood problem with the
+code, the trace threshold would be placed to the bottom and the
+lowest-level step-by-step messages would be printed.
+The PSLib tracing facility provides the above functionality, along
+with the ability to assign different trace levels to messages from
+different software components.  Each trace message, when placed in the
+code, is assigned to be part of a specific tracing 'facility', defined
+in more detail below.  The trace level for that specific message is
+also set when the message is placed.  Each facility may have its trace
+level set independently.  Thus, it is possible to request detailed
+trace output for one facility while minimizing the verbosity of the
+trace output from the rest of the program.
+The trace facilities consist of a hierarchy of names.  A trace
+facility is defined by a string consisting of words separated by dots,
+with a hierarchy equivalent to that of UNIX directory names.  The
+top-level facility is simply \code{'.'} (one dot).  The next level
+would be \code{'.A'}, followed by \code{.A.B}, and so on.  The
+relationship is seen in two ways.  First, a facility inherits the
+trace level of its parent unless explicitly specified.  Second, the
+hierarchy is used to format the listing of the trace facilities so
+that they are easy to read.  The first of these rules provides a
+mechanism to define the default trace levels for any facility even if
+it has not been registered explicitly since all named facilities are
+implicitly children of the top level facility (\code{.}).  The second
+rule is simply an organizational technique to make the listing of
+facility information clear.  In specifying a facility, the leading
+dot shall be optional, as a convenience to the user.
+The API to place a trace message in the code, and simultaneously set
+its trace level and facility, is:
+%
+\begin{prototype}
+void psTrace(const char *facil, int level, const char *fmt,...);
+void psTraceV(const char *facil, int level, const char *fmt, va_list ap);
+\end{prototype}
+%
+where the \code{fmt} argument is a printf-style formatting code
+followed by possible arguments to that formatting statement, to be
+implemented using the \code{vprintf} functions.  This command
+specifies the name of the facility to which the message belongs
+(\code{facil}), the trace level for this message in that facility
+(\code{level}) and the message itself.  The \code{psTraceV} version of
+the command accepts a \code{va_list} argument list rather than a
+variable number of arguments.
+The trace level for any facility may be set at any time with the
+following function:
+%
+\begin{prototype}
+int psTraceSetLevel(const char *facil, int level);
+\end{prototype}
+%
+where \code{level} specifies the current trace level for the facility
+named by \code{facil}.  The currently defined trace level for a given
+facility may be determined by the function:
+%
+\begin{prototype}
+int psTraceGetLevel(const char *facil);
+\end{prototype}
+%
+which returns the trace level of the named facility following the
+rules specified above.  A specified trace message (identified by
+\code{psTrace}) must be printed if and only if
+\code{psTraceGetLevel(facil)} returns a value greater than or equal to
+the value of \code{level} for that message.  That is, a larger
+number for the trace level corresponds to lower-level statements, and
+hence is more verbose.
+PSLib includes a utility function for examining the current tracing
+levels of all facilities:
+%
+\begin{prototype}
+void psTracePrintLevels(void);
+\end{prototype}
+%
+This function prints the hierarchy of trace facilities along with the
+current trace level for each facility.  For example, a particular
+program may have a few facilities defined, along with their trace
+levels.  A call to \code{psTracePrintLevels} may produce a listing
+which appears as:
+\begin{verbatim}
+.                        0
+ .IPP                    0
+ .IPP.debias             1
+ .IPP.flatten            1
+  .IPP.flatten.divide    2
+  .IPP.object.findpeak   1
+  .IPP.object.getsky     1
+\end{verbatim}
+Considering the same program, the programmer might place a variety of
+trace messages throughout the \code{flatten} portion of the code with
+different types of messages, such as:
+%
+\begin{verbatim}
+psTrace("IPP.flatten", 2, "starting flatten function\n");
+psTrace("IPP.flatten", 0, "flat-field image is \%s\n", filename);
+psTrace("IPP.flatten.divide", 2, "doing the divide\n");
+psTrace("IPP.flatten.divide", 3, "trying the loop, i = \%d\n", i);
+psTrace("IPP.flatten.divide", 1, "got an invalid pixel value (NaN) at \%d,\%d\n");
+psTrace("IPP.flatten.divide", 2, "divide is done\n");
+\end{verbatim}
+%
+Under the trace levels set above, if the code actually reached each of
+these trace messages, the following messages would be printed:
+%
+\begin{verbatim}
+flat-field image is foo.fits
+  doing the divide
+  got an invalid pixel value (NaN) at 500,20
+  divide is done
+\end{verbatim}
+%
+while these two would not be printed because their facility level was
+too low:
+%
+\begin{verbatim}
+  starting flatten function
+   trying the loop, i = 0
+   trying the loop, i = 1
+   trying the loop, i = 2
+...
+\end{verbatim}
+%
+The availability of the tracing facility at run-time, must be decided
+at compilation: If the C pre-processor macro \code{PS_NO_TRACE} is
+defined, all trace code must be replaced by empty space so that none
+of the code is compiled.  This can be implemented via macro front-ends
+to private versions of the user APIs.  In addition, a function
+\code{bool psTraceReset(void)} will free memory used by \code{psTrace}
+functions, effectively resetting all trace levels to 0.
+The trace may optionally be written to a file or other output
+destination with \code{psTraceSetDestination}:
+\begin{prototype}
+void psTraceSetDestination(int fd);
+\end{prototype}
+If the \code{fd} is 0, then the trace is sent to standard output,
+otherwise it is sent to the specified file descriptor.  A call to
+\code{psTraceSetDestination} automatically closes the file descriptor.
+The corresponding function
+\begin{prototype}
+int psTraceGetDestination();
+\end{prototype}
+returns the current trace destination file descriptor.  If the
+destination has not been defined by the user, the descriptor for
+\code{stdout} is returned.
+The trace output format is controlled with the function:
+%
+\begin{prototype}
+bool psTraceSetFormat(const char *fmt);
+\end{prototype}
+%
+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{THLNM}, which produces trace messages in
+the form:
+\begin{verbatim}
+YYYY-MM-DD hh:mm:ssZ | hostname | L | name
+    The message goes here
+    and is indented by 4 spaces.
+\end{verbatim}
+where \code{YYYY}, \code{MM}, \code{DD}, \code{hh}, \code{mm}, and
+\code{ss} are the year, month (Jan is 01), day of the month, hours
+(0--23), minutes, and seconds when the trace 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 character 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 fields, \code{facil} and \code{msg}, are the
+arguments to \code{psTrace}.  The \code{msg} is placed on a new line
+(allowing the \code{name} to fill the rest of the previous line),
+with each line indented by 4 spaces.  An example message is:
+%
+\begin{verbatim}
+:02:24 20:14:18Z | alibaba.IfA.Hawaii.Edu | I | example.utils.helloWorld
+    Hello world,
+    it's me calling.
+\end{verbatim}
+%
+The possible order of the format entries is fixed and not determined
+by the order of the letters used in \code{psTraceSetFormat}.  Selecting
+an output format with fewer than the complete set of 5 entries simply
+removes those entries from the output messages.
+Specifying a \code{fmt} of \code{NULL} turns off logging (equivalent
+to calling \code{psLogSetDestination(PS_LOG_TO_NONE)}, whereas if the
+\code{fmt} is \code{""}, then the format reverts to the default.
+\subsubsection{Message Logging}
+\hlabel{psLogMsg}
+Message logging is similar in some respects to tracing.  Like trace
+messages, log messages are placed in the code at various locations to
+provide output describing the current state of the program.  Like
+the PSLib trace facility, a good log facility should have the
+capability of associating each message with an importance or severity
+level, and at any point, the level for which messages are actually
+printed should be set in a flexible manner.   Unlike trace messages,
+however, log messages are always part of the code and are available in
+the production version as well as in test versions.
+The PSLib logging facility does not include the extensive facility
+levels which are provided by the trace facility.  Less control over
+the granularity is needed for the log messages than for the trace
+messages.
+A log message is placed in the code with the command:
+%
+\begin{prototype}
+void psLogMsg(const char *name, int level, const char *fmt, ...);
+void psLogMsgV(const char *name, int level, const char *fmt, va_list ap);
+\end{prototype}
+where \code{name} is a word to describe the source of the message,
+\code{level} is the severity level of this message, and \code{fmt}
+is a printf-style formatting statement defining the actual message,
+and is followed by the arguments to the formatting code.  The second
+form, \code{psLogMsgV} is an equivalent command which takes a
+\code{va_list} argument.
+A log message may have any level specified in the range 0-9, though
+the first 4 levels are associated with symbolic names:
+%
+\begin{datatype}
+enum { PS_LOG_ABORT = 0, PS_LOG_ERROR, PS_LOG_WARN, PS_LOG_INFO };
+\end{datatype}
+%
+At any time, the program may set the current log level, the level
+above which log messages are ignored, using the function:
+%
+\begin{prototype}
+int psLogSetLevel(int level);
+\end{prototype}
+%
+This function returns the previous log level.  A specific message
+invoked with \code{psLogMsg} is only printed if its value of
+\code{level} is less than the current value set by
+\code{psLogSetLevel}.  The default log level is set to
+\code{PS_LOG_INFO}.
+Log messages are sent to the destination most recently set using:
+%
+\begin{prototype}
+bool psLogSetDestination(int fd);
+\end{prototype}
+%
+If the \code{fd} is 0, then the log is sent to standard output,
+otherwise it is sent to the specified file descriptor.  A call to
+\code{psLogSetDestination} automatically closes an open file
+descriptor.
+The corresponding function
+\begin{prototype}
+int psLogGetDestination();
+\end{prototype}
+returns the current log destination file descriptor.  If the
+destination has not been defined by the user, the descriptor for
+\code{stdout} is returned.
+The output format is controlled with the function:
+%
+\begin{prototype}
+bool psLogSetFormat(const char *fmt);
+\end{prototype}
+%
+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{THLNM}, which produces log messages in
+the form:
+\begin{verbatim}
+YYYY-MM-DD hh:mm:ssZ | hostname | L | name
+    The message goes here
+    and is indented by 4 spaces.
+\end{verbatim}
+where \code{YYYY}, \code{MM}, \code{DD}, \code{hh}, \code{mm}, and
+\code{ss} are the year, month (Jan is 01), 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 character 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 fields, \code{name} and \code{msg}, are the
+arguments to \code{psLogMsg}.  The \code{msg} is placed on a new line
+(allowing the \code{name} to fill the rest of the previous line),
+with each line indented by 4 spaces.  An example message is:
+%
+\begin{verbatim}
+:02:24 20:14:18Z | alibaba.IfA.Hawaii.Edu | I | example.utils.helloWorld
+    Hello world,
+    it's me calling.
+\end{verbatim}
+%
+The possible order of the format entries is fixed and not determined
+by the order of the letters used in \code{psLogSetFormat}.  Selecting
+an output format with fewer than the complete set of 5 entries simply
+removes those entries from the output messages.
+Specifying a \code{fmt} of \code{NULL} turns off logging (equivalent
+to calling \code{psLogSetDestination(PS_LOG_TO_NONE)}, whereas if the
+\code{fmt} is \code{""}, then the format reverts to the default.
+The following utility opens an output file descriptor for use by the
+trace and log facilities.
+\begin{prototype}
+int psMessageDestination (const char *dest);
+\end{prototype}
+%
+The destination string consists of a URL in the form
+\code{protocol:location}.  The \code{protocol} value may be
+\code{file}, to send the log to a local file named by the value of
+\code{location}.  Future expansion may allow the logger to send
+messages to an IP logger, with a protocol to be defined later.  Three
+other special values are allowed for the \code{dest} parameter
+(without specifying a protocol): \code{stderr} and \code{stdout},
+which return the file descriptors for \code{stderr} and \code{stdout}
+respectively, and \code{none} which returns the special descriptor to
+turn off logging.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Error Handling}
+\hlabel{errorStack}
+\PS{} errors shall be raised using a function, \code{psError}, with the
+caller supplying a component name and error message.  It is desireable
+to be able to trace an error through the program so that the events
+that led to the error may be quickly and clearly identified.
+\code{psError} prints an error message and doesn't abort, but instead
+returns the error code.
+\begin{prototype}
+psErrorCode p_psError(const char *filename, unsigned int lineno, const char *func, psErrorCode code,
+                      bool new, const char *fmt, ...);
+\end{prototype}
+\begin{datatype}
+#define psError(code, new, fmt, ...) psError(__FILE__, __LINE__, __func__, code, new, fmt, __VA_ARGS__)
+\end{datatype}
+\code{psError} is a macro definition that allows the filename, line
+number and function name to be inputted to a private function,
+\code{p_psError}.  The \code{code} is an enumerated type which lists
+the possible \textit{classes} of errors (e.g. \code{PS_ERR_IO}) that
+\PS{} code can generate (see section \ref{psErrorCodes}). The
+\code{new} argument takes a boolean which, if \code{true} specifies
+that the error was set initially at this location, and if \code{false}
+specifies that an error was passed to this location.  Raising new
+error should clear the error stack.  The final required argument,
+\code{fmt}, is a \code{printf}-style format that is passed to
+\code{psLogMsgV} with code \code{PS_LOG_ERROR}, and component equal to
+the concatenation of the file name and the line number, separated by a
+colon.  The result of a call to \code{psError} shall be to push an
+error onto a stack; this stack is cleared if \code{new} is true, or by
+a call to \code{psErrorClear}.
+The errors on the error stack are defined as the following:
+\begin{datatype}
+typedef struct {
+    char *name;                         ///< category of code that caused the error
+    psErrorCode code;                   ///< class of error (equivalent to errno)
+    char *msg;                          ///< the message associated with the error
+} psErr;
+\end{datatype}
+The last error reported is available from \code{psErrorLast}; if no
+errors are current, a non-\code{NULL} \code{psErr} shall be returned
+with code \code{PS_ERR_NONE}.  Previous errors on the stack shall be
+returned by \code{psErrorGet} (a value of \code{0} passed to
+\code{psErrorGet} is equivalent to a call to \code{psErrorLast}).
+The error stack may be completely cleared with \code{psErrorClear}.
+%
+\begin{prototype}
+unsigned int psErrorGetStackSize(void);
+const psErr *psErrorGet(int which);
+const psErr *psErrorLast(void);
+void psErrorClear(void);
+\end{prototype}
+\code{psErrorGetStackSize} shall return the number of errors on the
+stack.  The entire error stack may be printed to an open file
+descriptor by calling \code{psErrorStackPrint} (or
+\code{psErrorStackPrintV}); if and only if there are current errors,
+the printf-style string \code{fmt} is first printed to the file
+descriptor \code{fd}. In this printout, error codes shall be replaced
+by their string equivalents as defined in the next section.  Note that
+these are also available in the \code{psErr} structure. The successive
+lines of the traceback should be indented by an additional space.
+\code{psErrorStackPrintV} must not invoke \code{va_end}.
+%
+\begin{prototype}
+void psErrorStackPrint(FILE *fd, const char *fmt, ...);
+void psErrorStackPrintV(FILE *fd, const char *fmt, va_list va);
+\end{prototype}
+Any error \code{code}s less then or equal to \code{PS_ERR_BASE} (see
+next section) must be taken to be valid values of \code{errno}, and
+\code{psErrorStackPrint} must print the value returned by
+\code{strerror} if such error codes are encountered.
+The routine \code{psErrorCodeString} returns the string associated
+with an error code:
+\begin{prototype}
+const char *psErrorCodeString(psErrorCode code);
+\end{prototype}
+\subsubsection{Error Codes}
+\hlabel{psErrorCodes}
+Both error codes for PSLib and error codes for projects that use PSLib
+may be registered.  In the former case, the error codes must be
+registered on initialisation (see \code{psLibInit}), whereas in the
+latter case, they must be explicitly registered by the programmer.
+\paragraph{Registering error codes}
+PSLib and any project needed to use PSLib must define the necessary
+error codes and associated message strings.  An array of error codes
+may be registered with the PSLib error handler using the function:
+\begin{prototype}
+void psErrorRegister(const psErrorDescription *errors, psS32 nerror);
+\end{prototype}
+where the errors are represented internally as follows:
+\begin{datatype}
+typedef struct {
+    psErrorCode code;                  ///< An error code
+    const char *descrip;               ///< the associated description
+} psErrorDescription;
+\end{datatype}
+PSLib internal errors must be registered with the function
+\code{psErrorRegister}, which should be called as part of the
+program initialization to set up the error codes.  It is left to the
+external project to produce their own error registration functions
+which must also be called during initialization. There is a clear need
+to coordinate the choice of error numbers.  It is expected that error
+code ranges for different projects must be managed by the Project
+Office within Pan-STARRS.
+\paragraph{Error Codes for PSLib}
+For ease of maintenance, error codes for PSLib must be defined by an
+auxiliary file, conventionally named \file{psErrorCodes.dat}.  The
+format of this file must consist of a number of lines, each of the
+form:
+\begin{verbatim}
+NAME [ = value ][,] STRING
+\end{verbatim}
+where \code{[ = value]} and the comma are optional, and no spaces are
+significant except in the STRING.  Comments extend from \code{#} to
+the end of the line (except that a \code{\#} must be replaced by
+\code{#} and not taken to start a comment). For example,
+\begin{verbatim}
+#
+# This file is used to generate psErrorClasses.h
+#
+NONE = 0,               not an error; must be 0
+BASE = 256,             first value we use; should avoid errno conflicts
+UNKNOWN,                unknown error
+# This is a comment, and is ignored.
+IO,                     I/O error
+BADFREE,                bad argument to psFree()
+MEMORY_CORRUPTION,      memory corruption detected
+\end{verbatim}
+The values \code{NONE = 0} and {UNKNOWN} must be present.
+A script, called from the Makefiles, must generate two files,
+\file{psErrorCodes.h} and \file{psErrorCodes.c} from the input file
+\file{psErrorCodes.dat}.  \file{psErrorCodes.h} must define an
+enumerated type \code{psErrorCode} with elements \code{PS_ERR_NAME}
+and values as specified in \file{psErrorCodes.dat}, e.g.
+\begin{datatype}
+#if !defined(PS_ERROR_CODES_H)
+#define PS_ERROR_CODES_H
+typedef enum {
+    PS_ERR_NONE = 0,
+    PS_ERR_BASE = 256,
+    PS_ERR_UNKNOWN,
+    PS_ERR_IO,
+    PS_ERR_BADFREE,
+    PS_ERR_MEMORY_CORRUPTION,
+    PS_ERR_N_ERR_CLASSES,
+} psErrorCode;
+#endif
+\end{datatype}
+\file{psErrorCodes.c} must define the necessary functions to register
+the error codes.
+This script will likely be of use to the user, and so it shall be
+installed as part of PSLib.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Abort}
+\code{psAbort}, must call \code{psLogMsgV} with a level of
+\code{PS_LOG_ABORT}, and then call \code{abort}.
+\begin{prototype}
+void psAbort(const char *name, const char *fmt,...);
+\end{prototype}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\pagebreak
+\section{Containers}
+We require general data containers, so that associated values (e.g.\
+the elements of an array) may be connected as a whole.  We require the
+following types of containers:
+\begin{itemize}
+\item Arrays;
+\item Doubly-linked lists;
+\item Hashes;
+\item Pixel lists;
+\item Bit sets;
+\item Metadata; and
+\item Lookup tables.
+\end{itemize}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Arrays}
+We require an order collection of unspecified data elements.  We
+define \code{psArray} to carry such a collection:
+%
+\begin{datatype}
+typedef struct {
+    const long n;                       ///< size of array
+    const long nalloc;                  ///< allocated data block
+    void **data;                        ///< pointer to data block
+    void *lock;                         ///< Optional lock for thread safety
+}} psArray;
+\end{datatype}
+%
+In this structure, the argument \code{n} is the length of the array
+(the number of elements); \code{nalloc} is the number of elements
+allocated ($nalloc \ge n$).  The allocated memory is pointed to by
+\code{data}.  The structure is associated with a constructor and a
+destructor:
+%
+\begin{prototype}
+psArray *psArrayAlloc(long nalloc);
+psArray *psArrayRealloc(psArray *array, long nalloc);
+\end{prototype}
+%
+In these functions, \code{nalloc} is the number of elements to
+allocate.  For \code{psArrayAlloc}, the value of \code{psArray.n} is
+set to \code{nalloc}.  Users may choose to restrict the data range
+after the \code{psArrayAlloc} function is called.  For
+\code{psArrayRealloc}, if the value of \code{nalloc} is smaller than
+the current value of \code{psArray.n}, then \code{psArray.n} is set to
+\code{nalloc}, the array is adjusted down to match \code{nalloc}, and
+the extra elements are dropped and freed if necesitated by the
+reference counter.  If \code{nalloc} is larger than the current value
+of \code{psArray.n}, \code{psArray.n} is left intact.  If the value of
+\code{array} is \code{NULL}, then \code{psArrayRealloc} must return an
+error.
+\begin{prototype}
+psArray *psArrayAdd(psArray *array, long delta, psPtr data);
+\end{prototype}
+This function adds a value to the end of an array.  If the current
+length of the array (\code{psArray.n}) is at the limit of the
+allocated space, additional space is allocated.  The value of
+\code{delta} defines how many elements to add on each pass (if this
+value is less than 1, 10 shall be used).
+\begin{prototype}
+bool psArrayRemove(psArray *array, const psPtr data);
+\end{prototype}
+This function removes all entries of \code{value} in the \code{array},
+reducing the total number of elements of \code{array} as needed.
+Returns \code{TRUE} if any elements were removed, otherwise
+    const int x0, y0;                   ///< data region relative to parent
+\code{FALSE}.
+\begin{prototype}
+bool psArraySet(psArray *array, long position, psPtr data);
+psPtr psArrayGet(const psArray *array, long position);
+\end{prototype}
+These accessor functions are provided as a convenience to the user.
+\code{psArraySet} sets the value of the \code{in} array at the specified
+\code{position} to \code{value}, returning \code{true} if successful.
+\code{psArrayGet} returns the value of the \code{in} array at the
+specified \code{position}.
+\begin{datatype}
+typedef int (*psComparePtrFunc) (
+    const void **a,                    ///< first comparison target
+    const void **b                     ///< second comparison target
+);
+\end{datatype}
+\begin{prototype}
+psArray *psArraySort(psArray *array, psComparePtrFunc func);
+\end{prototype}
+An array may be sorted using \code{psArraySort}, which requires the
+specification of a comparison function to specify how the objects on
+the list should be sorted.  The motivation is primarily to be able to
+iterate on a sorted list of keys from a hash.  The \code{array} is
+sorted in-place.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Doubly-linked lists}
+\label{sec:psList}
+\PS{} shall support doubly linked lists through a type \code{psList}:
+%
+\begin{datatype}
+typedef struct {
+   long n;                              ///< number of elements on list
+   psListElem *head;                    ///< first element on list (may be NULL)
+   psListElem *tail;                    ///< last element on list (may be NULL)
+   psArray *iterators;                  ///< array of psListIterator: iteration cursors
+   void *lock;                          ///< Optional lock for thread safety
+} psList;
+\end{datatype}
+%
+The type \code{psList} represents the container of the list.  It has a
+pointer to the first element in the linked list (\code{head}), a
+pointer to the last element in the list (\code{tail}), an array of
+iteration cursors, (\code{iterators}), and an entry to define the
+number of elements in the list (\code{n}).
+The elements of the list are defined by the type \code{psListElem}:
+%
+\begin{datatype}
+typedef struct psListElem {
+   struct psListElem *prev;            ///< previous link in list
+   struct psListElem *next;            ///< next link in list
+   void *data;                         ///< real data item
+} psListElem;
+\end{datatype}
+%
+which includes a pointer to the next element in the list
+(\code{next}), the previous element in the list (\code{prev}), and a
+\code{void} pointer to whatever data is represented by this list
+element.    The following supporting functions are required:
+\begin{prototype}
+psList *psListAlloc(psPtr data);
+\end{prototype}
+Create a list.  This function may take a pointer to a data item, or it
+may take \code{NULL}.  The allocator creates both the \code{psList}
+and the first element in the list, pointed to by both
+\code{psList.head} and \code{psList.tail}.  If the data entry is
+\code{NULL}, then an empty list, with both pointers set to \code{NULL}
+should be created.
+The destructor function for \code{psList} must call \code{psFree} for
+all the the data associated with the list.
+All data items placed onto lists must have their reference counters
+(section \ref{secMemRefcounter}) incremented.  When elements are
+removed from a list, they must have their reference counters
+decremented.  The action of retrieving data from a list (with one of
+the three \code{psListGet} functions) is considered ``borrowing'' the
+reference, so no action is performed on the reference counter.
+Iteration on the list shall be achieved by means of a list iterator
+type:
+\begin{datatype}
+typedef struct {
+    psList *list;                       ///< List iterator works on
+    psListElem *cursor;                 ///< The current iterator cursor
+    bool offEnd;                        ///< Is the iterator off the end?
+    long index;                         ///< Index of iterator, to assist performance
+    bool mutable;                       ///< Is it permissible to modify the list?
+} psListIterator;
+\end{datatype}
+The \code{psListIterator} keeps track of which list element the
+iterator \code{cursor} is currently pointing at.  \code{index} is the
+index of the list iterator, which is used to assist performance when
+using numerical locations.  The boolean member, \code{offEnd},
+indicates whether the iterator has progressed off the end of the list
+(i.e., beyond the last item).  The boolean \code{mutable} specifies
+whether it is permissible to modify the list pointed to by the
+iterator.  \code{psListAddBefore} and \code{psListAddAfter} are not
+permitted to modify a list that is not \code{mutable} (i.e., only the
+\code{psListGetAndIncrement} and \code{psListGetAndDecrement}
+operations are permissible for a non-\code{mutable} list).
+The corresponding constructor shall be:
+\begin{prototype}
+psListIterator *psListIteratorAlloc(const psList *list, long location, bool mutable);
+\end{prototype}
+Here, \code{list} is the \code{psList} on which the iterator will
+iterate, and \code{location} is the initial starting point, and may be
+a numerical index or it may be one of the special values:
+\code{PS_LIST_HEAD} or \code{PS_LIST_TAIL}, which are defined as 0 and
+-1, respectively; a negative index is interpreted as relative to the
+end of the list.  The boolean \code{mutable} specifies whether it is
+permissible to modify the list pointed to by the iterator.
+The destructor for \code{psListIterator} shall, after freeing the
+\code{psListIterator}, also reorganise the \code{iter} array
+(replacing the element being removed with the last element) and
+resizing the array appropriately.
+A list \code{iterator} shall be set to a specific \code{location} on
+the list upon calling \code{psListIteratorSet}:
+\begin{prototype}
+bool psListIteratorSet(psListIterator *iterator, int location);
+\end{prototype}
+Again, the \code{location} may be a numerical index or it may be one
+of the special values: \code{PS_LIST_HEAD} or \code{PS_LIST_TAIL},
+which are defined as 0 and -1, respectively; a negative index is
+interpreted as relative to the end of the list.  The function shall
+return \code{true} if the reset was successful, or \code{false}
+otherwise.
+\begin{prototype}
+bool psListAdd(psList *list, long location, psPtr data);
+bool psListAddAfter(psListIterator *iterator, psPtr data);
+bool psListAddBefore(psListIterator *iterator, psPtr data);
+\end{prototype}
+the first function, \code{psListAdd}, adds an entry to the \code{list}
+and returns a boolean giving the success or failure of the
+operation. The value of \code{location} may be a numerical index the
+\code{data} is to inhabit (if \code{location} is greater than the
+number of items on the list, then the function shall generate a
+warning and add the \code{data} to the tail) or it may be one of the
+special values: \code{PS_LIST_HEAD} or \code{PS_LIST_TAIL}, which are
+defined as 0 and -1, respectively; a negative index is interpreted as
+relative to the end of the list.  The other two functions,
+\code{psListAddAfter} and \code{psListAddBefore} specify that the
+\code{data} shall be added after or before (respectively) the current
+cursor position of the \code{iterator}.
+\begin{prototype}
+psPtr psListGet(psList *list, long location);
+psPtr psListGetAndIncrement(psListIterator *iterator);
+psPtr psListGetAndDecrement(psListIterator *iterator);
+\end{prototype}
+A data item may be retrieved from the list with these functions.  The
+first function, \code{psListGet} simply returns the value specified by
+its \code{location}, which may be a numerical index or it may be one
+of the special values: \code{PS_LIST_HEAD = 0} or \code{PS_LIST_TAIL =
+-1}; negative indices are interpreted as relative to the end of the
+list.  The other two functions, \code{psListGetAndIncrement} and
+\code{psListGetAndDecrement} return the item under the iteration
+cursor before advancing to the next or previous item, respectively.
+In the event that the iteration cursor is at the tail of the list,
+\code{psListGetAndIncrement} shall return the tail item and then set
+the \code{cursor} to \code{NULL} and \code{offEnd} to \code{true}.  In
+the event that the iteration cursor is at the head of the list,
+\code{psListGetAndDecrement} shall return the head item and then set
+the \code{cursor} to \code{NULL} (and \code{offEnd} should already be
+\code{false}).  In the event that the iteration \code{cursor} is
+\code{NULL}, \code{psListGetAndIncrement} and
+\code{psListGetAndDecrement} shall return \code{NULL}, and advance the
+iteration \code{cursor} only if the intended direction places the
+cursor back on the list; otherwise a warning shall be generated, and
+no change shall be made.  If \code{psListGetAndDecrement} was called
+with \code{offEnd} as \code{true}, then \code{offEnd} shall also be
+toggled back to \code{false} to indicate that the \code{cursor} is no
+longer off the end of the list.
+\begin{prototype}
+bool psListRemove(psList *list, long location)
+bool psListRemoveData(psList *list, psPtr data);
+\end{prototype}
+A data item may be removed from the list with these functions.  For
+\code{psListRemove}, the value of \code{location} may be the numerical
+index or it may be one of the special values: \code{PS_LIST_HEAD} or
+\code{PS_LIST_TAIL}, which are defined as 0 and -1, respectively; a
+negative index is interpreted as relative to the end of the list.  For
+\code{psListRemoveData}, the data item to be removed is identified by
+matching the pointer value with \code{psPtr data}.  The functions
+return a value of \code{true} if the operation was successful, and
+\code{false} otherwise.  In both cases, if any iterators are currently
+pointing at the item to be removed, the item shall be removed and
+those iterators pointing at it shall be moved to the next, and the
+function shall return \code{true}.  If the item to be removed is not
+on the list, an error shall be generated and the function shall return
+\code{false}.
+\begin{prototype}
+psArray *psListToArray(const psList *list);
+psList  *psArrayToList(const psArray *array);
+\end{prototype}
+These two functions are available to convert between the
+\code{psList} and \code{psArray} containers.  These functions do not
+free the elements or destroy the input collection.  Rather, they
+increment the reference counter for each of the elements.
+\begin{prototype}
+psList *psListSort(psList *list, psComparePtrFunc func);
+\end{prototype}
+A list may be sorted using \code{psListSort}, which requires the
+specification of a comparison function to specify how the objects on
+the list should be sorted.  The motivation is primarily to be able to
+iterate on a sorted list of keys from a hash.  The \code{list} is
+sorted in-place.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Hash Tables}
+\hlabel{psHash}
+Hash tables are critical for quick retrieval of text-based data.  The
+concept is as follows: Given a large collection of text strings, it is
+inefficient to search for a particular entry by performing a basic
+string comparison on all entries until a match is found.  Even if a
+single list is sorted, we will still spend a substantial amount of
+time iterating across the entries in the list.  In a hash table, we
+define an operation, the hash function, which uses the bytes of the
+string to construct a numerical value, the hash value.  The hash value
+is defined to have a limited range of $N$ values.  The hash table
+consists of $N$ buckets, each of which contains a list of the strings
+whose hash value corresponds to the bucket number.  Searching for a
+specific string involves calculating the hash value for the string,
+going to the appropriate bucket, and searching through the
+corresponding list until the string is matched.
+For PSLib, we define a hash table and hash buckets as follows:
+\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.}
+%
+\begin{datatype}
+typedef struct {
+    long n;                             ///< number of buckets
+    psHashBucket **buckets;             ///< the buckets themselves
+    void *lock;                         ///< Optional lock for thread safety
+}} psHash;
+\end{datatype}
+%
+where \code{n} is the number of buckets defined for the hash functions, and
+\code{buckets} is an array of pointers to the individual buckets, each of which
+is defined by:
+%
+\begin{datatype}
+typedef struct psHashBucket {
+    char *key;                          ///< key for this item of data
+    void *data;                         ///< the data itself
+    struct psHashBucket *next;          ///< list of other possible keys
+} psHashBucket;
+\end{datatype}
+where each bucket contains the value of the \code{key}, a pointer to
+the \code{data}, and a pointer to the \code{next} list entry in the
+bucket (in the event that two or more keys have the same hash value).
+A hash table is created with the following function:
+\begin{prototype}
+psHash *psHashAlloc(long nalloc);
+\end{prototype}
+which allocates the space for the hash table, creating and
+initializing \code{n} hash buckets.
+The destructor for \code{psHash} must free all data associated with a complete hash table.
+A data item may be added to the hash table with the function:
+\begin{prototype}
+bool psHashAdd(psHash *hash, const char *key, psPtr data);
+\end{prototype}
+In this function, the value of the string \code{key} is used to
+construct the hash value, find the appropriate bucket set, and add the
+new element \code{data} to the list.  An existing element with the same
+value of \code{key} is destroyed using its registered destructor
+(\code{psMemBlock}). The return value of the function is a boolean
+defining the success or failure of the operation.
+The data associated with a given key may be found with the function:
+\begin{prototype}
+psPtr psHashLookup(const psHash *hash, const char *key);
+\end{prototype}
+which returns the data value pointed to by the element associated with
+\code{key}, or the value \code{NULL} if no match is found.  Similarly,
+a specific key may be removed (deleted) with the function:
+\begin{prototype}
+bool psHashRemove(psHash *hash, const char *key);
+\end{prototype}
+The function returns a value of \code{true} if the operation was
+successfull, and \code{false} otherwise.
+The function
+\begin{prototype}
+psList *psHashKeyList(const psHash *hash);
+\end{prototype}
+returns the complete list of defined keys associated with the
+\code{psHash} table as a linked list.
+\begin{prototype}
+psArray *psHashToArray(const psHash *hash);
+\end{prototype}
+This function places the data in a \code{psHash} into a \code{psArray}
+container.  This function does not free the elements or destroy the
+input collection.  Rather, it increments the reference counter for
+each of the elements.  The resulting array does not have any
+information about the has key values, and the order is not
+significant.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Pixel Lists}
+Usually an image mask is the best way to carry information about what
+pixels mean what.  However, in the case where the number of pixels in
+which we are interested is limited, it is more efficient to simply
+carry a list of pixels.  An example of this is in the image
+combination code, where we want to perform an operation on a
+relatively small fraction of pixels, and it is inefficient to go
+through an entire mask image checking each pixel.
+\begin{datatype}
+typedef struct {
+    int x;                      // x coordinate
+    int y;                      // y coordinate
+} psPixelCoord;
+typedef struct {
+    psU32 n;                    // Number in use
+    const psU32 nalloc;         // Number allocated
+    psPixelCoord *data;         // The pixel coordinates
+    void *lock;                         ///< Lock for thread safety
+} psPixels;
+\end{datatype}
+\begin{prototype}
+psPixels *psPixelsAlloc(psU32 nalloc);
+psPixels *psPixelsRealloc(psPixels *pixels, psU32 nalloc);
+\end{prototype}
+\code{psPixelsAlloc} and \code{psPixelsRealloc} provide dynamic
+allocation and reallocation in a manner analogous to those provided
+by \code{psVectorAlloc} and \code{psVectorRealloc}.
+\begin{prototype}
+psPixels *psPixelsCopy(psPixels *out, const psPixels *pixels);
+psPixels *psPixelsConcatenate(psPixels *out, const psPixels *pixels);
+\end{prototype}
+\code{psPixelsCopy} shall copy the contents of \code{pixels} to the
+\code{out}.  In the event that \code{out} is \code{NULL}, a new
+\code{psPixels} shall be allocated, and the contents of \code{pixels}
+simply copied in.  If \code{pixels} is \code{NULL}, the function shall
+generate an error and return \code{NULL}.
+\code{psPixelsConcatenate} shall concatenate the \code{pixels} onto
+\code{out}.  In the event that \code{out} is \code{NULL}, the function
+performs a \code{psPixelsCopy}, returning the copy.  If \code{pixels}
+is \code{NULL}, the function shall generate an error and return
+\code{NULL}.  The function shall take care to ensure that there are no
+duplicate pixels in \code{out} (since the order in which the pixels
+are stored is not important, the values may be sorted, allowing the
+use of a faster algorithm than a linear scan).
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{BitSets}
+BitSets are required in order to turn options on and off.  We require
+the capability to have a bitset of arbitrary length (i.e., not limited
+by the length of a \code{long}, say).  The \code{psBitSet} structure
+is defined below.  Note that the entry \code{bits} is an array of type
+\code{char} storing the bits as bits of each byte in the array, with 8
+bits available for each byte in the array.  Also note that the
+constructor is passed the number of required bits, which implies that
+\code{ceil(n/8)} bytes must be allocated.  The bitset structure is
+define by:
+\begin{datatype}
+typedef struct {
+    long n;                             ///< Number of chars that form the bitset
+    char *bits;                         ///< The bits
+    void *lock;                         ///< Optional lock for thread safety
+}} psBitSet;
+\end{datatype}
+We also require the corresponding constructor and destructor:
+\begin{prototype}
+psBitSet *psBitSetAlloc(long nalloc);
+\end{prototype}
+where \code{n} is the requested number of bits.
+Several basic operations on bitsets are required:
+\begin{itemize}
+\item Set a bit;
+\item Check if a bit is set; and
+\item \code{OR}, \code{AND} and \code{XOR} two bitsets.
+\item \code{NOT} a bitset.
+\end{itemize}
+The corresponding APIs are defined below:
+\begin{prototype}
+psBitSet *psBitSetSet(psBitSet *bitSet, long bit);
+psBitSet* psBitSetClear(psBitSet *bitSet, long bit);
+psBitSet *psBitSetOp(psBitSet *outBitSet, const psBitSet *inBitSet1, const char *operator, const psBitSet *inBitSet2);
+psBitSet *psBitSetNot(psBitSet *outBitSet, const psBitSet *inBitSet);
+bool psBitSetTest(const psBitSet *bitSet, long bit);
+char *psBitSetToString(const psBitSet* bitSet);
+\end{prototype}
+\code{psBitSetSet} sets the specified \code{bit} in the
+\code{psBitSet}, and returns the updated bitset.  The input bitset
+will be modified.
+\code{psBitSetClear} clears the specified \code{bit} in the \code{bitSet}
+and returns the updated bitset.  The input bitset will be modified.
+\code{psBitSetOp} returns the \code{psBitSet} that is the result of
+performing the specified \code{operator} (one of \code{"AND"},
+\code{"OR"}, or \code{"XOR"}) on \code{inBitSet1} and \code{inBitSet2}.
+If the output bitset \code{outBitSet} is \code{NULL}, it is created by
+the function.
+\code{psBitSetNot} applies a unary \code{NOT} to a bitset, placing the
+answer in the bitset \code{out}, or creating a new bitset if
+\code{out} is \code{NULL}.
+\code{psBitSetTest} returns a true value if the specified \code{bit}
+is set; otherwise, it returns a false value.
+Finally, \code{psBitSetToString} returns a string representation of
+the specified \code{bits}.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Metadata}
+\label{sec:metadata}
+\subsubsection{Conceptual Overview}
+Within PSLib, we provide a data structure to carry metadata and
+mechanisms to manipulate the metadata.  Metadata is a general concept
+that requires some discussion.  In any data analysis task, the
+ensemble of all possible data may be divided into two or three
+classes: there is the specific data of interest, there is data which
+is related or critical but not the primary data of interest, and there
+is all of the other data which may or may not be interesting.  For
+example, consider a simple 2D image obtained of a galaxy from a CCD
+camera on a telescope.  If you want to study the galaxy, the specific
+data of interest is the collection of pixels.  There are a variety of
+other pieces of data which are closely related and crucial to
+understanding the data in those pixels, such as the dimensions of the
+image, the coordinate system, the time of the image, the exposure
+time, and so forth.  Other data may be known which may be less
+critical to understanding the image, but which may be interesting or
+desired at a later date.  For example, the observer who took the
+image, the filter manufacturer, the humidity at the telescope, etc.
+Formally, all of the related data which describe the principal data of
+interest are metadata.  Note that which piece is the metadata and
+which is the data may depend on the context.  If you are examining the
+pixels in an image, the coordinate and flux of an object may be part
+of the metadata.  However, if you are analyzing a collection of
+objects extracted from an image, you may consider then pixel data
+simply part of the metadata associated with the list of objects.
+There are various ways to handle metadata vs data within a programming
+environment.  In C, it is convenient to use structures to group
+associated data together.  One possibility is to define the metadata
+as part of the associated data structure.  For example, the image data
+structure would have elements for all possible associated measurement.
+This approach is both cumbersome (because of the large number metadata
+types), impractical (because the full range of necessary metadata is
+difficult to know in advance) and inflexible (because any change in
+the collection of metadata requires addition of new structure elements
+and recompilation).
+An alternative is to place the metadata in a generic container and use
+lookup mechanisms to extract the appropriate metadata when needed.  An
+example of this is would be a text-based FITS header for an image read
+into a flat text buffer.  In this implementation, metadata lookup
+functions could return the current value of, for example, NAXIS1 (the
+number of columns of the image) by scanning through the header buffer.
+This method has the benefits of flexibility and simplicity of
+programming interface, but it has the disadvantage that all metadata
+is accessed though this lookup mechanism.  This may make the code less
+readable and it may slow down the access.
+PSLib implements an intermediate solution to this problem.  We specify
+a flexible, generic metadata container and access methods.  Data types
+which require association with a general collection of metadata should
+include an entry of this metadata type.  However, a subset of metadata
+concepts which are basic and frequently required may be placed in the
+coded structure elements.  This approach allows the code to refer to
+the basic metadata concepts as part of the data structure (ie,
+\code{image.nx}), but also allows us to provide access to any
+arbitrary metadata which may be generated.  As a practical matter, the
+choice of which entries are only in the metadata and which are part of
+the explicit structure elements is rather subjective.  Any data
+elements which are frequently used should be put in the structure;
+those which are only infrequently needed should be left in the generic
+metadata.
+There are some points of caution which must be noted.  Any
+manipulation of the data should be reflected in the metadata where
+appropriate.  This is always an issue of concern.  For example,
+consider an image of dimensions \code{nx, ny}.  If a function extracts
+a subraster, it must change the values of \code{nx, ny} to match the
+new dimensions.  What should it do to the corresponding metadata?
+Clearly, it should change the corresponding value which defines
+\code{nX, nY}.  However, it is not quite so simple: there may be other
+metadata values which depend on those values.  These must also be
+changed appropriately.  What if the metadata element points to a
+copy of the metadata which may be shared by other representations of
+the image?  These must be treated differently because the change would
+invalidate those other references.  Care must be taken, therefore,
+when writing functions which operate on the data to consider all of
+the relevant metadata entries which must also be updated.
+A related issue is the definition of metadata names.  Entries in a
+structure have the advantage of being hardwired: every instance of
+that structure will have the same name for the same entry.  This is
+not necessarily the case with a more flexible metadata container.  The
+image exposure time is a notorious example in astronomy.  Different
+observatories use different header keywords (ie, metadata names) for
+the same concept of the exposure time (\code{EXPTIME},
+\code{EXPOSURE}, \code{OPENTIME}, \code{INTTIME}, etc).  Any system
+which operates on these metadata needs to address the issue of
+identifying these names.  This issue seems like an argument for
+hardwiring metadata in the structure, but in fact it does not present
+such a strong case.  If the metadata are hardwired, some function will
+still have to know how to interpret the various names to populate the
+structure.  The concept can still be localized with generic metadata
+containers by including abstract metadata names within the code which
+are tied to the various implementations-specific metadata names.
+\subsubsection{Metadata Representation}
+\begin{figure}
+\psfig{file=Metadata,width=6.5in}
+\caption{Metadata Structures\label{fig:metadata}}
+\end{figure}
+This section addresses the question of how \PS{} metadata should be
+represented in memory, not how it should be represented on disk.
+We define an item of metadata with the following structure:
+\filbreak
+\begin{datatype}
+typedef struct {
+    const psS32 id;                     ///< unique ID for this item
+    char *name;                         ///< Name of item
+    psMetadataType type;                ///< type of this item
+    const union {
+        psS32 S32;                      ///< integer data
+        psF32 F32;                      ///< floating-point data
+        psF64 F64;                      ///< double-precision data
+        psList *list;                   ///< psList entry
+        psMetadata *md;                 ///< psMetadata entry
+        psPtr V;                        ///< other type
+    } data;                             ///< value of metadata
+    char *comment;                      ///< optional comment ("", not NULL)
+} psMetadataItem;
+\end{datatype}
+The \code{id} is a unique identifier for this item of metadata;
+experience shows that such tags are useful.  The entry \code{name}
+specifies the name of the metadata item.  The value of the metadata is
+given by the union \code{data}, and may be of type \code{psS32},
+\code{psF32}, \code{psF64}, or an arbitrary rich structure pointed at
+by the \code{void} pointer \code{V}.  A character string comment
+associated with this metadata item may be stored in the element
+\code{comment}. The \code{type} entry specifies how to interpret the
+type of the data being represented, given by the enumerated type
+\code{psMetadataType}:
+%
+\filbreak
+\begin{datatype}
+typedef enum {                         ///< type of item.data is:
+    PS_META_S32  = PS_TYPE_S32,        ///< psS32 primitive data.
+    PS_META_F32  = PS_TYPE_F32,        ///< psF32 primitive data.
+    PS_META_F64  = PS_TYPE_F64,        ///< psF64 primitive data.
+    PS_META_BOOL = PS_TYPE_BOOL,       ///< psBool primitive data.
+    PS_META_LIST = 0x10000,            ///< List data (Stored as item.data.list).
+    PS_META_STR,                       ///< String data (Stored as item.data.V).
+    PS_META_META,                      ///< Metadata (Stored as item.data.md).
+    PS_META_VEC,                       ///< Vector data (Stored as item.data.V).
+    PS_META_IMG,                       ///< Image data (Stored as item.data.V).
+    PS_META_HASH,                      ///< Hash data (Stored as item.data.V).
+    PS_META_LOOKUPTABLE,               ///< Lookup table data (Stored as item.data.V).
+    PS_META_JPEG,                      ///< JPEG data (Stored as item.data.V).
+    PS_META_PNG,                       ///< PNG data (Stored as item.data.V).
+    PS_META_ASTROM,                    ///< Astrometric coefficients (Stored as item.data.V).
+    PS_META_TIME,                      ///< psTime object (Stored as item.data.V).
+    PS_META_UNKNOWN,                   ///< Other data (Stored as item.data.V).
+    PS_META_MULTI                      ///< Used internally, do not create a metadata item of this type.
+} psMetadataType;
+\end{datatype}
+The macro \code{PS_META_IS_PRIMITIVE(psMetadataType.type)} returns
+true if the type is one of the primitive data types (S32, F64, etc).
+In such a case, the data value is directly available.  Otherwise, a
+pointer to the data is available.
+A collection of metadata is represented by the \code{psMetadata} structure:
+\begin{datatype}
+typedef struct {
+    psList *list;                       ///< list of psMetadataItem
+    psHash *hash;                       ///< hash table of the same metadata
+    void *lock;                         ///< Optional lock for thread safety
+}} psMetadata;
+\end{datatype}
+The type \code{psMetadata} is a container class for metadata. Note
+that there are in fact \emph{two} representations of the metadata
+(each \code{psMetadataItem} appears on both).  The first
+representation employs a doubly-linked list that allows the order of
+the metadata to be preserved (e.g., if FITS headers are read in a
+particular order, they should be written in the same order).  The
+second representation employs a hash table which allows fast look-up
+given a specific metadata keyword.
+Certain metadata names (such as the FITS keywords \code{COMMENT} and
+\code{HISTORY} in a FITS header) may be repeated with different
+values.  In such a case, the \code{psMetadata.list} structure contains
+the entries in their original sequence with duplicate keys.  The
+\code{psMetadata.hash} entries, which are required to have unique
+keys, would have a single entry with the keyword of the repeated key,
+with the value of \code{psMetadataType} set to \code{PS_META_MULTI},
+and the \code{psMetadataItem.data} element pointing to a \code{psList}
+containing the actual entries.  If \code{psMetadataItemAlloc} is
+called with the type set to \code{PS_META_MULTI}, such a repeated key
+is created.  In this case, the data value passed to
+\code{psMetadataItemAlloc} (the quantity in ellipsis) must be
+\code{NULL}.  An empty \code{psMetadataItem} with the given keyword is
+created to hold future entries of that keyword.
+As a convenience to the user, the following type-specific functions are
+also defined:
+\begin{prototype}
+psMetadataItem* psMetadataItemAllocStr(const char* name, const char* comment, const char* value);
+psMetadataItem* psMetadataItemAllocF32(const char* name, const char* comment, psF32 value);
+psMetadataItem* psMetadataItemAllocF64(const char* name, const char* comment, psF64 value);
+psMetadataItem* psMetadataItemAllocS32(const char* name, const char* comment, psS32 value);
+psMetadataItem* psMetadataItemAllocBool(const char* name, const char* comment, bool value);
+psMetadataItem* psMetadataItemAllocPtr(const char* name, psMetadataType type, const char* comment, psPtr value);
+\end{prototype}
+\subsubsection{Metadata APIs}
+\begin{prototype}
+psMetadata *psMetadataAlloc(void);
+\end{prototype}
+The constructor for the collection of metadata, \code{psMetadata},
+simply returns an empty metadata container (employing the constructors
+for the doubly-linked list and hash table).  The destructor needs to
+free each of the \code{psMetadataItem}s.
+\begin{prototype}
+psMetadataItem *psMetadataItemAlloc(const char *name, psMetadataType type, const char *comment, ...);
+psMetadataItem *psMetadataItemAllocV(const char *name, psMetadataType type, const char *comment, va_list list);
+\end{prototype}
+The allocator for \code{psMetadataItem} returns a full
+\code{psMetadataItem} ready for insertion into the \code{psMetadata}.
+The \code{name} entry specifies the name to use for this metadata
+item, and may include \code{sprintf}-type formating codes.  The
+\code{comment} entry is a fixed string which is used for the comment
+associated with this metadata item.  The metadata data and the
+arguments to the \code{name} formatting codes are passed, in that
+order (metadata pointer first), to \code{psMetadataItemAlloc} as
+arguments following the comment string.  The data must be a pointer
+for any data types which are stored in the element \code{data.void},
+while other data types are passed as numeric values.  The argument
+list must be interpreted appropriately by the \code{va_list} operators
+in the function.
+\begin{prototype}
+bool psMetadataAddItem(psMetadata *md, const psMetadataItem *item, psS32 location, psS32 flags);
+bool psMetadataAdd(psMetadata *md, int location, const char *name, int format, const char *comment, ...);
+bool psMetadataAddV(psMetadata *md, int location, const char *name, int format, const char *comment,
+                    va_list list);
+\end{prototype}
+Items may be added to the metadata in one of two ways --- firstly, an
+item may be added by appending a \code{psMetadataItem} which has
+already been created; and secondly by directly providing the data to
+be appended.  In both cases, the return value defines the success
+(\code{true}) or failure of the operation.  The second function,
+\code{psMetadataAdd} takes a pointer or value which is interpreted by
+the function using variadic argument interpretation.  The third
+version is the \code{va_list} version of the second function.  All
+three functions take a parameter, \code{location}, which specifies
+where in the list to place the element, following the conventions for
+the \code{psList}.  The entry \code{mode} for \code{psMetadataAddItem}
+is a bit mask constructed by OR-ing the allowed option flags (eg,
+\code{PS_META_REPLACE}) which specify minor variations on the
+behavior.  The \code{format} entry, which specifies both the metadata
+type and the optional flags, is constructed by bit-wise OR-ing the
+appropriate \code{psMetadataType} and allowed option flags.  Care
+should be taken not to leak memory when appending an item for which
+the key already exists in the metadata (and is not
+\code{PS_META_MULTI}).
+%
+\begin{datatype}
+typedef enum {                          ///< option flags for psMetadata functions
+    PS_META_DEFAULT         = 0,        ///< default behavior (0x0000) for use in mode above
+    PS_META_REPLACE         = 0x1000000 ///< allow entry to be replaced
+    PS_META_DUPLICATE_OK    = 0x2000000 ///< allow duplicate entries
+    PS_META_NULL            = 0x4000000 ///< psMetadataItem.data is a NULL value
+} psMetadataFlags;
+\end{datatype}
+The functions above take option flags which modify the behavior when
+metadata items are added to the metadata list.  These flags must be
+bit-exclusive of those used above for the \code{psMetadataTypes}.  The
+flags have the following meanings:
+\code{PS_META_DEFAULT}: This is the zero bit mask, to allow the
+default behavior for \code{psMetadataAddItem} above.  If this is OR-ed
+with a \code{psMetadataType}, the result is as if no OR-ing took
+place.
+\code{PS_META_REPLACE}: Replace an existing, unique entry. If the
+given metadata item exists in the metadata collection, and is not of
+type \code{PS_META_MULTI}, then the item replaces the existing entry.
+\code{PS_META_DUPLICATE_OK}: Allow the new metadata item key to be a
+duplicate (ie, \code{PS_META_MULTI}).  If an existing item with the
+same key is already \code{PS_META_MULTI}, the new item is added to the
+\code{PS_META_MULTI} list.  If the existing item is not
+\code{PS_META_MULTI}, a \code{PS_META_MULTI} list is created to
+contain both the existing item and the new item.  The original entry's
+location on the psMetadata.list must be maintained.
+\code{PS_META_NULL}:  Indicates that \code{psMetadataItem.data} should be
+ignored and that the the current value is ``NULL'' or undefined.  The
+\code{psMetadataItem} must have a proper \code{type} set and it's \code{data}
+field shall have a valid value.  e.g. A \code{type} of \code{PS_META_STR} would
+require that 's \code{data} is set to \code{NULL}.
+There are several of cases to handle for duplication of an existing
+key by a new key, some identified above.  The following situations
+must also be handled:
+If the new key already exists, but is not \code{PS_META_MULTI}, and
+the new item is not flagged as either \code{PS_META_DUPLICATE_OK} or
+\code{PS_META_REPLACE}, an error is raised.
+If the new key already exists, and the existing item is
+\code{PS_META_MULTI}, the new item is added to the MULTI list.  Note
+that if the new item is also of type \code{PS_META_MULTI}, no action
+is taken, but a successful exit status is returned (the action of
+adding a \code{PS_META_MULTI} item to the metadata is equivalent to
+setting that key to be tagged as \code{PS_META_MULTI}.  If it is
+{\em already} \code{PS_META_MULTI}, this effect has already been
+achieved).
+An example of code to use these metadata APIs to generate the
+structure seen in Figure~\ref{fig:metadata} is given below.
+\begin{verbatim}
+md = psMetadataAlloc();
+psMetadataAdd(md, PS_LIST_TAIL, "SIMPLE",   PS_META_BOOL, "basic fits",            TRUE);
+psMetadataAdd(md, PS_LIST_TAIL, "BLANK",    PS_META_S32,  "invalid pixel data",    -32768);
+psMetadataAdd(md, PS_LIST_TAIL, "DATE-OBS", PS_META_STR,  "observing date UT", "   2004-6-16");
+psMetadataAdd(md, PS_LIST_TAIL, "COMMENT",  PS_META_LIST, "head of comment block", NULL);
+psMetadataAdd(md, PS_LIST_TAIL, "COMMENT",  PS_META_STR,  "",                      "DATA");
+psMetadataAdd(md, PS_LIST_TAIL, "COMMENT",  PS_META_STR,  "",                      "PARAMS");
+psMetadataAdd(md, PS_LIST_TAIL, "EXPTIME",  PS_META_F32,  "exposure time (sec)",   1.05);
+psMetadataAdd(md, PS_LIST_TAIL, "COMMENT",  PS_META_STR,  "",                      "FOO");
+cell = psMetadataAlloc();
+psMetadataAdd(cell, PS_LIST_TAIL, "EXTNAME",  PS_META_STR,  "",                    "CCD00");
+psMetadataAdd(cell, PS_LIST_TAIL, "BIASNAME", PS_META_STR,  "",                    "BSEC-00");
+psMetadataAdd(cell, PS_LIST_TAIL, "CHIP",     PS_META_STR,  "",                    "CHIP.00");
+psMetadataAdd(md,   PS_LIST_TAIL, "CELL.00",  PS_META_META, "",                    cell);
+cell = psMetadataAlloc();
+psMetadataAdd(cell, PS_LIST_TAIL, "EXTNAME",  PS_META_STR,  "",                    "CCD01");
+psMetadataAdd(cell, PS_LIST_TAIL, "BIASNAME", PS_META_STR,  "",                    "BSEC-01");
+psMetadataAdd(cell, PS_LIST_TAIL, "CHIP",     PS_META_STR,  "",                    "CHIP.01");
+psMetadataAdd(md,   PS_LIST_TAIL, "CELL.01",  PS_META_META, "",                    cell);
+\end{verbatim}
+The following code shows how to use the APIs to replace one of these values:
+\begin{verbatim}
+psMetadataAdd(md, PS_LIST_TAIL, "EXPTIME",  PS_META_F32 | PS_REPLACE,  "new exposure time (sec)",   2.05);
+\end{verbatim}
+As a convenience to the user, the following type-specific functions
+are specified:
+\begin{prototype}
+bool psMetadataAddStr(psMetadata* md, psS32 location, const char* name, const char* comment,
+                        const char* value);
+bool psMetadataAddS32(psMetadata* md, psS32 location, const char* name, const char* comment, psS32 value);
+bool psMetadataAddF32(psMetadata* md, psS32 location, const char* name, const char* comment, psF32 value);
+bool psMetadataAddF64(psMetadata* md, psS32 location, const char* name, const char* comment, psF64 value);
+bool psMetadataAddBool(psMetadata* md, psS32 location, const char* name, const char* comment, bool value);
+bool psMetadataAddPtr(psMetadata* md, psS32 location, const char* name, psMetadataType type,
+                        const char* comment, psPtr value);
+\end{prototype}
+Items may be removed from the metadata by specifying a key or a
+location in the list.  If the value of \code{name} is \code{NULL}, the
+value of \code{location} is used.  If the value of \code{name} is not
+\code{NULL}, then \code{location} must be set to
+\code{PS_LIST_UNKNOWN}.  If the key matches a metadata item, the item
+is removed from the metadata and \code{true} is returned; otherwise,
+\code{false} is returned.  If the key is not unique, then \emph{all}
+items corresponding to the key are removed, and \code{true} is
+returned.
+%
+\begin{prototype}
+bool psMetadataRemove(psMetadata *md, int location, const char *key);
+\end{prototype}
+Items may be found within the metadata by providing a key.  In the
+event that the key is non-unique, the first item is returned.
+\begin{prototype}
+psMetadataItem *psMetadataLookup(const psMetadata *md, const char *key);
+\end{prototype}
+Several utility functions are provided for simple cases.  These
+functions perform the effort of casting the data to the appropriate
+type.  The numerical functions shall return 0.0 if their key is not
+found.  If the pointer value of \code{status} is not \code{NULL}, it
+is set to reflect the success or failure of the lookup.
+\begin{prototype}
+psPtr psMetadataLookupStr(bool *status, const psMetadata *md, const char *key);
+psS32 psMetadataLookupS32(bool *status, const psMetadata *md, const char *key);
+psF32 psMetadataLookupF32(bool *status, const psMetadata *md, const char *key);
+psF64 psMetadataLookupF64(bool *status, const psMetadata *md, const char *key);
+bool psMetadataLookupBool(bool *status, const psMetadata *md, const char *key);
+psPtr psMetadataLookupPtr(bool *status, const psMetadata *md, const char *key);
+\end{prototype}
+Items may be retrieved from the metadata by their entry position.  The
+value of which specifies the desired entry in the fashion of
+\code{psList}.
+\begin{prototype}
+psMetadataItem *psMetadataGet(const psMetadata *md, int location);
+\end{prototype}
+The metadata list component may be iterated over by using a
+\code{psMetadataIterator} in a fashion equivalent to the
+\code{psListIterator}:
+\begin{datatype}
+typedef struct {
+    psListIterator* iter;              ///< iterator for the psMetadata's psList
+    regex_t* regex;                     ///< the subsetting regular expression
+} psMetadataIterator;
+\end{datatype}
+The iterator may be set to a location in the \code{psMetadata} list,
+and the user may get the previous or next item in the list relative to
+that location.  \code{psMetadataGetNext} has the ability to match the
+key using a POSIX \code{regex}, e.g., if the user only wants to
+iterate through \code{IPP.machines.sky} and doesn't want to bother
+with \code{IPP.machines.detector}.  The iterator should iterate over
+every item in the metadata list, even those that are contained in a
+\code{PS_META_LIST}.  The value \code{iterator} specifies the iterator
+to be used.  In setting the iterator, the position of the iterator is
+defined by \code{location}, which follows the conventions of the
+\code{psList} iterators.
+\begin{prototype}
+psMetadataIterator *psMetadataIteratorAlloc(psMetadata *md, int location, const char *regex);
+bool psMetadataIteratorSet(psMetadataIterator *iterator, int location);
+psMetadataItem *psMetadataGetAndIncrement(psMetadataIterator *iterator);
+psMetadataItem *psMetadataGetAndDecrement(psMetadataIterator *iterator);
+\end{prototype}
+Metadata items may be printed to an open file descriptor based on a
+provided format.  The format string is an sprintf format statement
+with exactly one \% formatting command.  If the metadata item type is
+a numeric type, this formatting command must also be numeric, and type
+conversion performed to the value to match the format type.  If the
+metadata item type is a string, the formatting command must also be
+for a string (\%s type of command).  If the metadata type is any other
+data type, printing is not allowed.
+\begin{prototype}
+bool psMetadataItemPrint(FILE *fd, const char *format, const psMetadataItem *item);
+\end{prototype}
+\subsubsection{Configuration files}
+\label{sec:configspec}
+It will be necessary for the \PS{} system, in order to load
+pre-defined settings, to parse a configuration file into a
+\code{psMetadata} structure.  This shall be performed by the
+function \code{psMetadataConfigParse}, as described below.
+\begin{prototype}
+psMetadata *psMetadataConfigParse(psMetadata *md, int *nFail, const char *filename, bool overwrite);
+\end{prototype}
+Given a metadata container, \code{md}, and the name of a configuration
+file, \code{filename}, \code{psMetadataConfigParse} shall parse the
+configuration file, placing the contained key/type/value/comment quads
+into the metadata, and returning a pointer to the metadata structure.
+The number of lines that failed to parse is returned in \code{nFail}.
+Multiple specifications of a key that haven't been declared (see
+below) are overwritten if and only if \code{overwrite} is \code{true}.
+If the metadata container is \code{NULL}, it shall be allocated.
+On error, the function shall return \code{NULL}.
+It is also useful to be able to convert a \code{psMetadata} structure into the
+Configuration File format for debugging purposes and to enable persistent
+configuration.
+\begin{prototype}
+char *psMetadataConfigFormat(psMetadata *md);
+bool psMetadataConfigWrite(psMetadata *md, const char *filename);
+\end{prototype}
+The \code{psMetadataConfigFormat} function converts a \code{psMetadata}
+structure (including any nested \code{psMetadata}) into a Configuration File
+formatted string.  A \code{NULL} shall be returned on error.  The
+\code{psMetadataConfigWrite} behaves the same as \code{psMetadataConfigFormat}
+except that the string is written out to \code{filename}.  \code{false} is
+returned on failure.
+\paragraph{Comments}
+The configuration file shall consist of plain text with
+key/type/value/comment quads on separate lines.  Blank lines,
+including those consisting solely of whitespace (both spaces and
+tabs), shall be ignored, as shall lines that commence with the comment
+character (a hash mark, \code{#}), either immediately at the start of
+the line, or preceded by whitespace.  The key/type/value/comment quads
+shall all lie on a single line, separated by whitespace.
+The key shall be first, possibly preceded on the line by whitespace
+which should not form part of the key.
+\paragraph{NULL values}
+The ``value'' of a quad may be declare to be undefined with the \code{NULL}
+keyword.  \code{NULL} is allowed to co-exist with a ``comment'' and may be
+surrounded by whitespace.  Any non-whitespace character will cause of the
+``value'' to be interpreted as a string.
+\begin{verbatim}
+foo     STR     NULL    # string with a NULL value
+bar     STR     NULL a  # string with a value of "NULL a"
+\end{verbatim}
+\paragraph{Types}
+\subparagraph{Scalar \& Vector}
+Next, to assist the casting of the value, shall be a string identifying the
+type of the value, which shall correspond to one of the simple types supported
+in \code{psMetadata}: \code{STRING,BOOL,S32,F32,F64}; \code{STR} may be used to
+abbreviate \code{STRING}; valid time types are \code{UTC,UT1,TAI,TT}.
+\tbd{May, in the future, require more types, including U8,S16,C64,
+which will also necessitate updating the definition of psMetadata.}
+The value shall follow the type: strings may consist of multiple words, and
+shall have all leading and trailing whitespace removed; booleans shall simply
+be either \code{T} or \code{F}.  Time type values will be in the ISO8601
+compatible format of "YYYY-MM-DDTHH:MM:SS,sZ".  When parsed, time types shall
+be represented as a \code{psTime} object.
+Following the value may be an optional comment, preceded by a comment
+character (a hash mark, \code{#}), which in the case of a string
+value, serves to mark the end of the value, and for other types serves
+to identify the comment to the reader.  Only one comment character may
+be present on any single line (i.e., neither strings nor comments are
+permitted to contain the comment character).  The comment may consist
+of multiple words, and shall have leading and trailing whitespace
+removed.
+One wrinkle is the specification of vectors.  Keys for which the value
+is to be parsed as a vector shall be preceded immediately by a
+``vector symbol'', which we choose to be the ``at'' sign, \code{@}.
+In this case, the type shall be interpreted as the type for the
+vector, which may be any of the signed or unsigned integer or floating
+point types (\code{U8,U16,U32,U64,S8,S16,S32,S32,S64,F32,F64}) but not
+the complex floating point types; and the value shall consist of
+multiple numbers, separated either by a comma or whitespace.  These
+values shall populate a \code{psVector} of the appropriate type in the
+order in which they appear in the configuration file.
+\tbd{May add complex types, likely to be specified with values such as
+.23+4.56i in the future.}
+\tbd{May add null, Not-a-Number (NaN), de-normalized, underflow, overflow,
+and/or +/-infinity values for selected types.}
+\subparagraph{MULTI}
+An additional hurdle is the specification of keys that may be non-unique (such
+as the \code{COMMENT} keyword in a FITS header).  These keys shall be specified
+in the configuration file as non-unique with a \code{MULTI} declaration.  In
+the form \code{[keyword] MULTI}.  No other data may be provided on this line,
+though a comment, preceded by the comment marker, is valid.  A warning shall
+be produced when a key which has not been specified to be non-unique is
+repeated; in this case, the former value shall be overwritten if
+\code{overwrite} is \code{true}, otherwise the line shall be ignored and
+counted as one that could not be parsed.  It should be noted that non-unique
+keys may be of mixed type (even the \code{TYPE} and \code{METADATA} complex
+types). For example:
+\begin{verbatim}
+comment     MULTI   # a comment
+comment     STR     some string
+comment     F32     1.23456
+comment     BOOL    T
+\end{verbatim}
+If a line does not conform to the rules laid out here, a warning shall
+be generated, it shall be ignored and counted as a line that could not
+be parsed.  The total number of lines that were not able to be parsed
+(including those that were ignored because \code{overwrite} is
+\code{false}, and any other parsing problems, but not including blank
+lines and comment lines) shall be returned by the function in the
+argument \code{nFail}.
+Here are some examples of lines of a valid configuration file:
+\filbreak
+\begin{verbatim}
+Double     F64     1.23456789      # This is a comment
+Float    F32 0.98765 # This is a comment too
+String  STR This is the string that forms the value #comment
+ # This is a comment line and is to be ignored
+boolean     BOOL    T # The value of `boolean' is `true'
+@primes U8  2,3 5 7,11,13 17 #   These are prime numbers
+comment MULTI # The rest of this line is ignored, but `comment' is set to be non-unique
+comment STR This
+comment STR     is
+comment STR       a
+comment STR        non-unique
+comment STR                  key
+Float F64 1.23456 # This generates a warning, and, if `overwrite' is `false', is ignored
+\end{verbatim}
+Of course, a real configuration file should look much nicer to humans
+than the above example, but PSLib must be able to parse such ugly
+files.
+\paragraph{Complex Types}
+\subparagraph{TYPE}
+We support a modest tree structure by defining a reserved keyword \code{TYPE}.
+Any line in the config file which starts with the word \code{TYPE} shall be
+interpreted as defining a new valid type.  The defined type name follows the
+word \code{TYPE}, and is in turn followed by an arbitrary number of words.
+These words are to be interpreted as the names of an embedded \code{psMetadata}
+entry, where the values are given on any line which (following the \code{TYPE}
+definition) employs the new type name.  For example, a new type may be defined
+as:
+\begin{verbatim}
+TYPE      CELL   EXTNAME   BIASSEC  CHIP
+CELL.00   CELL   CCD00     BSEC-00  CHIP.00
+CELL.01   CELL   CCD01     BSEC-01  CHIP.00
+\end{verbatim}
+When \code{psMetadataConfigParse} encounters the \code{TYPE} line, it
+should construct a \code{psMetadata} container and fill it with
+\code{psMetadataItems} having the names \code{EXTNAME, BIASSEC, CHIP},
+with type \code{PS_META_STR}, but data allocated.  When it next
+encounters an entry of type \code{CELL}, it should then use the given
+name (e.g., \code{CELL.00}) for the \code{psMetadataItem}, and copy
+the \code{psMetadata} data onto the \code{psMetadataItem.data.md}
+entry, filling in the values from the rest of the line (\code{CCD00,
+BSEC-00, CHIP.00}).  This hierarchical structure is illustrated in
+Figure~\ref{fig:metadata}.
+\subparagraph{METADATA}
+Another way to form a tree-like structure is to directly define a
+\code{psMetadata} entry using a sequence of successive lines to define the
+values of the \code{psMetadataItem} entries.  The initial line defines the new
+\code{psMetadata} entry and its name.  The following lines have the same format
+as the other metadata config file entries.  The sequence is terminated with a
+line with a single word \code{END}.  For example, a metadata entry may be
+defined as:
+\begin{verbatim}
+CELL      METADATA
+ EXTNAME   STR   CCD00
+ BIASSEC   STR   BSEC-00
+ CHIP      STR   CHIP.00
+ NCELL     S32   24
+END
+\end{verbatim}
+\paragraph{Scoping Rules}
+A simple set of ``Scoping Rules'' are required to properly parse a
+configuration file.  ``Scope'' refers to the current ``level'' of
+\code{METADATA} that a statement appears in.  Statements that are not contained
+in a nested \code{METADATA} are said to be in the ``Top level scope''.  Each
+level of nested \code{METADATA} statements create a new ``lower level scope''.
+\begin{itemize}
+\item
+Variable names are unique only to the current level of scope.
+\item
+non-unique keywords (\code{MULTI}) apply only to the current scope.  i.e. They
+are invalid in ``higher'' or ``lower'' level scopes.
+\item
+\code{TYPE} declarations apply only to the current scope.
+\item
+\code{METADATA} declarations must begin and end in the same scope.  i.e.  They
+may not be declared and end in two different nested METADATA and the same
+depth.
+\end{itemize}
+A series of test inputs is contained in
+\S\ref{sec:configtest}.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsubsection{Lookup Tables}
+Lookup tables store a variety of values indexed on a certain column.
+An example is for storing the difference between UT1 and UTC, and the
+polar motion vector as a function of date.
+One of the key functionalities of a lookup table is to read data from
+an ordinary text file into an array of vectors.  This functionality is
+generally useful, and so we specify a separate function that may be
+called independently:
+\begin{prototype}
+psArray *psVectorsReadFromFile(const char *filename, const char *format);
+\end{prototype}
+\code{psVectorsReadFromFile} shall return an array of
+\code{psVector}s, read from the specified \code{filename}.  The file
+shall be plain text, consisting of an identical number of columns on
+each line, with the values separated by whitespace.  Lines commencing
+with a comment character (the pound sign, \code{#}) and blank lines
+shall be ignored.  The \code{format} is a \code{scanf}-like format
+which specifies the number of columns in the file, as well as their
+types.  The following formats shall be defined: \code{\%d} for psS32,
+\code{\%ld} for psS64, \code{\%f} for psF32, and \code{\%lf} for
+psF64.  A star (\code{*}) in the format shall indicate that the column
+is to be skipped.
+\begin{datatype}
+typedef struct {
+    const char *filename;               ///< File from which data is to be read
+    const char *format;                 ///< scanf-like format string for file
+    long indexCol;                      ///< Column of the index vector (starting at zero)
+    psVector *index;                    ///< Index values
+    psArray *values;                    ///< Corresponding values: an array of vectors
+    const psF64 validFrom, validTo;     ///< Range of validity
+} psLookupTable;
+\end{datatype}
+\code{filename} shall specify the file from which the lookup table
+data is to be read.  \code{format} shall contain a \code{scanf}-like
+format string specifying how the columns are to be interpreted (see
+\code{psVectorsReadFromFile}).  \code{indexCol} shall specify the
+index of the column (with the first column having an index of zero)
+that will form the index values.  \code{index} shall contain the index
+values, which shall be sorted in increasing order.  The \code{values}
+shall consist of an array of vectors, each of the same length as the
+\code{index} vector.  The vectors (including the \code{index} and all
+vectors in the \code{values} array) may be any numerical type except
+complex types.  The \code{validFrom} and \code{validTo} shall specify
+the range of valid values for the index; in most cases, these will
+simply be the first and last indices.
+The constructor shall be:
+\begin{prototype}
+psLookupTable *psLookupTableAlloc(const char *filename, ///< File from which to read
+                                  const char *format,   ///< scanf-like format string
+                                  long indexCol         ///< Column of the index vector (starting at zero)
+                                  );
+\end{prototype}
+This function shall allocate a \code{psLookupTable}, and set the
+appropriate values, but it shall not read the lookup table.  This is
+so that the lookup table can be specified at the initialisation of a
+program, but not read unless required.
+The destructor shall free all the components.
+\begin{prototype}
+psLookupTable *psLookupTableImport(psLookupTable *table,    ///< Lookup table into which to import
+                                   const psArray *vectors,  ///< Array of vectors
+                                   long indexCol            ///< Index of the index vector in the array of vectors
+                                   );
+\end{prototype}
+\code{psLookupTableImport} shall import an array of vectors into a
+\code{table}.  If \code{table} is \code{NULL}, a new
+\code{psLookupTable} shall be allocated and returned.  The array of
+\code{vectors}, which was likely generated by
+\code{psVectorsReadFromFile}, are imported by setting the
+\code{table->index} to the vector specified by the \code{indexCol},
+and pointing the \code{table->values} array data to the remaining
+vectors in \code{vectors}.  Reference counters for the vectors shall
+be incremented as appropriate.  The \code{validFrom} and
+\code{validTo} members of the \code{table} shall be set to the first
+and last values in the index vector.  If the \code{index} vector is
+not sorted in the file, the lookup table shall be sorted prior to the
+function returning.
+\begin{prototype}
+long psLookupTableRead(psLookupTable *table);
+\end{prototype}
+\code{psLookupTableRead} combines \code{psVectorsReadFromFile} and
+\code{psLookupTableImport} to read the appropriate file and import the
+data into the extant \code{table}.  If the input \code{table} has
+already been read from a file, the file shall be re-read, and the
+contents replaced.  The function shall return the number of lines read
+(not including ignored lines).
+Interpolation on a lookup table is performed by the following
+functions:
+\begin{datatype}
+typedef enum {
+    PS_LOOKUP_SUCCESS,                  ///< Table lookup succeeded
+    PS_LOOKUP_PAST_TOP,                 ///< Lookup off top of table
+    PS_LOOKUP_PAST_BOTTOM,              ///< Lookup off bottom of table
+    PS_LOOKUP_ERROR                     ///< Any other type of lookup error
+} psLookupStatusType;
+\end{datatype}
+\begin{prototype}
+double psLookupTableInterpolate(const psLookupTable *table, double index, long column, psLookupStatusType *status);
+psVector *psLookupTableInterpolateAll(const psLookupTable *table, double index, psVector *stats);
+\end{prototype}
+Both functions shall interpolate the \code{table} at the provided
+\code{index}.  For \code{psLookupTableInterpolate}, only the value in
+the specified \code{column} shall be calculated and returned.  For
+\code{psLookupTableInterpolateAll}, all the values shall be calculated
+and returned as a \code{psVector}, the type of which shall be
+\code{PS_TYPE_F64}.
+If the \code{index} is beyond the range of the \code{table},
+\code{psLookupTableInterpolate} shall return \code{NaN}, and
+\code{psLookupTableInterpolateAll} shall return \code{NULL} --- that
+is, no attempt is made at extrapolation.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Mathematical Structures}
+Throughout PSLib, we require a variety of structures which correspond
+to different mathematical data concepts.  For example, we have a data
+structure which corresponds to one-dimensional arrays (vectors) of
+different data types (\code{int}, \code{float}, etc).  We also have a
+data structure which corresponds to two-dimensional arrays (images or
+matrices), again with different data types for the individual
+elements.
+A variety of functions perform operations which are equivalent for
+different data types of the same dimension, or may even be defined for
+different data types of different dimensions.  For example, if we
+write the operation $x + y$, the operation is clearly defined
+regardless of whether the operands $x$ and $y$ are both zero
+dimensional (single numbers), one dimensional (vectors), two
+dimensional (images), etc. It is even reasonable to define the meaning
+of such an operation if the data dimensions do not match: if $x$ is a
+scalar and $y$ is an image, the natural operation is to add the value
+of $x$ to every element of $y$; we can also define the meaning of the
+operation if $x$ is a vector and $y$ is a matrix.  Nor does it matter
+mathematically that the element data types match; the sum of a float
+and an integer is a well-defined quantity.  One constraint should be
+noted: the size of the elements in each dimension must match.  For
+example, if $x$ were a vector of 100 elements, but $y$ were a vector
+of 1000 elements, the meaning of the operation $x + y$ is unclear.
+This type of operation should be invalid and should generate an error.
+Given that some functions should be able to operate equivalently (or
+identically) on a wide range of data types, we define a mechanism
+which allows the C functions to accept a generic data type, and
+determine the type of the data on the basis of the data.
+Supported data types must be defined by a structure in which
+the first element is always of type \code{psType}:
+\begin{datatype}
+typedef struct {
+    psDimen dimen;                      ///< The dimensionality
+    psElemType type;                    ///< The type
+} psType;
+\end{datatype}
+where \code{psDimen dimen} defines the dimensionality of the data and
+\code{psElemType type} defines the data type of each element.  These
+two variable types are defined as:
+\begin{datatype}
+typedef enum {
+    PS_DIMEN_SCALAR,                    ///< Scalar
+    PS_DIMEN_VECTOR,                    ///< A vector
+    PS_DIMEN_TRANSV,                    ///< A transposed vector
+    PS_DIMEN_IMAGE,                     ///< An image (matrix)
+    PS_DIMEN_OTHER                      ///< Not supported for arithmetic
+} psDimen;
+\end{datatype}
+and
+\begin{datatype}
+typedef enum {
+    PS_TYPE_S8,                         ///< Character
+    PS_TYPE_S16,                        ///< Short integer
+    PS_TYPE_S32,                        ///< Integer
+    PS_TYPE_S64,                        ///< Long integer
+    PS_TYPE_U8,                         ///< Unsigned character
+    PS_TYPE_U16,                        ///< Unsigned short integer
+    PS_TYPE_U32,                        ///< Unsigned integer
+    PS_TYPE_U64,                        ///< Unsigned long integer
+    PS_TYPE_F32,                        ///< Floating point
+    PS_TYPE_F64,                        ///< Double-precision floating point
+    PS_TYPE_C32,                        ///< Complex numbers consisting of floats
+    PS_TYPE_C64,                        ///< Complex numbers consisting of doubles
+    PS_TYPE_BOOL                        ///< Boolean value
+} psElemType;
+\end{datatype}
+We discuss the application of \code{psType} in more detail in
+section~\ref{sec:arithmetic}.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Math Casting}
+We define a basic data type which only contains the type information.
+This structure should be used to cast an unknown \code{psMath} data
+structure (\code{psImage}, \code{psVector}, \code{psScalar}) so the
+data type testing may be safely performed.
+\begin{datatype}
+typedef struct {
+    psType type;                        ///< data type information
+} psMath;
+\end{datatype}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Scalars}
 We define a basic scalar data type which includes the type
 …
 \code{psScalar} data (see \S\ref{sec:arithmetic}).
+\subsection{Simple Vectors}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Vectors}
 We require several related types of basic one-dimensional arrays:
 …
 integers to be preserved.
+\subsection{Simple Images}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Images}
 The most important data product produced by the telescope is an image.
 …
 \begin{datatype}
 typedef struct {
   float x0;
   float x1;
   float y0;
   float y1;
+    float x0;
+    float x1;
+    float y0;
+    float y1;
 } psRegion;
 \end{datatype}
 …
 \begin{prototype}
 psRegion psRegionForImage (psImage *image, psRegion in);
+psRegion psRegionForImage(psImage *image, psRegion in);
 \end{prototype}
 …
 replaced by their corrected value appropriate to the given image.
+\subsubsection{Image Pixel Lists}
+Usually an image mask is the best way to carry information about what
+pixels mean what.  However, in the case where the number of pixels in
+which we are interested is limited, it is more efficient to simply
+carry a list of pixels.  An example of this is in the image
+combination code, where we want to perform an operation on a
+relatively small fraction of pixels, and it is inefficient to go
+through an entire mask image checking each pixel.
+\begin{datatype}
+typedef struct {
+    int x;                      // x coordinate
+    int y;                      // y coordinate
+} psPixelCoord;
+typedef struct {
+    psU32 n;                    // Number in use
+    const psU32 nalloc;         // Number allocated
+    psPixelCoord *data;         // The pixel coordinates
+    void *lock;                         ///< Lock for thread safety
+} psPixels;
+\end{datatype}
+\begin{prototype}
+psPixels *psPixelsAlloc(psU32 nalloc);
+psPixels *psPixelsRealloc(psPixels *pixels, psU32 nalloc);
+\end{prototype}
+\code{psPixelsAlloc} and \code{psPixelsRealloc} provide dynamic
+allocation and reallocation in a manner analogous to those provided
+by \code{psVectorAlloc} and \code{psVectorRealloc}.
+\begin{prototype}
+psImage *psPixelsToMask(psImage *out, const psPixels *pixels, psRegion region, unsigned int maskVal);
+psPixels *psPixelsFromMask(psPixels *out, const psImage *mask, unsigned int maskVal);
+\end{prototype}
+\code{psPixelsToMask} shall return an image of type U8 with the
+\code{pixels} lying within the specified \code{region} set to the
+\code{maskVal}.  The \code{out} image shall be modified if supplied,
+or allocated and returned if \code{NULL}.  The size of the output
+image shall be \code{region.x1 - region.x0} by \code{region.y1 -
+region.y0}, with \code{out->x0 = region.x0} and \code{out->y0 =
+region.y0}.  In the event that either of \code{pixels} or
+\code{region} are \code{NULL}, the function shall generate an error
+and return \code{NULL}.
+\code{psMaskToPixels} shall return a \code{psPixels} containing the
+coordinates in the \code{mask} that match the \code{maskVal}.  The
+\code{out} pixel list shall be modified if supplied, or allocated and
+returned if \code{NULL}.  In the event that \code{mask} is
+\code{NULL}, the function shall generate an error and return
+\code{NULL}.
+\begin{prototype}
+psPixels *psPixelsCopy(psPixels *out, const psPixels *pixels);
+psPixels *psPixelsConcatenate(psPixels *out, const psPixels *pixels);
+\end{prototype}
+\code{psPixelsCopy} shall copy the contents of \code{pixels} to the
+\code{out}.  In the event that \code{out} is \code{NULL}, a new
+\code{psPixels} shall be allocated, and the contents of \code{pixels}
+simply copied in.  If \code{pixels} is \code{NULL}, the function shall
+generate an error and return \code{NULL}.
+\code{psPixelsConcatenate} shall concatenate the \code{pixels} onto
+\code{out}.  In the event that \code{out} is \code{NULL}, the function
+performs a \code{psPixelsCopy}, returning the copy.  If \code{pixels}
+is \code{NULL}, the function shall generate an error and return
+\code{NULL}.  The function shall take care to ensure that there are no
+duplicate pixels in \code{out} (since the order in which the pixels
+are stored is not important, the values may be sorted, allowing the
+use of a faster algorithm than a linear scan).
+\subsection{Math Casting}
+We define a basic data type which only contains the type information.
+This structure should be used to cast an unknown \code{psMath} data
+structure (\code{psImage}, \code{psVector}, \code{psScalar}) so the
+data type testing may be safely performed.
+\begin{datatype}
+typedef struct {
+    psType type;                        ///< data type information
+} psMath;
+\end{datatype}
+\subsection{Simple Arrays}
+We require an order collection of unspecified data elements.  We
+define \code{psArray} to carry such a collection:
+%
+\begin{datatype}
+typedef struct {
+    const long n;                       ///< size of array
+    const long nalloc;                  ///< allocated data block
+    void **data;                        ///< pointer to data block
+    void *lock;                         ///< Optional lock for thread safety
+}} psArray;
+\end{datatype}
+%
+In this structure, the argument \code{n} is the length of the array
+(the number of elements); \code{nalloc} is the number of elements
+allocated ($nalloc \ge n$).  The allocated memory is pointed to by
+\code{data}.  The structure is associated with a constructor and a
+destructor:
+%
+\begin{prototype}
+psArray *psArrayAlloc(long nalloc);
+psArray *psArrayRealloc(psArray *array, long nalloc);
+\end{prototype}
+%
+In these functions, \code{nalloc} is the number of elements to
+allocate.  For \code{psArrayAlloc}, the value of \code{psArray.n} is
+set to \code{nalloc}.  Users may choose to restrict the data range
+after the \code{psArrayAlloc} function is called.  For
+\code{psArrayRealloc}, if the value of \code{nalloc} is smaller than
+the current value of \code{psArray.n}, then \code{psArray.n} is set to
+\code{nalloc}, the array is adjusted down to match \code{nalloc}, and
+the extra elements are dropped and freed if necesitated by the
+reference counter.  If \code{nalloc} is larger than the current value
+of \code{psArray.n}, \code{psArray.n} is left intact.  If the value of
+\code{array} is \code{NULL}, then \code{psArrayRealloc} must return an
+error.
+\begin{prototype}
+psArray *psArrayAdd(psArray *array, long delta, psPtr data);
+\end{prototype}
+This function adds a value to the end of an array.  If the current
+length of the array (\code{psArray.n}) is at the limit of the
+allocated space, additional space is allocated.  The value of
+\code{delta} defines how many elements to add on each pass (if this
+value is less than 1, 10 shall be used).
+\begin{prototype}
+bool psArrayRemove(psArray *array, const psPtr data);
+\end{prototype}
+This function removes all entries of \code{value} in the \code{array},
+reducing the total number of elements of \code{array} as needed.
+Returns \code{TRUE} if any elements were removed, otherwise
+    const int x0, y0;                   ///< data region relative to parent
+\code{FALSE}.
+\begin{prototype}
+bool psArraySet(psArray *array, long position, psPtr data);
+psPtr psArrayGet(const psArray *array, long position);
+\end{prototype}
+These accessor functions are provided as a convenience to the user.
+\code{psArraySet} sets the value of the \code{in} array at the specified
+\code{position} to \code{value}, returning \code{true} if successful.
+\code{psArrayGet} returns the value of the \code{in} array at the
+specified \code{position}.
+\begin{datatype}
+typedef int (*psComparePtrFunc) (
+    const void **a,                    ///< first comparison target
+    const void **b                     ///< second comparison target
+);
+\end{datatype}
+\begin{prototype}
+psArray *psArraySort(psArray *array, psComparePtrFunc func);
+\end{prototype}
+An array may be sorted using \code{psArraySort}, which requires the
+specification of a comparison function to specify how the objects on
+the list should be sorted.  The motivation is primarily to be able to
+iterate on a sorted list of keys from a hash.  The \code{array} is
+sorted in-place.
+\subsection{Doubly-linked lists}
+\label{sec:psList}
+\PS{} shall support doubly linked lists through a type \code{psList}:
+%
+\begin{datatype}
+typedef struct {
+   long n;                              ///< number of elements on list
+   psListElem *head;                    ///< first element on list (may be NULL)
+   psListElem *tail;                    ///< last element on list (may be NULL)
+   psArray *iterators;                  ///< array of psListIterator: iteration cursors
+   void *lock;                          ///< Optional lock for thread safety
+} psList;
+\end{datatype}
+%
+The type \code{psList} represents the container of the list.  It has a
+pointer to the first element in the linked list (\code{head}), a
+pointer to the last element in the list (\code{tail}), an array of
+iteration cursors, (\code{iterators}), and an entry to define the
+number of elements in the list (\code{n}).
+The elements of the list are defined by the type \code{psListElem}:
+%
+\begin{datatype}
+typedef struct psListElem {
+   struct psListElem *prev;            ///< previous link in list
+   struct psListElem *next;            ///< next link in list
+   void *data;                         ///< real data item
+} psListElem;
+\end{datatype}
+%
+which includes a pointer to the next element in the list
+(\code{next}), the previous element in the list (\code{prev}), and a
+\code{void} pointer to whatever data is represented by this list
+element.    The following supporting functions are required:
+\begin{prototype}
+psList *psListAlloc(psPtr data);
+\end{prototype}
+Create a list.  This function may take a pointer to a data item, or it
+may take \code{NULL}.  The allocator creates both the \code{psList}
+and the first element in the list, pointed to by both
+\code{psList.head} and \code{psList.tail}.  If the data entry is
+\code{NULL}, then an empty list, with both pointers set to \code{NULL}
+should be created.
+The destructor function for \code{psList} must call \code{psFree} for
+all the the data associated with the list.
+All data items placed onto lists must have their reference counters
+(section \ref{secMemRefcounter}) incremented.  When elements are
+removed from a list, they must have their reference counters
+decremented.  The action of retrieving data from a list (with one of
+the three \code{psListGet} functions) is considered ``borrowing'' the
+reference, so no action is performed on the reference counter.
+Iteration on the list shall be achieved by means of a list iterator
+type:
+\begin{datatype}
+typedef struct {
+    psList *list;                       ///< List iterator works on
+    psListElem *cursor;                 ///< The current iterator cursor
+    bool offEnd;                        ///< Is the iterator off the end?
+    long index;                         ///< Index of iterator, to assist performance
+    bool mutable;                       ///< Is it permissible to modify the list?
+} psListIterator;
+\end{datatype}
+The \code{psListIterator} keeps track of which list element the
+iterator \code{cursor} is currently pointing at.  \code{index} is the
+index of the list iterator, which is used to assist performance when
+using numerical locations.  The boolean member, \code{offEnd},
+indicates whether the iterator has progressed off the end of the list
+(i.e., beyond the last item).  The boolean \code{mutable} specifies
+whether it is permissible to modify the list pointed to by the
+iterator.  \code{psListAddBefore} and \code{psListAddAfter} are not
+permitted to modify a list that is not \code{mutable} (i.e., only the
+\code{psListGetAndIncrement} and \code{psListGetAndDecrement}
+operations are permissible for a non-\code{mutable} list).
+The corresponding constructor shall be:
+\begin{prototype}
+psListIterator *psListIteratorAlloc(const psList *list, long location, bool mutable);
+\end{prototype}
+Here, \code{list} is the \code{psList} on which the iterator will
+iterate, and \code{location} is the initial starting point, and may be
+a numerical index or it may be one of the special values:
+\code{PS_LIST_HEAD} or \code{PS_LIST_TAIL}, which are defined as 0 and
+-1, respectively; a negative index is interpreted as relative to the
+end of the list.  The boolean \code{mutable} specifies whether it is
+permissible to modify the list pointed to by the iterator.
+The destructor for \code{psListIterator} shall, after freeing the
+\code{psListIterator}, also reorganise the \code{iter} array
+(replacing the element being removed with the last element) and
+resizing the array appropriately.
+A list \code{iterator} shall be set to a specific \code{location} on
+the list upon calling \code{psListIteratorSet}:
+\begin{prototype}
+bool psListIteratorSet(psListIterator *iterator, int location);
+\end{prototype}
+Again, the \code{location} may be a numerical index or it may be one
+of the special values: \code{PS_LIST_HEAD} or \code{PS_LIST_TAIL},
+which are defined as 0 and -1, respectively; a negative index is
+interpreted as relative to the end of the list.  The function shall
+return \code{true} if the reset was successful, or \code{false}
+otherwise.
+\begin{prototype}
+bool psListAdd(psList *list, long location, psPtr data);
+bool psListAddAfter(psListIterator *iterator, psPtr data);
+bool psListAddBefore(psListIterator *iterator, psPtr data);
+\end{prototype}
+the first function, \code{psListAdd}, adds an entry to the \code{list}
+and returns a boolean giving the success or failure of the
+operation. The value of \code{location} may be a numerical index the
+\code{data} is to inhabit (if \code{location} is greater than the
+number of items on the list, then the function shall generate a
+warning and add the \code{data} to the tail) or it may be one of the
+special values: \code{PS_LIST_HEAD} or \code{PS_LIST_TAIL}, which are
+defined as 0 and -1, respectively; a negative index is interpreted as
+relative to the end of the list.  The other two functions,
+\code{psListAddAfter} and \code{psListAddBefore} specify that the
+\code{data} shall be added after or before (respectively) the current
+cursor position of the \code{iterator}.
+\begin{prototype}
+psPtr psListGet(psList *list, long location);
+psPtr psListGetAndIncrement(psListIterator *iterator);
+psPtr psListGetAndDecrement(psListIterator *iterator);
+\end{prototype}
+A data item may be retrieved from the list with these functions.  The
+first function, \code{psListGet} simply returns the value specified by
+its \code{location}, which may be a numerical index or it may be one
+of the special values: \code{PS_LIST_HEAD = 0} or \code{PS_LIST_TAIL =
+-1}; negative indices are interpreted as relative to the end of the
+list.  The other two functions, \code{psListGetAndIncrement} and
+\code{psListGetAndDecrement} return the item under the iteration
+cursor before advancing to the next or previous item, respectively.
+In the event that the iteration cursor is at the tail of the list,
+\code{psListGetAndIncrement} shall return the tail item and then set
+the \code{cursor} to \code{NULL} and \code{offEnd} to \code{true}.  In
+the event that the iteration cursor is at the head of the list,
+\code{psListGetAndDecrement} shall return the head item and then set
+the \code{cursor} to \code{NULL} (and \code{offEnd} should already be
+\code{false}).  In the event that the iteration \code{cursor} is
+\code{NULL}, \code{psListGetAndIncrement} and
+\code{psListGetAndDecrement} shall return \code{NULL}, and advance the
+iteration \code{cursor} only if the intended direction places the
+cursor back on the list; otherwise a warning shall be generated, and
+no change shall be made.  If \code{psListGetAndDecrement} was called
+with \code{offEnd} as \code{true}, then \code{offEnd} shall also be
+toggled back to \code{false} to indicate that the \code{cursor} is no
+longer off the end of the list.
+\begin{prototype}
+bool psListRemove(psList *list, long location)
+bool psListRemoveData(psList *list, psPtr data);
+\end{prototype}
+A data item may be removed from the list with these functions.  For
+\code{psListRemove}, the value of \code{location} may be the numerical
+index or it may be one of the special values: \code{PS_LIST_HEAD} or
+\code{PS_LIST_TAIL}, which are defined as 0 and -1, respectively; a
+negative index is interpreted as relative to the end of the list.  For
+\code{psListRemoveData}, the data item to be removed is identified by
+matching the pointer value with \code{psPtr data}.  The functions
+return a value of \code{true} if the operation was successful, and
+\code{false} otherwise.  In both cases, if any iterators are currently
+pointing at the item to be removed, the item shall be removed and
+those iterators pointing at it shall be moved to the next, and the
+function shall return \code{true}.  If the item to be removed is not
+on the list, an error shall be generated and the function shall return
+\code{false}.
+\begin{prototype}
+psArray *psListToArray(const psList *list);
+psList  *psArrayToList(const psArray *array);
+\end{prototype}
+These two functions are available to convert between the
+\code{psList} and \code{psArray} containers.  These functions do not
+free the elements or destroy the input collection.  Rather, they
+increment the reference counter for each of the elements.
+\begin{prototype}
+psList *psListSort(psList *list, psComparePtrFunc func);
+\end{prototype}
+A list may be sorted using \code{psListSort}, which requires the
+specification of a comparison function to specify how the objects on
+the list should be sorted.  The motivation is primarily to be able to
+iterate on a sorted list of keys from a hash.  The \code{list} is
+sorted in-place.
+\subsection{Hash Tables}
+\hlabel{psHash}
+Hash tables are critical for quick retrieval of text-based data.  The
+concept is as follows: Given a large collection of text strings, it is
+inefficient to search for a particular entry by performing a basic
+string comparison on all entries until a match is found.  Even if a
+single list is sorted, we will still spend a substantial amount of
+time iterating across the entries in the list.  In a hash table, we
+define an operation, the hash function, which uses the bytes of the
+string to construct a numerical value, the hash value.  The hash value
+is defined to have a limited range of $N$ values.  The hash table
+consists of $N$ buckets, each of which contains a list of the strings
+whose hash value corresponds to the bucket number.  Searching for a
+specific string involves calculating the hash value for the string,
+going to the appropriate bucket, and searching through the
+corresponding list until the string is matched.
+For PSLib, we define a hash table and hash buckets as follows:
+\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.}
+%
+\begin{datatype}
+typedef struct {
+    long n;                             ///< number of buckets
+    psHashBucket **buckets;             ///< the buckets themselves
+    void *lock;                         ///< Optional lock for thread safety
+}} psHash;
+\end{datatype}
+%
+where \code{n} is the number of buckets defined for the hash functions, and
+\code{buckets} is an array of pointers to the individual buckets, each of which
+is defined by:
+%
+\begin{datatype}
+typedef struct psHashBucket {
+    char *key;                          ///< key for this item of data
+    void *data;                         ///< the data itself
+    struct psHashBucket *next;          ///< list of other possible keys
+} psHashBucket;
+\end{datatype}
+where each bucket contains the value of the \code{key}, a pointer to
+the \code{data}, and a pointer to the \code{next} list entry in the
+bucket (in the event that two or more keys have the same hash value).
+A hash table is created with the following function:
+\begin{prototype}
+psHash *psHashAlloc(long nalloc);
+\end{prototype}
+which allocates the space for the hash table, creating and
+initializing \code{n} hash buckets.
+The destructor for \code{psHash} must free all data associated with a complete hash table.
+A data item may be added to the hash table with the function:
+\begin{prototype}
+bool psHashAdd(psHash *hash, const char *key, psPtr data);
+\end{prototype}
+In this function, the value of the string \code{key} is used to
+construct the hash value, find the appropriate bucket set, and add the
+new element \code{data} to the list.  An existing element with the same
+value of \code{key} is destroyed using its registered destructor
+(\code{psMemBlock}). The return value of the function is a boolean
+defining the success or failure of the operation.
+The data associated with a given key may be found with the function:
+\begin{prototype}
+psPtr psHashLookup(const psHash *hash, const char *key);
+\end{prototype}
+which returns the data value pointed to by the element associated with
+\code{key}, or the value \code{NULL} if no match is found.  Similarly,
+a specific key may be removed (deleted) with the function:
+\begin{prototype}
+bool psHashRemove(psHash *hash, const char *key);
+\end{prototype}
+The function returns a value of \code{true} if the operation was
+successfull, and \code{false} otherwise.
+The function
+\begin{prototype}
+psList *psHashKeyList(const psHash *hash);
+\end{prototype}
+returns the complete list of defined keys associated with the
+\code{psHash} table as a linked list.
+\begin{prototype}
+psArray *psHashToArray(const psHash *hash);
+\end{prototype}
+This function places the data in a \code{psHash} into a \code{psArray}
+container.  This function does not free the elements or destroy the
+input collection.  Rather, it increments the reference counter for
+each of the elements.  The resulting array does not have any
+information about the has key values, and the order is not
+significant.
+\subsection{Lookup Tables}
+Lookup tables store a variety of values indexed on a certain column.
+An example is for storing the difference between UT1 and UTC, and the
+polar motion vector as a function of date.
+One of the key functionalities of a lookup table is to read data from
+an ordinary text file into an array of vectors.  This functionality is
+generally useful, and so we specify a separate function that may be
+called independently:
+\begin{prototype}
+psArray *psVectorsReadFromFile(const char *filename, const char *format);
+\end{prototype}
+\code{psVectorsReadFromFile} shall return an array of
+\code{psVector}s, read from the specified \code{filename}.  The file
+shall be plain text, consisting of an identical number of columns on
+each line, with the values separated by whitespace.  Lines commencing
+with a comment character (the pound sign, \code{#}) and blank lines
+shall be ignored.  The \code{format} is a \code{scanf}-like format
+which specifies the number of columns in the file, as well as their
+types.  The following formats shall be defined: \code{\%d} for psS32,
+\code{\%ld} for psS64, \code{\%f} for psF32, and \code{\%lf} for
+psF64.  A star (\code{*}) in the format shall indicate that the column
+is to be skipped.
+\begin{datatype}
+typedef struct {
+    const char *filename;               ///< File from which data is to be read
+    const char *format;                 ///< scanf-like format string for file
+    long indexCol;                      ///< Column of the index vector (starting at zero)
+    psVector *index;                    ///< Index values
+    psArray *values;                    ///< Corresponding values: an array of vectors
+    const psF64 validFrom, validTo;     ///< Range of validity
+} psLookupTable;
+\end{datatype}
+\code{filename} shall specify the file from which the lookup table
+data is to be read.  \code{format} shall contain a \code{scanf}-like
+format string specifying how the columns are to be interpreted (see
+\code{psVectorsReadFromFile}).  \code{indexCol} shall specify the
+index of the column (with the first column having an index of zero)
+that will form the index values.  \code{index} shall contain the index
+values, which shall be sorted in increasing order.  The \code{values}
+shall consist of an array of vectors, each of the same length as the
+\code{index} vector.  The vectors (including the \code{index} and all
+vectors in the \code{values} array) may be any numerical type except
+complex types.  The \code{validFrom} and \code{validTo} shall specify
+the range of valid values for the index; in most cases, these will
+simply be the first and last indices.
+The constructor shall be:
+\begin{prototype}
+psLookupTable *psLookupTableAlloc(const char *filename, ///< File from which to read
+                                  const char *format,   ///< scanf-like format string
+                                  long indexCol         ///< Column of the index vector (starting at zero)
+                                  );
+\end{prototype}
+This function shall allocate a \code{psLookupTable}, and set the
+appropriate values, but it shall not read the lookup table.  This is
+so that the lookup table can be specified at the initialisation of a
+program, but not read unless required.
+The destructor shall free all the components.
+\begin{prototype}
+psLookupTable *psLookupTableImport(psLookupTable *table,    ///< Lookup table into which to import
+                                   const psArray *vectors,  ///< Array of vectors
+                                   long indexCol            ///< Index of the index vector in the array of vectors
+                                   );
+\end{prototype}
+\code{psLookupTableImport} shall import an array of vectors into a
+\code{table}.  If \code{table} is \code{NULL}, a new
+\code{psLookupTable} shall be allocated and returned.  The array of
+\code{vectors}, which was likely generated by
+\code{psVectorsReadFromFile}, are imported by setting the
+\code{table->index} to the vector specified by the \code{indexCol},
+and pointing the \code{table->values} array data to the remaining
+vectors in \code{vectors}.  Reference counters for the vectors shall
+be incremented as appropriate.  The \code{validFrom} and
+\code{validTo} members of the \code{table} shall be set to the first
+and last values in the index vector.  If the \code{index} vector is
+not sorted in the file, the lookup table shall be sorted prior to the
+function returning.
+\begin{prototype}
+long psLookupTableRead(psLookupTable *table);
+\end{prototype}
+\code{psLookupTableRead} combines \code{psVectorsReadFromFile} and
+\code{psLookupTableImport} to read the appropriate file and import the
+data into the extant \code{table}.  If the input \code{table} has
+already been read from a file, the file shall be re-read, and the
+contents replaced.  The function shall return the number of lines read
+(not including ignored lines).
+Interpolation on a lookup table is performed by the following
+functions:
+\begin{datatype}
+typedef enum {
+    PS_LOOKUP_SUCCESS,                  ///< Table lookup succeeded
+    PS_LOOKUP_PAST_TOP,                 ///< Lookup off top of table
+    PS_LOOKUP_PAST_BOTTOM,              ///< Lookup off bottom of table
+    PS_LOOKUP_ERROR                     ///< Any other type of lookup error
+} psLookupStatusType;
+\end{datatype}
+\begin{prototype}
+double psLookupTableInterpolate(const psLookupTable *table, double index, long column, psLookupStatusType *status);
+psVector *psLookupTableInterpolateAll(const psLookupTable *table, double index, psVector *stats);
+\end{prototype}
+Both functions shall interpolate the \code{table} at the provided
+\code{index}.  For \code{psLookupTableInterpolate}, only the value in
+the specified \code{column} shall be calculated and returned.  For
+\code{psLookupTableInterpolateAll}, all the values shall be calculated
+and returned as a \code{psVector}, the type of which shall be
+\code{PS_TYPE_F64}.
+If the \code{index} is beyond the range of the \code{table},
+\code{psLookupTableInterpolate} shall return \code{NaN}, and
+\code{psLookupTableInterpolateAll} shall return \code{NULL} --- that
+is, no attempt is made at extrapolation.
+\pagebreak
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\pagebreak
+\subsection{BitSets}
+BitSets are required in order to turn options on and off.  We require
+the capability to have a bitset of arbitrary length (i.e., not limited
+by the length of a \code{long}, say).  The \code{psBitSet} structure
+is defined below.  Note that the entry \code{bits} is an array of type
+\code{char} storing the bits as bits of each byte in the array, with 8
+bits available for each byte in the array.  Also note that the
+constructor is passed the number of required bits, which implies that
+\code{ceil(n/8)} bytes must be allocated.  The bitset structure is
+define by:
+\begin{datatype}
+typedef struct {
+    long n;                             ///< Number of chars that form the bitset
+    char *bits;                         ///< The bits
+    void *lock;                         ///< Optional lock for thread safety
+}} psBitSet;
+\end{datatype}
+We also require the corresponding constructor and destructor:
+\begin{prototype}
+psBitSet *psBitSetAlloc(long nalloc);
+\end{prototype}
+where \code{n} is the requested number of bits.
+Several basic operations on bitsets are required:
+\begin{itemize}
+\item Set a bit;
+\item Check if a bit is set; and
+\item \code{OR}, \code{AND} and \code{XOR} two bitsets.
+\item \code{NOT} a bitset.
+\end{itemize}
+The corresponding APIs are defined below:
+\begin{prototype}
+psBitSet *psBitSetSet(psBitSet *bitSet, long bit);
+psBitSet* psBitSetClear(psBitSet *bitSet, long bit);
+psBitSet *psBitSetOp(psBitSet *outBitSet, const psBitSet *inBitSet1, const char *operator, const psBitSet *inBitSet2);
+psBitSet *psBitSetNot(psBitSet *outBitSet, const psBitSet *inBitSet);
+bool psBitSetTest(const psBitSet *bitSet, long bit);
+char *psBitSetToString(const psBitSet* bitSet);
+\end{prototype}
+\code{psBitSetSet} sets the specified \code{bit} in the
+\code{psBitSet}, and returns the updated bitset.  The input bitset
+will be modified.
+\code{psBitSetClear} clears the specified \code{bit} in the \code{bitSet}
+and returns the updated bitset.  The input bitset will be modified.
+\code{psBitSetOp} returns the \code{psBitSet} that is the result of
+performing the specified \code{operator} (one of \code{"AND"},
+\code{"OR"}, or \code{"XOR"}) on \code{inBitSet1} and \code{inBitSet2}.
+If the output bitset \code{outBitSet} is \code{NULL}, it is created by
+the function.
+\code{psBitSetNot} applies a unary \code{NOT} to a bitset, placing the
+answer in the bitset \code{out}, or creating a new bitset if
+\code{out} is \code{NULL}.
+\code{psBitSetTest} returns a true value if the specified \code{bit}
+is set; otherwise, it returns a false value.
+Finally, \code{psBitSetToString} returns a string representation of
+the specified \code{bits}.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Rich Data Structures and I/O}
+\subsection{Metadata}
+\label{sec:metadata}
+\subsubsection{Conceptual Overview}
+Within PSLib, we provide a data structure to carry metadata and
+mechanisms to manipulate the metadata.  Metadata is a general concept
+that requires some discussion.  In any data analysis task, the
+ensemble of all possible data may be divided into two or three
+classes: there is the specific data of interest, there is data which
+is related or critical but not the primary data of interest, and there
+is all of the other data which may or may not be interesting.  For
+example, consider a simple 2D image obtained of a galaxy from a CCD
+camera on a telescope.  If you want to study the galaxy, the specific
+data of interest is the collection of pixels.  There are a variety of
+other pieces of data which are closely related and crucial to
+understanding the data in those pixels, such as the dimensions of the
+image, the coordinate system, the time of the image, the exposure
+time, and so forth.  Other data may be known which may be less
+critical to understanding the image, but which may be interesting or
+desired at a later date.  For example, the observer who took the
+image, the filter manufacturer, the humidity at the telescope, etc.
+Formally, all of the related data which describe the principal data of
+interest are metadata.  Note that which piece is the metadata and
+which is the data may depend on the context.  If you are examining the
+pixels in an image, the coordinate and flux of an object may be part
+of the metadata.  However, if you are analyzing a collection of
+objects extracted from an image, you may consider then pixel data
+simply part of the metadata associated with the list of objects.
+There are various ways to handle metadata vs data within a programming
+environment.  In C, it is convenient to use structures to group
+associated data together.  One possibility is to define the metadata
+as part of the associated data structure.  For example, the image data
+structure would have elements for all possible associated measurement.
+This approach is both cumbersome (because of the large number metadata
+types), impractical (because the full range of necessary metadata is
+difficult to know in advance) and inflexible (because any change in
+the collection of metadata requires addition of new structure elements
+and recompilation).
+An alternative is to place the metadata in a generic container and use
+lookup mechanisms to extract the appropriate metadata when needed.  An
+example of this is would be a text-based FITS header for an image read
+into a flat text buffer.  In this implementation, metadata lookup
+functions could return the current value of, for example, NAXIS1 (the
+number of columns of the image) by scanning through the header buffer.
+This method has the benefits of flexibility and simplicity of
+programming interface, but it has the disadvantage that all metadata
+is accessed though this lookup mechanism.  This may make the code less
+readable and it may slow down the access.
+PSLib implements an intermediate solution to this problem.  We specify
+a flexible, generic metadata container and access methods.  Data types
+which require association with a general collection of metadata should
+include an entry of this metadata type.  However, a subset of metadata
+concepts which are basic and frequently required may be placed in the
+coded structure elements.  This approach allows the code to refer to
+the basic metadata concepts as part of the data structure (ie,
+\code{image.nx}), but also allows us to provide access to any
+arbitrary metadata which may be generated.  As a practical matter, the
+choice of which entries are only in the metadata and which are part of
+the explicit structure elements is rather subjective.  Any data
+elements which are frequently used should be put in the structure;
+those which are only infrequently needed should be left in the generic
+metadata.
+There are some points of caution which must be noted.  Any
+manipulation of the data should be reflected in the metadata where
+appropriate.  This is always an issue of concern.  For example,
+consider an image of dimensions \code{nx, ny}.  If a function extracts
+a subraster, it must change the values of \code{nx, ny} to match the
+new dimensions.  What should it do to the corresponding metadata?
+Clearly, it should change the corresponding value which defines
+\code{nX, nY}.  However, it is not quite so simple: there may be other
+metadata values which depend on those values.  These must also be
+changed appropriately.  What if the metadata element points to a
+copy of the metadata which may be shared by other representations of
+the image?  These must be treated differently because the change would
+invalidate those other references.  Care must be taken, therefore,
+when writing functions which operate on the data to consider all of
+the relevant metadata entries which must also be updated.
+A related issue is the definition of metadata names.  Entries in a
+structure have the advantage of being hardwired: every instance of
+that structure will have the same name for the same entry.  This is
+not necessarily the case with a more flexible metadata container.  The
+image exposure time is a notorious example in astronomy.  Different
+observatories use different header keywords (ie, metadata names) for
+the same concept of the exposure time (\code{EXPTIME},
+\code{EXPOSURE}, \code{OPENTIME}, \code{INTTIME}, etc).  Any system
+which operates on these metadata needs to address the issue of
+identifying these names.  This issue seems like an argument for
+hardwiring metadata in the structure, but in fact it does not present
+such a strong case.  If the metadata are hardwired, some function will
+still have to know how to interpret the various names to populate the
+structure.  The concept can still be localized with generic metadata
+containers by including abstract metadata names within the code which
+are tied to the various implementations-specific metadata names.
+\subsubsection{Metadata Representation}
+\begin{figure}
+\psfig{file=Metadata,width=6.5in}
+\caption{Metadata Structures\label{fig:metadata}}
+\end{figure}
+This section addresses the question of how \PS{} metadata should be
+represented in memory, not how it should be represented on disk.
+We define an item of metadata with the following structure:
+\filbreak
+\begin{datatype}
+typedef struct {
+    const psS32 id;                     ///< unique ID for this item
+    char *name;                         ///< Name of item
+    psMetadataType type;                ///< type of this item
+    const union {
+        psS32 S32;                      ///< integer data
+        psF32 F32;                      ///< floating-point data
+        psF64 F64;                      ///< double-precision data
+        psList *list;                   ///< psList entry
+        psMetadata *md;                 ///< psMetadata entry
+        psPtr V;                        ///< other type
+    } data;                             ///< value of metadata
+    char *comment;                      ///< optional comment ("", not NULL)
+} psMetadataItem;
+\end{datatype}
+The \code{id} is a unique identifier for this item of metadata;
+experience shows that such tags are useful.  The entry \code{name}
+specifies the name of the metadata item.  The value of the metadata is
+given by the union \code{data}, and may be of type \code{psS32},
+\code{psF32}, \code{psF64}, or an arbitrary rich structure pointed at
+by the \code{void} pointer \code{V}.  A character string comment
+associated with this metadata item may be stored in the element
+\code{comment}. The \code{type} entry specifies how to interpret the
+type of the data being represented, given by the enumerated type
+\code{psMetadataType}:
+%
+\filbreak
+\begin{datatype}
+typedef enum {                         ///< type of item.data is:
+    PS_META_S32  = PS_TYPE_S32,        ///< psS32 primitive data.
+    PS_META_F32  = PS_TYPE_F32,        ///< psF32 primitive data.
+    PS_META_F64  = PS_TYPE_F64,        ///< psF64 primitive data.
+    PS_META_BOOL = PS_TYPE_BOOL,       ///< psBool primitive data.
+    PS_META_LIST = 0x10000,            ///< List data (Stored as item.data.list).
+    PS_META_STR,                       ///< String data (Stored as item.data.V).
+    PS_META_META,                      ///< Metadata (Stored as item.data.md).
+    PS_META_VEC,                       ///< Vector data (Stored as item.data.V).
+    PS_META_IMG,                       ///< Image data (Stored as item.data.V).
+    PS_META_HASH,                      ///< Hash data (Stored as item.data.V).
+    PS_META_LOOKUPTABLE,               ///< Lookup table data (Stored as item.data.V).
+    PS_META_JPEG,                      ///< JPEG data (Stored as item.data.V).
+    PS_META_PNG,                       ///< PNG data (Stored as item.data.V).
+    PS_META_ASTROM,                    ///< Astrometric coefficients (Stored as item.data.V).
+    PS_META_TIME,                      ///< psTime object (Stored as item.data.V).
+    PS_META_UNKNOWN,                   ///< Other data (Stored as item.data.V).
+    PS_META_MULTI                      ///< Used internally, do not create a metadata item of this type.
+} psMetadataType;
+\end{datatype}
+The macro \code{PS_META_IS_PRIMITIVE(psMetadataType.type)} returns
+true if the type is one of the primitive data types (S32, F64, etc).
+In such a case, the data value is directly available.  Otherwise, a
+pointer to the data is available.
+A collection of metadata is represented by the \code{psMetadata} structure:
+\begin{datatype}
+typedef struct {
+    psList *list;                       ///< list of psMetadataItem
+    psHash *hash;                       ///< hash table of the same metadata
+    void *lock;                         ///< Optional lock for thread safety
+}} psMetadata;
+\end{datatype}
+The type \code{psMetadata} is a container class for metadata. Note
+that there are in fact \emph{two} representations of the metadata
+(each \code{psMetadataItem} appears on both).  The first
+representation employs a doubly-linked list that allows the order of
+the metadata to be preserved (e.g., if FITS headers are read in a
+particular order, they should be written in the same order).  The
+second representation employs a hash table which allows fast look-up
+given a specific metadata keyword.
+Certain metadata names (such as the FITS keywords \code{COMMENT} and
+\code{HISTORY} in a FITS header) may be repeated with different
+values.  In such a case, the \code{psMetadata.list} structure contains
+the entries in their original sequence with duplicate keys.  The
+\code{psMetadata.hash} entries, which are required to have unique
+keys, would have a single entry with the keyword of the repeated key,
+with the value of \code{psMetadataType} set to \code{PS_META_MULTI},
+and the \code{psMetadataItem.data} element pointing to a \code{psList}
+containing the actual entries.  If \code{psMetadataItemAlloc} is
+called with the type set to \code{PS_META_MULTI}, such a repeated key
+is created.  In this case, the data value passed to
+\code{psMetadataItemAlloc} (the quantity in ellipsis) must be
+\code{NULL}.  An empty \code{psMetadataItem} with the given keyword is
+created to hold future entries of that keyword.
+As a convenience to the user, the following type-specific functions are
+also defined:
+\begin{prototype}
+psMetadataItem* psMetadataItemAllocStr(const char* name, const char* comment, const char* value);
+psMetadataItem* psMetadataItemAllocF32(const char* name, const char* comment, psF32 value);
+psMetadataItem* psMetadataItemAllocF64(const char* name, const char* comment, psF64 value);
+psMetadataItem* psMetadataItemAllocS32(const char* name, const char* comment, psS32 value);
+psMetadataItem* psMetadataItemAllocBool(const char* name, const char* comment, bool value);
+psMetadataItem* psMetadataItemAllocPtr(const char* name, psMetadataType type, const char* comment, psPtr value);
+\end{prototype}
+\subsubsection{Metadata APIs}
+\begin{prototype}
+psMetadata *psMetadataAlloc(void);
+\end{prototype}
+The constructor for the collection of metadata, \code{psMetadata},
+simply returns an empty metadata container (employing the constructors
+for the doubly-linked list and hash table).  The destructor needs to
+free each of the \code{psMetadataItem}s.
+\begin{prototype}
+psMetadataItem *psMetadataItemAlloc(const char *name, psMetadataType type, const char *comment, ...);
+psMetadataItem *psMetadataItemAllocV(const char *name, psMetadataType type, const char *comment, va_list list);
+\end{prototype}
+The allocator for \code{psMetadataItem} returns a full
+\code{psMetadataItem} ready for insertion into the \code{psMetadata}.
+The \code{name} entry specifies the name to use for this metadata
+item, and may include \code{sprintf}-type formating codes.  The
+\code{comment} entry is a fixed string which is used for the comment
+associated with this metadata item.  The metadata data and the
+arguments to the \code{name} formatting codes are passed, in that
+order (metadata pointer first), to \code{psMetadataItemAlloc} as
+arguments following the comment string.  The data must be a pointer
+for any data types which are stored in the element \code{data.void},
+while other data types are passed as numeric values.  The argument
+list must be interpreted appropriately by the \code{va_list} operators
+in the function.
+\begin{prototype}
+bool psMetadataAddItem(psMetadata *md, const psMetadataItem *item, psS32 location, psS32 flags);
+bool psMetadataAdd(psMetadata *md, int location, const char *name, int format, const char *comment, ...);
+bool psMetadataAddV(psMetadata *md, int location, const char *name, int format, const char *comment,
+                    va_list list);
+\end{prototype}
+Items may be added to the metadata in one of two ways --- firstly, an
+item may be added by appending a \code{psMetadataItem} which has
+already been created; and secondly by directly providing the data to
+be appended.  In both cases, the return value defines the success
+(\code{true}) or failure of the operation.  The second function,
+\code{psMetadataAdd} takes a pointer or value which is interpreted by
+the function using variadic argument interpretation.  The third
+version is the \code{va_list} version of the second function.  All
+three functions take a parameter, \code{location}, which specifies
+where in the list to place the element, following the conventions for
+the \code{psList}.  The entry \code{mode} for \code{psMetadataAddItem}
+is a bit mask constructed by OR-ing the allowed option flags (eg,
+\code{PS_META_REPLACE}) which specify minor variations on the
+behavior.  The \code{format} entry, which specifies both the metadata
+type and the optional flags, is constructed by bit-wise OR-ing the
+appropriate \code{psMetadataType} and allowed option flags.  Care
+should be taken not to leak memory when appending an item for which
+the key already exists in the metadata (and is not
+\code{PS_META_MULTI}).
+%
+\begin{datatype}
+typedef enum {                          ///< option flags for psMetadata functions
+    PS_META_DEFAULT         = 0,        ///< default behavior (0x0000) for use in mode above
+    PS_META_REPLACE         = 0x1000000 ///< allow entry to be replaced
+    PS_META_DUPLICATE_OK    = 0x2000000 ///< allow duplicate entries
+    PS_META_NULL            = 0x4000000 ///< psMetadataItem.data is a NULL value
+} psMetadataFlags;
+\end{datatype}
+The functions above take option flags which modify the behavior when
+metadata items are added to the metadata list.  These flags must be
+bit-exclusive of those used above for the \code{psMetadataTypes}.  The
+flags have the following meanings:
+\code{PS_META_DEFAULT}: This is the zero bit mask, to allow the
+default behavior for \code{psMetadataAddItem} above.  If this is OR-ed
+with a \code{psMetadataType}, the result is as if no OR-ing took
+place.
+\code{PS_META_REPLACE}: Replace an existing, unique entry. If the
+given metadata item exists in the metadata collection, and is not of
+type \code{PS_META_MULTI}, then the item replaces the existing entry.
+\code{PS_META_DUPLICATE_OK}: Allow the new metadata item key to be a
+duplicate (ie, \code{PS_META_MULTI}).  If an existing item with the
+same key is already \code{PS_META_MULTI}, the new item is added to the
+\code{PS_META_MULTI} list.  If the existing item is not
+\code{PS_META_MULTI}, a \code{PS_META_MULTI} list is created to
+contain both the existing item and the new item.  The original entry's
+location on the psMetadata.list must be maintained.
+\code{PS_META_NULL}:  Indicates that \code{psMetadataItem.data} should be
+ignored and that the the current value is ``NULL'' or undefined.  The
+\code{psMetadataItem} must have a proper \code{type} set and it's \code{data}
+field shall have a valid value.  e.g. A \code{type} of \code{PS_META_STR} would
+require that 's \code{data} is set to \code{NULL}.
+There are several of cases to handle for duplication of an existing
+key by a new key, some identified above.  The following situations
+must also be handled:
+If the new key already exists, but is not \code{PS_META_MULTI}, and
+the new item is not flagged as either \code{PS_META_DUPLICATE_OK} or
+\code{PS_META_REPLACE}, an error is raised.
+If the new key already exists, and the existing item is
+\code{PS_META_MULTI}, the new item is added to the MULTI list.  Note
+that if the new item is also of type \code{PS_META_MULTI}, no action
+is taken, but a successful exit status is returned (the action of
+adding a \code{PS_META_MULTI} item to the metadata is equivalent to
+setting that key to be tagged as \code{PS_META_MULTI}.  If it is
+{\em already} \code{PS_META_MULTI}, this effect has already been
+achieved).
+An example of code to use these metadata APIs to generate the
+structure seen in Figure~\ref{fig:metadata} is given below.
+\begin{verbatim}
+md = psMetadataAlloc();
+psMetadataAdd(md, PS_LIST_TAIL, "SIMPLE",   PS_META_BOOL, "basic fits",            TRUE);
+psMetadataAdd(md, PS_LIST_TAIL, "BLANK",    PS_META_S32,  "invalid pixel data",    -32768);
+psMetadataAdd(md, PS_LIST_TAIL, "DATE-OBS", PS_META_STR,  "observing date UT", "   2004-6-16");
+psMetadataAdd(md, PS_LIST_TAIL, "COMMENT",  PS_META_LIST, "head of comment block", NULL);
+psMetadataAdd(md, PS_LIST_TAIL, "COMMENT",  PS_META_STR,  "",                      "DATA");
+psMetadataAdd(md, PS_LIST_TAIL, "COMMENT",  PS_META_STR,  "",                      "PARAMS");
+psMetadataAdd(md, PS_LIST_TAIL, "EXPTIME",  PS_META_F32,  "exposure time (sec)",   1.05);
+psMetadataAdd(md, PS_LIST_TAIL, "COMMENT",  PS_META_STR,  "",                      "FOO");
+cell = psMetadataAlloc();
+psMetadataAdd(cell, PS_LIST_TAIL, "EXTNAME",  PS_META_STR,  "",                    "CCD00");
+psMetadataAdd(cell, PS_LIST_TAIL, "BIASNAME", PS_META_STR,  "",                    "BSEC-00");
+psMetadataAdd(cell, PS_LIST_TAIL, "CHIP",     PS_META_STR,  "",                    "CHIP.00");
+psMetadataAdd(md,   PS_LIST_TAIL, "CELL.00",  PS_META_META, "",                    cell);
+cell = psMetadataAlloc();
+psMetadataAdd(cell, PS_LIST_TAIL, "EXTNAME",  PS_META_STR,  "",                    "CCD01");
+psMetadataAdd(cell, PS_LIST_TAIL, "BIASNAME", PS_META_STR,  "",                    "BSEC-01");
+psMetadataAdd(cell, PS_LIST_TAIL, "CHIP",     PS_META_STR,  "",                    "CHIP.01");
+psMetadataAdd(md,   PS_LIST_TAIL, "CELL.01",  PS_META_META, "",                    cell);
+\end{verbatim}
+The following code shows how to use the APIs to replace one of these values:
+\begin{verbatim}
+psMetadataAdd(md, PS_LIST_TAIL, "EXPTIME",  PS_META_F32 | PS_REPLACE,  "new exposure time (sec)",   2.05);
+\end{verbatim}
+As a convenience to the user, the following type-specific functions
+are specified:
+\begin{prototype}
+bool psMetadataAddStr(psMetadata* md, psS32 location, const char* name, const char* comment,
+                        const char* value);
+bool psMetadataAddS32(psMetadata* md, psS32 location, const char* name, const char* comment, psS32 value);
+bool psMetadataAddF32(psMetadata* md, psS32 location, const char* name, const char* comment, psF32 value);
+bool psMetadataAddF64(psMetadata* md, psS32 location, const char* name, const char* comment, psF64 value);
+bool psMetadataAddBool(psMetadata* md, psS32 location, const char* name, const char* comment, bool value);
+bool psMetadataAddPtr(psMetadata* md, psS32 location, const char* name, psMetadataType type,
+                        const char* comment, psPtr value);
+\end{prototype}
+Items may be removed from the metadata by specifying a key or a
+location in the list.  If the value of \code{name} is \code{NULL}, the
+value of \code{location} is used.  If the value of \code{name} is not
+\code{NULL}, then \code{location} must be set to
+\code{PS_LIST_UNKNOWN}.  If the key matches a metadata item, the item
+is removed from the metadata and \code{true} is returned; otherwise,
+\code{false} is returned.  If the key is not unique, then \emph{all}
+items corresponding to the key are removed, and \code{true} is
+returned.
+%
+\begin{prototype}
+bool psMetadataRemove(psMetadata *md, int location, const char *key);
+\end{prototype}
+Items may be found within the metadata by providing a key.  In the
+event that the key is non-unique, the first item is returned.
+\begin{prototype}
+psMetadataItem *psMetadataLookup(const psMetadata *md, const char *key);
+\end{prototype}
+Several utility functions are provided for simple cases.  These
+functions perform the effort of casting the data to the appropriate
+type.  The numerical functions shall return 0.0 if their key is not
+found.  If the pointer value of \code{status} is not \code{NULL}, it
+is set to reflect the success or failure of the lookup.
+\begin{prototype}
+psPtr psMetadataLookupStr(bool *status, const psMetadata *md, const char *key);
+psS32 psMetadataLookupS32(bool *status, const psMetadata *md, const char *key);
+psF32 psMetadataLookupF32(bool *status, const psMetadata *md, const char *key);
+psF64 psMetadataLookupF64(bool *status, const psMetadata *md, const char *key);
+bool psMetadataLookupBool(bool *status, const psMetadata *md, const char *key);
+psPtr psMetadataLookupPtr(bool *status, const psMetadata *md, const char *key);
+\end{prototype}
+Items may be retrieved from the metadata by their entry position.  The
+value of which specifies the desired entry in the fashion of
+\code{psList}.
+\begin{prototype}
+psMetadataItem *psMetadataGet(const psMetadata *md, int location);
+\end{prototype}
+The metadata list component may be iterated over by using a
+\code{psMetadataIterator} in a fashion equivalent to the
+\code{psListIterator}:
+\begin{datatype}
+typedef struct {
+    psListIterator* iter;              ///< iterator for the psMetadata's psList
+    regex_t* regex;                     ///< the subsetting regular expression
+} psMetadataIterator;
+\end{datatype}
+The iterator may be set to a location in the \code{psMetadata} list,
+and the user may get the previous or next item in the list relative to
+that location.  \code{psMetadataGetNext} has the ability to match the
+key using a POSIX \code{regex}, e.g., if the user only wants to
+iterate through \code{IPP.machines.sky} and doesn't want to bother
+with \code{IPP.machines.detector}.  The iterator should iterate over
+every item in the metadata list, even those that are contained in a
+\code{PS_META_LIST}.  The value \code{iterator} specifies the iterator
+to be used.  In setting the iterator, the position of the iterator is
+defined by \code{location}, which follows the conventions of the
+\code{psList} iterators.
+\begin{prototype}
+psMetadataIterator *psMetadataIteratorAlloc(psMetadata *md, int location, const char *regex);
+bool psMetadataIteratorSet(psMetadataIterator *iterator, int location);
+psMetadataItem *psMetadataGetAndIncrement(psMetadataIterator *iterator);
+psMetadataItem *psMetadataGetAndDecrement(psMetadataIterator *iterator);
+\end{prototype}
+Metadata items may be printed to an open file descriptor based on a
+provided format.  The format string is an sprintf format statement
+with exactly one \% formatting command.  If the metadata item type is
+a numeric type, this formatting command must also be numeric, and type
+conversion performed to the value to match the format type.  If the
+metadata item type is a string, the formatting command must also be
+for a string (\%s type of command).  If the metadata type is any other
+data type, printing is not allowed.
+\begin{prototype}
+bool psMetadataItemPrint(FILE *fd, const char *format, const psMetadataItem *item);
+\end{prototype}
+\subsubsection{Configuration files}
+\label{sec:configspec}
+It will be necessary for the \PS{} system, in order to load
+pre-defined settings, to parse a configuration file into a
+\code{psMetadata} structure.  This shall be performed by the
+function \code{psMetadataConfigParse}, as described below.
+\begin{prototype}
+psMetadata *psMetadataConfigParse(psMetadata *md, int *nFail, const char *filename, bool overwrite);
+\end{prototype}
+Given a metadata container, \code{md}, and the name of a configuration
+file, \code{filename}, \code{psMetadataConfigParse} shall parse the
+configuration file, placing the contained key/type/value/comment quads
+into the metadata, and returning a pointer to the metadata structure.
+The number of lines that failed to parse is returned in \code{nFail}.
+Multiple specifications of a key that haven't been declared (see
+below) are overwritten if and only if \code{overwrite} is \code{true}.
+If the metadata container is \code{NULL}, it shall be allocated.
+On error, the function shall return \code{NULL}.
+It is also useful to be able to convert a \code{psMetadata} structure into the
+Configuration File format for debugging purposes and to enable persistent
+configuration.
+\begin{prototype}
+char *psMetadataConfigFormat(psMetadata *md);
+bool psMetadataConfigWrite(psMetadata *md, const char *filename);
+\end{prototype}
+The \code{psMetadataConfigFormat} function converts a \code{psMetadata}
+structure (including any nested \code{psMetadata}) into a Configuration File
+formatted string.  A \code{NULL} shall be returned on error.  The
+\code{psMetadataConfigWrite} behaves the same as \code{psMetadataConfigFormat}
+except that the string is written out to \code{filename}.  \code{false} is
+returned on failure.
+\paragraph{Comments}
+The configuration file shall consist of plain text with
+key/type/value/comment quads on separate lines.  Blank lines,
+including those consisting solely of whitespace (both spaces and
+tabs), shall be ignored, as shall lines that commence with the comment
+character (a hash mark, \code{#}), either immediately at the start of
+the line, or preceded by whitespace.  The key/type/value/comment quads
+shall all lie on a single line, separated by whitespace.
+The key shall be first, possibly preceded on the line by whitespace
+which should not form part of the key.
+\paragraph{NULL values}
+The ``value'' of a quad may be declare to be undefined with the \code{NULL}
+keyword.  \code{NULL} is allowed to co-exist with a ``comment'' and may be
+surrounded by whitespace.  Any non-whitespace character will cause of the
+``value'' to be interpreted as a string.
+\begin{verbatim}
+foo     STR     NULL    # string with a NULL value
+bar     STR     NULL a  # string with a value of "NULL a"
+\end{verbatim}
+\paragraph{Types}
+\subparagraph{Scalar \& Vector}
+Next, to assist the casting of the value, shall be a string identifying the
+type of the value, which shall correspond to one of the simple types supported
+in \code{psMetadata}: \code{STRING,BOOL,S32,F32,F64}; \code{STR} may be used to
+abbreviate \code{STRING}; valid time types are \code{UTC,UT1,TAI,TT}.
+\tbd{May, in the future, require more types, including U8,S16,C64,
+which will also necessitate updating the definition of psMetadata.}
+The value shall follow the type: strings may consist of multiple words, and
+shall have all leading and trailing whitespace removed; booleans shall simply
+be either \code{T} or \code{F}.  Time type values will be in the ISO8601
+compatible format of "YYYY-MM-DDTHH:MM:SS,sZ".  When parsed, time types shall
+be represented as a \code{psTime} object.
+Following the value may be an optional comment, preceded by a comment
+character (a hash mark, \code{#}), which in the case of a string
+value, serves to mark the end of the value, and for other types serves
+to identify the comment to the reader.  Only one comment character may
+be present on any single line (i.e., neither strings nor comments are
+permitted to contain the comment character).  The comment may consist
+of multiple words, and shall have leading and trailing whitespace
+removed.
+One wrinkle is the specification of vectors.  Keys for which the value
+is to be parsed as a vector shall be preceded immediately by a
+``vector symbol'', which we choose to be the ``at'' sign, \code{@}.
+In this case, the type shall be interpreted as the type for the
+vector, which may be any of the signed or unsigned integer or floating
+point types (\code{U8,U16,U32,U64,S8,S16,S32,S32,S64,F32,F64}) but not
+the complex floating point types; and the value shall consist of
+multiple numbers, separated either by a comma or whitespace.  These
+values shall populate a \code{psVector} of the appropriate type in the
+order in which they appear in the configuration file.
+\tbd{May add complex types, likely to be specified with values such as
+.23+4.56i in the future.}
+\tbd{May add null, Not-a-Number (NaN), de-normalized, underflow, overflow,
+and/or +/-infinity values for selected types.}
+\subparagraph{MULTI}
+An additional hurdle is the specification of keys that may be non-unique (such
+as the \code{COMMENT} keyword in a FITS header).  These keys shall be specified
+in the configuration file as non-unique with a \code{MULTI} declaration.  In
+the form \code{[keyword] MULTI}.  No other data may be provided on this line,
+though a comment, preceded by the comment marker, is valid.  A warning shall
+be produced when a key which has not been specified to be non-unique is
+repeated; in this case, the former value shall be overwritten if
+\code{overwrite} is \code{true}, otherwise the line shall be ignored and
+counted as one that could not be parsed.  It should be noted that non-unique
+keys may be of mixed type (even the \code{TYPE} and \code{METADATA} complex
+types). For example:
+\begin{verbatim}
+comment     MULTI   # a comment
+comment     STR     some string
+comment     F32     1.23456
+comment     BOOL    T
+\end{verbatim}
+If a line does not conform to the rules laid out here, a warning shall
+be generated, it shall be ignored and counted as a line that could not
+be parsed.  The total number of lines that were not able to be parsed
+(including those that were ignored because \code{overwrite} is
+\code{false}, and any other parsing problems, but not including blank
+lines and comment lines) shall be returned by the function in the
+argument \code{nFail}.
+Here are some examples of lines of a valid configuration file:
+\filbreak
+\begin{verbatim}
+Double     F64     1.23456789      # This is a comment
+Float    F32 0.98765 # This is a comment too
+String  STR This is the string that forms the value #comment
+ # This is a comment line and is to be ignored
+boolean     BOOL    T # The value of `boolean' is `true'
+@primes U8  2,3 5 7,11,13 17 #   These are prime numbers
+comment MULTI # The rest of this line is ignored, but `comment' is set to be non-unique
+comment STR This
+comment STR     is
+comment STR       a
+comment STR        non-unique
+comment STR                  key
+Float F64 1.23456 # This generates a warning, and, if `overwrite' is `false', is ignored
+\end{verbatim}
+Of course, a real configuration file should look much nicer to humans
+than the above example, but PSLib must be able to parse such ugly
+files.
+\paragraph{Complex Types}
+\subparagraph{TYPE}
+We support a modest tree structure by defining a reserved keyword \code{TYPE}.
+Any line in the config file which starts with the word \code{TYPE} shall be
+interpreted as defining a new valid type.  The defined type name follows the
+word \code{TYPE}, and is in turn followed by an arbitrary number of words.
+These words are to be interpreted as the names of an embedded \code{psMetadata}
+entry, where the values are given on any line which (following the \code{TYPE}
+definition) employs the new type name.  For example, a new type may be defined
+as:
+\begin{verbatim}
+TYPE      CELL   EXTNAME   BIASSEC  CHIP
+CELL.00   CELL   CCD00     BSEC-00  CHIP.00
+CELL.01   CELL   CCD01     BSEC-01  CHIP.00
+\end{verbatim}
+When \code{psMetadataConfigParse} encounters the \code{TYPE} line, it
+should construct a \code{psMetadata} container and fill it with
+\code{psMetadataItems} having the names \code{EXTNAME, BIASSEC, CHIP},
+with type \code{PS_META_STR}, but data allocated.  When it next
+encounters an entry of type \code{CELL}, it should then use the given
+name (e.g., \code{CELL.00}) for the \code{psMetadataItem}, and copy
+the \code{psMetadata} data onto the \code{psMetadataItem.data.md}
+entry, filling in the values from the rest of the line (\code{CCD00,
+BSEC-00, CHIP.00}).  This hierarchical structure is illustrated in
+Figure~\ref{fig:metadata}.
+\subparagraph{METADATA}
+Another way to form a tree-like structure is to directly define a
+\code{psMetadata} entry using a sequence of successive lines to define the
+values of the \code{psMetadataItem} entries.  The initial line defines the new
+\code{psMetadata} entry and its name.  The following lines have the same format
+as the other metadata config file entries.  The sequence is terminated with a
+line with a single word \code{END}.  For example, a metadata entry may be
+defined as:
+\begin{verbatim}
+CELL      METADATA
+ EXTNAME   STR   CCD00
+ BIASSEC   STR   BSEC-00
+ CHIP      STR   CHIP.00
+ NCELL     S32   24
+END
+\end{verbatim}
+\paragraph{Scoping Rules}
+A simple set of ``Scoping Rules'' are required to properly parse a
+configuration file.  ``Scope'' refers to the current ``level'' of
+\code{METADATA} that a statement appears in.  Statements that are not contained
+in a nested \code{METADATA} are said to be in the ``Top level scope''.  Each
+level of nested \code{METADATA} statements create a new ``lower level scope''.
+\begin{itemize}
+\item
+Variable names are unique only to the current level of scope.
+\item
+non-unique keywords (\code{MULTI}) apply only to the current scope.  i.e. They
+are invalid in ``higher'' or ``lower'' level scopes.
+\item
+\code{TYPE} declarations apply only to the current scope.
+\item
+\code{METADATA} declarations must begin and end in the same scope.  i.e.  They
+may not be declared and end in two different nested METADATA and the same
+depth.
+\end{itemize}
+A series of test inputs is contained in
+\S\ref{sec:configtest}.
+\section{Input/Output}
 \subsection{XML Functions}
 …
 fail and return FALSE.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \pagebreak
 \section{Data manipulation}
 …
 following capabilities:
 \begin{itemize}
-\item Bit masks;
 \item Vector and image arithmetic;
 \item Sorting;
 …
 \item Matrix operations and linear algebra;
 \item (Fast) Fourier Transforms;
 \item General functions; and
+\item General mathematical functions; and
 \item Minimization and fitting routines.
 \end{itemize}
 …
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \subsection{Statistics Functions}
 \subsubsection{Vector Statistics}
+\subsection{Statistical Functions}
+\subsubsection{Statistical measures}
 We require a very general statistics function, which, given a vector
 …
 %% \subsubsubsection{Pre-defined Functions for LM}
+%%
 %% We define some commonly used functions for use with the LM
 %% minimization, used for the purpose of performing $\chi^2$ fitting:
+%%
 %% \begin{prototype}
 %% psMinimizeLMChi2Func psMinimizeLMChi2Gauss1D;
 %% psMinimizeLMChi2Func psMinimizeLMChi2Gauss2D;
 %% \end{prototype}
+%%
 %% \code{psMinimizeChi2LMGauss1D} shall take as \code{params}, the
 %% normalization, center, and standard deviation of a Gaussian to be fit,
 …
 %% the value of the Gaussian at the value, and the derivatives
 %% (\code{deriv}) with respect to each of the parameters.
+%%
 %% \code{psMinimizeChi2LMGauss2D} shall take, as \code{params}, the
 %% normalization, center (two values), standard deviation (two values)
 …
 the following types: \code{psU8}, \code{psU16}.
+\begin{prototype}
+psImage *psPixelsToMask(psImage *out, const psPixels *pixels, psRegion region, unsigned int maskVal);
+psPixels *psPixelsFromMask(psPixels *out, const psImage *mask, unsigned int maskVal);
+\end{prototype}
+\code{psPixelsToMask} shall return an image of type U8 with the
+\code{pixels} lying within the specified \code{region} set to the
+\code{maskVal}.  The \code{out} image shall be modified if supplied,
+or allocated and returned if \code{NULL}.  The size of the output
+image shall be \code{region.x1 - region.x0} by \code{region.y1 -
+region.y0}, with \code{out->x0 = region.x0} and \code{out->y0 =
+region.y0}.  In the event that either of \code{pixels} or
+\code{region} are \code{NULL}, the function shall generate an error
+and return \code{NULL}.
+\code{psMaskToPixels} shall return a \code{psPixels} containing the
+coordinates in the \code{mask} that match the \code{maskVal}.  The
+\code{out} pixel list shall be modified if supplied, or allocated and
+returned if \code{NULL}.  In the event that \code{mask} is
+\code{NULL}, the function shall generate an error and return
+\code{NULL}.
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 …
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \subsection{Matrix operations and linear algebra}

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 4239

Legend:

trunk/doc/pslib/ChangeLogSDRS.tex

trunk/doc/pslib/psLibSDRS.tex

Download in other formats: