WL#6074: Memroot allocator for C++ STL

Affects: Server-5.7   —   Status: Complete

An allocator is used to insulate C++ Standard Library algorithms and containers
that must allocate memory from the details of physical memory. The standard
library comes with an allocator which uses the heap (or freestore)

This worklog will implement two allocators:
1) One that takes memory from a MySQL MEM_ROOT
2) One that uses heap (via my_malloc/my_free).

The latter is important for GIS/Boost as it allows for Performance Schema
tracking of memory usage.

User Documentation

None required.
NF-1: This worklog will in itself not make any changes to server behavior.
It will only add two STL memory allocator + unit test coverage.
Currently, MEM_ROOT cannot de-allocate memory chunks.
This somewhat limits the applicability of a MEM_ROOT based allocator.
It would still be useful to allocate e.g. vectors, lists, etc. in MEM_ROOT,
and to be able to use standard algorithms (e.g. find, sort, ...) on them.

Descriptions of allocators, how to implement, how to use, are found several
places on the web:


matt austern, Dr.Dobb's, December 2000

codeguru, February 2004, VC++6.0, gcc3.2, stlport4
nice, step-by-step "cookbook", with workarounds for VC++6.0

codeproject, Aug 2003

C++ Language Library:
The public interface is described by the ISO C++ standard, section 20.4.1:

  namespace std {
    template  class allocator;

    // specialize for void:
    template <> class allocator {
      typedef void*       pointer;
      typedef const void* const_pointer;
      // reference to void members are impossible.
      typedef void value_type;
      template  struct rebind { typedef allocator
                                         other; };

    template  class allocator {
      typedef size_t    size_type;
      typedef ptrdiff_t difference_type;
      typedef T*        pointer;
      typedef const T*  const_pointer;
      typedef T&        reference;
      typedef const T&  const_reference;
      typedef T         value_type;
      template  struct rebind { typedef allocator
                                         other; };

      allocator() throw();
      allocator(const allocator&) throw();
      template  allocator(const allocator&) throw();
      ~allocator() throw();

      pointer address(reference x) const;
      const_pointer address(const_reference x) const;

      pointer allocate(size_type,
                       allocator::const_pointer hint = 0);
      void deallocate(pointer p, size_type n);
      size_type max_size() const throw();

      void construct(pointer p, const T& val);
      void destroy(pointer p);
In addition to that, the following two global functions belong to it as well:

  bool operator==(const allocator&, const allocator&)

  bool operator!=(const allocator&, const allocator&)

The memroot allocator needs to keep a pointer to its MEM_ROOT, 
and use alloc_root() in the allocate() member function.

The my_alloc/my_free allocator needs to remember the PSI_memory_key to
allow for Performance Schema tracking.

So both allocators will be stateful and lack a default constructor.
This means that they cannot be used for std::basic_string due to this libstd++
bug: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56437
"basic_string assumes that allocators are default-constructible"