WvStreams
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 
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 
59 {
60  for (rewind(); next(); )
61  if (link->data == data)
62  break;
63  return link;
64 }
65 
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
WvListBase::IterBase::find
WvLink * find(const void *data)
Rewinds the iterator and repositions it over the element that matches the specified value.
Definition: wvlinklist.cc:58
WvListBase::count
size_t count() const
Returns the number of elements in the list.
Definition: wvlinklist.cc:24
WvListBase::IterBase::rewind
void rewind()
Rewinds the iterator to make it point to an imaginary element preceeding the first element of the lis...
Definition: wvlinklist.h:90
WvListBase::IterBase::next
WvLink * next()
Moves the iterator along the list to point to the next element.
Definition: wvlinklist.h:103
WvListBase::reverse
void reverse()
Reverses the order of elements in the list.
Definition: wvlinklist.cc:35
WvListBase::IterBase::find_next
WvLink * find_next(const void *data)
Repositions the iterator over the element that matches the specified value.
Definition: wvlinklist.cc:66