lkptr.h

Go to the documentation of this file.

/* lkptr.h (C) 2007  adolfo@di-mare.com  */

/* THIS IS FREE SOFWTWARE.
   - Use at your own risk; acknowledge authorship, please.
   - You can never blame the author for your use of this software.
   - Released to the world under LGPLv3:
     http://www.gnu.org/licenses/lgpl-3.0.html
*/

/** \file  lkptr.h
    \brief simple reference LinKed PoinTeR.
    \see http://www.di-mare.com/adolfo/p/lkptr.htm

    \author Adolfo Di Mare <adolfo@di-mare.com>
    \date   2007
*/

/** \class lkptr.
    \brief These smart pointer share the object they point to.
    Only after the last pointer releases its reference will the object be deleted.
    - Whenever the object will be changed by one of the pointers, all the
      other pointers will also see the change.
    - The implementation stores three pointers for every \c lkptr,
      but does not allocate anything on the free store.
    - Every \c lkptr is implemented using 3 internal pointers which
      makes it 3 times as big as a regular pointer. In exchange,
      automatic garbage collection is provided by the C++
      constructor - destructor protocol of execution.
    - These pointers are double linked together. When only one pointer
      is in the chain, then the object will be deleted if the pointer
      releases it. Otherwise, the object will not be deleted because
      the other pointers in the chain are still referencing it.
    - These pointers are not intrusive, because they do not need an
      extra field in the pointed object to keep track of how many
      pointers reference the same object.
    - These pointers do not allocate extra memory to keep track of the
      reference count, because the linked list itself binds together
      all pointers that reference the same object.
    - A diagram for the pointer chain is shown in the documentation for
      method \c ok().
    - Many of the pointer operators will never throw exceptions (hence
      the \c "throw()" especification in the method signature).
    - Memory leaks are extremely rare. Reference counting/linking can
      leak in the case of circular references (i.e., when the pointed
      object itself contains a counted/linked pointer, which points
      to an object that contains the original counted/linked  pointer).
    - These pointers cannot be used in ROM memory because they modify
      each other when double linking, even if they are \c const.

\par Usage:
\code
void foo() {
    lkptr<AnyClass> p(new AnyClass); // "p" is one smart-pointer
    lkptr<AnyClass> q;               // "q" is the other smart-pointer

    p->DoSomething();               // no syntax change when using pointers
    q = p;                          // share the object
    q->Change();                    // both "*p" && "*q" get changed
    p = q;                          // both still point to the same object
    lkptr<AnyClass> r = p;          // The 3 of them share the same object

    // delete p; // No need to worry about destruction
    // delete q; // the lkptr<> destructor will handle deletions for you.
    // delete r;
}
\endcode

    - This work is based on Sharon's paper:
      - "Smart Pointers - What, Why, Which?"
      - http://ootips.org/yonat/4dev/smart-pointers.html
      - Yonat Sharon <yonat@ootips.org>
      - 1999.
*/
template <typename X>
class lkptr;

/** \class array_lkptr.
    \brief Similar to \c lkptr<>, but points to an array instead of a single object.
*/
template <typename X>
class array_lkptr;

/// MOD this when your compiler does compile this correctly.
#undef COMPILER_lkptr

#ifdef _MSC_VER
    #if _MSC_VER >= 1300 // .net Microsoft Visual Studio C++
        #define COMPILER_lkptr
    #endif
#endif

#ifdef __BORLANDC__               // Borland C++
    #if (__BORLANDC__ <= 0x0410)  // BC++ v3.1 or earlier
        #undef  COMPILER_lkptr
    #endif
#endif

#ifdef __GNUC__                   // GNU C++
    #define  COMPILER_lkptr
#endif

#ifndef COMPILER_lkptr
    #error  Compiler not yet supported // emit error
    #define lkptr_h     // avoid file inclussion || compilation
#endif

#ifndef   lkptr_h
#define   lkptr_h ///< Avoid multiple file inclusion

#if 0
              +-----------+ *X
              | lkptr_rep | *next
              +-----------+ *prev
                    |
            +----------------+
            |                |
     +-----------+     +-----------+
     |array_lkptr|     |   lkptr   |
     +-----------+     +-----------+
                             |
                     +----------------+
                     |                |
              +-----------+     +-----------+
              | wide_lkptr|     | weak_lkptr|
     *my_weak |-----------|     |-----------| *owner
              +-----------+     +-----------+

- lkptr_rep:   Contains the 3 pointers [*X *next *prev]
- lktpr:       Contains the 3 pointers [*X *next *prev]
- array_lkptr: Contains the 3 pointers [*X *next *prev]

- wide_lkptr: this->my_weak points to my weak_lkptr<> chain
- weak_lkptr: this->owner point to the wide_lkptr<> where iAmGlued
- weak_lkptr: Only one weak_lkptr<> in chain has (this->owner!=0)
- wide_lkptr: More than one lkptr<> in chain can have its weak_lkptr<> chain
- array_weak_lkptr: not supported
#endif

