Changeset 1794

Timestamp:

Sep 10, 2004, 4:34:50 PM (22 years ago)

Author:

Paul Price

Message:

Reworked psList to employ multiple iterators.

File:

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

trunk/doc/pslib/psLibSDRS.tex

@@ -1 @@
-%%% $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 +1419 @@
 \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 +1426 @@
    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 +1464 @@
 \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 +1600 @@
 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}