List.h

Go to the documentation of this file.

/*  Copyright (C) 2003-2021 Free Electron Organization
    Any use of this software requires a license.  If a valid license
    was not distributed with this file, visit freeelectron.org. */

/** @file */

#ifndef __core_List_h__
#define __core_List_h__


#define FE_LIST_REF_DEBUG           FALSE

//* verify pointer usage with lists
#ifndef FE_LIST_STORE_CHECKPOINTER
#define FE_LIST_STORE_CHECKPOINTER  TRUE
#endif

#if FE_CODEGEN<=FE_DEBUG && FE_LIST_STORE_CHECKPOINTER
#define FE_LIST_CHECKPOINTER        TRUE
#else
#define FE_LIST_CHECKPOINTER        FALSE
#endif

namespace fe
{

/******************************************************************************
    WARNING:    this class must contain all data used by List;
                it is intended to be interchangable with a List through a void*

    TODO allocator policy
******************************************************************************/
/**************************************************************************//**
    @brief Type-nonspecific Base Functionality of fe::List <>

    @ingroup core

    Allows access to generic list without knowing the element type.
*//***************************************************************************/
class FE_DL_EXPORT ListCore
{
    protected:
        class   NodeCore;
    public:
        class   Context;

                ListCore(void);
virtual         ~ListCore(void);

                /// Set the AutoDestruct flag.  If TRUE, destruction of
                /// the list will attempt to destroy all the elements.
        void    setAutoDestruct(BWORD set)      { m_autodestruct=set; }

                /// Get the AutoDestruct flag.
        BWORD   autoDestruct(void)              { return m_autodestruct; }

                /// Returns the number of elements on the list.
        U32     size(void) const                { return m_length; }

                /// Remove and delete nodes, but don't delete contents
        void    removeAll(void);

                /// Moves the node at the first context before the
                /// node at the second context.
        BWORD   moveNodeBefore(Context& from,Context& to)
                {   return coreMoveNode(true,from,to); }
                /// Moves the node at the first context after the
                /// node at the second context.
        BWORD   moveNodeAfter(Context& from,Context& to)
                {   return coreMoveNode(false,from,to); }

                /// Returns TRUE if the context is before the first element.
        BWORD   isAtHeadNull(Context& rContext) const
                {   return !m_length ||
                            (!rContext.current() && !rContext.isAtTailNull());}
                /// Returns TRUE if the context is after the last element.
        BWORD   isAtTailNull(Context& rContext) const
                {   return !m_length ||
                            (!rContext.current() && rContext.isAtTailNull()); }

    /**********************************************************************//**
        @brief A view state into an fe::List <>

        @ingroup core

        Do not access Context members except indirectly through List.

        If you like iterators better, use fe::List::Iterator which
        wraps an fe::List::Context.

        Context is similar to an iterator except that it does not contain
        a pointer to an List<>.  All access to an List<> is done directly
        through List<> member functions with an Context argument.
        This means that
            * Context is generic and does not need to be templated.
            * The context is very lightweight and has no template
                instantiation.
            * No special permissions are needed for context to list accesses.
            * Your code always explicitly says which list it is accessing.
    *//***********************************************************************/
    class FE_DL_EXPORT Context
    {
        public:
                        Context(void)   { init(); }

                        /// Copy constructor
                        Context(const Context& operand)
                        {
#if FE_LIST_STORE_CHECKPOINTER
                            FE_MAYBE_UNUSED(m_pListCore);
#endif
                            init();
                            setCurrent(operand.m_pCurrent);
                            setAtTailNull(operand.isAtTailNull());
                        }

    virtual             ~Context(void)
                        {
//                          feLog("%p Context dec %p\n",this,m_pCurrent);
                            if(m_pCurrent)
                                m_pCurrent->decRef();
                        }

                        /// Copy state from another context
            Context     &operator=(Context& operand)
                        {
                            setCurrent(operand.current());
                            setAtTailNull(operand.isAtTailNull());
                            return *this;
                        }


                        /** @brief Reinitialize state

                            @internal */
            void        init(void)
                        {
                            m_pCurrent=NULL;
                            m_at_tail=false;
#if FE_LIST_CHECKPOINTER
                            m_pListCore=NULL;
#endif
                        }

                        /** @brief Get current position on list

                            @internal */
            NodeCore*   current(void)
                        {
                            checkValid();
                            return m_pCurrent;
                        }

