Changeset 337

Timestamp:

Mar 31, 2004, 4:34:37 PM (22 years ago)

Author:

eugene

Message:

substantial additions to the text of psDlist and psHash.

File:

• trunk/doc/pslib/psLibSDRS.tex (modified) (3 diffs)

trunk/doc/pslib/psLibSDRS.tex

@@ -1 @@
-%%% $Id: psLibSDRS.tex,v 1.15 2004-03-31 21:27:48 eugene Exp $
+%%% $Id: psLibSDRS.tex,v 1.16 2004-04-01 02:34:37 eugene Exp $
 \documentclass[panstarrs]{panstarrs}
 %\documentclass[panstarrs]{panstarrs}
@@ -788 +788 @@
 \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 several
+data structures which correspond to one-dimensional arrays (vectors)
+of different data types (\code{int}, \code{float}, etc).  We also have
+different data structures which correspond 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 probably be invalid.
+
+Given that some functions should be able to operate equivalently (or
+identically) on a wide range of data types, it seems cumbersome to be
+forced into defining a large number of C functions to handle the
+different data types, just because we have different structures.
+Admittedly, some details of the function would have to vary for
+different data types, but since the basic function is the same, it
+would help both the user and programmer if the same function could be
+used for different data types.  We therefore 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.  The mechanism uses the
+structure \code{psType}.
+
+Each of these equivalent data type is defined by a structure in which
+the first element is always of type \code{psType}.  This element
+defines both the dimensions of the array and the data type of each
+element.  The structure is as follows:
+\begin{verbatim}
+typedef struct {
+    psDimen dimen;                      ///< The dimensionality
+    psElemType type;                    ///< The type
+} psType;
+\begin{end}
+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 structures:
+\begin{verbatim}
+typedef enum {
+    PS_DIMEN_SCALAR,                    ///< Scalar
+    PS_DIMEN_VECTOR,                    ///< A vector
+    PS_DIMEN_TRANSV,                    ///< A transposed vector
+    PS_DIMEN_MATRIX,                    ///< A matrix
+    PS_DIMEN_OTHER                      ///< Something else that's not supported for arithmetic
+} psDimen;
+\end{verbatim}
+and
+\begin{verbatim}
+typedef enum {
+    PS_TYPE_CHAR,                       ///< Character
+    PS_TYPE_SHORT,                      ///< Short integer
+    PS_TYPE_INT,                        ///< Integer
+    PS_TYPE_LONG,                       ///< Long integer
+    PS_TYPE_UCHAR,                      ///< Unsigned character
+    PS_TYPE_USHORT,                     ///< Unsigned short integer
+    PS_TYPE_UINT,                       ///< Unsigned integer
+    PS_TYPE_ULONG,                      ///< Unsigned long integer
+    PS_TYPE_FLOAT,                      ///< Floating point
+    PS_TYPE_DOUBLE,                     ///< Double-precision floating point
+    PS_TYPE_COMPLEX,                    ///< Complex numbers consisting of floating point
+    PS_TYPE_OTHER,                      ///< Something else that's not supported for arithmetic
+} psElemType;
+\end{verbatim}
+We discuss the application of \code{psType} in more detail in
+section~\ref{math}.  
+
 \subsection{Simple Array types}
 
+\begin{verbatim}
+psIntArray
+psFloatArray
+psDoubleArray
+psComplexArray
+psVoidPtrArray
+\end{verbatim}
+
 \subsubsection{Arrays of Simple Types}
 
