/*****************************************************************************
 * $Id: gfx_shared_val.hh,v 1.14 2006/08/03 02:17:21 devel Exp $
 * @file
 * @author	Jim E. Brooks  http://www.jimbrooks.org
 * @brief	Template class for sharing objects by value.
 * @verbatim
 *
 * Which to use?  SharedVal or SharedPtr?
 * --------------------------------------
 * Use SharedVal if:
 * - want maximum sharing but you can't predetermine which objects
 *   can be shared and need code to determine that
 * Use SharedPtr if:
 * - you know in advance that an object will be shared
 * - or need to share arrays
 * - or writing a deep copy constructor isn't practical
 * - or writing operator<() isn't practical
 * - or need speed (zero-copy)
 *
 * Overview:
 * ---------
 * This is a singleton template class for sharing non-array objects by value
 * using a reference count.  Copies of objects, not the originals, are shared.
 * When given an object (value) never before encountered, ShareVal() will
 * create a new object with the same value using its copy constructor
 * and store it in a STL map.  Thereafter, ShareVal() will return a pointer
 * to the copy of an object when passed an object that has the same value,
 * and increments its* reference count.  UnshareVal() decrements the reference count,
 * and when the count reaches zero, will free the object (which is a copy).
 *
 * Note that a copy of an object is shared, not the original.
 * The value of an object, not its address, is tested for equality.
 * The caller is responsible for deleting the original if appropriate.
 *
 * Usage:
 * ------
 * - Declare a SharedValFactory<> static member variable in namespace gfx:
 *   namespace gfx {
 *       template<> SharedValFactory<YourClass>* SharedValFactory<YourClass>::mInstance = NULL;
 *   } // namespace gfx
 * - Call the interface non-member functions ShareVal() and UnshareVal().
 * - Your class must have a copy constructor.
 * - Your copy constructor probably should do a deep copy.
 * - Your class must have a non-member operator<() (required by STL map).
 * - A copy of the original object is stored and is the basis of sharing.
 *   The caller is responsible for freeing the original object.
 *
 * Caveats:
 * --------
 * This class has the potential for being slow if an object has a lot of members.
 * Your copy constructor and destructor will be called several times
 * (depending on the STL implementation).  As the STL map will call
 * your operator<(), traversing the STL map (tree) could be slow.
 *
 * WARNING: Beware of putting classes with SharedVal members into
 * STL containers such as vector unless your class has a copy constructor.
 * Otherwise, a bug occurs if your destructor unshares the object
 * but the STL could use the default member-wise copy which would
 * copy an stale/invalid pointer to the shared object.
 *
 * Alternative (sharing an object's resources):
 * --------------------------------------------
 * (This alternative is implemented as SharedPtr in gfx_shared_ptr.hh.)
 * If writing a copy constructor that does deep-copy is impractical
 * (which the SharedVal template class requires),
 * an alternative is to share an object's resources, rather than the object itself.
 * This applies to objects with a small foot-print and whose resources are pointed to.
 * A copy constructor could be safely written to copy pointers to resources
 * by using an "untied" reference count (a reference count allocated on the heap).
 * Sharing an object is effectively done by the copy constructor.
 * The destructor only deletes the resources when the last object is deleted
 * (when the reference count becomes zero).
 *
 * Design notes:
 * -------------
 * Copies of objects are shared, rather than the originals, to avoid the
 * complication that would arise when the shared object's reference count
 * hits zero, but what if the original object is static (delete can't be used)
 * or if it's in the heap (delete should be used).
 * Testing object equality is done by their values, not their addresses,
 * as two separate objects could have the same value.
 * And a faux-pas was to cache objects using their pointers (in an attempt
 * to bypass tree/map traversal) because of the possibility of the C++ library
 * recycling the same address on the heap but for objects with different values.
 *
 * The interface to the class are the non-member template functions ShareVal()
 * and UnshareVal().  UnshareVal() becomes a NOP when the program is exiting,
 * to avoid memory corruption when static objects are destroyed: destructors
 * of other static objects may try to call SharedValFactory::Unshare()
 * after a static SharedValFactory object was destroyed (C++ doesn't define
 * the order of destroying static objects).  However, a non-member function
 * can be safely called during exit, hence UnshareVal().  An aesthetic drawback
 * is requiring the client to define mInstance in namespace gfx.
 *
 * @endverbatim
 *//*
 * LEGAL:	COPYRIGHT (C) JIM E. BROOKS 2005
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE (GPL).
 *****************************************************************************/

#ifndef GFX_SHARED_VAL_HH
#define GFX_SHARED_VAL_HH

#include <utility>
#include <map>
#include "gfx_defs.hh"
#include "gfx_funcs.hh"

