Index: /trunk/doc/pslib/psLibSDRS.tex =================================================================== --- /trunk/doc/pslib/psLibSDRS.tex (revision 336) +++ /trunk/doc/pslib/psLibSDRS.tex (revision 337) @@ -1,3 +1,3 @@ -%%% $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,184 +788,193 @@ \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,219 +983,204 @@ 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}