Reverse a doubly linked list in O(1) time

#ifndef GYM_CLRS_V3_10_2_8_LINKED_LIST_H_6D4EBDB0_5B18_4FC1_A34A_CBBF36FE95E4
#define GYM_CLRS_V3_10_2_8_LINKED_LIST_H_6D4EBDB0_5B18_4FC1_A34A_CBBF36FE95E4

#include <assert.h>
#include <stdint.h>
#include <boost/call_traits.hpp>

namespace pratique
{
    namespace clrs_version
    {
        namespace detail
        {
            template <typename T>
            struct Node
            {
                T data;
                uintptr_t link;
            };

            template <typename T>
            inline Node<T> * next( Node<T> * previous, Node<T> * node )
            {
                uintptr_t n = reinterpret_cast<uintptr_t>( previous ) ^ node->link;
                return reinterpret_cast<Node<T>*>( n );
            }

            template <typename T>
            inline Node<T> * previous( Node<T> * node, Node<T> * next )
            {
                uintptr_t p = node->link ^ reinterpret_cast<uintptr_t>( next );
                return reinterpret_cast<Node<T>*>( p );
            }

            template <typename T>
            inline uintptr_t compound( Node<T> * previous, Node<T> * next )
            {
                return reinterpret_cast<uintptr_t>( previous ) ^ reinterpret_cast<uintptr_t>( next );
            }
        }

        template <typename T>
        class DoublyLinkedList
        {
            detail::Node<T> * m_head, * m_last;

            inline static detail::Node<T> * forward( detail::Node<T> ** previous, detail::Node<T> ** node )
            {
                detail::Node<T> * tmp = *node;
                *node = detail::next( *previous, *node );
                *previous = tmp;
                return tmp;
            }

            inline static detail::Node<T> * backward( detail::Node<T> ** node, detail::Node<T> ** next )
            {
                detail::Node<T> * tmp = *node;
                *node = detail::previous( *node, *next );
                *next = tmp;
                return tmp;
            }

            inline void free()
            {
                if ( m_head != NULL ) {
                    detail::Node<T> * p = NULL, * n = m_head;
                    do {
                        delete forward( &p, &n );
                    } while ( n != m_head );
                    m_head = m_last = NULL;
                }
            }
        public:
	        typedef size_t size_type;

            DoublyLinkedList() : m_head( NULL ), m_last( NULL ) {}

            ~DoublyLinkedList()
            {
                free();
            }

            DoublyLinkedList( DoublyLinkedList<T> const & dll ) : m_head( NULL ), m_last( NULL )
            {
                if ( dll.m_head != NULL ) {
                    assert( dll.m_last != NULL );
                    detail::Node<T> * p = NULL, * n = dll.m_head, * tmp;
                    detail::Node<T> * mya = NULL, * myp = NULL, * myn = NULL;
                    ScopeGuard copy_destructor(
                        [&]() {
                            for ( detail::Node<T> * p = NULL, * n = m_head; n != myp; ) {
                                delete forward( &p, &n );
                            }
                            delete myp;
                        }
                    );
                    do {
                        tmp = forward( &p, &n );
                        myn = new detail::Node<T>;
                        myn->data = tmp->data;
                        if ( m_head == NULL ) {
                            m_head = myn;
                        }
                        if ( myp != NULL ) {
                            myp->link = detail::compound( mya, myn );
                        }
                        mya = myp;
                        myp = myn;
                    } while ( n != dll.m_head );
                    copy_destructor.dismiss();
                    myp->link = detail::compound( mya, m_head );
                }
            }
            DoublyLinkedList<T> & operator=( DoublyLinkedList<T> const & dll )
            {
                if ( this != &dll ) {
                    DoublyLinkedList<T>( dll ).swap( *this );
                }
                return *this;
            }

            void swap( DoublyLinkedList<T> & dll )
            {
                using std::swap;
                swap( m_head, dll.m_head );
                swap( m_last, dll.m_last );
            }

            bool operator==( DoublyLinkedList<T> const & dll ) const
            {
                bool equals = false;
                detail::Node<T> * p = NULL, * n = dll.m_head;
                detail::Node<T> * myp = NULL, * myn = m_head;
                if ( n != NULL && myn != NULL ) {
                    do {
                        if ( n->data == myn->data ) {
                            forward( &p, &n );
                            forward( &myp, &myn );
                        } else {
                            break;
                        }
                    } while ( n != dll.m_head && myn != m_head );
                    equals = ( n == dll.m_head && myn == m_head );
                } else {
                    equals = true;
                }
                return equals;
            }

            inline bool operator!=( DoublyLinkedList<T> const & dll ) const
            {
                return !( operator==( dll ) );
            }

            inline bool empty() const
            {
                return ( m_head == NULL );
            }

