WvStreams
wvlinklist.cc
00001 /*
00002  * Worldvisions Weaver Software:
00003  *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
00004  * 
00005  * Implementation of a Linked List management class, or rather, macros that
00006  * declare arbitrary linked list management classes.
00007  * 
00008  * wvlinklist.h does all the real work.
00009  */
00010 #include "wvlinklist.h"
00011 
00012 WvLink::WvLink(void *_data, WvLink *prev, WvLink *&tail, bool _autofree,
00013                const char *_id)
00014 {
00015     data = _data;
00016     next = prev->next;
00017     if (!next) tail = this;
00018     prev->next = this;
00019     autofree = _autofree;
00020     id = _id;
00021 }
00022 
00023 
00024 size_t WvListBase::count() const
00025 {
00026     WvLink *l;
00027     size_t n = 0;
00028     
00029     for (l = head.next; l; l = l->next)
00030         n++;
00031     return n;
00032 }
00033 
00034 
00035 void WvListBase::reverse()
00036 {
00037     WvLink *prev, *curr, *next;
00038 
00039     if (!head.next || !head.next->next)
00040         return;
00041     
00042     prev = head.next;
00043     curr = prev->next; 
00044    
00045     do {
00046         next = curr->next;
00047         curr->next = prev;
00048         prev = curr;
00049         curr = next;
00050     } while(curr);
00051     
00052     tail = head.next;
00053     tail->next = NULL;
00054     head.next = prev;
00055 }
00056 
00057 
00058 WvLink *WvListBase::IterBase::find(const void *data)
00059 {
00060     for (rewind(); next(); )
00061         if (link->data == data)
00062             break;
00063     return link;
00064 }
00065 
00066 WvLink *WvListBase::IterBase::find_next(const void *data)
00067 {
00068     if (link)
00069     {
00070         if (link->data == data)
00071             return link;
00072 
00073         for (rewind(); next(); )
00074             if (link->data == data)
00075                 break;
00076     }
00077     return link;
00078 }
00079 
00080 
00081 #if 0
00082 static WvListBase::SorterBase::CompareFunc *actual_compare = NULL;
00083 
00084 static int magic_compare(const void *_a, const void *_b)
00085 {
00086     WvLink *a = *(WvLink **)_a, *b = *(WvLink **)_b;
00087     return actual_compare(a->data, b->data);
00088 }
00089 
00090 void WvListBase::SorterBase::rewind(CompareFunc *cmp)
00091 {
00092     if (array)
00093         delete array;
00094     array = lptr = NULL;
00095 
00096     int n = list->count();
00097     array = new WvLink * [n+1];
00098     WvLink **aptr = array;
00099 
00100     // fill the array with data pointers for sorting, so that the user doesn't
00101     // have to deal with the WvLink objects.  Put the WvLink pointers back 
00102     // in after sorting.
00103     IterBase i(*list);
00104     aptr = array;
00105     for (i.rewind(); i.next(); )
00106     {
00107         *aptr = i.cur();
00108         aptr++;
00109     }
00110     
00111     *aptr = NULL;
00112 
00113     // sort the array.  "Very nearly re-entrant" (unless the compare function
00114     // ends up being called recursively or something really weird...)
00115     CompareFunc *old_compare = actual_compare;
00116     actual_compare = cmp;
00117     qsort(array, n, sizeof(WvLink *), magic_compare);
00118     actual_compare = old_compare;
00119 
00120     lptr = NULL;    // subsequent next() will set it to first element.
00121 }
00122 #endif