utils/wvlinklist.cc

   1 /*
   2  * Worldvisions Weaver Software:
   3  *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
   4  *
   5  * Implementation of a Linked List management class, or rather, macros that
   6  * declare arbitrary linked list management classes.
   7  *
   8  * wvlinklist.h does all the real work.
   9  */
  10 #include "wvlinklist.h"
  11
  12 WvLink::WvLink(void *_data, WvLink *prev, WvLink *&tail, bool _autofree,
  13                const char *_id)
  14 {
  15     data = _data;
  16     next = prev->next;
  17     if (!next) tail = this;
  18     prev->next = this;
  19     autofree = _autofree;
  20     id = _id;
  21 }
  22
  23
  24 size_t WvListBase::count() const
  25 {
  26     WvLink *l;
  27     size_t n = 0;
  28
  29     for (l = head.next; l; l = l->next)
  30         n++;
  31     return n;
  32 }
  33
  34
  35 void WvListBase::reverse()
  36 {
  37     WvLink *prev, *curr, *next;
  38
  39     if (!head.next || !head.next->next)
  40         return;
  41
  42     prev = head.next;
  43     curr = prev->next;
  44
  45     do {
  46         next = curr->next;
  47         curr->next = prev;
  48         prev = curr;
  49         curr = next;
  50     } while(curr);
  51
  52     tail = head.next;
  53     tail->next = NULL;
  54     head.next = prev;
  55 }
  56
  57
  58 WvLink *WvListBase::IterBase::find(const void *data)
  59 {
  60     for (rewind(); next(); )
  61         if (link->data == data)
  62             break;
  63     return link;
  64 }
  65
  66 WvLink *WvListBase::IterBase::find_next(const void *data)
  67 {
  68     if (link)
  69     {
  70         if (link->data == data)
  71             return link;
  72
  73         for (rewind(); next(); )
  74             if (link->data == data)
  75                 break;
  76     }
  77     return link;
  78 }
  79
  80
  81 #if 0
  82 static WvListBase::SorterBase::CompareFunc *actual_compare = NULL;
  83
  84 static int magic_compare(const void *_a, const void *_b)
  85 {
  86     WvLink *a = *(WvLink **)_a, *b = *(WvLink **)_b;
  87     return actual_compare(a->data, b->data);
  88 }
  89
  90 void WvListBase::SorterBase::rewind(CompareFunc *cmp)
  91 {
  92     if (array)
  93         delete array;
  94     array = lptr = NULL;
  95
  96     int n = list->count();
  97     array = new WvLink * [n+1];
  98     WvLink **aptr = array;
  99
 100     // fill the array with data pointers for sorting, so that the user doesn't
 101     // have to deal with the WvLink objects.  Put the WvLink pointers back
 102     // in after sorting.
 103     IterBase i(*list);
 104     aptr = array;
 105     for (i.rewind(); i.next(); )
 106     {
 107         *aptr = i.cur();
 108         aptr++;
 109     }
 110
 111     *aptr = NULL;
 112
 113     // sort the array.  "Very nearly re-entrant" (unless the compare function
 114     // ends up being called recursively or something really weird...)
 115     CompareFunc *old_compare = actual_compare;
 116     actual_compare = cmp;
 117     qsort(array, n, sizeof(WvLink *), magic_compare);
 118     actual_compare = old_compare;
 119
 120     lptr = NULL;    // subsequent next() will set it to first element.
 121 }
 122 #endif