Changeset 454

Timestamp:

Apr 19, 2004, 11:01:12 AM (22 years ago)

Author:

desonia

Message:

from IP3

Location:

trunk/psLib/src/sysUtils

Files:

• psDList.c (modified) (1 diff)
• psDList.h (modified) (1 diff)

trunk/psLib/src/sysUtils/psDList.c

@@ +1 @@
+/*
+ * Minimal support for doubly linked lists
+ */
+#include <stdlib.h>
+#include <stdio.h>
+#include <assert.h>
+#include "psLib.h"
+
+static psDlistElem *dlistElemAlloc(void)
+{
+    return(psAlloc(sizeof(psDlistElem)));
+}
+
+static void dlistElemFree(psDlistElem *elem)
+{
+    psFree(elem);
+}
+
+/*****************************************************************************/
+
+psDlist *psDlistAlloc(void *data) // initial data item; may be NULL
+{
+    psDlist *list = psAlloc(sizeof(psDlist));
+
+    list->n = 0;
+    list->head = list->tail = NULL;
+    list->iter = NULL;
+    if (data != NULL)
+    {
+        psDlistAdd(list, data, PS_DLIST_TAIL);
+    }
+
+    return list;
+}
+
+void psDlistFree(psDlist *list,  // list to destroy
+                 void (*elemFree)(void *)) // destructor for data on list
+{
+    if (list == NULL)
+    {
+        return;
+    }
+
+    psDlistElem *ptr = list->head;
+    while (ptr != NULL)
+    {
+        psDlistElem *next = ptr->next;
+
+        if (elemFree == NULL) {
+            psMemDecrRefCounter(ptr->data);
+        } else {
+            elemFree(psMemDecrRefCounter(ptr->data));
+        }
+        dlistElemFree(ptr);
+
+        ptr = next;
+    }
+
+    psFree(list);
+}
+
+/*****************************************************************************/
+/*
+ * Add an element to a list
+ */
+psDlist *psDlistAdd(psDlist *list, // list to add to; may be NULL
+                    void *data,  // data to add
+                    int where)  // where to add data. PS_DLIST_HEAD,
+// PS_DLIST_TAIL, or an integer
+{
+    psDlistElem *elem = dlistElemAlloc();
+
+    if (list == NULL)
+    {
+        list = psDlistAlloc(NULL);
+    }
+
+    if (where > list->n)
+    {  // XXX need better diagnostic here
+        fprintf(stderr, "Invalid index %d (only %d elements)\n",
+                where, list->n);
+        dlistElemFree(elem);  // cleanup
+
+        return list;
+    }
+
+    if (where == PS_DLIST_HEAD)
+    { // easy
+        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)
+    { // also easy
+        elem->prev = list->tail;
+        elem->next = NULL;
+        elem->data = psMemIncrRefCounter(data);
+
+        if (list->tail != NULL) {
+            list->tail->next = elem;
+        }
+
+        list->tail = elem;
+        if (list->head == NULL) {
+            list->head = elem;
+        }
+        list->n++;
+    } else
+    {    // XXX
+        fprintf(stderr, "Insertion into psDlists is not yet supported\n");
+        return psDlistAdd(list, data, PS_DLIST_TAIL);
+    }
+
+    return list;
+}
+
+/*****************************************************************************/
+
+psDlist *psDlistAppend(psDlist *list, // list to add to; may be NULL
+                       void *data) // data to add at end
+{
+    return psDlistAdd(list, data, PS_DLIST_TAIL);
+}
+
+/*****************************************************************************/
+/*
+ * 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
+{
+    psDlistElem *elem = NULL;  // element to remove
+    assert (list != NULL);
+
+    if (data != NULL)
+    {
+        assert (which == PS_DLIST_UNKNOWN);
+
+        int i = 0;   // index
+        for (psDlistElem *ptr = list->head; ptr != NULL; ptr = ptr->next, i++) {
+            if (ptr->data == data) {
+                return psDlistRemove(list, NULL, i);
+            }
+        }
+
+        psTrace("utils.dlist.remove", 5, "Failed to find 0x%x on psDlist 0x%x", data, list);
+
+        return NULL;
+    }
+
+    if (which == PS_DLIST_HEAD || which == 0)
+    {
+        if (list->head == NULL) {
+            return NULL;
+        } 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__, PS_ERR_BAD_INDEX, 1, "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;
+            }
+        }
+    }
+    /*
+     * 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} initialise 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,  // list to retrieve element from
+    int which)    // index of item, or PS_DLIST_NEXT,
+// or PS_DLIST_PREV
+{
+    assert (list != NULL);
+
+    switch (which) {
+    case PS_DLIST_HEAD:  // easy
+        ((psDlist *)list)->iter = ITER_INIT_HEAD;
+        return (list->head == NULL) ? NULL : list->head->data;
+    case PS_DLIST_TAIL:  // also easy
+        ((psDlist *)list)->iter = ITER_INIT_TAIL;
+        return (list->tail == NULL) ? NULL : list->tail->data;
+    case PS_DLIST_PREV:  // 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_PREV) {
+            ((psDlist *)list)->iter = list->iter->prev;
+        } else if (which == PS_DLIST_NEXT) {
+            ((psDlist *)list)->iter = list->iter->next;
+        } else {
+            fprintf(stderr,"You cannot get here\n");
+            abort();
+        }
+
+        if (list->iter == NULL) {
+            return NULL;
+        }
+        return list->iter->data; // XXX what if data is NULL?
+
+        break;
+    default:    // XXX
+        fprintf(stderr,
+                "Retrieval from psDlists by index is not yet supported\n");
+        return NULL;
+    }
+}
+
+/*****************************************************************************/
+/*
+ * 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, // the list in question
+                        int where, // where on the list should I start?
+                        int which) // @notused@ the desired iterator
+{
+    if (where != PS_DLIST_HEAD && where != PS_DLIST_TAIL)
+    {
+        psError(__func__, PS_ERR_UNKNOWN, 1, "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, // the list in question
+                     int which)  // @notused@ the desired iterator
+{
+    return psDlistGet(list, PS_DLIST_NEXT);
+}
+
+void *psDlistGetPrev(psDlist *list, // the list in question
+                     int which)  // @notused@ the desired iterator
+{
+    return psDlistGet(list, PS_DLIST_PREV);
+}
+
+/*****************************************************************************/
+/*
+ * 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;
+}

trunk/psLib/src/sysUtils/psDList.h

@@ -1 @@
-//
-// C++ Interface: psDList
-//
-// Description:
-//
-//
-// Author: Robert DeSonia <robert.desonia@mhpcc.hpc.mil>, (C) 2004
-//
-// Copyright: See COPYING file that comes with this distribution
-//
-//
+#if !defined(PS_DLIST_H)
+#define PS_DLIST_H
+
+/** \file psDlist.h
+ *  \brief Support for doubly linked lists
+ *  \ingroup DataGroup
+ */
+
+/** 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
+{
+    int n;    ///< 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
+}
+psDlist;
+
+/** Special values of index into list */
+enum {
+    PS_DLIST_HEAD = 0,   ///< at head
+    PS_DLIST_TAIL = -1,   ///< at tail
+    PS_DLIST_UNKNOWN = -2,  ///< unknown position
+    PS_DLIST_PREV = -3,   ///< previous element
+    PS_DLIST_NEXT = -4   ///< next element
+};
+
+/** Functions **************************************************************/
+/** \addtogroup DataGroup General Data Container Utilities
+ *  \{
+ */
+
+/** Constructor */
+psDlist *psDlistAlloc(void *data) ///< initial data item; may be NULL
+;
+
+/** Destructor */
+void psDlistFree(psDlist *list,  ///< list to destroy
+                 void (*elemFree)(void *)) ///< destructor for data on list
+;
+
+/**** List maintainence functions ****/
+
+/** 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
+;
+
+/** Append to a list */
+psDlist *psDlistAppend(psDlist *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
+;
+
+/** 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
+;
+
+/** Set the iterator */
+void psDlistSetIterator(psDlist *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
+;
+
+/** Get prev element relative to iter */
+void *psDlistGetPrev(psDlist *list) ///< list to retrieve element from
+;
+
+/** Convert doubly-linked list to an array */
+psVoidPtrArray *psDlistToArray(psDlist *dlist) ///< List to convert
+;
+
+/** Convert array to a doubly-linked list */
+psDlist *psArrayToDlist(psVoidPtrArray *arr) ///< Array to convert
+;
+
+/* \} */ // End of DataGroup Functions
+
+#endif