1/* Copyright (c) 2000, 2010, 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 St, Fifth Floor, Boston, MA 02110-1301 USA */
15
16/* Handling of arrays that can grow dynamicly. */
17
18#include "mysys_priv.h"
19#include "m_string.h"
20
21/*
22 Initiate dynamic array
23
24 SYNOPSIS
25 init_dynamic_array2()
26 array Pointer to an array
27 element_size Size of element
28 init_buffer Initial buffer pointer
29 init_alloc Number of initial elements
30 alloc_increment Increment for adding new elements
31 my_flags Flags to my_malloc
32
33 DESCRIPTION
34 init_dynamic_array() initiates array and allocate space for
35 init_alloc eilements.
36 Array is usable even if space allocation failed, hence, the
37 function never returns TRUE.
38
39 RETURN VALUE
40 FALSE Ok
41*/
42
43my_bool init_dynamic_array2(DYNAMIC_ARRAY *array, uint element_size,
44 void *init_buffer, uint init_alloc,
45 uint alloc_increment, myf my_flags)
46{
47 DBUG_ENTER("init_dynamic_array2");
48 if (!alloc_increment)
49 {
50 alloc_increment=MY_MAX((8192-MALLOC_OVERHEAD)/element_size,16);
51 if (init_alloc > 8 && alloc_increment > init_alloc * 2)
52 alloc_increment=init_alloc*2;
53 }
54 array->elements=0;
55 array->max_element=init_alloc;
56 array->alloc_increment=alloc_increment;
57 array->size_of_element=element_size;
58 array->malloc_flags= my_flags;
59 DBUG_ASSERT((my_flags & MY_INIT_BUFFER_USED) == 0);
60 if ((array->buffer= init_buffer))
61 {
62 array->malloc_flags|= MY_INIT_BUFFER_USED;
63 DBUG_RETURN(FALSE);
64 }
65 /*
66 Since the dynamic array is usable even if allocation fails here malloc
67 should not throw an error
68 */
69 if (init_alloc &&
70 !(array->buffer= (uchar*) my_malloc(element_size*init_alloc,
71 MYF(my_flags))))
72 array->max_element=0;
73 DBUG_RETURN(FALSE);
74}
75
76/*
77 Insert element at the end of array. Allocate memory if needed.
78
79 SYNOPSIS
80 insert_dynamic()
81 array
82 element
83
84 RETURN VALUE
85 TRUE Insert failed
86 FALSE Ok
87*/
88
89my_bool insert_dynamic(DYNAMIC_ARRAY *array, const void * element)
90{
91 void *buffer;
92 if (array->elements == array->max_element)
93 { /* Call only when necessary */
94 if (!(buffer=alloc_dynamic(array)))
95 return TRUE;
96 }
97 else
98 {
99 buffer=array->buffer+(array->elements * array->size_of_element);
100 array->elements++;
101 }
102 memcpy(buffer,element,(size_t) array->size_of_element);
103 return FALSE;
104}
105
106
107/*
108 Alloc space for next element(s)
109
110 SYNOPSIS
111 alloc_dynamic()
112 array
113
114 DESCRIPTION
115 alloc_dynamic() checks if there is empty space for at least
116 one element if not tries to allocate space for alloc_increment
117 elements at the end of array.
118
119 RETURN VALUE
120 pointer Pointer to empty space for element
121 0 Error
122*/
123
124void *alloc_dynamic(DYNAMIC_ARRAY *array)
125{
126 DBUG_ENTER("alloc_dynamic");
127 if (array->elements == array->max_element)
128 {
129 char *new_ptr;
130 if (array->malloc_flags & MY_INIT_BUFFER_USED)
131 {
132 /*
133 In this scenario, the buffer is statically preallocated,
134 so we have to create an all-new malloc since we overflowed
135 */
136 if (!(new_ptr= (char *) my_malloc((array->max_element+
137 array->alloc_increment) *
138 array->size_of_element,
139 MYF(array->malloc_flags | MY_WME))))
140 DBUG_RETURN(0);
141 memcpy(new_ptr, array->buffer,
142 array->elements * array->size_of_element);
143 array->malloc_flags&= ~MY_INIT_BUFFER_USED;
144 }
145 else if (!(new_ptr=(char*)
146 my_realloc(array->buffer,(array->max_element+
147 array->alloc_increment)*
148 array->size_of_element,
149 MYF(MY_WME | MY_ALLOW_ZERO_PTR |
150 array->malloc_flags))))
151 DBUG_RETURN(0);
152 array->buffer= (uchar*) new_ptr;
153 array->max_element+=array->alloc_increment;
154 }
155 DBUG_RETURN(array->buffer+(array->elements++ * array->size_of_element));
156}
157
158
159/*
160 Pop last element from array.
161
162 SYNOPSIS
163 pop_dynamic()
164 array
165
166 RETURN VALUE
167 pointer Ok
168 0 Array is empty
169*/
170
171void *pop_dynamic(DYNAMIC_ARRAY *array)
172{
173 if (array->elements)
174 return array->buffer+(--array->elements * array->size_of_element);
175 return 0;
176}
177
178/*
179 Replace element in array with given element and index
180
181 SYNOPSIS
182 set_dynamic()
183 array
184 element Element to be inserted
185 idx Index where element is to be inserted
186
187 DESCRIPTION
188 set_dynamic() replaces element in array.
189 If idx > max_element insert new element. Allocate memory if needed.
190
191 RETURN VALUE
192 TRUE Idx was out of range and allocation of new memory failed
193 FALSE Ok
194*/
195
196my_bool set_dynamic(DYNAMIC_ARRAY *array, const void *element, uint idx)
197{
198 if (idx >= array->elements)
199 {
200 if (idx >= array->max_element && allocate_dynamic(array, idx))
201 return TRUE;
202 bzero((uchar*) (array->buffer+array->elements*array->size_of_element),
203 (idx - array->elements)*array->size_of_element);
204 array->elements=idx+1;
205 }
206 memcpy(array->buffer+(idx * array->size_of_element),element,
207 (size_t) array->size_of_element);
208 return FALSE;
209}
210
211
212/*
213 Ensure that dynamic array has enough elements
214
215 SYNOPSIS
216 allocate_dynamic()
217 array
218 max_elements Numbers of elements that is needed
219
220 NOTES
221 Any new allocated element are NOT initialized
222
223 RETURN VALUE
224 FALSE Ok
225 TRUE Allocation of new memory failed
226*/
227
228my_bool allocate_dynamic(DYNAMIC_ARRAY *array, uint max_elements)
229{
230 DBUG_ENTER("allocate_dynamic");
231
232 if (max_elements >= array->max_element)
233 {
234 uint size;
235 uchar *new_ptr;
236 size= (max_elements + array->alloc_increment)/array->alloc_increment;
237 size*= array->alloc_increment;
238 if (array->malloc_flags & MY_INIT_BUFFER_USED)
239 {
240 /*
241 In this senerio, the buffer is statically preallocated,
242 so we have to create an all-new malloc since we overflowed
243 */
244 if (!(new_ptr= (uchar *) my_malloc(size *
245 array->size_of_element,
246 MYF(array->malloc_flags | MY_WME))))
247 DBUG_RETURN(0);
248 memcpy(new_ptr, array->buffer,
249 array->elements * array->size_of_element);
250 array->malloc_flags&= ~MY_INIT_BUFFER_USED;
251 }
252 else if (!(new_ptr= (uchar*) my_realloc(array->buffer,size*
253 array->size_of_element,
254 MYF(MY_WME | MY_ALLOW_ZERO_PTR |
255 array->malloc_flags))))
256 DBUG_RETURN(TRUE);
257 array->buffer= new_ptr;
258 array->max_element= size;
259 }
260 DBUG_RETURN(FALSE);
261}
262
263
264/*
265 Get an element from array by given index
266
267 SYNOPSIS
268 get_dynamic()
269 array
270 uchar* Element to be returned. If idx > elements contain zeroes.
271 idx Index of element wanted.
272*/
273
274void get_dynamic(DYNAMIC_ARRAY *array, void *element, uint idx)
275{
276 if (idx >= array->elements)
277 {
278 DBUG_PRINT("warning",("To big array idx: %d, array size is %d",
279 idx,array->elements));
280 bzero(element,array->size_of_element);
281 return;
282 }
283 memcpy(element,array->buffer+idx*array->size_of_element,
284 (size_t) array->size_of_element);
285}
286
287
288/*
289 Empty array by freeing all memory
290
291 SYNOPSIS
292 delete_dynamic()
293 array Array to be deleted
294*/
295
296void delete_dynamic(DYNAMIC_ARRAY *array)
297{
298 /*
299 Just mark as empty if we are using a static buffer
300 */
301 if (!(array->malloc_flags & MY_INIT_BUFFER_USED) && array->buffer)
302 my_free(array->buffer);
303
304 array->buffer= 0;
305 array->elements= array->max_element= 0;
306}
307
308/*
309 Delete element by given index
310
311 SYNOPSIS
312 delete_dynamic_element()
313 array
314 idx Index of element to be deleted
315*/
316
317void delete_dynamic_element(DYNAMIC_ARRAY *array, uint idx)
318{
319 char *ptr= (char*) array->buffer+array->size_of_element*idx;
320 array->elements--;
321 memmove(ptr,ptr+array->size_of_element,
322 (array->elements-idx)*array->size_of_element);
323}
324
325/*
326 Wrapper around delete_dynamic, calling a FREE function on every
327 element, before releasing the memory
328
329 SYNOPSIS
330 delete_dynamic_with_callback()
331 array
332 f The function to be called on every element before
333 deleting the array;
334*/
335void delete_dynamic_with_callback(DYNAMIC_ARRAY *array, FREE_FUNC f) {
336 uint i;
337 char *ptr= (char*) array->buffer;
338 for (i= 0; i < array->elements; i++, ptr+= array->size_of_element) {
339 f(ptr);
340 }
341 delete_dynamic(array);
342}
343/*
344 Free unused memory
345
346 SYNOPSIS
347 freeze_size()
348 array Array to be freed
349
350*/
351
352void freeze_size(DYNAMIC_ARRAY *array)
353{
354 uint elements;
355
356 /*
357 Do nothing if we are using a static buffer
358 */
359 if (array->malloc_flags & MY_INIT_BUFFER_USED)
360 return;
361
362 elements= MY_MAX(array->elements, 1);
363 if (array->buffer && array->max_element > elements)
364 {
365 array->buffer=(uchar*) my_realloc(array->buffer,
366 elements*array->size_of_element,
367 MYF(MY_WME | array->malloc_flags));
368 array->max_element= elements;
369 }
370}
371
372#ifdef NOT_USED
373/*
374 Get the index of a dynamic element
375
376 SYNOPSIS
377 get_index_dynamic()
378 array Array
379 element Whose element index
380
381*/
382
383int get_index_dynamic(DYNAMIC_ARRAY *array, void* element)
384{
385 size_t ret;
386 if (array->buffer > (uchar*) element)
387 return -1;
388
389 ret= ((uchar*) element - array->buffer) / array->size_of_element;
390 if (ret > array->elements)
391 return -1;
392
393 return ret;
394
395}
396#endif
397