                        /** @brief Set current position on list

                            @internal */
            void        setCurrent(NodeCore* set)
                        {
//                          feLog("%p Context set %p -> %p\n",
//                                  (U32)this,(U32)m_pCurrent,(U32)set);
                            if(m_pCurrent==set)
                                return;

                            if(m_pCurrent)
                                m_pCurrent->decRef();
                            if(set)
                            {
                                FEASSERT(set->valid());
                                set->incRef();
                            }
                            m_pCurrent=set;
                        }

                        /** @brief Set whether context is after the tail

                            @internal */
            void        setAtTailNull(BWORD set)            { m_at_tail=set; }

                        /** @brief Get whether context is after the tail

                            @internal */
            BWORD       isAtTailNull(void) const
                        {
                            return m_at_tail;
                        }

        private:
            void        checkValid(void)
                        {
                            // if m_pCurrent is fine
                            if(!m_pCurrent || m_pCurrent->valid())
                                return;

                            // find heir
                            NodeCore* heir=m_pCurrent;
                            while(heir && !heir->valid())
                                heir=heir->heir();

                            // if good heir, copy
                            if(heir && heir->valid())
                            {
//                              fe_printf("heir %p\n",heir);
                                setCurrent(heir);
                                setAtTailNull(false);
                            }
                            // reset, reset
                            else
                            {
                                setCurrent(NULL);
                                setAtTailNull(false);
                            }
                        }

            NodeCore*   m_pCurrent;
            BWORD       m_at_tail;

#if FE_LIST_CHECKPOINTER
        public:
                        /** @brief Store pointer to current list for debug

                            @internal */
            void        setCorePointer(const ListCore *pSet)
                        {
                            m_pListCore=pSet;
                        }

                        /** @brief Verify that we are accessing the
                            correct list

                            @internal */
            BWORD       checkCorePointer(const ListCore *pCheck) const
                        {
                            if(pCheck && m_pListCore && m_pListCore!=pCheck)
                                feLog("Context::CheckCorePointer"
                                        "(%p) does not match %p\n",
                                        pCheck,m_pListCore);
                            FEASSERT(!pCheck || !m_pListCore ||
                                    m_pListCore==pCheck);
                            return (!pCheck || !m_pListCore ||
                                    m_pListCore==pCheck);
                        }
#endif
#if FE_LIST_STORE_CHECKPOINTER
        private:
    const   ListCore*   m_pListCore;
#endif
    };

    protected:

    class FE_DL_EXPORT NodeCore: public Counted
    {
        public:
                        NodeCore(void):
                            m_valid(TRUE),
                            m_pPrevious(NULL),
                            m_pNext(NULL),
                            m_pHeir(NULL)
                        {
                            acquire();
                        }

    virtual             ~NodeCore(void)                                     {}

                        /** @brief Set pointer to node before this one

                            @internal */
            void        setPrevious(NodeCore* set)      { m_pPrevious=set; }
                        /** @brief Get pointer to node before this one

                            @internal */
            NodeCore*   previous(void) const            { return m_pPrevious;}

                        /** @brief Set pointer to node after this one

                            @internal */
            void        setNext(NodeCore* set)          { m_pNext=set; }
                        /** @brief Get pointer to node after this one

                            @internal */
            NodeCore*   next(void) const                { return m_pNext; }

                        /** @brief Set pointer to heir node

                            @internal */
            void        setHeir(NodeCore* set)          { m_pHeir=set; }
                        /** @brief Get pointer to heir node

                            @internal */
            NodeCore*   heir(void) const                { return m_pHeir; }

                        /** @brief Set flag indicating if node is in a list

                            @internal */
            void        setValid(BWORD set)             { m_valid=set;}
                        /** @brief Get flag indicating if node is in a list

                            @internal */
            BWORD       valid(void) const               { return m_valid; }

                        /** @brief Mark node as invalid and determine an heir

                            This happens when the node is removed
                            from its list.  It may still have references.

                            @internal */
            void        abandon(void)
                        {
                            const int references=releaseInternal();
#if FE_LIST_REF_DEBUG
                            feLog("%p Node::Abandon() %d\n",
                                    this,references+1);
#endif
                            // if someone is still pointing at this node,
                            // leave a trail to a potentially valid node
                            if(references)
                            {
                                if(m_pNext)
                                    m_pHeir=m_pNext;
                                else
                                    m_pHeir=m_pPrevious;

                                if(m_pHeir)
                                    m_pHeir->incRef();
#if FE_LIST_REF_DEBUG
                                feLog("%p Node heir=%p\n",this,m_pHeir);
#endif

                                setValid(false);
                            }
                            else
                            {
                                delete this;
                            }
                        }

