WvStreams
wvlinklist.h
1/* -*- Mode: C++ -*-
2 * Worldvisions Weaver Software:
3 * Copyright (C) 1997-2002 Net Integration Technologies, Inc.
4 *
5 * A linked list container.
6 */
7#ifndef __WVLINKLIST_H
8#define __WVLINKLIST_H
9
10#include "wvtypetraits.h"
11#include "wvsorter.h"
12
22{
23 WvListBase(const WvListBase &l); // copy constructor - not actually defined anywhere!
24private:
25 //This is private to force people to pass by reference, not by value
26 WvListBase& operator= (const WvListBase &l);
27
28public:
29 WvLink head, *tail;
30
32 WvListBase() : head(NULL, false)
33 { tail = &head; }
34
43 size_t count() const;
44
53 void reverse();
54
62 bool isempty() const
63 { return head.next == NULL; }
64
74 {
75 public:
76 const WvListBase *list;
77 WvLink *link, *prev;
78
84 { list = &l; link = NULL; }
85
90 void rewind() // dropping a const pointer here! Danger!
91 { prev = NULL; link = &((WvListBase *)list)->head; }
92
93
104 { prev = link; return link = link->next; }
105
111 WvLink *cur() const
112 { return link; }
113
118 void *vptr() const
119 { return link->data; }
120
134 WvLink *find(const void *data);
135
146 WvLink *find_next(const void*data);
147 };
148};
149
150
196template<class T>
197class WvList : public WvListBase
198{
199 // copy constructor: not defined anywhere!
200 WvList(const WvList &list);
201
202public:
205 { }
206
214 { zap(); }
215
217 void setup() {}
218
220 void shutdown() {}
221
228 void zap(bool destroy = true)
229 {
230 while (head.next)
231 unlink_after(& head, destroy);
232 }
233
241 T *first() const
242 { return (T*)head.next->data; }
243
251 T *last() const
252 { return (T*)tail->data; }
253
263 void add_after(WvLink *after, T *data, bool autofree,
264 const char *id = NULL )
265 {
266 (void)new WvLink((void *)data, after, tail, autofree, id);
267 }
268
276 void append(T *data, bool autofree, const char *id = NULL)
277 { add_after(tail, data, autofree, id); }
278
283 void add(T *data, bool autofree, const char *id = NULL)
284 { append(data, autofree, id); }
285
293 void prepend(T *data, bool autofree, const char *id = NULL)
294 { add_after(&head, data, autofree, id); }
295
303 void unlink(T *data)
304 { Iter i(*this); while (i.find(data)) i.unlink(); }
305
313 {
314 if(head.next != NULL)
315 { Iter i(*this); i.rewind(); i.next(); i.unlink(); }
316 }
325 void unlink_after(WvLink *after, bool destroy = true)
326 {
327 WvLink *next = after->next;
328 if(next != NULL)
329 {
330 T *obj = (destroy && next->get_autofree()) ?
331 static_cast<T*>(next->data) : NULL;
332 if (next == tail) tail = after;
333 next->unlink(after);
334 if (obj)
336 }
337 }
338
351 {
352 public:
357 Iter(const WvList &l) : IterBase(l)
358 { }
359
364 T *ptr() const
365 { return (T *)link->data; }
366
367 WvIterStuff(T);
368
372 bool get_autofree() const
373 {
374 return link->get_autofree();
375 }
376
380 void set_autofree(bool autofree)
381 {
382 link->set_autofree(autofree);
383 }
384
390 void unlink(bool destroy = true)
391 {
392 if (prev) ((WvList *)list)->unlink_after(prev, destroy);
393 link = prev->next;
394 }
395
409 void xunlink(bool destroy = true)
410 {
411 if (prev) ((WvList *)list)->unlink_after(prev, destroy);
412 link = prev;
413 }
414 };
415
418};
419
420#define DeclareWvList2(_classname_, _type_) \
421 typedef class WvList<_type_> _classname_
422
423#define DeclareWvList(_type_) DeclareWvList2(_type_##List, _type_)
424
425
426#endif // __WVLINKLIST_H
IterBase(const WvListBase &l)
Binds the iterator to the specified list.
Definition: wvlinklist.h:83
void rewind()
Rewinds the iterator to make it point to an imaginary element preceeding the first element of the lis...
Definition: wvlinklist.h:90
void * vptr() const
Returns a void pointer to the object at the iterator's current location.
Definition: wvlinklist.h:118
WvLink * cur() const
Returns a pointer to the WvLink at the iterator's current location.
Definition: wvlinklist.h:111
WvLink * find_next(const void *data)
Repositions the iterator over the element that matches the specified value.
Definition: wvlinklist.cc:66
WvLink * next()
Moves the iterator along the list to point to the next element.
Definition: wvlinklist.h:103
WvLink * find(const void *data)
Rewinds the iterator and repositions it over the element that matches the specified value.
Definition: wvlinklist.cc:58
WvListBase()
Creates an empty linked list.
Definition: wvlinklist.h:32
void reverse()
Reverses the order of elements in the list.
Definition: wvlinklist.cc:35
size_t count() const
Returns the number of elements in the list.
Definition: wvlinklist.cc:24
bool isempty() const
Quickly determines if the list is empty.
Definition: wvlinklist.h:62
The iterator type for linked lists.
Definition: wvlinklist.h:351
void set_autofree(bool autofree)
Sets the state of autofree for the current element.
Definition: wvlinklist.h:380
bool get_autofree() const
Returns the state of autofree for the current element.
Definition: wvlinklist.h:372
T * ptr() const
Returns a pointer to the current element.
Definition: wvlinklist.h:364
void unlink(bool destroy=true)
Unlinks the current element from the list and automatically increments the iterator to point to the n...
Definition: wvlinklist.h:390
void xunlink(bool destroy=true)
Unlinks the current element from the list but unlike unlink() automatically returns the iterator to t...
Definition: wvlinklist.h:409
Iter(const WvList &l)
Binds the iterator to the specified list.
Definition: wvlinklist.h:357
A linked list container class.
Definition: wvlinklist.h:198
void append(T *data, bool autofree, const char *id=NULL)
Appends the element to the end of the list.
Definition: wvlinklist.h:276
void unlink_first()
Unlinks the first element from the list.
Definition: wvlinklist.h:312
~WvList()
Destroys the linked list.
Definition: wvlinklist.h:213
void shutdown()
Invoked by subclasses before the linked list is destroyed.
Definition: wvlinklist.h:220
void prepend(T *data, bool autofree, const char *id=NULL)
Prepends the element to the beginning of the list.
Definition: wvlinklist.h:293
WvList()
Creates an empty linked list.
Definition: wvlinklist.h:204
class WvSorter< T, WvListBase, WvListBase::IterBase > Sorter
The sorted iterator type for linked lists.
Definition: wvlinklist.h:417
void unlink_after(WvLink *after, bool destroy=true)
Unlinks the element that follows the specified link in the list.
Definition: wvlinklist.h:325
void add(T *data, bool autofree, const char *id=NULL)
Synonym for append(T*, bool, char*).
Definition: wvlinklist.h:283
T * first() const
Returns a pointer to the first element in the linked list.
Definition: wvlinklist.h:241
T * last() const
Returns a pointer to the last element in the linked list.
Definition: wvlinklist.h:251
void setup()
Invoked by subclasses after the linked list is first created.
Definition: wvlinklist.h:217
void zap(bool destroy=true)
Clears the linked list.
Definition: wvlinklist.h:228
void unlink(T *data)
Unlinks the specified element from the list.
Definition: wvlinklist.h:303
void add_after(WvLink *after, T *data, bool autofree, const char *id=NULL)
Adds the element after the specified link in the list.
Definition: wvlinklist.h:263