C++ Standard Allocator, An Introduction and Implementation

Lai Shiaw San Kent
Rate me:
4.91/5 (26 votes)
18 Aug 2003CPOL10 min read
295.5K
1.8K
102
Introduction to the allocator concept, as well as implementing a policy-driven allocator template class
allocator.zip
// Generated by Henrik Stuart's .hpp generator: www.unprompted.com/hstuart/
#ifndef allocator_hpp_e1184f45_01e5_4089_b02d_d6f41dcf1192
#define allocator_hpp_e1184f45_01e5_4089_b02d_d6f41dcf1192

#include <SmallObj.h>
#include <limits>
#include <memory>

//	modelled after Sean Kent's allocator, with changes

namespace Dot {

///////////////////////////////////////////////////////////////////////////
//	class ObjectTraits
///////////////////////////////////////////////////////////////////////////

	//	Traits that describes an object T
	template<typename T>
	class ObjectTraits {
	public : 
		//	convert an ObjectTraits<T> to ObjectTraits<U>
		template<typename U>
		struct rebind {
			typedef ObjectTraits<U> other;
		};

	public : 
		inline explicit ObjectTraits() {}
		inline ~ObjectTraits() {}
		inline explicit ObjectTraits(ObjectTraits  const&) {}
		template <typename U>
		inline explicit ObjectTraits(ObjectTraits<U> const&) {}

		//	address
		inline T* address(T& r) { return &r; }
		inline T const* address(T const& r) { return &r; }

		inline static void construct(T* p, const T& t) { new(p) T(t); }
		inline static void destroy(T* p) { p->~T(); }
	};	//	end of class ObjectTraits

///////////////////////////////////////////////////////////////////////////
//	class StandardAllocPolicy
///////////////////////////////////////////////////////////////////////////

	//	a standard allocation policy using the free store
	template<typename T>
	class StandardAllocPolicy {
	public : 
		//	typedefs
		typedef T value_type;
		typedef value_type* pointer;
		typedef const value_type* const_pointer;
		typedef value_type& reference;
		typedef const value_type& const_reference;
		typedef std::size_t size_type;
		typedef std::ptrdiff_t difference_type;

	public : 
		//	convert an StandardAllocPolicy<T> to StandardAllocPolicy<U>
		template<typename U>
		struct rebind {
			typedef StandardAllocPolicy<U> other;
		};

	public : 
		inline explicit StandardAllocPolicy() {}
		inline ~StandardAllocPolicy() {}
		inline explicit StandardAllocPolicy(StandardAllocPolicy const&) {}
		template <typename U>
		inline explicit StandardAllocPolicy(StandardAllocPolicy<U> const&) {}

		//	memory allocation
		inline pointer allocate(size_type cnt, typename std::allocator<void>::const_pointer = 0) { return reinterpret_cast<pointer>(::operator new(cnt * sizeof (T))); }
		inline void deallocate(pointer p, size_type) { ::operator delete(p); }

		//	size
		inline size_type max_size() const { return std::numeric_limits<size_type>::max() / sizeof(T); }
	};	//	end of class StandardAllocPolicy

	//	determines if memory from another allocator can be deallocated from this one
	template<typename T, typename T2>
	inline bool operator==(StandardAllocPolicy<T> const&, StandardAllocPolicy<T2> const&) { 
		return true;
	}
	template<typename T, typename OtherAllocator>
	inline bool operator==(StandardAllocPolicy<T> const&, OtherAllocator const&) { 
		return false; 
	}

///////////////////////////////////////////////////////////////////////////
//	class FixedArrayAllocPolicy
///////////////////////////////////////////////////////////////////////////

	//	a fixed size array allocation policy
	//	should be used with vector only
	template<typename T, std::size_t numBlocks>
	class FixedArrayAllocPolicy {
	public : 
		//	typedefs
		typedef T value_type;
		typedef value_type* pointer;
		typedef const value_type* const_pointer;
		typedef value_type& reference;
		typedef const value_type& const_reference;
		typedef std::size_t size_type;
		typedef std::ptrdiff_t difference_type;

	public : 
		//	convert an FixedArrayAllocPolicy<T> to FixedArrayAllocPolicy<U>
		template<typename U>
		struct rebind {
			typedef FixedArrayAllocPolicy<U, numBlocks> other;
		};

	public : 
		inline explicit FixedArrayAllocPolicy() {}
		inline ~FixedArrayAllocPolicy() {}
		inline explicit FixedArrayAllocPolicy(FixedArrayAllocPolicy const&) {}
		template <typename U, std::size_t N2>
		inline explicit FixedArrayAllocPolicy(FixedArrayAllocPolicy<U, N2> const&) {}

		//	memory allocation
		inline pointer allocate(size_type cnt, typename std::allocator<void>::const_pointer = 0) { 
			return reinterpret_cast<pointer>(this->data_); 
		}
		inline void deallocate(pointer p, size_type) {}

		//	size
		inline size_type max_size() const { return numBlocks; }

