Index: /trunk/psLib/src/collections/Makefile =================================================================== --- /trunk/psLib/src/collections/Makefile (revision 873) +++ /trunk/psLib/src/collections/Makefile (revision 874) @@ -3,6 +3,6 @@ ## Makefile: collections ## -## $Revision: 1.17 $ $Name: not supported by cvs2svn $ -## $Date: 2004-06-04 19:36:07 $ +## $Revision: 1.18 $ $Name: not supported by cvs2svn $ +## $Date: 2004-06-04 23:44:36 $ ## ## Copyright 2004 Maui High Performance Computing Center, University of Hawaii @@ -34,5 +34,5 @@ psSort.o \ psImage.o \ - psDList.o + psDlist.o # Define PHONY target "all" which will make all the necessary items Index: unk/psLib/src/collections/psDList.c =================================================================== --- /trunk/psLib/src/collections/psDList.c (revision 873) +++ (revision ) @@ -1,447 +1,0 @@ -/** @file psDlist.h - * @brief Support for doubly linked lists - * @ingroup DataContainers - * - * @author Robert Lupton, Princeton University - * @author Robert Daniel DeSonia, MHPCC - * - * @version $Revision: 1.1 $ $Name: not supported by cvs2svn $ - * @date $Date: 2004-06-04 18:59:47 $ - * - * Copyright 2004 Maui High Performance Computing Center, University of Hawaii - */ - -#include -#include -#include -#include // we need a mutex to make this stuff thread safe. - -#include "psError.h" -#include "psAbort.h" -#include "psMemory.h" -#include "psDList.h" -#include "psTrace.h" - -#define ITER_INIT_HEAD ((void *)1) // next iteration should return head -#define ITER_INIT_TAIL ((void *)2) // next iteration should return tail - -// private functions. -psDlistElem* dlistGetIterator(psDlist* list); -int dlistGetIteratorIndex(psDlist* list); -void dlistSetIterator(psDlist *list, int where, bool lockList); - - - -static psDlistElem *dlistElemAlloc(void) -{ - return(psAlloc(sizeof(psDlistElem))); -} - -static void dlistElemFree(psDlistElem *elem) -{ - psFree(elem); -} - -psDlist *psDlistAlloc(void *data) -{ - psDlist *list = psAlloc(sizeof(psDlist)); - - list->size = 0; - list->head = list->tail = NULL; - list->iter = ITER_INIT_HEAD; - list->iterIndex = PS_DLIST_HEAD; - pthread_mutex_init(&(list->lock),NULL) - ; - - if (data != NULL) { - psDlistAdd(list, data, PS_DLIST_TAIL); - } - - return list; -} - -void psDlistFree(psDlist *list, void (*elemFree)(void *)) -{ - if (list == NULL) { - return; - } - - pthread_mutex_lock(&list->lock) - ; - - for(psDlistElem *ptr = list->head; ptr != NULL; ) { - psDlistElem *next = ptr->next; - - if (elemFree == NULL) { - psMemDecrRefCounter(ptr->data); - } else { - elemFree(psMemDecrRefCounter(ptr->data)); - } - dlistElemFree(ptr); - - ptr = next; - } - - pthread_mutex_unlock(&list->lock) - ; - - pthread_mutex_destroy(&list->lock) - ; - - psFree(list); -} - -psDlist *psDlistAdd(psDlist *list, void *data, int where) -{ - psDlistElem* position; - psDlistElem* elem = dlistElemAlloc(); - - if (list == NULL) { - list = psDlistAlloc(NULL); - } - - pthread_mutex_lock(&list->lock) - ; - - if (where <= PS_DLIST_UNKNOWN) { - /// XXX What is the better way to communicate this failure to the caller? - psError(__func__,"The given insert location (%i) for psDlistAdd is invalid. " - "Adding to head instead.",where); - where = PS_DLIST_HEAD; // given I can't tell caller about this, should just add it somewhere??? - } - - if (where > list->size) { - psError(__FILE__, "Invalid index %d (only %d elements in psDList); assuming tail.", where, - list->size); - where = PS_DLIST_TAIL; - } - - if (where == PS_DLIST_TAIL || list->size == 0) { - // insert the element at the end of the list - elem->prev = list->tail; - elem->next = NULL; - - if (list->tail != NULL) { - list->tail->next = elem; - } - - if (list->head == NULL) { - list->head = elem; - } - list->tail = elem; - - list->size++; - list->iter = elem; - list->iterIndex = list->size - 1; - } else { - // move ourselves to the given position - dlistSetIterator(list, where, false); - position = dlistGetIterator(list); - - if (position == NULL) { - psError(__func__,"%s failed to move cursor to specified location (%d)",__func__,where); - position = list->head; // since we no list->size != 0, this must be non-NULL - } - - // insert our new element in front of the given position - elem->prev = position->prev; - elem->next = position; - position->prev = elem; - - if (elem->prev == NULL) { // must be front of list - list->head = elem; - } else { - elem->prev->next = elem; - } - - list->size++; - list->iter = elem; - } - - elem->data = psMemIncrRefCounter(data); - - pthread_mutex_unlock(&list->lock) - ; - - return list; -} - -/*****************************************************************************/ - -psDlist *psDlistAppend(psDlist *list, void *data) -{ - return psDlistAdd(list, data, PS_DLIST_TAIL); -} - -/*****************************************************************************/ -/* - * Remove an element from a list - */ -void *psDlistRemove(psDlist *list, void *data, int which) -{ - psDlistElem *elem = NULL; // element to remove - if (list == NULL) { - psError(__func__,"list parameter found to be NULL in %s",__func__); - return NULL; - } - - // get exclusive access to list so that other threads will not get in the way. - pthread_mutex_lock(&list->lock) - ; - - if (which == PS_DLIST_UNKNOWN) { - // search list for the data item. - - int i = 0; // index - for (psDlistElem *ptr = list->head; ptr != NULL; ptr = ptr->next) { - if (ptr->data == data) { - which = i; - break; - } - i++; - } - - if (which == PS_DLIST_UNKNOWN) { - psError(__func__, "Failed to find 0x%x on psDlist 0x%x in %s.", data, list,__func__); - return NULL; - } - } - - // position the list's cursor to the desired location - dlistSetIterator(list,which,false); - elem = dlistGetIterator(list); - - if (elem == NULL) { - psError(__func__, "Couldn't position to given index (%d) to remove element from list.",which); - return NULL; - } - - list->size--; - - if (elem->prev == NULL) { // head of list? - list->head = elem->next; - } else { - elem->prev->next = elem->next; - } - - if (elem->next == NULL) { // tail of list? - list->tail = elem->prev; - - // removed tail, so iter should be the last element of list to keep it valid - if (list->size > 0) { - list->iter = list->tail; - list->iterIndex = list->size - 1; - } else { - list->iter = ITER_INIT_TAIL; - } - } else { - elem->next->prev = elem->prev; - list->iter = elem->next; - } - - pthread_mutex_unlock(&list->lock) - ; - - /* - * OK, delete list element and return the data - */ - data = elem->data; - dlistElemFree(elem); - return psMemDecrRefCounter(data); -} - -void psDlistSetIterator(psDlist *list, int where) -{ - dlistSetIterator(list,where,true); -} - -void dlistSetIterator(psDlist* list, int where, bool lockList) -{ - psDlistElem* cursor; - int position; - - if (list == NULL) { - psError(__func__,"Unexpected null pointer for psDlist parameter (%s:%d).",__FILE__,__LINE__); - return; - } - - if (where == PS_DLIST_CURRENT) { - return; - } - - if (lockList) { - pthread_mutex_lock(&list->lock) - ; // don't want the list changing on us while we move about - } - - if (where >= list->size) { - psError(__func__,"Tried to access an element beyond list end. " - "Moved to last element of list instead."); - where = list->size-1; - - switch (where) { - case PS_DLIST_HEAD: - list->iter = ITER_INIT_HEAD; - break; - - case PS_DLIST_TAIL: - list->iter = ITER_INIT_TAIL; - break; - - case PS_DLIST_PREVIOUS: - cursor = dlistGetIterator(list); - position = dlistGetIteratorIndex(list); - - if (cursor == NULL) { // list empty? - ((psDlist *)list)->iter = ITER_INIT_HEAD; - } else { - if (cursor->prev != NULL) { // don't go past head - list->iter = cursor->prev; - list->iterIndex = position-1; - break; - } - } - - case PS_DLIST_NEXT: - cursor = dlistGetIterator(list); - position = dlistGetIteratorIndex(list); - - if (cursor == NULL) { // list empty? - ((psDlist *)list)->iter = ITER_INIT_HEAD; - } else { - if (cursor->next != NULL) { // don't go pase tail - list->iter = cursor->next; - list->iterIndex = position+1; - break; - } - } - - case PS_DLIST_UNKNOWN: - psError(__func__,"Can't move to the PS_DLIST_UNKNOWN position. Not moving the iterator position."); - break; - case PS_DLIST_CURRENT: - break; - - default: - if (where < PS_DLIST_HEAD) { // bascially same as PS_DLIST_UNKNOWN above - psError(__func__,"Can't move to an unknown position. Not moving the iterator position."); - break; - } else { - int position = dlistGetIteratorIndex(list); - - if (where < position) { - int diff = position-where; - for (int count=0;count < diff; count++) { - dlistSetIterator(list,PS_DLIST_PREVIOUS,false); - } - } else { - int diff = where-position; - for (int count=0;count < diff; count++) { - dlistSetIterator(list,PS_DLIST_NEXT,false); - } - } - } - break; - } - - if (lockList) { - pthread_mutex_unlock(&list->lock) - ; - } - } -} - -psDlistElem* dlistGetIterator(psDlist* list) -{ - if (list->iter == ITER_INIT_HEAD) { - return list->head; - } else if (list->iter == ITER_INIT_TAIL) { - return list->tail; - } else { - return list->iter; - } -} - -int dlistGetIteratorIndex(psDlist* list) -{ - if (list->iter == ITER_INIT_HEAD) { - return 0; - } else if (list->iter == ITER_INIT_TAIL) { - return list->size-1; - } else { - return list->iterIndex; - } -} - -void* psDlistGet(psDlist* list,int which) -{ - psDlistElem* element; - - psDlistSetIterator(list,which); - element = dlistGetIterator(list); - - if (element == NULL) { - return NULL; - } else { - return element->data; - } -} -/* - * and now return the previous/next element of the list - */ -void *psDlistGetNext(psDlist *list) -{ - return psDlistGet(list, PS_DLIST_NEXT); -} - -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 - */ -psVoidPtrArray *psDlistToArray(psDlist *restrict dlist) -{ - if (dlist == NULL) { - return NULL; - } - - psVoidPtrArray *restrict arr = psVoidPtrArrayAlloc(dlist->size, dlist->size); - - psDlistElem *ptr = dlist->head; - for (int i = 0, n = dlist->size; i < n; i++) { - arr->arr[i] = ptr->data; - - ptr->data = NULL; - ptr = ptr->next; - } - - psDlistFree(dlist, NULL); - - return arr; -} - -psDlist *psArrayToDlist(psVoidPtrArray *arr) -{ - psDlist *list = psDlistAlloc(NULL); // list of elements - - for (int i = 0, n = arr->size; i < n; i++) { - psDlistAppend(list, - psMemDecrRefCounter(arr->arr[i])); // it's already Incr - arr->arr[i] = NULL; - } - - psVoidPtrArrayFree(arr, NULL); - - return list; -} - -#endif Index: unk/psLib/src/collections/psDList.h =================================================================== --- /trunk/psLib/src/collections/psDList.h (revision 873) +++ (revision ) @@ -1,132 +1,0 @@ -#if !defined(PS_DLIST_H) -#define PS_DLIST_H - -/** @file psDlist.h - * @brief Support for doubly linked lists - * @ingroup DataContainers - * - * @author Robert Lupton, Princeton University - * @author Robert Daniel DeSonia, MHPCC - * - * @version $Revision: 1.1 $ $Name: not supported by cvs2svn $ - * @date $Date: 2004-06-04 18:59:47 $ - * - * Copyright 2004 Maui High Performance Computing Center, University of Hawaii - */ - -#include // we need a mutex to make this stuff thread safe. - -/** Special values of index into list - * - * This list of possible list position values should be contiguous non-positive values ending with - * PS_DLIST_UNKNOWN. Any value less-than-or-equal-to PS_DLIST_UNKNOWN is considered a undefined position. - * - */ -enum { - PS_DLIST_HEAD = 0, ///< at head - PS_DLIST_TAIL = -1, ///< at tail - PS_DLIST_PREVIOUS = -2, ///< previous element - PS_DLIST_CURRENT = -3, ///< current element - PS_DLIST_NEXT = -4, ///< next element - PS_DLIST_UNKNOWN = -5 ///< unknown position (should be last in enum list) -}; - -/** 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 */ -typedef struct -{ - unsigned int size; ///< 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 - unsigned int iterIndex; ///< the numeric position of the iteration cursor in the list - pthread_mutex_t lock; ///< mutex to lock a node during changes -} -psDlist; - -/** @addtogroup DataContainers General Data Container Utilities - * @{ - */ - -/** Constructor */ -psDlist *psDlistAlloc( - void *data ///< initial data item; may be NULL -) -; - -/** Destructor */ -void psDlistFree( - psDlist* restrict list, ///< list to destroy - void (*elemFree)(void *) ///< destructor for data on list -); - -/** Add to list */ -psDlist* psDlistAdd( - psDlist* restrict 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* restrict list, ///< list to append to (may be NULL) - void *data ///< data item to add -); - -/** Remove from a list */ -void* psDlistRemove( - psDlist* restrict 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( - psDlist* restrict 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* restrict 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* restrict list ///< list to retrieve element from -); - -/** Get current element at iter */ -void* psDlistGetCurrent( - psDlist* restrict list ///< list to retrieve element from -); - -/** Get prev element relative to iter */ -void* psDlistGetPrevious( - psDlist* restrict list ///< list to retrieve element from -); - -/** Convert doubly-linked list to an array */ -#if 0 -psVoidPtrArray *psDlistToArray( - psDlist *dlist ///< List to convert -); - -/** Convert array to a doubly-linked list */ -psDlist *psArrayToDlist( - psVoidPtrArray *arr ///< Array to convert -); -#endif - -/// @} End of DataGroup Functions - -#endif Index: /trunk/psLib/src/collections/psDlist.c =================================================================== --- /trunk/psLib/src/collections/psDlist.c (revision 874) +++ /trunk/psLib/src/collections/psDlist.c (revision 874) @@ -0,0 +1,443 @@ +/** @file psDlist.h + * @brief Support for doubly linked lists + * @ingroup DataContainers + * + * @author Robert Lupton, Princeton University + * @author Robert Daniel DeSonia, MHPCC + * + * @version $Revision: 1.1 $ $Name: not supported by cvs2svn $ + * @date $Date: 2004-06-04 23:44:36 $ + * + * Copyright 2004 Maui High Performance Computing Center, University of Hawaii + */ + +#include +#include +#include +#include // we need a mutex to make this stuff thread safe. + +#include "psError.h" +#include "psAbort.h" +#include "psMemory.h" +#include "psDlist.h" +#include "psTrace.h" + +#define ITER_INIT_HEAD ((void *)1) // next iteration should return head +#define ITER_INIT_TAIL ((void *)2) // next iteration should return tail + +// private functions. +psDlistElem* dlistGetIterator(psDlist* list); +int dlistGetIteratorIndex(psDlist* list); +void dlistSetIterator(psDlist *list, int where, bool lockList); + + + +static psDlistElem *dlistElemAlloc(void) +{ + return(psAlloc(sizeof(psDlistElem))); +} + +static void dlistElemFree(psDlistElem *elem) +{ + psFree(elem); +} + +psDlist *psDlistAlloc(void *data) +{ + psDlist *list = psAlloc(sizeof(psDlist)); + + list->size = 0; + list->head = list->tail = NULL; + list->iter = ITER_INIT_HEAD; + list->iterIndex = PS_DLIST_HEAD; + pthread_mutex_init(&(list->lock),NULL) + ; + + if (data != NULL) { + psDlistAdd(list, data, PS_DLIST_TAIL); + } + + return list; +} + +void psDlistFree(psDlist *list, psFreeFcn elemFree) +{ + if (list == NULL) { + return; + } + + pthread_mutex_lock(&list->lock) + ; + + for(psDlistElem *ptr = list->head; ptr != NULL; ) { + psDlistElem *next = ptr->next; + + p_psCustomFree(elemFree, psMemDecrRefCounter(ptr->data)); + dlistElemFree(ptr); + + ptr = next; + } + + pthread_mutex_unlock(&list->lock) + ; + + pthread_mutex_destroy(&list->lock) + ; + + psFree(list); +} + +psDlist *psDlistAdd(psDlist *list, void *data, int where) +{ + psDlistElem* position; + psDlistElem* elem = dlistElemAlloc(); + + if (list == NULL) { + list = psDlistAlloc(NULL); + } + + pthread_mutex_lock(&list->lock) + ; + + if (where <= PS_DLIST_UNKNOWN) { + /// XXX What is the better way to communicate this failure to the caller? + psError(__func__,"The given insert location (%i) for psDlistAdd is invalid. " + "Adding to head instead.",where); + where = PS_DLIST_HEAD; // given I can't tell caller about this, should just add it somewhere??? + } + + if (where > 0 && where > list->size) { + psError(__FILE__, "Invalid index %d (only %d elements in psDList); assuming tail.", where, + list->size); + where = PS_DLIST_TAIL; + } + + if (where == PS_DLIST_TAIL || list->size == 0) { + // insert the element at the end of the list + elem->prev = list->tail; + elem->next = NULL; + + if (list->tail != NULL) { + list->tail->next = elem; + } + + if (list->head == NULL) { + list->head = elem; + } + list->tail = elem; + + list->size++; + list->iter = elem; + list->iterIndex = list->size - 1; + } else { + // move ourselves to the given position + dlistSetIterator(list, where, false); + position = dlistGetIterator(list); + + if (position == NULL) { + psError(__func__,"%s failed to move cursor to specified location (%d)",__func__,where); + position = list->head; // since we no list->size != 0, this must be non-NULL + } + + // insert our new element in front of the given position + elem->prev = position->prev; + elem->next = position; + position->prev = elem; + + if (elem->prev == NULL) { // must be front of list + list->head = elem; + } else { + elem->prev->next = elem; + } + + list->size++; + list->iter = elem; + } + + elem->data = psMemIncrRefCounter(data); + + pthread_mutex_unlock(&list->lock) + ; + + return list; +} + +/*****************************************************************************/ + +psDlist *psDlistAppend(psDlist *list, void *data) +{ + return psDlistAdd(list, data, PS_DLIST_TAIL); +} + +/*****************************************************************************/ +/* + * Remove an element from a list + */ +void *psDlistRemove(psDlist *list, void *data, int which) +{ + psDlistElem *elem = NULL; // element to remove + if (list == NULL) { + psError(__func__,"list parameter found to be NULL in %s",__func__); + return NULL; + } + + // get exclusive access to list so that other threads will not get in the way. + pthread_mutex_lock(&list->lock) + ; + + if (which == PS_DLIST_UNKNOWN) { + // search list for the data item. + + int i = 0; // index + for (psDlistElem *ptr = list->head; ptr != NULL; ptr = ptr->next) { + if (ptr->data == data) { + which = i; + break; + } + i++; + } + + if (which == PS_DLIST_UNKNOWN) { + psError(__func__, "Failed to find 0x%x on psDlist 0x%x in %s.", data, list,__func__); + return NULL; + } + } + + // position the list's cursor to the desired location + dlistSetIterator(list,which,false); + elem = dlistGetIterator(list); + + if (elem == NULL) { + psError(__func__, "Couldn't position to given index (%d) to remove element from list.",which); + return NULL; + } + + list->size--; + + if (elem->prev == NULL) { // head of list? + list->head = elem->next; + } else { + elem->prev->next = elem->next; + } + + if (elem->next == NULL) { // tail of list? + list->tail = elem->prev; + + // removed tail, so iter should be the last element of list to keep it valid + if (list->size > 0) { + list->iter = list->tail; + list->iterIndex = list->size - 1; + } else { + list->iter = ITER_INIT_TAIL; + } + } else { + elem->next->prev = elem->prev; + list->iter = elem->next; + } + + pthread_mutex_unlock(&list->lock) + ; + + /* + * OK, delete list element and return the data + */ + data = elem->data; + dlistElemFree(elem); + return psMemDecrRefCounter(data); +} + +void psDlistSetIterator(psDlist *list, int where) +{ + dlistSetIterator(list,where,true); +} + +void dlistSetIterator(psDlist* list, int where, bool lockList) +{ + psDlistElem* cursor; + int position; + + if (list == NULL) { + psError(__func__,"Unexpected null pointer for psDlist parameter (%s:%d).",__FILE__,__LINE__); + return; + } + + if (where == PS_DLIST_CURRENT) { + return; + } + + if (lockList) { + pthread_mutex_lock(&list->lock) + ; // don't want the list changing on us while we move about + } + + if (where >= list->size) { + psError(__func__,"Tried to access an element beyond list end. " + "Moved to last element of list instead."); + where = list->size-1; + + switch (where) { + case PS_DLIST_HEAD: + list->iter = ITER_INIT_HEAD; + break; + + case PS_DLIST_TAIL: + list->iter = ITER_INIT_TAIL; + break; + + case PS_DLIST_PREVIOUS: + cursor = dlistGetIterator(list); + position = dlistGetIteratorIndex(list); + + if (cursor == NULL) { // list empty? + ((psDlist *)list)->iter = ITER_INIT_HEAD; + } else { + if (cursor->prev != NULL) { // don't go past head + list->iter = cursor->prev; + list->iterIndex = position-1; + break; + } + } + + case PS_DLIST_NEXT: + cursor = dlistGetIterator(list); + position = dlistGetIteratorIndex(list); + + if (cursor == NULL) { // list empty? + ((psDlist *)list)->iter = ITER_INIT_HEAD; + } else { + if (cursor->next != NULL) { // don't go pase tail + list->iter = cursor->next; + list->iterIndex = position+1; + break; + } + } + + case PS_DLIST_UNKNOWN: + psError(__func__,"Can't move to the PS_DLIST_UNKNOWN position. Not moving the iterator position."); + break; + case PS_DLIST_CURRENT: + break; + + default: + if (where < PS_DLIST_HEAD) { // bascially same as PS_DLIST_UNKNOWN above + psError(__func__,"Can't move to an unknown position. Not moving the iterator position."); + break; + } else { + int position = dlistGetIteratorIndex(list); + + if (where < position) { + int diff = position-where; + for (int count=0;count < diff; count++) { + dlistSetIterator(list,PS_DLIST_PREVIOUS,false); + } + } else { + int diff = where-position; + for (int count=0;count < diff; count++) { + dlistSetIterator(list,PS_DLIST_NEXT,false); + } + } + } + break; + } + + if (lockList) { + pthread_mutex_unlock(&list->lock) + ; + } + } +} + +psDlistElem* dlistGetIterator(psDlist* list) +{ + if (list->iter == ITER_INIT_HEAD) { + return list->head; + } else if (list->iter == ITER_INIT_TAIL) { + return list->tail; + } else { + return list->iter; + } +} + +int dlistGetIteratorIndex(psDlist* list) +{ + if (list->iter == ITER_INIT_HEAD) { + return 0; + } else if (list->iter == ITER_INIT_TAIL) { + return list->size-1; + } else { + return list->iterIndex; + } +} + +void* psDlistGet(psDlist* list,int which) +{ + psDlistElem* element; + + psDlistSetIterator(list,which); + element = dlistGetIterator(list); + + if (element == NULL) { + return NULL; + } else { + return element->data; + } +} +/* + * and now return the previous/next element of the list + */ +void *psDlistGetNext(psDlist *list) +{ + return psDlistGet(list, PS_DLIST_NEXT); +} + +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 + */ +psVoidPtrArray *psDlistToArray(psDlist *restrict dlist) +{ + if (dlist == NULL) { + return NULL; + } + + psVoidPtrArray *restrict arr = psVoidPtrArrayAlloc(dlist->size, dlist->size); + + psDlistElem *ptr = dlist->head; + for (int i = 0, n = dlist->size; i < n; i++) { + arr->arr[i] = ptr->data; + + ptr->data = NULL; + ptr = ptr->next; + } + + psDlistFree(dlist, NULL); + + return arr; +} + +psDlist *psArrayToDlist(psVoidPtrArray *arr) +{ + psDlist *list = psDlistAlloc(NULL); // list of elements + + for (int i = 0, n = arr->size; i < n; i++) { + psDlistAppend(list, + psMemDecrRefCounter(arr->arr[i])); // it's already Incr + arr->arr[i] = NULL; + } + + psVoidPtrArrayFree(arr, NULL); + + return list; +} + +#endif Index: /trunk/psLib/src/collections/psDlist.h =================================================================== --- /trunk/psLib/src/collections/psDlist.h (revision 874) +++ /trunk/psLib/src/collections/psDlist.h (revision 874) @@ -0,0 +1,132 @@ +#if !defined(PS_DLIST_H) +#define PS_DLIST_H + +/** @file psDlist.h + * @brief Support for doubly linked lists + * @ingroup DataContainers + * + * @author Robert Lupton, Princeton University + * @author Robert Daniel DeSonia, MHPCC + * + * @version $Revision: 1.1 $ $Name: not supported by cvs2svn $ + * @date $Date: 2004-06-04 23:44:36 $ + * + * Copyright 2004 Maui High Performance Computing Center, University of Hawaii + */ + +#include // we need a mutex to make this stuff thread safe. + +/** Special values of index into list + * + * This list of possible list position values should be contiguous non-positive values ending with + * PS_DLIST_UNKNOWN. Any value less-than-or-equal-to PS_DLIST_UNKNOWN is considered a undefined position. + * + */ +enum { + PS_DLIST_HEAD = 0, ///< at head + PS_DLIST_TAIL = -1, ///< at tail + PS_DLIST_PREVIOUS = -2, ///< previous element + PS_DLIST_CURRENT = -3, ///< current element + PS_DLIST_NEXT = -4, ///< next element + PS_DLIST_UNKNOWN = -5 ///< unknown position (should be last in enum list) +}; + +/** 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 */ +typedef struct +{ + unsigned int size; ///< 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 + unsigned int iterIndex; ///< the numeric position of the iteration cursor in the list + pthread_mutex_t lock; ///< mutex to lock a node during changes +} +psDlist; + +/** @addtogroup DataContainers General Data Container Utilities + * @{ + */ + +/** Constructor */ +psDlist *psDlistAlloc( + void *data ///< initial data item; may be NULL +) +; + +/** Destructor */ +void psDlistFree( + psDlist* restrict list, ///< list to destroy + psFreeFcn elemFree ///< destructor for data on list +); + +/** Add to list */ +psDlist* psDlistAdd( + psDlist* restrict 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* restrict list, ///< list to append to (may be NULL) + void *data ///< data item to add +); + +/** Remove from a list */ +void* psDlistRemove( + psDlist* restrict 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( + psDlist* restrict 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* restrict 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* restrict list ///< list to retrieve element from +); + +/** Get current element at iter */ +void* psDlistGetCurrent( + psDlist* restrict list ///< list to retrieve element from +); + +/** Get prev element relative to iter */ +void* psDlistGetPrevious( + psDlist* restrict list ///< list to retrieve element from +); + +/** Convert doubly-linked list to an array */ +#if 0 +psVoidPtrArray *psDlistToArray( + psDlist *dlist ///< List to convert +); + +/** Convert array to a doubly-linked list */ +psDlist *psArrayToDlist( + psVoidPtrArray *arr ///< Array to convert +); +#endif + +/// @} End of DataGroup Functions + +#endif Index: /trunk/psLib/src/pslib.h =================================================================== --- /trunk/psLib/src/pslib.h (revision 873) +++ /trunk/psLib/src/pslib.h (revision 874) @@ -8,6 +8,6 @@ * @author Eric Van Alst, MHPCC * - * @version $Revision: 1.4 $ $Name: not supported by cvs2svn $ - * @date $Date: 2004-06-04 19:36:44 $ + * @version $Revision: 1.5 $ $Name: not supported by cvs2svn $ + * @date $Date: 2004-06-04 23:45:22 $ * * Copyright 2004 Maui High Performance Computing Center, University of Hawaii @@ -36,4 +36,5 @@ #include "psSort.h" #include "psHash.h" +#include "psDlist.h" // Data Manipulation