-Any \PS{} datatype \code{psType} may be associated with an array type
-\code{psTypeArray}:
+We require several types of basic one-dimensional arrays: arrays of
+values of type \code{int}, \code{float}, \code{double},
+\code{complex}, and \code{void *}.  We have defined structures for
+these types which are all equivalent.  We illustrate them with the
+example of \code{psFloatArray}:
+%
 \begin{verbatim}
 typedef struct {
-  int size;
-  int n;
-  psType *arr;
-} psTypeArray;
-\end{verbatim}
-with associated constructors and a destructor:
-\begin{verbatim}
-psTypeArray *psTypeAlloc(int n, int size);
-psTypeArray *psTypeRealloc(psTypeArray *arr, int n);
-void psTypeFree(psTypeArray *arr);  
-\end{verbatim}
-
-The argument \code{n} is the dimension of the array; \code{size}
-is the number of elements allocated ($s \ge n$).
-
-This type and functions may be declared and defined using two macros,
-\code{PS_DECLARE_ARRAY_TYPE(psType)} and
-\code{PS_CREATE_ARRAY_TYPE(psType)}.  The former defines the
-\code{typedef} and declares the prototypes (and is thus suitable for
-use in a header file); the latter generates the code for the three
-functions \code{psType(Alloc|Realloc|Free)} (and should thus appear in
-exactly one source file for a given type).
-
-The \code{psType} should be a single word (e.g. \code{psXY}); in particular,
-there is no requirement to support a pointer type (\eg{} \code{psXY *});
-see next section.
+    psType type;                        ///< Type of data.  Must be first element
+    int nalloc;                         ///< Total number of elements available
+    int n;                              ///< Number of elements in use
+    float *arr;                         ///< The array data
+} psFloatArray;
+\end{verbatim}
+%
+In this structure, the argument \code{n} is the length of the array
+(the number of elements); \code{size} is the number of elements
+allocated ($s \ge n$).  The allocated memory is available at
+\code{arr}.  The data type is defined by the first element,
+\code{psType}.  The structure is associated with a constructor and a destructor:
+%
+\begin{verbatim}
+psFloatArray *psFloatArrayAlloc(int nalloc);
+psFloatArray *psFloatArrayRealloc(psFloatArray *myArray, int nalloc);
+void psFloatArrayFree(psFloatArray *restrict myArray);
+\end{verbatim}
+%
+In these functions, \code{nalloc} is the number of elements to
+allocate.  For \code{psFloatArrayAlloc}, the value of
+\code{psFloatArray.n} is set to 0 and the allocated arrays are
+initialized to 0.0.  For \code{psFloatArrayRealloc}, if the value of
+\code{nalloc} is smaller than the current value of
+\code{psFloatArray.n}, then \code{psFloatArray.n} is set to
+\code{nalloc}, the array is adjusted down to match \code{nalloc}, and
+the extra elements are lost.  If \code{nalloc} is larger than the
+current value of \code{psFloatArray.n}, \code{psFloatArray.n} is left
+intact.  If the value of \code{myArray} is \code{NULL}, then
+\code{psFloatArrayRealloc} behaves like \code{psFloatArrayAlloc}.
+
+Basic one-dimensional arrays of all of the types listed above have
+equivalent structures, constructors, and destructors to those for
+\code{psFloatArray}, with the words \code{float} converted to the
+appropriate type.  Thus we have:
+\begin{verbatim}
+psIntArray *psIntArrayAlloc(int nalloc);
+psFloatArray *psFloatArrayAlloc(int nalloc);
+psDoubleArray *psDoubleArrayAlloc(int nalloc);
+psComplexArray *psComplexArrayAlloc(int nalloc);
+\end{verbatim}
+and so on for the other functions.  The collection of structures and
+functions may be easily generated with C pre-processor macros.
 
 \subsubsection{Arrays of Pointer Types}
 