	private : 
		T data_[numBlocks];
	};	//	end of class FixedArrayAllocPolicy

	//	determines if memory from another allocator can be deallocated from this one
	template<typename T, std::size_t N, typename T2, std::size_t N2>
	inline bool operator==(FixedArrayAllocPolicy<T, N> const&, FixedArrayAllocPolicy<T2, N2> const&) { 
		return false;
	}
	template<typename T, std::size_t N, typename OtherAllocator>
	inline bool operator==(FixedArrayAllocPolicy<T, N> const&, OtherAllocator const&) { 
		return false; 
	}

///////////////////////////////////////////////////////////////////////////
//	class SmallObjectAllocPolicy
///////////////////////////////////////////////////////////////////////////

	//	an allocator specialized for small object allocation
	//	using Loki's SmallObjAllocator
	template<typename T, std::size_t numBlocks = 64>
	class SmallObjectAllocPolicy {
	public : 
		//	typedefs
		typedef T value_type;
		typedef value_type* pointer;
		typedef const value_type* const_pointer;
		typedef value_type& reference;
		typedef const value_type& const_reference;
		typedef std::size_t size_type;
		typedef std::ptrdiff_t difference_type;

	public : 
		//	convert an SmallObjectAllocPolicy<T> to SmallObjectAllocPolicy<U>
		template<typename U>
		struct rebind {
			typedef SmallObjectAllocPolicy<U, numBlocks> other;
		};

	public : 
		inline explicit SmallObjectAllocPolicy() {}
		inline ~SmallObjectAllocPolicy() {}
		inline explicit SmallObjectAllocPolicy(SmallObjectAllocPolicy const&) {}
		template <typename T2, std::size_t N2>
		inline explicit SmallObjectAllocPolicy(SmallObjectAllocPolicy<T2, N2> const&) {}

		//	memory allocation
		inline pointer allocate(size_type cnt, typename std::allocator<void>::const_pointer = 0) {
			return reinterpret_cast<T*>(allocator_.Allocate(sizeof(T) * cnt));
		}
		inline void deallocate(pointer p, size_type cnt) {
			allocator_.Deallocate(p, sizeof(T) * cnt);
		}

		//	size
		inline size_type max_size() const { return std::numeric_limits<size_type>::max() / sizeof(T); }

	private:
		static Loki::SmallObjAllocator allocator_;
	};	//	end of class SmallObjectAllocPolicy

	//	optimized for single small object, hence chunk size and max object size is small
	//	otherwise using free store
	template<typename T, std::size_t numBlocks>
	Loki::SmallObjAllocator SmallObjectAllocPolicy<T, numBlocks>::allocator_(numBlocks * sizeof(T), sizeof(T));

	//	determines if memory from another allocator can be deallocated from this one
	template<typename T, std::size_t N>
	inline bool operator==(SmallObjectAllocPolicy<T, N> const&, SmallObjectAllocPolicy<T, N> const&) { 
		return true;
	}
	template<typename T, std::size_t N, typename T2, std::size_t N2>
	inline bool operator==(SmallObjectAllocPolicy<T, N> const&, SmallObjectAllocPolicy<T2, N2> const&) { 
		return false;
	}
	template<typename T, std::size_t N, typename OtherAllocator>
	inline bool operator==(SmallObjectAllocPolicy<T, N> const&, OtherAllocator const&) { 
		return false; 
	}

///////////////////////////////////////////////////////////////////////////
//	class TrackAllocPolicy
///////////////////////////////////////////////////////////////////////////

	//	an allocation policy that keeps track of memory usage
	template<typename T, typename Policy = StandardAllocPolicy<T> >
	class TrackAllocPolicy : public Policy {
	private : 
		typedef Policy AllocationPolicy;

	public : 
		//	convert an TrackAllocPolicy<T> to TrackAllocPolicy<U>
		template<typename U>
		struct rebind {
			typedef TrackAllocPolicy<U, typename AllocationPolicy::rebind<U>::other> other;
		};

	public : 
		inline explicit TrackAllocPolicy():total_(0), current_(0), peak_(0) {}
		inline ~TrackAllocPolicy() {}
		inline explicit TrackAllocPolicy(TrackAllocPolicy const& rhs):Policy(rhs), total_(rhs.total_), current_(rhs.current_), peak_(rhs.peak_) {}
		template <typename U>
		inline explicit TrackAllocPolicy(TrackAllocPolicy<U> const& rhs):Policy(rhs), total_(0), current_(0), peak_(0) {}

		//	memory allocation
		typename AllocationPolicy::pointer allocate(typename AllocationPolicy::size_type cnt, typename std::allocator<void>::const_pointer hint = 0) { 
			typename AllocationPolicy::pointer p = AllocationPolicy::allocate(cnt, hint);
			this->total_ += cnt;
			this->current_ += cnt;
			if ( this->current_ > this->peak_ ) {
				this->peak_ = this->current_;
			}
			return p;
		}
		inline void deallocate(typename AllocationPolicy::pointer p, typename AllocationPolicy::size_type cnt) { 
			AllocationPolicy::deallocate(p, cnt);
			this->current_ -= cnt;
		}