#if 0
              lkptr chain             weak_lkptr chain
                                               /---\
         +---+         +---+ my_weak  /------->|   |
         |   |<------->|   |--->--\   |        \---/
         +---+         +---+       \  v          ^
           ^             ^  \       /---\        |
           |             |   \--<---|   |        |
           |             |   owner  \---/        |
           v             v            ^          v
         +---+         +---+          |        /---\
         |   |<------->|   |          \------->|   |
         +---+         +---+                   \---/
#endif

/*
    Neither weak_lkptr<> nor wide_lkptr<> have been implemented.
    - If you need them, use boost::weak_ptr<>'s with boost::shared_ptr<>'s.
    - They DO need an external reference count, allocated in heap memory
      but this reference count can be obtained when the intelligent pointer
      is created invoking one of these factory functions:
      - make_shared().
      - allocate_shared().
    - These boost pointers have good multi-threadh capabilities.
    - http://www.boost.org/doc/libs/1_42_0/libs/smart_ptr/smart_ptr.htm
    - http://www.google.com/search?num=100&q=site:boost.com+smart_ptr.htm
*/

/// Accesory class that contains the fields all \c lkptr<> intelligent pointers.
template <typename X>
class base_lkptr { // not an inheritance base for lkptr<>'s
    template <typename Y> friend class lkptr;        // contains 3 pointers
    template <typename Y> friend class array_lkptr;  // contains 3 pointers
    template <typename Y> friend class wide_lkptr;   // contains 4 pointers
    template <typename Y> friend class weak_lkptr;   // contains 4 pointers
    template <typename Y> friend class test_lkptr;

private: // Rep
    X          * ptr;  ///< Pointer to referenced object (can be a \c NULL pointer).
    base_lkptr * prev; ///< Next in pointer chain.
    base_lkptr * next; ///< Previous in pointer chain.

public:  // Nothing is public in a base_lkptr<>:
private: // - Only the other lkptr<> classes can use it.

    /// Default constructor and constructor from a regular pointer.
    explicit base_lkptr(X* p = 0) throw() : ptr(p) { prev = next = this; }

    /// Constructor from a pointer to a derived class.
    /// - Check that the pointer is not null when types are not compatible.
    /// - Make sure the destructor for the base class is virtual.
    template <typename Y>
    explicit base_lkptr( Y* p ) throw() : ptr( dynamic_cast<X*>(p) )
    { prev = next = this; }

    /// Copy constructor: share the object with other pointers.
    base_lkptr( const base_lkptr& r ) throw()
    { acquire( const_cast<base_lkptr*>( &r ) ); }

    /// Copy constructor from a derived clase: share the object with other pointers.
    /// - Check that the pointer is not null when types are not compatible.
    /// - Make sure the destructor for the base class is virtual.
    template <typename Y>
    explicit base_lkptr( const base_lkptr<Y>& r ) throw() {
        ptr = dynamic_cast<X*>( r.get() ); // ( r.ptr )
        if   ( 0==ptr ) { autolink(); } // invalid cast
        else {
            acquire(
                const_cast<base_lkptr*>( // remove "const"
                    reinterpret_cast<const base_lkptr*>( &r ) ) );  // convert to pointer
        }
    }

     /// Destructor. Delete only if last reference.
     /// - The derived \c lkptr<>'s do the destruction.
    ~base_lkptr() { }

    /// Makes \c this->ptr point to \c r.ptr.
    /// - Insert \c "this" after \c "r" in the double chained pointer list.
    /// - If called after \c fast_release() will restore the invariant into \c "this".
    /// - Will link (this <--> r) even when r->ptr is a \c NULL pointer.
    void acquire(base_lkptr* r) throw() {
        this->ptr  = r->ptr;      // reference r's object
        this->next = r->next;
        this->next->prev = this; // 4 assignments to change the 4 next+prev chain pointers
        this->prev = r;
        r->next = this;
        // To double link with the list, "*r" must be changed. But the whole
        // implementation is easier if "*r" is const.
    }

    /// Unlink from pointer chain.
    void unlink() {
        prev->next = next;
        next->prev = prev;
    }
    /// Autolink: \c unique() becomes \c true.
    void autolink() {
        prev = next = this;
    }

#ifdef lkptr_MERGE_IS_PUBLIC
    /// Releases the object.
    /// - Should never be needed: use \c wide_lkptr<> && \c weak_lkptr<>.
    /// - Before: If this was the last reference, it will not delete the referenced object.
    /// - After: The pointer becomes \c NULL.
    /// - After: Simliar to \c reset(0) (with no delete).
    /// - Difference: never deletes the pointed object.
    void weak_release() {
        unlink();    // unlink from pointer chain
        autolink();  // restore invariant: unique in chain
        ptr = 0;
    }