namespace gfx {

template<typename T> inline T*   ShareVal( const T* const obj );
template<typename T> inline void UnshareVal( const T* const obj );

////////////////////////////////////////////////////////////////////////////////
/// @brief Singleton template class for sharing objects based on a STL map.
///
/// map pair: (objectValue,(objectCopyPointer,referenceCount))
/// The map-key is the object's value.  The map-value is the pair of
/// a pointer to a copy of the same object and the object's reference count.
///
template<typename T>
class SharedValFactory
{
    PREVENT_COPYING(SharedValFactory<T>)
public:
    static SharedValFactory<T>* GetInstance( void )
    {
        if ( mInstance == NULL ) mInstance = new SharedValFactory<T>;
        return mInstance;
    }
#if TESTING
	// Normally, DeleteInstance() isn't called to avoid order-of-destruction pitfall.
    static void DeleteInstance( void )
    {
        delete mInstance;
		mInstance = NULL;
    }
#endif
#if DEBUG || STATS
	/// @return Number of shared objects.
	static uint Size( void )
	{
		return GetInstance()->mMap.size();
	}
#endif

private:
					SharedValFactory( void );
					~SharedValFactory();
	inline T*		Share( const T* const obj );
	inline void		Unshare( const T* const obj );

	typedef T                       MapKey;
	typedef std::pair<T*,int>       MapVal;		///< (objectCopyPointer,referenceCount)
	typedef std::map<MapKey,MapVal> Map;

    static SharedValFactory<T>* mInstance;
	Map						mMap;				///< (objectValue,(objectCopyPointer,referenceCount))

friend T* ShareVal<>( const T* const obj );
friend void UnshareVal<>( const T* const obj );
friend bool TestSharedVal( void );
};

/*****************************************************************************
 * Interface function for sharing an object (increment reference count).
 * Given a pointer to an object, returns a pointer to a shared copy.
 * If the same object is passed again, the pointer to the same copy will be returned.
 *****************************************************************************/
template<typename T> inline T*
ShareVal( const T* const obj )
{
    return SharedValFactory<T>::GetInstance()->Share( obj );
}

/*****************************************************************************
 * Interface function for unsharing an object (decrement reference count).
 *****************************************************************************/
template<typename T> inline void
UnshareVal( const T* const obj )
{
    // A C++ pitfall is the undefined order of destruction of static objects.
    // This object may be static and when it has been destroyed,
	// another static object may errorneously try to unshare objects.
    // Avoid the pitfall by doing nothing if program is exiting.
    if ( EX( ! gExitingGfx ) )
    {
        SharedValFactory<T>::GetInstance()->Unshare( obj );
    }
}

/*****************************************************************************
 * Constructor.
 *****************************************************************************/
template<typename T>
SharedValFactory<T>::SharedValFactory( void )
{
    // NOP;
}

/*****************************************************************************
 * Destructor.
 *****************************************************************************/
template<typename T>
SharedValFactory<T>::~SharedValFactory()
{
	// Delete the objects in the map.
	// They were created by the new operator and copy constructor.
	typename Map::iterator itr;
	for ( itr = mMap.begin(); itr != mMap.end(); ++itr )
	{
		T* obj = itr->second.first;
		delete obj;
	}
}

/*****************************************************************************
 * Share a copy of an object.  NULL can be passed (NOP).
 * @return Pointer to a shared copy of the original object.
 *
 * A copy of the original object is stored and is the one that is shared.
 * The caller is responsible for freeing the original object.
 *
 * If the object was never encountered before, a new object is constructed
 * (by pointer) using a copy constructor, and stored in the STL map.
 * Otherwise, increments its reference count (for sharing an object).
 *****************************************************************************/
template<typename T>
T*
SharedValFactory<T>::Share( const T* const obj )
{
	typename Map::iterator itr;

	// For convenience (this eliminates lots of special-case code elsewhere).
	if ( UX(obj == NULL) ) return NULL;

	itr = mMap.find( *obj );
	if ( EX( itr != mMap.end() ) )
	{
		// Found it in the map.
		// Increment its reference count, return its pointer.
		++itr->second.second;
		return itr->second.first;
	}
	else
	{
		// Not there.  Use a copy constructor to create a new object,
		// then store its pointer in the map so it can be shared.
		T* copy = new T( *obj );
		std::pair<typename Map::iterator,bool> insertion;
		insertion = mMap.insert( std::make_pair( *obj, std::make_pair(copy,1) ) ); // reference count = 1
		return copy;
	}
}

/*****************************************************************************
 * Unshare a copy of an object.  NULL can be passed (NOP).
 *
 * The object's reference count is decremented and the object will be deleted
 * when the count reaches zero.
 *****************************************************************************/
template<typename T>
void
SharedValFactory<T>::Unshare( const T* const obj )
{
	// For convenience (this eliminates lots of special-case code elsewhere).
	if ( UX(obj == NULL) ) return;

	// Is the object in the map?
	typename Map::iterator itr = mMap.find( *obj );
	if ( itr != mMap.end() )
	{
		// Yes.  Decrement its reference count.  Free it if count has reached zero.
		if ( --itr->second.second == 0 )
		{
			// Delete object.
			T* objMapped = itr->second.first;
			delete objMapped;		// objMapped now invalid!

			// Remove from map.
			mMap.erase( itr );		// itr now invalid!
		}
	}
}

} // namespace gfx

#endif // GFX_SHARED_VAL_HH
