muta_ref.H

/*
 * This file is part of the "Archon" framework.
 * (http://files3d.sourceforge.net)
 *
 * Copyright © 2002 by Kristian Spangsege and Brian Kristiansen.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation under the terms of the GNU General Public License is
 * hereby granted. No representations are made about the suitability of
 * this software for any purpose. It is provided "as is" without express
 * or implied warranty. See the GNU General Public License
 * (http://www.gnu.org/copyleft/gpl.html) for more details.
 *
 * The characters in this file are ISO8859-1 encoded.
 *
 * The documentation in this file is in "Doxygen" style
 * (http://www.doxygen.org).
 */

#ifndef ARCHON_UTILITIES_MUTA_REF_H
#define ARCHON_UTILITIES_MUTA_REF_H

#include <archon/util/exception.H>
#include <archon/util/atomic.H>

namespace Archon
{
  namespace Utilities
  {
    using namespace std;

    template<typename T>
    struct MutaRef
    {
      typedef T ObjectType;

      void reset(T *q = 0)
      {
        _reset(q);
      }

      void mutate()
      {
        if(!p) return;

        /*
         * Since this MutaRef variable exists, the reference count of
         * the referenced object cannot be zero. It cannot _become_
         * zero since concurrent access to a MutaRef variable is
         * forbidden.
         *
         * If we find the object to be in the leaked state we know
         * it will remain in the leaked state (zero was not an
         * option.) If we find that the object has a reference count
         * of 1 we known that this MutaRef variable is the only
         * counted reference to the object, thus no new counted
         * references can be made to the object during the execution
         * of this function. Neither can the object enter the leaked
         * state.
         *
         * In summary, both -1 and 1 are stable states individually.
         *
         * Please note that the inverse of the test is not stable
         * (state 1 may be entered after the test but before the clone
         * operation), thus, the cloning may be carried out in vain.
         */
        if(p->refCount == -1 || p->refCount == 1) return;

        _clone();
      }

      void leak()
      {
        if(!p) return;

        /*
         * Since this MutaRef variable exists, the reference count of
         * the referenced object cannot be zero. It cannot become zero
         * since concurrent access to a MutaRef variable is forbidden.
         *
         * If we find that the object is in the leaked state we know
         * that it will remain in the leaked state (zero was not an
         * option.) So, in this case we are done.
         */
        if(p->refCount == -1) return;

        /*
         * At this point we know that the reference count is at least
         * 1. If we find it to be 1 we know that it will remain on
         * 1. Thus, failure of the following test is enough to
         * guarantee that the referenced object is unshared.
         *
         * We also have a guarantee that the referenced object is
         * unshared after calling clone().
         */
        if(p->refCount != 1) _clone();

        /*
         * At this point we know for sure that the reference count is
         * equal to 1 and will remain equal to 1 untill the assignment
         * below modifies it.
         */
        p->refCount = -1;
      }

      MutaRef(): p(0) {}

      MutaRef(const MutaRef &r): p(_copy(r.p)) {}

      ~MutaRef()
      {
        _break();
      }

      MutaRef &operator=(const MutaRef &r)
      {
        _reset(r.p);
        return *this;
      }

      T *operator->() const
      {
        if(p) return p;
        ARCHON_THROW1(StateException, "Dereferencing null");
      }

      operator bool() const { return p; }

    private:
      T *p;

      void _clone()
      {
        _break(dynamic_cast<T *>(p->refClone()));
        ++p->refCount;
      }

      static T *_copy(T *q)
      {
        if(!q) return 0;

        if(q->refCount == -1) q = dynamic_cast<T *>(q->refClone());

        /*
         * It is important that the incrementation below never happens
         * on an object in the leaked state.
         *
         * A transition to the leaked state can only occur from a
         * state where the reference count is 1. Thus to become -1 it
         * must fist become 1.
         *
         * When the reference count reaches 1 there must be
         * exactly 1 other MutaRef variables pointing to the same
         * object as this MutaRef variable (this MutaRef varibale
         * does not yet count.)
         *
         * This rules out the cases where the reference count is zero
         * at entry and the those where we did a clone operation,
         * since in those cases no other MutaRef variable could exist
         * (we are busy creating the first one.)
         *
         * Consequently this case must be one where we are
         * constructing this MutaRef variable as a copy of another.
         *
         * Since the construction of this MutaRef variable is not yet
         * complete, a transition to the leaked state must be
         * performed by calling leak() on some other MutaRef variable.
         *
         * Since there was only 1 other MutaRef variable, the one on
         * which leak() is called must be the same one that we are
         * copying.
         *
         * Now, such concurrent access is illegal and thus impossible.
         *
         * In other words, we know that the reference count cannot be
         * -1 when the following incrementation occurs.
         */
        ++q->refCount;

        return q;
      }

      void _break(T *q = 0)
      {
        /*
         * If we find the object to be in the leaked state, there is
         * only one reference to the object which must be the
         * reference we are about to destroy. Since this reference is
         * protected against access from other threads, the reference
         * count will remain on -1 untill the object is destoyed
         * below.
         *
         * On the other hand, if we find the object not to be in the
         * leaked state, we know that the reference count will be at
         * least 1 and that it will continue to be at least 1 until
         * modified by this thread below. We know this because the
         * refernce count was not 0 at entry and cannot become 0 prior
         * to the modification below since this variable represented
         * one reference at entry and access from other threads is
         * forbidden. Further more, a transition to the leaked state
         * can only be initiated when the reference count is equal to
         * 1. If the reference count is 1 or does become 1 the object
         * can no longer be accessed by other threads and thus, a
         * transition to the leaked state is impossible.
         */
        if(p && (p->refCount == -1 || p->refCount.decAndZeroTest()))
          p->refDelete();

        p = q;
      }

      void _reset(T *q)
      {
        if(p == q) return;
        _break(_copy(q));
      }
    };

    struct MutaRefObjectBase
    {
    protected:
      virtual MutaRefObjectBase *refClone() const = 0;

      virtual void refDelete() throw()
      {
        delete this;
      }

      MutaRefObjectBase(): refCount(0) {}

      virtual ~MutaRefObjectBase() {}

    private:
      template<typename T> friend struct MutaRef;

      /*
       * <pre>
       *
       * -1 Leaked object
       *  0 Fresh unreferenced object (or abandoned object)
       * >0 Referenced object
       *
       *   Fresh    Referenced    Leaked    Abandoned
       *
       *                     ,--> (-1)
       *    (0) ---> (>0) --<
       *                     `------------>  (0)
       *
       * </pre>
       *
       * The abandoned state will only exist shortly since it triggers
       * the deletion of the object.
       */
      mutable Atomic refCount;
    };

    template<typename T>
    struct MutaRefObject: MutaRefObjectBase
    {
      MutaRefObject(T v): value(v) {}

      MutaRefObject *refClone() const { return new MutaRefObject(value); }

      T value;
    };
  }
}

#endif // ARCHON_UTILITIES_MUTA_REF_H

---