    /// Releases the object.
    /// - If \c this->ptr is the last reference, it also deletes the object.
    /// - Leaves all the fields in \c "this" in a broken state.
    /// - Caller must ensure that all the fields get good values after invocation.
    void fast_release() {
        if ( prev == this ) { // auto-linked ==> unique()
            if ( ptr!=0 ) {
                delete ptr; // this could throw an exception
            }
        }
        else { // ! unique() ==> unlink from pointer chain
            unlink();
        }
        // leaves all the fields in a broken state:
        // prev = next = this; // set-all to nil pointer
        // ptr = 0;
    }
#endif

    #ifdef lkptr_MERGE_IS_PUBLIC
        public:  void merge( base_lkptr& r );
    #else
        private: void merge( base_lkptr& r ); public:
    #endif

    // Pointer access operators (these never throw exceptions)
    X* get()        const throw() { return  ptr; } ///< Returns a pointer to referenced object.
    X& value()      const throw() { return *ptr; } ///< Returns the referenced object.
    X& operator*()  const throw() { return *ptr; } ///< Returns the referenced object.
    X* operator->() const throw() { return  ptr; } ///< Returns a pointer to referenced object.
//  operator X* ()  const throw() { return  ptr; } ///< Returns a pointer to referenced object.

    /// Returns \c true if the object pointed is null and \c false otherwise.
    bool isNull() const throw() { return ptr == 0; }

    /// Return \c "true" when only one pointer references the object.
    bool unique() const throw() { return ( prev == this ); }

    /// Returns how many pointers are sharing the object referenced by \c "this".
    /// \dontinclude test_lkptr.cpp \skipline test::null_3x1
    /// \until       }}
    int  use_count() const throw();

    bool ok() const throw();
    template <typename Y> friend bool check_ok( const base_lkptr<Y>& p ) throw();

}; // base_lkptr

/// Blends together \c *this and \c r when both point to the same object.
/// - Should never be needed because it is erroneous to have unrelated
///   \c lkptr<>'s to the same object. This should be an error!
/// - Very usefull to avoid multiple destruction from unrelated \c lkptr<>'s
///   that reference the same object.
/// - Will not blend together null pointers.
/// - Requires linear time in the number \c use_count() of the \c lkptr<>'s to merge.
template <typename X>
void base_lkptr<X>::merge( base_lkptr<X>& r ) {
    if ( this == &r ) { // avoid autolink problems
        return;
    }
    else if ( this->ptr == 0 ) {
        return; // avoid linking together null pointers
    }
    else if ( this->ptr != r.ptr ) {
        return; // never merge when they don´t reference the same object
    }
    {   // avoid 4-nodes pointer problem
        base_lkptr<X> * r_prev = r.prev;
#if 1
        while ( r_prev != &r ) {  // never merge if they are already merged
            if ( r_prev==this ) { // already chained
                return;
            } // hopefully r's chain is shorter than this
            r_prev = r_prev->prev;
        }
#else
        /// Sorry: doesn´t work !!!
        base_lkptr<X> * this_prev = this->prev;
        for ( int i=0; i<25 ; ++i ) {
            if ( (r_prev==this) || (this_prev==&r) ) { // already chained
                return;
            } // hopefully r's chain is shorter than this
            r_prev    = r_prev->prev;
            this_prev = this_prev->prev;
        }
#endif

        r_prev = r.prev;
        base_lkptr<X> * this_next = this->next;

        r.prev = this;
        this->next = &r;
        r_prev->next = this_next;
        this_next->prev = r_prev;
    }
    // NOTE: see 4-node chain problem at the end of this file
}

template <typename X>
int base_lkptr<X>::use_count() const throw() {
    int n = 1; // count "this"
    const base_lkptr* q = this->next;
    while (q != this) { // while´s can´t be inlined
        q = q->next;
        ++n;
    }
    return n;
}

/// Verifies the invariant for class \c lkptr<X>.
/// \see base_lkptr<X>::ok().
template <typename X>
inline bool check_ok( const base_lkptr<X>& p ) throw() { return p.ok(); }

