Usable flyweight template class

[Daniel Lidström]

Hello!

I have recently created a cool flyweight template class. It is intended to
make it very easy to implement the flyweight design pattern. Let me show
some examples of its usage:

// we're going to make this class into a flyweight
struct State
{
std::string s1;
std::string s2;
// need to be able to compare states
bool operator==(const State& right) const
{
return s1==right.s1 && s2==right.s2;
}
};

// need to be able to hash states
std::size_t hash_value(const State& state)
{
std::size_t seed = 0;
boost::hash_combine(seed, state.s1);
boost::hash_combine(seed, state.s2);
return seed;
}

int main()
{
using namespace GFL;

State state1 = { "Daniel", "Lidstrom" };
State state2 = { "Bjarne", "Stroustrup" };

flyweight<State> fw1(state1);
flyweight<State> fw2(state2);

assert(fw1!=fw2);
fw1 = fw2;
assert(fw1==fw2);

// change members back to original
fw1->s1 = "Daniel";
fw1->s2 = "Lidstrom";

assert(fw1==state1); // fw1 now points back to original
}

Everytime a flyweight<State> object is created that existed previously, the
only memory overhead will be a pointer. The requirements of the fly object
is that it is EqualityComparable, CopyConstructible, and "Hashable". If you
use streaming you also have DefaultConstructible requirement.

