http://www.ousob.com --- Legacy Redefined OuSob - File: /wwwroot/clipx/usr/include/wvstreams/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>. * */ class WvListBase { WvListBase(const WvListBase &l); // copy constructor - not actually defined anywhere! private: //This is private to force people to pass by reference, not by value WvListBase& operator= (const WvListBase &l); public: WvLink head, *tail; /** Creates an empty linked list. */ 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 */ 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>. * */ class IterBase { public: const WvListBase *list; WvLink *link, *prev; /** * Binds the iterator to the specified list. * "l" is the list */ 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. */ 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 */ 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 */ 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. */ 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. * * In order to locate multiple matching elements, first call find() * and then use find_next(). * * Returns: the current WvLink pointer, or null if no such element * was found */ WvLink *find(const void *data); /** * Repositions the iterator over the element that matches the * specified value. * * Uses pointer equality (object identity) as the criteria for * finding the matching element. * * Returns: the current WvLink pointer, or null if no such element * was found */ WvLink *find_next(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 autofree * 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> class WvList : public WvListBase { // copy constructor: not defined anywhere! WvList(const WvList &list); public: /** Creates an empty linked list. */ WvList() { } /** * Destroys the linked list. * * Destroys any elements that were added with autofree == true. * */ ~WvList() { zap(); } /** Invoked by subclasses after the linked list is first created. */ void setup() {} /** Invoked by subclasses before the linked list is destroyed. */ void shutdown() {} /** * Clears the linked list. * * If destroy is true, destroys any elements that were added with autofree == true. * */ 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 */ 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 */ 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 * "autofree" is if true, takes ownership of the element * "id" is an optional string to associate with the element, or null */ void add_after(WvLink *after, T *data, bool autofree, char *id = NULL ) { (void)new WvLink((void *)data, after, tail, autofree, id); } /** * Appends the element to the end of the list. * * "data" is the element pointer, may be null * "autofree" is if true, takes ownership of the element * "id" is an optional string to associate with the element, or null */ void append(T *data, bool autofree, char *id = NULL) { add_after(tail, data, autofree, id); } /** * Synonym for append(T*, bool, char*). * @see append(T*, bool, char*) */ void add(T *data, bool autofree, char *id = NULL) { append(data, autofree, id); } /** * Prepends the element to the beginning of the list. * * "data" is the element pointer, may be null * "autofree" is if true, takes ownership of the element * "id" is an optional string to associate with the element, or null */ void prepend(T *data, bool autofree, char *id = NULL) { add_after(&head, data, autofree, id); } /** * Unlinks the specified element from the list. * * Destroys the element if it was added with autofree == true. * * "data" is the element pointer, may be null */ 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 autofree == true. * */ 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 autofree == true and * destroy == true. * * "after" is the link preceeding the element to be removed, non-null */ void unlink_after(WvLink *after, bool destroy = true) { WvLink *next = after->next; T *obj = (destroy && next->get_autofree()) ? 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. * */ class Iter : public WvListBase::IterBase { public: /** * Binds the iterator to the specified list. * "l" is the list */ Iter(const WvList &l) : IterBase(l) { } /** * Returns a pointer to the current element. * Returns: the element pointer, possibly null */ T *ptr() const { return (T *)link->data; } WvIterStuff(T); /** * Returns the state of autofree for the current element. */ bool get_autofree() const { return link->get_autofree(); } /** * Sets the state of autofree for the current element. */ void set_autofree(bool autofree) { link->set_autofree(autofree); } /** * Unlinks the current element from the list and automatically * increments the iterator to point to the next element as if * next() had been called. */ void unlink(bool destroy = true) { if (prev) ((WvList *)list)->unlink_after(prev, destroy); 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. * */ void xunlink(bool destroy = true) { if (prev) ((WvList *)list)->unlink_after(prev, destroy); link = prev; } }; /** The sorted iterator type for linked lists. */ 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