/** Verifies the invariant for class \c lkptr<X>.
    - Returns \c "true" when \c "p" contains a correct value.
    - It could return \c "true" even when it's value is corrupted.
    - it could never return if the value in \c "p" is corrupted.

    \par Rep: Description with words.
    - Field \c "ptr" is the pointer to the referenced object.
    - All pointers that point to the same object are linked together.
    - The list is double linked to allow for O(1) insertion and removal.
    - There is no "first" or "last" element in the list. What it is
      important is to be "in" the list, not which position in it a
      particular \c lkptr<X> occupies.

    \par Rep: Class diagram.
    \code
    <=================================>     <=============>
    |      p1        p2       p3      |     |      p4     |
    |    +-+-+     +-+-+     +-+-+    |     |    +-+-+    |
    <===>|*|*|<===>|*|*|<===>|*|*|<===>     <===>|*|*|<===>
         +-+-+     +-+-+     +-+-+               +-+-+
         | * |     | * |     | * |               | * |
         +-|-+     +-|-+     +-|-+               +-|-+
           |         |         |                   |
          \|/       \|/       \|/                 \|/
         +----------------------+      +----------------------+
         |     Shared object    |      |    Lonely Object     |
         +----------------------+      +----------------------+
    \endcode

    \code
     +--------+-------+  "ptr" points to the object
     |  prev  |       |
     +--------+  ptr  +
     |  next  |       |  "next" is next in chain
     +--------+-------+  "prev" is previous in chain
    \endcode

    \par The invariant: Description with words.
*/
template <typename X>
bool base_lkptr<X>::ok() const throw() {
    {   // check a single element double linked chain
        if      ( (next==this) && (prev==this) ) { /* Ok */ }
        else if ( (next==this) || (prev==this) ) {
            return false; // because one of them must be a broken link
            /// - Invariant (1) (broken link): A unique pointer should be self-linked with
            ///   both \c next && \c prev pointing to itself (\c this).
        }
    }

    {   // check the double linked chain
        const base_lkptr* frwd = this;
        const base_lkptr* back = this;
        do {
            if ( (frwd == frwd->next->prev) && (frwd == frwd->prev->next) ) { /* Ok */ }
            else {
                return false;
                /// - Invariant (2) (broken link): the double linked pointer chain can never be broken.
            }
            if ( this->ptr == frwd->ptr ) { /* Ok */ }
            else {
                return false;
                /// - Invariant (3) (broken ptr): Every pointer in the chain should reference
                ///   the same object.
            }

            if ( (back == back->next->prev) && (back == back->prev->next) ) { /* Ok */ }
            else {
                return false;
            }
            if ( this->ptr == back->ptr ) { /* Ok */ }
            else {
                return false;
            }

            frwd = frwd->next;
            back = back->prev;
        } while (frwd != this && back != this);

        if (  (frwd == this && back == this) ) { /* Ok */ }
        else {
            return false;
             /// - Invariant (4): chain is not a circular double linked chain
        }
    }

    // This "YES" style of programming makes it easier to define the invariant
    // in positive terms.
    // - The "else" statement are executed when the invariant is broken.

    {   // check that the pointed object is correct
    #if 0  // NOT implemented
           // WHY? To avoid forcing the pointed type to have a check_ok() function
        bool check_ok( const X& ); // forward declaration
        if ( check_ok( * ptr ) ) { /* Ok */ }
        else {
            return false; /// - Invariant (5) (corrupt pointed object)
        }
    #endif
    }

    if ( ptr==0 ) { // Check that the null pointer is in its own chain
    #ifdef lkptr_NULL_POINTERS_ARE_ALONE
        // There is really no harm if some null pointers are linked together.
        if ( (next==this) && (prev==this) ) { /* Ok */ }
        else {
            return false;
            /// - Invariant (6) (auto-link): A \c NULL pointer should be self-linked with
            ///   both \c next && \c prev pointing to itself (\c this).
        }
    #endif
    }

    return true;
}


template <typename X>
class lkptr {
    base_lkptr<X> b; ///< Contains the 3 pointers for the \c lkptr<>.
private:
    template <typename Y> friend class lkptr;
public:
    typedef X element_type;   ///< Standard name for the pointed object.
    typedef X value_type;     ///< Standard name for the pointed object.
    typedef X * pointer;      ///< Standard name for the pointer to the object.

    /// \copydoc base_lkptr::base_lkptr(X*).
    explicit lkptr(X* p = 0) throw() : b(p) { }

    /// \copydoc base_lkptr::base_lkptr(Y*).
    template <typename Y>
    explicit lkptr( Y* p ) throw() : b(p) { }

    /// \copydoc base_lkptr::base_lkptr(const base_lkptr&).
    lkptr( const lkptr& r ) throw() : b(r.b) { }

    /// \copydoc base_lkptr::base_lkptr(const base_lkptr<Y>&).
    template <typename Y>
    explicit lkptr( const lkptr<Y>& r ) throw() : b(r.b) { }

    ~lkptr() {
        if ( b.prev == &b ) {
            if ( b.ptr!=0 ) { delete b.ptr; }
        }
        else {
            b.unlink();
        }
    }  ///< Destructor.

    /// Copy operator: share the object with other pointers.
    lkptr& operator=( const lkptr& r ) {
        if (this == &r) { // avoid self - anhilation
            // don´t change
        }
        else {
            if ( b.prev == &(this->b) ) { // autolinked ==> unique()
                X* toDelete = b.ptr;
                b.ptr = 0;    // restore invariant before "delete"
                if ( toDelete!=0 ) {
                    delete toDelete; // this could throw an exception
                }
            }
            else {
                b.unlink();
            }
            #ifdef lkptr_NULL_POINTERS_ARE_ALONE
                if ( r.ptr == 0) {
                    b.prev = b.next = this;  // restore invariant: unique in chain
                    b.ptr = 0; // NULL pointers are always alone
                }
                else {
                    b.acquire( const_cast< base_lkptr<X> * >( &r.b ) ); // r's chain fields will be changed
                }
            #else
                {
                    b.acquire( const_cast< base_lkptr<X> * >( &r.b ) ); // r's chain fields will be changed
                }
            #endif
        }
        return *this;
    }