            size_type size() const
            {
                size_t count = 0;
                if ( m_head != NULL ) {
                    detail::Node<T> * previous = NULL, * current = m_head, * tmp;
                    do {
                        ++count;
                        tmp = current;
                        current = next( previous, current );
                        previous = tmp;
                    } while ( current != m_head );
                }
                return count;
            }

            void push_back( typename boost::call_traits<T>::param_type v )
            {
                detail::Node<T> * p = new detail::Node<T>;
                p->data = v;
                if ( m_head != NULL ) {
                    detail::Node<T> * previous = detail::previous( m_last, m_head );
                    m_last->link = detail::compound( previous, p );
                    p->link = detail::compound( m_last, m_head );
                } else {
                    detail::Node<T> * previous = NULL;
                    m_head = p;
                    m_head->link = detail::compound( previous, p );
                }
                m_last = p;
            }

            void pop_back()
            {
                if ( m_head != NULL ) {
                    detail::Node<T> * previous = detail::previous( m_last, m_head );
                    if ( previous != NULL ) {
                        detail::Node<T> * ancestor = detail::previous( previous, m_last );
                        delete m_last;
                        previous->link = detail::compound( ancestor, m_head );
                        m_last = previous;
                    } else {
                        assert( m_last == m_head );
                        delete m_head;
                        m_last = m_head = NULL;
                    }
                }
            }

            void push_front( typename boost::call_traits<T>::param_type v )
            {
                detail::Node<T> * null_previous = NULL;
                detail::Node<T> * p = new detail::Node<T>;
                p->data = v;
                if ( m_head != NULL ) {
                    detail::Node<T> * previous = detail::previous( m_last, m_head );
                    detail::Node<T> * next = detail::next( null_previous, m_head );
                    p->link = detail::compound( null_previous, m_head );
                    if ( previous != NULL ) {
                        m_last->link = detail::compound( previous, p );
                        m_head->link = detail::compound( p, next );
                    } else {
                        m_head->link = detail::compound( p, p );
                        m_last = m_head;
                    }
                } else {
                    p->link = detail::compound( null_previous, p );
                    m_last = p;
                }
                m_head = p;
            }

            void pop_front()
            {
                if ( m_head != NULL ) {
                    detail::Node<T> * null_previous = NULL;
                    detail::Node<T> * previous = detail::previous( m_last, m_head );
                    if ( previous != NULL ) {
                        detail::Node<T> * next = detail::next( null_previous, m_head );
                        if ( next != m_last ) {
                            detail::Node<T> * third = detail::next( m_head, next );
                            m_last->link = detail::compound( previous, next );
                            next->link = detail::compound( null_previous, third );
                        } else {
                            m_last->link = detail::compound( null_previous, m_last );
                        }
                        delete m_head;
                        m_head = next;
                    } else {
                        delete m_head;
                        m_head = m_last = NULL;
                    }
                }
            }

            void reverse()
            {
                if ( m_head != m_last ) {
                    detail::Node<T> * null_previous = NULL;
                    detail::Node<T> * previous = detail::previous( m_last, m_head );
                    detail::Node<T> * next = detail::next( null_previous, m_head );
                    m_last->link = detail::compound( null_previous, previous );
                    m_head->link = detail::compound( m_last, next );
                    std::swap( m_last, m_head );
                }
            }

            T const & front() const
            {
                assert( !empty() );
                return m_head->data;
            }

            T const & back() const
            {
                assert( !empty() );
                return m_last->data;
            }

            class Iterator
            {
                friend class DoublyLinkedList<T>;
                detail::Node<T> * m_previous, * m_current, * m_last;
                Iterator( DoublyLinkedList<T> const * dll ) : m_previous( NULL ), m_current( dll->m_head ), m_last( dll->m_last )  {}
            public:
                Iterator() : m_previous( NULL ), m_current( NULL ), m_last( NULL ) {}

                typedef std::bidirectional_iterator_tag iterator_category;

                typedef T value_type;
                typedef detail::Node<T> * pointer;
                typedef ptrdiff_t difference_type;
                typedef T const & reference;

                reference operator*() const
                {
                    return m_current->data;
                }

                Iterator & operator++()
                {
                    DoublyLinkedList<T>::forward( &m_previous, &m_current );
                    return (*this);
                }

                Iterator operator++(int)
                {
                    Iterator tmp( *this );
                    ++*this;
                    return tmp;
                }

                Iterator & operator--()
                {
                    DoublyLinkedList<T>::backward( &m_previous, &m_current );
                    return (*this);
                }

                Iterator operator--(int)
                {
                    Iterator tmp( *this );
                    --*this;
                    return tmp;
                }

                bool operator==( const Iterator & i ) const
                {
                    return ( m_current == i.m_current && m_previous == i.m_previous );
                }

