matras.c

filter: Statementstmt 35.4% 83 / 234 Branchbran 19.5% 27 / 138 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 29.5% 110 / 372 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« rtree/small/matras.h ↑ Summary rtree.c »
1 /*
2 * matras implementation
3 */
4  
5 #include "matras.h"
6 #include <limits.h>
7 #include <string.h>
8 #include <stdbool.h>
9  
10 #ifdef WIN32
11 #include <intrin.h>
12 #pragma intrinsic (_BitScanReverse)
13 #endif
14  
15 /*
16 * Binary logarithm of value (exact if the value is a power of 2,
17 * approximate (floored) otherwise)
18 */
19 static matras_id_t
20 6171 matras_log2(matras_id_t val)
21 {
22 6171 ▶ assert(val > 0);
Branch: 1 branch
BranchTrueFalseTotal
assert(val > 0); 0 6171 6171
23 #ifdef WIN32
24 unsigned long res = 0;
25 unsigned char nonzero = _BitScanReverse(&res, val);
26 assert(nonzero); (void)nonzero;
27 return (matras_id_t)res;
28 #else
29 return sizeof(unsigned int) * CHAR_BIT -
30 6171 __builtin_clz((unsigned int) val) - 1;
31 #endif
32 }
33  
34 /**
35 * Initialize an empty instance of pointer translating
36 * block allocator. Does not allocate memory.
37 */
38 void
39 14 matras_create(struct matras *m, matras_id_t extent_size, matras_id_t block_size,
40 matras_alloc_func alloc_func, matras_free_func free_func,
41 void *alloc_ctx)
42 {
43 /*extent_size must be power of 2 */
44 14 ▶ assert((extent_size & (extent_size - 1)) == 0);
Branch: 1 branch
BranchTrueFalseTotal
assert((extent_size & (extent_size - 1)) == 0); 0 14 14
45 /*block_size must be power of 2 */
46 14 ▶ assert((block_size & (block_size - 1)) == 0);
Branch: 1 branch
BranchTrueFalseTotal
assert((block_size & (block_size - 1)) == 0); 0 14 14
47 /*block must be not greater than the extent*/
48 14 ▶ assert(block_size <= extent_size);
Branch: 1 branch
BranchTrueFalseTotal
assert(block_size <= extent_size); 0 14 14
49 /*extent must be able to store at least two records*/
50 14 ▶ assert(extent_size > sizeof(void *));
Branch: 1 branch
BranchTrueFalseTotal
assert(extent_size > sizeof(void *)); 0 14 14
51  
52 14 m->head.block_count = 0;
53 14 m->head.prev_view = 0;
54 14 m->head.next_view = 0;
55 14 m->block_size = block_size;
56 14 m->extent_size = extent_size;
57 14 m->extent_count = 0;
58 14 m->alloc_func = alloc_func;
59 14 m->free_func = free_func;
60 14 m->alloc_ctx = alloc_ctx;
61  
62 14 matras_id_t log1 = matras_log2(extent_size);
63 14 matras_id_t log2 = matras_log2(block_size);
64 14 matras_id_t log3 = matras_log2(sizeof(void *));
65 14 m->log2_capacity = log1 * 3 - log2 - log3 * 2;
66 14 m->shift1 = log1 * 2 - log2 - log3;
67 14 m->shift2 = log1 - log2;
68 14 m->mask1 = (((matras_id_t)1) << m->shift1) - ((matras_id_t)1);
69 14 m->mask2 = (((matras_id_t)1) << m->shift2) - ((matras_id_t)1);
70 14 }
71  
72  
73 /**
74 * Free all memory used by an instance of matras and
75 * reinitialize it.
76 * Identical to matras_destroy(m); matras_create(m, ...);
77 */
78 void
79 0 matras_reset(struct matras *m)
80 {
81 0 matras_destroy(m);
82 0 m->head.block_count = 0;
83 0 }
84  
85 /**
86 * Helper functions for allocating new extent and incrementing extent counter
87 */
88 static inline void *
89 784 matras_alloc_extent(struct matras *m)
90 {
91 784 void *ext = m->alloc_func(m->alloc_ctx);
92 784 ▶ if (ext)
Branch: 1 branch
BranchTrueFalseTotal
if (ext) 784 0 784
93 784 m->extent_count++;
94 784 return ext;
95 }
96  
97 /**
98 * Helper functions for allocating new extent and incrementing extent counter
99 */
100 static inline void
101 784 matras_free_extent(struct matras *m, void *ext)
102 {
103 784 m->free_func(m->alloc_ctx, ext);
104 784 m->extent_count--;
105 784 }
106  
107 /**
108 * Free all memory used by an instance of matras.
109 */
110 void
111 14 matras_destroy(struct matras *m)
112 {
113 14 ▶ while (m->head.prev_view)
Branch: 1 branch
BranchTrueFalseTotal
while (m->head.prev_view) 0 14 14
114 0 matras_destroy_read_view(m, m->head.prev_view);
115 14 ▶ if (m->head.block_count == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (m->head.block_count == 0) 8 6 14
116 8 return;
117  
118 6 matras_id_t step1 = m->mask1 + 1;
119 6 matras_id_t step2 = m->mask2 + 1;
120 6 matras_id_t i1 = 0, j1 = 0, i2, j2;
121 6 matras_id_t ptrs_in_ext = m->extent_size / (matras_id_t)sizeof(void *);
122 6 struct matras_view *v = &m->head;
123 6 void **extent1 = (void **)v->root;
124 12 ▶ for (; j1 < v->block_count; i1++, j1 += step1) {
Branch: 1 branch
BranchTrueFalseTotal
for (; j1 < v->block_count; i1++, j1 += step1) { 6 6 12
125 6 void **extent2 = (void **)extent1[i1];
126 6 for (i2 = j2 = 0;
127 778 ▶ i2 < ptrs_in_ext && j1 + j2 < v->block_count;
Branch: 2 branches
BranchTrueFalseTotal
i2 < ptrs_in_ext && j1 + j2 < v->block_count; 778 0 778
i2 < ptrs_in_ext && j1 + j2 < v->block_count; 772 6 778
128 772 i2++, j2 += step2) {
129 772 void **extent3 = (void **)extent2[i2];
130 772 matras_free_extent(m, extent3);
131 }
132 6 matras_free_extent(m, extent2);
133 }
134 6 matras_free_extent(m, extent1);
135  
136 6 ▶ assert(m->extent_count == 0);
Branch: 1 branch
BranchTrueFalseTotal
assert(m->extent_count == 0); 0 6 6
137 }
138  
139  
140  
141 /**
142 * Allocate a new block. Return both, block pointer and block
143 * id.
144 *
145 * @retval NULL failed to allocate memory
146 */
147 void *
148 6135 matras_alloc(struct matras *m, matras_id_t *result_id)
149 {
150 6135 ▶ assert(m->head.block_count == 0 ||
Branch: 2 branches
BranchTrueFalseTotal
assert(m->head.block_count == 0 || 6129 6 6135
assert(m->head.block_count == 0 || 0 6129 6129
151 matras_log2(m->head.block_count) < m->log2_capacity);
152  
153 /* Current block_count is the ID of new block */
154 6135 matras_id_t id = m->head.block_count;
155  
156 /* See "Shifts and masks explanation" for details */
157 /* Additionally we determine if we must allocate extents.
158 * Basically,
159 * if n1 == 0 && n2 == 0 && n3 == 0, we must allocate root extent,
160 * if n2 == 0 && n3 == 0, we must allocate second level extent,
161 * if n3 == 0, we must allocate third level extent.
162 * Optimization:
163 * (n1 == 0 && n2 == 0 && n3 == 0) is identical to (id == 0)
164 * (n2 == 0 && n3 == 0) is identical to (id & mask1 == 0)
165 */
166 6135 matras_id_t extent1_available = id;
167 6135 matras_id_t n1 = id >> m->shift1;
168 6135 id &= m->mask1;
169 6135 matras_id_t extent2_available = id;
170 6135 matras_id_t n2 = id >> m->shift2;
171 6135 id &= m->mask2;
172 6135 matras_id_t extent3_available = id;
173 6135 matras_id_t n3 = id;
174  
175 void **extent1, **extent2;
176 char *extent3;
177  
178 6135 ▶ if (extent1_available) {
Branch: 1 branch
BranchTrueFalseTotal
if (extent1_available) { 6129 6 6135
179 6129 extent1 = (void **)m->head.root;
180 } else {
181 6 extent1 = (void **)matras_alloc_extent(m);
182 6 ▶ if (!extent1)
Branch: 1 branch
BranchTrueFalseTotal
if (!extent1) 0 6 6
183 0 return 0;
184 6 m->head.root = (void *)extent1;
185 }
186  
187 6135 ▶ if (extent2_available) {
Branch: 1 branch
BranchTrueFalseTotal
if (extent2_available) { 6129 6 6135
188 6129 extent2 = (void **)extent1[n1];
189 } else {
190 6 extent2 = (void **)matras_alloc_extent(m);
191 6 ▶ if (!extent2) {
Branch: 1 branch
BranchTrueFalseTotal
if (!extent2) { 0 6 6
192 0 ▶ if (!extent1_available) /* was created */
Branch: 1 branch
BranchTrueFalseTotal
if (!extent1_available) /* was created */ 0 0 0
193 0 matras_free_extent(m, extent1);
194 0 return 0;
195 }
196 6 extent1[n1] = (void *)extent2;
197 }
198  
199 6135 ▶ if (extent3_available) {
Branch: 1 branch
BranchTrueFalseTotal
if (extent3_available) { 5363 772 6135
200 5363 extent3 = (char *)extent2[n2];
201 } else {
202 772 extent3 = (char *)matras_alloc_extent(m);
203 772 ▶ if (!extent3) {
Branch: 1 branch
BranchTrueFalseTotal
if (!extent3) { 0 772 772
204 0 ▶ if (!extent1_available) /* was created */
Branch: 1 branch
BranchTrueFalseTotal
if (!extent1_available) /* was created */ 0 0 0
205 0 matras_free_extent(m, extent1);
206 0 ▶ if (!extent2_available) /* was created */
Branch: 1 branch
BranchTrueFalseTotal
if (!extent2_available) /* was created */ 0 0 0
207 0 matras_free_extent(m, extent2);
208 0 return 0;
209 }
210 772 extent2[n2] = (void *)extent3;
211 }
212  
213 6135 *result_id = m->head.block_count++;
214 6135 return (void *)(extent3 + n3 * m->block_size);
215 }
216  
217 /*
218 * Deallocate last block (block with maximum ID)
219 */
220 void
221 0 matras_dealloc(struct matras *m)
222 {
223 0 ▶ assert(m->head.block_count);
Branch: 1 branch
BranchTrueFalseTotal
assert(m->head.block_count); 0 0 0
224 0 matras_id_t id = m->head.block_count - 1;
225 0 matras_touch(m, id);
226 0 m->head.block_count = id;
227 /* Current block_count is the ID of deleting block */
228  
229 /* See "Shifts and masks explanation" for details */
230 /* Deleting extents in same way (but reverse order) like in matras_alloc
231 * See matras_alloc for details. */
232 0 bool extent1_free = !id;
233 0 matras_id_t n1 = id >> m->shift1;
234 0 id &= m->mask1;
235 0 bool extent2_free = !id;
236 0 matras_id_t n2 = id >> m->shift2;
237 0 id &= m->mask2;
238 0 bool extent3_free = !id;
239  
240 0 ▶ if (extent1_free || extent2_free || extent3_free) {
Branch: 3 branches
BranchTrueFalseTotal
if (extent1_free || extent2_free || extent3_free) { 0 0 0
if (extent1_free || extent2_free || extent3_free) { 0 0 0
if (extent1_free || extent2_free || extent3_free) { 0 0 0
241 void **extent1, **extent2, *extent3;
242 0 extent1 = (void **)m->head.root;
243 0 extent2 = (void **)extent1[n1];
244 0 extent3 = extent2[n2];
245 0 ▶ if (extent3_free)
Branch: 1 branch
BranchTrueFalseTotal
if (extent3_free) 0 0 0
246 0 matras_free_extent(m, extent3);
247 0 ▶ if (extent2_free)
Branch: 1 branch
BranchTrueFalseTotal
if (extent2_free) 0 0 0
248 0 matras_free_extent(m, extent2);
249 0 ▶ if (extent1_free)
Branch: 1 branch
BranchTrueFalseTotal
if (extent1_free) 0 0 0
250 0 matras_free_extent(m, extent1);
251 }
252 0 }
253  
254 /**
255 * Allocate a range_count of blocks. Return both, first block pointer
256 * and first block id. This method only works if current number of blocks and
257 * number of blocks in one extent are divisible by range_count.
258 * range_count must also be less or equal to number of blocks in one extent.
259 *
260 * @retval NULL failed to allocate memory
261 */
262 void *
263 0 matras_alloc_range(struct matras *m, matras_id_t *id, matras_id_t range_count)
264 {
265 0 ▶ assert(m->head.block_count % range_count == 0);
Branch: 1 branch
BranchTrueFalseTotal
assert(m->head.block_count % range_count == 0); 0 0 0
266 0 ▶ assert(m->extent_size / m->block_size % range_count == 0);
Branch: 1 branch
BranchTrueFalseTotal
assert(m->extent_size / m->block_size % range_count == 0); 0 0 0
267 0 void *res = matras_alloc(m, id);
268 0 ▶ if (res)
Branch: 1 branch
BranchTrueFalseTotal
if (res) 0 0 0
269 0 m->head.block_count += (range_count - 1);
270 0 return res;
271 }
272  
273 /*
274 * Deallocate last range_count of blocks (blocks with maximum ID)
275 * This method only works if current number of blocks and
276 * number of blocks in one extent are divisible by range_count.
277 * range_count must also be less or equal to number of blocks in one extent.
278 */
279 void
280 0 matras_dealloc_range(struct matras *m, matras_id_t range_count)
281 {
282 0 ▶ assert(m->head.block_count % range_count == 0);
Branch: 1 branch
BranchTrueFalseTotal
assert(m->head.block_count % range_count == 0); 0 0 0
283 0 ▶ assert(m->extent_size / m->block_size % range_count == 0);
Branch: 1 branch
BranchTrueFalseTotal
assert(m->extent_size / m->block_size % range_count == 0); 0 0 0
284 0 m->head.block_count -= (range_count - 1);
285 0 matras_dealloc(m);
286 0 }
287  
288 /**
289 * Return the number of allocated extents (of size m->extent_size each)
290 */
291 matras_id_t
292 0 matras_extent_count(const struct matras *m)
293 {
294 0 return m->extent_count;
295 }
296  
297 /*
298 * Create new read view.
299 */
300 void
301 0 matras_create_read_view(struct matras *m, struct matras_view *v)
302 {
303 0 *v = m->head;
304 0 v->next_view = &m->head;
305 0 m->head.prev_view = v;
306 0 ▶ if (v->prev_view)
Branch: 1 branch
BranchTrueFalseTotal
if (v->prev_view) 0 0 0
307 0 v->prev_view->next_view = v;
308 0 }
309  
310 /*
311 * Delete a read view.
312 */
313 void
314 0 matras_destroy_read_view(struct matras *m, struct matras_view *v)
315 {
316 0 ▶ assert(v != &m->head);
Branch: 1 branch
BranchTrueFalseTotal
assert(v != &m->head); 0 0 0
317 0 ▶ if (!v->next_view)
Branch: 1 branch
BranchTrueFalseTotal
if (!v->next_view) 0 0 0
318 0 return;
319 0 struct matras_view *next_view = v->next_view;
320 0 struct matras_view *prev_view = v->prev_view;
321 0 next_view->prev_view = prev_view;
322 0 ▶ if (prev_view)
Branch: 1 branch
BranchTrueFalseTotal
if (prev_view) 0 0 0
323 0 prev_view->next_view = next_view;
324 0 v->next_view = 0;
325  
326 0 ▶ if (v->block_count == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (v->block_count == 0) 0 0 0
327 0 return;
328 0 ▶ if (v->root == next_view->root && next_view->block_count)
Branch: 2 branches
BranchTrueFalseTotal
if (v->root == next_view->root && next_view->block_count) 0 0 0
if (v->root == next_view->root && next_view->block_count) 0 0 0
329 0 return;
330 0 ▶ if (prev_view && v->root == prev_view->root && prev_view->block_count)
Branch: 3 branches
BranchTrueFalseTotal
if (prev_view && v->root == prev_view->root && prev_view->block_count) 0 0 0
if (prev_view && v->root == prev_view->root && prev_view->block_count) 0 0 0
if (prev_view && v->root == prev_view->root && prev_view->block_count) 0 0 0
331 0 return;
332 0 void **extent1 = (void **)v->root;
333 0 void **extent1n = (void **) next_view->root;
334 0 void **extent1p = 0;
335 0 ▶ if (prev_view)
Branch: 1 branch
BranchTrueFalseTotal
if (prev_view) 0 0 0
336 0 extent1p = (void **) prev_view->root;
337 0 matras_id_t step1 = m->mask1 + 1;
338 0 matras_id_t step2 = m->mask2 + 1;
339 0 matras_id_t i1 = 0, j1 = 0, i2, j2;
340 0 matras_id_t ptrs_in_ext = m->extent_size / (matras_id_t)sizeof(void *);
341 0 ▶ for (; j1 < v->block_count; i1++, j1 += step1) {
Branch: 1 branch
BranchTrueFalseTotal
for (; j1 < v->block_count; i1++, j1 += step1) { 0 0 0
342 0 void **extent2 = (void **)extent1[i1];
343 0 void **extent2n = 0;
344 0 void **extent2p = 0;
345 0 ▶ if (next_view->block_count > j1) {
Branch: 1 branch
BranchTrueFalseTotal
if (next_view->block_count > j1) { 0 0 0
346 0 ▶ if (extent1[i1] == extent1n[i1])
Branch: 1 branch
BranchTrueFalseTotal
if (extent1[i1] == extent1n[i1]) 0 0 0
347 0 continue;
348 0 extent2n = (void **) extent1n[i1];
349 }
350 0 ▶ if (prev_view && prev_view->block_count > j1) {
Branch: 2 branches
BranchTrueFalseTotal
if (prev_view && prev_view->block_count > j1) { 0 0 0
if (prev_view && prev_view->block_count > j1) { 0 0 0
351 0 ▶ if (extent1[i1] == extent1p[i1])
Branch: 1 branch
BranchTrueFalseTotal
if (extent1[i1] == extent1p[i1]) 0 0 0
352 0 continue;
353 0 extent2p = (void **) extent1p[i1];
354 }
355 0 for (i2 = j2 = 0;
356 0 ▶ i2 < ptrs_in_ext && j1 + j2 < v->block_count;
Branch: 2 branches
BranchTrueFalseTotal
i2 < ptrs_in_ext && j1 + j2 < v->block_count; 0 0 0
i2 < ptrs_in_ext && j1 + j2 < v->block_count; 0 0 0
357 0 i2++, j2 += step2) {
358 0 void **extent3 = (void **)extent2[i2];
359 0 ▶ if (next_view->block_count > j1 + j2) {
Branch: 1 branch
BranchTrueFalseTotal
if (next_view->block_count > j1 + j2) { 0 0 0
360 0 ▶ if (extent2[i2] == extent2n[i2])
Branch: 1 branch
BranchTrueFalseTotal
if (extent2[i2] == extent2n[i2]) 0 0 0
361 0 continue;
362 }
363 0 ▶ if (prev_view && prev_view->block_count > j1 + j2) {
Branch: 2 branches
BranchTrueFalseTotal
if (prev_view && prev_view->block_count > j1 + j2) { 0 0 0
if (prev_view && prev_view->block_count > j1 + j2) { 0 0 0
364 0 ▶ if (extent2[i2] == extent2p[i2])
Branch: 1 branch
BranchTrueFalseTotal
if (extent2[i2] == extent2p[i2]) 0 0 0
365 0 continue;
366 }
367 0 matras_free_extent(m, extent3);
368 }
369 0 matras_free_extent(m, extent2);
370 }
371 0 matras_free_extent(m, extent1);
372 }
373  
374 /*
375 * Notify matras that memory at given ID will be changed.
376 * Returns (perhaps new) address of memory associated with that block.
377 * Returns NULL on memory error
378 * Only needed (and does any work) if some versions are used.
379 */
380 void *
381 0 matras_touch(struct matras *m, matras_id_t id)
382 {
383 0 ▶ assert(id < m->head.block_count);
Branch: 1 branch
BranchTrueFalseTotal
assert(id < m->head.block_count); 0 0 0
384  
385 0 ▶ if (!m->head.prev_view)
Branch: 1 branch
BranchTrueFalseTotal
if (!m->head.prev_view) 0 0 0
386 0 return matras_get(m, id);
387  
388 0 ▶ if (m->head.prev_view->block_count) {
Branch: 1 branch
BranchTrueFalseTotal
if (m->head.prev_view->block_count) { 0 0 0
389 0 matras_id_t extent_id = id >> m->shift2;
390 0 matras_id_t next_last_id = m->head.prev_view->block_count - 1;
391 0 matras_id_t next_last_extent_id = next_last_id >> m->shift2;
392 0 ▶ if (extent_id > next_last_extent_id)
Branch: 1 branch
BranchTrueFalseTotal
if (extent_id > next_last_extent_id) 0 0 0
393 0 return matras_get(m, id);
394 } else {
395 0 return matras_get(m, id);
396 }
397  
398 /* see "Shifts and masks explanation" for details */
399 0 matras_id_t n1 = id >> m->shift1;
400 0 matras_id_t n2 = (id & m->mask1) >> m->shift2;
401 0 matras_id_t n3 = id & m->mask2;
402  
403 0 void **extent1 = (void **)m->head.root;
404 0 void **extent1p = (void **)m->head.prev_view->root;
405 0 ▶ if (extent1 == extent1p) {
Branch: 1 branch
BranchTrueFalseTotal
if (extent1 == extent1p) { 0 0 0
406 0 void *new_extent = matras_alloc_extent(m);
407 0 ▶ if (!new_extent)
Branch: 1 branch
BranchTrueFalseTotal
if (!new_extent) 0 0 0
408 0 return 0;
409 0 memcpy(new_extent, extent1, m->extent_size);
410 0 m->head.root = new_extent;
411 0 extent1 = (void **)new_extent;
412 }
413  
414 0 void **extent2 = (void **)extent1[n1];
415 0 void **extent2p = (void **)extent1p[n1];
416 0 ▶ if (extent2 == extent2p) {
Branch: 1 branch
BranchTrueFalseTotal
if (extent2 == extent2p) { 0 0 0
417 0 void *new_extent = matras_alloc_extent(m);
418 0 ▶ if (!new_extent)
Branch: 1 branch
BranchTrueFalseTotal
if (!new_extent) 0 0 0
419 0 return 0;
420 0 memcpy(new_extent, extent2, m->extent_size);
421 0 extent1[n1] = new_extent;
422 0 extent2 = (void **)new_extent;
423 }
424  
425 0 char *extent3 = (char *)extent2[n2];
426 0 char *extent3p = (char *)extent2p[n2];
427 0 ▶ if (extent3 == extent3p) {
Branch: 1 branch
BranchTrueFalseTotal
if (extent3 == extent3p) { 0 0 0
428 0 void *new_extent = matras_alloc_extent(m);
429 0 ▶ if (!new_extent)
Branch: 1 branch
BranchTrueFalseTotal
if (!new_extent) 0 0 0
430 0 return 0;
431 0 memcpy(new_extent, extent3, m->extent_size);
432 0 extent2[n2] = new_extent;
433 0 extent3 = (char *)new_extent;
434 }
435  
436 0 return &extent3[n3 * m->block_size];
437 }
« rtree/small/matras.h ↑ Summary rtree.c »