    /// Copy operator from a derived clase: share the object with other pointers.
    /// - Will not copy when types are not compatible.
    /// - Make sure the destructor for the base class is virtual.
    template <typename Y>
    lkptr& operator=( const lkptr<Y>& r ) {
        X* ptr = dynamic_cast<X*>( r.b.ptr );
        if ( 0!=ptr ) { // avoid invalid typecast
            this->operator=( * ( reinterpret_cast<const lkptr*>( &r ) ) );
        }
        return *this;
    }

    void swap( lkptr& r ) throw(); ///< Swaps with \c r.

    X* get()        const throw() { return b.get();         } ///< \copydoc base_lkptr::get() const.
    X& value()      const throw() { return b.value();       } ///< \copydoc base_lkptr::value()const.
    X& operator*()  const throw() { return b.operator*();   } ///< \copydoc base_lkptr::operator*() const.
    X* operator->() const throw() { return b.operator->();  } ///< \copydoc base_lkptr::operator->() const.
//  operator X* ()  const throw() { return b.operator X*(); } ///< \copydoc base_lkptr::operator X*() const.

    bool isNull()    const throw() { return b.isNull(); }    ///< \copydoc base_lkptr::isNull().
    bool unique()    const throw() { return b.unique(); }    ///< \copydoc base_lkptr::unique().
    int  use_count() const throw() { return b.use_count(); } ///< \copydoc base_lkptr::use_count().

    /// Releases the object.
    /// - Before: If this was the last reference, it also deletes the referenced object.
    /// - After: The pointer becomes \c NULL.
    /// - After: Equivalent to \c reset(0).
    void release() {
        if ( b.prev == &(this->b) ) { // autolinked ==> unique()
            X* toDelete = b.ptr;
            b.ptr = 0;    // restore invariant before "delete"
            if ( toDelete!=0 ) {
                delete toDelete; // this could throw an exception
            }
        }
        else { // ! unique() ==> unlink from pointer chain
            b.unlink();
            b.autolink(); // restore invariant: unique in chain
            b.ptr = 0;    // isNull() is true
        }
    }

    /// Resets the pointer so that it will point to \c "p".
    /// - Before: If this was the last reference, it also deletes the referenced object.
    /// - Before: \c "p==0" is a valid argument (\c NULL is ok).
    /// - After: The object pointed by \c "p" gets to be own by \c "this".
    /// - [DANGER] <code>V.reset( r.get() )</code> almost always is an error because
    ///   both \c V and \c r will destroy the referenced object. Use <code>V = r</code>.
    /// \dontinclude figures.h \skipline struct Point
    /// \until struct Rectangle
    /// \dontinclude test_lkptr.cpp \skipline test::inheritance
    /// \until }}
    void reset(X* p=0) {
        #if 0
            if (ptr == p) {
                return; // avoid self - anhilation
            }
        #endif
        release();
        b.ptr = p;
    }

    /// <code>(*this) = r</code>.
    void reset( const lkptr& r ) {
        this->operator= ( r ); // necessary to mask out reset(X*)
    #if 0
        {/* Note:
            Automatic conversion into a pointer is discouraged because it can lead
            to serious errors. If the conversion lktpr<X>::operator X*() exists, it
            would convert any lkptr<X> into its X*, which makes very easy the
            following erroneous usage:
                tik.reset( tak.get() ); // [ERROR] tik.reset( tak.operator X*() );
            This will causes double destruction of the pointed object because there
            are 2 unlinked lkptr<X>'s that own the same object.
        */
            X* ptrX = new X();
            lkptr<X> tik ( ptrX );
            lkptr<X> tak;

            tik = tak; assertTrue( tik.use_count() == 2 ); // ok
            tik.reset( tak.get() ); // [ERROR] tik.reset( tak.operator X*() );
            assertTrue( tik.use_count() == 1 );
            assertTrue( tak.use_count() == 1 ); // unlinked

            assertTrue( tik.next != &tak ); // they are unlinked
            assertTrue( tak.prev != &tik );
            assertTrue( tik.ptr == tak.ptr ); // both share the same object
        }   // ptrX gets destroyed twice
    #endif
    }

    /// <code>(*this) = r</code> [ from a derived class ].
    template <typename Y>
    void reset( const lkptr<Y>& r ) {
        this->operator=( r );
    }

    #ifdef lkptr_MERGE_IS_PUBLIC
        void merge( lkptr& r ) { b.merge( r.b ); } ///< \copydoc merge( base_lkptr& ).
        void weak_release() { b.weak_release(); }  ///< \copydoc weak_release( base_lkptr& ).
    #endif

