Repository of all objects of a certain type

[Marcel Müller]

Hi,

I have an application that uses internal business objects with a primary
key. For each key at most one instance must exist in memory. Otherwise
the content will become out of sync. The lifetime is managed by a
reference counter.


Currently this is implemented like that:

// Base class for the intrusive pointer interface.
class ref_count
{private
int RefCount;

template <class T>
friend class my_intrusive_ptr<T>;
};

template <class K>
class IComareableTo
{ virtual int CompareTo(const K& r) = 0;
};

// Container class that stores pointers to T accessable with the key K
// using the compare expression
// T* elem;
// elem->CompareTo(const K& key);
// T must implement ICompareTo<K>.
template <class T, class K>
class sorted_vector_p
{ typedef T* value_type;
typedef const K& key_type;
// ...

// Get an existing or an empty slot in the vector.
// In the latter case the returned pointer is NULL and the new slot is
// reserved at the location where an element with the given key must
// be inserted.
T*& get(const K& key);
// Find an existing object or return NULL.
T* find(const K& key) const;
// remove a reference or return NULL
T* erase(const K& key);
};


class MyKey
{public:
int Key1; // for example
int Key2;
};

class MyObject : public ref_count, public ICompareableTo<MyKey>
{public:
const MyKey Key;
private:
MyObject(const MyKey& key) : Key(key) {}
public:
~MyObject();

virtual int CompareTo(const K& r);

// Repository
private:
static sorted_vector_p<MyObject, MyKey> RP_Index;
public:
// Factory:
// Fetches an existing instance or creates a new one for the key K.
static my_intrusive_ptr<MyObject> GetByKey(const K& key);
// Fetches an existing instance or return NULL.
static my_intrusive_ptr<MyObject> FindByKey(const K& key)
{ return RP_Index.find(key); }
};

MyObject::~MyObject()
{ assert(RP_Index.erase(Key) == this);
}

my_intrusive_ptr<MyObject> MyObject::GetByKey(const K& key)
{ MyObject*& ptr = RP_Index.get(key);
if (!ptr)
ptr = new MyObject(key);
return ptr; // Implicit conversion to my_intrusive_ptr
}


This works as expected so far. However I have to copy and adapt the
static functions and the repository stuff for each type which requires
an index like that. In fact it is much more than above, because almost
all public functions are thread-safe.

I would like a more generic solution. But up to now I did not have a
better idea. At least they require the constructor of MyObject to be public.

Any recommendations for the above task?


Marcel

 

[James Kanze]

I have an application that uses internal business objects with
a primary key. For each key at most one instance must exist in
memory. Otherwise the content will become out of sync. The
lifetime is managed by a reference counter.

Currently this is implemented like that:

// Base class for the intrusive pointer interface.
class ref_count
{
private:
int RefCount;

template <class T>
friend class my_intrusive_ptr<T>;
};

template <class K>
class IComareableTo
{
virtual int CompareTo(const K& r) = 0;
};

// Container class that stores pointers to T accessable with the key K
// using the compare expression
// T* elem;
// elem->CompareTo(const K& key);
// T must implement ICompareTo<K>.
template <class T, class K>
class sorted_vector_p
{
typedef T* value_type;
typedef const K& key_type;
// ...

// Get an existing or an empty slot in the vector.
// In the latter case the returned pointer is NULL and the new slot is
// reserved at the location where an element with the given key must
// be inserted.
T*& get(const K& key);
// Find an existing object or return NULL.
T* find(const K& key) const;
// remove a reference or return NULL
T* erase(const K& key);
};

class MyKey
{
public:
int Key1; // for example
int Key2;
};

class MyObject : public ref_count, public ICompareableTo<MyKey>
{
public:
const MyKey Key;
private:
MyObject(const MyKey& key) : Key(key) {}
public:
~MyObject();

virtual int CompareTo(const K& r);

// Repository
private:
static sorted_vector_p<MyObject, MyKey> RP_Index;
public:
// Factory:
// Fetches an existing instance or creates a new one for the key K.
static my_intrusive_ptr<MyObject> GetByKey(const K& key);
// Fetches an existing instance or return NULL.
static my_intrusive_ptr<MyObject> FindByKey(const K& key)
{ return RP_Index.find(key); }
};

