release/src/router/mysql/sql/mem_root_array.h

   1 /* Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved.
   2
   3    This program is free software; you can redistribute it and/or modify
   4    it under the terms of the GNU General Public License as published by
   5    the Free Software Foundation; version 2 of the License.
   6
   7    This program is distributed in the hope that it will be useful,
   8    but WITHOUT ANY WARRANTY; without even the implied warranty of
   9    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10    GNU General Public License for more details.
  11
  12    You should have received a copy of the GNU General Public License
  13    along with this program; if not, write to the Free Software
  14    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA */
  15
  16
  17 #ifndef MEM_ROOT_ARRAY_INCLUDED
  18 #define MEM_ROOT_ARRAY_INCLUDED
  19
  20 #include <my_alloc.h>
  21
  22 /**
  23    A typesafe replacement for DYNAMIC_ARRAY.
  24    We use MEM_ROOT for allocating storage, rather than the C++ heap.
  25    The interface is chosen to be similar to std::vector.
  26
  27    @remark
  28    Unlike DYNAMIC_ARRAY, elements are properly copied
  29    (rather than memcpy()d) if the underlying array needs to be expanded.
  30
  31    @remark
  32    Depending on has_trivial_destructor, we destroy objects which are
  33    removed from the array (including when the array object itself is destroyed).
  34
  35    @remark
  36    Note that MEM_ROOT has no facility for reusing free space,
  37    so don't use this if multiple re-expansions are likely to happen.
  38
  39    @param Element_type The type of the elements of the container.
  40           Elements must be copyable.
  41    @param has_trivial_destructor If true, we don't destroy elements.
  42           We could have used type traits to determine this.
  43           __has_trivial_destructor is supported by some (but not all)
  44           compilers we use.
  45 */
  46 template<typename Element_type, bool has_trivial_destructor>
  47 class Mem_root_array
  48 {
  49 public:
  50   Mem_root_array(MEM_ROOT *root)
  51     : m_root(root), m_array(NULL), m_size(0), m_capacity(0)
  52   {
  53     DBUG_ASSERT(m_root != NULL);
  54   }
  55
  56   ~Mem_root_array()
  57   {
  58     clear();
  59   }
  60
  61   Element_type &at(size_t n)
  62   {
  63     DBUG_ASSERT(n < size());
  64     return m_array[n];
  65   }
  66
  67   const Element_type &at(size_t n) const
  68   {
  69     DBUG_ASSERT(n < size());
  70     return m_array[n];
  71   }
  72
  73   // Returns a pointer to the first element in the array.
  74   Element_type *begin() { return &m_array[0]; }
  75
  76   // Returns a pointer to the past-the-end element in the array.
  77   Element_type *end() { return &m_array[size()]; }
  78
  79   // Erases all of the elements.
  80   void clear()
  81   {
  82     if (!empty())
  83       chop(0);
  84   }
  85
  86   /*
  87     Chops the tail off the array, erasing all tail elements.
  88     @param pos Index of first element to erase.
  89   */
  90   void chop(const size_t pos)
  91   {
  92     DBUG_ASSERT(pos < m_size);
  93     if (!has_trivial_destructor)
  94     {
  95       for (size_t ix= pos; ix < m_size; ++ix)
  96       {
  97         Element_type *p= &m_array[ix];
  98         p->~Element_type();              // Destroy discarded element.
  99       }
 100     }
 101     m_size= pos;
 102   }
 103
 104   /*
 105     Reserves space for array elements.
 106     Copies over existing elements, in case we are re-expanding the array.
 107
 108     @param  n number of elements.
 109     @retval true if out-of-memory, false otherwise.
 110   */
 111   bool reserve(size_t n)
 112   {
 113     if (n <= m_capacity)
 114       return false;
 115
 116     void *mem= alloc_root(m_root, n * element_size());
 117     if (!mem)
 118       return true;
 119     Element_type *array= static_cast<Element_type*>(mem);
 120
 121     // Copy all the existing elements into the new array.
 122     for (size_t ix= 0; ix < m_size; ++ix)
 123     {
 124       Element_type *new_p= &array[ix];
 125       Element_type *old_p= &m_array[ix];
 126       new (new_p) Element_type(*old_p);         // Copy into new location.
 127       if (!has_trivial_destructor)
 128         old_p->~Element_type();                 // Destroy the old element.
 129     }
 130
 131     // Forget the old array.
 132     m_array= array;
 133     m_capacity= n;
 134     return false;
 135   }
 136
 137   /*
 138     Adds a new element at the end of the array, after its current last
 139     element. The content of this new element is initialized to a copy of
 140     the input argument.
 141
 142     @param  element Object to copy.
 143     @retval true if out-of-memory, false otherwise.
 144   */
 145   bool push_back(const Element_type &element)
 146   {
 147     const size_t min_capacity= 20;
 148     const size_t expansion_factor= 2;
 149     if (0 == m_capacity && reserve(min_capacity))
 150       return true;
 151     if (m_size == m_capacity && reserve(m_capacity * expansion_factor))
 152       return true;
 153     Element_type *p= &m_array[m_size++];
 154     new (p) Element_type(element);
 155     return false;
 156   }
 157
 158   size_t capacity()     const { return m_capacity; }
 159   size_t element_size() const { return sizeof(Element_type); }
 160   bool   empty()        const { return size() == 0; }
 161   size_t size()         const { return m_size; }
 162
 163 private:
 164   MEM_ROOT *const m_root;
 165   Element_type   *m_array;
 166   size_t          m_size;
 167   size_t          m_capacity;
 168
 169   // Not (yet) implemented.
 170   Mem_root_array(const Mem_root_array&);
 171   Mem_root_array &operator=(const Mem_root_array&);
 172 };
 173
 174
 175 #endif  // MEM_ROOT_ARRAY_INCLUDED