    bool ok() const throw() { return b.ok(); } ///< \copydoc base_lkptr::ok().
    template <typename Y> friend bool check_ok( const lkptr<Y>& p ) throw();

private:
    template <typename Y> friend class test_lkptr; ///< Test \c lkptr<X>.

#if 0 // doesn´t work
private:
    array_lkptr<X>&
    operator=(  const array_lkptr<X>& r ); ///< Forbid mixing \c lktpr<> with \c array_lktpr<>.
    void reset( const array_lkptr<X>& r ); ///< Forbid mixing \c lktpr<> with \c array_lktpr<>.
    void merge( const array_lkptr<X>& r ); ///< Forbid mixing \c lktpr<> with \c array_lktpr<>.
#endif
}; // class lkptr<>

/// Swaps with \c r.
template <typename X>
void lkptr<X>::swap( lkptr<X>& r ) throw() {
    lkptr tmp = *this; // Thanks, David
    *this = r;
    r = tmp;
}

/// Swap <code> l <==> r </code>.
template <typename X>
inline void swap( lkptr<X>& l , lkptr<X>& r ) throw() {
    l.swap( r );
}

template <typename X>
inline bool check_ok( const lkptr<X>& p ) throw()
{ return check_ok( p.b ); } ///< \copydoc check_ok(const base_lkptr<X>&).

/// <code> (p == q) </code> ???
template <typename X>
inline bool operator<( const lkptr<X> & p, const lkptr<X> & q )  {
    return p.get() < q.get();
}

/// <code> (p == q) </code> ???
template <typename X>
inline bool operator==( const lkptr<X> & p, const lkptr<X> & q )  {
    return p.get() == q.get();
}

/// <code> (p != q) </code> ???
template <typename X>
inline bool operator!=( const lkptr<X> & p, const lkptr<X> & q )  {
    return ! (p == q);
}

/*  Note:
    The implementation for array_lkptr<> is almos equal to the implementation for lkptr<>.
    These are the differences:
    - Instead of "lkptr" the class name is "array_lkptr".
    - Instead of using "delete b.ptr" what is used is "delete [] b.ptr" (vector delete).
    - Instead of using "delete toDelete" what is used is delete [] toDelete" (vector delete).

    It is NOT wise to derive these 2 implementations from base_lkptr<> because the
    compiler includes the copy operator=() for all the classes, and then it allows for
    errors like these:
    lkptr<E>       lk;
    array_lkptr<E> vec;

    vec = lk;                        // error: no match for 'operator=' in 'vec = lk'
                    lk  = vec;       // error: no match for 'operator=' in 'lk = vec'
    lk.merge( vec );                 // error: no matching function for call to lkptr<int>::merge(array_lkptr<int>&)
                    vec.merge( lk ); // error: no matching function for call to array_lkptr<int>::merge(lkptr<int>&)
    lk.reset( vec );                 // error: no matching function for call to lkptr<int>::reset(array_lkptr<int>&)
                    vec.reset( lk ); // error: no matching function for call to array_lkptr<int>::reset(lkptr<int>&)

*/

template <typename X>
class array_lkptr {
    base_lkptr<X> b; ///< Contains the 3 pointers for the \c array_lkptr<>.
private:
    template <typename Y> friend class array_lkptr;
public:
    typedef X element_type;   ///< Standard name for the pointed object.
    typedef X value_type;     ///< Standard name for the pointed object.
    typedef X * pointer;      ///< Standard name for the pointer to the object.

    /// V[i].
    X& operator[]( int i ) {
        return this->b.ptr[i];
    }

    /// \copydoc base_lkptr::base_lkptr(X*).
    explicit array_lkptr(X* p = 0) throw() : b(p) { }

    /// \copydoc base_lkptr::base_lkptr(Y*).
    template <typename Y>
    explicit array_lkptr( Y* p ) throw() : b(p) { }

    /// \copydoc base_lkptr::base_lkptr(const base_lkptr&).
    array_lkptr( const array_lkptr& r ) throw() : b(r.b) { }

    /// \copydoc base_lkptr::base_lkptr(const base_lkptr<Y>&).
    template <typename Y>
    explicit array_lkptr( const array_lkptr<Y>& r ) throw() : b(r.b) { }

    ~array_lkptr() {
        if ( b.prev == &b ) {
            if ( b.ptr!=0 ) { delete [] b.ptr; }
        }
        else {
            b.unlink();
        }
    }  ///< Destructor.

