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-1335  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   /// Convenience typedef, same typedef name as std::vector
51   typedef Element_type value_type;
52 
Mem_root_array(MEM_ROOT * root)53   Mem_root_array(MEM_ROOT *root)
54     : m_root(root), m_array(NULL), m_size(0), m_capacity(0)
55   {
56     DBUG_ASSERT(m_root != NULL);
57   }
58 
59   Mem_root_array(MEM_ROOT *root, size_t n, const value_type &val= value_type())
m_root(root)60     : m_root(root), m_array(NULL), m_size(0), m_capacity(0)
61   {
62     resize(n, val);
63   }
64 
~Mem_root_array()65   ~Mem_root_array()
66   {
67     clear();
68   }
69 
at(size_t n)70   Element_type &at(size_t n)
71   {
72     DBUG_ASSERT(n < size());
73     return m_array[n];
74   }
75 
at(size_t n)76   const Element_type &at(size_t n) const
77   {
78     DBUG_ASSERT(n < size());
79     return m_array[n];
80   }
81 
82   Element_type &operator[](size_t n) { return at(n); }
83   const Element_type &operator[](size_t n) const { return at(n); }
84 
back()85   Element_type &back() { return at(size() - 1); }
back()86   const Element_type &back() const { return at(size() - 1); }
87 
88   // Returns a pointer to the first element in the array.
begin()89   Element_type *begin() { return &m_array[0]; }
90 
91   // Returns a pointer to the past-the-end element in the array.
end()92   Element_type *end() { return &m_array[size()]; }
93 
94   // Erases all of the elements.
clear()95   void clear()
96   {
97     if (!empty())
98       chop(0);
99   }
100 
101   /*
102     Chops the tail off the array, erasing all tail elements.
103     @param pos Index of first element to erase.
104   */
chop(const size_t pos)105   void chop(const size_t pos)
106   {
107     DBUG_ASSERT(pos < m_size);
108     if (!has_trivial_destructor)
109     {
110       for (size_t ix= pos; ix < m_size; ++ix)
111       {
112         Element_type *p= &m_array[ix];
113         p->~Element_type();              // Destroy discarded element.
114       }
115     }
116     m_size= pos;
117   }
118 
119   /*
120     Reserves space for array elements.
121     Copies over existing elements, in case we are re-expanding the array.
122 
123     @param  n number of elements.
124     @retval true if out-of-memory, false otherwise.
125   */
reserve(size_t n)126   bool reserve(size_t n)
127   {
128     if (n <= m_capacity)
129       return false;
130 
131     void *mem= alloc_root(m_root, n * element_size());
132     if (!mem)
133       return true;
134     Element_type *array= static_cast<Element_type*>(mem);
135 
136     // Copy all the existing elements into the new array.
137     for (size_t ix= 0; ix < m_size; ++ix)
138     {
139       Element_type *new_p= &array[ix];
140       Element_type *old_p= &m_array[ix];
141       new (new_p) Element_type(*old_p);         // Copy into new location.
142       if (!has_trivial_destructor)
143         old_p->~Element_type();                 // Destroy the old element.
144     }
145 
146     // Forget the old array.
147     m_array= array;
148     m_capacity= n;
149     return false;
150   }
151 
152   /*
153     Adds a new element at the end of the array, after its current last
154     element. The content of this new element is initialized to a copy of
155     the input argument.
156 
157     @param  element Object to copy.
158     @retval true if out-of-memory, false otherwise.
159   */
push_back(const Element_type & element)160   bool push_back(const Element_type &element)
161   {
162     const size_t min_capacity= 20;
163     const size_t expansion_factor= 2;
164     if (0 == m_capacity && reserve(min_capacity))
165       return true;
166     if (m_size == m_capacity && reserve(m_capacity * expansion_factor))
167       return true;
168     Element_type *p= &m_array[m_size++];
169     new (p) Element_type(element);
170     return false;
171   }
172 
173   /**
174     Removes the last element in the array, effectively reducing the
175     container size by one. This destroys the removed element.
176    */
pop_back()177   void pop_back()
178   {
179     DBUG_ASSERT(!empty());
180     if (!has_trivial_destructor)
181       back().~Element_type();
182     m_size-= 1;
183   }
184 
185   /**
186     Resizes the container so that it contains n elements.
187 
188     If n is smaller than the current container size, the content is
189     reduced to its first n elements, removing those beyond (and
190     destroying them).
191 
192     If n is greater than the current container size, the content is
193     expanded by inserting at the end as many elements as needed to
194     reach a size of n. If val is specified, the new elements are
195     initialized as copies of val, otherwise, they are
196     value-initialized.
197 
198     If n is also greater than the current container capacity, an automatic
199     reallocation of the allocated storage space takes place.
200 
201     Notice that this function changes the actual content of the
202     container by inserting or erasing elements from it.
203    */
204   void resize(size_t n, const value_type &val= value_type())
205   {
206     if (n == m_size)
207       return;
208     if (n > m_size)
209     {
210       if (!reserve(n))
211       {
212         while (n != m_size)
213           push_back(val);
214       }
215       return;
216     }
217     if (!has_trivial_destructor)
218     {
219       while (n != m_size)
220         pop_back();
221     }
222     m_size= n;
223   }
224 
capacity()225   size_t capacity()     const { return m_capacity; }
element_size()226   size_t element_size() const { return sizeof(Element_type); }
empty()227   bool   empty()        const { return size() == 0; }
size()228   size_t size()         const { return m_size; }
229 
230 private:
231   MEM_ROOT *const m_root;
232   Element_type   *m_array;
233   size_t          m_size;
234   size_t          m_capacity;
235 
236   // Not (yet) implemented.
237   Mem_root_array(const Mem_root_array&);
238   Mem_root_array &operator=(const Mem_root_array&);
239 };
240 
241 
242 #endif  // MEM_ROOT_ARRAY_INCLUDED
243