WvStreams
|
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