    /// Copy operator: share the object with other pointers.
    array_lkptr& operator=( const array_lkptr& r ) {
        if (this == &r) { // avoid self - anhilation
            // don´t change
        }
        else {
            if ( b.prev == &(this->b) ) { // autolinked ==> unique()
                X* toDelete = b.ptr;
                b.ptr = 0;    // restore invariant before "delete"
                if ( toDelete!=0 ) {
                    delete [] toDelete; // this could throw an exception
                }
            }
            else {
                b.unlink();
            }
            #ifdef array_lkptr_NULL_POINTERS_ARE_ALONE
                if ( r.ptr == 0) {
                    b.prev = b.next = this;  // restore invariant: unique in chain
                    b.ptr = 0; // NULL pointers are always alone
                }
                else {
                    b.acquire( const_cast< base_lkptr<X> * >( &r.b ) ); // r's chain fields will be changed
                }
            #else
                {
                    b.acquire( const_cast< base_lkptr<X> * >( &r.b ) ); // r's chain fields will be changed
                }
            #endif
        }
        return *this;
    }

    /// Copy operator from a derived clase: share the object with other pointers.
    /// - Will not copy when types are not compatible.
    /// - Make sure the destructor for the base class is virtual.
    template <typename Y>
    array_lkptr& operator=( const array_lkptr<Y>& r ) {
        X* ptr = dynamic_cast<X*>( r.b.ptr );
        if ( 0!=ptr ) { // avoid invalid typecast
            this->operator=( * ( reinterpret_cast<const array_lkptr*>( &r ) ) );
        }
        return *this;
    }

    void swap( array_lkptr& r ) throw(); ///< Swaps with \c r.

    X* get()        const throw() { return b.get();         } ///< \copydoc base_lkptr::get() const.
    X& value()      const throw() { return b.value();       } ///< \copydoc base_lkptr::value() const.
    X& operator*()  const throw() { return b.operator*();   } ///< \copydoc base_lkptr::operator*() const.
    X* operator->() const throw() { return b.operator->();  } ///< \copydoc base_lkptr::operator->() const.
//  operator X* ()  const throw() { return b.operator X*(); } ///< \copydoc base_lkptr::operator X*() const.

    bool isNull()    const throw() { return b.isNull(); }    ///< \copydoc base_lkptr::isNull().
    bool unique()    const throw() { return b.unique(); }    ///< \copydoc base_lkptr::unique().
    int  use_count() const throw() { return b.use_count(); } ///< \copydoc base_lkptr::use_count().

    /// Releases the object.
    /// - Before: If this was the last reference, it also deletes the referenced object.
    /// - After: The pointer becomes \c NULL.
    /// - After: Equivalent to \c reset(0).
    void release() {
        if ( b.prev == &(this->b) ) { // autolinked ==> unique()
            X* toDelete = b.ptr;
            b.ptr = 0;    // restore invariant before "delete"
            if ( toDelete!=0 ) {
                delete [] toDelete; // this could throw an exception
            }
        }
        else { // ! unique() ==> unlink from pointer chain
            b.unlink();
            b.autolink(); // restore invariant: unique in chain
            b.ptr = 0;    // isNull() is true
        }
    }

    /// Resets the pointer so that it will point to \c "p".
    /// - Before: If this was the last reference, it also deletes the referenced object.
    /// - Before: \c "p==0" is a valid argument (\c NULL is ok).
    /// - After: The object pointed by \c "p" gets to be own by \c "this".
    /// - [DANGER] <code>V.reset( r.get() )</code> almost always is an error because
    ///   both \c V and \c r will destroy the referenced object. Use <code>V = r</code>.
    /// \dontinclude figures.h \skipline struct Point
    /// \until struct Rectangle
    /// \dontinclude test_lkptr.cpp \skipline test::inheritance
    /// \until }}
    void reset(X* p=0) {
        #if 0
            if (ptr == p) {
                return; // avoid self - anhilation
            }
        #endif
        release();
        b.ptr = p;
    }

    /// <code>(*this) = r</code>.
    void reset( const array_lkptr& r ) {
        this->operator= ( r ); // necessary to mask out reset(X*)
    #if 0
        {/* Note:
            Automatic conversion into a pointer is discouraged because it can lead
            to serious errors. If the conversion lktpr<X>::operator X*() exists, it
            would convert any array_lkptr<X> into its X*, which makes very easy the
            following erroneous usage:
                tik.reset( tak.get() ); // [ERROR] tik.reset( tak.operator X*() );
            This will causes double destruction of the pointed object because there
            are 2 unlinked array_lkptr<X>'s that own the same object.
        */
            X* ptrX = new X();
            array_lkptr<X> tik ( ptrX );
            array_lkptr<X> tak;

            tik = tak; assertTrue( tik.use_count() == 2 ); // ok
            tik.reset( tak.get() ); // [ERROR] tik.reset( tak.operator X*() );
            assertTrue( tik.use_count() == 1 );
            assertTrue( tak.use_count() == 1 ); // unlinked

            assertTrue( tik.next != &tak ); // they are unlinked
            assertTrue( tak.prev != &tik );
            assertTrue( tik.ptr == tak.ptr ); // both share the same object
        }   // ptrX gets destroyed twice
    #endif
    }

    /// <code>(*this) = r</code> [ from a derived class ].
    template <typename Y>
    void reset( const array_lkptr<Y>& r ) {
        this->operator=( r );
    }

