WL#6074: Memroot allocator for C++ STL

Affects: Server-5.7   —   Status: Complete   —   Priority: Medium

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:

wikipedia 
http://en.wikipedia.org/wiki/Allocator_(C%2B%2B)

matt austern, Dr.Dobb's, December 2000
http://drdobbs.com/article/print?articleId=184403759&siteSectionName=
http://drdobbs.com/cpp/184403759?pgno=2

codeguru, February 2004, VC++6.0, gcc3.2, stlport4
nice, step-by-step "cookbook", with workarounds for VC++6.0
http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4079

codeproject, Aug 2003
http://www.codeproject.com/KB/cpp/allocator.aspx

C++ Language Library:
http://www.cplusplus.com/reference
The public interface is described by the ISO C++ standard, section 20.4.1:

  namespace std {
    template <class T> class allocator;

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

    template <class T> class allocator {
    public:
      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 <class U> struct rebind { typedef allocator<U>
                                         other; };

      allocator() throw();
      allocator(const allocator&) throw();
      template <class U> allocator(const allocator<U>&) throw();
      ~allocator() throw();

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

      pointer allocate(size_type,
                       allocator<void>::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:

  template <class T1, class T2>
  bool operator==(const allocator<T1>&, const allocator<T2>&)
                  throw();

  template <class T1, class T2>
  bool operator!=(const allocator<T1>&, const allocator<T2>&)
                  throw();


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"