                        /** @brief Increment reference count

                            @internal */
            void        incRef(void)
                        {
#if FE_LIST_REF_DEBUG
                            const int references=releaseInternal();
                            feLog("%p Node::IncRef() %d->%d\n",
                                    this,references,references+1);
#endif
                            acquire();
                        }
                        /** @brief Decrement reference count

                            @internal */
            void        decRef(void);

    protected:

            BWORD       m_valid;

            NodeCore*   m_pPrevious;
            NodeCore*   m_pNext;
            NodeCore*   m_pHeir;
    };

        NodeCore*   coreGetElement(I32 index) const;
        NodeCore*   coreInsert(BWORD before,Context& rContext,
                            NodeCore* existingNode);
        BWORD       coreRemoveNode(NodeCore* node);
        BWORD       coreMoveNode(BWORD before,Context& from,Context& to);

        NodeCore*   m_pHead;
        NodeCore*   m_pTail;
        I32         m_length;
        BWORD       m_autodestruct;

    protected:
virtual NodeCore*   newNode(void) const                                     =0;
        void        internalToHead(Context& rContext) const;
        void        internalPostIncrement(Context& rContext) const;
        void        internalDetachNode(NodeCore* node);
        NodeCore*   internalGetCurrent(Context& rContext) const
                    {
#if FE_LIST_CHECKPOINTER
                    rContext.checkCorePointer(this);
#endif
                    return rContext.current();
                    }
};

/**************************************************************************//**
    @brief Fully Bidirectional Doubly-Linked List

    @ingroup core

    Why would you use this list?
        - Truly bidirectional: no need for reverse lists or reverse iterators
        - Retainable iterators: designed to endure long term access
        - Complete iterators: you don't have to go back to the list for any
            subset of the functionality.
            The iterators can do everything.
        - Delete anything you want, whenever you want:
            you can erase nodes that other contexts are looking at or even
            a list itself with still outstanding contexts.
            Cascading references will adapt on next usage as though the other
            contexts were watching along with every step (but they aren't).

    What is a Context?
        - A Context is basically the typeless state of an Iterator.
            But really, the Iterator is a Context permanently associated with a
            specific instance of a typed List.
        - You can manipulate a List through Context's, Iterator's, or directly
            through the List itself.
        - Context's can be reused between multiple Lists of different types,
            but Iterator's don't require you to keep track of which List
            you're looking into.

    Since the List is fully bidirectional, there is a NULL entry at both
    beginning and the end.  The toHead and toTail methods move to the first
    entry next to the NULL on either end (if a non-NULL entry exists).

    If SearchForContent() is to be used and type T has non-trivial data
    complexity, the operator == should probably be defined for type T.
    Some examples of data complexity are:
        - pointer data members
        - data members that do not contribute to 'equality'
        - data whose equality can be more efficiently determined with something
          other than the default bytewise comparison.
        - fuzzy or soft data

    A new Context defaults to pointing at the NULL at the start of the list.
    A new Iterator defaults to pointing at the head of the list.

    Example using a fe::List::Iterator:
    @code
        List<MyClass*> list;
        List<MyClass*>::Iterator iterator(list);
        MyClass* one=new MyClass();

        // add element
        list.append(one);

        // read element
        MyClass* two= *iterator;

        // do something to all elements
        MyClass* node;
        iterator.toHead();
        while((node= *iterator++)!=NULL)
        {
            node->doSomething();
        }
    @endcode

    Example using a fe::ListCore::Context:
    @code
        List<MyClass*> list;
        ListCore::Context context;
        MyClass* one=new MyClass();

        // add element
        list.append(one);

        // read element
        MyClass* two=list.current(context);

        // do something to all elements
        MyClass* node;
        list.toHead(context);
        while( (node=list.postIncrement(context)) != NULL)
        {
            node->doSomething();
        }
    @endcode

    No Context's or Iterator's will lose place if elements are removed,
    even if removed with a different Context or Iterator.
    Reference counting prevents invalid pointers and heir chains
    follow destruction chains to find valid nodes.

    Note that much of the functionality of this class is implemented in the
    non-template class ListCore.  This is done to reduce template
    instantiation size.

    By using setAutoDestruct(true), all elements remaining
    on the list are deleted when the list is destructed.

    WARNING: if pointer-to elements were not created with new(),
    failures during auto-delete will probably occur.  Note that
    setAutoDestruct(true) is especially precarious when elements may be in
    more than one list.
    In that case, it is very possible for elements to be deleted
    that are still members of other lists.

    NOTE: Modern mechanisms are in place that attempt to do the right delete
    operation for a variety of types.  See fe::deleteByType<> for details.
*//***************************************************************************/
template <typename T>
class FE_DL_EXPORT List: public ListCore
{
    private:

