Index: /trunk/psLib/src/sysUtils/psDList.c =================================================================== --- /trunk/psLib/src/sysUtils/psDList.c (revision 459) +++ /trunk/psLib/src/sysUtils/psDList.c (revision 460) @@ -1,9 +1,23 @@ -/* - * Minimal support for doubly linked lists - */ +/** @file psDlist.h + * @brief Support for doubly linked lists + * @ingroup DataContainers + * + * @author Robert Lupton, Princeton University + * @author Robert Daniel DeSonia, MHPCC + * + * @version $Revision: 1.3 $ $Name: not supported by cvs2svn $ + * @date $Date: 2004-04-20 01:38:34 $ + * + * Copyright 2004 Maui High Performance Computing Center, University of Hawaii + */ + #include #include #include -#include "psLib.h" +#include "psError.h" +#include "psAbort.h" +#include "psMemory.h" +#include "psDList.h" +#include "psTrace.h" static psDlistElem *dlistElemAlloc(void) @@ -17,7 +31,5 @@ } -/*****************************************************************************/ - -psDlist *psDlistAlloc(void *data) // initial data item; may be NULL +psDlist *psDlistAlloc(void *data) { psDlist *list = psAlloc(sizeof(psDlist)); @@ -26,6 +38,6 @@ list->head = list->tail = NULL; list->iter = NULL; - if (data != NULL) - { + list->iterIndex = 0; + if (data != NULL) { psDlistAdd(list, data, PS_DLIST_TAIL); } @@ -34,15 +46,11 @@ } -void psDlistFree(psDlist *list, // list to destroy - void (*elemFree)(void *)) // destructor for data on list -{ - if (list == NULL) - { +void psDlistFree(psDlist *list, void (*elemFree)(void *)) +{ + if (list == NULL) { return; } - psDlistElem *ptr = list->head; - while (ptr != NULL) - { + for(psDlistElem *ptr = list->head; ptr != NULL; ) { psDlistElem *next = ptr->next; @@ -60,31 +68,20 @@ } -/*****************************************************************************/ -/* - * Add an element to a list - */ -psDlist *psDlistAdd(psDlist *list, // list to add to; may be NULL - void *data, // data to add - int where) // where to add data. PS_DLIST_HEAD, -// PS_DLIST_TAIL, or an integer +psDlist *psDlistAdd(psDlist *list, void *data, int where) { psDlistElem *elem = dlistElemAlloc(); - if (list == NULL) - { + if (list == NULL) { list = psDlistAlloc(NULL); } - if (where > list->n) - { // XXX need better diagnostic here - fprintf(stderr, "Invalid index %d (only %d elements)\n", - where, list->n); - dlistElemFree(elem); // cleanup + if (where > list->n) { + psError(__FILE__, "Invalid index %d (only %d elements in psDList).", where, list->n); + dlistElemFree(elem); // cleanup just allocated element return list; } - if (where == PS_DLIST_HEAD) - { // easy + if (where == PS_DLIST_HEAD) { elem->prev = NULL; elem->next = list->head; @@ -100,6 +97,5 @@ } list->n++; - } else if (where == PS_DLIST_TAIL) - { // also easy + } else if (where == PS_DLIST_TAIL) { elem->prev = list->tail; elem->next = NULL; @@ -115,8 +111,36 @@ } list->n++; - } else - { // XXX - fprintf(stderr, "Insertion into psDlists is not yet supported\n"); - return psDlistAdd(list, data, PS_DLIST_TAIL); + } else if (where == PS_DLIST_PREVIOUS) { + if (list->iter == NULL) { // if no position, just insert it in the front of the list. + return psDlistAdd(list,data,PS_DLIST_HEAD); + } + elem->prev = list->iter->prev; + elem->next = list->iter; + elem->data = psMemIncrRefCounter(data); + + list->iter->prev = elem; + if (elem->prev != NULL) { + elem->prev->next = elem; + } + + list->n++; + } else if (where == PS_DLIST_NEXT) { + if (list->iter == NULL) { + return psDlistAdd(list,data,PS_DLIST_TAIL); + } + elem->prev = list->iter; + elem->next = list->iter->next; + elem->data = psMemIncrRefCounter(data); + + list->iter->next = elem; + if (elem->next != NULL) { + elem->next->prev = elem; + } + + list->n++; + } else if (where < 0) { + /// XXX What is the best way to communicate this failure to the caller? + psError(__func__,"The given insert location (%i) for psDlistAdd is invalid.",where); + } else { } @@ -156,5 +180,5 @@ } - psTrace("utils.dlist.remove", 5, "Failed to find 0x%x on psDlist 0x%x", data, list); + psTrace(__FILE__, 5, "Failed to find 0x%x on psDlist 0x%x", data, list); return NULL; @@ -199,5 +223,5 @@ if (which < 0 || which >= list->n) { // out of bounds - psError(__func__, PS_ERR_BAD_INDEX, 1, "Index %d is not in range [0..%d] for list 0x%x", which, list->n, + psError(__func__,"Index %d is not in range [0..%d] for list 0x%x", which, list->n, list); return NULL; @@ -229,7 +253,7 @@ * * If which is psDlist{Next,Prev} return the next/previous - * data and move the iteration cursor - * - * If which is psDlist{Head,Tail} initialise the iteration pointer + * data and move the iteration cursor + * + * If which is psDlist{Head,Tail} initialize the iteration pointer * and return the head/tail * @@ -239,19 +263,21 @@ #define ITER_INIT_TAIL ((void *)2) // next iteration should return tail -void *psDlistGet( - const psDlist *list, // list to retrieve element from - int which) // index of item, or PS_DLIST_NEXT, -// or PS_DLIST_PREV -{ - assert (list != NULL); +void *psDlistGet(const psDlist *list, int which) +{ + if (list == NULL) { + psError(__func__,"Unexpected null pointer for psDlist parameter (%s:%d).",__FILE__,__LINE__); + return NULL; + } switch (which) { - case PS_DLIST_HEAD: // easy + case PS_DLIST_HEAD: ((psDlist *)list)->iter = ITER_INIT_HEAD; return (list->head == NULL) ? NULL : list->head->data; - case PS_DLIST_TAIL: // also easy + + case PS_DLIST_TAIL: ((psDlist *)list)->iter = ITER_INIT_TAIL; return (list->tail == NULL) ? NULL : list->tail->data; - case PS_DLIST_PREV: // use iterator + + case PS_DLIST_PREVIOUS: // use iterator case PS_DLIST_NEXT: if (list->iter == NULL) { @@ -261,11 +287,10 @@ } else if (list->iter == ITER_INIT_TAIL) { ((psDlist *)list)->iter = list->tail; - } else if (which == PS_DLIST_PREV) { + } else if (which == PS_DLIST_PREVIOUS) { ((psDlist *)list)->iter = list->iter->prev; } else if (which == PS_DLIST_NEXT) { ((psDlist *)list)->iter = list->iter->next; } else { - fprintf(stderr,"You cannot get here\n"); - abort(); + psAbort(__func__,"Unreachable line was reached in %s:%d?",__FILE__,__LINE__); } @@ -276,8 +301,16 @@ break; - default: // XXX - fprintf(stderr, - "Retrieval from psDlists by index is not yet supported\n"); - return NULL; + default: + if (which < 0) { + psError(__func__,"the position is invalid for %s",__func__); + return NULL; + } + ((psDlist *)list)->iter = list->head; + for (int i=0;iiter == NULL) { + return NULL; + } + return list->iter->data; // XXX what if data is NULL? } } @@ -289,11 +322,9 @@ * First a call to set the iteration pointer to the head of the list */ -void psDlistSetIterator(psDlist *list, // the list in question - int where, // where on the list should I start? - int which) // @notused@ the desired iterator -{ - if (where != PS_DLIST_HEAD && where != PS_DLIST_TAIL) - { - psError(__func__, PS_ERR_UNKNOWN, 1, "Invalid where argument: %d; assuming PS_DLIST_HEAD", where); +void psDlistSetIterator(psDlist *list, + int where) +{ + if (where != PS_DLIST_HEAD && where != PS_DLIST_TAIL) { + psError(__func__, "Invalid where argument: %d; assuming PS_DLIST_HEAD", where); where = PS_DLIST_HEAD; } @@ -305,17 +336,20 @@ * and now return the previous/next element of the list */ -void *psDlistGetNext(psDlist *list, // the list in question - int which) // @notused@ the desired iterator +void *psDlistGetNext(psDlist *list) { return psDlistGet(list, PS_DLIST_NEXT); } -void *psDlistGetPrev(psDlist *list, // the list in question - int which) // @notused@ the desired iterator -{ - return psDlistGet(list, PS_DLIST_PREV); -} - -/*****************************************************************************/ +void *psDlistGetPrevious(psDlist *list) +{ + return psDlistGet(list, PS_DLIST_PREVIOUS); +} + +void *psDlistGetCurrent(psDlist *list) +{ + return psDlistGet(list, PS_DLIST_CURRENT); +} + +#if 0 /* * Convert a psDlist to/from a psVoidPtrArray @@ -356,2 +390,4 @@ return list; } + +#endif Index: /trunk/psLib/src/sysUtils/psDList.h =================================================================== --- /trunk/psLib/src/sysUtils/psDList.h (revision 459) +++ /trunk/psLib/src/sysUtils/psDList.h (revision 460) @@ -9,16 +9,26 @@ * @author Robert Daniel DeSonia, MHPCC * - * @version $Revision: 1.3 $ $Name: not supported by cvs2svn $ - * @date $Date: 2004-04-19 21:06:37 $ + * @version $Revision: 1.4 $ $Name: not supported by cvs2svn $ + * @date $Date: 2004-04-20 01:38:34 $ * * Copyright 2004 Maui High Performance Computing Center, University of Hawaii */ +/** 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_PREVIOUS = -3, ///< previous element + PS_DLIST_CURRENT = -4, ///< current element + PS_DLIST_NEXT = -5 ///< next element +}; + /** 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 + struct psDlistElem *prev; ///< previous link in list + struct psDlistElem *next; ///< next link in list + void *data; ///< real data item } psDlistElem; @@ -27,80 +37,87 @@ 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 + 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 + int iterIndex; } 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 -}; - -/** Functions **************************************************************/ -/** \addtogroup DataGroup General Data Container Utilities - * \{ +/** @addtogroup DataContainers General Data Container Utilities + * @{ */ /** Constructor */ -psDlist *psDlistAlloc(void *data) ///< initial data item; may be NULL -; +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 ****/ +void psDlistFree( + psDlist *list, ///< list to destroy + void (*elemFree)(void *) ///< destructor for data on list +); /** 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 -; +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 -; +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, PS_DLIST_NEXT, PS_DLIST_PREV -; +void *psDlistRemove( + psDlist *list, ///< list to remove element from + void *data, ///< data item to remove + int which ///< index of item, or PS_DLIST_UNKNOWN, PS_DLIST_NEXT, 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, PS_DLIST_PREV, PS_DLIST_UNKNOWN -; +void *psDlistGet( + const psDlist *list, ///< list to retrieve element from + int which ///< index of item, or PS_DLIST_NEXT, PS_DLIST_PREV, PS_DLIST_UNKNOWN +); /** Set the iterator */ -void psDlistSetIterator(psDlist *list, ///< list to retrieve element from - int where) ///< index, PS_DLIST_HEAD, or PS_DLIST_TAIL -; +void psDlistSetIterator( + psDlist *list, ///< list to retrieve element from + int where ///< index, PS_DLIST_HEAD, or PS_DLIST_TAIL +); /** Get next element relative to iter */ -void *psDlistGetNext(psDlist *list) ///< list to retrieve element from -; +void *psDlistGetNext( + psDlist *list ///< list to retrieve element from +); + +/** Get current element at iter */ +void *psDlistGetCurrent( + psDlist *list ///< list to retrieve element from +); /** Get prev element relative to iter */ -void *psDlistGetPrev(psDlist *list) ///< list to retrieve element from -; +void *psDlistGetPrevious( + psDlist *list ///< list to retrieve element from +); /** Convert doubly-linked list to an array */ -psVoidPtrArray *psDlistToArray(psDlist *dlist) ///< List to convert -; +#if 0 +psVoidPtrArray *psDlistToArray( + psDlist *dlist ///< List to convert +); /** Convert array to a doubly-linked list */ -psDlist *psArrayToDlist(psVoidPtrArray *arr) ///< Array to convert -; +psDlist *psArrayToDlist( + psVoidPtrArray *arr ///< Array to convert +); +#endif -/* \} */ // End of DataGroup Functions +/// @} End of DataGroup Functions #endif