psList.h

Go to the documentation of this file.

/** @file psList.h
 *  @brief Support for doubly linked lists
 *
 *  @author Robert Lupton, Princeton University
 *  @author Robert Daniel DeSonia, MHPCC
 *
 *  @ingroup LinkedList
 *
 *  @version $Revision: 1.1.1.1 $ $Name:  $
 *  @date $Date: 2005/06/15 21:08:12 $
 *
 *  Copyright 2004-2005 Maui High Performance Computing Center, University of Hawaii
 */

#ifndef PS_LIST_H
#define PS_LIST_H

#include <pthread.h>                   // we need a mutex to make this stuff thread safe.

#include "psCompare.h"
#include "psArray.h"

/** @addtogroup LinkedList
 *  @{
 */

/** 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
};

/** Doubly-linked list element */
typedef struct psListElem
{
    struct psListElem* prev;           ///< previous link in list
    struct psListElem* next;           ///< next link in list
    psPtr data;                        ///< real data item
}
psListElem;

/** The psList Linked list structure.  User should not allocate this struct
 *  directly; rather the psListAlloc should be used.
 *
 *  @see psListAlloc
 */
typedef struct
{
    psU32 size;                        ///< number of elements on list
    psListElem* head;                  ///< first element on list (may be NULL)
    psListElem* tail;                  ///< last element on list (may be NULL)
    psArray* iterators;
    ///< array of all iterators associated with this list.  First iterator is
    ///< used internally to improve performance when using indexed access, all
    ///< others are user-level iterators created by psListIteratorAlloc.

    pthread_mutex_t lock;              ///< mutex to lock a node during changes
}
psList;

/** The psList iterator structure.  This should be allocated via
 *  psListIteratorAlloc and not directly.
 *
 *  The life span of a psListIterator object is ended by either a psFree
 *  of this structure OR psFree of the psList in which it operates on.
 *
 *  @see psListIteratorAlloc, psListIteratorSet, psListGetAndIncrement, psListGetAndDecrement
 */
typedef struct
{
psList* list;                      ///< List iterator to works on
psListElem* cursor;                ///< current cursor position
int index;                         ///< the index number in the list
bool offEnd;                       ///< Iterator off the end?
bool mutable;                      ///< Is it permissible to modify the list?
}
psListIterator;


/** Creates a psList linked list object.
 *
 *  @return psList* A new psList object.
 */
psList* psListAlloc(
    psPtr data
    ///< initial data item; may be NULL if no an empty psList is desired
)
;

/** Creates a psListIterator object and associates it with a psList.
 *
 *  @return psListIterator* A new psListIterator object.
 */
psListIterator* psListIteratorAlloc(
    psList* list,                      ///< the psList to iterate with
    int location,                      ///< the initial starting point.
    ///<  This can be a numeric index, PS_LIST_HEAD, or PS_LIST_TAIL.
    bool mutable                       ///< Is it permissible to modify list?
);

/** Set the iterator of the list to a given position.  If location is invalid the
 *  iterator position is not changed.
 *
 *  @return psBool        TRUE if iterator successfully set, otherwise FALSE.
 */
psBool psListIteratorSet(
    psListIterator* iterator,            ///< list iterator
    int location                         ///< index number, PS_LIST_HEAD, or PS_LIST_TAIL
);

/** Adds an element to a psList at position given.
 *
 *  @return psBool        TRUE if item was successfully added, otherwise FALSE.
 */
psBool psListAdd(
    psList* list,                      ///< list to add item to
    psS32 location,                    ///< index, PS_LIST_HEAD, PS_LIST_TAIL, or numbered location.
    psPtr data                         ///< data item to add.  If NULL, list is not modified.
);

/** Adds an data item to a psList at position just after the list position given
 *
 *  @return psBool        TRUE if item was successfully added, otherwise FALSE.
 */
psBool psListAddAfter(
    psListIterator* list,              ///< list position to add item to
    psPtr data                         ///< data item to add.  If NULL, list is not modified.
);

/** Adds an data item to a psList at position just before the list position given
 *
 *  @return psBool        TRUE if item was successfully added, otherwise FALSE.
 */
psBool psListAddBefore(
    psListIterator* list,              ///< list position to add item to
    psPtr data                         ///< data item to add.  If NULL, list is not modified.
);

/** Remove an item at the specified location from a list.
 *
 *  @return psBool        TRUE if element is successfully removed, otherwise FALSE.
 */
psBool psListRemove(
    psList* list,                      ///< list to remove element from
    psS32 location                     ///< index of item
);

/** Remove an item from a list.
 *
 *  @return psBool        TRUE if element is successfully removed, otherwise FALSE.
 */
psBool psListRemoveData(
    psList* list,                      ///< list to remove element from
    psPtr data                         ///< data item to find and remove
);

/** Retrieve an item from a list.
 *
 *  @return psPtr       the item corresponding to the location parameter.  If
 *                      location is invalid (e.g., a numbered index greater
 *                      than the list size or if the list is empty), a
 *                      NULL is returned.
 */
psPtr psListGet(
    psList* list,                      ///< list to retrieve element from
    psS32 location                     ///< index number, PS_LIST_HEAD, or PS_LIST_TAIL
);

/** Position the specified iterator to the next item in list.
 *
 *  @return psPtr       the data item at the original iterator position or NULL if the
 *                      iterator went past the end of the list.
 */
psPtr psListGetAndIncrement(
    psListIterator* iterator           ///< iterator to move
);

/** Position the specified iterator to the previous item in list.
 *
 *  @return psPtr       the data item at the original iterator position or NULL if the
 *                      iterator went past the beginning of the list.
 */
psPtr psListGetAndDecrement(
    psListIterator* iterator           ///< iterator to move
);

/** Convert a linked list to an array
 *
 *  @return psArray* A new psArray populated with elements from the list,
 *                      or NULL if the given dlist parameter is NULL.
 */
psArray* psListToArray(
    psList* dlist                      ///< List to convert
);

/** Convert array to a doubly-linked list
 *
 *  @return psList* A new psList populated with elements formt the psArray,
 *                      or NULL is the given arr parameter is NULL.
 */
psList* psArrayToList(
    psArray* arr                       ///< vector to convert
);

/** Sort a list via a comparison function.
 *
 *  The comparison function must return an integer less than, equal to, or
 *  greater than zero if the first argument is considered to be respectively
 *  less than, equal to, or greater than the second.
 *
 *  If two members compare as equal, their order in the sorted array is
 *  undefined.
 *
 *  @return psList*     Sorted list.
 */
psList* psListSort(
    psList* list,                      ///< the list to sort
    psComparePtrFcn compare            ///< the comparison function
);

/// @} End of DataGroup Functions

#endif // #ifndef PS_LIST_H

---