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.

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

/// 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

template <class X> class lkptr; // class declaration follows

/** 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 <class X>
class lkptr {
private: // Rep fields have the "m_" prefix
    X     * m_ptr;  ///< Pointer to referenced object (can be a \c NULL pointer).
    lkptr * m_prev; ///< Next in pointer chain.
    lkptr * m_next; ///< Previous in pointer chain.
public:
    typedef X element_type;   ///< Standard name for the pointed object.
    typedef X value_type;     ///< Standard name for the pointed object.

    /// Default constructor and constructor from a regular pointer.
    explicit lkptr(X* p = 0) throw() : m_ptr(p) { m_prev = m_next = this; }
    ~lkptr() { fast_release(); } ///< Destructor. Delete only if last reference.

    /// Copy constructor: share the object with other pointers.
    lkptr( const lkptr& r ) throw() { acquire( const_cast<lkptr*>( &r ) ); }
    /// Copy operator: share the object with other pointers.
    lkptr& operator=( const lkptr& r ) {
        if (this != &r) { // avoid self - anhilation
            fast_release(); // all the fields are in a broken state
            #ifdef lkptr_NULL_POINTERS_ARE_ALONE
                if ( r.m_ptr == 0) {
                    m_prev = m_next = this;  // restore invariant: unique in chain
                    m_ptr = 0; // NULL pointers are always alone
                }
                else {
                    acquire( const_cast< lkptr<X> * >( &r ) ); // r's chain fields will be changed
                }
            #else
                acquire( const_cast< lkptr<X> * >( &r ) ); // r's chain fields will be changed
            #endif
        }
        return *this;
        /*  NOTE:
            A lkptr<D> will be implicitly converted to a lkptr<B>
            if a D* can be converted to a B*. ( D ~~ Derived ... B ~~ Base )
        */
    }
    void swap( lkptr & r ) throw();
    // Pointer access operators (these never throw exceptions)
    X* get()        const throw() { return  m_ptr; } ///< Returns a pointer to referenced object.
    X& value()      const throw() { return *m_ptr; } ///< Returns the referenced object.
    X& operator*()  const throw() { return *m_ptr; } ///< Returns the referenced object.
    X* operator->() const throw() { return  m_ptr; } ///< Returns a pointer to referenced object.
    operator X* ()  const throw() { return  m_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 m_ptr == 0; }

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

    /// Returns how many pointers are sharing the object referenced by \c "this".
    int  use_count() const throw();

    /// 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() {
        fast_release();          // all the fields are in a broken state
        m_prev = m_next = this;  // restore invariant: unique in chain
        m_ptr = 0;
    }

    /// Releases the object.
    /// - 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() {
        m_prev->m_next = m_next; // unlink from pointer chaing
        m_next->m_prev = m_prev;
        m_prev = m_next = this;  // restore invariant: unique in chain
        m_ptr = 0;
    }

    /// 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".
    void reset(X* p=0) {
        if (m_ptr == p) {
            return; // avoid self - anhilation
        }
        fast_release(); // all the fields are in a broken state
        m_prev = m_next = this;  // restore invariant: unique in chain
        m_ptr = p;
    }

    bool ok() const throw();
    template <class Y> friend bool check_ok( const lkptr<Y>& p ) throw();

private:
    /// Makes \c this->m_ptr point to \c r.m_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->m_ptr is a \c NULL pointer.
    void acquire(lkptr* r) throw() {
        m_ptr = r->m_ptr;      // reference r's object
        m_next = r->m_next;
        m_next->m_prev = this; // 4 assignments to change the 4 next+prev chain pointers
        m_prev = r;
        r->m_next = this;
        // To double link with the list, "*r" must be changed. But the whole
        // implementation is easier if "*r" is const.
    }

    /// Releases the object.
    /// - If \c this->m_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 ( m_prev == this ) { // auto-linked ==> unique()
            if ( m_ptr!=0 ) {
                delete m_ptr; // this could throw an exception
            }
        }
        else { // ! unique() ==> unlink from pointer chain
            m_prev->m_next = m_next;
            m_next->m_prev = m_prev;
        }
        // leaves all the fields in a broken state:
        // m_prev = m_next = this; // set-all to nil pointer
        // m_ptr = 0;
    }

    template <class Y> friend class test_lkptr; ///< Test \c lkptr<X>.
}; // class lkptr

