The Standard Librarian: A Debugging Allocator

Listing 1: Complete implementation of the debugging allocator

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;
}