base_dlist.hh

Go to the documentation of this file.

/*
 * LEGAL:   COPYRIGHT (C) 2004 JIM E. BROOKS
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE VERSION 2 (GPL 2).
 *****************************************************************************/

#ifndef BASE_DLIST_HH
#define BASE_DLIST_HH 1

namespace base {

template<typename T,typename LOCK> class Dlist;
template<typename T,typename LOCK> class DlistIterator;

template<typename T,typename LOCK=FastLock>
class Dlink
{

friend class Dlist<T,LOCK>;
private:
    // ctor/dtor are private: only Dlist can create/delete Dlinks.
    Dlink( void ) { SET_TYPESIG( this, TYPESIG_DLINK ); }
    ~Dlink()      { INVALIDATE_TYPESIG( this, TYPESIG_DLINK ); }
    Dlink*  mPrev;  // next link
    Dlink*  mNext;  // previous link
    T*      mObj;   // pointer to actual object
public:
    // Client can get object pointer but can't reassign it.
    T*          Obj( void ) const { CHECK_TYPESIG(this,TYPESIG_DLINK); return mObj; }
    
};

template<typename T,typename LOCK=FastLock>  // or LOCK can be NoLock
class Dlist : public Shared, public SemiThreadable
{


    // Sentinel never has an object, but use a different address than NULL
    // to distinguish from other dlinks that may have NULL pointers.
#define DLIST_SENTINEL_NULL_OBJ  (reinterpret_cast<T*>(ILLEGAL_PTR))

