1/* Copyright (c) 2006, 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/*
17 Analog of DYNAMIC_ARRAY that never reallocs
18 (so no pointer into the array may ever become invalid).
19
20 Memory is allocated in non-contiguous chunks.
21 This data structure is not space efficient for sparse arrays.
22
23 Every element is aligned to sizeof(element) boundary
24 (to avoid false sharing if element is big enough).
25
26 LF_DYNARRAY is a recursive structure. On the zero level
27 LF_DYNARRAY::level[0] it's an array of LF_DYNARRAY_LEVEL_LENGTH elements,
28 on the first level it's an array of LF_DYNARRAY_LEVEL_LENGTH pointers
29 to arrays of elements, on the second level it's an array of pointers
30 to arrays of pointers to arrays of elements. And so on.
31
32 With four levels the number of elements is limited to 4311810304
33 (but as in all functions index is uint, the real limit is 2^32-1)
34
35 Actually, it's wait-free, not lock-free ;-)
36*/
37
38#include <my_global.h>
39#include <m_string.h>
40#include <my_sys.h>
41#include <lf.h>
42
43void lf_dynarray_init(LF_DYNARRAY *array, uint element_size)
44{
45 bzero(array, sizeof(*array));
46 array->size_of_element= element_size;
47}
48
49static void recursive_free(void **alloc, int level)
50{
51 if (!alloc)
52 return;
53
54 if (level)
55 {
56 int i;
57 for (i= 0; i < LF_DYNARRAY_LEVEL_LENGTH; i++)
58 recursive_free(alloc[i], level-1);
59 my_free(alloc);
60 }
61 else
62 my_free(alloc[-1]);
63}
64
65void lf_dynarray_destroy(LF_DYNARRAY *array)
66{
67 int i;
68 for (i= 0; i < LF_DYNARRAY_LEVELS; i++)
69 recursive_free(array->level[i], i);
70}
71
72static const ulong dynarray_idxes_in_prev_levels[LF_DYNARRAY_LEVELS]=
73{
74 0, /* +1 here to to avoid -1's below */
75 LF_DYNARRAY_LEVEL_LENGTH,
76 LF_DYNARRAY_LEVEL_LENGTH * LF_DYNARRAY_LEVEL_LENGTH +
77 LF_DYNARRAY_LEVEL_LENGTH,
78 LF_DYNARRAY_LEVEL_LENGTH * LF_DYNARRAY_LEVEL_LENGTH *
79 LF_DYNARRAY_LEVEL_LENGTH + LF_DYNARRAY_LEVEL_LENGTH *
80 LF_DYNARRAY_LEVEL_LENGTH + LF_DYNARRAY_LEVEL_LENGTH
81};
82
83static const ulong dynarray_idxes_in_prev_level[LF_DYNARRAY_LEVELS]=
84{
85 0, /* +1 here to to avoid -1's below */
86 LF_DYNARRAY_LEVEL_LENGTH,
87 LF_DYNARRAY_LEVEL_LENGTH * LF_DYNARRAY_LEVEL_LENGTH,
88 LF_DYNARRAY_LEVEL_LENGTH * LF_DYNARRAY_LEVEL_LENGTH *
89 LF_DYNARRAY_LEVEL_LENGTH,
90};
91
92/*
93 Returns a valid lvalue pointer to the element number 'idx'.
94 Allocates memory if necessary.
95*/
96void *lf_dynarray_lvalue(LF_DYNARRAY *array, uint idx)
97{
98 void * ptr, * volatile * ptr_ptr= 0;
99 int i;
100
101 for (i= LF_DYNARRAY_LEVELS-1; idx < dynarray_idxes_in_prev_levels[i]; i--)
102 /* no-op */;
103 ptr_ptr= &array->level[i];
104 idx-= dynarray_idxes_in_prev_levels[i];
105 for (; i > 0; i--)
106 {
107 if (!(ptr= *ptr_ptr))
108 {
109 void *alloc= my_malloc(LF_DYNARRAY_LEVEL_LENGTH * sizeof(void *),
110 MYF(MY_WME|MY_ZEROFILL));
111 if (unlikely(!alloc))
112 return(NULL);
113 if (my_atomic_casptr(ptr_ptr, &ptr, alloc))
114 ptr= alloc;
115 else
116 my_free(alloc);
117 }
118 ptr_ptr= ((void **)ptr) + idx / dynarray_idxes_in_prev_level[i];
119 idx%= dynarray_idxes_in_prev_level[i];
120 }
121 if (!(ptr= *ptr_ptr))
122 {
123 uchar *alloc, *data;
124 alloc= my_malloc(LF_DYNARRAY_LEVEL_LENGTH * array->size_of_element +
125 MY_MAX(array->size_of_element, sizeof(void *)),
126 MYF(MY_WME|MY_ZEROFILL));
127 if (unlikely(!alloc))
128 return(NULL);
129 /* reserve the space for free() address */
130 data= alloc + sizeof(void *);
131 { /* alignment */
132 intptr mod= ((intptr)data) % array->size_of_element;
133 if (mod)
134 data+= array->size_of_element - mod;
135 }
136 ((void **)data)[-1]= alloc; /* free() will need the original pointer */
137 if (my_atomic_casptr(ptr_ptr, &ptr, data))
138 ptr= data;
139 else
140 my_free(alloc);
141 }
142 return ((uchar*)ptr) + array->size_of_element * idx;
143}
144
145/*
146 Returns a pointer to the element number 'idx'
147 or NULL if an element does not exists
148*/
149void *lf_dynarray_value(LF_DYNARRAY *array, uint idx)
150{
151 void * ptr, * volatile * ptr_ptr= 0;
152 int i;
153
154 for (i= LF_DYNARRAY_LEVELS-1; idx < dynarray_idxes_in_prev_levels[i]; i--)
155 /* no-op */;
156 ptr_ptr= &array->level[i];
157 idx-= dynarray_idxes_in_prev_levels[i];
158 for (; i > 0; i--)
159 {
160 if (!(ptr= *ptr_ptr))
161 return(NULL);
162 ptr_ptr= ((void **)ptr) + idx / dynarray_idxes_in_prev_level[i];
163 idx %= dynarray_idxes_in_prev_level[i];
164 }
165 if (!(ptr= *ptr_ptr))
166 return(NULL);
167 return ((uchar*)ptr) + array->size_of_element * idx;
168}
169
170static int recursive_iterate(LF_DYNARRAY *array, void *ptr, int level,
171 lf_dynarray_func func, void *arg)
172{
173 int res, i;
174 if (!ptr)
175 return 0;
176 if (!level)
177 return func(ptr, arg);
178 for (i= 0; i < LF_DYNARRAY_LEVEL_LENGTH; i++)
179 if ((res= recursive_iterate(array, ((void **)ptr)[i], level-1, func, arg)))
180 return res;
181 return 0;
182}
183
184/*
185 Calls func(array, arg) on every array of LF_DYNARRAY_LEVEL_LENGTH elements
186 in lf_dynarray.
187
188 DESCRIPTION
189 lf_dynarray consists of a set of arrays, LF_DYNARRAY_LEVEL_LENGTH elements
190 each. lf_dynarray_iterate() calls user-supplied function on every array
191 from the set. It is the fastest way to scan the array, faster than
192 for (i=0; i < N; i++) { func(lf_dynarray_value(dynarray, i)); }
193
194 NOTE
195 if func() returns non-zero, the scan is aborted
196*/
197int lf_dynarray_iterate(LF_DYNARRAY *array, lf_dynarray_func func, void *arg)
198{
199 int i, res;
200 for (i= 0; i < LF_DYNARRAY_LEVELS; i++)
201 if ((res= recursive_iterate(array, array->level[i], i, func, arg)))
202 return res;
203 return 0;
204}
205
206