template <class Allocator, class T = typename Allocator::value_type>
class debug_allocator {
public: // Typedefs from underlying allocator.
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef typename Allocator::pointer pointer;
typedef typename Allocator::const_pointer const_pointer;
typedef typename Allocator::reference reference;
typedef typename Allocator::const_reference const_reference;
typedef typename Allocator::value_type value_type;
template <class U> struct rebind {
typedef typename Allocator::template rebind<U>::other A2;
typedef debug_allocator<A2, typename A2::value_type> other;
};
public: // Constructor, destructor, etc.
// Default constructor.
debug_allocator()
: alloc(), hash_code(0)
{ compute_hash(); }
// Constructor from an underlying allocator.
template <class Allocator2>
debug_allocator(const Allocator2& a)
: alloc(a), hash_code(0)
{ compute_hash(); }
// Copy constructor.
debug_allocator(const debug_allocator& a)
: alloc(a.alloc), hash_code(0)
{ compute_hash(); }
// Generalized copy constructor.
template <class A2, class T2>
debug_allocator(const debug_allocator<A2, T2>& a)
: alloc(a.alloc), hash_code(0)
{ compute_hash(); }
// Destructor.
~debug_allocator() {}
public: // Member functions.
// The only interesting ones
// are allocate and deallocate.
pointer allocate(size_type n, const void* = 0);
void deallocate(pointer p, size_type n);
pointer address(reference x) const { return a.address(x); }
const_pointer address(const_reference x) const {
return a.address(x);
}
void construct(pointer p, const value_type& x);
void destroy(pointer p);
size_type max_size() const { return a.max_size(); }
friend bool operator==(const debug_allocator& x,
const debug_allocator& y)
{ return x.alloc == y.alloc; }
friend bool operator!=(const debug_allocator& x,
const debug_allocator& y)
{ return x.alloc != y.alloc; }
private:
typedef typename Allocator::template rebind<char>::other
char_alloc;
typedef typename Allocator::template rebind<std::size_t>::other
size_alloc;
// Calculate the hash code, and store it in this->hash_code.
// Only used in the constructor.
void compute_hash();
const char* hash_code_as_bytes()
{ return reinterpret_cast<const char*>(&hash_code); }
// Number of bytes required to store n objects of type value_type.
// Does not include the overhead for debugging.
size_type data_size(size_type n)
{ return n * sizeof(value_type); }
// Number of bytes allocated in front of the user-visible memory
// block. Must be large enough to store two objects of type
// size_t, and to preserve alignment.
size_type padding_before(size_type)
{ return 2 * sizeof(std::size_t); }
// Number of bytes from the beginning of the block we allocate
// until the beginning of the sentinel.
size_type sentinel_offset(size_type n)
{ return data_size(n) + padding_before(n); }
// Number of bytes in the sentinel.
size_type sentinel_size()
{ return sizeof(std::size_t); }
// Size of the area we allocate to store n objects,
// including overhead.
size_type total_bytes(size_type n)
{ return data_size(n) + padding_before(n) + sentinel_size(); }
Allocator alloc;
std::size_t hash_code;
};
// Specialization when the value type is void. We provide typedefs
// (and not even all of those), and we save the underlying allocator
// so we can convert back to some other type.
template <class Allocator>
class debug_allocator<Allocator, void> {
public:
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef typename Allocator::pointer pointer;
typedef typename Allocator::const_pointer const_pointer;
typedef typename Allocator::value_type value_type;
template <class U> struct rebind {
typedef typename Allocator::template rebind<U>::other A2;
typedef debug_allocator<A2, typename A2::value_type> other;
};
debug_allocator() : alloc() { }
template <class A2>
debug_allocator(const A2& a) : alloc(a) { }
debug_allocator(const debug_allocator& a) : alloc(a.alloc) { }
template <class A2, class T2>
debug_allocator(const debug_allocator<A2, T2>& a) :
alloc(a.alloc) { }
~debug_allocator() {}
private:
Allocator alloc;
};
// Noninline member functions for debug_allocator. They are not defined
// for the void specialization.
template <class Allocator, class T>
typename debug_allocator<Allocator, T>::pointer
debug_allocator<Allocator, T>::allocate
(size_type n, const void* = 0) {
assert(n != 0);
// Allocate enough space for n objects of type T, plus the debug
// info at the beginning, plus a one-byte sentinel at the end.
typedef typename char_alloc::pointer char_pointer;
typedef typename size_alloc::pointer size_pointer;
char_pointer result = char_alloc(alloc).allocate(total_bytes(n));
// Store the size.
size_pointer debug_area = size_pointer(result);
size_alloc(alloc).construct(debug_area + 0, n);
// Store a hash code based on the type name.
size_alloc(alloc).construct(debug_area + 1, hash_code);
// Store the sentinel, which is just the hash code again.
// For reasons of alignment, we have to copy it byte by byte.
typename char_alloc::pointer sentinel_area =
result + sentinel_offset(n);
const char* sentinel = hash_code_as_bytes();
{
char_alloc ca(alloc);
int i = 0;
try {
for ( ; i < sentinel_size(); ++i)
ca.construct(sentinel_area + i, sentinel[i]);
}
catch(...) {
for (int j = 0; j < i; ++j)
ca.destroy(&*(sentinel_area + j));
throw;
}
}
// Return a pointer to the user-visible portion of the memory.
pointer data_area = pointer(result + padding_before(n));
return data_area;
}
template <class Allocator, class T>
void debug_allocator<Allocator, T>::deallocate
(pointer p, size_type n) {
assert(n != 0);
// Get a pointer to the space where we put the debugging information.
typedef typename char_alloc::pointer char_pointer;
typedef typename size_alloc::pointer size_pointer;
char_pointer cp = char_pointer(p);
size_pointer debug_area = size_pointer(cp - padding_before(n));
// Get the size request and the hash code, and check for consistency.
size_t stored_n = debug_area[0];
size_t stored_hash = debug_area[1];
assert(n == stored_n);
assert(hash_code == stored_hash);
// Get the sentinel, and check for consistency.
char_pointer sentinel_area =
char_pointer(debug_area) + sentinel_offset(n);
const char* sentinel = hash_code_as_bytes();
assert(std::equal(sentinel, sentinel + sentinel_size(),
sentinel_area));
// Destroy our debugging information.
size_alloc(alloc).destroy(debug_area + 0);
size_alloc(alloc).destroy(debug_area + 1);
for (size_type i = 0; i < sentinel_size(); ++i)
char_alloc(alloc).destroy(sentinel_area + i);
// Release the storage.
char_alloc(alloc).deallocate(cp - padding_before(n), total_bytes(n));
}
template <class Allocator, class T>
void debug_allocator<Allocator, T>::construct(pointer p, const
value_type& x)
{
assert(p);
a.construct(p, x);
}
template <class Allocator, class T>
void debug_allocator<Allocator, T>::destroy(pointer p)
{
assert(p);
a.destroy(p);
}
template <class Allocator, class T>
void debug_allocator<Allocator, T>::compute_hash() {
const char* name = typeid(value_type).name();
hash_code = 0;
for ( ; *name != '\0'; ++name)
hash_code = hash_code * (size_t) 37 + (size_t) *name;
}