-The data type created with \code{PS_CREATE_ARRAY_TYPE} (\code{psType})
-contains an array of \code{psType}s not
-pointers to \code{psType}s; this means that the individual elements are
-not allocated using \code{psTypeAlloc}, are not correctly initialized,
-and shouldn't be individually deleted with \code{psTypeFree};
-
-If you wish to use arrays of pointers, use the macros
-\code{PS_DECLARE_ARRAY_PTR_TYPE(psType)} and
-\code{PS_CREATE_ARRAY_PTR_TYPE(psType)}. These
-create types \code{typedef psType *psTypePtr} and \code{psTypePtrArray}:
+Arrays of pointer types need some additional specification.  We
+require an array of pointers of type \code{void}, with which we can
+carry around a collection of data of an arbitrary type which is more
+complicated than the simple numeric types above.  The structure is a follows:
+%
 \begin{verbatim}
 typedef struct {
-  int size;
-  int n;
-  psTypePtr *arr;
-} psTypePtrArray;
-\end{verbatim}
-with associated constructors and a destructor:
-\begin{verbatim}
-psTypePtrArray *psTypePtrAlloc(int n, int size);
-psTypePtrArray *psTypePtrRealloc(psTypePtrArray *arr, int n);
-void psTypePtrArrayFree(psTypePtrArray *arr);  
-\end{verbatim}
-
-These constructors create arrays of \code{psType *} and call
-\code{psTypeAlloc} and \code{psTypeFree} to allocate and free the
-elements. As for the simple arrays, The former defines the typedef and
-declares the prototypes (and is thus suitable for use in a header
-file) and the latter generates the code for the three functions
-\code{psType(Alloc|Realloc|Free)} (and should thus appear in exactly one
-source file for a given type).
-
-The objects pointed to by these types have had their \code{refCounter}s
-incremented (see \ref{secMemRefcounter}); to remove an element from the array you
-need to say something like:
-\begin{verbatim}
-  psTypePtrArray *pt = psTypePtrArrayAlloc(10, 10);
-  psType *xy = psMemDecrRefCounter(pt->arr[0]);
-  pt->arr[0] = NULL;
-\end{verbatim}
-
-\subsubsection{Arrays of \texttt{void *}}
-\hlabel{secArrayVoidPtr}
-
-Arrays of \code{void *} are different, as they need an explicitly-specified
-destructor.
-
-We require a type \code{psVoidPtrArray} that behaves in all respects
-as if it had been created with:
-\begin{verbatim}
-typedef void *psVoidPtr;
-PS_DECLARE_ARRAY_TYPE(psVoidPtr);
-PS_CREATE_ARRAY_TYPE(psVoidPtr);
-\end{verbatim}
-except that its destructor is specified as:
-\begin{verbatim}
-void psVoidPtrArrayFree(psVoidPtrArray *arr,      // array to destroy
-                       void (*elemFree)(void *)); // destructor for array data
-\end{verbatim}
-
-The routine \code{psVoidPtrArrayFree} assumes that all pointers
-had their reference counters incremented
-when they were inserted onto the array.\footnote{%
-  \eg{} \code{va->arr[i] = psMemIncrRefCounter(ptr);}}
-
+    psType type;                        ///< Type of data.  Must be first element
+    int nalloc;                         ///< Total number of elements available
+    int n;                              ///< Number of elements in use
+    void **arr;                         ///< The array data
+} psVoidPtrArray;
+\end{verbatim}
+%
+There is also an equivalent set of constructors and destructor:
+%
+\begin{verbatim}
+psVoidPtrArray *psVoidPtrArrayAlloc(int nalloc);
+psVoidPtrArray *psVoidPtrArrayRealloc(psVoidPtrArray *myArray, int nalloc);
+void psVoidPtrArrayFree(psVoidPtrArray *restrict myArray, void (*elemFree)(void *));
+\end{verbatim}
+%
+The only difference with the numeric array types is the addition of a
+destructor function which is passed to \code{psVoidPrtArrayFree}.
+This function, which may be \code{NULL}, is called for each existing
+element of the array before the array itself is freed.  If the
+function is \code{NULL}, the elements are are not freed.
+
+The routine \code{psVoidPtrArrayFree} assumes that all pointers had
+their reference counters incremented when they were inserted onto the
+array.\footnote{\eg{} \code{va->arr[i] = psMemIncrRefCounter(ptr);}}
 If \code{psVoidPtrArrayFree}'s argument \code{elemFree} is NULL, the
 list should be deleted, but not the elements on it (although their
 \code{refcounter}'s should be decremented).
 
-\subsubsection{Examples of Array Types}
-
-The following is a complete C program that illustrates the use of
-\code{array}s.
-\begin{verbatim}
-#include "psLib.h"
-
-typedef struct {
-    int x, y;
-} psXY;
-
-psXY *psXYAlloc(void)
-{
-    return psAlloc(sizeof(psXY));
-}
-
-void psXYFree(psXY *xy)
-{
-    psFree(xy);
-}
-
-PS_DECLARE_ARRAY_TYPE(psXY);
-PS_CREATE_ARRAY_TYPE(psXY);
-
-PS_DECLARE_ARRAY_PTR_TYPE(psXY);
-PS_CREATE_ARRAY_PTR_TYPE(psXY);
-
-int main(void)
-{
-    psXYArray *t = psXYArrayAlloc(10, 15);
-    psXYPtrArray *pt = psXYPtrArrayAlloc(10, 10);
-
-    for (int i = 0; i < t->n; i++) {
-        t->arr[i].x = i;
-        pt->arr[i]->y = 10*i;
-    }
-
-    t = psXYArrayRealloc(t, 5);
-    t = psXYArrayRealloc(t, 8);
-
-    for (int i = 0; i < t->n; i++) {
-        printf("%d %d  ", t->arr[i].x, pt->arr[i]->y);
-    }
-    printf("\n");
-    
-    psXYArrayFree(t);
-
-    psXY *xy = psMemDecrRefCounter(pt->arr[0]);
-    pt->arr[0] = NULL;
-    psXYFree(xy);    
-    
-    psXYPtrArrayFree(pt);
-
-    psMemCheckLeaks(0, NULL, stderr);
-
-    return 0;
-}
-\end{verbatim}
-
 \subsection{Doubly-linked lists}
 \hlabel{psDlist}
 
-\PS{} supports doubly linked lists through a type \code{psDlist}.  The
-type consists of the following definitions:
-
-\begin{verbatim}
-/** Doubly-linked list element */
-typedef struct psDlistElem {
-   struct psDlistElem *prev;            ///< previous link in list
-   struct psDlistElem *next;            ///< next link in list
-   void *data;                          ///< real data item
-} psDlistElem;
-
-/** Doubly-linked list */
+\PS{} supports doubly linked lists through a type \code{psDlist}:
+%
+\begin{verbatim}
 typedef struct {
    int n;                               ///< number of elements on list
@@ -974 +983 @@
    psDlistElem *iter;                   ///< iteration cursor
 } psDlist;
-
-/** Special values of index into list */
-enum {
-   PS_DLIST_HEAD = 0,                   ///< at head
-   PS_DLIST_TAIL = -1,                  ///< at tail
-   PS_DLIST_UNKNOWN = -2,               ///< unknown position
-   PS_DLIST_PREV = -3,                  ///< previous element
-   PS_DLIST_NEXT = -4                   ///< next element
-};
-\end{verbatim}
-
-The API is:
-
-\begin{verbatim}
-/** Constructor */
-psDlist *psDlistAlloc(void *data        ///< initial data item; may be NULL
-                      );
-
-/** Destructor */
-void psDlistFree(psDlist *list,         ///< list to destroy
-                void (*elemFree)(void *) ///< destructor for data on list
-                 );
-
-/**** List maintainence functions ****/
-
-/** Add to list */
-psDlist *psDlistAdd(psDlist *list,      ///< list to add to (may be NULL)
-                    void *data,         ///< data item to add
-                    int where           ///< index, PS_DLIST_HEAD, or PS_DLIST_TAIL
-                    );
-
-/** Append to a list */
-psDlist *psDlistAppend(psDlist *list,   ///< list to append to (may be NULL)
-                       void *data       ///< data item to add
-                       );
-
-/** Remove from a list */
-void *psDlistRemove(psDlist *list,      ///< list to remove element from
-                    void *data,         ///< data item to remove
-                    int which           ///< index of item, or PS_DLIST_UNKNOWN, or PS_DLIST_NEXT, or
-                                        ///< PS_DLIST_PREV
-                    );
-/** Retrieve from a list */
-void *psDlistGet(const psDlist *list,   ///< list to retrieve element from
-                 int which              ///< index of item, or PS_DLIST_NEXT, or PS_DLIST_PREV
-                 );
-
-/** Convert doubly-linked list to an array */
-psVoidPtrArray *psDlistToArray(psDlist *dlist ///< List to convert
-                               );
-
-/** Convert array to a doubly-linked list */
-psDlist *psArrayToDlist(psVoidPtrArray *arr ///< Array to convert
-                        );
-\end{verbatim}
-
-All data items placed onto lists (e.g. with \code{psDlistAdd}) shall
-have their reference counters (section \ref{secMemRefcounter})
-incremented.  When elements are removed from a list with
-\code{psDlistRemove}, they shall have their reference counters
-decremented. The action of retrieving data from a list (with
-\code{psDlistGet}) shall not affect their reference counter.
-
-If \code{psDlistFree}'s argument \code{elemFree} is NULL, the
-list should be deleted, but not the elements on it (although their
-\code{refcounter}s should be decremented).
-
-Iteration over all elements of the list is provided by the functions:
-\begin{verbatim}
-/** Set the iterator */
-void psDlistSetIterator(psDlist *list,  ///< list to retrieve element from
-                        int where,      ///< index, PS_DLIST_HEAD, or PS_DLIST_TAIL
-                        int which       ///< index of item, or PS_DLIST_UNKNOWN, or PS_DLIST_NEXT, or
-                                        ///< PS_DLIST_PREV
-                        );
-
-/** Get next element */
-void *psDlistGetNext(psDlist *list,     ///< list to retrieve element from
-                     int which          ///< index of item, or PS_DLIST_UNKNOWN, or PS_DLIST_NEXT, or
-                                        ///< PS_DLIST_PREV
-                     );
-
-/** Get previous element */
-void *psDlistGetPrev(psDlist *list,     ///< list to retrieve element from
-                     int which          ///< index of item, or PS_DLIST_UNKNOWN, or PS_DLIST_NEXT, or
-                                        ///< PS_DLIST_PREV
-                     );
-\end{verbatim}
-in which the \code{where} argument must be \code{PS_DLIST_HEAD} or \code{PS_DLIST_TAIL},
-to start at the head or tail of the list, and \code{psDlistGetNext} and \code{psDlistGetPrev}
-return the next/previous element. The argument \code{which} identifies which of potentially
-many iteration cursors should be used; it must currently always be \code{0}.
-
-Explicit traversal of the list using the \code{psDlistElem}s
-\code{prev} and \code{next} pointers is also supported.
-
-The routines to convert to and from \code{psVoidPtrArray}s,
-\code{psDlistToArray} and \code{psArrayToDlist} shall ensure that the
-objects on the arrays and lists have had their reference pointers
-correctly incremented (see section \ref{secArrayVoidPtr}) (\eg{} that
-\code{psArrayToDlist(psDlistToArray(list))} returns a properly-formed
-\code{psDlist}).
-
-\subsubsubsection{Rationale}
-
-\tbd{defer this example to the psDlist section?}
-
-The \code{psMemBlock.refcounter} is clearly useful for detecting
-attempts to free memory that is already free.  A more complex
-application is for allowing pointers to complex data-objects (e.g.\
-images) to appear in more than one data structure simultaneously:
-
-\begin{verbatim}
-typedef struct {
-    char *name;
-    int value;
-} psSimple;
-
-psSimple *psSimpleAlloc(const char *name, int val)
-{
-    psSimple *simp = psAlloc(sizeof(psSimple));
-    simp->name = strcpy(psAlloc(strlen(name) + 1), name);
-    simp->value = val;
-
-    return simp;
-}
-
-void psSimpleFree(psSimple *simp)
-{
-    if (simp == NULL) { return; }
-
-    if (psMemGetRefCounter(simp) > 1) {
-        (void)psMemDecrRefCounter(simp);
-        return;
-    }
-}
-\end{verbatim}
-
-Because of the use of the \code{refcounter} field, we can safely put items of
-this type onto many lists:
-\goodbreak
-\begin{verbatim}
-simp = psSimpleAlloc("RHL", 0);
-psDlistAppend(list1, psMemIncrRefCounter(simp));
-psDlistAppend(list2, psMemIncrRefCounter(simp));
-psSimpleFree(simp);
-\end{verbatim}
-
-(Note: in fact there is no need to explicitly increment the counter
-in this case, as the \code{psDlistAppend} (section \ref{psDlist})
-API specifies that it
-does it for you.)
+\end{verbatim}
+%
+The type \code{psDlist} 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}), \tbd{an entry
+for the current cursor location (\code{iter})}, 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{psDlistElem}:
+%
+\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;
+\end{verbatim}
+%
+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.  
+
+A list may be created with the function
+\begin{verbatim}
+psDlist *psDlistAlloc(void *data);
+\end{verbatim}
+which may take a pointer to a data item, or it may take \code{NULL}.
+The allocator creates both the \code{psDlist} and the first element in
+the list, pointed to by both \code{psDlist.head} and
+\code{psDlist.tail}.  If the data entry is \code{NULL}, then an empty
+list, with both pointers set to \code{NULL} should be created.  
+
+An entry may be added to the list with the function:
+\begin{verbatim}
+psDlist *psDlistAdd(psDlist *list, void *data, int where);
+\end{verbatim}
+which takes a pointer to the list and also returns a pointer to the
+list.  The returned pointer must be used as the value of
+\code{psDlist} may have changed.  The value of \code{where} specifies
+if the specified data item should be placed on the front of the list
+(\code{PS_DLIST_HEAD}), at the end of the list (\code{PS_DLIST_TAIL}), 
+\tbd{use of other options?}.  
+
+A data item may be retrieved from the list with the function:
+\begin{verbatim}
+void *psDlistGet(psDlist *list, int which);
+\end{verbatim}
+The value of \code{which} may be the numerical index or it may be one
+of the special values: \code{PS_DLIST_HEAD}, \code{PS_DLIST_TAIL},
+\code{PS_DLIST_PREV}, and \code{PS_DLIST_NEXT}, all of which are
+defined as negative integers.
+
+A data item may be removed from the list with the function:
+\begin{verbatim}
+void *psDlistRemove(psDlist *list, void *data, int which);
+\end{verbatim}
+The value of \code{which} may be the numerical index or it may be one
+of the special values: \code{PS_DLIST_HEAD}, \code{PS_DLIST_TAIL},
+\code{PS_DLIST_PREV}, \code{PS_DLIST_UNKNOWN}, and
+\code{PS_DLIST_NEXT}, all of which are defined as negative integers.
+If the value of \code{which} is \code{PS_DLIST_UNKNOWN}, then the data
+item is identified by matching the pointer value with \code{void
+*data}.
+
+All data items placed onto lists (\code{psDlistAdd}) shall have their
+reference counters (section \ref{secMemRefcounter}) incremented.  When
+elements are removed from a list with \code{psDlistRemove}, they shall
+have their reference counters decremented. The action of retrieving
+data from a list (with \code{psDlistGet}) shall not affect their
+reference counter.
+
+A complete list may be freed with the destructor:
+\begin{verbatim}
+void psDlistFree(psDlist *list, void (*elemFree)(void *));
+\end{verbatim}
+If the element destructor (\code{elemFree}) is \code{NULL}, the list
+should be deleted, but not the elements, although their
+\code{refcounter}s should be decremented.
+
+Two functions are available to convert between the \code{psDlist} and
+\code{psVoidPtrArray} containers:
+\begin{verbatim}
+psVoidPtrArray *psDlistToArray(psDlist *dlist);
+psDlist *psArrayToDlist(psVoidPtrArray *arr);
+\end{verbatim}
+These functions do not free the elements or destroy the input
+collection.  Rather, they increment the reference counter for each of
+the elements. 
+
+Iteration over all elements of the list using the iteration cursor
+\code{iter} is provided by the functions:
+\begin{verbatim}
+void psDlistSetIterator(psDlist *list, int where);
+void *psDlistGetNext(psDlist *list);
+void *psDlistGetPrev(psDlist *list);
+\end{verbatim}
+The first of these functions uses the value of \code{where} to set the
+iteration cursor for the given list to the beginning
+\code{PS_DLIST_HEAD} or the end \code{PS_DLIST_TAIL}.  The next two
+functions move the iteration cursor forward or backwards, returning
+the data item from the resulting list entry, or returning \code{NULL}
+at the end of the list.  Explicit traversal of the list using the
+\code{psDlistElem}s \code{prev} and \code{next} pointers is also
+supported.
 
 \subsection{Hash Tables}
 \hlabel{psHash}
 
