ChainNode.hh

Go to the documentation of this file.

#ifndef NO_PTR_CHAIN_NODE_2_H
#define NO_PTR_CHAIN_NODE_2_H

#include <assert.h>
#include "NoPtrFwd.hh"
#include "nullness.hh"

namespace NoPtr
{
    namespace NoPtrImpl
    {

    /* A node of a double-linked chain of segments. Only slightly 
       more complex conceptually than SegmentNode, yet double memory
       needed, and operations in general more expensive. 
       
       ChainNode arranges so that the first item is never null if 
       the list of two neighbor nodes is not empty. I.e., it first
       sets others[0] before others[1], and moves others[1] to 
       others[0] if others[0] gets removed. This simplifies certain
       algorithms. 
       
       Note that, as with SegmentNode, copy implies connection to the 
       \a rhs node. Unlike SegmentNode, each chain node can have two 
       neighbors. This means that the two examples of failures shown
       for SegmentNode succeed for ChainNode. Actually, ChainNode 
       can handle any depth of function call with pass-by-value. An
       example of where ChainNode would fail is:
       \code
        void func1(ChainNode cn) {
            ChainNode cn2(cn); 
            func2(cn);
        }
        void func2(ChainNode) {} // assertion fails here
        func1( ChainNode() );
        \endcode
       
       */
    class ChainNode
    {
        public:
            // default is unlinked
            ChainNode() {others[0] = others[1] = NullPtr;}
            // just connect us to \a rhs, if rhs still has free slot
            ChainNode(ChainNode& rhs) 
            {
                assert(rhs.others[1] == NullPtr); 
                connectBare(rhs);
            }
            // unlink self from chain
           ~ChainNode() {removeSelf();}

            // connect us to \a rhs; disconnects us first, if necessary
            void connect(ChainNode& rhs) 
            {
                if (this != &rhs)
                {
                    removeSelf();
                    connectBare(rhs);
                }
            }
            // disconnect us from neighbor nodes
            void disconnect()
            {
                removeSelf();
                others[0] = others[1] = NullPtr;
            }
            // swap with another node; rather expensive op, avoid using. 
            void swap(ChainNode& rhs)
            { 
                // First, swap others[0] and rhs.others[0]
                ChainNode* tmp = others[0];
                others[0]     = rhs.others[0];
                rhs.others[0] = tmp;

                // then swap others[1] and rhs.others[1]
                tmp           = others[1];
                others[1]     = rhs.others[1];
                rhs.others[1] = tmp;

                // Next, reconnect those that point to rhs to point to us
                reconnect(others[0], &rhs, this);
                reconnect(others[1], &rhs, this);

                // Finally, reconnect those in rhs that point to us to point to rhs
                reconnect(rhs.others[0], this, &rhs);
                reconnect(rhs.others[1], this, &rhs);
            }
            // true if at least one neighbor node
            bool isConnected() const {return others[0] != NullPtr;}
            // Only for debugging: get neighbors
            const ChainNode* const * neighbors() const {return others;}

        private:
            // just connect us to \a rhs straight
            void connectBare(ChainNode& rhs)
            {
                rhs.add(this);
                others[0] = &rhs;
                others[1] = NullPtr;
            }
            // needed by swap: connect \a other to \a nnew
            // instead of \a old
            void reconnect(ChainNode* other, 
                           ChainNode* old, ChainNode* nnew)
            {
                // only if new is not the other itself!
                if (other && other != nnew) other->replace(old, nnew);
            }
            // remove from neighbors list; if this requires 
            // reconnecting one of the two neighbors to the other
            // so the chain is not broken
            void removeSelf()
            {
                if (others[1] != NullPtr) // replace self to not break chain
                {
                    others[0]->replace(this, others[1]);
                    others[1]->replace(this, others[0]);
                }
                else if (others[0] != NullPtr) 
                    // end of chain, just remove us:
                    others[0]->remove(this);
            }
            // directly add \a newNode to our list of neighbors; 
            // asserts that slot available
            void add(ChainNode* newNode)
            {
                if (others[0] == NullPtr) 
                {
                    others[0] = newNode;
                    assert(others[1] == NullPtr);
                }
                else 
                {
                    assert(others[1] != newNode);
                    others[1] = newNode;
                }
            }
            // directly remove \a obsNode from our list
            void remove(ChainNode* obsNode)
            {
                if (others[0] == obsNode) 
                {
                    others[0] = others[1];
                    others[1] = NullPtr;
                }
                else
                {
                    assert(others[1] == obsNode);
                    others[1] = NullPtr;
                }
            }
            // replace \a obsNode with \a newNode in *this
            void replace(ChainNode* obsNode, ChainNode* newNode)
            {
                if (others[0] == obsNode) 
                {
                    others[0] = newNode;
                    assert(others[1] != newNode);
                }
                else
                {
                    assert(others[1] == obsNode);
                    others[1] = newNode;
                }
            }

        private:
            ChainNode(const ChainNode&); // forbidden
            ChainNode& operator=(const ChainNode&); // forbidden
                
        private:
            ChainNode* others[2]; // two pointers
    };
    
    } // implementation namespace
    
} // namespace

#endif // NO_PTR_CHAIN_NODE_2_H    

---