    // mHead should always point to sentinel.  Sentinel should never have an object.
#define CHECK_DLIST_HEAD_TAIL() \
    CHECK_TYPESIG( mHead, TYPESIG_DLINK ); \
    CHECK_TYPESIG( mTail, TYPESIG_DLINK ); \
    ASSERT( mHead->mObj == DLIST_SENTINEL_NULL_OBJ );

public:
    enum eDestroy { DESTROY, KEEP };

public:
    Dlist( eDestroy destroy = DESTROY )
    {
        // Allows Dlist to be on stack while lock is on heap.
        THREAD_CODE( mInstanceLock = new LOCK; )

        SET_TYPESIG( this, TYPESIG_DLIST );

        mDestroy = destroy;

        // Make the sentinel which points to itself.
        mHead = mTail = new Dlink<T>;
        mHead->mObj = DLIST_SENTINEL_NULL_OBJ;  // sentinel never has an object
        mHead->mPrev = mHead->mNext = mTail->mPrev = mTail->mNext = mHead;
    }

public:
    ~Dlist()
    {
        Clear();       // delete linked objects
        delete mHead;  // delete hidden sentinel (Clear() kept it)
        THREAD_CODE( delete mInstanceLock; )
        INVALIDATE_TYPESIG( this, TYPESIG_DLIST );
    }

public:
    void
    Clear( void )
    {
    THREAD_CODE( typename LOCK::Auto autolock( mInstanceLock ); )

        // Delete links (and optionally the linked objects) but keep the sentinel.
        // Sentinel is needed if after clearing, new links are added.
        Dlink<T>* dlink = mHead->mNext;
        while ( dlink != dlink->mNext )
        {
            //ASSERT( dlink->mObj != NULL );  // allow client to assign NULL object
            CHECK_TYPESIG(dlink,TYPESIG_DLINK);
            CHECK_TYPESIG(dlink->mNext,TYPESIG_DLINK);

            Dlink<T>* next = dlink->mNext;  // before dlink is unlinked (don't saw off branch)
            if ( mDestroy == DESTROY )
                delete dlink->mObj;
            Unlink( dlink );  // delete the link struct itself
            dlink = next;
        }
        ASSERT( mHead == mTail );  // head==tail==sentinel
        CHECK_DLIST_HEAD_TAIL();
    }

public:
    Dlink<T>*  // Dlink<> is a safe ptr as it destructor is private
    Prepend( T* obj )
    {
    THREAD_CODE( typename LOCK::Auto autolock( mInstanceLock ); )

    CHECK_DLIST_HEAD_TAIL();

        // As a sentinel is used, head/tail always point to something,
        // and there is always a previous and a next link.

        // New link struct for this object.
        Dlink<T>* dlink = new Dlink<T>;

        // Insert new link between head/sentinel link and second link.
        if ( UX(mHead == mTail) ) mTail = dlink; // if dlist is empty, new link is the tail
        dlink->mNext = mHead->mNext;
        dlink->mPrev = mHead;
        dlink->mObj  = obj;
        mHead->mNext = dlink->mNext->mPrev = dlink;
        CHECK_TYPESIG(dlink->mNext,TYPESIG_DLINK);
        CHECK_TYPESIG(dlink->mPrev,TYPESIG_DLINK);
        CHECK_DLIST_HEAD_TAIL();
        return dlink;
    }

public:
    Dlink<T>*
    Append( T* obj )
    {
    THREAD_CODE( typename LOCK::Auto autolock( mInstanceLock ); )

    CHECK_DLIST_HEAD_TAIL();

        // As a sentinel is used, head/tail always point to something,
        // and there is always a previous and a next link.
        // New link struct for this object.
        Dlink<T>* dlink = new Dlink<T>;

        // Link to tail and supplant it.
        dlink->mPrev = mTail;
        dlink->mNext = mTail->mNext;  // mTail->mNext = mHead = sentinel
        dlink->mObj  = obj;
        mTail->mNext = dlink;
        mTail        = dlink;
        mHead->mPrev = dlink;  // head back to tail
        CHECK_TYPESIG(dlink->mNext,TYPESIG_DLINK);
        CHECK_TYPESIG(dlink->mPrev,TYPESIG_DLINK);
        CHECK_DLIST_HEAD_TAIL();

        return dlink;
    }

public:
    void
    Unlink( Dlink<T>* dlink )
    {
    THREAD_CODE( typename LOCK::Auto autolock( mInstanceLock ); )

    CHECK_TYPESIG( dlink, TYPESIG_DLINK );
    CHECK_DLIST_HEAD_TAIL();

        // As a sentinel is used, head/tail always point to something,
        // and there is always a previous and a next link.
        if ( UX(mTail == dlink) ) mTail = dlink->mPrev;  // update tail if unlinking it
        CHECK_TYPESIG(dlink->mNext,TYPESIG_DLINK);
        CHECK_TYPESIG(dlink->mPrev,TYPESIG_DLINK);
        dlink->mPrev->mNext = dlink->mNext;  // preceding --> following
        dlink->mNext->mPrev = dlink->mPrev;  // following --> preceding
        delete dlink;
        CHECK_DLIST_HEAD_TAIL();
    }

public:
    bool
    IfEmpty( void ) const
    {
    THREAD_CODE( typename LOCK::Auto autolock( mInstanceLock ); )

    CHECK_DLIST_HEAD_TAIL();

        return mHead == mTail;  // empty if sentinel is the only link
    }

public:
    bool
    IfMoreThanOne( void ) const
    {
    THREAD_CODE( typename LOCK::Auto autolock( mInstanceLock ); )

    CHECK_DLIST_HEAD_TAIL();

        // If first and second links exist.
        return mHead->mNext != mHead
            && mHead->mNext->mNext != mHead;
    }

public:
    Dlink<T>*
    First( void ) const
    {
    THREAD_CODE( typename LOCK::Auto autolock( mInstanceLock ); )

    CHECK_DLIST_HEAD_TAIL();
    CHECK_TYPESIG(mHead->mNext,TYPESIG_DLINK);  // works either way

        return mHead == mTail ? NULL : mHead->mNext;
    }

public:
    Dlink<T>*
    Last( void ) const
    {
    THREAD_CODE( typename LOCK::Auto autolock( mInstanceLock ); )

    CHECK_DLIST_HEAD_TAIL();

        return mHead == mTail ? NULL : mTail;
    }

public:
    Dlink<T>*
    Prev( const Dlink<T>* dlink ) const
    {
    THREAD_CODE( typename LOCK::Auto autolock( mInstanceLock ); )

    CHECK_DLIST_HEAD_TAIL();
    CHECK_TYPESIG(dlink,TYPESIG_DLINK);
    CHECK_TYPESIG(dlink->mPrev,TYPESIG_DLINK);
    ASSERT( dlink != mHead );  // catch passing head
    ASSERT( ! (dlink->mPrev == mHead && mHead->mPrev == mHead) );  // catch returning head

        return dlink->mPrev != mHead ? dlink->mPrev : mHead->mPrev;
    }

public:
    Dlink<T>*
    Next( const Dlink<T>* dlink ) const
    {
    THREAD_CODE( typename LOCK::Auto autolock( mInstanceLock ); )

    CHECK_DLIST_HEAD_TAIL();
    CHECK_TYPESIG(dlink,TYPESIG_DLINK);
    CHECK_TYPESIG(dlink->mNext,TYPESIG_DLINK);
    ASSERT( dlink != mHead );  // catch passing head
    ASSERT( ! (dlink->mNext == mHead && mHead->mNext == mHead) );  // catch returning head

        return dlink->mNext != mHead ? dlink->mNext : mHead->mNext;
    }

public:
    bool
    IfLinked( const T* obj )
    {
        Dlink<T>* first = First();
        if ( first != NULL )  // if not empty
        {
            // Until Next() wraps back to first link.
            // Start with first link.
            Dlink<T>* lnk = first;
            do
            {
                if ( lnk->Obj() == obj )
                    return true;
                lnk = Next( lnk );
            }
            while ( lnk != first );  // fall thru to return false
        }
        return false;
    }

public:
    void Lock( void ) const  // logically const
    {
        THREAD_CODE( mInstanceLock->Lock(); )
    }

