1 ////////////////////////////////////////////////////////////////////////////////
3 // Copyright (c) 2001 by Andrei Alexandrescu
4 // This code accompanies the book:
5 // Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design
6 // Patterns Applied". Copyright (c) 2001. Addison-Wesley.
7 // Permission to use, copy, modify, distribute and sell this software for any
8 // purpose is hereby granted without fee, provided that the above copyright
9 // notice appear in all copies and that both that copyright notice and this
10 // permission notice appear in supporting documentation.
11 // The author or Addison-Wesley Longman make no representations about the
12 // suitability of this software for any purpose. It is provided "as is"
13 // without express or implied warranty.
14 ////////////////////////////////////////////////////////////////////////////////
15 #ifndef LOKI_SMALLOBJ_INC_
16 #define LOKI_SMALLOBJ_INC_
18 // $Id: SmallObj.h 806 2007-02-03 00:01:52Z rich_sposato $
21 #include "LokiExport.h"
23 #include "Singleton.h"
25 #include <new> // needed for std::nothrow_t parameter.
27 #ifndef LOKI_DEFAULT_CHUNK_SIZE
28 #define LOKI_DEFAULT_CHUNK_SIZE 4096
31 #ifndef LOKI_MAX_SMALL_OBJECT_SIZE
32 #define LOKI_MAX_SMALL_OBJECT_SIZE 256
35 #ifndef LOKI_DEFAULT_OBJECT_ALIGNMENT
36 #define LOKI_DEFAULT_OBJECT_ALIGNMENT 4
39 #ifndef LOKI_DEFAULT_SMALLOBJ_LIFETIME
40 #define LOKI_DEFAULT_SMALLOBJ_LIFETIME ::Loki::LongevityLifetime::DieAsSmallObjectParent
43 #if defined(LOKI_SMALL_OBJECT_USE_NEW_ARRAY) && defined(_MSC_VER)
44 #pragma message("Don't define LOKI_SMALL_OBJECT_USE_NEW_ARRAY when using a Microsoft compiler to prevent memory leaks.")
45 #pragma message("now calling '#undef LOKI_SMALL_OBJECT_USE_NEW_ARRAY'")
46 #undef LOKI_SMALL_OBJECT_USE_NEW_ARRAY
49 /// \defgroup SmallObjectGroup Small objects
51 /// \defgroup SmallObjectGroupInternal Internals
52 /// \ingroup SmallObjectGroup
56 namespace LongevityLifetime
58 /** @struct DieAsSmallObjectParent
59 @ingroup SmallObjectGroup
60 Lifetime policy to manage lifetime dependencies of
61 SmallObject base and child classes.
62 The Base class should have this lifetime
65 struct DieAsSmallObjectParent : DieLast<T> {};
67 /** @struct DieAsSmallObjectChild
68 @ingroup SmallObjectGroup
69 Lifetime policy to manage lifetime dependencies of
70 SmallObject base and child classes.
71 The Child class should have this lifetime
74 struct DieAsSmallObjectChild : DieDirectlyBeforeLast<T> {};
80 /** @class SmallObjAllocator
81 @ingroup SmallObjectGroupInternal
82 Manages pool of fixed-size allocators.
83 Designed to be a non-templated base class of AllocatorSingleton so that
84 implementation details can be safely hidden in the source code file.
86 class LOKI_EXPORT SmallObjAllocator
89 /** The only available constructor needs certain parameters in order to
90 initialize all the FixedAllocator's. This throws only if
91 @param pageSize # of bytes in a page of memory.
92 @param maxObjectSize Max # of bytes which this may allocate.
93 @param objectAlignSize # of bytes between alignment boundaries.
95 SmallObjAllocator( std::size_t pageSize, std::size_t maxObjectSize,
96 std::size_t objectAlignSize );
98 /** Destructor releases all blocks, all Chunks, and FixedAllocator's.
99 Any outstanding blocks are unavailable, and should not be used after
100 this destructor is called. The destructor is deliberately non-virtual
101 because it is protected, not public.
103 ~SmallObjAllocator( void );
106 /** Allocates a block of memory of requested size. Complexity is often
107 constant-time, but might be O(C) where C is the number of Chunks in a
110 @par Exception Safety Level
111 Provides either strong-exception safety, or no-throw exception-safety
112 level depending upon doThrow parameter. The reason it provides two
113 levels of exception safety is because it is used by both the nothrow
114 and throwing new operators. The underlying implementation will never
115 throw of its own accord, but this can decide to throw if it does not
116 allocate. The only exception it should emit is std::bad_alloc.
118 @par Allocation Failure
119 If it does not allocate, it will call TrimExcessMemory and attempt to
120 allocate again, before it decides to throw or return NULL. Many
121 allocators loop through several new_handler functions, and terminate
122 if they can not allocate, but not this one. It only makes one attempt
123 using its own implementation of the new_handler, and then returns NULL
124 or throws so that the program can decide what to do at a higher level.
125 (Side note: Even though the C++ Standard allows allocators and
126 new_handlers to terminate if they fail, the Loki allocator does not do
127 that since that policy is not polite to a host program.)
129 @param size # of bytes needed for allocation.
130 @param doThrow True if this should throw if unable to allocate, false
131 if it should provide no-throw exception safety level.
132 @return NULL if nothing allocated and doThrow is false. Else the
133 pointer to an available block of memory.
135 void *Allocate( std::size_t size, bool doThrow );
137 /** Deallocates a block of memory at a given place and of a specific
138 size. Complexity is almost always constant-time, and is O(C) only if
139 it has to search for which Chunk deallocates. This never throws.
141 void Deallocate( void *p, std::size_t size );
143 /** Deallocates a block of memory at a given place but of unknown size
144 size. Complexity is O(F + C) where F is the count of FixedAllocator's
145 in the pool, and C is the number of Chunks in all FixedAllocator's. This
146 does not throw exceptions. This overloaded version of Deallocate is
147 called by the nothow delete operator - which is called when the nothrow
148 new operator is used, but a constructor throws an exception.
150 void Deallocate( void *p );
152 /// Returns max # of bytes which this can allocate.
153 inline std::size_t GetMaxObjectSize() const
155 return maxSmallObjectSize_;
158 /// Returns # of bytes between allocation boundaries.
159 inline std::size_t GetAlignment() const
161 return objectAlignSize_;
164 /** Releases empty Chunks from memory. Complexity is O(F + C) where F
165 is the count of FixedAllocator's in the pool, and C is the number of
166 Chunks in all FixedAllocator's. This will never throw. This is called
167 by AllocatorSingleto::ClearExtraMemory, the new_handler function for
168 Loki's allocator, and is called internally when an allocation fails.
169 @return True if any memory released, or false if none released.
171 bool TrimExcessMemory( void );
173 /** Returns true if anything in implementation is corrupt. Complexity
174 is O(F + C + B) where F is the count of FixedAllocator's in the pool,
175 C is the number of Chunks in all FixedAllocator's, and B is the number
176 of blocks in all Chunks. If it determines any data is corrupted, this
177 will return true in release version, but assert in debug version at
178 the line where it detects the corrupted data. If it does not detect
179 any corrupted data, it returns false.
181 bool IsCorrupt( void ) const;
184 /// Default-constructor is not implemented.
185 SmallObjAllocator( void );
186 /// Copy-constructor is not implemented.
187 SmallObjAllocator( const SmallObjAllocator & );
188 /// Copy-assignment operator is not implemented.
189 SmallObjAllocator &operator = ( const SmallObjAllocator & );
191 /// Pointer to array of fixed-size allocators.
192 Loki::FixedAllocator *pool_;
194 /// Largest object size supported by allocators.
195 const std::size_t maxSmallObjectSize_;
197 /// Size of alignment boundaries.
198 const std::size_t objectAlignSize_;
202 /** @class AllocatorSingleton
203 @ingroup SmallObjectGroupInternal
204 This template class is derived from
205 SmallObjAllocator in order to pass template arguments into it, and still
206 have a default constructor for the singleton. Each instance is a unique
207 combination of all the template parameters, and hence is singleton only
208 with respect to those parameters. The template parameters have default
209 values and the class has typedefs identical to both SmallObject and
210 SmallValueObject so that this class can be used directly instead of going
211 through SmallObject or SmallValueObject. That design feature allows
212 clients to use the new_handler without having the name of the new_handler
213 function show up in classes derived from SmallObject or SmallValueObject.
214 Thus, the only functions in the allocator which show up in SmallObject or
215 SmallValueObject inheritance hierarchies are the new and delete
220 template <class, class> class ThreadingModel = LOKI_DEFAULT_THREADING_NO_OBJ_LEVEL,
221 std::size_t chunkSize = LOKI_DEFAULT_CHUNK_SIZE,
222 std::size_t maxSmallObjectSize = LOKI_MAX_SMALL_OBJECT_SIZE,
223 std::size_t objectAlignSize = LOKI_DEFAULT_OBJECT_ALIGNMENT,
224 template <class> class LifetimePolicy = LOKI_DEFAULT_SMALLOBJ_LIFETIME,
225 class MutexPolicy = LOKI_DEFAULT_MUTEX
227 class AllocatorSingleton : public SmallObjAllocator
231 /// Defines type of allocator.
232 typedef AllocatorSingleton< ThreadingModel, chunkSize,
233 maxSmallObjectSize, objectAlignSize, LifetimePolicy > MyAllocator;
235 /// Defines type for thread-safety locking mechanism.
236 typedef ThreadingModel< MyAllocator, MutexPolicy > MyThreadingModel;
238 /// Defines singleton made from allocator.
239 typedef Loki::SingletonHolder< MyAllocator, Loki::CreateStatic,
240 LifetimePolicy, ThreadingModel > MyAllocatorSingleton;
242 /// Returns reference to the singleton.
243 inline static AllocatorSingleton &Instance( void )
245 return MyAllocatorSingleton::Instance();
248 /// The default constructor is not meant to be called directly.
249 inline AllocatorSingleton() :
250 SmallObjAllocator( chunkSize, maxSmallObjectSize, objectAlignSize )
253 /// The destructor is not meant to be called directly.
254 inline ~AllocatorSingleton( void ) {}
256 /** Clears any excess memory used by the allocator. Complexity is
257 O(F + C) where F is the count of FixedAllocator's in the pool, and C
258 is the number of Chunks in all FixedAllocator's. This never throws.
259 @note This function can be used as a new_handler when Loki and other
260 memory allocators can no longer allocate. Although the C++ Standard
261 allows new_handler functions to terminate the program when they can
262 not release any memory, this will not do so.
264 static void ClearExtraMemory( void );
266 /** Returns true if anything in implementation is corrupt. Complexity
267 is O(F + C + B) where F is the count of FixedAllocator's in the pool,
268 C is the number of Chunks in all FixedAllocator's, and B is the number
269 of blocks in all Chunks. If it determines any data is corrupted, this
270 will return true in release version, but assert in debug version at
271 the line where it detects the corrupted data. If it does not detect
272 any corrupted data, it returns false.
274 static bool IsCorrupted( void );
277 /// Copy-constructor is not implemented.
278 AllocatorSingleton( const AllocatorSingleton & );
279 /// Copy-assignment operator is not implemented.
280 AllocatorSingleton &operator = ( const AllocatorSingleton & );
285 template <class, class> class T,
289 template <class> class L,
292 void AllocatorSingleton< T, C, M, O, L, X >::ClearExtraMemory( void )
294 typename MyThreadingModel::Lock lock;
295 (void)lock; // get rid of warning
296 Instance().TrimExcessMemory();
301 template <class, class> class T,
305 template <class> class L,
308 bool AllocatorSingleton< T, C, M, O, L, X >::IsCorrupted( void )
310 typename MyThreadingModel::Lock lock;
311 (void)lock; // get rid of warning
312 return Instance().IsCorrupt();
315 /** This standalone function provides the longevity level for Small-Object
316 Allocators which use the Loki::SingletonWithLongevity policy. The
317 SingletonWithLongevity class can find this function through argument-
320 @par Longevity Levels
321 No Small-Object Allocator depends on any other Small-Object allocator, so
322 this does not need to calculate dependency levels among allocators, and
323 it returns just a constant. All allocators must live longer than the
324 objects which use the allocators, it must return a longevity level higher
325 than any such object.
329 template <class, class> class T,
333 template <class> class L,
336 inline unsigned int GetLongevity(
337 AllocatorSingleton< T, C, M, O, L, X > * )
339 // Returns highest possible value.
344 /** @class SmallObjectBase
345 @ingroup SmallObjectGroup
346 Base class for small object allocation classes.
347 The shared implementation of the new and delete operators are here instead
348 of being duplicated in both SmallObject or SmallValueObject, later just
349 called Small-Objects. This class is not meant to be used directly by clients,
350 or derived from by clients. Class has no data members so compilers can
351 use Empty-Base-Optimization.
354 This class doesn't support ObjectLevelLockable policy for ThreadingModel.
355 The allocator is a singleton, so a per-instance mutex is not necessary.
356 Nor is using ObjectLevelLockable recommended with SingletonHolder since
357 the SingletonHolder::MakeInstance function requires a mutex that exists
358 prior to when the object is created - which is not possible if the mutex
359 is inside the object, such as required for ObjectLevelLockable. If you
360 attempt to use ObjectLevelLockable, the compiler will emit errors because
361 it can't use the default constructor in ObjectLevelLockable. If you need
362 a thread-safe allocator, use the ClassLevelLockable policy.
366 The SmallObjectBase template needs a lifetime policy because it owns
367 a singleton of SmallObjAllocator which does all the low level functions.
368 When using a Small-Object in combination with the SingletonHolder template
369 you have to choose two lifetimes, that of the Small-Object and that of
370 the singleton. The rule is: The Small-Object lifetime must be greater than
371 the lifetime of the singleton hosting the Small-Object. Violating this rule
372 results in a crash on exit, because the hosting singleton tries to delete
373 the Small-Object which is then already destroyed.
375 The lifetime policies recommended for use with Small-Objects hosted
376 by a SingletonHolder template are
377 - LongevityLifetime::DieAsSmallObjectParent / LongevityLifetime::DieAsSmallObjectChild
378 - SingletonWithLongevity
379 - FollowIntoDeath (not supported by MSVC 7.1)
382 The default lifetime of Small-Objects is
383 LongevityLifetime::DieAsSmallObjectParent to
384 insure that memory is not released before a object with the lifetime
385 LongevityLifetime::DieAsSmallObjectChild using that
386 memory is destroyed. The LongevityLifetime::DieAsSmallObjectParent
387 lifetime has the highest possible value of a SetLongevity lifetime, so
388 you can use it in combination with your own lifetime not having also
389 the highest possible value.
391 The DefaultLifetime and PhoenixSingleton policies are *not* recommended
392 since they can cause the allocator to be destroyed and release memory
393 for singletons hosting a object which inherit from either SmallObject
398 - LongevityLifetime: The Small-Object has
399 LongevityLifetime::DieAsSmallObjectParent policy and the Singleton
400 hosting the Small-Object has LongevityLifetime::DieAsSmallObjectChild.
401 The child lifetime has a hard coded SetLongevity lifetime which is
402 shorter than the lifetime of the parent, thus the child dies
405 - Both Small-Object and Singleton use SingletonWithLongevity policy.
406 The longevity level for the singleton must be lower than that for the
407 Small-Object. This is why the AllocatorSingleton's GetLongevity function
408 returns the highest value.
410 - FollowIntoDeath lifetime: The Small-Object has
411 FollowIntoDeath::With<LIFETIME>::AsMasterLiftime
412 policy and the Singleton has
413 FollowIntoDeath::AfterMaster<MASTERSINGLETON>::IsDestroyed policy,
414 where you could choose the LIFETIME.
416 - Both Small-Object and Singleton use NoDestroy policy.
417 Since neither is ever destroyed, the destruction order does not matter.
418 Note: you will get memory leaks!
420 - The Small-Object has NoDestroy policy but the Singleton has
421 SingletonWithLongevity policy. Note: you will get memory leaks!
424 You should *not* use NoDestroy for the singleton, and then use
425 SingletonWithLongevity for the Small-Object.
429 - test/SmallObj/SmallSingleton.cpp
430 - test/Singleton/Dependencies.cpp
434 template <class, class> class ThreadingModel,
435 std::size_t chunkSize,
436 std::size_t maxSmallObjectSize,
437 std::size_t objectAlignSize,
438 template <class> class LifetimePolicy,
441 class SmallObjectBase
444 #if (LOKI_MAX_SMALL_OBJECT_SIZE != 0) && (LOKI_DEFAULT_CHUNK_SIZE != 0) && (LOKI_DEFAULT_OBJECT_ALIGNMENT != 0)
447 /// Defines type of allocator singleton, must be public
448 /// to handle singleton lifetime dependencies.
449 typedef AllocatorSingleton< ThreadingModel, chunkSize,
450 maxSmallObjectSize, objectAlignSize, LifetimePolicy > ObjAllocatorSingleton;
454 /// Defines type for thread-safety locking mechanism.
455 typedef ThreadingModel< ObjAllocatorSingleton, MutexPolicy > MyThreadingModel;
457 /// Use singleton defined in AllocatorSingleton.
458 typedef typename ObjAllocatorSingleton::MyAllocatorSingleton MyAllocatorSingleton;
462 /// Throwing single-object new throws bad_alloc when allocation fails.
464 /// @note MSVC complains about non-empty exception specification lists.
465 static void *operator new ( std::size_t size )
467 static void *operator new ( std::size_t size ) throw ( std::bad_alloc )
470 typename MyThreadingModel::Lock lock;
471 (void)lock; // get rid of warning
472 return MyAllocatorSingleton::Instance().Allocate( size, true );
475 /// Non-throwing single-object new returns NULL if allocation fails.
476 static void *operator new ( std::size_t size, const std::nothrow_t & ) throw ()
478 typename MyThreadingModel::Lock lock;
479 (void)lock; // get rid of warning
480 return MyAllocatorSingleton::Instance().Allocate( size, false );
483 /// Placement single-object new merely calls global placement new.
484 inline static void *operator new ( std::size_t size, void *place )
486 return ::operator new( size, place );
489 /// Single-object delete.
490 static void operator delete ( void *p, std::size_t size ) throw ()
492 typename MyThreadingModel::Lock lock;
493 (void)lock; // get rid of warning
494 MyAllocatorSingleton::Instance().Deallocate( p, size );
497 /** Non-throwing single-object delete is only called when nothrow
498 new operator is used, and the constructor throws an exception.
500 static void operator delete ( void *p, const std::nothrow_t & ) throw()
502 typename MyThreadingModel::Lock lock;
503 (void)lock; // get rid of warning
504 MyAllocatorSingleton::Instance().Deallocate( p );
507 /// Placement single-object delete merely calls global placement delete.
508 inline static void operator delete ( void *p, void *place )
510 ::operator delete ( p, place );
513 #ifdef LOKI_SMALL_OBJECT_USE_NEW_ARRAY
515 /// Throwing array-object new throws bad_alloc when allocation fails.
517 /// @note MSVC complains about non-empty exception specification lists.
518 static void *operator new [] ( std::size_t size )
520 static void *operator new [] ( std::size_t size )
521 throw ( std::bad_alloc )
524 typename MyThreadingModel::Lock lock;
525 (void)lock; // get rid of warning
526 return MyAllocatorSingleton::Instance().Allocate( size, true );
529 /// Non-throwing array-object new returns NULL if allocation fails.
530 static void *operator new [] ( std::size_t size,
531 const std::nothrow_t & ) throw ()
533 typename MyThreadingModel::Lock lock;
534 (void)lock; // get rid of warning
535 return MyAllocatorSingleton::Instance().Allocate( size, false );
538 /// Placement array-object new merely calls global placement new.
539 inline static void *operator new [] ( std::size_t size, void *place )
541 return ::operator new( size, place );
544 /// Array-object delete.
545 static void operator delete [] ( void *p, std::size_t size ) throw ()
547 typename MyThreadingModel::Lock lock;
548 (void)lock; // get rid of warning
549 MyAllocatorSingleton::Instance().Deallocate( p, size );
552 /** Non-throwing array-object delete is only called when nothrow
553 new operator is used, and the constructor throws an exception.
555 static void operator delete [] ( void *p,
556 const std::nothrow_t & ) throw()
558 typename MyThreadingModel::Lock lock;
559 (void)lock; // get rid of warning
560 MyAllocatorSingleton::Instance().Deallocate( p );
563 /// Placement array-object delete merely calls global placement delete.
564 inline static void operator delete [] ( void *p, void *place )
566 ::operator delete ( p, place );
568 #endif // #if use new array functions.
570 #endif // #if default template parameters are not zero
573 inline SmallObjectBase( void ) {}
574 inline SmallObjectBase( const SmallObjectBase & ) {}
575 inline SmallObjectBase &operator = ( const SmallObjectBase & )
579 inline ~SmallObjectBase() {}
580 }; // end class SmallObjectBase
583 /** @class SmallObject
584 @ingroup SmallObjectGroup
585 SmallObject Base class for polymorphic small objects, offers fast
586 allocations & deallocations. Destructor is virtual and public. Default
587 constructor is trivial. Copy-constructor and copy-assignment operator are
588 not implemented since polymorphic classes almost always disable those
589 operations. Class has no data members so compilers can use
590 Empty-Base-Optimization.
594 template <class, class> class ThreadingModel = LOKI_DEFAULT_THREADING_NO_OBJ_LEVEL,
595 std::size_t chunkSize = LOKI_DEFAULT_CHUNK_SIZE,
596 std::size_t maxSmallObjectSize = LOKI_MAX_SMALL_OBJECT_SIZE,
597 std::size_t objectAlignSize = LOKI_DEFAULT_OBJECT_ALIGNMENT,
598 template <class> class LifetimePolicy = LOKI_DEFAULT_SMALLOBJ_LIFETIME,
599 class MutexPolicy = LOKI_DEFAULT_MUTEX
601 class SmallObject : public SmallObjectBase< ThreadingModel, chunkSize,
602 maxSmallObjectSize, objectAlignSize, LifetimePolicy, MutexPolicy >
606 virtual ~SmallObject() {}
608 inline SmallObject( void ) {}
611 /// Copy-constructor is not implemented.
612 SmallObject( const SmallObject & );
613 /// Copy-assignment operator is not implemented.
614 SmallObject &operator = ( const SmallObject & );
615 }; // end class SmallObject
618 /** @class SmallValueObject
619 @ingroup SmallObjectGroup
620 SmallValueObject Base class for small objects with value-type
621 semantics - offers fast allocations & deallocations. Destructor is
622 non-virtual, inline, and protected to prevent unintentional destruction
623 through base class. Default constructor is trivial. Copy-constructor
624 and copy-assignment operator are trivial since value-types almost always
625 need those operations. Class has no data members so compilers can use
626 Empty-Base-Optimization.
630 template <class, class> class ThreadingModel = LOKI_DEFAULT_THREADING_NO_OBJ_LEVEL,
631 std::size_t chunkSize = LOKI_DEFAULT_CHUNK_SIZE,
632 std::size_t maxSmallObjectSize = LOKI_MAX_SMALL_OBJECT_SIZE,
633 std::size_t objectAlignSize = LOKI_DEFAULT_OBJECT_ALIGNMENT,
634 template <class> class LifetimePolicy = LOKI_DEFAULT_SMALLOBJ_LIFETIME,
635 class MutexPolicy = LOKI_DEFAULT_MUTEX
637 class SmallValueObject : public SmallObjectBase< ThreadingModel, chunkSize,
638 maxSmallObjectSize, objectAlignSize, LifetimePolicy, MutexPolicy >
641 inline SmallValueObject( void ) {}
642 inline SmallValueObject( const SmallValueObject & ) {}
643 inline SmallValueObject &operator = ( const SmallValueObject & )
647 inline ~SmallValueObject() {}
648 }; // end class SmallValueObject
652 #endif // end file guardian