    class FE_DL_EXPORT Node: public NodeCore
    {
        public:
                    Node(void)
                    {
                        m_entry=defaultByType<T>(T());
#if FE_COUNTED_TRACK
                        setName(FE_TYPESTRING(T));
                        trackReference(*(void**)&m_entry,this,verboseName());
#endif
                    }
    virtual         ~Node(void)
                    {
#if FE_COUNTED_TRACK
                        untrackReference(*(void**)&m_entry,this);
#endif
                    }

                    /** @brief Set the payload

                        @internal */
            void    setEntry(T& set)
                    {
#if FE_COUNTED_TRACK
                        untrackReference(*(void**)&m_entry,this);
                        trackReference(*(void**)&set,this,verboseName());
#endif
                        m_entry=set;
                    }
                    /** @brief Get the payload

                        @internal */
            T       entry(void) const                   { return m_entry; }
                    /** @brief Get the location of the payload

                        @internal */
            T*      storage(void)                       { return &m_entry; }

#if FE_COUNTED_STORE_TRACKER
const   String      verboseName(void) const
                    {   return "List::Node "+name(); }
#endif
        private:

            T       m_entry;
    };

virtual NodeCore*   newNode(void) const
                    {
                        NodeCore* pNode=new Node();
#if FE_COUNTED_TRACK
                        pNode->trackReference(
                                const_cast<void*>((const void*)this),
                                "List::newNode");
#endif
                        return pNode;
                    }

    public:
                List(void)
                {
#if FE_COUNTED_TRACK
                    //* Generally, there is no need to register a list since it
                    //* will usually be member of an object already registered.
//                  Counted::registerRegion(this,
//                          sizeof(List),
//                          String("List<")+FE_TYPESTRING(T)+">");
#endif
                }
virtual         ~List(void)
                {
#if FE_COUNTED_TRACK
//                  Counted::deregisterRegion(this);
#endif
                    if(m_autodestruct)
                        deleteAll();
                    else
                        removeAll();
                }

    /*** STANDARD RULES
        prefix
        const MyIncrementableClass& operator++();
        const MyIncrementableClass& operator--();
        postfix
        MyIncrementableClass operator++(int);
        MyIncrementableClass operator--(int);

        a and b values of type X
        u, m    identifiers
        r       value of type X&
        t       value of type T

        X u     u might have a singular value
        X()     X() might be singular
        X(a)    copy constructor, a == X(a)
        X u(a)  copy constructor, u == a
        X u = a assignment, u == a
        a == b,
        a != b  return value convertible to bool
        *a = t  result is not used
        *a      return value convertible to T&
        a->m    equivalent to (*a).m
        ++r     returns X&
        r++     return value convertable to const X&
        *r++    returns T&
        --r     returns X&
        r--     return value convertable to const X&
        *r--    returns T&
    */
    /*********************************************************************//**
        @brief Type-specific Iterator for an fe::List <>

        @ingroup core

        This is a templated wrapper for the type-non-specific
        fe::ListCore::Context.
    *//**********************************************************************/
    class FE_DL_EXPORT Iterator: protected Context
    {
        public:
                        Iterator(List<T>& rList): m_pList(&rList) { toHead(); }
                        Iterator(const Iterator& rOperand): Context(rOperand),
                                m_pList(rOperand.m_pList)                   {}
            Iterator&   operator=(Iterator& rOperand)
                        {   Context::operator=(rOperand);
                            m_pList=rOperand.m_pList;
                            return *this; }
                        /// @brief Compare by content (not by pointer)
            BWORD       operator==(const Iterator& rOperand) const
                        { return operator*()==rOperand.operator*(); }
                        /// @brief Inverse compare by content (not by pointer)
            BWORD       operator!=(const Iterator& rOperand) const
                        { return operator*()!=rOperand.operator*(); }
                        /// @brief Use the entry pointed at
            T           operator->(void)
                        {   return m_pList->current(*this); }
                        /// @brief Return the entry pointed at
            T           operator*(void)
                        {   return m_pList->current(*this); }
                        /// @brief Pre Increment
            Iterator&   operator++(void)
                        {   m_pList->preIncrement(*this);
                            return *this; }
                        /// @brief Pre Decrement
            Iterator&   operator--(void)
                        {   m_pList->preDecrement(*this);
                            return *this; }
                        /// @brief Post Increment
            Iterator    operator++(int)
                        {   Iterator iterator=*this;
                            m_pList->postIncrement(*this);
                            return iterator; }
                        /// @brief Post Decrement
            Iterator    operator--(int)
                        {   Iterator iterator=*this;
                            m_pList->postDecrement(*this);
                            return iterator; }

