Logo Search packages:      
Sourcecode: wvstreams version File versions

wvlinklist.h

/* -*- Mode: C++ -*-
 * Worldvisions Weaver Software:
 *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
 *
 * A linked list container.
 */
#ifndef __WVLINKLIST_H
#define __WVLINKLIST_H

#include "wvtypetraits.h"
#include "wvsorter.h"

/**
 * @internal
 * The untyped base class of WvList<T>.
 * 
 * Putting common code in here allows us to prevent it from being
 * replicated by each template instantiation of WvList<T>.
 * 
 */
00021 class WvListBase
{
    WvListBase(const WvListBase &l); // copy constructor - not actually defined anywhere!
protected:
    WvListBase& operator= (const WvListBase &l);
    
public:
    WvLink head, *tail;

    /** Creates an empty linked list. */
00031     WvListBase() : head(NULL, false)
        { tail = &head; }

    /**
     * Returns the number of elements in the list.
     * 
     * This function causes a full traversal of the list which may be
     * overly inefficient depending on how and when it is used.
     * 
     * Returns: the number of elements
     */
    size_t count() const;

    /**
     * Reverses the order of elements in the list.
     *
     * This function traverses the list and rearranges the pointers
     * and updates the pointers to head & tail appropriately.
     *
     * It does nothing for lists of count<2
     */
    void reverse();

    /**
     * Quickly determines if the list is empty.
     * 
     * This is much faster than checking count() == 0.
     * 
     * Returns: true if empty
     */
00061     bool isempty() const
        { return head.next == NULL; }

    /**
     * @internal
     * The untyped base class of WvList<T>::Iter.
     * 
     * Putting common code in here allows us to prevent it from being
     * replicated by each template instantiation of WvList<T>.
     * 
     */
00072     class IterBase
    {
    public:
      const WvListBase *list;
      WvLink *link, *prev;

        /**
         * Binds the iterator to the specified list.
         * "l" is the list
         */
00082       IterBase(const WvListBase &l)
            { list = &l; link = NULL; }

        /**
         * Rewinds the iterator to make it point to an imaginary element
         * preceeding the first element of the list.
         */
00089       void rewind() // dropping a const pointer here!  Danger!
            { prev = NULL; link = &((WvListBase *)list)->head; }

      
        /**
         * Moves the iterator along the list to point to the next element.
         * 
         * If the iterator had just been rewound, it now points to the
         * first element of the list.
         * 
         * Returns: the current WvLink pointer, or null if there were no
         *         more elements remaining in the traversal sequence
         */
00102       WvLink *next()
            { prev = link; return link = link->next; }

        /**
         * Returns a pointer to the WvLink at the iterator's current location.
         * Returns: the current WvLink pointer, or null if there were no
         *         more elements remaining in the traversal sequence
         */
00110       WvLink *cur() const
            { return link; }
      
      /**
       * Returns a void pointer to the object at the iterator's current
       * location.  You should almost never need this.  Use ptr() instead.
       */
00117       void *vptr() const
          { return link->data; }

        /**
         * Rewinds the iterator and repositions it over the element that
         * matches the specified value.
         * 
         * Uses pointer equality (object identity) as the criteria for
         * finding the matching element.
         * 
         * It is not possible to use find(const void*) to locate multiple
         * matching elements unless the list is altered between invocations
         * since it always starts searching from the head of the list
         * rather than from the current location.
         * 
         * Returns: the current WvLink pointer, or null if no such element
         *         was found
         */
      WvLink *find(const void *data);
    };
};


/**
 * A linked list container class.
 * 
 * Some rather horrible macros are used to declare actual concrete
 * list types.
 * 
 * Example:
 * 
 *   DeclareWvList(WvString);
 *
 *   int main()
 *   {
 *       WvStringList l;
 *       WvStringList::Iter i(l);
 *
 *       ... fill the list ...
 *
 *       i.rewind();
 *       while (i.next())
 *           printf("%s\\n", i.str);
 *   }
 * 
 * 
 * Deallocating list will free all of the WvLinks in the list, but
 * will only free the user objects that were added with auto_free
 * set to true.
 * 
 * We need to malloc memory for each WvLink as well as the data it
 * stores; this is unnecessarily slow.  I would rather have made a
 * base "Link" class for object types that could be stored as links
 * in a list, and then used object->next instead of all the
 * List Iterator stuff, but the end result was pure ugliness, so I
 * gave up.  At least this way, the same object can be in multiple
 * lists.
 * 
 * List type construction is facilitated by the following macros:
 * 
 *  - DeclareWvList(Type): creates a subclass named WvListType
 *     that contains pointers to Type.
 *  - DeclareWvList2(name, Type): as the above, but calls the
 *     resulting class by the specified name. 
 * 
 * 
 * "T" is the object type
 */
