Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/more/count_bdy.htm @ 14

Last change on this file since 14 was 12, checked in by landauf, 18 years ago

added boost
File size: 24.8 KB
Line 
1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
2
3<HTML>
4
5<HEAD>
6
7   <TITLE>Counted Body Techniques</TITLE>
8
9   <META NAME="GENERATOR" CONTENT="Microsoft FrontPage 4.0">
10
11   <META NAME="Author" CONTENT="Kevlin Henney">
12
13   <META NAME="KeyWords" CONTENT="C++, Reference Counting, Advanced Techniques, Smart Pointers, Patterns">
14
15</HEAD>
16
17<BODY bgcolor="#FFFFFF" text="#000000">
18
19
20
21<H1 ALIGN=CENTER><I><FONT SIZE=+4>Counted Body Techniques</FONT></I></H1>
22
23
24
25<CENTER><P><B><FONT SIZE=+1><a href="../people/kevlin_henney.htm">Kevlin Henney</a><BR>
26
27</FONT>(<A HREF="mailto:kevlin@acm.org">kevlin@acm.org</A>, <a HREF="mailto:khenney@qatraining.com">khenney@qatraining.com</a>)</B></P></CENTER>
28
29
30
31<UL>
32
33<P>Reference counting techniques? Nothing new, you might think. Every good
34
35C++ text that takes you to an intermediate or advanced level will introduce
36
37the concept. It has been explored with such thoroughness in the past that
38
39you might be forgiven for thinking that everything that can be said has
40
41been said. Well, let's start from first principles and see if we can unearth
42
43something new....</P>
44
45</UL>
46
47
48
49
50<HR WIDTH="100%">
51<H2>And then there were none...</H2>
52
53
54<UL>
55
56<P>The principle behind reference counting is to keep a running usage count
57
58of an object so that when it falls to zero we know the object is unused.
59
60This is normally used to simplify the memory management for dynamically
61
62allocated objects: keep a count of the number of references held to that
63
64object and, on zero, delete the object.</P>
65
66
67
68<P>How to keep a track of the number of users of an object? Well, normal
69
70pointers are quite dumb, and so an extra level of indirection is required
71
72to manage the count. This is essentially the P<FONT SIZE=-1>ROXY</FONT>
73
74pattern described in <I>Design Patterns</I> [Gamma, Helm, Johnson &amp;
75
76Vlissides, Addison-Wesley, <FONT SIZE=-1>ISBN </FONT>0-201-63361-2]. The
77
78intent is given as</P>
79
80
81
82<UL>
83
84<P><I>Provide a surrogate or placeholder for another object to control
85
86access to it.</I></P>
87
88</UL>
89
90
91
92<P>Coplien [<I>Advanced C++ Programming Styles and Idioms</I>, Addison-Wesley,
93
94<FONT SIZE=-1>ISBN </FONT>0-201-56365-7] defines a set of idioms related
95
96to this essential separation of a handle and a body part. The <I>Taligent
97
98Guide to Designing Programs </I>[Addison-Wesley, <FONT SIZE=-1>ISBN </FONT>0-201-40888-0]
99
100identifies a number of specific categories for proxies (aka surrogates).
101
102Broadly speaking they fall into two general categories:</P>
103
104
105
106<UL>
107
108<LI><I>Hidden</I>: The handle is the object of interest, hiding the body
109
110itself. The functionality of the handle is obtained by delegation to the
111
112body, and the user of the handle is unaware of the body. Reference counted
113
114strings offer a transparent optimisation. The body is shared between copies
115
116of a string until such a time as a change is needed, at which point a copy
117
118is made. Such a C<FONT SIZE=-1>OPY</FONT> <FONT SIZE=-1>ON</FONT> W<FONT SIZE=-1>RITE</FONT>
119
120pattern (a specialisation of L<FONT SIZE=-1>AZY</FONT> E<FONT SIZE=-1>VALUATION</FONT>)
121
122requires the use of a hidden reference counted body.</LI>
123
124
125
126<LI><I>Explicit</I>: Here the body is of interest and the handle merely
127
128provides intelligence for its access and housekeeping. In C++ this is often
129
130implemented as the S<FONT SIZE=-1>MART</FONT> P<FONT SIZE=-1>OINTER</FONT>
131
132idiom. One such application is that of reference counted smart pointers
133
134that collaborate to keep a count of an object, deleting it when the count
135
136falls to zero.</LI>
137
138</UL>
139
140</UL>
141
142
143
144
145<HR WIDTH="100%">
146<H2>Attached vs detached</H2>
147
148
149<UL>
150
151<P>For reference counted smart pointers there are two places the count
152
153can exist, resulting in two different patterns, both outlined in <I>Software
154
155Patterns</I> [Coplien, SIGS, <FONT SIZE=-1>ISBN </FONT>0-884842-50-X]:</P>
156
157
158
159<UL>
160
161<LI>C<FONT SIZE=-1>OUNTED</FONT> B<FONT SIZE=-1>ODY</FONT> or A<FONT SIZE=-1>TTACHED</FONT>
162
163C<FONT SIZE=-1>OUNTED</FONT> H<FONT SIZE=-1>ANDLE</FONT>/B<FONT SIZE=-1>ODY</FONT>
164
165places the count within the object being counted. The benefits are that
166
167countability is a part of the object being counted, and that reference
168
169counting does not require an additional object. The drawbacks are clearly
170
171that this is intrusive, and that the space for the reference count is wasted
172
173when the object is not heap based. Therefore the reference counting ties
174
175you to a particular implementation and style of use.</LI>
176
177
178
179<LI>D<FONT SIZE=-1>ETACHED</FONT> C<FONT SIZE=-1>OUNTED</FONT> H<FONT SIZE=-1>ANDLE</FONT>/B<FONT SIZE=-1>ODY</FONT>
180
181places the count outside the object being counted, such that they are handled
182
183together. The clear benefit of this is that this technique is completely
184
185unintrusive, with all of the intelligence and support apparatus in the
186
187smart pointer, and therefore can be used on classes created independently
188
189of the reference counted pointer. The main disadvantage is that frequent
190
191use of this can lead to a proliferation of small objects, i.e. the counter,
192
193being created on the heap.</LI>
194
195</UL>
196
197
198
199<P>Even with this simple analysis, it seems that the D<FONT SIZE=-1>ETACHED</FONT>
200
201C<FONT SIZE=-1>OUNTED</FONT> H<FONT SIZE=-1>ANDLE</FONT>/B<FONT SIZE=-1>ODY</FONT>
202
203approach is ahead. Indeed, with the increasing use of templates this is
204
205often the favourite, and is the principle behind the common - but not standard
206
207- <TT><FONT SIZE=+1>counted_ptr</FONT></TT>.
208<I>[The Boost name is <a href="../libs/smart_ptr/shared_ptr.htm"><TT><FONT SIZE=+1>shared_ptr</FONT></TT></a>
209
210rather than <TT><FONT SIZE=+1>counted_ptr</FONT></TT>.]</I></P>
211
212
213
214<P>A common implementation of C<FONT SIZE=-1>OUNTED</FONT> B<FONT SIZE=-1>ODY</FONT>
215
216is to provide the counting mechanism in a base class that the counted type
217
218is derived from. Either that, or the reference counting mechanism is provided
219
220anew for each class that needs it. Both of these approaches are unsatisfactory
221
222because they are quite closed, coupling a class into a particular framework.
223
224Added to this the non-cohesiveness of having the count lying dormant in
225
226a non-counted object, and you get the feeling that excepting its use in
227
228widespread object models such as COM and CORBA the C<FONT SIZE=-1>OUNTED</FONT>
229
230B<FONT SIZE=-1>ODY</FONT> approach is perhaps only of use in specialised
231
232situations.</P>
233
234</UL>
235
236
237
238<HR WIDTH="100%">
239<H2>A requirements based approach</H2>
240
241
242<UL>
243
244<P>It is the question of openness that convinced me to revisit the problems
245
246with the C<FONT SIZE=-1>OUNTED</FONT> B<FONT SIZE=-1>ODY</FONT> idiom.
247
248Yes, there is a certain degree of intrusion expected when using this idiom,
249
250but is there anyway to minimise this and decouple the choice of counting
251
252mechanism from the smart pointer type used?</P>
253
254
255
256<P>In recent years the most instructive body of code and specification
257
258for constructing open general purpose components has been the Stepanov
259
260and Lee's STL (Standard Template Library), now part of the C++ standard
261
262library. The STL approach makes extensive use of compile time polymorphism
263
264based on well defined operational requirements for types. For instance,
265
266each container, contained and iterator type is defined by the operations
267
268that should be performable on an object of that type, often with annotations
269
270describing additional constraints. Compile time polymorphism, as its name
271
272suggests, resolves functions at compile time based on function name and
273
274argument usage, i.e. overloading. This is less intrusive, although less
275
276easily diagnosed if incorrect, than runtime poymorphism that is based on
277
278types, names and function signatures.</P>
279
280
281
282<P>This requirements based approach can be applied to reference counting.
283
284The operations we need for a type to be <I>Countable</I> are loosely:</P>
285
286
287
288<UL>
289
290<LI>An <TT><FONT SIZE=+1>acquire</FONT></TT> operation that registers interest
291
292in a <I>Countable </I>object.</LI>
293
294
295
296<LI>A <TT><FONT SIZE=+1>release</FONT></TT> operation unregisters interest
297
298in a <I>Countable </I>object.</LI>
299
300
301
302<LI>An <TT><FONT SIZE=+1>acquired</FONT></TT> query that returns whether
303
304or not a <I>Countable </I>object is currently acquired.</LI>
305
306
307
308<LI>A <TT><FONT SIZE=+1>dispose</FONT></TT> operation that is responsible
309
310for disposing of an object that is no longer acquired.</LI>
311
312</UL>
313
314
315
316<P>Note that the count is deduced as a part of the abstract state of this
317
318type, and is not mentioned or defined in any other way. The openness of
319
320this approach derives in part from the use of global functions, meaning
321
322that no particular member functions are implied; a perfect way to wrap
323
324up an existing counted body class without modifying the class itself. The
325
326other aspect to the openness comes from a more precise specification of
327
328the operations.</P>
329
330
331
332<P>For a type to be <I>Countable</I> it must satisfy the following requirements,
333
334where <TT><FONT SIZE=+1>ptr</FONT></TT> is a non-null pointer to a single
335
336object (i.e. not an array) of the type, and <I><TT><FONT SIZE=+1>#function</FONT></TT></I>
337
338indicates number of calls to <TT><FONT SIZE=+1><I>function(</I>ptr<I>)</I></FONT></TT>:</P>
339
340
341
342<CENTER><TABLE BORDER=1 CELLSPACING=2 CELLPADDING=2 >
343
344<TR>
345
346<TD><I>Expression</I></TD>
347
348
349
350<TD><I>Return type</I></TD>
351
352
353
354<TD><I>Semantics and notes</I></TD>
355
356</TR>
357
358
359
360<TR>
361
362<TD><TT><FONT SIZE=+1>acquire(ptr)</FONT></TT></TD>
363
364
365
366<TD>no requirement</TD>
367
368
369
370<TD><I>post</I>: <TT><FONT SIZE=+1>acquired(ptr)</FONT></TT></TD>
371
372</TR>
373
374
375
376<TR>
377
378<TD><TT><FONT SIZE=+1>release(ptr)</FONT></TT></TD>
379
380
381
382<TD>no requirement</TD>
383
384
385
386<TD><I>pre</I>: <TT><FONT SIZE=+1>acquired(ptr)<BR>
387
388</FONT></TT><I>post</I>: <TT><FONT SIZE=+1>acquired(ptr) == #acquire -
389
390#release</FONT></TT></TD>
391
392</TR>
393
394
395
396<TR>
397
398<TD><TT><FONT SIZE=+1>acquired(ptr)</FONT></TT></TD>
399
400
401
402<TD>convertible to <TT><FONT SIZE=+1>bool</FONT></TT></TD>
403
404
405
406<TD><I>return</I>: <TT><FONT SIZE=+1>#acquire &gt; #release</FONT></TT></TD>
407
408</TR>
409
410
411
412<TR>
413
414<TD><TT><FONT SIZE=+1>dispose(ptr, ptr)</FONT></TT></TD>
415
416
417
418<TD>no requirement</TD>
419
420
421
422<TD><I>pre</I>: <TT><FONT SIZE=+1>!acquired(ptr)<BR>
423
424</FONT></TT><I>post</I>: <TT><FONT SIZE=+1>*ptr</FONT></TT> no longer usable</TD>
425
426</TR>
427
428</TABLE></CENTER>
429
430
431
432<P>Note that the two arguments to <TT><FONT SIZE=+1>dispose</FONT></TT>
433
434are to support selection of the appropriate type safe version of the function
435
436to be called. In the general case the intent is that the first argument
437
438determines the type to be deleted, and would typically be templated, while
439
440the second selects which template to use, e.g. by conforming to a specific
441
442base class.</P>
443
444
445
446<P>In addition the following requirements must also be satisfied, where
447
448<TT><FONT SIZE=+1>null</FONT></TT> is a null pointer to the <I>Countable</I>
449
450type:</P>
451
452
453
454<CENTER><TABLE BORDER=1 >
455
456<TR>
457
458<TD><I>Expression</I></TD>
459
460
461
462<TD><I>Return type</I></TD>
463
464
465
466<TD><I>Semantics and notes</I></TD>
467
468</TR>
469
470
471
472<TR>
473
474<TD><TT><FONT SIZE=+1>acquire(null)</FONT></TT></TD>
475
476
477
478<TD>no requirement</TD>
479
480
481
482<TD><I>action</I>: none</TD>
483
484</TR>
485
486
487
488<TR>
489
490<TD><TT><FONT SIZE=+1>release(null)</FONT></TT></TD>
491
492
493
494<TD>no requirement</TD>
495
496
497
498<TD><I>action</I>: none</TD>
499
500</TR>
501
502
503
504<TR>
505
506<TD><TT><FONT SIZE=+1>acquired(null)</FONT></TT></TD>
507
508
509
510<TD>convertible to <TT><FONT SIZE=+1>bool</FONT></TT></TD>
511
512
513
514<TD><I>return</I>: <TT><FONT SIZE=+1>false</FONT></TT></TD>
515
516</TR>
517
518
519
520<TR>
521
522<TD><TT><FONT SIZE=+1>dispose(null, null)</FONT></TT></TD>
523
524
525
526<TD>no requirement</TD>
527
528
529
530<TD><I>action</I>: none</TD>
531
532</TR>
533
534</TABLE></CENTER>
535
536
537
538<P>Note that there are no requirements on these functions in terms of exceptions
539
540thrown or not thrown, except that if exceptions are thrown the functions
541
542themselves should be exception safe.</P>
543
544</UL>
545
546
547
548<HR WIDTH="100%">
549<H2>Getting smart</H2>
550
551
552<UL>
553
554<P>Given the <I>Countable</I> requirements for a type, it is possible to
555
556define a generic smart pointer type that uses them for reference counting:</P>
557
558
559
560<UL>
561<PRE><TT>template&lt;typename countable_type&gt;
562class countable_ptr
563{
564public: // construction and destruction
565
566    explicit countable_ptr(countable_type *);
567    countable_ptr(const countable_ptr &amp;);
568    ~countable_ptr();
569
570public: // access
571
572    countable_type *operator-&gt;() const;
573    countable_type &amp;operator*() const;
574    countable_type *get() const;
575
576public: // modification
577
578    countable_ptr &amp;clear();
579    countable_ptr &amp;assign(countable_type *);
580    countable_ptr &amp;assign(const countable_ptr &amp;);
581    countable_ptr &amp;operator=(const countable_ptr &amp;);
582
583private: // representation
584
585    countable_type *body;
586
587};
588</TT></PRE>
589
590</UL>
591
592
593
594<P>The interface to this class has been kept intentionally simple, e.g.
595
596member templates and <TT><FONT SIZE=+1>throw</FONT></TT> specs have been
597
598omitted, for exposition. The majority of the functions are quite simple
599
600in implementation, relying very much on the <TT><FONT SIZE=+1>assign</FONT></TT>
601
602member as a keystone function:</P>
603
604
605
606<UL>
607
608<PRE><TT>template&lt;typename countable_type&gt;
609countable_ptr&lt;countable_type&gt;::countable_ptr(countable_type *initial)
610  : body(initial)
611{
612    acquire(body);
613}
614
615template&lt;typename countable_type&gt;
616countable_ptr&lt;countable_type&gt;::countable_ptr(const countable_ptr &amp;other)
617  : body(other.body)
618{
619    acquire(body);
620}
621
622template&lt;typename countable_type&gt;
623countable_ptr&lt;countable_type&gt;::~countable_ptr()
624{
625    clear();
626}
627
628template&lt;typename countable_type&gt;
629countable_type *countable_ptr&lt;countable_type&gt;::operator-&gt;() const
630{
631    return body;
632}
633
634template&lt;typename countable_type&gt;
635countable_type &amp;countable_ptr&lt;countable_type&gt;::operator*() const
636{
637    return *body;
638}
639
640template&lt;typename countable_type&gt;
641countable_type *countable_ptr&lt;countable_type&gt;::get() const
642{
643    return body;
644}
645
646template&lt;typename countable_type&gt;
647countable_ptr&lt;countable_type&gt; &amp;countable_ptr&lt;countable_type&gt;::clear()
648{
649    return assign(0);
650}
651
652template&lt;typename countable_type&gt;
653countable_ptr&lt;countable_type&gt; &amp;countable_ptr&lt;countable_type&gt;::assign(countable_type *rhs)
654{
655    // set to rhs (uses Copy Before Release idiom which is self assignment safe)
656    acquire(rhs);
657    countable_type *old_body = body;
658    body = rhs;
659
660    // tidy up
661    release(old_body);
662    if(!acquired(old_body))
663    {
664        dispose(old_body, old_body);
665    }
666
667    return *this;
668}
669
670template&lt;typename countable_type&gt;
671countable_ptr&lt;countable_type&gt; &amp;countable_ptr&lt;countable_type&gt;::assign(const countable_ptr &amp;rhs)
672{
673    return assign(rhs.body);
674}
675
676template&lt;typename countable_type&gt;
677countable_ptr&lt;countable_type&gt; &amp;countable_ptr&lt;countable_type&gt;::operator=(const countable_ptr &amp;rhs)
678{
679    return assign(rhs);
680}
681</TT></PRE>
682
683</UL>
684
685</UL>
686
687
688
689<HR WIDTH="100%">
690<H2>Public accountability</H2>
691
692
693<UL>
694
695<P>Conformance to the requirements means that a type can be used with <TT><FONT SIZE=+1>countable_ptr</FONT></TT>.
696
697Here is an implementation mix-in class (<I>mix-imp</I>) that confers countability
698
699on its derived classes through member functions. This class can be used
700
701as a class adaptor:</P>
702
703
704
705<UL>
706
707<PRE><TT>class countability
708{
709public: // manipulation
710
711    void acquire() const;
712    void release() const;
713    size_t acquired() const;
714
715protected: // construction and destruction
716
717    countability();
718    ~countability();
719
720private: // representation
721
722    mutable size_t count;
723
724private: // prevention
725
726    countability(const countability &amp;);
727    countability &amp;operator=(const countability &amp;);
728
729};
730</TT></PRE>
731
732</UL>
733
734
735
736<P>Notice that the manipulation functions are <TT><FONT SIZE=+1>const</FONT></TT>
737
738and that the <TT><FONT SIZE=+1>count</FONT></TT> member itself is <TT><FONT SIZE=+1>mutable</FONT></TT>.
739
740This is because countability is not a part of an object's abstract state:
741
742memory management does not depend on the <TT><FONT SIZE=+1>const</FONT></TT>-ness
743
744or otherwise of an object. I won't include the definitions of the member
745
746functions here as you can probably guess them: increment, decrement and
747
748return the current count, respectively for the manipulation functions.
749
750In a multithreaded environment you should ensure that such read and write
751
752operations are atomic.</P>
753
754
755
756<P>So how do we make this class <I>Countable</I>? A simple set of forwarding
757
758functions does the job:</P>
759
760
761
762<UL>
763
764<PRE><TT>void acquire(const countability *ptr)
765{
766    if(ptr)
767    {
768        ptr-&gt;acquire();
769    }
770}
771
772void release(const countability *ptr)
773{
774    if(ptr)
775    {
776        ptr-&gt;release();
777    }
778}
779
780size_t acquired(const countability *ptr)
781{
782    return ptr ? ptr-&gt;acquired() : 0;
783}
784
785template&lt;class countability_derived&gt;
786void dispose(const countability_derived *ptr, const countability *)
787{
788    delete ptr;
789}
790</TT></PRE>
791
792</UL>
793
794
795
796<P>Any type that now derives from <TT><FONT SIZE=+1>countability</FONT></TT>
797
798may now be used with <TT><FONT SIZE=+1>countable_ptr</FONT></TT>:</P>
799
800
801
802<UL>
803
804<PRE><TT>class example : public countability
805{
806    ...
807};
808
809void simple()
810{
811    countable_ptr&lt;example&gt; ptr(new example);
812    countable_ptr&lt;example&gt; qtr(ptr);
813    ptr.clear(); // set ptr to point to null
814}   // allocated object deleted when qtr destructs
815</TT></PRE>
816</UL>
817</UL>
818
819
820
821
822<HR WIDTH="100%">
823<H2>Runtime mixin</H2>
824
825
826<UL>
827
828<P>The challenge is to apply C<FONT SIZE=-1>OUNTED</FONT> B<FONT SIZE=-1>ODY</FONT>
829
830in a non-intrusive fashion, such that there is no overhead when an object
831
832is not counted. What we would like to do is confer this capability on a
833
834per object rather than on a per class basis. Effectively we are after <I>Countability
835
836</I>on any object, i.e. anything pointed to by a <TT><FONT SIZE=+1>void
837
838*</FONT></TT>! It goes without saying that <TT><FONT SIZE=+1>void</FONT></TT>
839
840is perhaps the least committed of any type.</P>
841
842
843
844<P>The forces to resolve on this are quite interesting, to say the least.
845
846Interesting, but not insurmountable. Given that the class of a runtime
847
848object cannot change dynamically in any well defined manner, and the layout
849
850of the object must be fixed, we have to find a new place and time to add
851
852the counting state. The fact that this must be added only on heap creation
853
854suggests the following solution:</P>
855
856
857
858<UL>
859
860<PRE><TT>struct countable_new;
861extern const countable_new countable;
862
863void *operator new(size_t, const countable_new &amp;);
864void operator delete(void *, const countable_new &amp;);</TT></PRE>
865</UL>
866
867
868
869<P>We have overloaded <TT><FONT SIZE=+1>operator new</FONT></TT> with a
870
871dummy argument to distinguish it from the regular global <TT><FONT SIZE=+1>operator
872
873new</FONT></TT>. This is comparable to the use of the <TT><FONT SIZE=+1>std::nothrow_t</FONT></TT>
874
875type and <TT><FONT SIZE=+1>std::nothrow</FONT></TT> object in the standard
876
877library. The placement <TT><FONT SIZE=+1>operator delete</FONT></TT> is
878
879there to perform any tidy up in the event of failed construction. Note
880
881that this is not yet supported on all that many compilers.</P>
882
883
884
885<P>The result of a <TT><FONT SIZE=+1>new</FONT></TT> expression using <TT><FONT SIZE=+1>countable</FONT></TT>
886
887is an object allocated on the heap that has a header block that holds the
888
889count, i.e. we have extended the object by prefixing it. We can provide
890
891a couple of features in an anonymous namespace (not shown) in the implementation
892
893file for for supporting the count and its access from a raw pointer:</P>
894
895
896
897<UL>
898
899<PRE><TT>struct count
900{
901    size_t value;
902};
903
904count *header(const void *ptr)
905{
906    return const_cast&lt;count *&gt;(static_cast&lt;const count *&gt;(ptr) - 1);
907}
908</TT></PRE>
909
910</UL>
911
912
913
914<P>An important constraint to observe here is the alignment of <TT><FONT SIZE=+1>count</FONT></TT>
915
916should be such that it is suitably aligned for any type. For the definition
917
918shown this will be the case on almost all platforms. However, you may need
919
920to add a padding member for those that don't, e.g. using an anonymous <TT><FONT SIZE=+1>union</FONT></TT>
921
922to coalign <TT><FONT SIZE=+1>count</FONT></TT> and the most aligned type.
923
924Unfortunately, there is no portable way of specifying this such that the
925
926minimum alignment is also observed - this is a common problem when specifying
927
928your own allocators that do not directly use the results of either <TT><FONT SIZE=+1>new</FONT></TT>
929
930or <TT><FONT SIZE=+1>malloc</FONT></TT>.</P>
931
932
933
934<P>Again, note that the count is not considered to be a part of the logical
935
936state of the object, and hence the conversion from <TT><FONT SIZE=+1>const</FONT></TT>
937
938to non-<TT><FONT SIZE=+1>const</FONT></TT> - <TT><FONT SIZE=+1>count</FONT></TT>
939
940is in effect a <TT><FONT SIZE=+1>mutable</FONT></TT> type.</P>
941
942
943
944<P>The allocator functions themselves are fairly straightforward:</P>
945
946
947
948<UL>
949
950<PRE><TT>void *operator new(size_t size, const countable_new &amp;)
951{
952    count *allocated = static_cast&lt;count *&gt;(::operator new(sizeof(count) + size));
953    *allocated = count(); // initialise the header
954    return allocated + 1; // adjust result to point to the body
955}
956
957void operator delete(void *ptr, const countable_new &amp;)
958{
959    ::operator delete(header(ptr));
960}
961</TT></PRE>
962
963</UL>
964
965
966
967<P>Given a correctly allocated header, we now need the <I>Countable </I>functions
968
969to operate on <TT><FONT SIZE=+1>const void *</FONT></TT> to complete the
970
971picture:</P>
972
973
974
975<UL>
976
977<PRE><TT>void acquire(const void *ptr)
978{
979    if(ptr)
980    {
981        ++header(ptr)-&gt;value;
982    }
983}
984
985void release(const void *ptr)
986{
987    if(ptr)
988    {
989        --header(ptr)-&gt;value;
990    }
991}
992
993size_t acquired(const void *ptr)
994{
995    return ptr ? header(ptr)-&gt;value : 0;
996}
997
998template&lt;typename countable_type&gt;
999void dispose(const countable_type *ptr, const void *)
1000{
1001    ptr-&gt;~countable_type();
1002    operator delete(const_cast&lt;countable_type *&gt;(ptr), countable);
1003}
1004</TT></PRE>
1005
1006</UL>
1007
1008
1009
1010<P>The most complex of these is the <TT><FONT SIZE=+1>dispose</FONT></TT>
1011
1012function that must ensure that the correct type is destructed and also
1013
1014that the memory is collected from the correct offset. It uses the value
1015
1016and type of first argument to perform this correctly, and the second argument
1017
1018merely acts as a strategy selector, i.e. the use of <TT><FONT SIZE=+1>const
1019
1020void *</FONT></TT> distinguishes it from the earlier dispose shown for
1021
1022<TT><FONT SIZE=+1>const countability *</FONT></TT>.</P>
1023
1024</UL>
1025
1026
1027
1028
1029<HR WIDTH="100%">
1030<H2>Getting smarter</H2>
1031
1032
1033
1034<UL>
1035
1036<P>Now that we have a way of adding countability at creation for objects
1037
1038of any type, what extra is needed to make this work with the <TT><FONT SIZE=+1>countable_ptr</FONT></TT>
1039
1040we defined earlier? Good news: nothing!</P>
1041
1042
1043
1044<UL>
1045
1046<PRE><TT>class example
1047{
1048    ...
1049};
1050
1051void simple()
1052{
1053    countable_ptr&lt;example&gt; ptr(new(countable) example);
1054    countable_ptr&lt;example&gt; qtr(ptr);
1055    ptr.clear(); // set ptr to point to null
1056}   // allocated object deleted when qtr destructs
1057</TT></PRE>
1058
1059</UL>
1060
1061
1062
1063<P>The <TT><FONT SIZE=+1>new(countable)</FONT></TT> expression defines
1064
1065a different policy for allocation and deallocation and, in common with
1066
1067other allocators, any attempt to mix your allocation policies, e.g. call
1068
1069<TT><FONT SIZE=+1>delete</FONT></TT> on an object allocated with <TT><FONT SIZE=+1>new(countable)</FONT></TT>,
1070
1071results in undefined behaviour. This is similar to what happens when you
1072
1073mix <TT><FONT SIZE=+1>new[]</FONT></TT> with <TT><FONT SIZE=+1>delete</FONT></TT>
1074
1075or <TT><FONT SIZE=+1>malloc</FONT></TT> with <TT><FONT SIZE=+1>delete</FONT></TT>.
1076
1077The whole point of <I>Countable </I>conformance is that <I>Countable </I>objects
1078
1079are used with <TT><FONT SIZE=+1>countable_ptr</FONT></TT>, and this ensures
1080
1081the correct use.</P>
1082
1083
1084
1085<P>However, accidents will happen, and inevitably you may forget to allocate
1086
1087using <TT><FONT SIZE=+1>new(countable)</FONT></TT> and instead use <TT><FONT SIZE=+1>new</FONT></TT>.
1088
1089This error and others can be detected in most cases by extending the code
1090
1091shown here to add a check member to the <TT><FONT SIZE=+1>count</FONT></TT>,
1092
1093validating the check on every access. A benefit of ensuring clear separation
1094
1095between header and implementation source files means that you can introduce
1096
1097a checking version of this allocator without having to recompile your code.</P>
1098
1099</UL>
1100
1101
1102
1103
1104<HR WIDTH="100%">
1105<H2>Conclusion</H2>
1106
1107
1108
1109<UL>
1110
1111<P>There are two key concepts that this article has introduced:</P>
1112
1113
1114
1115<UL>
1116
1117<LI>The use of a generic requirements based approach to simplify and adapt
1118
1119the use of the C<FONT SIZE=-1>OUNTED</FONT> B<FONT SIZE=-1>ODY</FONT> pattern.</LI>
1120
1121
1122
1123<LI>The ability, through control of allocation, to dynamically and non-intrusively
1124
1125add capabilities to fixed types using the R<FONT SIZE=-1>UNTIME</FONT>
1126
1127M<FONT SIZE=-1>IXIN</FONT> pattern.</LI>
1128
1129</UL>
1130
1131
1132
1133<P>The application of the two together gives rise to a new variant of the
1134
1135essential C<FONT SIZE=-1>OUNTED</FONT> B<FONT SIZE=-1>ODY</FONT> pattern,
1136
1137U<FONT SIZE=-1>NINTRUSIVE</FONT> C<FONT SIZE=-1>OUNTED</FONT> B<FONT SIZE=-1>ODY</FONT>.
1138
1139You can take this theme even further and contrive a simple garbage collection
1140
1141system for C++.</P>
1142
1143
1144
1145<P>The complete code for <TT><FONT SIZE=+1>countable_ptr</FONT></TT>, <TT><FONT SIZE=+1>countability</FONT></TT>,
1146
1147and the <TT><FONT SIZE=+1>countable new</FONT></TT> is also available.</P>
1148
1149</UL>
1150
1151
1152
1153<DIV ALIGN=right><P>
1154
1155<HR WIDTH="100%"><FONT SIZE=-1><I>First published in </I><a href="http://www.accu.org/c++sig/public/Overload.html">Overload</a> <I>25,
1156
1157April 1998, ISSN 1354-3172<BR>
1158
1159&copy; Copyright Kevlin Henney, 1998, 1999</I></FONT></DIV>
1160
1161
1162
1163</BODY>
1164
1165</HTML>
1166
Note: See TracBrowser for help on using the repository browser.