[CODE][STL] LexiSTL: LList<> (part 1)

From: Chris Jacobson (fear@ATHENET.NET)
Date: 04/28/98

As mentioned before in a post (concerning the scan snippet) that this
would be coming:

Its a great template class to use.  The only requirements: you must be
running a C++ CircleMUD, and have skill in coding, because I won't assist
in using this piece of code.  I do request that if you use it, that the
comment-header stay intact.  Its not that much to ask, really...

Here is the "info" part of the mail.

-- Features
* Multiple-Iterator Depth Safe:
    The list keeps a record of iterators that are running through the
    so if an item is removed from the list, it will automatically update
    all iterators, and safely remove it, not interfering with iteration
* Only increases memory usage a small amount:
    Only a +8 byte increase per list "head" (obj->contains,
    There is only a +4 byte increase per element, assuming you remove the
    now-unused NEXT pointers (one exception: if you use AutoEquip patch,
    leave the next_content pointer in the ObjData struct, but fix anything
    else that attempts to use next_content.)
* Append and Prepend elements (great for using the dynamic board patch,
    no longer need to reverse message order!)
* Customizable to dual-linked list if one wishes
* Customizable to allow Insert() and [] accesses (at a speed hit of
* I suppose if one wants, this could be made a regular class or, heaven
    forbid, a series of C function calls and structs.

-- Usage
To use LList<>, you would declare any "head" pointer of a linked list, to
be an instance of the LList class.  Candidates include obj->contains,
world[].people, world[].contents, object_list, etc.


LList<ObjData *> object_list;

class ObjData {
 LList<ObjData *> contains;

-- Methods
void      LList<T>::LList(void)    - Default constructor
void      LList<T>::LList(T)       - Constructor which starts with T as
first element
void      LList<T>::~LList(void)   - Destructor - clears the nodes
void      LList<T>::Prepend(T)     - Prepends T to the (beginning of the)
void      LList<T>::Append(T)      - Append T to the (end of the) list
void      LList<T>::Add(T)         - Same as LList<T>::Prepend(T)
void      LList<T>::Remove(T)      - Remove item from list
SInt32    LList<T>::Count(void)    - Return number of items in list
T         LList<T>::Top(void)      - Return head of list
bool      LList<T>::InList(T)      - Returns true if item is in list
void      LList<T>::UpdateIters(void)   - If you copy the contents of the
               list (obj->contains = obj2->contains) this must be called
               to fix any iters.  Note: I only used this twice, in REdit,
               when I copy over the room.  I don't believe it is really
               necessary anyways.

void      LListIterator<T>::LListIterator(LList<T> &)  - Default
void      LListIterator<T>::~LListIterator(void)       - Destructor
void      LListIteartor<T>::Update(LListNode<T> *)     - Internal
T         LListIterator<T>::Next(void)       - Return item and move up one
T         LListIterator<T>::Peek(void)       - Peek at current (unseen)
void      LListIterator<T>::Reset(void)      - Reset to start of list

LListNode<T> is an internal class, you never need to use it.

-- Iterating
Iterating can be done with one of two methods.  The first is a
quick-and-simple macro solution, which creates the iterator then deletes
it as soon as it is done:

START_ITER(iterator_name, variable, variable_type, list_to_iterate) {
} END_ITER(iterator_name)

Such as:

START_ITER(iter, ch, CharData *, world[room].people) {
} END_ITER(iter)

The second method, which is useful if you need to reuse the same iterator
(on the exact same list), is demonstrated in the scan snippet I submitted
recently, is leak-safe:

LListIterator<variable_type> iterator_name(list_to_iterate);

while ((variable = iter.Next()) {

As always, to reset the iterator to the beginning of the list, call:

-- Safety
If you have to return; (not break/etc) during mid-iteration, make sure to
still do an END_ITER() if you started with the START_ITER() macro.  If
you return during mid-iteration and did not use the START_ITER() macro,
but DID use a pointer (rather than an instance) of the iterator, remember
to delete the pointer.  Otherwise, the memory will leak.
Also, if you must use multiple iters in the same function, name each one
differently and avoid double-deleting or END_ITER()'ing the same iter.

To overcome the above two problems, you can use an (untested mailer code)
"safe" version of START_ITER and END_ITER:

#define START_ITER(iter, var, type, list)                                               \
        LListIterator<type> iter(list); \
        while ((var = iter.Next()))

#define END_ITER(iter)

     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     | http://democracy.queensu.ca/~fletcher/Circle/list-faq.html |

This archive was generated by hypermail 2b30 : 12/15/00 PST