Index: /trunk/doc/draft/metadata.tex =================================================================== --- /trunk/doc/draft/metadata.tex (revision 130) +++ /trunk/doc/draft/metadata.tex (revision 130) @@ -0,0 +1,169 @@ +\documentclass[panstarrs]{panstarrs} +\newcommand\note[1]{{\bf #1}} +\newcommand\tbd[1]{{\bf [#1]}} + +\title{The \PS{} Metadata API} +\author{Robert Lupton, Gene Magnier} +\group{} +\organization{} +\docnumber{PSDC-???} + +\fancyhead{} +\fancyhead[L]{\PS{} Document} +\fancyhead[R]{PSDC-???} +\fancyhead[C]{Revision 0.1 -- Draft} +\fancyfoot[L]{psMetaData} +\fancyfoot[R]{\today} + +\begin{document} + +\pagenumbering{roman} \thispagestyle{empty} \maketitle + +\pagebreak \pagestyle{fancy} +{ \Large \bf Revision History} +\begin{center} +\begin{tabular}{|p{1in}|p{1in}|p{4.5in}|} +\hline +{\bf Revision Number} & {\bf Release Date} & {\bf Description} \\ +\hline +%0.1 & 2003/12/08 & First draft \\ +\hline +\end{tabular} +\end{center} + +{ \Large \bf Referenced Documents} +\begin{center} +\begin{tabular}{|p{1in}|p{2.75in}|p{2.75in}|} +\hline +{\bf PanSTARRS ID} & {\bf Title} & {\bf Author} \\ +\hline +%%% References here. +\hline +\end{tabular} +\end{center} + +\pagebreak +\tableofcontents + +% \pagebreak +% \listoffigures + +\pagebreak \pagenumbering{arabic} + +\section{Introduction} + +This document addresses the question of how \PS{} +metadata should be represented in memory. We do not +(yet) address how it should be represented on disk. + +\section{Metadata Representation} + +We propose that an item of metadata be represented as a C structure: +\begin{verbatim} +/* + * A struct to define a single item of metadata + */ +typedef struct { + const int id; // unique ID for this item + + char *name; // Name of item + psMetaDataType type; // type of this item + const union { + float f; // floating value + int i; // integer value + void *v; // other type + } val; // value of metadata + char *comment; // optional comment ("", not NULL) + +} psMetaData; +\end{verbatim} + +The \code{id} is a unique identifier for this item of metadata; experience +shows that such tags are useful. + +The \code{psMetaDataType type} entry specifies the type of the data +being represented; the possibilities are listed in section \ref{metadataTypes}. + +\subsection{Possible Types of Metadata} +\label{metadataTypes} + +The possible types of metadata are identified by the enumerated type +\code{psMetaDataType} (see also table \ref{tabMetaDataTypes}): +\begin{verbatim} +/* + * Possible types of metadata. + */ +typedef enum { // type of val is: + psMetaFloat = 0, // float (.f) + psMetaInt, // int (.i) + psMetaStr, // string (.v) + psMetaImg, // image (.v) + psMetaJPEG, // JPEG (.v) + psMetaPNG, // PNG (.v) + psMetaAstrom, // astrometric coefficients (.v) + psMetaUnknown, // other (.v) + psMetaNType // Number of types; must be last +} psMetaDataType; +\end{verbatim} + +\begin{table} +\begin{tabular}{llll} +\textbf{Value} & \textbf{Type} & \textbf{member of union} & \textbf{Comments}\\ +\hline +psMetaFloat & float & f & value, not pointer, is stored \\ +psMetaInt & int & i & value, not pointer, is stored \\ +psMetaStr & string & v & value, not pointer to original, is stored \\ +psMetaImg & psImage & v & \\ +psMetaJPEG & JPEG & v & \\ +psMetaPNG & PNG & v & \\ +psMetaAstrom & psAstrom & v & \\ +psMetaUnknown & other & v & \\ +psMetaNType & (none) & & The number of types defined +\end{tabular} +\begin{caption}{Supported Metadata Types} +\label{tabMetaDataTypes} + Possible types of metadata +\end{caption} +\end{table} + +\section{Collections of Metadata} + +We also need to support a container class for metadata. We propose +using the standard \PS{} doubly-linked list type \code{psDlist} +(see \href{file:utils#psDlist}{utils.pdf} for details). For example: +\begin{verbatim} + psDlist *list = psDlistNew(NULL); // list of metadata + + psDlistAppend(list, psMetaDataNew("const.ten", psMetaInt, &ten, NULL, 0)); + psDlistAppend(list, psMetaDataNew("const.sqrt2", psMetaFloat, &sqrt2, + "square root of two", 0)); + psDlistAppend(list, psMetaDataNew("lang.hello", psMetaStr, "Bonjour", + "French", 0)); + /* + * Print all metadata to stdout + */ + (void)psDlistGet(list, psDlistTail); // initialise iterator + while ((ms = psDlistGet(list, psDlistPrev)) != NULL) { + psMetaDataPrint(stdout, ms); + } + /* + * Clean up + */ + psDlistDel(list, (void (*)(void *))psMetaDataDel); +\end{verbatim} + +\section{Naming convention for MetaData} + +The \code{psMetaData} struct includes a name. This name should be of +the form \code{name1.name2.name3$\cdots$}, e.g.\hfil\break +\null\qquad\qquad\code{IPP.phase1.ota12.biassec}. + +We shall set in place a system for assigning the top-level `domains' +to responsible individuals, and for gathering a complete list of +all metadata names in use throughout the project. + + +\bibliographystyle{plain} +\bibliography{panstarrs} + +\end{document} Index: /trunk/doc/draft/utils.tex =================================================================== --- /trunk/doc/draft/utils.tex (revision 130) +++ /trunk/doc/draft/utils.tex (revision 130) @@ -0,0 +1,987 @@ +\documentclass[panstarrs]{panstarrs} +\newcommand\note[1]{{\bf #1}} +\newcommand\tbd[1]{{\bf [#1]}} + +\title{The \PS{} Utilities API} +\author{Robert Lupton} +\group{} +\organization{} +\docnumber{PSDC-???} + +\fancyhead{} +\fancyhead[L]{\PS{} Document} +\fancyhead[R]{PSDC-???} +\fancyhead[C]{Revision 0.1 -- Draft} +\fancyfoot[L]{\PS{} Utilities} +\fancyfoot[R]{\today} + +\begin{document} + +\pagenumbering{roman} \thispagestyle{empty} \maketitle + +\pagebreak \pagestyle{fancy} +{ \Large \bf Revision History} +\begin{center} +\begin{tabular}{|p{1in}|p{1in}|p{4.5in}|} +\hline +{\bf Revision Number} & {\bf Release Date} & {\bf Description} \\ +\hline +%0.1 & 2003/12/08 & First draft \\ +\hline +\end{tabular} +\end{center} + +{ \Large \bf Referenced Documents} +\begin{center} +\begin{tabular}{|p{1in}|p{2.75in}|p{2.75in}|} +\hline +{\bf \PS{} ID} & {\bf Title} & {\bf Author} \\ +\hline +%%% References here. +\hline +\end{tabular} +\end{center} + +\pagebreak +\tableofcontents + +% \pagebreak +% \listoffigures + +\pagebreak \pagenumbering{arabic} + +\section{Memory Management} +\hlabel{psMemBlock} + +\subsection{Introduction} + +The \PS{} software system will need a level of memory management +placed between the operating system (malloc/free) and the high level +routines (e.g. \code{psMetaDataNew}). + +This layer is in addition to the possibility that specific heavily +used data types may need their own special-purpose memory managers; +but as we have specified that all user-level objects be allocated via +\code{typeNew/typeDel} functions, we will easily be able to +implement such functionality without impacting on the facilities +described here. + +All of the memory management APIs should be provided in a header file +\file{psMemory.h} which is included by \file{psUtils.h}. + +\textit{Do we want to rename \code{psAlloc} to \code{psNew} and + \code{psFree} to \code{psDel}? Or is it too late? XXX} + +\subsection{Rationale} + +We wish to insert our own layer of memory management for a number of +reasons: + +\begin{itemize} +\item + We wish to insulate ourselves from the details of the system-provided + \code{malloc}. There is no guarantee that the goals of the system + architect align with those of the \PS{} processing + +\item + We need at least a wrapper layer which handles failed memory + requests without requiring the application programmer to check + every attempted allocation. + +\item + We need to provide a mechanism for tracking and fixing memory + leaks. While it is possible to do this by linking with external + libraries (XXX reference), it is convenient to do so within the + \PS{} framework. + +\item + Similarly, we wish to provide convenient hooks to detect and diagnose + memory corruption. + +\item + While debugging complex scientific code, it is very useful to be + able to trace a given data structure as it passed through the + processing pipeline. + +\item + There may be other features that we wish to add in the future (e.g. + associating a type with every allocation). +\end{itemize} + +\subsection{A Minimal Specification} + +The previous section laid out a number of desiderata for a memory +management system. Rather than implement our own heap-manager at this +stage of the project, I propose that we put in place a sufficient +set of data structures and APIs, but initially implement only +a simple subset (e.g. that we not implement a multi-bucket memory +manager that takes in 100Mb chunks from the system and performs +sophisticated defragmentation and garbage collection). + +Subject to agreement with the IfA, some of the functions proposed +here may be omitted from the initial implementation; in particular +the routines \code{psMemCheckCorruption} and \code{psMemCheckLeaks} +may be hard to build efficiently in a simple implementation based +upon adding extra fields to allocation requests. + +\subsubsection{Extra information to be saved by Memory Allocation Functions} + +It is required that a table of all allocated memory blocks be +maintained by the \PS{} memory system. + +Each allocated block should preserve at least the information present +in the following struct definition: +\begin{verbatim} + typedef struct { + const unsigned long id; // a unique ID for this allocation + const char *file; // set from __FILE__ in e.g. p_psAlloc + const int lineno; // set from __LINE__ in e.g. p_psAlloc + int refcntr; // how many times pointer is referenced + const void *magic; // initialised to P_PS_MEMMAGIC + } psMemBlock; +\end{verbatim} + +The value of \code{P_PS_MEMMAGIC} shall be \code{(void *)0xdeadbeef}% +\footnote{Why this choice? Tradition, and because it's easy to notice + in a hex dump.} + +\subsubsection{APIs for using Memory Allocation Functions} + +\begin{table} +\begin{verbatim} +void *psAlloc(size_t size); +void *psRealloc(void *ptr, size_t size); +void psFree(void *ptr); + +void *p_psAlloc(size_t size, const char *file, int lineno); +void *p_psRealloc(void *ptr, size_t size, const char *file, int lineno); +void p_psFree(void *ptr, const char *file, int lineno); + +#define psAlloc(size) p_psAlloc(size, __FILE__, __LINE__) +#define psRealloc(ptr, size) p_psRealloc(ptr, size, __FILE__, __LINE__) +#define psFree(size) p_psFree(size, __FILE__, __LINE__) +\end{verbatim} +\begin{caption}{The APIs required to use the \PS{} memory allocation routines} + \hlabel{tabUsageAPI} + The APIs required to use the \PS{} memory allocation routines, and as + provided by \file{psMemory.h}. +\end{caption} +\end{table} + +The types and function prototypes for the part of the memory API +concerned with allocating and freeing memory are given in table +\ref{tabUsageAPI}). + +N.b. +\begin{itemize} +\item + The functions \code{psAlloc}, \code{psRealloc}, and + \code{psFree} are defined, and are required to be equivalent to + \code{p_psAlloc}, \code{p_psRealloc}, and \code{p_psFree} + with the final two arguments \code{"(unknown)"} and \code{0}. + + In the descriptions that follow, I shall not distinguish between the + functions with and without the \code{p_} prefix. + +\item + Except as specified below, the functions \code{psAlloc}, + \code{psRealloc}, and \code{psFree} have identical semantics + to the standard C library functins \code{malloc}, \code{realloc}, + and \code{free}. + +\item + In all cases, application code will call + \code{p_\{psAlloc,psRealloc,psFree\}} via the macros defined above. + +\item + The functions \code{psAlloc} and \code{psRealloc} shall never + return a \code{NULL} pointer. If they are unable to provide + the requested memory they should attempt to obtain the desired + memory by calling the routine registered by \code{psMemExhaustedSetCB} (see + subsubsection \ref{secMemAdvanced}), and if still unsuccessful, + call \code{abort()}. + +\item + The memory management routines shall maintain the field + \code{psMemBlock.refcntr}. It should be set to \code{1} + when a block is returned to the user. It is an error to + attempt to free a block with \code{psMemBlock.refcntr != 1} + (see subsubsection \ref{secMemRefcntr}). + +\item + Where practical and efficient, the memory manager shall call + the routine registered using the \code{psMemProblemSetCB} + (see section \ref{secMemAdvanced}) + whenever a corrupted block of memory is discovered. For example, + doubly-freed blocks can be detected by checking \code{psMemBlock.refcntr}. + +\item + There is no \code{psCalloc} function. Initialisation of data is + almost always more complex than setting all bytes to 0. +\end{itemize} + +\subsubsection{APIs for Tracing and Debugging Memory} +\hlabel{secMemAdvanced} + +\begin{table} +\begin{verbatim} +typedef int (*psMemCallback)(const psMemBlock *ptr); +typedef void (*psMemProblemCallback)(const psMemBlock *ptr, + const char *file, int lineno); +typedef void *(*psMemExhaustedCallback)(size_t size); + +psMemProblemCallback psMemProblemSetCB(psMemProblemCallback func); +psMemExhaustedCallback psMemExhaustedSetCB(psMemExhaustedCallback func); + +psMemCallback psMemAllocateSetCB(psMemCallback func); +psMemCallback psMemFreeSetCB(psMemCallback func); + +int psMemGetId(void); // get next memory ID + +long psMemSetAllocateID(long id); // set p_psMemAllocateID to id +long psMemSetFreeID(long id); // set p_psMemFreeID to id + +int psMemCheckLeaks( + int id0, // don't list blocks with id < id0 + psMemBlock ***arr, // pointer to array of pointers to + //leaked blocks, or NULL + FILE *fd); // print list of leaks to fd (or NULL) +int psMemCheckCorruption(int abort_on_error); +\end{verbatim} +\begin{caption}{The APIs required to use the \PS{} memory allocation routines} + \hlabel{tabCallbackAPI} + The APIs required to use the callback and tracing facilities + in \PS{} memory allocation routines, as defined in \file{psMemory.h}. +\end{caption} +\end{table} + +The types and function prototypes for this part of the memory API +are given in table \ref{tabCallbackAPI}. + +\subsubsection{Callback Routines} + +The four `\code{SetCB}' routines are: + +\begin{tabular}{ll|l} +\textbf{type} & \textbf{Name} & \textbf{Function of callback} \\ +psMemProblemCallback & psMemProblemSetCB & +Called when a problem is detected with data being managed on the heap \\ +psMemExhaustedCallback & psMemExhaustedSetCB & +Called when \code{psAlloc} is unable to satisfy a memory request. \\ +psMemCallback & psMemAllocateSetCB & +Callback is called when the \code{psMemBlock} with a specified ID is +allocated. \\ +psMemCallback & psMemFreeSetCB & +Callback is called when the \code{psMemBlock} with a specified ID is +freed. \\ +\end{tabular} + +N.b. +\begin{itemize} +\item + In all cases, the `\code{SetCB}' routine takes a pointer to the + desired callback function, and returns a pointer to the one that was + previously installed. If the function pointer is \code{NULL}, the + default callback function is reinstalled. + +\item + The routine installed by \code{psMemExhaustedSetCB} should return + a pointer to the desired memory or \code{NULL}; in the latter case + \code{psAlloc} will call \code{abort()} + +\item + \code{psMemGetId} returns the current value of \code{psMemBlock.id}. + +\item + The handler specified by \code{psMemAllocateSetCB} is called just + before the pointer with \code{psMemBlock.id} equal to + \code{p_psMemAllocateID} is returned to the user. The variable + \code{p_psMemAllocateID} should not be set directly in any + delivered code, \code{psMemSetAllocateID} should be used instead. + +\item + The handler specified by \code{psMemFreeSetCB} is called just + before the pointer with \code{psMemBlock.id} equal to + \code{p_psMemFreeID} is freed. The variable + \code{p_psMemFreeID} should not be set directly in any delivered + code, \code{psMemSetFreeID} should be used instead. + +\item + The routines \code{psMemSetFreeID} and \code{psMemSetAllocateID} + accept the desired ID value (see previous two items) and return + the old value to the user. + +\item + The return values of the handlers installed by \code{psMemAllocateSetCB} + and \code{psMemFreeSetCB} are used to increment the values of + \code{p_psMemAllocateID} and \code{p_psMemFreeID} respectively. + + For example, the return value \code{0} implies that the value is unchanged; + if the value is \code{2} the callback will be called again when the + memory ID counter has increased by two. +\end{itemize} + +\subsubsection{Memory Tracing and Corruption Routines} + +The routine \code{psMemCheckLeaks} may be used to check for memory +leaks. The return value is the number of blocks that have been +allocated but not freed. + +Only blocks with \code{psMemBlock.id} greater than \code{id0} +are checked; this allows the user to ignore blocks allocated +by initialisation routines. + +If the argument \code{arr} is non-\code{NULL}, then upon entering +the call \code{**arr} should be \code{NULL}. Upon return it is set +to an array of \code{psMemBlock *} pointers, one for each block +allocated but not freed. It is the caller's responsibility to free +this array with \code{psFree}. + +If the argument \code{fd} is non\code{NULL}, a one-line summary +of each block that has been allocated but not freed is written to that +file descriptor. + +The routine \code{psMemCheckCorruption} checks the entire heap for +corruption, calling the routine registered with +\code{psMemProblemSetCB} for each block detected as being corrupted. +The return value is the number of corrupted blocks detected. If the +argument \code{abort_on_error} is true, +\code{psMemCheckCorruption} shall call \code{abort()} as soon as +memory corruption is detected. + +\subsubsection{Reference Counting} +\hlabel{secMemRefcntr} + +The memory management routines include a field +\code{psMemBlock.refcntr} which must equal \code{1} whenever +a pointer is presented to \code{psFree}. + +The API for this field is: +\begin{verbatim} +int psMemGetRefCntr(void *vptr); // return refcntr +void *psMemIncrRefCntr(void *vptr); // increment refcntr and return vptr +void *psMemDecrRefCntr(void *vptr); // decrement refcntr and return vptr +\end{verbatim} + +The functions \code{psMemIncrRefCntr} and \code{psMemDecrRefCntr} shall +return \code{NULL} if passed a \code{NULL} pointer. + +\subsubsubsection{Rationale} + +\begin{table} +\begin{verbatim} +typedef struct { + char *name; + int value; +} psSimple; + +psSimple *psSimpleNew(const char *name, int val) +{ + psSimple *simp = psAlloc(sizeof(psSimple)); + simp->name = strcpy(psAlloc(strlen(name) + 1), name); + simp->value = val; + + return simp; +} + +void psSimpleDel(psSimple *simp) +{ + if (simp == NULL) { return; } + + if (psMemGetRefCntr(simp) > 1) { + (void)psMemDecrRefCntr(simp); + return; + } +} +\end{verbatim} +\begin{caption}{An example of reference counting} + \hlabel{tabReferenceCounting} + An example of using reference counting +\end{caption} +\end{table} + +The \code{psMemBlock.refcntr} is clearly useful for detecting +attempts to free memory that is already free. A more complex +application is for allowing pointers to complex data-objects (e.g. +images) to appear in more than one data structure simultaneously +(see table \ref{tabReferenceCounting}). + +Because of the use of the \code{refcntr} field, we can safely put items of +this type onto many lists: +\goodbreak +\begin{verbatim} +simp = psSimpleNew("RHL", 0); +psDlistAppend(list1, psMemIncrRefCntr(simp)); +psDlistAppend(list2, psMemIncrRefCntr(simp)); +psSimpleDel(simp); +\end{verbatim} + +(Note: in fact there is no need to explicitly increment the counter +in this case, as the \code{psDlistAppend} (section \ref{psDlist}) +API specifies that it +does it for you.) + +\section{Tracing and Logging} + +This document defines the \PS{} Tracing and Logging APIs; the former +refers to debug information that we wish to be able to turn on and off +without recompiling (although it will \emph{not} be available in +production code); the latter means information about the processing +that must be collected and saved, even in the production system. + +\subsection{Tracing APIs} +\hlabel{psTrace} + +\begin{table} + \begin{verbatim} +#if defined(PS_NTRACE) +# define psTrace(facil, level, ...) /* do nothing */ +#else +# define psTrace(facil, level, ...) \ + p_psTrace(facil, level, __VA_ARGS__) +#endif + +void p_psTrace(const char *facil, int level, ...); + +int psSetTraceLevel(const char *facil, // facilty of interest + int level); // desired trace level +int psGetTraceLevel(const char *name); // facilty of interest + +void psPrintTraceLevels(void); // print trace levels + \end{verbatim} + \begin{caption}{The public API for the trace facility + from \file{psTrace.h}.} + \hlabel{tabTraceAPI} + \end{caption} +\end{table} + +The public API for the trace facility (table \ref{tabTraceAPI}) +should be provided in a header file \file{psTrace.h} which +is included by \file{psUtils.h}. + +\begin{itemize} + \item + Logging is provided by the function \code{psTrace}, + which is actually a macro. When the macro \code{PS_NTRACE} + is defined, all occurrences of \code{psTrace} shall + be replaced by whitespace. + + \item + The first argument to \code{psTrace} is a name of the form + \code{aaa.bbb.ccc}. The second is an integer, + \code{level}. The remaining arguments are a printf-style format + and a (possibly empty) set of values for that formatting + string. When this trace is active, \code{psTrace} shall generate + the requested output on \code{stdout}, preceded by \code{level} + spaces. + + \item + The call \code{psSetTraceLevel(name, level)} shall set the trace + level for \code{name} to \code{level}. + + \item + The call \code{psGetTraceLevel(name)} shall return the level + associated with \code{name}. If \code{name} has not been + associated with a level, the routine shall remove the \textit{last} + element of \code{name} and attempt to look up its level; this + procedure shall be applied recursively until the name is reduced + to \code{""}; if this name has no level associated with + it, then the value \code{0} shall be returned (see examples + below). + + \item + The call \code{psTrace(name, level, ...)} + shall print the message if and only if + \code{psGetTraceLevel(name)} returns a value greater than + or equal to \code{level}. + + \item + \code{psPrintTraceLevels} shall print a listing of all + declared levels, displayed as a hierarchy with sub-components + sorted within each component (see examples below). + + Note in particular that the root of the tree, the name \code{""} + should print as \code{(root)}, and nodes which have not + been assigned a value should list their level as \code{.}. + + \item + All of the tracing facilities shall be SWIGed, with the exception + of \code{p_psTrace}. + + \item + There is no requirement that \code{psTrace} be usable from + within the functions that implement \file{psTrace.h} + or \file{psMemory.h} systems. +\end{itemize} + +\subsubsection{Examples of the use of Tracing Facilities} + +For example, after the commands: +\begin{verbatim} + psSetTraceLevel("aaa.bbb.ccc.ddd", 9); + psSetTraceLevel("aaa.bbb.ccc", 3); + psSetTraceLevel("aaa.bbb.ddd", 4); + psSetTraceLevel("aaa.BBB", 2); + psSetTraceLevel("BBB", 2); + psSetTraceLevel("BBB.XXX.YYY.ZZZ", 5); + psSetTraceLevel("aaa.bbb", 2); + psSetTraceLevel("aaa.bbb.ccc", 9); + psSetTraceLevel("aaa", 1); +\end{verbatim} +the command \code{psPrintTraceLevels()} should print: +\begin{verbatim} +(root) 0 + aaa 1 + bbb 2 + ccc 9 + ddd 9 + ddd 4 + BBB 2 + BBB 2 + XXX . + YYY . + ZZZ 5 +\end{verbatim} + +After this set of \code{psSetTraceLevel} commands, and if +\code{PS_NTRACE} is not defined, the following commands +\begin{verbatim} + psTrace("aaa.bbb.ddd", 2, "(aaa.bbb.ddd) Hello %s\n", "world"); + psTrace("aaa", 2, "aaa\n"); + psTrace("", 2, "\"\"\n"); + psTrace("aaa.bbb", 2, "aaa.bbb\n"); + psTrace("aaa.bbb.ddd", 2, "aaa.bbb.ddd\n"); + psTrace("aaa.bbb.ddd", 4, "aaa.bbb.ddd\n"); + psTrace("aaa.bbb.ddd", 2, "aaa.bbb.ddd\n"); + psTrace("aaa.bbb.ccc", 1, "aaa.bbb.ccc\n"); + psTrace("aaa.bbb.eee", 2, "aaa.bbb.eee\n"); +\end{verbatim} +should produce this output: +\begin{verbatim} + (aaa.bbb.ddd) Hello world + aaa.bbb + aaa.bbb.ddd + aaa.bbb.ddd + aaa.bbb.ddd + aaa.bbb.ccc + aaa.bbb.eee +\end{verbatim} + +\subsection{Message Logging} +\hlabel{psLogMsg} + +\begin{table} + \begin{verbatim} +enum { PS_LOG_ABORT = 0, PS_LOG_ERROR, PS_LOG_WARN, PS_LOG_INFO }; + +enum { PS_LOG_TO_STDERR, PS_LOG_TO_STDOUT }; + +void psLogMsg(const char *name, int level, const char *fmt, ...); +void p_psVLogMsg(const char *name, int level, const char *fmt, va_list ap); + +int psSetLogDestination(int dest); +int psSetLogLevel(int level); + \end{verbatim} + \begin{caption}{API for message logging} + \hlabel{tabLogMsgAPI} + The API for message logging. + \end{caption} +\end{table} + +The public API for the logging facility (table \ref{tabLogMsgAPI}) +should be provided in a header file \file{psLogMsg.h} which +is included by \file{psUtils.h}. + +The function \code{psSetLogLevel} may be used to set the current +level of logging; the previous value is returned. +The default value is \code{PS_LOG_INFO}. Valid values are 0---9 +inclusive (note that only the first four are required to have +symbolic names). + +A call to \code{psLogMsg(name, level, msg, ...)} shall generate +a log message if \code{level} is less than or equal to the +value most recently set using \code{psSetLogLevel}. The function +\code{p_psLogMsg} is identical, except that it expects a +final \code{va_list} argument. + +The format of the log message shall be of the form: +\begin{verbatim} +YYYY:MM:DD hh:mm:ssZ|hostname|l|name |msg +\end{verbatim} +\code{YYYY}, \code{MM}, \code{DD}, \code{hh}, \code{mm}, and \code{ss} +are the year, month (Jan == 1), day of the month, hours (0--23), +minutes, and seconds when the log message was received. Note that the +timestamp is in ISO order, and that the timezone is GMT (hence the +\code{Z}). + +The \code{hostname} is returned by \code{gethostname}, \code{l} is a +letter associated with the level (\code{A}, \code{E}, \code{W}, and +\code{I} for \code{PS_LOG_ABORT}, \code{PS_LOG_ERROR}, \code{PS_LOG_WARN}, +and \code{PS_LOG_INFO} respectively. Other levels are represented +numerically (\code{5} etc.). The other two field, \code{name} and +\code{msg} are arguments to \code{psLogMsg}; note that \code{name} has +a fixed width of 15 characters. If \code{msg} doesn't end in a newline, +a single newline is emitted to terminate the message. + +An example message is: +\begin{verbatim} +2004:02:24 20:14:18Z|alibaba.IfA.Hawaii.Edu|I|utils |Hello World +\end{verbatim} + +Log messages are sent to the destination most recently set using +\code{psSetLogDestination}. The only two values that are initially +defined are \code{PS_LOG_TO_STDERR} and \code{PS_LOG_TO_STDOUT} to +write to \code{stderr} and \code{stdout} respectively. + +\section{The Pan-STARRS \code{psDlist} doubly-linked list type} +\hlabel{psDlist} + +Pan-STARRS supports doubly linked lists through a type \code{psDlist}. +The type is defined in the header file \file{psDlist.h}, and consists +of the following definitions: + +\begin{verbatim} +typedef struct psDlistElem { + struct psDlistElem *prev; // previous link in list + struct psDlistElem *next; // next link in list + void *data; // real data item +} psDlistElem; + +typedef struct { + int n; // number of elements on list + psDlistElem *head; // first element on list (may be NULL) + psDlistElem *tail; // last element on list (may be NULL) + psDlistElem *iter; // iteration cursor; private +} psDlist; + +enum { // Special values of index into list + psDlistHead = 0, // at head + psDlistTail = -1, // at tail + psDlistUnknown = -2, // unknown position + psDlistPrev = -3, // previous element + psDlistNext = -4 // next element +}; +\end{verbatim} + +The API is: + +\begin{verbatim} +psDlist *psDlistNew(void *data); // initial data item; may be NULL + +void psDlistDel(psDlist *list, // list to destroy + void (*elemDel)(void *)); // destructor for list data, or NULL + +/* + * List maintainence functions + */ +psDlist *psDlistAdd(psDlist *list, // list to add to (may be NULL) + void *data, // data item to add + int where); // index, psDlistHead, or psDlistTail +psDlist *psDlistAppend(psDlist *list, // list to append to (may be NULL) + void *data); // data item to add +void *psDlistRemove(psDlist *list, // list to remove element from + void *data, // data item to remove + int which); // index of item, or psDlistUnknown, + // or psDlistNext, or psDlistPrev +void *psDlistGet(const psDlist *list, // list to retrieve element from + int which); // index of item, or psDlistNext, + // or psDlistPrev +/* + * Conversions to/from arrays + */ +psVoidPtrArray *psDlistToArray(psDlist *dlist); +psDlist *psArrayToDlist(psVoidPtrArray *arr); +\end{verbatim} + +All data items placed onto lists (e.g. with \code{psDlistAdd}) +shall have their reference counters (section \ref{secMemRefcntr}) incremented. +When elements +are removed from a list with \code{psDlistRemove}, they shall +have their reference counters decremented. The action of retrieving +data from a list (with \code{psDlistGet}) shall not affect +their reference counter. + +If \code{psDlistDel}'s argument \code{elemDel} is NULL, the +list should be deleted, but not the elements on it (although their +\code{refcntr}'s should be decremented). + +The \code{psDlistGet} routine may be used to provide an iterator. The +call \code{psDlistGet(list, psDlistHead)} returns the data from the +head link of the list, but also sets the iteration cursor to the head. +A seried of calls to \code{psDlistGet(list, psDlistNext)} return the +elements of the list in order (you may also use \code{psDlistTail} and +\code{psDlistPrev} to traverse the list backwards). + +Explicit traversal of the list using the \code{psDlistElem}'s +\code{prev} and \code{next} pointers is also supported. + +The routines to convert to and from \code{psVoidPtrArray}s, +\code{psDlistToArray} and \code{psArrayToDlist} shall ensure that the +objects on the arrays and lists have had their reference pointers +correctly incremented (see section \ref{secArrayVoidPtr}) (\eg{} that +\code{psArrayToDlist(psDlistToArray(list))} returns a properly-formed +\code{psDlist}). + +\section{The \PS{} Array types} + +\begin{table} + \begin{verbatim} + \end{verbatim} + \begin{caption}{The array creation macros defined in \file{psArray.h}} + \hlabel{tabPsArray} + \end{caption} +\end{table} + +\subsection{Arrays of Simple Types} + +Any \PS/ datatype \code{psType} may be associated with an array type +\code{psTypeArray}: +\begin{verbatim} +typedef struct { + int size; + int n; + psType *arr; +} psTypeArray; +\end{verbatim} +with associated constructors and a destructor: +\begin{verbatim} +psTypeArray *psTypeNew(int n, int size); +psTypeArray *psTypeRealloc(psTypeArray *arr, int n); +void psTypeDel(psTypeArray *arr); +\end{verbatim} + +The argument \code{n} is the dimension of the array; \code{size} +is the number of elements allocated ($s \ge n$). + +This type and functions may be declared and defined using two macros +from \file{psArray.h} (table \ref{tabPsArray}), +\code{PS_DECLARE_ARRAY_TYPE(psType)} and +\code{PS_CREATE_ARRAY_TYPE(psType)}. The former defines the typedef +and declares the prototypes (and is thus suitable for use in a +header file); the latter generates the code for the three functions +\code{psType(New|Realloc|Del} (and should thus appear in exactly one +source file for a given type). + +The \code{psType} should be a single word (e.g. \code{psXY}); in particular, +there is no requirement to support a pointer type (\eg{} \code{psXY *}); +see next section. + +\subsection{Arrays of Pointer Types} + +The data type created with \code{PS_CREATE_ARRAY_TYPE} (\code{psType}) +contains an array of \code{psType}s not +pointers to \code{psType}s; this means that the individual elements are +not allocated using \code{psTypeNew}, are not correctly initialized, +and shouldn't be individually deleted with \code{psTypeDel}; + +If you wish to use arrays of pointers, use the macros +\code{PS_DECLARE_ARRAY_PTR_TYPE(psType)} and +\code{PS_CREATE_ARRAY_PTR_TYPE(psType)} (table \ref{tabPsArray}). These +create types \code{typedef psType *psTypePtr} and \code{psTypePtrArray}: +\begin{verbatim} +typedef struct { + int size; + int n; + psTypePtr *arr; +} psTypePtrArray; +\end{verbatim} +with associated constructors and a destructor: +\begin{verbatim} +psTypePtrArray *psTypePtrNew(int n, int size); +psTypePtrArray *psTypePtrRealloc(psTypePtrArray *arr, int n); +void psTypePtrArrayDel(psTypePtrArray *arr); +\end{verbatim} + +These constructors create arrays of \code{psType *} and call +\code{psTypeNew} and \code{psTypeDel} to allocate and free the +elements. As for the simple arrays, The former defines the typedef and +declares the prototypes (and is thus suitable for use in a header +file) and the latter generates the code for the three functions +\code{psType(New|Realloc|Del} (and should thus appear in exactly one +source file for a given type). + +The objects pointed to by these types have had their \code{refCntr}s +incremented (see \ref{secMemRefcntr}); to remove an element from the array you +need to say something like: +\begin{verbatim} + psTypePtrArray *pt = psTypePtrArrayNew(10, 10); + psType *xy = psMemDecrRefCntr(pt->arr[0]); + pt->arr[0] = NULL; +\end{verbatim} + +\subsubsection{Arrays of \code{void *}} +\hlabel{secArrayVoidPtr} + +Arrays of \code{void *} are different, as the need an explicitly-specified +destructor. + +\file{psArray.h} shall specify a type \code{psVoidPtrArray} that +behaves in all respects as if it had been created with: +\begin{verbatim} +typedef void *psVoidPtr; +PS_DECLARE_ARRAY_TYPE(psVoidPtr); +PS_CREATE_ARRAY_TYPE(psVoidPtr); +\end{verbatim} +except that its destructor is specified as: +\begin{verbatim} +void psVoidPtrArrayDel(psVoidPtrArray *arr, // array to destroy + void (*elemDel)(void *)); // destructor for array data +\end{verbatim} + +The routine \code{psVoidPtrArrayDel} assumes that all pointers +had their reference counters incremented +when they were inserted onto the array.\footnote{% + \eg{} \code{va->arr[i] = psMemIncrRefCntr(ptr);}} + +If \code{psVoidPtrArrayDel}'s argument \code{elemDel} is NULL, the +list should be deleted, but not the elements on it (although their +\code{refcntr}'s should be decremented). + +\subsection{Examples of Array Types} + +The following is a complete C program that illustrates the use of +\code{array}s. +\begin{verbatim} +#include "psUtils.h" + +typedef struct { + int x, y; +} psXY; + +psXY *psXYNew(void) +{ + return psAlloc(sizeof(psXY)); +} + +void psXYDel(psXY *xy) +{ + psFree(xy); +} + +PS_DECLARE_ARRAY_TYPE(psXY); +PS_CREATE_ARRAY_TYPE(psXY); + +PS_DECLARE_ARRAY_PTR_TYPE(psXY); +PS_CREATE_ARRAY_PTR_TYPE(psXY); + +int main(void) +{ + psXYArray *t = psXYArrayNew(10, 15); + psXYPtrArray *pt = psXYPtrArrayNew(10, 10); + + for (int i = 0; i < t->n; i++) { + t->arr[i].x = i; + pt->arr[i]->y = 10*i; + } + + t = psXYArrayRealloc(t, 5); + t = psXYArrayRealloc(t, 8); + + for (int i = 0; i < t->n; i++) { + printf("%d %d ", t->arr[i].x, pt->arr[i]->y); + } + printf("\n"); + + psXYArrayDel(t); + + psXY *xy = psMemDecrRefCntr(pt->arr[0]); + pt->arr[0] = NULL; + psXYDel(xy); + + psXYPtrArrayDel(pt); + + psMemCheckLeaks(0, NULL, stderr); + + return 0; +} +\end{verbatim} + +\section{Hash Tables} +\hlabel{psHash} + +\begin{table} + \begin{verbatim} +typedef struct HashTable psHash; + +psHash *psHashNew(int nbucket); // initial number of buckets +void psHashDel(psHash *table, // hash table to be freed + void (*itemDel)(void *item)); // how to free hashed data; + // or NULL + +void *psHashInsert(psHash *table, // table to insert in + const char *key, // key to use + void *data, // data to insert + void (*itemDel)(void *item)); // how to free hashed data; + // or NULL +void *psHashLookup(psHash *table, // table to lookup key in + const char *key); // key to lookup + \end{verbatim} + \begin{caption}{The public API for hash tables from \file{psHash.h}} + \hlabel{tabPsHash} + \end{caption} +\end{table} + +The public API for the hash table (table \ref{tabPsHash}) +should be provided in a header file \file{psHash.h} which +is included by \file{psUtils.h}. +\footnote{ + We choose not to use the posix function \texttt{hcreate}, + \texttt{hdestroy}, and \code{hsearch} as they only support + a single hash table at any one time.} + +A hash table is an abstract type \texttt{psHash}. The argument +\texttt{nbucket} to \texttt{psHashNew} is a non-binding suggestion +from the user for the initial size of the hash table. + +If the \texttt{itemDel} argument to \texttt{psHashDel} is non-NULL, +it will be used to delete the data items that have been stored +in the hash table; if it is NULL this is the responsibility of +the caller. + +The routine \texttt{psHashInsert} must provide a non-NULL \texttt{itemDel} +argument if it wishes to change the value previously inserted keys; +if \texttt{itemDel} is NULL attempting to insert a pre-existing key +is an error, and the routine will return NULL. If \texttt{psHashInsert} +succeeds it returns \texttt{data}. + +\texttt{psHashLookup} returns the \texttt{data} associated with the +key, or NULL if the key's invalid. + +\section{Miscellaneous Utilities} + +The API for miscellaneous \PS{} utilities is provided by \file{psMisc.h} +which shall be included by \file{psUtils.h}. + +\begin{table} + \begin{verbatim} +#define PS_CONCAT(A, B) A ## B // Expands to AB +#define PS_CONCAT2(A, B) PS_CONCAT(A, B) // Also expands to AB +#define PS_CONCAT3(A, B, C) A ## B ## C // Expands to ABC + +#define PS_STRING(S) #S // converts argument S to string + +void psAbort(const char *name, const char *fmt, ...); +void psError(const char *name, const char *fmt, ...); +char *psStringCopy(const char *str); + \end{verbatim} + \begin{caption}{The utilities provided by \file{psMisc.h}} + \hlabel{psMisc} + \end{caption} +\end{table} + +\code{psAbort} shall call \code{psMsgLog} with a level of \code{PS_LOG_ABORT}, +and then call \code{abort}. +\code{psError} shall call \code{psMsgLog} with a level of \code{PS_LOG_ERROR}, +and then return. +In cases of doubt, a good choice for +\code{name} is \code{__func__}. + +\code{psStringCopy} shall allocate and return a copy of the input string. + + +\bibliographystyle{plain} +\bibliography{panstarrs} + + + +\end{document}