Changeset 169 for trunk/archive/pslib/src/Utils/dlist.c

Timestamp:

Mar 9, 2004, 2:53:44 PM (22 years ago)

Author:

rhl

Message:

1/ Add ability to remove by item's address to psDlistRemove()
2/ Rename New/Del to Alloc/Free
3/ Added psDlistSetIterator/psDlistGetNext/psDlistGetPrev

File:

• trunk/archive/pslib/src/Utils/dlist.c (modified) (18 diffs)

trunk/archive/pslib/src/Utils/dlist.c

@@ -7 +7 @@
 #include "psUtils.h"
 
-static psDlistElem *dlistElemNew(void)
+static psDlistElem *dlistElemAlloc(void)
 {
     return(psAlloc(sizeof(psDlistElem)));
 }
 
-static void dlistElemDel(psDlistElem *elem)
+static void dlistElemFree(psDlistElem *elem)
 {
     psFree(elem);
@@ -19 +19 @@
 /*****************************************************************************/
 
-psDlist *psDlistNew(void *data)         // initial data item; may be NULL
+psDlist *psDlistAlloc(void *data)       // initial data item; may be NULL
 {
     psDlist *list = psAlloc(sizeof(psDlist));
@@ -33 +33 @@
 }
 
-void psDlistDel(psDlist *list,          // list to destroy
-                void (*elemDel)(void *)) // destructor for data on list
+void psDlistFree(psDlist *list,         // list to destroy
+                 void (*elemFree)(void *)) // destructor for data on list
 {
     if (list == NULL) {
@@ -44 +44 @@
         psDlistElem *next = ptr->next;
 
-        if (elemDel == NULL) {
+        if (elemFree == NULL) {
             psMemDecrRefCounter(ptr->data);
         } else {
-            elemDel(psMemDecrRefCounter(ptr->data));
-        }
-        dlistElemDel(ptr);
+            elemFree(psMemDecrRefCounter(ptr->data));
+        }
+        dlistElemFree(ptr);
         
         ptr = next;
@@ -66 +66 @@
                                         // PS_DLIST_TAIL, or an integer
 {
-    psDlistElem *elem = dlistElemNew();
+    psDlistElem *elem = dlistElemAlloc();
 
     if (list == NULL) {
-        list = psDlistNew(NULL);
+        list = psDlistAlloc(NULL);
     }
 
@@ -75 +75 @@
         fprintf(stderr, "Invalid index %d (only %d elements)\n",
                 where, list->n);
-        dlistElemDel(elem);             // cleanup
+        dlistElemFree(elem);            // cleanup
         
         return list;
@@ -134 +134 @@
                                         // or PS_DLIST_TAIL
 {
+    psDlistElem *elem = NULL;           // element to remove
     assert (list != NULL);
 
@@ -139 +140 @@
         assert (which == PS_DLIST_UNKNOWN);
 
-        fprintf(stderr,"psDlistRemove does not yet support removal by data");
+        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) {
+    if (which == PS_DLIST_HEAD || which == 0) {
         if (list->head == NULL) {
             return NULL;
         } else {
-            data = list->head->data;
+            elem = list->head;
+            
             if (list->head->next != NULL) {
                 list->head->next->prev = NULL;
@@ -158 +168 @@
             }
         }
-    } else if (which == PS_DLIST_TAIL) {
+    } else if (which == PS_DLIST_TAIL || which == list->n - 1) {
         if (list->tail == NULL) {
             return NULL;
         } else {
-            data = list->tail->data;
+            elem = list->tail;
             if (list->tail->prev != NULL) {
                 list->tail->prev->next = NULL;
@@ -173 +183 @@
             }
         }
-    } else if (which != PS_DLIST_UNKNOWN) {
-        fprintf(stderr,"psDlistRemove does not yet support removal by index");
-        return 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;             
+            }
+        }
+    }
+    /*
+     * OK, delete list element and return the data
+     */
+    assert (elem != NULL);
+    data = elem->data;
+    dlistElemFree(elem);
 
     return psMemDecrRefCounter(data);
@@ -242 +272 @@
 /*****************************************************************************/
 /*
+ * 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__, "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
  */
@@ -250 +313 @@
     }
     
-    psVoidPtrArray *restrict arr = psVoidPtrArrayNew(dlist->n, dlist->n);
+    psVoidPtrArray *restrict arr = psVoidPtrArrayAlloc(dlist->n, dlist->n);
 
     psDlistElem *ptr = dlist->head;
@@ -260 +323 @@
     }
 
-    psDlistDel(dlist, NULL);
+    psDlistFree(dlist, NULL);
 
     return arr;    
@@ -267 +330 @@
 psDlist *psArrayToDlist(psVoidPtrArray *arr)
 {
-    psDlist *list = psDlistNew(NULL);   // list of elements
+    psDlist *list = psDlistAlloc(NULL); // list of elements
 
     for (int i = 0, n = arr->n; i < n; i++) {
@@ -275 +338 @@
     }
 
-    psVoidPtrArrayDel(arr, NULL);
+    psVoidPtrArrayFree(arr, NULL);
 
     return list;
@@ -284 +347 @@
 
 typedef struct { int i; } X;
-static X *xNew(int i) { X *x = psAlloc(sizeof(X)); x->i = i; return x; }
-static void xDel(X *x) { psFree(x); }
+static X *xAlloc(int i) { X *x = psAlloc(sizeof(X)); x->i = i; return x; }
+static void xFree(X *x) { psFree(x); }
 
 int main(void)
 {
-    psDlist *list = psDlistNew(NULL);   // list of metadata
-
-    psDlistAppend(list, xNew(1));
-    psDlistAppend(list, xNew(2));
-    psDlistAppend(list, xNew(3));
+    psDlist *list = psDlistAlloc(NULL); // list of metadata
+
+    psDlistAppend(list, xAlloc(1));
+    psDlistAppend(list, xAlloc(2));
+    psDlistAppend(list, xAlloc(3));
     /*
      * Print that data
@@ -334 +397 @@
     printf("\n");
 #endif
-    psVoidPtrArrayDel(arr, (void (*)(void *))xDel);
+    psVoidPtrArrayFree(arr, (void (*)(void *))xFree);
 #endif
 
@@ -349 +412 @@
      * Clean up
      */
-    psDlistDel(list, (void (*)(void *))xDel);
+    psDlistFree(list, (void (*)(void *))xFree);
     /*
      * Check for memory leaks