    void Unlock( void ) const
    {
        THREAD_CODE( mInstanceLock->Unlock(); )
    }

public:
    typedef LOCK LockType;  // traits

private:
    eDestroy            mDestroy;   
    Dlink<T>*           mHead;      
    Dlink<T>*           mTail;      

    // Iterator necessitates a recursive lock 
    THREAD_CODE( mutable LOCK* mInstanceLock; )

public:
    
    friend class DlistIterator<T,LOCK>;
};

template<typename T,typename LOCK=FastLock>
class DlistIterator : public AbstractIterator< SafePtr<T> >
{
public:
    DlistIterator( const Dlist<T,LOCK>& dlist )
    :   mDlist(dlist),
        mNext(NULL),  // to catch mistake of calling Next() before operator bool()
        mNextNext(dlist.First()),
        mLocked(false)
    {
    CHECK_TYPESIG(&mDlist,TYPESIG_DLIST);

        // Lock the whole list unless it was empty.
        if ( mNextNext != NULL )
        {
            mDlist.Lock();
            mLocked = true;
        }
        // If list was empty, Dlist::First() returned NULL into mNextNext
        // which causes operator bool() to return false.
    }

    ~DlistIterator()
    {
        // Don't even think about eliminating mLocked with testing list emptiness,
        // because the client may have added links.
        if ( mLocked ) mDlist.Unlock();
    }

    operator bool()
    {
        // mNextNext also serves as a flag.
        // When NULL, iteration should stop (empty or end of list).
        if ( mNextNext != NULL )
        {
        CHECK_TYPESIG(mNextNext,TYPESIG_DLINK);

            // Prepare for Next() being called.
            mNext = mNextNext;

            // Prepare for operator bool() being called again.
            // Advancing to the next link before Next() returns it is a critical step
            // to survive an iteration that unlinks what Next() returns.
            mNextNext = mDlist.Next( mNextNext );
            if ( UX( mNextNext == mDlist.First() ) )
                mNextNext = NULL;  // wrapped back to first link, end-of-list condition
            return true;
        }
        else
        {
            // No more items.  Unlock the list in case the client
            // will use the list after the iteration.
            if ( mLocked )
            {
                mDlist.Unlock(); mLocked = false;
            }
            return false;
        }
    }

    SafePtr<T>
    Next( void )
    {
        return mNext->Obj();
    }

private:
    const Dlist<T,LOCK>&    mDlist;     // iterator doesn't logically affect list elements
    Dlink<T>*               mNext;      // next link that Next() will return (current state)
    Dlink<T>*               mNextNext;  // link after mNext, if NULL then stops iteration (next state)
    bool                    mLocked;    // if this iterator locked the list
};

} // namespace base

#endif // BASE_DLIST_HH

Palomino 3D Engine documents generated by doxygen 1.5.3 on Fri Nov 23 11:26:06 2007