diff options
Diffstat (limited to 'mysys/array.c')
| -rw-r--r-- | mysys/array.c | 378 |
1 files changed, 378 insertions, 0 deletions
diff --git a/mysys/array.c b/mysys/array.c new file mode 100644 index 00000000..6e871ee6 --- /dev/null +++ b/mysys/array.c @@ -0,0 +1,378 @@ +/* Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335 USA */ + +/* Handling of arrays that can grow dynamicly. */ + +#include "mysys_priv.h" +#include "m_string.h" + +/* + Initiate dynamic array + + SYNOPSIS + init_dynamic_array2() + ps_key Key to register instrumented memory + array Pointer to an array + element_size Size of element + init_buffer Initial buffer pointer + init_alloc Number of initial elements + alloc_increment Increment for adding new elements + my_flags Flags to my_malloc + + DESCRIPTION + init_dynamic_array() initiates array and allocate space for + init_alloc eilements. + Array is usable even if space allocation failed, hence, the + function never returns TRUE. + + RETURN VALUE + FALSE Ok +*/ + +my_bool init_dynamic_array2(PSI_memory_key psi_key, DYNAMIC_ARRAY *array, + size_t element_size, void *init_buffer, + size_t init_alloc, size_t alloc_increment, + myf my_flags) +{ + DBUG_ENTER("init_dynamic_array2"); + if (!alloc_increment) + { + alloc_increment=MY_MAX((8192-MALLOC_OVERHEAD)/element_size,16); + if (init_alloc > 8 && alloc_increment > init_alloc * 2) + alloc_increment=init_alloc*2; + } + array->elements=0; + array->max_element=init_alloc; + array->alloc_increment=alloc_increment; + array->size_of_element=element_size; + array->m_psi_key= psi_key; + array->malloc_flags= my_flags; + DBUG_ASSERT((my_flags & MY_INIT_BUFFER_USED) == 0); + if ((array->buffer= init_buffer)) + { + array->malloc_flags|= MY_INIT_BUFFER_USED; + DBUG_RETURN(FALSE); + } + /* + Since the dynamic array is usable even if allocation fails here malloc + should not throw an error + */ + if (init_alloc && + !(array->buffer= (uchar*) my_malloc(psi_key, element_size*init_alloc, + MYF(my_flags)))) + array->max_element=0; + DBUG_RETURN(FALSE); +} + +/* + Insert element at the end of array. Allocate memory if needed. + + SYNOPSIS + insert_dynamic() + array + element + + RETURN VALUE + TRUE Insert failed + FALSE Ok +*/ + +my_bool insert_dynamic(DYNAMIC_ARRAY *array, const void * element) +{ + void *buffer; + if (array->elements == array->max_element) + { /* Call only when necessary */ + if (!(buffer=alloc_dynamic(array))) + return TRUE; + } + else + { + buffer=array->buffer+(array->elements * array->size_of_element); + array->elements++; + } + memcpy(buffer,element,(size_t) array->size_of_element); + return FALSE; +} + + +/* + Alloc space for next element(s) + + SYNOPSIS + alloc_dynamic() + array + + DESCRIPTION + alloc_dynamic() checks if there is empty space for at least + one element if not tries to allocate space for alloc_increment + elements at the end of array. + + RETURN VALUE + pointer Pointer to empty space for element + 0 Error +*/ + +void *alloc_dynamic(DYNAMIC_ARRAY *array) +{ + DBUG_ENTER("alloc_dynamic"); + + DBUG_ASSERT(array->size_of_element); /* Ensure init() is called */ + if (array->elements == array->max_element) + { + char *new_ptr; + if (array->malloc_flags & MY_INIT_BUFFER_USED) + { + /* + In this scenario, the buffer is statically preallocated, + so we have to create an all-new malloc since we overflowed + */ + if (!(new_ptr= (char *) my_malloc(array->m_psi_key, + (array->max_element+ + array->alloc_increment) * + array->size_of_element, + MYF(array->malloc_flags | MY_WME)))) + DBUG_RETURN(0); + if (array->elements) + memcpy(new_ptr, array->buffer, + array->elements * array->size_of_element); + array->malloc_flags&= ~MY_INIT_BUFFER_USED; + } + else if (!(new_ptr=(char*) + my_realloc(array->m_psi_key, array->buffer, + (array->max_element+ array->alloc_increment) * + array->size_of_element, + MYF(MY_WME | MY_ALLOW_ZERO_PTR | + array->malloc_flags)))) + DBUG_RETURN(0); + array->buffer= (uchar*) new_ptr; + array->max_element+=array->alloc_increment; + } + DBUG_RETURN(array->buffer+(array->elements++ * array->size_of_element)); +} + + +/* + Pop last element from array. + + SYNOPSIS + pop_dynamic() + array + + RETURN VALUE + pointer Ok + 0 Array is empty +*/ + +void *pop_dynamic(DYNAMIC_ARRAY *array) +{ + if (array->elements) + return array->buffer+(--array->elements * array->size_of_element); + return 0; +} + +/* + Replace element in array with given element and index + + SYNOPSIS + set_dynamic() + array + element Element to be inserted + idx Index where element is to be inserted + + DESCRIPTION + set_dynamic() replaces element in array. + If idx > max_element insert new element. Allocate memory if needed. + + RETURN VALUE + TRUE Idx was out of range and allocation of new memory failed + FALSE Ok +*/ + +my_bool set_dynamic(DYNAMIC_ARRAY *array, const void *element, size_t idx) +{ + if (idx >= array->elements) + { + if (idx >= array->max_element && allocate_dynamic(array, idx)) + return TRUE; + bzero((uchar*) (array->buffer+array->elements*array->size_of_element), + (idx - array->elements)*array->size_of_element); + array->elements=idx+1; + } + memcpy(array->buffer+(idx * array->size_of_element),element, + array->size_of_element); + return FALSE; +} + + +/* + Ensure that dynamic array has enough elements + + SYNOPSIS + allocate_dynamic() + array + max_elements Numbers of elements that is needed + + NOTES + Any new allocated element are NOT initialized + + RETURN VALUE + FALSE Ok + TRUE Allocation of new memory failed +*/ + +my_bool allocate_dynamic(DYNAMIC_ARRAY *array, size_t max_elements) +{ + DBUG_ENTER("allocate_dynamic"); + + if (max_elements >= array->max_element) + { + size_t size; + uchar *new_ptr; + size= (max_elements + array->alloc_increment)/array->alloc_increment; + size*= array->alloc_increment; + if (array->malloc_flags & MY_INIT_BUFFER_USED) + { + /* + In this senerio, the buffer is statically preallocated, + so we have to create an all-new malloc since we overflowed + */ + if (!(new_ptr= (uchar *) my_malloc(array->m_psi_key, size * + array->size_of_element, + MYF(array->malloc_flags | MY_WME)))) + DBUG_RETURN(0); + memcpy(new_ptr, array->buffer, + array->elements * array->size_of_element); + array->malloc_flags&= ~MY_INIT_BUFFER_USED; + } + else if (!(new_ptr= (uchar*) my_realloc(array->m_psi_key, + array->buffer,size * + array->size_of_element, + MYF(MY_WME | MY_ALLOW_ZERO_PTR | + array->malloc_flags)))) + DBUG_RETURN(TRUE); + array->buffer= new_ptr; + array->max_element= size; + } + DBUG_RETURN(FALSE); +} + + +/* + Get an element from array by given index + + SYNOPSIS + get_dynamic() + array + uchar* Element to be returned. If idx > elements contain zeroes. + idx Index of element wanted. +*/ + +void get_dynamic(DYNAMIC_ARRAY *array, void *element, size_t idx) +{ + if (idx >= array->elements) + { + DBUG_PRINT("warning",("To big array idx: %d, array size is %d", + idx,array->elements)); + bzero(element,array->size_of_element); + return; + } + memcpy(element,array->buffer+idx*array->size_of_element, + (size_t) array->size_of_element); +} + + +/* + Empty array by freeing all memory + + SYNOPSIS + delete_dynamic() + array Array to be deleted +*/ + +void delete_dynamic(DYNAMIC_ARRAY *array) +{ + /* + Just mark as empty if we are using a static buffer + */ + if (!(array->malloc_flags & MY_INIT_BUFFER_USED) && array->buffer) + my_free(array->buffer); + + array->buffer= 0; + array->elements= array->max_element= 0; +} + +/* + Delete element by given index + + SYNOPSIS + delete_dynamic_element() + array + idx Index of element to be deleted +*/ + +void delete_dynamic_element(DYNAMIC_ARRAY *array, size_t idx) +{ + char *ptr= (char*) array->buffer+array->size_of_element*idx; + array->elements--; + memmove(ptr,ptr+array->size_of_element, + (array->elements-idx)*array->size_of_element); +} + +/* + Wrapper around delete_dynamic, calling a FREE function on every + element, before releasing the memory + + SYNOPSIS + delete_dynamic_with_callback() + array + f The function to be called on every element before + deleting the array; +*/ +void delete_dynamic_with_callback(DYNAMIC_ARRAY *array, FREE_FUNC f) { + size_t i; + char *ptr= (char*) array->buffer; + for (i= 0; i < array->elements; i++, ptr+= array->size_of_element) { + f(ptr); + } + delete_dynamic(array); +} +/* + Free unused memory + + SYNOPSIS + freeze_size() + array Array to be freed + +*/ + +void freeze_size(DYNAMIC_ARRAY *array) +{ + size_t elements; + + /* + Do nothing if we are using a static buffer + */ + if (array->malloc_flags & MY_INIT_BUFFER_USED) + return; + + elements= MY_MAX(array->elements, 1); + if (array->buffer && array->max_element > elements) + { + array->buffer=(uchar*) my_realloc(array->m_psi_key, array->buffer, + elements * array->size_of_element, + MYF(MY_WME | array->malloc_flags)); + array->max_element= elements; + } +} |