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 Tue Oct 5 01:09:20 2004 for WvStreams by doxygen 1.3.7