1 /***************************************************************************
2 * include/stxxl/bits/common/counting_ptr.h
3 *
4 * Part of the STXXL. See http://stxxl.sourceforge.net
5 *
6 * Copyright (C) 2010-2011 Raoul Steffen <R-Steffen@gmx.de>
7 * Copyright (C) 2013 Timo Bingmann <tb@panthema.net>
8 *
9 * Distributed under the Boost Software License, Version 1.0.
10 * (See accompanying file LICENSE_1_0.txt or copy at
11 * http://www.boost.org/LICENSE_1_0.txt)
12 **************************************************************************/
13
14 #ifndef STXXL_COMMON_COUNTING_PTR_HEADER
15 #define STXXL_COMMON_COUNTING_PTR_HEADER
16
17 #include <cassert>
18 #include <cstdlib>
19 #include <algorithm>
20 #include <stxxl/types>
21 #include <stxxl/bits/config.h>
22 #include <stxxl/bits/common/mutex.h>
23
24 STXXL_BEGIN_NAMESPACE
25
26 //! \addtogroup support
27 //! \{
28
29 /*!
30 * High-performance smart pointer used as a wrapping reference counting
31 * pointer.
32 *
33 * This smart pointer class requires two functions in the templated type: void
34 * inc_reference() and void dec_reference(). These must increment and decrement
35 * a reference counter inside the templated object. When initialized, the type
36 * must have reference count zero. It is _not_ immediately called with
37 * add_reference(). Each new object referencing the data calls add_reference()
38 * and each destroying holder calls del_reference(). When the data object
39 * determines that it's internal counter is zero, then it must destroy itself.
40 *
41 * Accompanying the counting_ptr is a const_counting_ptr and a class
42 * counted_object, from which reference counted classes must be derive
43 * from. The class counted_object implement all methods required for reference
44 * counting.
45 *
46 * The whole method is more similar to boost' instrusive_ptr, but also yields
47 * something resembling shared_ptr.
48 */
49 template <class Type>
50 class counting_ptr
51 {
52 public:
53 //! contained type.
54 typedef Type element_type;
55
56 private:
57 //! the pointer to the currently referenced object.
58 Type* m_ptr;
59
60 protected:
61 //! increment reference counter for current object.
inc_reference()62 void inc_reference()
63 { inc_reference(m_ptr); }
64
65 //! increment reference counter of other object.
inc_reference(Type * o)66 void inc_reference(Type* o)
67 { if (o) o->inc_reference(); }
68
69 //! decrement reference counter of current object and maybe delete it.
dec_reference()70 void dec_reference()
71 { if (m_ptr && m_ptr->dec_reference()) delete m_ptr; }
72
73 public:
74 //! default constructor: contains a NULL pointer.
counting_ptr()75 counting_ptr() : m_ptr(NULL)
76 { }
77
78 //! constructor with pointer: initializes new reference to ptr.
counting_ptr(Type * ptr)79 counting_ptr(Type* ptr) : m_ptr(ptr)
80 { inc_reference(); }
81
82 //! copy-constructor: also initializes new reference to ptr.
counting_ptr(const counting_ptr & other_ptr)83 counting_ptr(const counting_ptr& other_ptr) : m_ptr(other_ptr)
84 { inc_reference(); }
85
86 //! assignment operator: dereference current object and acquire reference on new one.
87 counting_ptr& operator = (const counting_ptr& other_ptr)
88 { return operator = (other_ptr.m_ptr); }
89
90 //! assignment to pointer: dereference current and acquire reference to new ptr.
91 counting_ptr& operator = (Type* ptr)
92 {
93 inc_reference(ptr);
94 dec_reference();
95 m_ptr = ptr;
96 return *this;
97 }
98
99 //! destructor: decrements reference counter in ptr.
~counting_ptr()100 ~counting_ptr()
101 { dec_reference(); }
102
103 //! return the enclosed object as reference.
104 Type& operator * () const
105 {
106 assert(m_ptr);
107 return *m_ptr;
108 }
109
110 //! return the enclosed pointer.
111 Type* operator -> () const
112 {
113 assert(m_ptr);
114 return m_ptr;
115 }
116
117 //! implicit cast to the enclosed pointer.
118 operator Type* () const
119 { return m_ptr; }
120
121 //! return the enclosed pointer.
get()122 Type * get() const
123 { return m_ptr; }
124
125 //! test equality of only the pointer values.
126 bool operator == (const counting_ptr& other_ptr) const
127 { return m_ptr == other_ptr.m_ptr; }
128
129 //! test inequality of only the pointer values.
130 bool operator != (const counting_ptr& other_ptr) const
131 { return m_ptr != other_ptr.m_ptr; }
132
133 //! cast to bool check for a NULL pointer
134 operator bool () const
135 { return valid(); }
136
137 //! test for a non-NULL pointer
valid()138 bool valid() const
139 { return (m_ptr != NULL); }
140
141 //! test for a NULL pointer
empty()142 bool empty() const
143 { return (m_ptr == NULL); }
144
145 //! if the object is referred by this counting_ptr only
unique()146 bool unique() const
147 { return m_ptr && m_ptr->unique(); }
148
149 //! make and refer a copy if the original object was shared.
unify()150 void unify()
151 {
152 if (m_ptr && ! m_ptr->unique())
153 operator = (new Type(*m_ptr));
154 }
155
156 //! swap enclosed object with another counting pointer (no reference counts need change)
swap(counting_ptr & b)157 void swap(counting_ptr& b)
158 {
159 std::swap(m_ptr, b.m_ptr);
160 }
161 };
162
163 //! swap enclosed object with another counting pointer (no reference counts need change)
164 template <class A>
swap(counting_ptr<A> & a1,counting_ptr<A> & a2)165 void swap(counting_ptr<A>& a1, counting_ptr<A>& a2)
166 {
167 a1.swap(a2);
168 }
169
170 /*!
171 * High-performance smart pointer used as a wrapping reference counting
172 * pointer.
173 *
174 * This smart pointer class requires two functions in the templated type: void
175 * inc_reference() and void dec_reference(). These must increment and decrement
176 * a reference counter inside the templated object. When initialized, the type
177 * must have reference count zero. It is _not_ immediately called with
178 * add_reference(). Each new object referencing the data calls add_reference()
179 * and each destroying holder calls del_reference(). When the data object
180 * determines that it's internal counter is zero, then it must destroy itself.
181 *
182 * Accompanying the counting_ptr is a const_counting_ptr and a class
183 * counted_object, from which reference counted classes must be derive
184 * from. The class counted_object implement all methods required for reference
185 * counting.
186 *
187 * The whole method is more similar to boost' instrusive_ptr, but also yields
188 * something resembling shared_ptr.
189 */
190 template <class Type>
191 class const_counting_ptr
192 {
193 public:
194 //! contained type.
195 typedef Type element_type;
196
197 private:
198 //! the pointer to the currently referenced object.
199 const Type* m_ptr;
200
201 protected:
202 //! increment reference counter for current object.
inc_reference()203 void inc_reference()
204 { inc_reference(m_ptr); }
205
206 //! increment reference counter of other object.
inc_reference(const Type * o)207 void inc_reference(const Type* o)
208 { if (o) o->inc_reference(); }
209
210 //! decrement reference counter of current object and maybe delete it.
dec_reference()211 void dec_reference()
212 { if (m_ptr && m_ptr->dec_reference()) delete m_ptr; }
213
214 public:
215 //! default constructor: contains a NULL pointer.
const_counting_ptr()216 const_counting_ptr() : m_ptr(NULL)
217 { }
218
219 //! constructor with pointer: initializes new reference to ptr.
const_counting_ptr(const Type * ptr)220 const_counting_ptr(const Type* ptr) : m_ptr(ptr)
221 { inc_reference(); }
222
223 //! copy-constructor: also initializes new reference to ptr.
const_counting_ptr(const const_counting_ptr & other_ptr)224 const_counting_ptr(const const_counting_ptr& other_ptr) : m_ptr(other_ptr)
225 { inc_reference(); }
226
227 //! constructor from non-const: also initializes new reference to ptr.
const_counting_ptr(const counting_ptr<Type> & other_ptr)228 const_counting_ptr(const counting_ptr<Type>& other_ptr) : m_ptr(other_ptr.get())
229 { inc_reference(); }
230
231 //! assignment operator: dereference current object and acquire reference on new one.
232 const_counting_ptr& operator = (const const_counting_ptr& other_ptr)
233 { return operator = (other_ptr.m_ptr); }
234
235 //! assignment operator: dereference current object and acquire reference on new one.
236 const_counting_ptr& operator = (const counting_ptr<Type>& other_ptr)
237 { return operator = (other_ptr.get()); }
238
239 //! assignment to pointer: dereference current and acquire reference to new ptr.
240 const_counting_ptr& operator = (const Type* ptr)
241 {
242 inc_reference(ptr);
243 dec_reference();
244 m_ptr = ptr;
245 return *this;
246 }
247
248 //! destructor: decrements reference counter in ptr.
~const_counting_ptr()249 ~const_counting_ptr()
250 { dec_reference(); }
251
252 //! return the enclosed object as reference.
253 const Type& operator * () const
254 {
255 assert(m_ptr);
256 return *m_ptr;
257 }
258
259 //! return the enclosed pointer.
260 const Type* operator -> () const
261 {
262 assert(m_ptr);
263 return m_ptr;
264 }
265
266 //! implicit cast to the enclosed pointer.
267 operator const Type* () const
268 { return m_ptr; }
269
270 //! return the enclosed pointer.
get()271 const Type * get() const
272 { return m_ptr; }
273
274 //! test equality of only the pointer values.
275 bool operator == (const const_counting_ptr& other_ptr) const
276 { return m_ptr == other_ptr.m_ptr; }
277
278 //! test inequality of only the pointer values.
279 bool operator != (const const_counting_ptr& other_ptr) const
280 { return m_ptr != other_ptr.m_ptr; }
281
282 //! test equality of only the pointer values.
283 bool operator == (const counting_ptr<Type>& other_ptr) const
284 { return m_ptr == other_ptr.get(); }
285
286 //! test inequality of only the pointer values.
287 bool operator != (const counting_ptr<Type>& other_ptr) const
288 { return m_ptr != other_ptr.get(); }
289
290 //! cast to bool check for a NULL pointer
291 operator bool () const
292 { return m_ptr; }
293
294 //! test for a non-NULL pointer
valid()295 bool valid() const
296 { return m_ptr; }
297
298 //! test for a NULL pointer
empty()299 bool empty() const
300 { return !m_ptr; }
301
302 //! if the object is referred by this const_counting_ptr only
unique()303 bool unique() const
304 { return m_ptr && m_ptr->unique(); }
305
306 //! swap enclosed object with another const_counting pointer (no reference counts need change)
swap(const_counting_ptr & b)307 void swap(const_counting_ptr& b)
308 {
309 std::swap(m_ptr, b.m_ptr);
310 }
311 };
312
313 //! swap enclosed object with another const_counting pointer (no reference counts need change)
314 template <class A>
swap(const_counting_ptr<A> & a1,const_counting_ptr<A> & a2)315 void swap(const_counting_ptr<A>& a1, const_counting_ptr<A>& a2)
316 {
317 a1.swap(a2);
318 }
319
320 /*!
321 * Provides reference counting abilities for use with counting_ptr.
322 *
323 * Use as superclass of the actual object, this adds a reference_count
324 * value. Then either use counting_ptr as pointer to manage references and
325 * deletion, or just do normal new and delete.
326 *
327 * For thread-safe functions, use atomic_counted_object instead of this class!
328 */
329 class counted_object
330 {
331 private:
332 //! the reference count is kept mutable to all const_counting_ptr() to
333 //! change the reference count.
334 mutable unsigned_type m_reference_count;
335
336 public:
337 //! new objects have zero reference count
counted_object()338 counted_object()
339 : m_reference_count(0) { }
340
341 //! coping still creates a new object with zero reference count
counted_object(const counted_object &)342 counted_object(const counted_object&)
343 : m_reference_count(0) { }
344
345 //! assignment operator, leaves pointers unchanged
346 counted_object& operator = (const counted_object&)
347 { return *this; } // changing the contents leaves pointers unchanged
348
~counted_object()349 ~counted_object()
350 { assert(m_reference_count == 0); }
351
352 public:
353 //! Call whenever setting a pointer to the object
inc_reference()354 void inc_reference() const
355 { ++m_reference_count; }
356
357 //! Call whenever resetting (i.e. overwriting) a pointer to the object.
358 //! IMPORTANT: In case of self-assignment, call AFTER inc_reference().
359 //! \return if the object has to be deleted (i.e. if it's reference count dropped to zero)
dec_reference()360 bool dec_reference() const
361 { return (! --m_reference_count); }
362
363 //! Test if the counted_object is referenced by only one counting_ptr.
unique()364 bool unique() const
365 { return (m_reference_count == 1); }
366
367 //! Return the number of references to this object (for debugging)
get_reference_count()368 unsigned_type get_reference_count() const
369 { return m_reference_count; }
370 };
371
372 #if STXXL_HAVE_SYNC_ADD_AND_FETCH || STXXL_MSVC
373
374 /*!
375 * Provides reference counting abilities for use with counting_ptr with atomics
376 * operations.
377 *
378 * Use as superclass of the actual object, this adds a reference_count
379 * value. Then either use counting_ptr as pointer to manage references and
380 * deletion, or just do normal new and delete.
381 *
382 * This class does thread-safe increment and decrement using atomic operations
383 * on an integral type.
384 */
385 class atomic_counted_object
386 {
387 private:
388 //! the reference count is kept mutable to all const_counting_ptr() to
389 //! change the reference count.
390 #if STXXL_MSVC
391 mutable long m_reference_count;
392 #else
393 mutable unsigned_type m_reference_count;
394 #endif
395
396 public:
397 //! new objects have zero reference count
atomic_counted_object()398 atomic_counted_object()
399 : m_reference_count(0) { }
400
401 //! coping still creates a new object with zero reference count
atomic_counted_object(const atomic_counted_object &)402 atomic_counted_object(const atomic_counted_object&)
403 : m_reference_count(0) { }
404
405 //! assignment operator, leaves pointers unchanged
406 atomic_counted_object& operator = (const atomic_counted_object&)
407 { return *this; } // changing the contents leaves pointers unchanged
408
~atomic_counted_object()409 ~atomic_counted_object()
410 { assert(m_reference_count == 0); }
411
412 public:
413 //! Call whenever setting a pointer to the object
inc_reference()414 void inc_reference() const
415 {
416 #if STXXL_MSVC
417 _InterlockedIncrement(&m_reference_count);
418 #else
419 __sync_add_and_fetch(&m_reference_count, +1);
420 #endif
421 }
422
423 //! Call whenever resetting (i.e. overwriting) a pointer to the object.
424 //! IMPORTANT: In case of self-assignment, call AFTER inc_reference().
425 //! \return if the object has to be deleted (i.e. if it's reference count dropped to zero)
dec_reference()426 bool dec_reference() const
427 {
428 #if STXXL_MSVC
429 return (_InterlockedDecrement(&m_reference_count) == 0);
430 #else
431 return (__sync_add_and_fetch(&m_reference_count, -1) == 0);
432 #endif
433 }
434
435 //! Test if the counted_object is referenced by only one counting_ptr.
unique()436 bool unique() const
437 {
438 return (m_reference_count == 1);
439 }
440
441 //! Return the number of references to this object (for debugging)
get_reference_count()442 unsigned_type get_reference_count() const
443 {
444 return m_reference_count;
445 }
446 };
447
448 #else // no atomic intrinsics found, use mutexes (slow)
449
450 /*!
451 * Provides reference counting abilities for use with counting_ptr with mutex
452 * locking.
453 *
454 * Use as superclass of the actual object, this adds a reference_count
455 * value. Then either use counting_ptr as pointer to manage references and
456 * deletion, or just do normal new and delete.
457 *
458 * This class does thread-safe increment and decrement using scoped locks. A
459 * faster version of this class is available using atomic operations.
460 */
461 class atomic_counted_object
462 {
463 private:
464 //! the reference count is kept mutable to all const_counting_ptr() to
465 //! change the reference count.
466 mutable unsigned_type m_reference_count;
467
468 //! the mutex used to synchronize access to the reference counter.
469 mutable mutex m_reference_count_mutex;
470
471 public:
472 //! new objects have zero reference count
atomic_counted_object()473 atomic_counted_object()
474 : m_reference_count(0) { }
475
476 //! coping still creates a new object with zero reference count
atomic_counted_object(const atomic_counted_object &)477 atomic_counted_object(const atomic_counted_object&)
478 : m_reference_count(0) { }
479
480 //! assignment operator, leaves pointers unchanged
481 atomic_counted_object& operator = (const atomic_counted_object&)
482 { return *this; } // changing the contents leaves pointers unchanged
483
~atomic_counted_object()484 ~atomic_counted_object()
485 { assert(m_reference_count == 0); }
486
487 public:
488 //! Call whenever setting a pointer to the object
inc_reference()489 void inc_reference() const
490 {
491 scoped_mutex_lock lock(m_reference_count_mutex);
492 ++m_reference_count;
493 }
494
495 //! Call whenever resetting (i.e. overwriting) a pointer to the object.
496 //! IMPORTANT: In case of self-assignment, call AFTER inc_reference().
497 //! \return if the object has to be deleted (i.e. if it's reference count dropped to zero)
dec_reference()498 bool dec_reference() const
499 {
500 scoped_mutex_lock lock(m_reference_count_mutex);
501 return (--m_reference_count == 0);
502 }
503
504 //! Test if the counted_object is referenced by only one counting_ptr.
unique()505 bool unique() const
506 {
507 scoped_mutex_lock lock(m_reference_count_mutex);
508 return (m_reference_count == 1);
509 }
510
511 //! Return the number of references to this object (for debugging)
get_reference_count()512 unsigned_type get_reference_count() const
513 {
514 scoped_mutex_lock lock(m_reference_count_mutex);
515 return m_reference_count;
516 }
517 };
518
519 #endif
520
521 //! \}
522
523 STXXL_END_NAMESPACE
524
525 #endif // !STXXL_COMMON_COUNTING_PTR_HEADER
526