Index: /trunk/doc/pslib/psLibSDRS.tex =================================================================== --- /trunk/doc/pslib/psLibSDRS.tex (revision 1793) +++ /trunk/doc/pslib/psLibSDRS.tex (revision 1794) @@ -1,3 +1,3 @@ -%%% $Id: psLibSDRS.tex,v 1.121 2004-09-10 00:33:54 price Exp $ +%%% $Id: psLibSDRS.tex,v 1.122 2004-09-11 02:34:50 price Exp $ \documentclass[panstarrs,spec]{panstarrs} @@ -1419,5 +1419,5 @@ \label{sec:psList} -\PS{} supports doubly linked lists through a type \code{psList}: +\PS{} shall support doubly linked lists through a type \code{psList}: % \begin{verbatim} @@ -1426,15 +1426,18 @@ psListElem *head; ///< first element on list (may be NULL) psListElem *tail; ///< last element on list (may be NULL) - psListElem *iter; ///< iteration cursor - unsigned int iterIndex; ///< the numeric position of the iteration cursor in the list + unsigned int nIter; ///< number of iterators + psListIterator **iter; ///< iteration cursors pthread_mutex_t lock; ///< mutex to lock a node during changes } psList; \end{verbatim} % -The type \code{psList} represents the container of the list. It has -a pointer to the first element in the linked list (\code{head}), a +The type \code{psList} represents the container of the list. It has a +pointer to the first element in the linked list (\code{head}), a pointer to the last element in the list (\code{tail}), an entry for the current cursor location (\code{iter}), and an entry to define the -number of elements in the list (\code{n}). +number of elements in the list (\code{size}). Iteration on the list +is achieved by means of an array of \code{nIter} iteration cursors, +\code{iter}. The \code{lock} should be applied during changes to the +list to maintain thread safety. The elements of the list are defined by the type \code{psListElem}: @@ -1461,50 +1464,131 @@ \code{psList.head} and \code{psList.tail}. If the data entry is \code{NULL}, then an empty list, with both pointers are set to -\code{NULL} should be created. - -The destructor function for \code{psList} must free the data -associated with the entire list. +\code{NULL} should be created. The number of iterators in the list is +initially set to zero. + +The destructor function for \code{psList} must call \code{psFree} for +all the the data associated with the list. + +All data items placed onto lists must have their reference counters +(section \ref{secMemRefcounter}) incremented. When elements are +removed from a list, they must have their reference counters +decremented. The action of retrieving data from a list (with one of +the three \code{psListGet} functions) also increments the reference +counter. + +Iteration on the list shall be achieved by means of a list iterator +type: +\begin{verbatim} +typedef struct { + psList *list; ///< List iterator works on + unsigned int num; ///< Iterator number + psListElem *cursor; ///< The current iterator cursor + bool offEnd; ///< Is the iterator off the end? +} psListIterator; +\end{verbatim} +The \code{psListIterator} keeps track of which list element the +iterator \code{cursor} is currently pointing at. \code{num} is the +number of the list iterator in the parent \code{list}'s array of +iterators, so \code{list->iter[num]} points to the list iterator. The +boolean member, \code{offEnd}, indicates whether the iterator has +progressed off the end of the list (i.e., beyond the last item). + +The corresponding constructor shall be: +\begin{verbatim} +psListIterator *psListIteratorAlloc(psList *list, int location); +\end{verbatim} +Here, \code{list} is the \code{psList} on which the iterator will +iterate, and \code{location} is the initial starting point, and may be +a numerical index or it may be one of the special values: +\code{PS_LIST_HEAD} or \code{PS_LIST_TAIL}, which are defined as +negative integers. Of course, the \code{psListElem} pointed to by the +iterator shall have its \code{refCounter} incremented. + +The destructor for \code{psListIterator} shall, after freeing the +\code{psListIterator} and decrementing the \code{refCounter} of the +\code{psListElem} that it pointed to, also reorganise the \code{iter} +array (replacing the element being removed with the last element) and +resizing the array appropriately. + +A list \code{iterator} shall be set to a specific \code{location} on +the list upon calling \code{psListIteratorSet}: +\begin{verbatim} +bool psListIteratorSet(psListIterator *iterator, int location); +\end{verbatim} +Again, the \code{location} may be a numerical index or it may be one +of the special values: \code{PS_LIST_HEAD} or \code{PS_LIST_TAIL}, +which are defined as negative integers. The function shall return +\code{true} if the reset was successful, or \code{false} otherwise. \begin{verbatim} bool psListAdd(psList *list, int location, void *data); -\end{verbatim} -Add an entry to the list with this function, which takes a pointer to -the list and returns a boolean giving the success or failure of the -operation. The value of \code{location} specifies if the specified -data item should be placed on the front of the list -(\code{PS_LIST_HEAD}), at the end of the list (\code{PS_LIST_TAIL}), -to add after (\code{PS_LIST_NEXT}) or before (\code{PS_LIST_PREV}) the -current element (specified by the iteration cursor), or an index that -the new \code{data} should inhabit. +bool psListAddAfter(psListIterator *iterator, void *data); +bool psListAddBefore(psListIterator *iterator, void *data); +\end{verbatim} +the first function, \code{psListAdd}, adds an entry to the \code{list} +and returns a boolean giving the success or failure of the +operation. The value of \code{location} may be a numerical index the +\code{data} is to inhabit (if \code{location} is greater than the +number of items on the list, then the function shall generate a +warning and add the \code{data} to the tail) or it may be one of the +special values: \code{PS_LIST_HEAD} or \code{PS_LIST_TAIL}, which are +defined as negative integers. The other two functions, +\code{psListAddAfter} and \code{psListAddBefore} specify that the +\code{data} shall be added after or before (respectively) the current +cursor position of the \code{iterator}. \begin{verbatim} void *psListGet(psList *list, int location); -\end{verbatim} -A data item may be retrieved from the list with this function. The -value of \code{location} may be the numerical index or it may be one -of the special values: \code{PS_LIST_HEAD}, \code{PS_LIST_TAIL}, -\code{PS_LIST_PREV}, and \code{PS_LIST_NEXT}, all of which are defined -as negative integers, allowing \code{location} to also be the index of -one of the data items. - -\begin{verbatim} -bool psListRemove(psList *list, int location, void *data); -\end{verbatim} -A data item may be removed from the list with this function. The -value of \code{location} may be the numerical index or it may be one -of the special values: \code{PS_LIST_HEAD}, \code{PS_LIST_TAIL}, -\code{PS_LIST_PREV}, \code{PS_LIST_UNKNOWN}, and \code{PS_LIST_NEXT}, -all of which are defined as negative integers. If the value of -\code{location} is \code{PS_LIST_UNKNOWN}, then the data item is -identified by matching the pointer value with \code{void *data}. The -function returns a value of \code{true} if the operation was -successful, and \code{false} otherwise. - -All data items placed onto lists (\code{psListAdd}) must have their -reference counters (section \ref{secMemRefcounter}) incremented. When -elements are removed from a list with \code{psListRemove}, they must -have their reference counters decremented. The action of retrieving -data from a list (with \code{psListGet}) also increments the reference -counter. +void *psListGetNext(psListIterator *iterator); +void *psListGetPrevious(psListIterator *iterator); +\end{verbatim} +A data item may be retrieved from the list with these functions. The +first function, \code{psListGet} simply returns the value specified +by its \code{location}, which may be a numerical index or it may be +one of the special values: \code{PS_LIST_HEAD} or \code{PS_LIST_TAIL}, +which are defined as negative integers, allowing \code{location} to +also be the index of one of the data items. The other two functions, +\code{psListGetNext} and \code{psListGetPrevious} return the item +under the iteration cursor before advancing to the next or previous +item, respectively. + +In the event that the iteration cursor is at the tail of the list, +\code{psListGetNext} shall return the tail item and then set the +\code{cursor} to \code{NULL} and \code{offEnd} to \code{true}. In the +event that the iteration cursor is at the head of the list, +\code{psListGetPrevious} shall return the head item and then set the +\code{cursor} to \code{NULL} (and \code{offEnd} should already be +\code{false}). In the event that the iteration \code{cursor} is +\code{NULL}, \code{psListGetNext} and \code{psListGetPrevious} shall +return \code{NULL}, and advance the iteration \code{cursor} only if +the intended direction places the cursor back on the list; otherwise a +warning shall be generated, and no change shall be made. If +\code{psListGetPrevious} was called with \code{offEnd} as \code{true}, +then \code{offEnd} shall also be toggled back to \code{false} to +indicate that the \code{cursor} is no longer off the end of the list. +When setting the \code{cursor}, the appropriate \code{refCounter}s +shall be incremented and decremented. + +\begin{verbatim} +bool psListRemove(psList *list, int location) +bool psListRemoveData(psList *list, void *data); +bool psListRemoveAfter(psListIterator *iterator); +bool psListRemoveBefore(psListIterator *iterator); +\end{verbatim} +A data item may be removed from the list with these functions. For +\code{psListRemove}, the value of \code{location} may be the numerical +index or it may be one of the special values: \code{PS_LIST_HEAD} or +\code{PS_LIST_TAIL}, which are defined as negative integers. For +\code{psListRemoveData}, the data item to be removed is identified by +matching the pointer value with \code{void *data}. The functions +return a value of \code{true} if the operation was successful, and +\code{false} otherwise. The other two functions, +\code{psListRemoveBefore} and \code{psListRemoveAfter} remove the item +before or after (respectively) the iteration cursor. In all cases, if +any iterators are currently pointing at the item to be removed, or the +item to be removed is not on the list, an error shall be generated, +the item shall not be removed, and the function shall return +\code{false}. + \begin{verbatim} @@ -1516,20 +1600,4 @@ free the elements or destroy the input collection. Rather, they increment the reference counter for each of the elements. - -\begin{verbatim} -void psListSetIterator(psList *list, int iterator, int location); -void *psListGetNext(psList *list, int iterator); -void *psListGetPrevious(psList *list, int iterator); -\end{verbatim} -Iteration over all elements of the list using the iteration cursor -\code{iter} is provided by these functions. The first of these -functions uses the value of \code{location} to set the iteration -cursor for the given list to the beginning \code{PS_LIST_HEAD} or the -end \code{PS_LIST_TAIL} for the iterator specified by \code{iterator}. -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{psListElem}s \code{prev} and \code{next} pointers is -also supported. \begin{verbatim}