template<class T>
00186 class WvList : public WvListBase
{
    // copy constructor: not defined anywhere!
    WvList(const WvList &list);

public:
    /** Creates an empty linked list. */
00193     WvList()
      { }
    
    /**
     * Destroys the linked list.
     * 
     * Destroys any elements that were added with auto_free == true.
     * 
     */
00202     ~WvList()
      { zap(); }
      
    /** Invoked by subclasses after the linked list is first created. */
00206     void setup() {}
    
    /** Invoked by subclasses before the linked list is destroyed. */
00209     void shutdown() {}

    /**
     * Clears the linked list.
     * 
     * If destroy is true, destroys any elements that were added with auto_free == true.
     * 
     */
00217     void zap(bool destroy = true)
    {
        while (head.next)
            unlink_after(& head, destroy);
    }

    /**
     * Returns a pointer to the first element in the linked list.
     * 
     * The list must be non-empty.
     * 
     * Returns: the element pointer, possibly null
     */
00230     T *first() const
        { return (T*)head.next->data; }

    /**
     * Returns a pointer to the last element in the linked list.
     * 
     * The list must be non-empty.
     * 
     * Returns: the element pointer, possibly null
     */
00240     T *last() const
        { return (T*)tail->data; }

    /**
     * Adds the element after the specified link in the list.
     *
     * "link" is the link preceeding the desired location of the element
     *             to be inserted, non-null
     * "data" is the element pointer, may be null
     * "auto_free" is if true, takes ownership of the element
     * "id" is an optional string to associate with the element, or null
     */
00252     void add_after(WvLink *after, T *data, bool auto_free,
                  char *id = NULL )
    {
      (void)new WvLink((void *)data, after, tail, auto_free, id);
    }

    /**
     * Appends the element to the end of the list.
     *
     * "data" is the element pointer, may be null
     * "auto_free" is if true, takes ownership of the element
     * "id" is an optional string to associate with the element, or null
     */
00265     void append(T *data, bool auto_free, char *id = NULL)
      { add_after(tail, data, auto_free, id); }

    /**
     * Synonym for append(T*, bool, char*).
     * @see append(T*, bool, char*)
     */
00272     void add(T *data, bool auto_free, char *id = NULL)
        { append(data, auto_free, id); }

    /**
     * Prepends the element to the beginning of the list.
     *
     * "data" is the element pointer, may be null
     * "auto_free" is if true, takes ownership of the element
     * "id" is an optional string to associate with the element, or null
     */
00282     void prepend(T *data, bool auto_free, char *id = NULL)
      { add_after(&head, data, auto_free, id); }

    /**
     * Unlinks the specified element from the list.
     * 
     * Destroys the element if it was added with auto_free == true.
     * 
     * "data" is the element pointer, may be null
     */
00292     void unlink(T *data)
        { Iter i(*this); while (i.find(data)) i.unlink(); }

    /**
     * Unlinks the first element from the list.
     * 
     * Destroys the element if it was added with auto_free == true.
     * 
     */ 
00301     void unlink_first()
        { Iter i(*this); i.rewind(); i.next(); i.unlink(); }

    /**
     * Unlinks the element that follows the specified link in the list.
     * 
     * Destroys the element if it was added with auto_free == true and
     * destroy == true.
     * 
     * "after" is the link preceeding the element to be removed, non-null
     */ 
00312     void unlink_after(WvLink *after, bool destroy = true)
    {
        WvLink *next = after->next;
        T *obj = (destroy && next->auto_free) ?
            static_cast<T*>(next->data) : NULL;
        if (next == tail) tail = after;
        next->unlink(after);
      if (obj)
          WvTraits<T>::release(obj);
    }

    /**
     * The iterator type for linked lists.
     * 
     * An iterator instance does not initially point to any valid
     * elements in a list.  Before using, it must be reset using rewind()
     * which causes it to point to an imaginary element located before
     * the first elements in the list.  Then next() must be invoked
     * to incrementally move the iterator along the list to first element,
     * and then later to the second, third, and subsequent elements.
     * 
     */
00334     class Iter : public WvListBase::IterBase
    {
    public:
        /**
         * Binds the iterator to the specified list.
         * "l" is the list
         */
00341         Iter(const WvList &l) : IterBase(l)
            { }

        /**
         * Returns a pointer to the current element.
         * Returns: the element pointer, possibly null
         */
00348         T *ptr() const
            { return (T *)link->data; }

      WvIterStuff(T);
      
        /**
         * Unlinks the current element from the list and automatically
         * increments the iterator to point to the next element as if
         * next() had been called.
         */
00358         void unlink()
        {
          if (prev) ((WvList *)list)->unlink_after(prev);
          link = prev->next;
        }
      
        /**
         * Unlinks the current element from the list but unlike unlink()
         * automatically returns the iterator to the previous link in
         * the list such that next() must be called to obtain the
         * next element.
         * 
         * This version allows for writing neater loop structures since
         * an element can be unlinked in mid-traversal while still allowing
         * the iterator to be incremented at the top of the loop as usual.
         * 
         * Calling xunlink() twice in a row is currently unsupported.
         * 
         */
00377       void xunlink()
      {
          if (prev) ((WvList *)list)->unlink_after(prev);
          link = prev;
      }
    };
    
    /** The sorted iterator type for linked lists. */
00385     typedef class WvSorter<T, WvListBase, WvListBase::IterBase> Sorter;
};

#define DeclareWvList2(_classname_, _type_)  \
    typedef class WvList<_type_> _classname_ 

#define DeclareWvList(_type_) DeclareWvList2(_type_##List, _type_)


#endif // __WVLINKLIST_H

Generated by  Doxygen 1.6.0   Back to index