		// get stats
		inline typename AllocationPolicy::size_type TotalAllocations() { return this->total_; }
		inline typename AllocationPolicy::size_type CurrentAllocations() { return this->current_; }
		inline typename AllocationPolicy::size_type PeakAllocations() { return this->peak_; }

	private : 
		typename AllocationPolicy::size_type total_;	//	total allocations
		typename AllocationPolicy::size_type current_;	//	current allocations
		typename AllocationPolicy::size_type peak_;	//	peak allocations
	};	//	end of class TrackAllocPolicy

	//	determines if memory from another allocator can be deallocated from this one
	template<typename T, typename Policy, typename T2, typename Policy2>
	inline bool operator==(TrackAllocPolicy<T, Policy> const& lhs, TrackAllocPolicy<T2, Policy2> const& rhs) { 
		return operator==(static_cast<Policy&>(lhs), static_cast<Policy&>(rhs)); 
	}
	template<typename T, typename Policy, typename OtherAllocator>
	inline bool operator==(TrackAllocPolicy<T, Policy> const& lhs, OtherAllocator const& rhs) { 
		return operator==(static_cast<Policy&>(lhs), rhs); 
	}

///////////////////////////////////////////////////////////////////////////
//	class Allocator
///////////////////////////////////////////////////////////////////////////

	//	Policy driven allocator object
	template<typename T, typename Policy = StandardAllocPolicy<T>, typename Traits = ObjectTraits<T> >
	class Allocator : public Policy, public Traits {
	private : 
		typedef Policy AllocationPolicy;
		typedef Traits TTraits;

	public : 
		typedef typename AllocationPolicy::size_type size_type;
		typedef typename AllocationPolicy::difference_type difference_type;
		typedef typename AllocationPolicy::pointer pointer;
		typedef typename AllocationPolicy::const_pointer const_pointer;
		typedef typename AllocationPolicy::reference reference;
		typedef typename AllocationPolicy::const_reference const_reference;
		typedef typename AllocationPolicy::value_type value_type;

	public : 
		template<typename U>
		struct rebind {
			typedef Allocator<U, typename AllocationPolicy::rebind<U>::other> other;
		};

	public : 
		inline explicit Allocator() {}
		inline ~Allocator() {}
		inline Allocator(Allocator const& rhs):Traits(rhs), Policy(rhs) {}
		template <typename U>
		inline explicit Allocator(Allocator<U> const&) {}
		template <typename U, typename P, typename T2>
		inline Allocator(Allocator<U, P, T2> const& rhs):Traits(rhs), Policy(rhs) {}

		//	memory allocation
		inline pointer allocate(size_type cnt, typename std::allocator<void>::const_pointer hint = 0) { 
			return AllocationPolicy::allocate(cnt, hint);
		}
		inline void deallocate(pointer p, size_type cnt) { 
			AllocationPolicy::deallocate(p, cnt);
		}
	};	//	end of class Allocator

	//	determines if memory from another allocator can be deallocated from this one
	template<typename T, typename P, typename Tr>
	inline bool operator==(Allocator<T, P, Tr> const& lhs, Allocator<T, P, Tr> const& rhs) { 
		return operator==(static_cast<P&>(lhs), static_cast<P&>(rhs)); 
	}
	template<typename T, typename P, typename Tr, typename T2, typename P2, typename Tr2>
	inline bool operator==(Allocator<T, P, Tr> const& lhs, Allocator<T2, P2, Tr2> const& rhs) { 
		return operator==(static_cast<P&>(lhs), static_cast<P2&>(rhs)); 
	}
	template<typename T, typename P, typename Tr, typename OtherAllocator>
	inline bool operator==(Allocator<T, P, Tr> const& lhs, OtherAllocator const& rhs) { 
		return operator==(static_cast<P&>(lhs), rhs); 
	}
	template<typename T, typename P, typename Tr>
	inline bool operator!=(Allocator<T, P, Tr> const& lhs, Allocator<T, P, Tr> const& rhs) { 
		return !operator==(lhs, rhs); 
	}
	template<typename T, typename P, typename Tr, typename T2, typename P2, typename Tr2>
	inline bool operator!=(Allocator<T, P, Tr> const& lhs, Allocator<T2, P2, Tr2> const& rhs) { 
		return !operator==(lhs, rhs); 
	}
	template<typename T, typename P, typename Tr, typename OtherAllocator>
	inline bool operator!=(Allocator<T, P, Tr> const& lhs, OtherAllocator const& rhs) { 
		return !operator==(lhs, rhs); 
	}

};	//	end of namespace Dot

#endif // allocator_hpp_e1184f45_01e5_4089_b02d_d6f41dcf1192
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.
License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)
Written By
Lai Shiaw San Kent
Web Developer
Singapore
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.
C++ Standard Allocator, An Introduction and Implementation

License

Comments and Discussions