                        /// @brief Point the iterator at the first entry.
            T           toHead(void)        { return m_pList->toHead(*this); }
                        /// @brief Point the iterator at the last entry.
            T           toTail(void)        { return m_pList->toTail(*this); }
                        /// @brief Returns TRUE if pointing to the head NULL
            BWORD       isAtHeadNull(void)
                        {   return m_pList->isAtHeadNull(*this); }
                        /// @brief Returns TRUE if pointing to the tail NULL
            BWORD       isAtTailNull(void)
                        {   return m_pList->isAtTailNull(*this); }
                        /// @brief Add a new entry directly before this iterator
            T*          insertBefore(T pEntry)
                        {   return m_pList->insertBefore(*this,pEntry); }
                        /// @brief Add a new entry directly after this iterator
            T*          insertAfter(T pEntry)
                        {   return m_pList->insertAfter(*this,pEntry); }
                        /** @brief Move the entry at this iterator to the
                            position before the argument */
            BWORD       moveCurrentBefore(const Iterator& rOperand)
                        {   return m_pList->moveNodeBefore(*this,rOperand); }
                        /** @brief Move the entry at this iterator to the
                            position after the argument */
            BWORD       moveCurrentAfter(const Iterator& rOperand)
                        {   return m_pList->moveNodeAfter(*this,rOperand); }
                        /// @brief Remove this entry from the list
            BWORD       remove(void)
                        {   return m_pList->removeCurrent(*this); }
                        /** @brief Replace this entry with a new object

                            The previous entry is returned. */
            T           replace(T pSubstitute)
                        {   return m_pList->replaceCurrent(*this,pSubstitute); }
                        /// @brief Remove this entry from the list and delete it
            BWORD       deleteEntry(void)
                        {   return m_pList->deleteCurrent(*this); }
                        /** @brief Point the iterator at the first entry with
                            a given pointer */
            T           searchForElement(const T pEntry)
                        {   return m_pList->searchForElement(*this,pEntry); }
                        /** @brief Point the iterator at the first entry
                            equivalent to the given pointed-to value */
            T           searchForContent(const T pValue)
                        {   return m_pList->searchForContent(*this,pValue); }
            List*       list(void)  { return m_pList; }
        private:
            List*       m_pList;
    };

                /** Insert a new element before the context.
                    Returns the location of the new element or NULL if the
                    internal node allocation failed. */
        T*      insertBefore(Context& rContext,T pEntry)
                {   Node* pNode=(Node *)coreInsert(true,rContext,NULL);
                    pNode->setEntry(pEntry); return pNode->storage(); }
                /** Insert a new element after the context.
                    Returns the location of the new element or NULL if the
                    internal node allocation failed. */
        T*      insertAfter(Context& rContext,T pEntry)
                {   Node* pNode=(Node *)coreInsert(false,rContext,NULL);
                    pNode->setEntry(pEntry); return pNode->storage(); }
                /** Insert a new element at the beginning of the list.
                    Returns the location of the new element or NULL if the
                    internal node allocation failed. */
        T*      prepend(T pEntry)
                {
                    Context rContext;
                    rContext.setCurrent(m_pHead);
#if FE_LIST_CHECKPOINTER
                    rContext.setCorePointer(this);
#endif
                    Node* pNode=(Node*)coreInsert(true,rContext,NULL);
                    if(!pNode)
                        return (T*)NULL;
                    pNode->setEntry(pEntry);
                    return pNode->storage();
                }
                /** Insert a new element at the end of the list.
                    Returns the location of the new element or NULL if the
                    internal node allocation failed. */
        T*      append(T pEntry)
                {
                    Context rContext;
                    rContext.setCurrent(m_pTail);
#if FE_LIST_CHECKPOINTER
                    rContext.setCorePointer(this);
#endif
                    Node* pNode=(Node*)coreInsert(false,rContext,NULL);
                    if(!pNode)
                        return (T*)NULL;
                    pNode->setEntry(pEntry);
                    return pNode->storage();
                }