/// Swaps with \c r.
template <class X>
void lkptr<X>::swap ( lkptr<X>& r ) throw() {
#if 1 // David
    lkptr tmp = *this;
    *this = r;
    r = tmp;
#else // Adolfo
    if ( r.m_next == this || r.m_prev == this ) { // they are chained together
        return; // they both must point to same object
    }
    {   // swap pointers
        X* tmp = this->m_ptr;
        m_ptr = r.m_ptr;
        r.m_ptr = tmp;
    }

    if ( m_prev == this ) {
        if ( r.m_prev == & r ) {
            return; // both are already alone by themselves
        }
        else { // "*this" is alone but "r" is not
            this->m_next = r.m_next;
            this->m_prev = r.m_prev;
            r.m_next->m_prev = this;
            r.m_prev->m_next = this;
            r.m_next = r.m_prev = & r; // "r" becomes alone
        }
    }
    else if ( r.m_prev == & r ) {  // "r" is alone but "*this" is not
        r.m_next = this->m_next;
        r.m_prev = this->m_prev;
        this->m_next->m_prev = & r;
        this->m_prev->m_next = & r;
        m_next = m_prev = this; // "*this" becomes alone
    }
    else { // general case: neither is alone
        {   // set the pointers for the other nodes
            this->m_prev->m_next = & r;
            this->m_next->m_prev = & r;
            r.m_next->m_prev = this;
            r.m_prev->m_next = this;
        }
        {   // swap this->m_prev <==> r.m_prev
            lkptr * tmp = this->m_prev;
            this->m_prev = r.m_prev;
            r.m_prev = tmp;
        }
        {   // swap this->m_next <==> r.m_next
            lkptr * tmp = this->m_next;
            this->m_next = r.m_next;
            r.m_next = tmp;
        }
    }
#endif
}

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

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

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

/// Verifies the invariant for class \c lkptr<Y>.
/// \see lkptr<Y>::ok().
template <class Y>
inline bool check_ok( const lkptr<Y>& 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 "m_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
     +--------+-------+  "m_ptr" points to the object
     | m_prev |       |
     +--------+ m_ptr +
     | m_next |       |  "m_next" is next in chain
     +--------+-------+  "m_prev" is previous in chain
    \endcode

    \par The invariant: Description with words.
*/
template <class X>
bool lkptr<X>::ok() const throw() {
    {   // check a single element double linked chain
        if      ( (m_next==this) && (m_prev==this) ) { /* Ok */ }
        else if ( (m_next==this) || (m_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 m_next && \c m_prev pointing to itself (\c this).
        }
    }

    {   // check the double linked chain
        const lkptr* q = this;
        do {
            if ( (q == q->m_next->m_prev) && (q == q->m_prev->m_next) ) { /* Ok */ }
            else {
                return false;
                /// - Invariant (2) (broken link): the double linked pointer can never be broken.
            }
            if (this->m_ptr == q->m_ptr) { /* Ok */ }
            else {
                return false;
                /// - Invariant (3) (broken m_ptr): Every pointer in the chain should reference
                ///   the same object.
            }
            q = q->m_next;
        } while (q != this);
    }

    // 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( * m_ptr ) ) { /* Ok */ }
        else {
            return false; /// - Invariant (4) (corrupt pointed object)
        }
    #endif
    }

    if ( m_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 ( (m_next==this) && (m_prev==this) ) { /* Ok */ }
        else {
            return false;
            /// - Invariant (5) (auto-link): A \c NULL pointer should be self-linked with
            ///   both \c m_next && \c m_prev pointing to itself (\c this).
        }
    #endif
    }

    return true;
}

#endif // lkptr_h
#undef COMPILER_lkptr

// EOF: lkptr.h

---