Index: /trunk/psLib/src/collections/Makefile =================================================================== --- /trunk/psLib/src/collections/Makefile (revision 918) +++ /trunk/psLib/src/collections/Makefile (revision 919) @@ -3,6 +3,6 @@ ## Makefile: collections ## -## $Revision: 1.18 $ $Name: not supported by cvs2svn $ -## $Date: 2004-06-04 23:44:36 $ +## $Revision: 1.19 $ $Name: not supported by cvs2svn $ +## $Date: 2004-06-08 19:08:40 $ ## ## Copyright 2004 Maui High Performance Computing Center, University of Hawaii @@ -34,5 +34,5 @@ psSort.o \ psImage.o \ - psDlist.o + psList.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 918) +++ (revision ) @@ -1,468 +1,0 @@ -/** @file psDlist.c - * @brief Support for doubly linked lists - * @ingroup DataContainers - * - * @author Robert Lupton, Princeton University - * @author Robert Daniel DeSonia, MHPCC - * - * @version $Revision: 1.4 $ $Name: not supported by cvs2svn $ - * @date $Date: 2004-06-08 02:39:42 $ - * - * 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" -#include "psLogMsg.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(); - int cursorIndex = 0; - - if (list == NULL) { - return NULL; - } - - if (data == NULL) { - return list; - } - - pthread_mutex_lock(&list->lock) - ; - - if (where <= PS_DLIST_UNKNOWN) { - /// XXX What is the better way to communicate this failure to the caller? - psLogMsg(__func__,PS_LOG_WARN, - "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) { - psLogMsg(__func__,PS_LOG_WARN, - "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); - cursorIndex = dlistGetIteratorIndex(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; - list->iterIndex = cursorIndex; - } - - 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 - int cursorIndex = 0; - - 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); - cursorIndex = dlistGetIteratorIndex(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; - list->iterIndex = cursorIndex; - } - - 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 >= (int)list->size) { - list->iter = NULL; - return; - } - - 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->iter = cursor->prev; - list->iterIndex = position-1; - } - break; - - case PS_DLIST_NEXT: - cursor = dlistGetIterator(list); - position = dlistGetIteratorIndex(list); - - if (cursor != NULL) { - list->iter = cursor->next; - list->iterIndex = position+1; - } - 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."); - } else { - cursor = dlistGetIterator(list); - if (cursor == NULL) { // reset the iterator if it is invalid - list->iter = ITER_INIT_HEAD; - list->iterIndex = 0; - } - - 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 == NULL) { - return NULL; - } - - 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); -} - -/* - * Convert a psDlist to/from a psVoidPtrArray - */ -psVector* psDlistToVector(psDlist* restrict dlist) -{ - psDlistElem* ptr; - unsigned int n; - psVector* restrict arr; - - if (dlist == NULL) { - return NULL; - } - - if (dlist->size > 0) { - arr = psVectorAlloc(dlist->size, PS_TYPE_PTR); - } else { - arr = psVectorAlloc(1, PS_TYPE_PTR); - } - - arr->n = dlist->size; - - - ptr = dlist->head; - n = dlist->size; - for (int i = 0; i < n; i++) { - arr->data.PTR[i] = psMemIncrRefCounter(ptr->data); - ptr = ptr->next; - } - - return arr; -} - -psDlist* psVectorToDlist(psVector* arr) -{ - unsigned int n; - psDlist* list; // list of elements - - if (arr == NULL) { - return NULL; - } - - if (arr->type.type != PS_TYPE_PTR) { - psError(__func__,"Can not convert a non pointer-vector to a linked list."); - return NULL; - } - - list = psDlistAlloc(NULL); - n = arr->n; - for (int i = 0; i < n; i++) { - psDlistAppend(list,arr->data.PTR[i]); - } - - return list; -} Index: unk/psLib/src/collections/psDlist.h =================================================================== --- /trunk/psLib/src/collections/psDlist.h (revision 918) +++ (revision ) @@ -1,133 +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.3 $ $Name: not supported by cvs2svn $ - * @date $Date: 2004-06-08 02:18:15 $ - * - * Copyright 2004 Maui High Performance Computing Center, University of Hawaii - */ - -#include // we need a mutex to make this stuff thread safe. - -#include "psVector.h" - -/** 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 -) -; - -#include "psMemory.h" -/** 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 */ -psVector* psDlistToVector( - psDlist *dlist ///< List to convert -); - -/** Convert array to a doubly-linked list */ -psDlist* psVectorToDlist( - psVector* arr ///< vector to convert -); - -/// @} End of DataGroup Functions - -#endif Index: /trunk/psLib/src/collections/psList.c =================================================================== --- /trunk/psLib/src/collections/psList.c (revision 919) +++ /trunk/psLib/src/collections/psList.c (revision 919) @@ -0,0 +1,468 @@ +/** @file psList.c + * @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-08 19:08:40 $ + * + * 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 "psList.h" +#include "psTrace.h" +#include "psLogMsg.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. +psListElem* listGetIterator(psList* list); +int listGetIteratorIndex(psList* list); +void listSetIterator(psList *list, int where, bool lockList); + + + +static psListElem *listElemAlloc(void) +{ + return(psAlloc(sizeof(psListElem))); +} + +static void listElemFree(psListElem *elem) +{ + psFree(elem); +} + +psList *psListAlloc(void *data) +{ + psList *list = psAlloc(sizeof(psList)); + + list->size = 0; + list->head = list->tail = NULL; + list->iter = ITER_INIT_HEAD; + list->iterIndex = PS_LIST_HEAD; + pthread_mutex_init(&(list->lock),NULL) + ; + + if (data != NULL) { + psListAdd(list, data, PS_LIST_TAIL); + } + + return list; +} + +void psListFree(psList *list, psFreeFcn elemFree) +{ + if (list == NULL) { + return; + } + + pthread_mutex_lock(&list->lock) + ; + + for(psListElem *ptr = list->head; ptr != NULL; ) { + psListElem *next = ptr->next; + + p_psCustomFree(elemFree, psMemDecrRefCounter(ptr->data)); + listElemFree(ptr); + + ptr = next; + } + + pthread_mutex_unlock(&list->lock) + ; + + pthread_mutex_destroy(&list->lock) + ; + + psFree(list); +} + +psList* psListAdd(psList *list, void *data, int where) +{ + psListElem* position; + psListElem* elem = listElemAlloc(); + int cursorIndex = 0; + + if (list == NULL) { + return NULL; + } + + if (data == NULL) { + return list; + } + + pthread_mutex_lock(&list->lock) + ; + + if (where <= PS_LIST_UNKNOWN) { + /// XXX What is the better way to communicate this failure to the caller? + psLogMsg(__func__,PS_LOG_WARN, + "The given insert location (%i) for psListAdd is invalid. Adding to head instead.", + where); + where = PS_LIST_HEAD; // given I can't tell caller about this, should just add it somewhere??? + } + + if (where > 0 && where > list->size) { + psLogMsg(__func__,PS_LOG_WARN, + "Invalid index %d (only %d elements in psList); assuming tail.", + where, list->size); + where = PS_LIST_TAIL; + } + + if (where == PS_LIST_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 + listSetIterator(list, where, false); + position = listGetIterator(list); + cursorIndex = listGetIteratorIndex(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; + list->iterIndex = cursorIndex; + } + + elem->data = psMemIncrRefCounter(data); + + pthread_mutex_unlock(&list->lock) + ; + + return list; +} + +/*****************************************************************************/ + +psList *psListAppend(psList *list, void *data) +{ + return psListAdd(list, data, PS_LIST_TAIL); +} + +/*****************************************************************************/ +/* + * Remove an element from a list + */ +void *psListRemove(psList *list, void *data, int which) +{ + psListElem *elem = NULL; // element to remove + int cursorIndex = 0; + + 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_LIST_UNKNOWN) { + // search list for the data item. + + int i = 0; // index + for (psListElem *ptr = list->head; ptr != NULL; ptr = ptr->next) { + if (ptr->data == data) { + which = i; + break; + } + i++; + } + + if (which == PS_LIST_UNKNOWN) { + psError(__func__, "Failed to find 0x%x on psList 0x%x in %s.", data, list,__func__); + return NULL; + } + } + + // position the list's cursor to the desired location + listSetIterator(list,which,false); + elem = listGetIterator(list); + cursorIndex = listGetIteratorIndex(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; + list->iterIndex = cursorIndex; + } + + pthread_mutex_unlock(&list->lock) + ; + + /* + * OK, delete list element and return the data + */ + data = elem->data; + listElemFree(elem); + return psMemDecrRefCounter(data); +} + +void psListSetIterator(psList *list, int where) +{ + listSetIterator(list,where,true); +} + +void listSetIterator(psList* list, int where, bool lockList) +{ + psListElem* cursor; + int position; + + if (list == NULL) { + psError(__func__,"Unexpected null pointer for psList parameter (%s:%d).",__FILE__,__LINE__); + return; + } + + if (where == PS_LIST_CURRENT) { + return; + } + + if (lockList) { + pthread_mutex_lock(&list->lock) + ; + // don't want the list changing on us while we move about + } + + if (where >= (int)list->size) { + list->iter = NULL; + return; + } + + switch (where) { + case PS_LIST_HEAD: + list->iter = ITER_INIT_HEAD; + break; + + case PS_LIST_TAIL: + list->iter = ITER_INIT_TAIL; + break; + + case PS_LIST_PREVIOUS: + cursor = listGetIterator(list); + position = listGetIteratorIndex(list); + + if (cursor != NULL) { + list->iter = cursor->prev; + list->iterIndex = position-1; + } + break; + + case PS_LIST_NEXT: + cursor = listGetIterator(list); + position = listGetIteratorIndex(list); + + if (cursor != NULL) { + list->iter = cursor->next; + list->iterIndex = position+1; + } + break; + + case PS_LIST_CURRENT: + break; + + default: + if (where <= PS_LIST_HEAD) { // bascially same as PS_LIST_UNKNOWN above + psError(__func__,"Can't move to an unknown position. Not moving the iterator position."); + } else { + cursor = listGetIterator(list); + if (cursor == NULL) { // reset the iterator if it is invalid + list->iter = ITER_INIT_HEAD; + list->iterIndex = 0; + } + + int position = listGetIteratorIndex(list); + + if (where < position) { + int diff = position-where; + for (int count=0;count < diff; count++) { + listSetIterator(list,PS_LIST_PREVIOUS,false); + } + } else { + int diff = where-position; + for (int count=0;count < diff; count++) { + listSetIterator(list,PS_LIST_NEXT,false); + } + } + } + break; + } + + if (lockList) { + pthread_mutex_unlock(&list->lock) + ; + } +} + +psListElem* listGetIterator(psList* list) +{ + if (list == NULL) { + return NULL; + } + + if (list->iter == ITER_INIT_HEAD) { + return list->head; + } else if (list->iter == ITER_INIT_TAIL) { + return list->tail; + } else { + return list->iter; + } +} + +int listGetIteratorIndex(psList* 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* psListGet(psList* list,int which) +{ + psListElem* element; + + psListSetIterator(list,which); + element = listGetIterator(list); + + if (element == NULL) { + return NULL; + } else { + return element->data; + } +} +/* + * and now return the previous/next element of the list + */ +void *psListGetNext(psList *list) +{ + return psListGet(list, PS_LIST_NEXT); +} + +void *psListGetPrevious(psList *list) +{ + return psListGet(list, PS_LIST_PREVIOUS); +} + +void *psListGetCurrent(psList *list) +{ + return psListGet(list, PS_LIST_CURRENT); +} + +/* + * Convert a psList to/from a psVoidPtrArray + */ +psVector* psListToVector(psList* restrict list) +{ + psListElem* ptr; + unsigned int n; + psVector* restrict arr; + + if (list == NULL) { + return NULL; + } + + if (list->size > 0) { + arr = psVectorAlloc(list->size, PS_TYPE_PTR); + } else { + arr = psVectorAlloc(1, PS_TYPE_PTR); + } + + arr->n = list->size; + + + ptr = list->head; + n = list->size; + for (int i = 0; i < n; i++) { + arr->data.PTR[i] = psMemIncrRefCounter(ptr->data); + ptr = ptr->next; + } + + return arr; +} + +psList* psVectorToDlist(psVector* arr) +{ + unsigned int n; + psList* list; // list of elements + + if (arr == NULL) { + return NULL; + } + + if (arr->type.type != PS_TYPE_PTR) { + psError(__func__,"Can not convert a non pointer-vector to a linked list."); + return NULL; + } + + list = psListAlloc(NULL); + n = arr->n; + for (int i = 0; i < n; i++) { + psListAppend(list,arr->data.PTR[i]); + } + + return list; +} Index: /trunk/psLib/src/collections/psList.h =================================================================== --- /trunk/psLib/src/collections/psList.h (revision 919) +++ /trunk/psLib/src/collections/psList.h (revision 919) @@ -0,0 +1,133 @@ +#if !defined(PS_LIST_H) +#define PS_LIST_H + +/** @file psList.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-08 19:08:40 $ + * + * Copyright 2004 Maui High Performance Computing Center, University of Hawaii + */ + +#include // we need a mutex to make this stuff thread safe. + +#include "psVector.h" + +/** Special values of index into list + * + * This list of possible list position values should be contiguous non-positive values ending with + * PS_LIST_UNKNOWN. Any value less-than-or-equal-to PS_LIST_UNKNOWN is considered a undefined position. + * + */ +enum { + PS_LIST_HEAD = 0, ///< at head + PS_LIST_TAIL = -1, ///< at tail + PS_LIST_PREVIOUS = -2, ///< previous element + PS_LIST_CURRENT = -3, ///< current element + PS_LIST_NEXT = -4, ///< next element + PS_LIST_UNKNOWN = -5 ///< unknown position (should be last in enum list) +}; + +/** Doubly-linked list element */ +typedef struct psListElem +{ + struct psListElem *prev; ///< previous link in list + struct psListElem *next; ///< next link in list + void *data; ///< real data item +} +psListElem; + +/** Doubly-linked list */ +typedef struct +{ + unsigned int size; ///< number of elements on list + 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 + pthread_mutex_t lock; ///< mutex to lock a node during changes +} +psList; + +/** @addtogroup DataContainers General Data Container Utilities + * @{ + */ + +/** Constructor */ +psList *psListAlloc( + void *data ///< initial data item; may be NULL +) +; + +#include "psMemory.h" +/** Destructor */ +void psListFree( + psList* restrict list, ///< list to destroy + psFreeFcn elemFree ///< destructor for data on list +); + +/** Add to list */ +psList* psListAdd( + psList* restrict list, ///< list to add to (may be NULL) + void* data, ///< data item to add + int where ///< index, PS_LIST_HEAD, or PS_LIST_TAIL +); + +/** Append to a list */ +psList* psListAppend( + psList* restrict list, ///< list to append to (may be NULL) + void *data ///< data item to add +); + +/** Remove from a list */ +void* psListRemove( + psList* restrict list, ///< list to remove element from + void *data, ///< data item to remove + int which ///< index of item, or PS_LIST_UNKNOWN, PS_LIST_NEXT, PS_LIST_PREV +); + +/** Retrieve from a list */ +void* psListGet( + psList* restrict list, ///< list to retrieve element from + int which ///< index of item, or PS_LIST_NEXT, PS_LIST_PREV, PS_LIST_UNKNOWN +); + +/** Set the iterator */ +void psListSetIterator( + psList* restrict list, ///< list to retrieve element from + int where ///< index, PS_LIST_HEAD, or PS_LIST_TAIL +); + +/** Get next element relative to iter */ +void* psListGetNext( + psList* restrict list ///< list to retrieve element from +); + +/** Get current element at iter */ +void* psListGetCurrent( + psList* restrict list ///< list to retrieve element from +); + +/** Get prev element relative to iter */ +void* psListGetPrevious( + psList* restrict list ///< list to retrieve element from +); + +/** Convert doubly-linked list to an array */ +psVector* psListToVector( + psList *dlist ///< List to convert +); + +/** Convert array to a doubly-linked list */ +psList* psVectorToDlist( + psVector* arr ///< vector to convert +); + +/// @} End of DataGroup Functions + +#endif Index: /trunk/psLib/src/pslib.h =================================================================== --- /trunk/psLib/src/pslib.h (revision 918) +++ /trunk/psLib/src/pslib.h (revision 919) @@ -8,6 +8,6 @@ * @author Eric Van Alst, MHPCC * - * @version $Revision: 1.5 $ $Name: not supported by cvs2svn $ - * @date $Date: 2004-06-04 23:45:22 $ + * @version $Revision: 1.6 $ $Name: not supported by cvs2svn $ + * @date $Date: 2004-06-08 19:08:40 $ * * Copyright 2004 Maui High Performance Computing Center, University of Hawaii @@ -36,5 +36,5 @@ #include "psSort.h" #include "psHash.h" -#include "psDlist.h" +#include "psList.h" // Data Manipulation Index: /trunk/psLib/src/sysUtils/psHash.c =================================================================== --- /trunk/psLib/src/sysUtils/psHash.c (revision 918) +++ /trunk/psLib/src/sysUtils/psHash.c (revision 919) @@ -10,6 +10,6 @@ * @author George Gusciora, MHPCC * - * @version $Revision: 1.6 $ $Name: not supported by cvs2svn $ - * @date $Date: 2004-06-07 00:32:53 $ + * @version $Revision: 1.7 $ $Name: not supported by cvs2svn $ + * @date $Date: 2004-06-08 19:08:40 $ * * Copyright 2004 Maui High Performance Computing Center, University of Hawaii @@ -25,8 +25,8 @@ #include "psAbort.h" -psDlist *psHashKeyList(psHash *table) +psList *psHashKeyList(psHash *table) { int i = 0; - psDlist *myLinkList = NULL; + psList *myLinkList = NULL; if (table == NULL) { @@ -34,9 +34,9 @@ } - myLinkList = psDlistAlloc(NULL); + myLinkList = psListAlloc(NULL); for (i=0;inbucket;i++) { if (table->buckets[i] != NULL) { - psDlistAdd(myLinkList, (table->buckets[i])->key, PS_DLIST_HEAD); + psListAdd(myLinkList, (table->buckets[i])->key, PS_LIST_HEAD); } } Index: /trunk/psLib/src/sysUtils/psHash.h =================================================================== --- /trunk/psLib/src/sysUtils/psHash.h (revision 918) +++ /trunk/psLib/src/sysUtils/psHash.h (revision 919) @@ -10,6 +10,6 @@ * @author George Gusciora, MHPCC * - * @version $Revision: 1.7 $ $Name: not supported by cvs2svn $ - * @date $Date: 2004-06-07 00:32:53 $ + * @version $Revision: 1.8 $ $Name: not supported by cvs2svn $ + * @date $Date: 2004-06-08 19:08:40 $ * * Copyright 2004 Maui High Performance Computing Center, University of Hawaii @@ -23,5 +23,5 @@ * \ingroup DataGroup */ -#include "psDlist.h" +#include "psList.h" @@ -78,5 +78,5 @@ /// List all keys in table. -psDlist *psHashKeyList(psHash *table); +psList *psHashKeyList(psHash *table); /* \} */ // End of DataGroup Functions Index: /trunk/psLib/src/types/psList.c =================================================================== --- /trunk/psLib/src/types/psList.c (revision 919) +++ /trunk/psLib/src/types/psList.c (revision 919) @@ -0,0 +1,468 @@ +/** @file psList.c + * @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-08 19:08:40 $ + * + * 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 "psList.h" +#include "psTrace.h" +#include "psLogMsg.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. +psListElem* listGetIterator(psList* list); +int listGetIteratorIndex(psList* list); +void listSetIterator(psList *list, int where, bool lockList); + + + +static psListElem *listElemAlloc(void) +{ + return(psAlloc(sizeof(psListElem))); +} + +static void listElemFree(psListElem *elem) +{ + psFree(elem); +} + +psList *psListAlloc(void *data) +{ + psList *list = psAlloc(sizeof(psList)); + + list->size = 0; + list->head = list->tail = NULL; + list->iter = ITER_INIT_HEAD; + list->iterIndex = PS_LIST_HEAD; + pthread_mutex_init(&(list->lock),NULL) + ; + + if (data != NULL) { + psListAdd(list, data, PS_LIST_TAIL); + } + + return list; +} + +void psListFree(psList *list, psFreeFcn elemFree) +{ + if (list == NULL) { + return; + } + + pthread_mutex_lock(&list->lock) + ; + + for(psListElem *ptr = list->head; ptr != NULL; ) { + psListElem *next = ptr->next; + + p_psCustomFree(elemFree, psMemDecrRefCounter(ptr->data)); + listElemFree(ptr); + + ptr = next; + } + + pthread_mutex_unlock(&list->lock) + ; + + pthread_mutex_destroy(&list->lock) + ; + + psFree(list); +} + +psList* psListAdd(psList *list, void *data, int where) +{ + psListElem* position; + psListElem* elem = listElemAlloc(); + int cursorIndex = 0; + + if (list == NULL) { + return NULL; + } + + if (data == NULL) { + return list; + } + + pthread_mutex_lock(&list->lock) + ; + + if (where <= PS_LIST_UNKNOWN) { + /// XXX What is the better way to communicate this failure to the caller? + psLogMsg(__func__,PS_LOG_WARN, + "The given insert location (%i) for psListAdd is invalid. Adding to head instead.", + where); + where = PS_LIST_HEAD; // given I can't tell caller about this, should just add it somewhere??? + } + + if (where > 0 && where > list->size) { + psLogMsg(__func__,PS_LOG_WARN, + "Invalid index %d (only %d elements in psList); assuming tail.", + where, list->size); + where = PS_LIST_TAIL; + } + + if (where == PS_LIST_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 + listSetIterator(list, where, false); + position = listGetIterator(list); + cursorIndex = listGetIteratorIndex(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; + list->iterIndex = cursorIndex; + } + + elem->data = psMemIncrRefCounter(data); + + pthread_mutex_unlock(&list->lock) + ; + + return list; +} + +/*****************************************************************************/ + +psList *psListAppend(psList *list, void *data) +{ + return psListAdd(list, data, PS_LIST_TAIL); +} + +/*****************************************************************************/ +/* + * Remove an element from a list + */ +void *psListRemove(psList *list, void *data, int which) +{ + psListElem *elem = NULL; // element to remove + int cursorIndex = 0; + + 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_LIST_UNKNOWN) { + // search list for the data item. + + int i = 0; // index + for (psListElem *ptr = list->head; ptr != NULL; ptr = ptr->next) { + if (ptr->data == data) { + which = i; + break; + } + i++; + } + + if (which == PS_LIST_UNKNOWN) { + psError(__func__, "Failed to find 0x%x on psList 0x%x in %s.", data, list,__func__); + return NULL; + } + } + + // position the list's cursor to the desired location + listSetIterator(list,which,false); + elem = listGetIterator(list); + cursorIndex = listGetIteratorIndex(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; + list->iterIndex = cursorIndex; + } + + pthread_mutex_unlock(&list->lock) + ; + + /* + * OK, delete list element and return the data + */ + data = elem->data; + listElemFree(elem); + return psMemDecrRefCounter(data); +} + +void psListSetIterator(psList *list, int where) +{ + listSetIterator(list,where,true); +} + +void listSetIterator(psList* list, int where, bool lockList) +{ + psListElem* cursor; + int position; + + if (list == NULL) { + psError(__func__,"Unexpected null pointer for psList parameter (%s:%d).",__FILE__,__LINE__); + return; + } + + if (where == PS_LIST_CURRENT) { + return; + } + + if (lockList) { + pthread_mutex_lock(&list->lock) + ; + // don't want the list changing on us while we move about + } + + if (where >= (int)list->size) { + list->iter = NULL; + return; + } + + switch (where) { + case PS_LIST_HEAD: + list->iter = ITER_INIT_HEAD; + break; + + case PS_LIST_TAIL: + list->iter = ITER_INIT_TAIL; + break; + + case PS_LIST_PREVIOUS: + cursor = listGetIterator(list); + position = listGetIteratorIndex(list); + + if (cursor != NULL) { + list->iter = cursor->prev; + list->iterIndex = position-1; + } + break; + + case PS_LIST_NEXT: + cursor = listGetIterator(list); + position = listGetIteratorIndex(list); + + if (cursor != NULL) { + list->iter = cursor->next; + list->iterIndex = position+1; + } + break; + + case PS_LIST_CURRENT: + break; + + default: + if (where <= PS_LIST_HEAD) { // bascially same as PS_LIST_UNKNOWN above + psError(__func__,"Can't move to an unknown position. Not moving the iterator position."); + } else { + cursor = listGetIterator(list); + if (cursor == NULL) { // reset the iterator if it is invalid + list->iter = ITER_INIT_HEAD; + list->iterIndex = 0; + } + + int position = listGetIteratorIndex(list); + + if (where < position) { + int diff = position-where; + for (int count=0;count < diff; count++) { + listSetIterator(list,PS_LIST_PREVIOUS,false); + } + } else { + int diff = where-position; + for (int count=0;count < diff; count++) { + listSetIterator(list,PS_LIST_NEXT,false); + } + } + } + break; + } + + if (lockList) { + pthread_mutex_unlock(&list->lock) + ; + } +} + +psListElem* listGetIterator(psList* list) +{ + if (list == NULL) { + return NULL; + } + + if (list->iter == ITER_INIT_HEAD) { + return list->head; + } else if (list->iter == ITER_INIT_TAIL) { + return list->tail; + } else { + return list->iter; + } +} + +int listGetIteratorIndex(psList* 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* psListGet(psList* list,int which) +{ + psListElem* element; + + psListSetIterator(list,which); + element = listGetIterator(list); + + if (element == NULL) { + return NULL; + } else { + return element->data; + } +} +/* + * and now return the previous/next element of the list + */ +void *psListGetNext(psList *list) +{ + return psListGet(list, PS_LIST_NEXT); +} + +void *psListGetPrevious(psList *list) +{ + return psListGet(list, PS_LIST_PREVIOUS); +} + +void *psListGetCurrent(psList *list) +{ + return psListGet(list, PS_LIST_CURRENT); +} + +/* + * Convert a psList to/from a psVoidPtrArray + */ +psVector* psListToVector(psList* restrict list) +{ + psListElem* ptr; + unsigned int n; + psVector* restrict arr; + + if (list == NULL) { + return NULL; + } + + if (list->size > 0) { + arr = psVectorAlloc(list->size, PS_TYPE_PTR); + } else { + arr = psVectorAlloc(1, PS_TYPE_PTR); + } + + arr->n = list->size; + + + ptr = list->head; + n = list->size; + for (int i = 0; i < n; i++) { + arr->data.PTR[i] = psMemIncrRefCounter(ptr->data); + ptr = ptr->next; + } + + return arr; +} + +psList* psVectorToDlist(psVector* arr) +{ + unsigned int n; + psList* list; // list of elements + + if (arr == NULL) { + return NULL; + } + + if (arr->type.type != PS_TYPE_PTR) { + psError(__func__,"Can not convert a non pointer-vector to a linked list."); + return NULL; + } + + list = psListAlloc(NULL); + n = arr->n; + for (int i = 0; i < n; i++) { + psListAppend(list,arr->data.PTR[i]); + } + + return list; +} Index: /trunk/psLib/src/types/psList.h =================================================================== --- /trunk/psLib/src/types/psList.h (revision 919) +++ /trunk/psLib/src/types/psList.h (revision 919) @@ -0,0 +1,133 @@ +#if !defined(PS_LIST_H) +#define PS_LIST_H + +/** @file psList.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-08 19:08:40 $ + * + * Copyright 2004 Maui High Performance Computing Center, University of Hawaii + */ + +#include // we need a mutex to make this stuff thread safe. + +#include "psVector.h" + +/** Special values of index into list + * + * This list of possible list position values should be contiguous non-positive values ending with + * PS_LIST_UNKNOWN. Any value less-than-or-equal-to PS_LIST_UNKNOWN is considered a undefined position. + * + */ +enum { + PS_LIST_HEAD = 0, ///< at head + PS_LIST_TAIL = -1, ///< at tail + PS_LIST_PREVIOUS = -2, ///< previous element + PS_LIST_CURRENT = -3, ///< current element + PS_LIST_NEXT = -4, ///< next element + PS_LIST_UNKNOWN = -5 ///< unknown position (should be last in enum list) +}; + +/** Doubly-linked list element */ +typedef struct psListElem +{ + struct psListElem *prev; ///< previous link in list + struct psListElem *next; ///< next link in list + void *data; ///< real data item +} +psListElem; + +/** Doubly-linked list */ +typedef struct +{ + unsigned int size; ///< number of elements on list + 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 + pthread_mutex_t lock; ///< mutex to lock a node during changes +} +psList; + +/** @addtogroup DataContainers General Data Container Utilities + * @{ + */ + +/** Constructor */ +psList *psListAlloc( + void *data ///< initial data item; may be NULL +) +; + +#include "psMemory.h" +/** Destructor */ +void psListFree( + psList* restrict list, ///< list to destroy + psFreeFcn elemFree ///< destructor for data on list +); + +/** Add to list */ +psList* psListAdd( + psList* restrict list, ///< list to add to (may be NULL) + void* data, ///< data item to add + int where ///< index, PS_LIST_HEAD, or PS_LIST_TAIL +); + +/** Append to a list */ +psList* psListAppend( + psList* restrict list, ///< list to append to (may be NULL) + void *data ///< data item to add +); + +/** Remove from a list */ +void* psListRemove( + psList* restrict list, ///< list to remove element from + void *data, ///< data item to remove + int which ///< index of item, or PS_LIST_UNKNOWN, PS_LIST_NEXT, PS_LIST_PREV +); + +/** Retrieve from a list */ +void* psListGet( + psList* restrict list, ///< list to retrieve element from + int which ///< index of item, or PS_LIST_NEXT, PS_LIST_PREV, PS_LIST_UNKNOWN +); + +/** Set the iterator */ +void psListSetIterator( + psList* restrict list, ///< list to retrieve element from + int where ///< index, PS_LIST_HEAD, or PS_LIST_TAIL +); + +/** Get next element relative to iter */ +void* psListGetNext( + psList* restrict list ///< list to retrieve element from +); + +/** Get current element at iter */ +void* psListGetCurrent( + psList* restrict list ///< list to retrieve element from +); + +/** Get prev element relative to iter */ +void* psListGetPrevious( + psList* restrict list ///< list to retrieve element from +); + +/** Convert doubly-linked list to an array */ +psVector* psListToVector( + psList *dlist ///< List to convert +); + +/** Convert array to a doubly-linked list */ +psList* psVectorToDlist( + psVector* arr ///< vector to convert +); + +/// @} End of DataGroup Functions + +#endif