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
 *
 *  @version $Revision: 1.39 $ $Name:  $
 *  @date $Date: 2007/01/23 22:47:23 $
 *
 *  Copyright 2004-2005 Maui High Performance Computing Center, University of Hawaii
 */

#ifndef PS_LIST_H
#define PS_LIST_H

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

/// @addtogroup DataContainer Data Containers
///  @{

/** 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
{
    long n;                            ///< 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.
    void *lock;                        ///< Optional lock for thread safety
}
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
    bool offEnd;                       ///< Iterator off the end?
    long index;                         ///< the index number in the list
    bool mutable;                      ///< Is it permissible to modify the list?
}
psListIterator;


/** Checks the type of a particular pointer.
 *
 *  Uses the appropriate deallocation function in psMemBlock to check the ptr datatype.
 *
 *  @return bool:       True if the pointer matches a psList structure, false otherwise.
 */
bool psMemCheckList(
    psPtr ptr                          ///< the pointer whose type to check
)
;

/** Creates a psList linked list object.
 *
 *  @return psList* A new psList object.
 */
psList* psListAlloc(
    psPtr data          ///< initial data item; may be NULL if 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
    long 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 bool        TRUE if iterator successfully set, otherwise FALSE.
 */
bool psListIteratorSet(
    psListIterator* iterator,          ///< list iterator
    long location                      ///< index number, PS_LIST_HEAD, or PS_LIST_TAIL
);

/** Adds an element to a psList at position given.
 *
 *  @return bool        TRUE if item was successfully added, otherwise FALSE.
 */
bool psListAdd(
    psList* list,                      ///< list to add item to
    long 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 bool        TRUE if item was successfully added, otherwise FALSE.
 */
bool psListAddAfter(
    psListIterator* iterator,          ///< list position to add item to
    psPtr data                         ///< data item to add.  If NULL, list is not modified.
);

/** Adds a data item to a psList at position just before the list position given
 *
 *  @return bool        TRUE if item was successfully added, otherwise FALSE.
 */
bool psListAddBefore(
    psListIterator* iterator,          ///< 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 bool        TRUE if element is successfully removed, otherwise FALSE.
 */
bool psListRemove(
    psList* list,                      ///< list to remove element from
    long location                      ///< index of item
);

/** Remove an item from a list.
 *
 *  @return bool        TRUE if element is successfully removed, otherwise FALSE.
 */
bool 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
    long 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(
    const psList* list                 ///< 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(
    const psArray* array               ///< 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
    psComparePtrFunc func              ///< the comparison function
);

/** Get the number of elements in use from a specified psList. (list.n)
 *
 *  @return long:       The number of elements in use.
 */
long psListLength(
    const psList *list                 ///< input psList
);

/// @} End of DataContainer Functions
#endif // #ifndef PS_LIST_H

---