|
1
by Clint Byrum
Import upstream version 5.5.17 |
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 |
||
43 |
void lf_dynarray_init(LF_DYNARRAY *array, uint element_size) |
|
44 |
{
|
|
45 |
bzero(array, sizeof(*array)); |
|
46 |
array->size_of_element= element_size; |
|
47 |
my_atomic_rwlock_init(&array->lock); |
|
48 |
}
|
|
49 |
||
50 |
static void recursive_free(void **alloc, int level) |
|
51 |
{
|
|
52 |
if (!alloc) |
|
53 |
return; |
|
54 |
||
55 |
if (level) |
|
56 |
{
|
|
57 |
int i; |
|
58 |
for (i= 0; i < LF_DYNARRAY_LEVEL_LENGTH; i++) |
|
59 |
recursive_free(alloc[i], level-1); |
|
60 |
my_free(alloc); |
|
61 |
}
|
|
62 |
else
|
|
63 |
my_free(alloc[-1]); |
|
64 |
}
|
|
65 |
||
66 |
void lf_dynarray_destroy(LF_DYNARRAY *array) |
|
67 |
{
|
|
68 |
int i; |
|
69 |
for (i= 0; i < LF_DYNARRAY_LEVELS; i++) |
|
70 |
recursive_free(array->level[i], i); |
|
71 |
my_atomic_rwlock_destroy(&array->lock); |
|
72 |
}
|
|
73 |
||
74 |
static const ulong dynarray_idxes_in_prev_levels[LF_DYNARRAY_LEVELS]= |
|
75 |
{
|
|
76 |
0, /* +1 here to to avoid -1's below */ |
|
77 |
LF_DYNARRAY_LEVEL_LENGTH, |
|
78 |
LF_DYNARRAY_LEVEL_LENGTH * LF_DYNARRAY_LEVEL_LENGTH + |
|
79 |
LF_DYNARRAY_LEVEL_LENGTH, |
|
80 |
LF_DYNARRAY_LEVEL_LENGTH * LF_DYNARRAY_LEVEL_LENGTH * |
|
81 |
LF_DYNARRAY_LEVEL_LENGTH + LF_DYNARRAY_LEVEL_LENGTH * |
|
82 |
LF_DYNARRAY_LEVEL_LENGTH + LF_DYNARRAY_LEVEL_LENGTH |
|
83 |
};
|
|
84 |
||
85 |
static const ulong dynarray_idxes_in_prev_level[LF_DYNARRAY_LEVELS]= |
|
86 |
{
|
|
87 |
0, /* +1 here to to avoid -1's below */ |
|
88 |
LF_DYNARRAY_LEVEL_LENGTH, |
|
89 |
LF_DYNARRAY_LEVEL_LENGTH * LF_DYNARRAY_LEVEL_LENGTH, |
|
90 |
LF_DYNARRAY_LEVEL_LENGTH * LF_DYNARRAY_LEVEL_LENGTH * |
|
91 |
LF_DYNARRAY_LEVEL_LENGTH, |
|
92 |
};
|
|
93 |
||
94 |
/*
|
|
95 |
Returns a valid lvalue pointer to the element number 'idx'.
|
|
96 |
Allocates memory if necessary.
|
|
97 |
*/
|
|
98 |
void *_lf_dynarray_lvalue(LF_DYNARRAY *array, uint idx) |
|
99 |
{
|
|
100 |
void * ptr, * volatile * ptr_ptr= 0; |
|
101 |
int i; |
|
102 |
||
103 |
for (i= LF_DYNARRAY_LEVELS-1; idx < dynarray_idxes_in_prev_levels[i]; i--) |
|
104 |
/* no-op */; |
|
105 |
ptr_ptr= &array->level[i]; |
|
106 |
idx-= dynarray_idxes_in_prev_levels[i]; |
|
107 |
for (; i > 0; i--) |
|
108 |
{
|
|
109 |
if (!(ptr= *ptr_ptr)) |
|
110 |
{
|
|
111 |
void *alloc= my_malloc(LF_DYNARRAY_LEVEL_LENGTH * sizeof(void *), |
|
112 |
MYF(MY_WME|MY_ZEROFILL)); |
|
113 |
if (unlikely(!alloc)) |
|
114 |
return(NULL); |
|
115 |
if (my_atomic_casptr(ptr_ptr, &ptr, alloc)) |
|
116 |
ptr= alloc; |
|
117 |
else
|
|
118 |
my_free(alloc); |
|
119 |
}
|
|
120 |
ptr_ptr= ((void **)ptr) + idx / dynarray_idxes_in_prev_level[i]; |
|
121 |
idx%= dynarray_idxes_in_prev_level[i]; |
|
122 |
}
|
|
123 |
if (!(ptr= *ptr_ptr)) |
|
124 |
{
|
|
125 |
uchar *alloc, *data; |
|
126 |
alloc= my_malloc(LF_DYNARRAY_LEVEL_LENGTH * array->size_of_element + |
|
127 |
max(array->size_of_element, sizeof(void *)), |
|
128 |
MYF(MY_WME|MY_ZEROFILL)); |
|
129 |
if (unlikely(!alloc)) |
|
130 |
return(NULL); |
|
131 |
/* reserve the space for free() address */
|
|
132 |
data= alloc + sizeof(void *); |
|
133 |
{ /* alignment */ |
|
134 |
intptr mod= ((intptr)data) % array->size_of_element; |
|
135 |
if (mod) |
|
136 |
data+= array->size_of_element - mod; |
|
137 |
}
|
|
138 |
((void **)data)[-1]= alloc; /* free() will need the original pointer */ |
|
139 |
if (my_atomic_casptr(ptr_ptr, &ptr, data)) |
|
140 |
ptr= data; |
|
141 |
else
|
|
142 |
my_free(alloc); |
|
143 |
}
|
|
144 |
return ((uchar*)ptr) + array->size_of_element * idx; |
|
145 |
}
|
|
146 |
||
147 |
/*
|
|
148 |
Returns a pointer to the element number 'idx'
|
|
149 |
or NULL if an element does not exists
|
|
150 |
*/
|
|
151 |
void *_lf_dynarray_value(LF_DYNARRAY *array, uint idx) |
|
152 |
{
|
|
153 |
void * ptr, * volatile * ptr_ptr= 0; |
|
154 |
int i; |
|
155 |
||
156 |
for (i= LF_DYNARRAY_LEVELS-1; idx < dynarray_idxes_in_prev_levels[i]; i--) |
|
157 |
/* no-op */; |
|
158 |
ptr_ptr= &array->level[i]; |
|
159 |
idx-= dynarray_idxes_in_prev_levels[i]; |
|
160 |
for (; i > 0; i--) |
|
161 |
{
|
|
162 |
if (!(ptr= *ptr_ptr)) |
|
163 |
return(NULL); |
|
164 |
ptr_ptr= ((void **)ptr) + idx / dynarray_idxes_in_prev_level[i]; |
|
165 |
idx %= dynarray_idxes_in_prev_level[i]; |
|
166 |
}
|
|
167 |
if (!(ptr= *ptr_ptr)) |
|
168 |
return(NULL); |
|
169 |
return ((uchar*)ptr) + array->size_of_element * idx; |
|
170 |
}
|
|
171 |
||
172 |
static int recursive_iterate(LF_DYNARRAY *array, void *ptr, int level, |
|
173 |
lf_dynarray_func func, void *arg) |
|
174 |
{
|
|
175 |
int res, i; |
|
176 |
if (!ptr) |
|
177 |
return 0; |
|
178 |
if (!level) |
|
179 |
return func(ptr, arg); |
|
180 |
for (i= 0; i < LF_DYNARRAY_LEVEL_LENGTH; i++) |
|
181 |
if ((res= recursive_iterate(array, ((void **)ptr)[i], level-1, func, arg))) |
|
182 |
return res; |
|
183 |
return 0; |
|
184 |
}
|
|
185 |
||
186 |
/*
|
|
187 |
Calls func(array, arg) on every array of LF_DYNARRAY_LEVEL_LENGTH elements
|
|
188 |
in lf_dynarray.
|
|
189 |
||
190 |
DESCRIPTION
|
|
191 |
lf_dynarray consists of a set of arrays, LF_DYNARRAY_LEVEL_LENGTH elements
|
|
192 |
each. _lf_dynarray_iterate() calls user-supplied function on every array
|
|
193 |
from the set. It is the fastest way to scan the array, faster than
|
|
194 |
for (i=0; i < N; i++) { func(_lf_dynarray_value(dynarray, i)); }
|
|
195 |
||
196 |
NOTE
|
|
197 |
if func() returns non-zero, the scan is aborted
|
|
198 |
*/
|
|
199 |
int _lf_dynarray_iterate(LF_DYNARRAY *array, lf_dynarray_func func, void *arg) |
|
200 |
{
|
|
201 |
int i, res; |
|
202 |
for (i= 0; i < LF_DYNARRAY_LEVELS; i++) |
|
203 |
if ((res= recursive_iterate(array, array->level[i], i, func, arg))) |
|
204 |
return res; |
|
205 |
return 0; |
|
206 |
}
|
|
207 |