Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

wvlinklist.h

Go to the documentation of this file.
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.  This looks pretty
00007  * horrible, but lets us do stuff like this:
00008  *
00009  *       DeclareWvList(WvString);
00010  *
00011  *       int main()
00012  *       {
00013  *           WvStringList l;
00014  *           WvStringList::Iter i(l);
00015  *           ... fill the list ...
00016  *
00017  *           i.rewind();
00018  *           while (i.next())
00019  *               printf("%s\n", i.str);
00020  *
00021  *           ...
00022  *       }
00023  *
00024  * NOTES:
00025  *    - We need to malloc memory for each WvLink as well as the data it
00026  *        stores; this is unnecessarily slow.  I would rather have made a
00027  *        base "Link" class for object types that could be stored as links
00028  *        in a list, and then used object->next instead of all the
00029  *        List Iterator stuff, but the end result was pure ugliness, so I
00030  *        gave up.  At least this way, the same object can be in multiple
00031  *        lists.
00032  *
00033  *    - DeclareWvList2() allows the user to include arbitrary lines
00034  *        inside the class definition.  For example:
00035  *             DeclareWvList2(WvString, void autofill(););
00036  *
00037  *    - Deallocating a *List object will free all the WvLinks in the list,
00038  *        but not necessarily all the objects that the WvLinks point to
00039  *        (depending on the value of link->auto_free)
00040  */
00041 #ifndef __WVLINKLIST_H
00042 #define __WVLINKLIST_H
00043 
00044 #include <assert.h>
00045 #include "wvsorter.h"
00046 
00047 class WvListBase
00048 {
00049 public:
00050     WvLink head, *tail;
00051     WvListBase() : head(NULL, false)
00052         { tail = &head; }
00053     WvListBase(const WvListBase &l); // copy constructor - not actually defined anywhere!
00054     WvListBase& operator= (const WvListBase &l);
00055     size_t count() const;
00056 
00057     // this could be done with count() but it would be slow
00058     bool isempty() const
00059         { return head.next == NULL; }
00060 
00061     // the base class for list iterators
00062     class IterBase
00063     {
00064     public:
00065         const WvListBase *list;
00066         WvLink *link, *prev;
00067 
00068         IterBase(const WvListBase &l)
00069             { list = &l; link = NULL; }
00070         void rewind() // dropping a const pointer here!  Danger!
00071             { prev = NULL; link = &((WvListBase *)list)->head; }
00072         WvLink *next()
00073             { prev = link; return link = link->next; }
00074         WvLink *cur() const
00075             { return link; }
00076 
00077         // set 'cur' to the WvLink that points to 'data', and return the
00078         // link.  If 'data' is not found, sets cur=NULL and returns NULL.
00079         WvLink *find(const void *data);
00080     };
00081 };
00082 
00083 template <class _type_>
00084 class WvList : public WvListBase
00085 {
00086 public:
00087     WvList()
00088         { }
00089         
00090     ~WvList()
00091         { zap(); }
00092         
00093     // default implementations
00094     void setup() {}
00095     void shutdown() {}
00096 
00097     void zap()
00098     {
00099         WvLink *l, *n=head.next;
00100         head.next = NULL;
00101         tail = &head;
00102         while ((l = n) != NULL)
00103         {
00104             n = l->next;
00105             if (l->auto_free) delete (_type_ *)l->data;
00106             delete l;
00107         }
00108     }
00109 
00110     _type_ *first() const
00111         {
00112             assert(!isempty());
00113             return (_type_*)head.next->data;
00114         }
00115 
00116     _type_ *last() const
00117         { return (_type_*)last->data; }
00118 
00119     void add_after(WvLink *after, _type_ *data, bool auto_free,
00120                         char *id = NULL )
00121         { (void)new WvLink((void *)data, after, tail, auto_free, id); }
00122 
00123     void append(_type_ *data, bool auto_free, char *id = NULL)
00124         { add_after(tail, data, auto_free, id); }
00125 
00126     void prepend(_type_ *data, bool auto_free, char *id = NULL)
00127         { add_after(&head, data, auto_free, id); }
00128 
00129     void unlink(_type_ *data)
00130         { Iter i(*this); while (i.find(data)) i.unlink(); }
00131 
00132     void unlink_first()
00133         { Iter i(*this); i.rewind(); i.next(); i.unlink(); }
00134 
00135     void unlink_after(WvLink *after)
00136     {
00137          if (after->next->auto_free)
00138              delete (_type_ *)after->next->data;
00139          if (after->next == tail) tail = after;
00140          if (after->next) after->next->unlink(after);
00141     }
00142 
00143     class Iter : public WvListBase::IterBase
00144     {
00145     public:
00146         Iter(const WvList &l) : IterBase(l)
00147             { }
00148         _type_ *ptr() const
00149             { return (_type_ *)link->data; }
00150         WvIterStuff(_type_);
00151         
00152         void unlink()
00153         {
00154             if (prev) ((WvList *)list)->unlink_after(prev);
00155             link = prev->next;
00156         }
00157         
00158         // like unlink(), except it leaves the iterator semi-invalid so
00159         // you have to do a next() before accessing it again.  In retrospect,
00160         // this is probably a nicer API than unlink() (since you can then
00161         // just do next() at the top of the loop regardless of whether you
00162         // did unlink()) but it would be too painful to change it everywhere
00163         // right now.
00164         void xunlink()
00165         {
00166             if (prev) ((WvList *)list)->unlink_after(prev);
00167             link = prev;
00168         }
00169     };
00170     
00171     typedef class WvSorter<_type_,WvListBase,WvListBase::IterBase> Sorter;
00172 };
00173 
00174 
00175 #define DeclareWvList3(_type_,_newname_,_extra_)        \
00176     class _newname_ : public WvList<_type_>             \
00177     {                                                   \
00178     public:                                             \
00179         _newname_() { setup(); }                        \
00180                                                         \
00181         ~_newname_() { shutdown(); }                    \
00182         _extra_                                         \
00183     };
00184 
00185 #define DeclareWvList2(_type_,_extra_)                  \
00186                 DeclareWvList3(_type_,_type_##List,_extra_ )
00187 
00188 #define DeclareWvList(_type_) DeclareWvList2(_type_, )
00189 
00190 
00191 #endif // __WVLINKLIST_H

Generated on Sun Aug 25 12:42:14 2002 for WvStreams by doxygen1.2.15