MyObject::~MyObject()
{
assert(RP_Index.erase(Key) == this);
}

my_intrusive_ptr<MyObject> MyObject::GetByKey(const K& key)
{
MyObject*& ptr = RP_Index.get(key);
if (!ptr)
ptr = new MyObject(key);
return ptr; // Implicit conversion to my_intrusive_ptr
}

This works as expected so far. However I have to copy and
adapt the static functions and the repository stuff for each
type which requires an index like that. In fact it is much
more than above, because almost all public functions are
thread-safe.

I would like a more generic solution. But up to now I did not
have a better idea. At least they require the constructor of
MyObject to be public.

Any recommendations for the above task?

Would something like the following work here:

template< typename ObjType, typename KeyType >
class ContainerSupport
{
private:
static sorted_vector_p<ObjType, KeyType> RP_Index;
public:
// Factory:
// Fetches an existing instance or creates a new one for the
key K.
static my_intrusive_ptr<ObjType> GetByKey(const K& key);
// Fetches an existing instance or return NULL.
static my_intrusive_ptr<ObjType> FindByKey(const K& key)
{ return RP_Index.find(key); }
} ;

then:

class MyObject : public ContainerSupport< MyObject, MyKey >
// ...
{
// ...
} ;

As long as the only things in the base class template which
depend on the template parameter are static members or friends,
I think it should work. You might have to use the compilation
firewall idiom or the singleton pattern for the RP_Index, but I
don't think it should be necessary. Static data members of a
template should only be instantiated when and where used; in
your case, only when someone actually calls MyObject::GetByKey
or MyObject::FindByKey, at which time, MyObject shoud be a
complete type.

 

[Marcel Müller]

Would something like the following work here:

template< typename ObjType, typename KeyType >
class ContainerSupport
{
private:
static sorted_vector_p<ObjType, KeyType> RP_Index;
public:
// Factory:
// Fetches an existing instance or creates a new one for the
key K.
static my_intrusive_ptr<ObjType> GetByKey(const K& key);
// Fetches an existing instance or return NULL.
static my_intrusive_ptr<ObjType> FindByKey(const K& key)
{ return RP_Index.find(key); }
} ;

then:

class MyObject : public ContainerSupport< MyObject, MyKey >
// ...
{
// ...
} ;

As long as the only things in the base class template which
depend on the template parameter are static members or friends,
I think it should work.

Well, the only disadvantage I see is that the factory of ObjType (or the
constructor) must be public. This is a bit dangerous with respect to
data integrity.

> You might have to use the compilation
firewall idiom or the singleton pattern for the RP_Index, but I
don't think it should be necessary. Static data members of a
template should only be instantiated when and where used;

It should be sufficient when the statics are linked as weak symbols when
the template class is instantiated for some certain parameters from a
C++ file. But you are right. Strictly speaking there is a cyclic
dependency to the derived class. I have to check this since the compiler
is quite old. But I think I already used something like that.

I just tested the following:

class MyObject : public ContainerSupport<MyObject, MyKey>
{ friend class ContainerSupport<MyObject, MyKey>;
....


It works as far as I can see and the constructor of MyObject is private.
I wonder a bit since ContainerSupport<MyObject, MyKey> is not yet a
friend of MyObject when the template is instantiated. But at least the
17 year old IBM compiler and gcc 3.3.5 ate it. Maybe because of the same
reason as the above dependency.

Pretty useful pattern.


Marcel

 

[James Kanze]

Well, the only disadvantage I see is that the factory of
ObjType (or the constructor) must be public. This is a bit
dangerous with respect to data integrity.

I thought the factory was public in your original example. Or
do you mean rather: the constructor must be public (which of
course, allows client code to create instances which aren't in
the index). If this is a problem, you can declare

It should be sufficient when the statics are linked as weak
symbols when the template class is instantiated for some
certain parameters from a C++ file. But you are right.
Strictly speaking there is a cyclic dependency to the derived
class. I have to check this since the compiler is quite old.
But I think I already used something like that.

Barton and Nackmann described a similar idiom, in which the
templated base class only contained friend functions; the
standard explicitly makes this legal. If I understand things
correctly, the same rules apply here: the class template itself
is instantiated when it appears as a base class, the member
functions and static data members, however, only when they are
used. In this case (as with the Barton and Nackmann trick),
there is nothing in the class definition itself which requires a
complete definition of the instantiation type, so the fact that
it is instantiated before the class definition is complete
shouldn't be a problem. Any possible problem would be because
of two phase look-up -- if you do something in a non-dependent
context which requires the complete class type, I'm not sure
what is supposed to happen. But how could an expression which
required the complete class type be non-dependent? The only
thing I'm not sure of is the way dependency affects static data
members. (But I'm not sure that that's really relevant here
either. It's not so much a case of name lookup, but whether the
class is complete at the point of instantiation. And it will
be.)

I just tested the following:

class MyObject : public ContainerSupport<MyObject, MyKey>
{ friend class ContainerSupport<MyObject, MyKey>;
...

It works as far as I can see and the constructor of MyObject
is private. I wonder a bit since ContainerSupport<MyObject,
MyKey> is not yet a friend of MyObject when the template is
instantiated.

But it is! The constructor of MyObject is only used in the
functions, not in the class itself, and the functions are only
instantiated when they are actually used, at the point of use.
Note that the real question here isn't whether the friend
declaration is visible. The rule is that any code which
constructs an object requires a complete class definition. The
key here is that the templated class itself doesn't need the
type to be complete---the completeness is only required in
static data members and member functions, which are only
instantiated if and where needed, and the point of instantiation
"immediately follows the namespace scope declaration or
definition that refers to the specialization". (See §14.7.1 and
§14.6.4.1.)

But at least the 17 year old IBM compiler and gcc 3.3.5 ate
it. Maybe because of the same reason as the above dependency.

I wouldn't count on this working with just any 17 year old
compiler. 17 years ago, class instantiation was all or nothing
for most compilers (if they supported templates at all). IBM is
probably an exception---that's where Barton and Nackmann worked,
and they pushed the compiler team considerably (much like Boost
has in recent times). At the time, IBM was considerably in
advance of anyone else with regards to templates.

Pretty useful pattern.

Yep. I can't take credit for it, however---Barton and Nackmann
proposed a variant of it well over ten years ago.

 

[Marcel Müller]

Hi,

I thought the factory was public in your original example. Or
do you mean rather: the constructor must be public

Yes, the latter. Either I need a public constructor some other public
factory method of MyObject.

(which of
course, allows client code to create instances which aren't in
the index). If this is a problem, you can declare
ContainerSupport< MyObject, MyKey > friend of MyObject, and keep
the destructors private.
Exactly.



But it is! The constructor of MyObject is only used in the
functions, not in the class itself, and the functions are only
instantiated when they are actually used, at the point of use.

[...]

Should be fine.

I wouldn't count on this working with just any 17 year old
compiler. 17 years ago, class instantiation was all or nothing
for most compilers (if they supported templates at all). IBM is
probably an exception---that's where Barton and Nackmann worked,
and they pushed the compiler team considerably (much like Boost
has in recent times). At the time, IBM was considerably in
advance of anyone else with regards to templates.

The IBM VAC++ 3.0 compiler did not cause much harm so far. The only
unsupported pattern I found so far is that it cannot handle temporaries
in conditional expressions. But even in this case a warning told about
that fact.
The ececutables are pretty small and the compilation time is neglectable
in comparsion to g++. I did not find any differences in the behaviour of
the application so far. So I mostly use IBM Visual Age. Only the
warnings of gcc are a bit more sensitive to potentially buggy code
fragments.
I was a bit supprised about the good C++ support too. gcc before 3.x was
quite unuseable with respect to C++, Watcom too. And Borland C++ was
always more like a conglomerate of compiler bugs.

Yep. I can't take credit for it, however---Barton and Nackmann
proposed a variant of it well over ten years ago.

I never heard about that before. Maybe because I didn't need it. But it
was not that simple to get the pattern fully thread-safe. I finally got
it by checking whether the intrusive reference counter is non-zero
before returning an element from the index.


Marcel