                /// Append a copy of an entire list of identical type
        void    append(List<T>& list)
                {
                    T pT;
                    Context rContext;
                    list.toHead(rContext);
                    while((pT=list.postIncrement(rContext))!=NULL)
                        append(pT);
                }

                /** This is the straightforward remove implementation.  This
                    Remove() will look for the entry in the list by simply
                    checking each member entry in order.  This can be very slow
                    in some cases.  See remove(T entry, Context& hint)
                    for a faster alternative. */
        BWORD   remove(T pEntry)
                {
                    Context context;
                    Node* pNode;
                    T pEntry2;

                    internalToHead(context);
                    while((pNode=(Node*)internalGetCurrent(context)) != NULL
                            && (pEntry2=pNode->entry()) !=
                            defaultByType<T>(T()))
                    {
                        if(pEntry2==pEntry)
                            return coreRemoveNode(context.current());
                        else
                            internalPostIncrement(context);
                    }

                    return false;
                }

                /** This remove() method uses a hint Context to check
                    current, next, and prev nodes (in that order) before
                    reverting to a head to tail scan.  In most cases this
                    significantly reduces execution time. */
        BWORD   remove(T pEntry, Context& hint)
                {
#if FE_LIST_CHECKPOINTER
                    hint.checkCorePointer(this);
#endif

                    NodeCore* pNodeCore;
                    if((pNodeCore=hint.current()))
                    {
                        if(((Node*)pNodeCore)->entry()==pEntry)
                            return coreRemoveNode(pNodeCore);
                        else if(pNodeCore->next() &&
                                ((Node*)pNodeCore->next())->entry()==pEntry)
                            return coreRemoveNode(pNodeCore->next());
                        else if(pNodeCore->previous() &&
                                ((Node*)pNodeCore->previous())->entry()==pEntry)
                            return coreRemoveNode(pNodeCore->previous());
                    }

                    return remove(pEntry);
                }


                /// Remove the current node on the given context.
        BWORD   removeCurrent(Context& rContext)
                {
                    Node* pNode=(Node*)rContext.current();

                    if(pNode)
                    {
                        T ptr=pNode->entry();
                        BWORD success=coreRemoveNode(pNode);
                        FEASSERT(success);
                        return success;
                    }

                    return false;
                }

                /// Replace the current pointer on the given context.
        T       replaceCurrent(Context& rContext,T pSubstitute)
                {
                    Node* pNode=(Node*)rContext.current();
                    if(pNode)
                    {
                        T pCurrent=pNode->entry();
                        pNode->setEntry(pSubstitute);
                        return pCurrent;
                    }
                    return defaultByType<T>(T());
                }
/*
                template<bool B>
        void    deleteIfTrue(List<T,B>* pList,T t)          {}
        void    deleteIfTrue(List<T,true>* pList,T pT)      { delete pT; }
*/
                /// Remove all nodes and delete their pointers.
        void    deleteAll(void)
                {
                    while( m_pHead != NULL)
                    {
                        T pEntry=((Node*)m_pHead)->entry();
#if FE_CODEGEN<=FE_DEBUG
                        BWORD result=
#endif
                                coreRemoveNode(m_pHead);
                        FEASSERT(result);
//                      deleteIfTrue(this,pEntry);
                        deleteByType(pEntry);
                    }
                }

                /// Remove and delete the current node on the given context.
        BWORD   deleteCurrent(Context& rContext)
                {
                    Node* node=rContext.current();

                    if(node)
                    {
                        T pEntry=node->entry();
                        BWORD success=coreRemoveNode(node);
                        FEASSERT(success);
//                      deleteIfTrue(this,pEntry);
                        deleteByType(pEntry);
                        return success;
                    }

                    return false;
                }

