Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

wvlinklist.h

Go to the documentation of this file.
00001 /* -*- Mode: C++ -*-
00002  * Worldvisions Weaver Software:
00003  *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
00004  *
00005  * A linked list container.
00006  */
00007 #ifndef __WVLINKLIST_H
00008 #define __WVLINKLIST_H
00009 
00010 #include <assert.h>
00011 #include "wvsorter.h"
00012 
00013 /**
00014  * @internal
00015  * The untyped base class of WvList<T>.
00016  * 
00017  * Putting common code in here allows us to prevent it from being
00018  * replicated by each template instantiation of WvList<T>.
00019  * 
00020  */
00021 class WvListBase
00022 {
00023     WvListBase(const WvListBase &l); // copy constructor - not actually defined anywhere!
00024 protected:
00025     WvListBase& operator= (const WvListBase &l);
00026     
00027 public:
00028     WvLink head, *tail;
00029 
00030     /** Creates an empty linked list. */
00031     WvListBase() : head(NULL, false)
00032         { tail = &head; }
00033 
00034     /**
00035      * Returns the number of elements in the list.
00036      * 
00037      * This function causes a full traversal of the list which may be
00038      * overly inefficient depending on how and when it is used.
00039      * 
00040      * Returns: the number of elements
00041      */
00042     size_t count() const;
00043 
00044     /**
00045      * Reverses the order of elements in the list.
00046      *
00047      * This function traverses the list and rearranges the pointers
00048      * and updates the pointers to head & tail appropriately.
00049      *
00050      * It does nothing for lists of count<2
00051      */
00052     void reverse();
00053 
00054     /**
00055      * Quickly determines if the list is empty.
00056      * 
00057      * This is much faster than checking count() == 0.
00058      * 
00059      * Returns: true if empty
00060      */
00061     bool isempty() const
00062         { return head.next == NULL; }
00063 
00064     /**
00065      * @internal
00066      * The untyped base class of WvList<T>::Iter.
00067      * 
00068      * Putting common code in here allows us to prevent it from being
00069      * replicated by each template instantiation of WvList<T>.
00070      * 
00071      */
00072     class IterBase
00073     {
00074     public:
00075         const WvListBase *list;
00076         WvLink *link, *prev;
00077 
00078         /**
00079          * Binds the iterator to the specified list.
00080          * "l" is the list
00081          */
00082         IterBase(const WvListBase &l)
00083             { list = &l; link = NULL; }
00084 
00085         /**
00086          * Rewinds the iterator to make it point to an imaginary element
00087          * preceeding the first element of the list.
00088          */
00089         void rewind() // dropping a const pointer here!  Danger!
00090             { prev = NULL; link = &((WvListBase *)list)->head; }
00091 
00092         
00093         /**
00094          * Moves the iterator along the list to point to the next element.
00095          * 
00096          * If the iterator had just been rewound, it now points to the
00097          * first element of the list.
00098          * 
00099          * Returns: the current WvLink pointer, or null if there were no
00100          *         more elements remaining in the traversal sequence
00101          */
00102         WvLink *next()
00103             { prev = link; return link = link->next; }
00104 
00105         /**
00106          * Returns a pointer to the WvLink at the iterator's current location.
00107          * Returns: the current WvLink pointer, or null if there were no
00108          *         more elements remaining in the traversal sequence
00109          */
00110         WvLink *cur() const
00111             { return link; }
00112         
00113         /**
00114          * Returns a void pointer to the object at the iterator's current
00115          * location.  You should almost never need this.  Use ptr() instead.
00116          */
00117         void *vptr() const
00118             { return link->data; }
00119 
00120         /**
00121          * Rewinds the iterator and repositions it over the element that
00122          * matches the specified value.
00123          * 
00124          * Uses pointer equality (object identity) as the criteria for
00125          * finding the matching element.
00126          * 
00127          * It is not possible to use find(const void*) to locate multiple
00128          * matching elements unless the list is altered between invocations
00129          * since it always starts searching from the head of the list
00130          * rather than from the current location.
00131          * 
00132          * Returns: the current WvLink pointer, or null if no such element
00133          *         was found
00134          */
00135         WvLink *find(const void *data);
00136     };
00137 };
00138 
00139 /**
00140  * A linked list container class.
00141  * 
00142  * Some rather horrible macros are used to declare actual concrete
00143  * list types.
00144  * 
00145  * Example:
00146  * 
00147  *   DeclareWvList(WvString);
00148  *
00149  *   int main()
00150  *   {
00151  *       WvStringList l;
00152  *       WvStringList::Iter i(l);
00153  *
00154  *       ... fill the list ...
00155  *
00156  *       i.rewind();
00157  *       while (i.next())
00158  *           printf("%s\\n", i.str);
00159  *   }
00160  * 
00161  * 
00162  * Deallocating list will free all of the WvLinks in the list, but
00163  * will only free the user objects that were added with auto_free
00164  * set to true.
00165  * 
00166  * We need to malloc memory for each WvLink as well as the data it
00167  * stores; this is unnecessarily slow.  I would rather have made a
00168  * base "Link" class for object types that could be stored as links
00169  * in a list, and then used object->next instead of all the
00170  * List Iterator stuff, but the end result was pure ugliness, so I
00171  * gave up.  At least this way, the same object can be in multiple
00172  * lists.
00173  * 
00174  * List type construction is facilitated by the following macros:
00175  * 
00176  *  - DeclareWvList(Type): creates a subclass named WvListType
00177  *     that contains pointers to Type.
00178  *  - DeclareWvList2(name, Type): as the above, but calls the
00179  *     resulting class by the specified name. 
00180  * 
00181  * 
00182  * "T" is the object type
00183  */
00184 template<class T>
00185 class WvList : public WvListBase
00186 {
00187     // copy constructor: not defined anywhere!
00188     WvList(const WvList &list);
00189 public:
00190     /** Creates an empty linked list. */
00191     WvList()
00192         { }
00193     
00194     /**
00195      * Destroys the linked list.
00196      * 
00197      * Destroys any elements that were added with auto_free == true.
00198      * 
00199      */
00200     ~WvList()
00201         { zap(); }
00202         
00203     /** Invoked by subclasses after the linked list is first created. */
00204     void setup() {}
00205     
00206     /** Invoked by subclasses before the linked list is destroyed. */
00207     void shutdown() {}
00208 
00209     /**
00210      * Clears the linked list.
00211      * 
00212      * If destroy is true, destroys any elements that were added with auto_free == true.
00213      * 
00214      */
00215     void zap(bool destroy = true)
00216     {
00217         while (head.next)
00218             unlink_after(& head, destroy);
00219     }
00220 
00221     /**
00222      * Returns a pointer to the first element in the linked list.
00223      * 
00224      * The list must be non-empty.
00225      * 
00226      * Returns: the element pointer, possibly null
00227      */
00228     T *first() const
00229         {
00230             assert(!isempty());
00231             return (T*)head.next->data;
00232         }
00233 
00234     /**
00235      * Returns a pointer to the last element in the linked list.
00236      * 
00237      * The list must be non-empty.
00238      * 
00239      * Returns: the element pointer, possibly null
00240      */
00241     T *last() const
00242         { return (T*)tail->data; }
00243 
00244     /**
00245      * Adds the element after the specified link in the list.
00246      *
00247      * "link" is the link preceeding the desired location of the element
00248      *             to be inserted, non-null
00249      * "data" is the element pointer, may be null
00250      * "auto_free" is if true, takes ownership of the element
00251      * "id" is an optional string to associate with the element, or null
00252      */
00253     void add_after(WvLink *after, T *data, bool auto_free,
00254                         char *id = NULL )
00255         { (void)new WvLink((void *)data, after, tail, auto_free, id); }
00256 
00257     /**
00258      * Appends the element to the end of the list.
00259      *
00260      * "data" is the element pointer, may be null
00261      * "auto_free" is if true, takes ownership of the element
00262      * "id" is an optional string to associate with the element, or null
00263      */
00264     void append(T *data, bool auto_free, char *id = NULL)
00265         { add_after(tail, data, auto_free, id); }
00266 
00267     /**
00268      * Synonym for append(T*, bool, char*).
00269      * @see append(T*, bool, char*)
00270      */
00271     void add(T *data, bool auto_free, char *id = NULL)
00272         { append(data, auto_free, id); }
00273 
00274     /**
00275      * Prepends the element to the beginning of the list.
00276      *
00277      * "data" is the element pointer, may be null
00278      * "auto_free" is if true, takes ownership of the element
00279      * "id" is an optional string to associate with the element, or null
00280      */
00281     void prepend(T *data, bool auto_free, char *id = NULL)
00282         { add_after(&head, data, auto_free, id); }
00283 
00284     /**
00285      * Unlinks the specified element from the list.
00286      * 
00287      * Destroys the element if it was added with auto_free == true.
00288      * 
00289      * "data" is the element pointer, may be null
00290      */
00291     void unlink(T *data)
00292         { Iter i(*this); while (i.find(data)) i.unlink(); }
00293 
00294     /**
00295      * Unlinks the first element from the list.
00296      * 
00297      * Destroys the element if it was added with auto_free == true.
00298      * 
00299      */ 
00300     void unlink_first()
00301         { Iter i(*this); i.rewind(); i.next(); i.unlink(); }
00302 
00303     /**
00304      * Unlinks the element that follows the specified link in the list.
00305      * 
00306      * Destroys the element if it was added with auto_free == true and
00307      * destroy == true.
00308      * 
00309      * "after" is the link preceeding the element to be removed, non-null
00310      */ 
00311     void unlink_after(WvLink *after, bool destroy = true)
00312     {
00313         WvLink *next = after->next;
00314         T *obj = (destroy && next->auto_free) ?
00315             static_cast<T*>(next->data) : NULL;
00316         if (next == tail) tail = after;
00317         next->unlink(after);
00318         delete obj;
00319     }
00320 
00321     /**
00322      * The iterator type for linked lists.
00323      * 
00324      * An iterator instance does not initially point to any valid
00325      * elements in a list.  Before using, it must be reset using rewind()
00326      * which causes it to point to an imaginary element located before
00327      * the first elements in the list.  Then next() must be invoked
00328      * to incrementally move the iterator along the list to first element,
00329      * and then later to the second, third, and subsequent elements.
00330      * 
00331      */
00332     class Iter : public WvListBase::IterBase
00333     {
00334     public:
00335         /**
00336          * Binds the iterator to the specified list.
00337          * "l" is the list
00338          */
00339         Iter(const WvList &l) : IterBase(l)
00340             { }
00341 
00342         /**
00343          * Returns a pointer to the current element.
00344          * Returns: the element pointer, possibly null
00345          */
00346         T *ptr() const
00347             { return (T *)link->data; }
00348 
00349         WvIterStuff(T);
00350         
00351         /**
00352          * Unlinks the current element from the list and automatically
00353          * increments the iterator to point to the next element as if
00354          * next() had been called.
00355          */
00356         void unlink()
00357         {
00358             if (prev) ((WvList *)list)->unlink_after(prev);
00359             link = prev->next;
00360         }
00361         
00362         /**
00363          * Unlinks the current element from the list but unlike unlink()
00364          * automatically returns the iterator to the previous link in
00365          * the list such that next() must be called to obtain the
00366          * next element.
00367          * 
00368          * This version allows for writing neater loop structures since
00369          * an element can be unlinked in mid-traversal while still allowing
00370          * the iterator to be incremented at the top of the loop as usual.
00371          * 
00372          * Calling xunlink() twice in a row is currently unsupported.
00373          * 
00374          */
00375         void xunlink()
00376         {
00377             if (prev) ((WvList *)list)->unlink_after(prev);
00378             link = prev;
00379         }
00380     };
00381     
00382     /** The sorted iterator type for linked lists. */
00383     typedef class WvSorter<T, WvListBase, WvListBase::IterBase> Sorter;
00384 };
00385 
00386 #define DeclareWvList2(_classname_, _type_)  \
00387     typedef class WvList<_type_> _classname_ 
00388 
00389 #define DeclareWvList(_type_) DeclareWvList2(_type_##List, _type_)
00390 
00391 
00392 #endif // __WVLINKLIST_H

Generated on Sat Mar 13 14:55:46 2004 for WvStreams by doxygen 1.3.6-20040222