                bool operator!=( const Iterator& i ) const
                {
                    return ( m_current != i.m_current || m_previous != i.m_previous );
                }
            };

            typedef Iterator iterator;

            iterator begin() const { return Iterator( this ); }
            iterator end() const
            {
                Iterator i;
                i.m_previous = this->m_last;
                i.m_current = this->m_head;
                i.m_last = this->m_last;
                return i;
            }
        };
    }
}

#endif //GYM_CLRS_V3_10_2_8_LINKED_LIST_H_6D4EBDB0_5B18_4FC1_A34A_CBBF36FE95E4

The testing code is:

    typedef pratique::clrs_version::DoublyLinkedList<int> mydll;

    void must_be_equals( mydll const & l, mydll const & r )
    {
        if ( l != r ) {
            fprintf( stderr, "Bad implementation for the problem CRLS 10-2-8\n" );
            DebugBreak();
        }
    }

    void clrs_list_test()
    {
        {
            mydll dll;

            {
                mydll copy( dll );
                must_be_equals( dll, copy );
            }

            dll.push_back( 1 );
            dll.pop_back();

            {
                mydll copy( dll );
                must_be_equals( dll, copy );
            }
        }

        {
            mydll dll;

            dll.push_back( 1 );
            {
                mydll copy( dll );
                must_be_equals( dll, copy );
            }

            dll.push_back( 2 );
            dll.pop_back();

            {
                mydll copy( dll );
                must_be_equals( dll, copy );
            }
        }

        {
            mydll dll;
            const int limits = 128;
            int to_be_compared[ limits ];
            for ( int i = 0; i < limits; ++i ) {
                to_be_compared[i] = i;
            }

            for ( int i = 0; i < limits; ++i ) {
                dll.push_back( i );
                if ( !std::equal( dll.begin(), dll.end(), std::begin( to_be_compared ) ) ) {
                    fprintf( stderr, "Bad implementation for the problem CRLS 10-2-8\n" );
                    DebugBreak();
                    break;
                }
            }

            while ( !dll.empty() ) {
                dll.pop_back();
            }

            for ( int i = 0; i < limits; ++i ) {
                dll.push_back( i );
                if ( !std::equal( dll.begin(), dll.end(), std::begin( to_be_compared ) ) ) {
                    fprintf( stderr, "Bad implementation for the problem CRLS 10-2-8\n" );
                    DebugBreak();
                    break;
                }
            }

            dll.reverse();

            int count = 0;
            std::vector<int> result;
            while ( !dll.empty() ) {
                ++count;
                result.push_back( dll.back() );
                dll.pop_back();
            }

            for ( int i = 0; i < limits; ++i ) {
                if ( result[i] != i ) {
                    fprintf( stderr, "Bad implementation for the problem CRLS 10-2-8\n" );
                    DebugBreak();
                    break;
                }
            }

            mydll copy( dll );
            must_be_equals( dll, copy );
        }

        {
            mydll dll;

            dll.push_front( 1 );
            dll.pop_front();

            {
                mydll copy( dll );
                must_be_equals( dll, copy );
            }
        }

        {
            mydll dll;

            dll.push_front( 1 );
            {
                mydll copy( dll );
                must_be_equals( dll, copy );
            }

            dll.push_front( 2 );
            dll.pop_front();

            {
                mydll copy( dll );
                must_be_equals( dll, copy );
            }
        }

        {
            mydll dll;
            const int limits = 128;
            int to_be_compared[ limits ];
            for ( int i = 0; i < limits; ++i ) {
                to_be_compared[i] = i;
            }

            for ( int i = limits - 1; i >= 0; --i ) {
                dll.push_front( i );
                if ( !std::equal( dll.begin(), dll.end(), std::begin( to_be_compared ) + i ) ) {
                    fprintf( stderr, "Bad implementation for the problem CRLS 10-2-8\n" );
                    DebugBreak();
                    break;
                }
            }

            while ( !dll.empty() ) {
                dll.pop_back();
            }

            for ( int i = limits - 1; i >= 0; --i ) {
                dll.push_front( i );
                if ( !std::equal( dll.begin(), dll.end(), std::begin( to_be_compared ) + i ) ) {
                    fprintf( stderr, "Bad implementation for the problem CRLS 10-2-8\n" );
                    DebugBreak();
                    break;
                }
            }

            dll.reverse();

            int count = 0;
            std::vector<int> result;
            while ( !dll.empty() ) {
                ++count;
                result.push_back( dll.back() );
                dll.pop_back();
            }

            for ( int i = 0; i < limits; ++i ) {
                if ( result[i] != i ) {
                    fprintf( stderr, "Bad implementation for the problem CRLS 10-2-8\n" );
                    DebugBreak();
                    break;
                }
            }

            mydll copy( dll );
            must_be_equals( dll, copy );
        }
    }