-The public APIs for the hash table (table \ref{tabPsHash}) are shown below.
-\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{verbatim}
-typedef struct HashTable psHash;        ///< Opaque type for a hash table
-
-/// Allocate hash buckets in table.
-psHash *psHashAlloc(int nbucket         ///< initial number of buckets
-    );
-
-/// Free hash buckets from table.
-void psHashFree(psHash *table,          ///< hash table to be freed
-                void (*itemFree)(void *item) ///< how to free hashed data; or NULL
-    );
-
-/// Insert entry into table.
-void *psHashInsert(psHash *table,       ///< table to insert in
-                   const char *key,     ///< key to use
-                   void *data,          ///< data to insert
-                   void (*itemFree)(void *item) ///< how to free hashed data; or NULL
-    );
-
-/// Lookup key in table.
-void *psHashLookup(psHash *table,       ///< table to lookup key in
-                   const char *key      ///< key to lookup
-    );
-
-/// Remove key from table.
-void *psHashRemove(psHash *table,       ///< table to lookup key in
-                   const char *key      ///< key to lookup
-    );
-\end{verbatim}
-
-A hash table is an abstract type \code{psHash}.  The argument
-\code{nbucket} to \code{psHashAlloc} is a non-binding suggestion
-from the user for the initial size of the hash table.
-
-If the \code{itemFree} argument to \code{psHashFree} is non-NULL,
-it will be used to delete the data items that have been stored
-in the hash table; if it is NULL this is the responsibility of
-the caller.
-
-The routine \code{psHashInsert} must provide a non-NULL \code{itemFree}
-argument if it wishes to change the value for previously inserted keys;
-if \code{itemFree} is NULL attempting to insert a pre-existing key
-is an error, and the routine will return NULL.  If  \code{psHashInsert}
-succeeds it returns \code{data}.
-
-\code{psHashLookup} returns the \code{data} associated with the
-key, or NULL if the key's invalid.
-
-\code{psHashRemove} removes the entry associated with the
-key from the table, and returns the \code{data}; if the key's invalid it returns NULL.
-
-\code{psHashKeylist} returns the complete list of defined keys
-associated with the psHash table. \tbd{API is not yet specified.}
+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{verbatim}
+typedef struct {
+    int nbucket;                        // number of buckets
+    psHashBucket **buckets;             // the buckets themselves
+} psHash;
+\end{verbatim}
+%
+where \code{nbucket} is the number of buckets defined for the hash
+functions, and \code{buckets} are the individual buckets, each of
+which is defined by:
+%
+\begin{verbatim}
+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{verbatim}
+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. 
+
+A hash table is created with the following function:
+\begin{verbatim}
+psHash *psHashAlloc(int nbucket);
+\end{verbatim}
+which allocates the space for the hash table and initializes all of
+the buckets.  \tbd{why specify nbucket? isn't it set by the hash
+function?}.  
+
+A data item may be added to the hash table with the function:
+\begin{verbatim}
+void *psHashInsert(psHash *table, char *key, void *data, void (*itemFree)(void *item));
+\end{verbatim}
+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.  The element destructor,
+\code{itemFree}, is provided to destroy an existing element with the
+same value of \code{key}.  The routine \code{psHashInsert} must
+provide a non-NULL \code{itemFree} argument if it wishes to change the
+value for previously inserted keys; if \code{itemFree} is NULL
+attempting to insert a pre-existing key is an error, and the routine
+will return NULL.  If \code{psHashInsert} succeeds it returns
+\code{data}.
+
+The data associated with a given key may be found with the function:
+\begin{verbatim}
+void *psHashLookup(psHash *table, char *key);
+\end{verbatim}
+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{verbatim}
+void *psHashRemove(psHash *table, char *key);
+\end{verbatim}
+\tbd{what is return value?}
+
+A complete hash table may be freed by calling:
+\begin{verbatim}
+void psHashFree(psHash *table, void (*itemFree)(void *item));
+\end{verbatim}
+where the function \code{itemFree} is provided to delete the
+individual elements in the table.  If it is NULL this is the
+responsibility of the caller.
+
+The function
+\begin{verbatim}
+psDlist *psHashKeylist(psHast *table);
+\end{verbatim}
+returns the complete list of defined keys associated with the psHash
+table as a linked list.
 
 \section{Data manipulation}