Index: /trunk/psLib/src/sysUtils/Makefile =================================================================== --- /trunk/psLib/src/sysUtils/Makefile (revision 505) +++ /trunk/psLib/src/sysUtils/Makefile (revision 506) @@ -3,6 +3,6 @@ ## Makefile: sysUtils ## -## $Revision: 1.5 $ $Name: not supported by cvs2svn $ -## $Date: 2004-04-21 19:02:28 $ +## $Revision: 1.6 $ $Name: not supported by cvs2svn $ +## $Date: 2004-04-23 00:19:42 $ ## ## Copyright 2004 Maui High Performance Computing Center, University of Hawaii @@ -34,8 +34,9 @@ psError.o \ psTrace.o \ - psLogMsg.o \ - psHash.o \ + psLogMsg.o \ + psHash.o \ psAbort.o \ - psString.o + psString.o \ + psDList.o # Define PHONY target "all" which will make all the necessary items Index: /trunk/psLib/src/sysUtils/psDList.c =================================================================== --- /trunk/psLib/src/sysUtils/psDList.c (revision 505) +++ /trunk/psLib/src/sysUtils/psDList.c (revision 506) @@ -6,6 +6,6 @@ * @author Robert Daniel DeSonia, MHPCC * - * @version $Revision: 1.4 $ $Name: not supported by cvs2svn $ - * @date $Date: 2004-04-21 00:15:17 $ + * @version $Revision: 1.5 $ $Name: not supported by cvs2svn $ + * @date $Date: 2004-04-23 00:19:42 $ * * Copyright 2004 Maui High Performance Computing Center, University of Hawaii @@ -13,6 +13,8 @@ #include +#include #include -#include +#include // we need a mutex to make this stuff thread safe. + #include "psError.h" #include "psAbort.h" @@ -21,4 +23,14 @@ #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) { @@ -35,8 +47,11 @@ psDlist *list = psAlloc(sizeof(psDlist)); - list->n = 0; + list->size = 0; list->head = list->tail = NULL; - list->iter = NULL; - list->iterIndex = 0; + 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); @@ -51,4 +66,7 @@ return; } + + pthread_mutex_lock(&list->lock) + ; for(psDlistElem *ptr = list->head; ptr != NULL; ) { @@ -65,4 +83,10 @@ } + pthread_mutex_unlock(&list->lock) + ; + + pthread_mutex_destroy(&list->lock) + ; + psFree(list); } @@ -70,5 +94,6 @@ psDlist *psDlistAdd(psDlist *list, void *data, int where) { - psDlistElem *elem = dlistElemAlloc(); + psDlistElem* position; + psDlistElem* elem = dlistElemAlloc(); if (list == NULL) { @@ -76,44 +101,24 @@ } - if (where > list->n) { - psError(__FILE__, "Invalid index %d (only %d elements in psDList); assuming tail.", where, list->n); + 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_PREVIOUS) { - if (list->iter == NULL) { // if no iterator position, just insert it in the front of the list. - where = PS_DLIST_HEAD; - } else { - 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++; - } - } - - if (where == PS_DLIST_HEAD) { - elem->prev = NULL; - elem->next = list->head; - elem->data = psMemIncrRefCounter(data); - - if (list->head != NULL) { - list->head->prev = elem; - } - - list->head = elem; - if (list->tail == NULL) { - list->tail = elem; - } - list->n++; - } else if (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; - elem->data = psMemIncrRefCounter(data); if (list->tail != NULL) { @@ -121,30 +126,41 @@ } - list->tail = elem; if (list->head == NULL) { list->head = elem; } - list->n++; - } else - 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. " - "Adding to head instead.",where); - return psDlistAdd(list,data,PS_DLIST_HEAD); // should add it somewhere... - } else {} + 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; @@ -153,6 +169,5 @@ /*****************************************************************************/ -psDlist *psDlistAppend(psDlist *list, // list to add to; may be NULL - void *data) // data to add at end +psDlist *psDlistAppend(psDlist *list, void *data) { return psDlistAdd(list, data, PS_DLIST_TAIL); @@ -163,230 +178,270 @@ * Remove an element from a list */ -void *psDlistRemove(psDlist *list, // list to remove element from - void *data, // data item to remove (or NULL) - int which) // index of item, if known. -// PS_DLIST_UNKNOWN, or PS_DLIST_HEAD, -// or PS_DLIST_TAIL +void *psDlistRemove(psDlist *list, void *data, int which) { psDlistElem *elem = NULL; // element to remove - assert (list != NULL); - - if (data != NULL) - { - assert (which == PS_DLIST_UNKNOWN); + 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, i++) { + for (psDlistElem *ptr = list->head; ptr != NULL; ptr = ptr->next) { if (ptr->data == data) { - return psDlistRemove(list, NULL, i); + which = i; + break; } - } - - psTrace(__FILE__, 5, "Failed to find 0x%x on psDlist 0x%x", data, list); - + 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; } - if (which == PS_DLIST_HEAD || which == 0) - { - if (list->head == NULL) { - 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 { - elem = list->head; - - if (list->head->next != NULL) { - list->head->next->prev = NULL; - } - list->head = list->head->next; - list->n--; - - if (list->head == NULL) { - list->tail = NULL; - } - } - } else if (which == PS_DLIST_TAIL || which == list->n - 1) - { - if (list->tail == NULL) { - return NULL; - } else { - elem = list->tail; - if (list->tail->prev != NULL) { - list->tail->prev->next = NULL; - } - list->tail = list->tail->prev; - list->n--; - - if (list->tail == NULL) { - list->head = NULL; - } - } - } else if (which != PS_DLIST_UNKNOWN) - { // an index in the middle of the list - assert (which != 0 && which != list->n - 1); - - if (which < 0 || which >= list->n) { // out of bounds - psError(__func__,"Index %d is not in range [0..%d] for list 0x%x", which, list->n, - list); - return NULL; - } - - int i = 0; // index - for (psDlistElem *ptr = list->head; ptr != NULL; ptr = ptr->next, i++) { - if (i == which) { - ptr->prev->next = ptr->next; - ptr->next->prev = ptr->prev; - - elem = ptr; - } - } - } + 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 */ - assert (elem != NULL); data = elem->data; dlistElemFree(elem); - return psMemDecrRefCounter(data); } -/* - * Retrieve an element from the list, or iterate over list. - * - * If which is psDlist{Next,Prev} return the next/previous - * data and move the iteration cursor - * - * If which is psDlist{Head,Tail} initialize the iteration pointer - * and return the head/tail - * - * Otherwise, return the desired element - */ -#define ITER_INIT_HEAD ((void *)1) // next iteration should return head -#define ITER_INIT_TAIL ((void *)2) // next iteration should return tail - -void *psDlistGet(const psDlist *list, int which) -{ +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; - } - - switch (which) { - case PS_DLIST_HEAD: - ((psDlist *)list)->iter = ITER_INIT_HEAD; - return (list->head == NULL) ? NULL : list->head->data; - - case PS_DLIST_TAIL: - ((psDlist *)list)->iter = ITER_INIT_TAIL; - return (list->tail == NULL) ? NULL : list->tail->data; - - case PS_DLIST_PREVIOUS: // use iterator - case PS_DLIST_NEXT: - if (list->iter == NULL) { - return NULL; - } else if (list->iter == ITER_INIT_HEAD) { - ((psDlist *)list)->iter = list->head; - } else if (list->iter == ITER_INIT_TAIL) { - ((psDlist *)list)->iter = list->tail; - } 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 { - psAbort(__func__,"Unreachable line was reached in %s:%d?",__FILE__,__LINE__); - } - - if (list->iter == NULL) { - return NULL; - } - return list->iter->data; // XXX what if data is NULL? - - break; - 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? - } -} - -psDlistElem* dlistGetIterator(psDlist* list) -{ - - - /* - * Some wrappers for those iteration calls using psDlistGet. - * - * First a call to set the iteration pointer to the head of the list - */ - 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; - } - - psDlistGet(list, where); // initialise iterator at head/tail - } - - /* - * 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->n, dlist->n); - - psDlistElem *ptr = dlist->head; - for (int i = 0, n = dlist->n; 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->n; i < n; i++) { - psDlistAppend(list, - psMemDecrRefCounter(arr->arr[i])); // it's already Incr - arr->arr[i] = NULL; - } - - psVoidPtrArrayFree(arr, NULL); - - return list; - } - - #endif + } 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/sysUtils/psDList.h =================================================================== --- /trunk/psLib/src/sysUtils/psDList.h (revision 505) +++ /trunk/psLib/src/sysUtils/psDList.h (revision 506) @@ -9,18 +9,25 @@ * @author Robert Daniel DeSonia, MHPCC * - * @version $Revision: 1.5 $ $Name: not supported by cvs2svn $ - * @date $Date: 2004-04-21 00:15:17 $ + * @version $Revision: 1.6 $ $Name: not supported by cvs2svn $ + * @date $Date: 2004-04-23 00:19:42 $ * * Copyright 2004 Maui High Performance Computing Center, University of Hawaii */ -/** Special values of index into list */ +#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_UNKNOWN = -2, ///< unknown position - PS_DLIST_PREVIOUS = -3, ///< previous element - PS_DLIST_CURRENT = -4, ///< current element - PS_DLIST_NEXT = -5 ///< next element + 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) }; @@ -37,9 +44,10 @@ typedef struct { - int n; ///< number of elements on list + 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 - int iterIndex; + 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; @@ -51,58 +59,59 @@ /** Constructor */ psDlist *psDlistAlloc( - void *data ///< initial data item; may be NULL -); + void *data ///< initial data item; may be NULL +) +; /** Destructor */ void psDlistFree( - psDlist *list, ///< list to destroy - void (*elemFree)(void *) ///< destructor for data on list + psDlist* restrict 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* 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 *list, ///< list to append to (may be NULL) - void *data ///< data item to add +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 *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* 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( - 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( + 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 *list, ///< list to retrieve element from - int where ///< index, PS_DLIST_HEAD, or PS_DLIST_TAIL + 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 *list ///< list to retrieve element from +void* psDlistGetNext( + psDlist* restrict list ///< list to retrieve element from ); /** Get current element at iter */ -void *psDlistGetCurrent( - psDlist *list ///< list to retrieve element from +void* psDlistGetCurrent( + psDlist* restrict list ///< list to retrieve element from ); /** Get prev element relative to iter */ -void *psDlistGetPrevious( - psDlist *list ///< list to retrieve element from +void* psDlistGetPrevious( + psDlist* restrict list ///< list to retrieve element from ); @@ -110,10 +119,10 @@ #if 0 psVoidPtrArray *psDlistToArray( - psDlist *dlist ///< List to convert + psDlist *dlist ///< List to convert ); /** Convert array to a doubly-linked list */ psDlist *psArrayToDlist( - psVoidPtrArray *arr ///< Array to convert + psVoidPtrArray *arr ///< Array to convert ); #endif