Let's go straight to the code from here. This code should compile (with
some small modifications that you can probably do) with eVC4+STLport,
VC6+STLport, VC7.1, and gcc-4.1 (needs tr1/unordered_multimap). As you will
see I have used boost::hash, but you should be able to replace that very
easily. There is a more advanced flyweight library getting ready to enter
boost (which likely won't compile with eVC4), and I have stolen some of the
ideas for this class.

#include <boost/functional/hash.hpp> // hash_value

#if defined(_MSC_VER) && _MSC_VER>=1300
#include <hash_map> // hash_multimap
namespace GFLUtils = stdext;
#elif defined(STLPORT)
#include <hash_map>
namespace GFLUtils = std;
#elif defined(__GNUC__)
#include <tr1/unordered_map>
namespace GFLUtils = std::tr1;
#endif

namespace GFL
{
//! Used to hash and compare flyweights.
struct flyweight_traits
{
//!
//! Compare two flyweights.
//!
template<class T>
static bool equal(const T& left, const T& right)
{
return left == right;
}

//!
//! Compute the hash of a flyweight.
//!
template<class T>
static std::size_t hash(const T& t)
{
return hash_value(t);
}
};

//!
//! @author Daniel Lidstrom <daniel....@sbg.se>
//! @date 2007-11-16 11:20
//! @ingroup GFL
//! flyweight design pattern. Allows you to easily create flyweight
//! classes.
//!
template<class fl, class tr=flyweight_traits>
class flyweight
{
public:

typedef fl fly;
typedef tr traits;

//!
//! Default constructor.
//!
flyweight()
{
mfly = get_factory().insert(fly());
}

//!
//! Constructor.
//!
//! @param fly fly object (will be copied)
//!
flyweight(const fly& fly)
{
mfly = get_factory().insert(fly);
}

//!
//! Assignment operator.
//!
flyweight& operator=(const fly& fly)
{
return operator=(flyweight(fly));
}

//!
//! Swap contents of two flyweights.
//!
void swap(flyweight& right)
{
std::swap(right.mfly, mfly);
}

//!
//! Equality comparison. Two flyweights are considered equal
//! if their internal pointers are equal.
//!
friend bool operator==(const flyweight& left, const flyweight& right)
{
return &left.get() == &right.get();
}

friend bool operator!=(const flyweight& left, const flyweight& right)
{
return !(left==right);
}

//!
//! Output stream operator.
//!
template<class Stream>
Stream& StreamOut(Stream& stream) const
{
stream << get();
return stream;
}

//!
//! Input stream operator.
//!
template<class Stream>
Stream& StreamIn(Stream& stream)
{
fly f;
stream >> f;
operator=(flyweight(f));
return stream;
}

//!
//! Accessor.
//!
//! @return Fly
//!
const fly& get() const
{
return *mfly;
}

//!
//! Internal class used to allow changing of
//! a flyweight using the -> operator.
//!
class fly_proxy
{
flyweight& mflyweight;
fly mfly;

public:

fly_proxy(flyweight& f)
: mflyweight(f),
mfly(*f.mfly)
{}

// Exceptions are not allowed to propagate from destructors,
// is a requirement for using the standard library containers.
// That is very likely *not* a requirement for fly_proxy.
~fly_proxy()
{
mflyweight = mfly;
}

fly* operator->()
{
return &mfly;
}
};
friend class fly_proxy;

//!
//! Provides an easy way to access member functions of the fly.
//!
const fly* operator->() const
{
return mfly;
}

//!
//! Non-const version.
//!
fly_proxy operator->()
{
return fly_proxy(*this);
}

//!
//! Automatic conversion.
//!
operator const fly&() const
{
return get();
}

private:

class hashed_factory
{
#if defined(__GNUC__)
typedef GFLUtils::unordered_multimap<std::size_t, const fly> Map;
#else
typedef GFLUtils::hash_multimap<std::size_t, const fly> Map;
#endif
typedef typename Map::const_iterator const_iterator;
Map mMap;

public:

const fly* insert(const fly& fly)
{
std::size_t hashv = traits::hash(fly);
return insert(fly, hashv);
}

private:

const fly* insert(const fly& f, std::size_t hashv)
{
const fly* ret = 0;

std::pair<const_iterator, const_iterator> p
= mMap.equal_range(hashv);

for( const_iterator it=p.first; !ret && it!=p.second; ++it )
{
const fly& foundFly = it->second;
if( traits::equal(foundFly, f) )
{
ret = &foundFly;
}
}
// if we didn't find a previous fly, insert a new
if( !ret )
{
mMap.insert(std::make_pair(hashv, f));
ret = insert(f, hashv);
}
return ret;
}
};

static hashed_factory& get_factory()
{
static hashed_factory factory;
return factory;
}

const fly* mfly;
};
}

template<class Ostream, class fl, class tr>
Ostream& operator<<(Ostream& os, const GFL::flyweight<fl, tr>& f)
{
return f.StreamOut(os);
}

template<class Istream, class fl, class tr>
Istream& operator>>(Istream& is, GFL::flyweight<fl, tr>& f)
{
return f.StreamIn(is);
}

I would like to have constructive criticism, if possible. For example:
* How do I separate the internal factory into a template parameter, so that
for example the Hashable requirement can be changed.
* How can I create a policy so that entries in the internal factory can be
erased when no flyweight refers to them any longer. It is ok to use
weak_ptr and shared_ptr for this implementation, I just don't have a good
idea of how.
* Any other ideas for improvements?

All comments are welcome!

--
Daniel

[Tom Widmer [VC++ MVP]]

Daniel Lidström wrote:
> Hello!
>
> I have recently created a cool flyweight template class. It is intended to
> make it very easy to implement the flyweight design pattern. Let me show
> some examples of its usage:

[snip usage example]

> Everytime a flyweight<State> object is created that existed previously, the
> only memory overhead will be a pointer. The requirements of the fly object
> is that it is EqualityComparable, CopyConstructible, and "Hashable". If you
> use streaming you also have DefaultConstructible requirement.
>
> Let's go straight to the code from here. This code should compile (with
> some small modifications that you can probably do) with eVC4+STLport,
> VC6+STLport, VC7.1, and gcc-4.1 (needs tr1/unordered_multimap). As you will
> see I have used boost::hash, but you should be able to replace that very
> easily. There is a more advanced flyweight library getting ready to enter
> boost (which likely won't compile with eVC4), and I have stolen some of the
> ideas for this class.

> namespace GFL
> {
> //! Used to hash and compare flyweights.

Are you sure you don't want:

template <class Fly>

> struct flyweight_traits
> {
> //!
> //! Compare two flyweights.
> //!
> template<class T>
> static bool equal(const T& left, const T& right)
> {
> return left == right;
> }

since that allow you to do this:

typedef std::tr1::shared_ptr<Fly const> pointer;

//factory::insert must return type convertible to pointer
typedef default_factory_type<Fly> factory;
static factory& get_factory()
{
static factory f;
return f;
}

> };
>
> //!
> //! @author Daniel Lidstrom <daniel....@sbg.se>
> //! @date 2007-11-16 11:20
> //! @ingroup GFL
> //! flyweight design pattern. Allows you to easily create flyweight
> //! classes.
> //!
> template<class fl, class tr=flyweight_traits>

or
template<class fl, class tr=flyweight_traits<f1> >

> class flyweight
> {
> public:
>
> typedef fl fly;
> typedef tr traits;

typedef typename tr::pointer pointer;

[snip good stuff]

> //!
> //! Internal class used to allow changing of
> //! a flyweight using the -> operator.
> //!
> class fly_proxy
> {
> flyweight& mflyweight;
> fly mfly;
>
> public:
>
> fly_proxy(flyweight& f)
> : mflyweight(f),
> mfly(*f.mfly)
> {}
>
> // Exceptions are not allowed to propagate from destructors,
> // is a requirement for using the standard library containers.
> // That is very likely *not* a requirement for fly_proxy.

What if the non-const member function of fly that you are calling
throws? If the assignment in the destructor below also throws, won't you
get an immediate abort?

> ~fly_proxy()
> {
> mflyweight = mfly;
> }
>
> fly* operator->()
> {
> return &mfly;
> }
> };
> friend class fly_proxy;
>
> //!
> //! Provides an easy way to access member functions of the fly.
> //!
> const fly* operator->() const
> {
> return mfly;
> }
>
> //!
> //! Non-const version.
> //!
> fly_proxy operator->()
> {
> return fly_proxy(*this);
> }

Hmm, interesting, and I imagine it will usually work.

>
> //!
> //! Automatic conversion.
> //!
> operator const fly&() const
> {
> return get();
> }
>
> private:

static typename traits::factory& get_factory()
{
return traits::get_factory();
}

Alternatively, you could call traits::get_factory directly from code
needing the factory, obviating the need for the factory typedef.

pointer mfly;
};
}

> I would like to have constructive criticism, if possible. For example:
> * How do I separate the internal factory into a template parameter, so that
> for example the Hashable requirement can be changed.

See above.

> * How can I create a policy so that entries in the internal factory can be
> erased when no flyweight refers to them any longer. It is ok to use
> weak_ptr and shared_ptr for this implementation, I just don't have a good
> idea of how.

The factory type you use just needs to have a variable of type:
std::unordered_multimap<std::size_t, std::tr1::weak_ptr<const fly> > mMap;
pointer == shared_ptr<const fly>

Additionally, you could at certain times erase entries that have an
empty weak_ptr, or have a specific call to let you do it.

> * Any other ideas for improvements?

You could write a policy based factory to go with it, offering policies
for thread safety (e.g. insert is synchronised), etc.

Tom

[Daniel Lidström]

On Thu, 22 Nov 2007 14:21:29 +0000, Tom Widmer [VC++ MVP] wrote:

> Daniel Lidström wrote:
>> * How can I create a policy so that entries in the internal factory can be
>> erased when no flyweight refers to them any longer. It is ok to use
>> weak_ptr and shared_ptr for this implementation, I just don't have a good
>> idea of how.
>
> The factory type you use just needs to have a variable of type:
> std::unordered_multimap<std::size_t, std::tr1::weak_ptr<const fly> > mMap;
> pointer == shared_ptr<const fly>
>
> Additionally, you could at certain times erase entries that have an
> empty weak_ptr, or have a specific call to let you do it.
>
>
>> * Any other ideas for improvements?
>
> You could write a policy based factory to go with it, offering policies
> for thread safety (e.g. insert is synchronised), etc.

Thanks for the constructive criticism Tom! I will try your very good
suggestions. About exception safety in the operator-> chaining, I will have
to do some experiments.

--
Daniel