                /** Remove and delete the first entry that matches the argument.
                    If a match is not found, the argument is still deleted. */
        BWORD   deleteElement(T pEntry)
                {
                    BWORD result=remove(pEntry);
                    deleteByType(pEntry);

                    return result;
                }

                /** Rewind the context to the beginning of the list and return
                    the first element. */
        T       toHead(Context& rContext) const
                {
                    rContext.setCurrent(m_pHead);
#if FE_LIST_CHECKPOINTER
                    rContext.setCorePointer(this);
#endif
                    return current(rContext);
                }

                /** Move the context to the end of the list and return
                    the last element. */
        T       toTail(Context& rContext) const
                {
                    rContext.setCurrent(m_pTail);
#if FE_LIST_CHECKPOINTER
                    rContext.setCorePointer(this);
#endif
                    return current(rContext);
                }

                /** @brief Return the location of the first element matching
                    the given pointer or smart pointer

                    Only the pointers are compared.
                    Matches are not made by the content they point to. */
        T*      searchForElement(Context& rContext,const T pEntry) const
                {
                    Node* pNode;
                    T pEntry2;

                    internalToHead(rContext);
                    while((pNode=(Node*)internalGetCurrent(rContext)) != NULL
                            && (pEntry2=pNode->entry()) !=
                            defaultByType<T>(T()))
                    {
                        if(pEntry2==pEntry)
                            return ((Node*)rContext.current())->storage();
                        else
                            internalPostIncrement(rContext);
                    }

                    return NULL;
                }

                /** @brief Return the location of the first pointed-to
                    element with the same value

                    The elements are compared to the contents of *value.
                    The value argument is passed by pointer instead of
                    value or reference to prevent a requirement the
                    T be an instantiable class. */
        T*      searchForContent(Context& rContext,const T pValue) const
                {
                    if(!pValue)
                        return NULL;

                    toHead(rContext);

                    T pEntry2;
                    while( (pEntry2=current(rContext)) != NULL)
                    {
                        if(*pEntry2==*pValue)
                            return ((Node*)rContext.current())->storage();
                        else
                            postIncrement(rContext);
                    }

                    return NULL;
                }

                /// Return the current element before incrementing to the next
        T       postIncrement(Context& rContext) const
                {
                    Node* pNode,*pNext;

                    if((pNode=(Node*)rContext.current())!=NULL)
                    {
                        rContext.setCurrent(pNext=(Node*)pNode->next());
                        if(!pNext)
                            rContext.setAtTailNull(true);
                        return (pNode->entry());
                    }
                    else if(!isAtTailNull(rContext))
                        rContext.setCurrent(m_pHead);

                    return defaultByType<T>(T());
                }

                /** Return the current element before decrementing to the
                    previous */
        T       postDecrement(Context& rContext) const
                {
                    Node* pNode=(Node*)rContext.current();

                    if(pNode)
                    {
                        rContext.setCurrent(pNode->previous());
                        rContext.setAtTailNull(false);
                        return pNode->entry();
                    }
                    else if(isAtTailNull(rContext))
                        rContext.setCurrent(m_pTail);

                    rContext.setAtTailNull(false);
                    return defaultByType<T>(T());
                }

                /// Return the first element of the list (no context required)
        T       head(void) const
                {   return m_pHead?
                            ((Node*)m_pHead)->entry(): defaultByType<T>(T()); }

                /// Return the last element of the list (no context required)
        T       tail(void) const
                {   return m_pTail?
                            ((Node*)m_pTail)->entry(): defaultByType<T>(T()); }

                /// Return the current element of the context.
        T       current(Context& rContext) const
                {
#if FE_LIST_CHECKPOINTER
                    rContext.checkCorePointer(this);
#endif
                    Node* pNode=(Node*)rContext.current();
                    return pNode? pNode->entry(): defaultByType<T>(T());
                }

                //* trivial convenience functions

                /// Increment the context and return the next element
        T       preIncrement(Context& rContext) const
                {   postIncrement(rContext);
                    return current(rContext); }

                /// Decrement the context and return the previous element
        T       preDecrement(Context& rContext) const
                {   postDecrement(rContext);
                    return current(rContext); }

                /** Get an element by index.  This is not an array, so this
                    can be an inefficient operation */
        T       operator[](I32 index) const
                {   Node* pNode=(Node*)coreGetElement(index);
                    return pNode? pNode->entry(): defaultByType<T>(T()); }
};

} // namespace

#endif // __core_List_h__