/* Copyright (C) 2000 MySQL AB 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; either version 2 of the License, or (at your option) any later version. 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ /* Analog of DYNAMIC_ARRAY that never reallocs (so no pointer into the array may ever become invalid). Memory is allocated in non-contiguous chunks. This data structure is not space efficient for sparce arrays. The number of elements is limited to 2^16 Every element is aligned to sizeof(element) boundary (to avoid false sharing if element is big enough). LF_DYNARRAY is a recursive structure. On the zero level LF_DYNARRAY::level[0] it's an array of LF_DYNARRAY_LEVEL_LENGTH elements, on the first level it's an array of LF_DYNARRAY_LEVEL_LENGTH pointers to arrays of elements, on the second level it's an array of pointers to arrays of pointers to arrays of elements. And so on. Actually, it's wait-free, not lock-free ;-) */ #include <my_global.h> #include <strings.h> #include <my_sys.h> #include <lf.h> void lf_dynarray_init(LF_DYNARRAY *array, uint element_size) { bzero(array, sizeof(*array)); array->size_of_element= element_size; my_atomic_rwlock_init(&array->lock); } static void recursive_free(void **alloc, int level) { if (!alloc) return; if (level) { int i; for (i= 0; i < LF_DYNARRAY_LEVEL_LENGTH; i++) recursive_free(alloc[i], level-1); my_free((void *)alloc, MYF(0)); } else my_free(alloc[-1], MYF(0)); } void lf_dynarray_destroy(LF_DYNARRAY *array) { int i; for (i= 0; i < LF_DYNARRAY_LEVELS; i++) recursive_free(array->level[i], i); my_atomic_rwlock_destroy(&array->lock); bzero(array, sizeof(*array)); } static const int dynarray_idxes_in_prev_level[LF_DYNARRAY_LEVELS]= { 0, /* +1 here to to avoid -1's below */ LF_DYNARRAY_LEVEL_LENGTH, LF_DYNARRAY_LEVEL_LENGTH * LF_DYNARRAY_LEVEL_LENGTH, LF_DYNARRAY_LEVEL_LENGTH * LF_DYNARRAY_LEVEL_LENGTH * LF_DYNARRAY_LEVEL_LENGTH }; /* Returns a valid lvalue pointer to the element number 'idx'. Allocates memory if necessary. */ void *_lf_dynarray_lvalue(LF_DYNARRAY *array, uint idx) { void * ptr, * volatile * ptr_ptr= 0; int i; for (i= 3; idx < dynarray_idxes_in_prev_level[i]; i--) /* no-op */; ptr_ptr= &array->level[i]; idx-= dynarray_idxes_in_prev_level[i]; for (; i > 0; i--) { if (!(ptr= *ptr_ptr)) { void *alloc= my_malloc(LF_DYNARRAY_LEVEL_LENGTH * sizeof(void *), MYF(MY_WME|MY_ZEROFILL)); if (!alloc) return(NULL); if (my_atomic_casptr(ptr_ptr, &ptr, alloc)) ptr= alloc; else my_free(alloc, MYF(0)); } ptr_ptr= ((void **)ptr) + idx / dynarray_idxes_in_prev_level[i]; idx%= dynarray_idxes_in_prev_level[i]; } if (!(ptr= *ptr_ptr)) { void *alloc, *data; alloc= my_malloc(LF_DYNARRAY_LEVEL_LENGTH * array->size_of_element + max(array->size_of_element, sizeof(void *)), MYF(MY_WME|MY_ZEROFILL)); if (!alloc) return(NULL); /* reserve the space for free() address */ data= alloc + sizeof(void *); { /* alignment */ intptr mod= ((intptr)data) % array->size_of_element; if (mod) data+= array->size_of_element - mod; } ((void **)data)[-1]= alloc; /* free() will need the original pointer */ if (my_atomic_casptr(ptr_ptr, &ptr, data)) ptr= data; else my_free(alloc, MYF(0)); } return ptr + array->size_of_element * idx; } /* Returns a pointer to the element number 'idx' or NULL if an element does not exists */ void *_lf_dynarray_value(LF_DYNARRAY *array, uint idx) { void * ptr, * volatile * ptr_ptr= 0; int i; for (i= 3; idx < dynarray_idxes_in_prev_level[i]; i--) /* no-op */; ptr_ptr= &array->level[i]; idx-= dynarray_idxes_in_prev_level[i]; for (; i > 0; i--) { if (!(ptr= *ptr_ptr)) return(NULL); ptr_ptr= ((void **)ptr) + idx / dynarray_idxes_in_prev_level[i]; idx %= dynarray_idxes_in_prev_level[i]; } if (!(ptr= *ptr_ptr)) return(NULL); return ptr + array->size_of_element * idx; } static int recursive_iterate(LF_DYNARRAY *array, void *ptr, int level, lf_dynarray_func func, void *arg) { int res, i; if (!ptr) return 0; if (!level) return func(ptr, arg); for (i= 0; i < LF_DYNARRAY_LEVEL_LENGTH; i++) if ((res= recursive_iterate(array, ((void **)ptr)[i], level-1, func, arg))) return res; return 0; } /* Calls func(array, arg) on every array of LF_DYNARRAY_LEVEL_LENGTH elements in lf_dynarray. DESCRIPTION lf_dynarray consists of a set of arrays, LF_DYNARRAY_LEVEL_LENGTH elements each. _lf_dynarray_iterate() calls user-supplied function on every array from the set. It is the fastest way to scan the array, faster than for (i=0; i < N; i++) { func(_lf_dynarray_value(dynarray, i)); } */ int _lf_dynarray_iterate(LF_DYNARRAY *array, lf_dynarray_func func, void *arg) { int i, res; for (i= 0; i < LF_DYNARRAY_LEVELS; i++) if ((res= recursive_iterate(array, array->level[i], i, func, arg))) return res; return 0; }