include/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
  13 /**
  14  * @internal
  15  * The untyped base class of WvList<T>.
  16  *
  17  * Putting common code in here allows us to prevent it from being
  18  * replicated by each template instantiation of WvList<T>.
  19  *
  20  */
  21 class WvListBase
  22 {
  23     WvListBase(const WvListBase &l); // copy constructor - not actually defined anywhere!
  24 private:
  25     //This is private to force people to pass by reference, not by value
  26     WvListBase& operator= (const WvListBase &l);
  27
  28 public:
  29     WvLink head, *tail;
  30
  31     /** Creates an empty linked list. */
  32     WvListBase() : head(NULL, false)
  33         { tail = &head; }
  34
  35     /**
  36      * Returns the number of elements in the list.
  37      *
  38      * This function causes a full traversal of the list which may be
  39      * overly inefficient depending on how and when it is used.
  40      *
  41      * Returns: the number of elements
  42      */
  43     size_t count() const;
  44
  45     /**
  46      * Reverses the order of elements in the list.
  47      *
  48      * This function traverses the list and rearranges the pointers
  49      * and updates the pointers to head & tail appropriately.
  50      *
  51      * It does nothing for lists of count<2
  52      */
  53     void reverse();
  54
  55     /**
  56      * Quickly determines if the list is empty.
  57      *
  58      * This is much faster than checking count() == 0.
  59      *
  60      * Returns: true if empty
  61      */
  62     bool isempty() const
  63         { return head.next == NULL; }
  64
  65     /**
  66      * @internal
  67      * The untyped base class of WvList<T>::Iter.
  68      *
  69      * Putting common code in here allows us to prevent it from being
  70      * replicated by each template instantiation of WvList<T>.
  71      *
  72      */
  73     class IterBase
  74     {
  75     public:
  76         const WvListBase *list;
  77         WvLink *link, *prev;
  78
  79         /**
  80          * Binds the iterator to the specified list.
  81          * "l" is the list
  82          */
  83         IterBase(const WvListBase &l)
  84             { list = &l; link = NULL; }
  85
  86         /**
  87          * Rewinds the iterator to make it point to an imaginary element
  88          * preceeding the first element of the list.
  89          */
  90         void rewind() // dropping a const pointer here!  Danger!
  91             { prev = NULL; link = &((WvListBase *)list)->head; }
  92
  93
  94         /**
  95          * Moves the iterator along the list to point to the next element.
  96          *
  97          * If the iterator had just been rewound, it now points to the
  98          * first element of the list.
  99          *
 100          * Returns: the current WvLink pointer, or null if there were no
 101          *         more elements remaining in the traversal sequence
 102          */
 103         WvLink *next()
 104             { prev = link; return link = link->next; }
 105
 106         /**
 107          * Returns a pointer to the WvLink at the iterator's current location.
 108          * Returns: the current WvLink pointer, or null if there were no
 109          *         more elements remaining in the traversal sequence
 110          */
 111         WvLink *cur() const
 112             { return link; }
 113
 114         /**
 115          * Returns a void pointer to the object at the iterator's current
 116          * location.  You should almost never need this.  Use ptr() instead.
 117          */
 118         void *vptr() const
 119             { return link->data; }
 120
 121         /**
 122          * Rewinds the iterator and repositions it over the element that
 123          * matches the specified value.
 124          *
 125          * Uses pointer equality (object identity) as the criteria for
 126          * finding the matching element.
 127          *
 128          * In order to locate multiple matching elements, first call find()
 129          * and then use find_next().
 130          *
 131          * Returns: the current WvLink pointer, or null if no such element
 132          *          was found
 133          */
 134         WvLink *find(const void *data);
 135
 136         /**
 137          * Repositions the iterator over the element that matches the
 138          * specified value.
 139          *
 140          * Uses pointer equality (object identity) as the criteria for
 141          * finding the matching element.
 142          *
 143          * Returns: the current WvLink pointer, or null if no such element
 144          *          was found
 145          */
 146         WvLink *find_next(const void*data);
 147     };
 148 };
 149
 150
 151 /**
 152  * A linked list container class.
 153  *
 154  * Some rather horrible macros are used to declare actual concrete
 155  * list types.
 156  *
 157  * Example:
 158  *
 159  *   DeclareWvList(WvString);
 160  *
 161  *   int main()
 162  *   {
 163  *       WvStringList l;
 164  *       WvStringList::Iter i(l);
 165  *
 166  *       ... fill the list ...
 167  *
 168  *       i.rewind();
 169  *       while (i.next())
 170  *           printf("%s\\n", i.str);
 171  *   }
 172  *
 173  *
 174  * Deallocating list will free all of the WvLinks in the list, but
 175  * will only free the user objects that were added with autofree
 176  * set to true.
 177  *
 178  * We need to malloc memory for each WvLink as well as the data it
 179  * stores; this is unnecessarily slow.  I would rather have made a
 180  * base "Link" class for object types that could be stored as links
 181  * in a list, and then used object->next instead of all the
 182  * List Iterator stuff, but the end result was pure ugliness, so I
 183  * gave up.  At least this way, the same object can be in multiple
 184  * lists.
 185  *
 186  * List type construction is facilitated by the following macros:
 187  *
 188  *  - DeclareWvList(Type): creates a subclass named TypeList
 189  *     that contains pointers to Type.
 190  *  - DeclareWvList2(name, Type): as the above, but calls the
 191  *     resulting class by the specified name.
 192  *
 193  *
 194  * "T" is the object type
 195  */
 196 template<class T>
 197 class WvList : public WvListBase
 198 {
 199     // copy constructor: not defined anywhere!
 200     WvList(const WvList &list);
 201
 202 public:
 203     /** Creates an empty linked list. */
 204     WvList()
 205         { }
 206
 207     /**
 208      * Destroys the linked list.
 209      *
 210      * Destroys any elements that were added with autofree == true.
 211      *
 212      */
 213     ~WvList()
 214         { zap(); }
 215
 216     /** Invoked by subclasses after the linked list is first created. */
 217     void setup() {}
 218
 219     /** Invoked by subclasses before the linked list is destroyed. */
 220     void shutdown() {}
 221
 222     /**
 223      * Clears the linked list.
 224      *
 225      * If destroy is true, destroys any elements that were added with autofree == true.
 226      *
 227      */
 228     void zap(bool destroy = true)
 229     {
 230         while (head.next)
 231             unlink_after(& head, destroy);
 232     }
 233
 234     /**
 235      * Returns a pointer to the first element in the linked list.
 236      *
 237      * The list must be non-empty.
 238      *
 239      * Returns: the element pointer, possibly null
 240      */
 241     T *first() const
 242         { return (T*)head.next->data; }
 243
 244     /**
 245      * Returns a pointer to the last element in the linked list.
 246      *
 247      * The list must be non-empty.
 248      *
 249      * Returns: the element pointer, possibly null
 250      */
 251     T *last() const
 252         { return (T*)tail->data; }
 253
 254     /**
 255      * Adds the element after the specified link in the list.
 256      *
 257      * "link" is the link preceeding the desired location of the element
 258      *             to be inserted, non-null
 259      * "data" is the element pointer, may be null
 260      * "autofree" is if true, takes ownership of the element
 261      * "id" is an optional string to associate with the element, or null
 262      */
 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
 269     /**
 270      * Appends the element to the end of the list.
 271      *
 272      * "data" is the element pointer, may be null
 273      * "autofree" is if true, takes ownership of the element
 274      * "id" is an optional string to associate with the element, or null
 275      */
 276     void append(T *data, bool autofree, const char *id = NULL)
 277         { add_after(tail, data, autofree, id); }
 278
 279     /**
 280      * Synonym for append(T*, bool, char*).
 281      * @see append(T*, bool, char*)
 282      */
 283     void add(T *data, bool autofree, const char *id = NULL)
 284         { append(data, autofree, id); }
 285
 286     /**
 287      * Prepends the element to the beginning of the list.
 288      *
 289      * "data" is the element pointer, may be null
 290      * "autofree" is if true, takes ownership of the element
 291      * "id" is an optional string to associate with the element, or null
 292      */
 293     void prepend(T *data, bool autofree, const char *id = NULL)
 294         { add_after(&head, data, autofree, id); }
 295
 296     /**
 297      * Unlinks the specified element from the list.
 298      *
 299      * Destroys the element if it was added with autofree == true.
 300      *
 301      * "data" is the element pointer, may be null
 302      */
 303     void unlink(T *data)
 304         { Iter i(*this); while (i.find(data)) i.unlink(); }
 305
 306     /**
 307      * Unlinks the first element from the list.
 308      *
 309      * Destroys the element if it was added with autofree == true.
 310      *
 311      */
 312     void unlink_first()
 313     {
 314         if(head.next != NULL)
 315         { Iter i(*this); i.rewind(); i.next(); i.unlink(); }
 316     }
 317     /**
 318      * Unlinks the element that follows the specified link in the list.
 319      *
 320      * Destroys the element if it was added with autofree == true and
 321      * destroy == true.
 322      *
 323      * "after" is the link preceeding the element to be removed, non-null
 324      */
 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)
 335                 WvTraits<T>::release(obj);
 336         }
 337     }
 338
 339     /**
 340      * The iterator type for linked lists.
 341      *
 342      * An iterator instance does not initially point to any valid
 343      * elements in a list.  Before using, it must be reset using rewind()
 344      * which causes it to point to an imaginary element located before
 345      * the first elements in the list.  Then next() must be invoked
 346      * to incrementally move the iterator along the list to first element,
 347      * and then later to the second, third, and subsequent elements.
 348      *
 349      */
 350     class Iter : public WvListBase::IterBase
 351     {
 352     public:
 353         /**
 354          * Binds the iterator to the specified list.
 355          * "l" is the list
 356          */
 357         Iter(const WvList &l) : IterBase(l)
 358             { }
 359
 360         /**
 361          * Returns a pointer to the current element.
 362          * Returns: the element pointer, possibly null
 363          */
 364         T *ptr() const
 365             { return (T *)link->data; }
 366
 367         WvIterStuff(T);
 368
 369         /**
 370          * Returns the state of autofree for the current element.
 371          */
 372         bool get_autofree() const
 373         {
 374             return link->get_autofree();
 375         }
 376
 377         /**
 378          * Sets the state of autofree for the current element.
 379          */
 380         void set_autofree(bool autofree)
 381         {
 382             link->set_autofree(autofree);
 383         }
 384
 385         /**
 386          * Unlinks the current element from the list and automatically
 387          * increments the iterator to point to the next element as if
 388          * next() had been called.
 389          */
 390         void unlink(bool destroy = true)
 391         {
 392             if (prev) ((WvList *)list)->unlink_after(prev, destroy);
 393             link = prev->next;
 394         }
 395
 396         /**
 397          * Unlinks the current element from the list but unlike unlink()
 398          * automatically returns the iterator to the previous link in
 399          * the list such that next() must be called to obtain the
 400          * next element.
 401          *
 402          * This version allows for writing neater loop structures since
 403          * an element can be unlinked in mid-traversal while still allowing
 404          * the iterator to be incremented at the top of the loop as usual.
 405          *
 406          * Calling xunlink() twice in a row is currently unsupported.
 407          *
 408          */
 409         void xunlink(bool destroy = true)
 410         {
 411             if (prev) ((WvList *)list)->unlink_after(prev, destroy);
 412             link = prev;
 413         }
 414     };
 415
 416     /** The sorted iterator type for linked lists. */
 417     typedef class WvSorter<T, WvListBase, WvListBase::IterBase> Sorter;
 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