Contents
Introduction
This article is the natural evolution of the previous "The safest smart pointer of the East" and "Comparing different coding approach", always here on CodeProject.
The subject is one of the most treated in many OOP and Generic code books, with a variety of solutions. But - in my experience - I often found myself in trouble with certain "too zealot" implementations.
Many of you probably know libraries like Boost or Loki.
Well .. if you feel fine with that implementation of smart pointers ... forget about this article! Even if it can give something new to you, you'll probably already have enough motivations to stay with them, asking why another set of wheel.
But if you think that code to be sometimes an overkill, and you need something tiny, or you also need something simpler to be expanded, or you simply want to understand something about a possible way to do a policy based design, then you can get something from here.
Since I'm not new to this kind of stuffs, and some readers may also know other articles by me on the same subject, I must warn you: this is not an update of the previous series, but restarting with a new engine, more "modern" and less oriented in conserving old habitudes like Hungarian notation or other zealot implementation of patterns.
This time I won't respect any religion, but I consider all of them, case by case, with one objective: minimize the needed code.
Code structure
Since many classes are templates, I preferred an "inclusion model": all the code is inside the headers, that you can include in your projects. Headers dependency is resolved inside the headers themselves, no "cpp" files are provided.
All function and classes are grouped into namespaces, and all namespaces are grouped in the GE_ namespace. The idea is that such symbol should not conflict with any other third party library you can eventually use. If it does, just replace the GE_ string across all my provided files.
No dependency on MFC, ATL, or WTL exists. Instead, I depend on C++ STL and some CRT headers. All those dependency are included in all the files, through the "stdx/dependency.h" file.
That file also includes some helpers headers used extensively across all others. It doesn't include the headers of the "stdx" project itself.
To avoid entanglement between "standard" language classes and Windows related code, everything not related to Windows is coded independently from "windows.h" and grouped inside the "stdx" utility project. Instead everything that is a C++ wrap around Windows functionalities will be wrapped in the "winx" utility project (not in this article).
Testing units are inside the appropriate C++ projects, named C0, C1 � Cx. Don't run them in release version outside a debugger, since they don't have any effect. They make sense in debug mode, run inside a debugger, since they trace in the output window. A step-by-step execution is also a good way to see how they work.
Used patterns
The mostly used pattern is reference counting and the most used design pattern is policy inheritance. Not because I believe these patterns are able to solve everything, but because I found them particularly useful in handling dynamically allocated and limited resources.
The code is compiled with C++ 7.0. It should also work fine with C++ 7.1 or even 8.0 (native), apart from some damn typename keyword eventually forgotten "under the keyboard".
With reference counting I essentially mean, to apply some predefined action to objects at certain "moments" of their lifecycle, like the first time they are referred, on every new reference, every time a reference is lost, and when no more reference exist.
With policy inheritance I mean, an implementation of a given class operation across functions inherited by a base that is supplied across a template parameter. Typically:
template<class base>
class myclass: public base
{
...
};
Since this can be recursive, you can combine policies with declaration like:
typedef aclass<apolicy<anotherpolicy<yetanother<aType> > > > atypeinstance;
When polymorphism of an object is required, policy design is instead implemented across recurring templates:
template<class Derived, class traits>
class myclass
{
protected:
virtual ~myclass() {}
Derived* pThis() const {
return static_cast<Derived*>(const_cast<my_class*>(this)); }
static myclass* P(Derived* p) { return static_cast<myclass*>(p); }
...
};
Essentially, Derived is supposed to be a class having myclass<Derived> as its base, and that can be itself a (common) base for a variety of types overriding its interface.
Other patterns, like Composite-Visitors or like Signals-Events etc. are implemented mainly unorthodoxly, on top of these, mixing policy design with RTTI OOP inheritance (virtual functions, virtual bases etc.).
Implementing reference counting
A classical reference counting implementation is the one that comes with "smart pointers", in their various flavours like boost's or loki's.
But dealing with Win32 is a bit different: reference counting requires not only destruction policies, but also different ways to store data, (to close a HANDLE, you may need other information than the HANDLE itself) different creation and acquisition policies, the capability to handle both pointer and value semantics, the availability of strong and weak references and so on.
As far as my experience concerns, policy inheritance gives the required flexibility to handle modularly all these variants.
The std::smart<.> class
It is the class where to start from, to have smart pointer, smart handles, smart whatever. Marketing apart, it must be as empty as possible implementing only what cannot be inherited (that is: copy and assignment) in terms of inherited function from a parametric base.
template<class smart_policy>
class smart:
public smart_policy,
public operators<smart>
{
public:
smart() {}
~smart() {}
smart(const smart& s) {
assign(static_cast<const smart_policy&>(s)); }
template<class other>
smart(const smart<other>& s) {
assign(static_cast<const other&>(s)); }
template<class A, class B>
smart(const A& a, const B& b) { assign(a,b); }
smart(typename smart_policy::acquire_type a) { assign(a); }
smart& operator=(const smart& s)
{ assign(static_cast<const smart_policy&>(s)); return *this; }
typedef typename smart_policy::alias_type alias_type;
typedef typename smart_policy::acquire_type acquire_type;
typedef typename smart_policy::value_type value_type;
};
Note that smart doesn't contain any data or data operations. It supposes everything is inherited. The only thing it does is to call assign that is supposed to be inherited by smart_policy in all the required variants. Types definitions are also considered as inherited. Conversion is supported from other types of smart, or from an acquire_type.
refcounts::policy<.>
Reference counting is implemented inside the stdx::refcounts namespace, by the stdx::refcounts::policy class, that handles the reference counters (for both strong and weak references) and delegates to its parametric base the storage of data and their assignments.
strong means that a reference controls the object it holds (for example, by deleting it when no "controllers" control it), weak means that a reference "observes" the held object, reporting an invalid state, for example, if no more existent, but doesn't manage the object itself.
It also provides as a public function, that � due to the inheritance in smart is made so available- the operator!() that is true if there are no smart references active on the referred counters (or ... there is no object), or if the inherited policy has its own operator!() returning true.
Similarly, operator== and operator< short-circuit the inherited functions if the referred counter object is the same: when this happens, the pointers are equal by themselves.
Practically, it converts the assign function, in increment/decrement of shared counters, and calling of other "inherited by template parameter" functions, like on_addref, on_lastrelease, etc. like in these assign variants:
template<class other, bool b>
void assign(const policy<other,b>& a)
{
if(a.pCnt == pCnt) return;
clear_();
refcnt_policy::assign(static_cast<const other&>(a));
set_(a.pCnt);
}
void assign(acquire_type a)
{
counters* p = get_counters(a);
if(pCnt == p) return;
clear_();
refcnt_policy::assign(a);
set_(p);
}
pCnt is a pointer to a counters struct. The get_couters function must be inherited through the Type parameter of the policy template class (the policy of the policy), and is what makes us able to assign a dumb pointer to a smart pointer. We'll see later how.
The internal clear_ and set_ functions are the key of the counting mechanism, by calling pCnt->increment and pCnt->decrement respectively.
The increment and decrement are inside the counters as:
template<class P>
void decrement(P& p, bool bStrong)
{
if(bStrong)
{
p.on_release();
if(hold == 1)
{
p.on_lastrelease();
p.on_delete();
}
hold--;
}
ref--;
if(!ref)
delete this;
}
template<class P>
void increment(P& p, bool bStrong)
{
ref++;
if(bStrong)
{
hold++;
if(hold==1)
p.on_firstref();
p.on_addref();
}
}
Now the problem becomes "provide to refcounts::policy the required on_xxx functions, as well of the get_counters function".
Pointer semantics
To provide "pointer semantics" we need a policy that stores a pointer and provides dereferencing and member access operators.
The most generic one is stdx::pointers::policy<Type>.
template<class Type>
class policy
{
friend class policy;
private:
Type* ptr;
protected:
typedef Type* alias_type;
typedef Type value_type;
policy() { ptr=0; }
void on_addref() {}
void on_firstref() { }
void on_release() {}
void on_lastrelease() { }
void on_delete() { if(ptr) delete ptr; ptr=0; }
refcounts::counters* get_counters(Type* p)
{ return (p)? new refcounts::counters: 0; }
void clear() { ptr = 0; }
template<class other>
void assign(const policy<other>& p)
{ ptr = static_cast<Type*>(p.ptr); }
void assign(const policy& p) { ptr = p.ptr; }
void assign(Type* p) { ptr = p; }
bool equal(const policy& p) const { return ptr == p.ptr; }
bool less(const policy& p) const { return ptr < p.ptr; }
public:
bool operator!() const { return !ptr; }
Type* operator()() const { return ptr; }
template<class I>
Type& operator[](const I& i) const {
ASSERT(i==0); return operator*(); }
Type* operator->() const {
if(!ptr) throw_excpptr<excp<Type> >(); return ptr; }
Type& operator*() const {
if(!ptr) throw_excpptr<excp<Type> >(); return *ptr; }
operator Type*() const { return ptr; }
Type* New() { ptr = new Type; return ptr; }
typedef policy pointer_plc;
};
Note the way get_counters is implemented: it doesn't search for any Type to counters association: just creates new ones.
In general this is not a safe operation: passing a dumb to a smart pointer defined in this way should be done only once in the life of an object.
Note also that assignment from a different type is operated via static_cast, and note the simple delete in on_delete.
These are, clearly, minimum functionalities. We can always do something better, but "how" better, depends on different cases.
RTTI objects
RTTI objects are all classes having at least one virtual function (or inheriting some). When RTTI support is enabled on a compiler, dynamic_cast can be applied to conversions between RTTI objects. But there's more: whatever pointer to an RTTI class you have, if dynamic_cast-ed to void*, it will result in the address of the most external runtime object. That is: given a diamond you can have allocated on memory, whatever pointer to a whatever base of this diamond you have, dynamic_cast<void*>(pWhateverBase) will always return the same value; which can be used as the unique identifier for the object.
The first thing we can do is, override pointers::policy with pointers::dynpolicy:
template<class Type>
class dynpolicy:
public policy<Type>
{
protected:
template<class other>
void assign(const policy<other>& p)
{ assign(dynamic_cast<Type*>(p())); }
void assign(const dynpolicy& p) { assign(p()); }
void assign(Type* p) { policy<Type>::assign(p); }
};
It just uses dynamic_cast instead of static_cast. But, taking advantage from the previously described property, we can even override dynpolicy with mappedpolicy:
template<class Type>
class mappedpolicy:
public dynpolicy<Type>
{
private:
typedef typename std::map<void*, refcounts::counters*> map_t;
typedef typename dynpolicy<Type> base_t;
typedef typename
smart<refcounts::policy<pointers::policy<map_t>, true> > map_p;
static map_p map() { static map_p p(new map_t); return p; }
map_p pMap;
protected:
mappedpolicy() { pMap = map(); }
refcounts::counters* get_counters(Type* p)
{
refcounts::counters*& pcnt = (*pMap)[dynamic_cast<void*>(p)];
if(!pcnt) pcnt = new refcounts::counters;
return pcnt;
}
void on_delete()
{
pMap->erase(dynamic_cast<void*>(operator()()));
base_t::on_delete();
}
};
Here a statically available std::map is used to associate a void* identifying a RTTI object with its counters. get_counters creates new counters only if no counters are already mapped for a given object. This makes a smart pointer always safe whatever dumb pointer it receives. But if many objects are in the system, the map may become huge.
Intrusive pointers
An alternative to avoid this, is through an intrusive mechanism:
template<class Type>
class intrpolicy:
public dynpolicy<Type>
{
protected:
void on_addref()
{ if((*this)())
dynamic_cast<refcountable*>((*this)())->on_addref(); }
void on_firstref()
{ if((*this)())
dynamic_cast<refcountable*>((*this)())->on_firstref(); }
void on_release()
{ if((*this)())
dynamic_cast<refcountable*>((*this)())->on_release(); }
void on_lastrelease()
{ if((*this)())
dynamic_cast<refcountable*>((*this)())->on_lastrelease(); }
void on_delete()
{ if((*this)())
dynamic_cast<refcountable*>((*this)())->on_delete(); ptr = 0; }
refcounts::counters* get_counters(Type* p)
{ return (!p)? 0: dynamic_cast<i_refcountable*>(p)->get_counters(); }
};
Essentially, all the callbacks are delegated to the referred object, where homonymous functions are expected. Class stdx::refcountable defines those functions as virtual, allocating its own counters and keeping a reference to themselves, and doing delete this inside on_delete.
class refcountable
{
friend struct refcounts::counters;
public:
refcountable()
{
pCnt = new refcounts::counters;
pCnt->increment(*this, false);
}
virtual ~refcountable()
{
if(pCnt)
pCnt->decrement(*this, false);
pCnt=0;
}
private:
refcounts::counters* pCnt;
protected:
virtual void on_addref() {}
virtual void on_firstref() {}
virtual void on_release() {}
virtual void on_lastrelease() { }
virtual void on_delete() { delete this; }
virtual refcounts::counters* get_counters() { return pCnt; }
};
Shortcuts
By now, we can combine smart, refcounts and pointers policies to give a variety of smart pointers, or even create a new policy from scratch or by deriving existing ones.
For example, stdx::smart<stdx::refcounts::policy<stdx::pointers::policy<double>,true> > is a strong static-casting pointer to a double.
Since all these declarations may be a pain, if frequently needed, for combinations of frequent use, I have provided some shortcuts inside the stdx namespace:
template<class Type>
struct ptr
{
typedef smart<refcounts::policy<pointers::intrpolicy<Type>, true> > strong;
typedef smart<refcounts::policy<pointers::intrpolicy<Type>, false> > weak;
};
template<class Type>
struct statptr
{
typedef smart<refcounts::policy<pointers::policy<Type>, true> > strong;
typedef smart<refcounts::policy<pointers::policy<Type>, false> > weak;
};
template<class Type>
struct refcntvect
{
typedef smart<refcounts::policy<pointers::vectpolicy<Type>, true> > strong;
typedef smart<refcounts::policy<pointers::vectpolicy<Type>, false> > weak;
};
template<class Type>
struct dynptr
{
typedef smart<refcounts::policy<pointers::dynpolicy<Type>, true> > strong;
typedef smart<refcounts::policy<pointers::dynpolicy<Type>, false> > weak;
};
template<class Type>
struct mappedptr
{
typedef smart<refcounts::policy<pointers::mappedpolicy<Type>, true> > strong;
typedef smart<refcounts::policy<pointers::mappedpolicy<Type>, false> > weak;
};
With these definitions, the above declaration can be written as stdx::statptr<double>::strong.
Value semantics
Another interesting policy family can be obtained by considering a reference counting wrapper not to store a pointer (giving a smart pointer) but for storing a "value". This is typical where you want to ally some delete or create policy, for example, to a Windows HANDLE.
But the problem isn't necessarily bound to Windows: you can do the same, for example, with an array index etc..
The namespace values, contains a policy and a mapped policy. Just like for pointers.
template<
class Type,
Type nullval,
class CleanupFn
>
class policy
{
friend class policy;
private:
Type val;
CleanupFn fnCleanup;
protected:
typedef const Type& alias_type;
typedef const Type& acquire_type;
typedef Type value_type;
policy() { val=nullval; }
...
void on_delete() { fnCleanup(val); val=nullval; }
refcounts::counters* get_counters(Type* p) {
return new refcounts::counters; }
...
public:
bool operator!() const { return val == nullval; }
const Type& operator()() const { return val; }
operator const Type&() const { return val; }
};
template<class Type, Type nullval, class CleanupFn>
class mappedpolicy:
public policy<Type, nullval, CleanupFn>
{
...
refcounts::counters* get_counters(const Type& p)
{
refcounts::counters*& pcnt = (*pMap)[p];
if(!pcnt) pcnt = new refcounts::counters;
return pcnt;
}
void on_delete()
{
pMap->erase(operator()());
base_t::on_delete();
}
};
And, still just like with pointers, we also have stdx shortcuts:
template<class Type, Type nullval, class CleanupFn>
struct hnd
{
typedef smart<refcounts::policy<
values::policy<Type,nullval,CleanupFn>, true> > strong;
typedef smart<refcounts::policy<
values::policy<Type,nullval,CleanupFn>, false> > weak;
};
template<class Type, Type nullval, class CleanupFn>
struct mappedhnd
{
typedef smart<refcounts::policy<
values::mappedpolicy<Type,nullval,CleanupFn>, true> > strong;
typedef smart<refcounts::policy<
values::mappedpolicy<Type,nullval,CleanupFn>, false> > weak;
};
Testing with smart pointers or smart values can be found in c0.cpp.
Policing and boxing
There are essentially two ways to customize reference counting:
- By defining new policies (may be overriding existing ones) to be inherited by
smart: this can be useful wherever you need some special destruction behaviours.
- By defining a
refcoutnable class storing description data and implementing callbacks to do "maintenance" for that data, defining a smart pointer to that data, and implement a class to wrap around it.
The first point can be more traditional, but - in some complex cases- it may be required to store wide data structures. The second point allows to share such data structures among different pointers.
A boxing example: strings
Shared strings are semantically value objects that � instead of copying- shares read-only data. When data needs to be modified a new copy is created and modified.
template<class Type, class traits=strings::traits>
class string
{
private:
typedef std::vector<Type> data_t;
typedef stdx::statptr<data_t>::strong data_p;
data_p pData;
static data_p nullstr()
{
static data_p p;
if(!p)
p.New()->resize(1);
return p;
}
friend class string;
public:
string() { pData = nullstr(); }
Type* get_buffer(size_t len=-1)
{
if(len == -1) len = pData->size();
if(pData.get_holdcount() >1)
pData.New(*pData);
pData->resize(len+1);
return &(*pData)[0];
}
operator const Type*() const { return &(*pData)[0]; }
bool operator!() const { return !(*pData)[0]; }
void clear() { pData = nullstr(); }
size_t len() const { return pData->size()-1; }
string(const string& s) { pData = s.pData; }
string(const Type* p, size_t n=-1)
{
pData = nullstr();
if(n==-1)
n = traits::len(p);
Type* buff = get_buffer(n);
traits::copy(buff, p, n);
}
string(const Type& c, size_t n=1)
{
pData = new data_t(n+1, c);
(*pData)[n] = (*nullstr())[0];
}
string& operator=(const string& s) { pData = s.pData; return *this; }
string& operator+=(const string& s)
{
size_t n = len();
size_t m = s.len();
Type* buff = get_buffer(m+n);
traits::copy(buff+n, s, m);
return *this;
}
string operator+(const string& s)
{ return string(*this)+=s; }
...
}
The key of the management is the get_buffer function: if the hold counter is greater than 1 (that is: the data is shared) the data is cloned.
Note also that no functions allow to modify the data or to access them in non-const mode, except getbuffer. This gives std::string the behaviour of a value class, even if it is internally a reference counting pointer.
The traits parameter must be a struct providing the static len and copy functions and the struct base, that can be used to inherit other functionalities. The default strings::traits implements them for a generic Type using linear loops, and provides base as an empty struct.
Note that, as far as it is provided, stdx::string is not an OOP string class, but only a data sharer. It implements as member functions only what is required to manage the data, but you must still rely on external standard library functions to handle string operations.
Policing example for a recurring template: compounds
Compound objects are � in their essence- objects that can collect each other, where an object may contain other objects.
This is different with a pure "generic programming" pattern, like STL, where collections contain generic homogeneous types, with each of the objects unaware of the fact that it is collected. Collecting pointers can allow polymorphism, but the objects are still unaware of the collection. With the advantage that they (or better, their pointers) can be a member of many collections, but the impossibility for an object to know about its next or previous.
Compound objects � in this implementation- are nodes having their own references for previous, next, parent, .... But they also need to have their own specific interface.
This is achieved by having node references expressed in terms of pointers to classes implementing node functionality by inheriting a node class: a class derives from node and the node contains pointers to that class. This is a game for recurring templates (see compounds.h).
template<class Derived, class traits = ... >
class chain_node:
public traits::base
{
public:
...
};
You can define your chainable node as:
class yourchainable:
public stdx::chain_node<yourchainable>
{ ... };
Previous and next references are implemented in terms of pointer to Derived: but the "pointer" can be ... whatever object having a dereferencing operator. Which object, it is defined inside the traits class, that must provide the definitions that comes as in comp_dumb_traits (that used normal "dumb" pointers) or comp_smart_traits (that uses smart intrusive pointers).
Note that comp_xxx is not by itself a template, but contains all template members. Although this complicates a bit the coding of the policy itself, it results in a simpler usage of the policy, since there is no need to specify the type it must apply to.
The chain_node class
As illustrated above, chain_node holds the next and previous pointers. When comp_smart_traits is used, the forward pointer is strong, while the backward one's weak: this makes an element in the chain to keep-alive the subsequent and being kept-alive by the precedent.
The set_next and set_prev functions have obvious meaning, but a less obvious consequence: A->set_next(B) and B->set_prev(A) are not the same: in the first case B leaves its original chain and joins A's interposing between A and its original next; in the second case, it is A joining B chain, interposing between B's previous and B. In both the cases, the one who leaves the original chain is the parameter passed node.
The hierarchy_node class
Similarly, a hierarchy node is implemented by a siblings chain, with a parent weak pointer and the first and last children strong pointer. Of course, regular pointers are used if comp_dumb_traits is used.
Like a chain node, a hierarchy node has not only set_prev and set_next but also set_first, set_last and set_at. To navigate the hierarchy, get_xxx functions are available for both shallow (walking on siblings) and deep (walking children also) iterations.
Iterating onto compounds
Class stdx::ierator<class Compound, class iter_trs = iter_traits_chain, class traits = Compound::traits_t> has pointer semantics, and all the increment/decrement operators. The implementation of those operators is defined in terms of iter_trs supplied functions, that are provided as iter_traits_chain and iter_traits_deep. The internal iterator pointer type, is obtained from traits as traits::types<NODE>::wptr.
Samples of usage, can be found in C2.cpp.
To be as STL compliant as possible, stdx::iterator defines the STL iterator typedefs, and the xx_node classes have begin/end functions. But, since compounds are self-collections, end will always return a "null iterator". No doubt this is a difference with STL: decrementing an iterator that reached the end of a collection is legal in STL, but illegal here.
Independently on that, std::for_each works, and � in your own defined loops- you can both check an stdx::iterator with an "end" iterator, or simply check if it is null with operator!.
Graphs
With the same policing mechanism, graphs can be created with graph_node and graph_arc derived classes. When smart pointers are used, nodes sustain arcs (the arc lists use strong pointers) while arc only observes (by weak pointers) nodes. Thus, while nodes must exist by themselves (may be collected somewhere else), arcs are deleted when no nodes refer them, if not elsewhere referenced.
In this implementation, both graph_node and graph_arc are recurring templates taking as parameters the class derived from themselves and the class deriving their counterparts.
Note that these two classes only contain the functions to compose a graph (linking nodes with arcs). Algorithms cannot be here, since they depend on what the nodes and arcs represent. And that mostly depend on the arcs and nodes data, inside the derived classes. In this sense they are like stdx::string: generic programming classes, not OOP objects.
A sample of usage is in C3.cpp
Iterating through graphs
Since graph::nodes outgoing and incoming arcs pointers are stored in std::lists, it should be possible to iterate those lists by exposing their begin/end function and their iterator type.
But this is impractical, since such iterator iterates over pointers, thus, accessing the arcs will require a double de-reference (that is: operator-> doesn't work, and arc members should be accessed as (**iter).member). To avoid this annoying syntax, the helper stdx::derefiterator inherits whatever STL compliant iterator, replacing the * and -> operators to mask the double indirection. This is used as graph::node::arc_iterator, that is also returned by begin_arcfrom, begin_arcto, end_arcfrom, end_arcto.
Routing messages through graphs
Similar to std::for_each, iterating over the arcs of a node or over their liked nodes can be done with graph::route_arcs and graph::route_nodes. They both keep a generic Data& and a starting Node& and apply a Fn(Arc*, Data&) and Fn(Node*, Data&) respectively. The Fn can be whatever functional object, including the one returned by std::mem_func, allowing to pass the Data& to a member function.
This mechanism can be also used as a sort of static-types event-routing network (since nodes can re-route the messages).
Conclusions
If you'd the patience to read up 'till now, compliments!. The article was probably a bit long.
This is not certainly an industrial code, but it can be useful in all those situations where you don't have to depend on large libraries to do small things. As I told in the beginning, if you already depend on those libraries use them. If you don't, or if you just want to try a different approach, consider this as a "starting point".