    #ifdef array_lkptr_MERGE_IS_PUBLIC
        void merge( array_lkptr& r ) { b.merge( r.b ); } ///< \copydoc merge( base_lkptr& ).
        void weak_release() { b.weak_release(); }  ///< \copydoc weak_release( base_lkptr& ).
    #endif

    bool ok() const throw() { return b.ok(); } ///< \copydoc base_lkptr::ok().
    template <typename Y> friend bool check_ok( const array_lkptr<Y>& p ) throw();

private:
    template <typename Y> friend class base_lkptr; ///< Test \c array_lkptr<X>.

#if 0 // doesn´t work
private:
    array_array_lkptr<X>&
    operator=(  const array_array_lkptr<X>& r ); ///< Forbid mixing \c lktpr<> with \c array_lktpr<>.
    void reset( const array_array_lkptr<X>& r ); ///< Forbid mixing \c lktpr<> with \c array_lktpr<>.
    void merge( const array_array_lkptr<X>& r ); ///< Forbid mixing \c lktpr<> with \c array_lktpr<>.
#endif
}; // class array_lkptr<>

/// Swaps with \c r.
template <typename X>
void array_lkptr<X>::swap( array_lkptr<X>& r ) throw() {
    array_lkptr tmp = *this; // Thanks, David
    *this = r;
    r = tmp;
}

/// Swap <code> l <==> r </code>.
template <typename X>
inline void swap( array_lkptr<X>& l , array_lkptr<X>& r ) throw() {
    l.swap( r );
}

template <typename X>
inline bool check_ok( const array_lkptr<X>& p ) throw()
{ return check_ok( p.b ); } ///< \copydoc check_ok(const base_lkptr<X>&).

/// <code> (p == q) </code> ???
template <typename X>
inline bool operator<( const array_lkptr<X> & p, const array_lkptr<X> & q )  {
    return p.get() < q.get();
}

/// <code> (p == q) </code> ???
template <typename X>
inline bool operator==( const array_lkptr<X> & p, const array_lkptr<X> & q )  {
    return p.get() == q.get();
}

/// <code> (p != q) </code> ???
template <typename X>
inline bool operator!=( const array_lkptr<X> & p, const array_lkptr<X> & q )  {
    return ! (p == q);
}



/*  NOTE:
    When [this] and [r] are in the same chain and the chain has
    4 nodes, executing the pointer assignment sequence in merge()
    results in the 4-node chain being splitted into 2 chains
    of 2-nodes each.

    This 4-node chain diagram shows this special case, and shows
    why it is necessary to use a while() loop to implement merge().

               +---->----------------->---------+
    this      /                                 |
     ||      / ++===<=================<===\     |
     ||     /  ||                         \\    |
     \/    /   \/                          \\   v
    +-----/-+-------+             +-------+-\\----+
    |    /  | next  |             |       |  \\   |
    |  [**] | [**]  |             | [**]  |  [**] |  <== r
    |  prev |  ||   |             |   |   |       |
    +-------+--++---+             +---+---+-------+
        ^      ||                     |       /\
        |      ||                     |       ||
        |      \/                     v       ||
    +---+---+-------+             +-------+---++--+
    |   |   |       |             |       |   ||  |
    |  [**] | [**]  |<------------+--[**] |  [**] |  <== r_prev
    |       |   \\  |             |       |       |
    +-------+----\\-+             +-------+-------+
      /\          \\                          /\
      ||           \\                         ||
      ||            \===>=================>===++
    this_next

    // Execute this code in the above 4-node chain:
    r.prev = this;
    this->next = &r;
    r_prev->next = this_next;
    this_next->prev = r_prev;

    // The results is these 2 [broken] 2-node chains:


              +----->----------------->---------+
    this     /                                  |
     ||     /  ++===<=================<===\     |
     ||    /   ||                         \\    |
     \/   /    \/                          \\   v
    +----/--+-------+             +-------+-\\----+
    |   /   |       |             |       |  \\   |
    | [**]  | [**]  |<------------+-[**]  |  [**] |  <== r
    |       |   \\  |             |       |       |
    +-------+----\\-+             +-------+-------+
                  \\                          /\
                   \\                         ||
                    \===>=================>===++


              +----->----------------->---------+
             /                                  |
            /  ++===<=================<===\     |
           /   ||                         \\    |
          /    \/                          \\   v
    +----/--+-------+             +-------+-\\----+
    |   /   |       |             |       |  \\   |
    | [**]  | [**]  |<------------+-[**]  |  [**] |  <== r_prev
    |       |   \\  |             |       |       |
    +-------+----\\-+             +-------+-------+
      /\          \\                          /\
      ||           \\                         ||
      ||            \===>=================>===++
    this_next

*/

#endif // lkptr_h
#undef COMPILER_lkptr // clean up your own dirt

// EOF: lkptr.h