diff options
Diffstat (limited to '')
-rw-r--r-- | libraries/eina/src/lib/eina_array.c | 491 |
1 files changed, 491 insertions, 0 deletions
diff --git a/libraries/eina/src/lib/eina_array.c b/libraries/eina/src/lib/eina_array.c new file mode 100644 index 0000000..5a850ac --- /dev/null +++ b/libraries/eina/src/lib/eina_array.c | |||
@@ -0,0 +1,491 @@ | |||
1 | /* EINA - EFL data type library | ||
2 | * Copyright (C) 2008 Cedric Bail | ||
3 | * | ||
4 | * This library is free software; you can redistribute it and/or | ||
5 | * modify it under the terms of the GNU Lesser General Public | ||
6 | * License as published by the Free Software Foundation; either | ||
7 | * version 2.1 of the License, or (at your option) any later version. | ||
8 | * | ||
9 | * This library is distributed in the hope that it will be useful, | ||
10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
12 | * Lesser General Public License for more details. | ||
13 | * | ||
14 | * You should have received a copy of the GNU Lesser General Public | ||
15 | * License along with this library; | ||
16 | * if not, see <http://www.gnu.org/licenses/>. | ||
17 | */ | ||
18 | |||
19 | |||
20 | #ifdef HAVE_CONFIG_H | ||
21 | # include "config.h" | ||
22 | #endif | ||
23 | |||
24 | #include <assert.h> | ||
25 | #include <stdlib.h> | ||
26 | #include <string.h> | ||
27 | #include <stdio.h> | ||
28 | |||
29 | #include "eina_config.h" | ||
30 | #include "eina_private.h" | ||
31 | #include "eina_error.h" | ||
32 | #include "eina_log.h" | ||
33 | |||
34 | /* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */ | ||
35 | #include "eina_safety_checks.h" | ||
36 | #include "eina_array.h" | ||
37 | |||
38 | /*============================================================================* | ||
39 | * Local * | ||
40 | *============================================================================*/ | ||
41 | |||
42 | /** | ||
43 | * @cond LOCAL | ||
44 | */ | ||
45 | |||
46 | static const char EINA_MAGIC_ARRAY_STR[] = "Eina Array"; | ||
47 | static const char EINA_MAGIC_ARRAY_ITERATOR_STR[] = "Eina Array Iterator"; | ||
48 | static const char EINA_MAGIC_ARRAY_ACCESSOR_STR[] = "Eina Array Accessor"; | ||
49 | |||
50 | #define EINA_MAGIC_CHECK_ARRAY(d) \ | ||
51 | do { \ | ||
52 | if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_ARRAY)) { \ | ||
53 | EINA_MAGIC_FAIL(d, EINA_MAGIC_ARRAY); } \ | ||
54 | } while (0) | ||
55 | |||
56 | #define EINA_MAGIC_CHECK_ARRAY_ITERATOR(d, ...) \ | ||
57 | do { \ | ||
58 | if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_ARRAY_ITERATOR)) \ | ||
59 | { \ | ||
60 | EINA_MAGIC_FAIL(d, EINA_MAGIC_ARRAY_ITERATOR); \ | ||
61 | return __VA_ARGS__; \ | ||
62 | } \ | ||
63 | } while (0) | ||
64 | |||
65 | #define EINA_MAGIC_CHECK_ARRAY_ACCESSOR(d, ...) \ | ||
66 | do { \ | ||
67 | if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_ARRAY_ACCESSOR)) \ | ||
68 | { \ | ||
69 | EINA_MAGIC_FAIL(d, EINA_MAGIC_ACCESSOR); \ | ||
70 | return __VA_ARGS__; \ | ||
71 | } \ | ||
72 | } while (0) | ||
73 | |||
74 | |||
75 | typedef struct _Eina_Iterator_Array Eina_Iterator_Array; | ||
76 | struct _Eina_Iterator_Array | ||
77 | { | ||
78 | Eina_Iterator iterator; | ||
79 | |||
80 | const Eina_Array *array; | ||
81 | unsigned int index; | ||
82 | |||
83 | EINA_MAGIC | ||
84 | }; | ||
85 | |||
86 | typedef struct _Eina_Accessor_Array Eina_Accessor_Array; | ||
87 | struct _Eina_Accessor_Array | ||
88 | { | ||
89 | Eina_Accessor accessor; | ||
90 | const Eina_Array *array; | ||
91 | EINA_MAGIC | ||
92 | }; | ||
93 | |||
94 | static int _eina_array_log_dom = -1; | ||
95 | |||
96 | #ifdef ERR | ||
97 | #undef ERR | ||
98 | #endif | ||
99 | #define ERR(...) EINA_LOG_DOM_ERR(_eina_array_log_dom, __VA_ARGS__) | ||
100 | |||
101 | #ifdef DBG | ||
102 | #undef DBG | ||
103 | #endif | ||
104 | #define DBG(...) EINA_LOG_DOM_DBG(_eina_array_log_dom, __VA_ARGS__) | ||
105 | |||
106 | static void eina_array_iterator_free(Eina_Iterator_Array *it) EINA_ARG_NONNULL(1); | ||
107 | static Eina_Array *eina_array_iterator_get_container(Eina_Iterator_Array *it) EINA_ARG_NONNULL(1); | ||
108 | static Eina_Bool eina_array_iterator_next(Eina_Iterator_Array *it, | ||
109 | void **data) EINA_ARG_NONNULL(1); | ||
110 | |||
111 | static Eina_Bool eina_array_accessor_get_at(Eina_Accessor_Array *it, | ||
112 | unsigned int idx, | ||
113 | void **data) EINA_ARG_NONNULL(1); | ||
114 | static Eina_Array *eina_array_accessor_get_container(Eina_Accessor_Array *it) EINA_ARG_NONNULL(1); | ||
115 | static void eina_array_accessor_free(Eina_Accessor_Array *it) EINA_ARG_NONNULL(1); | ||
116 | |||
117 | static Eina_Bool | ||
118 | eina_array_iterator_next(Eina_Iterator_Array *it, void **data) | ||
119 | { | ||
120 | EINA_MAGIC_CHECK_ARRAY_ITERATOR(it, EINA_FALSE); | ||
121 | |||
122 | if (!(it->index < eina_array_count_get(it->array))) | ||
123 | return EINA_FALSE; | ||
124 | |||
125 | if (data) | ||
126 | *data = eina_array_data_get(it->array, it->index); | ||
127 | |||
128 | it->index++; | ||
129 | return EINA_TRUE; | ||
130 | } | ||
131 | |||
132 | static Eina_Array * | ||
133 | eina_array_iterator_get_container(Eina_Iterator_Array *it) | ||
134 | { | ||
135 | EINA_MAGIC_CHECK_ARRAY_ITERATOR(it, NULL); | ||
136 | return (Eina_Array *)it->array; | ||
137 | } | ||
138 | |||
139 | static void | ||
140 | eina_array_iterator_free(Eina_Iterator_Array *it) | ||
141 | { | ||
142 | EINA_MAGIC_CHECK_ARRAY_ITERATOR(it); | ||
143 | MAGIC_FREE(it); | ||
144 | } | ||
145 | |||
146 | static Eina_Bool | ||
147 | eina_array_accessor_get_at(Eina_Accessor_Array *it, | ||
148 | unsigned int idx, | ||
149 | void **data) | ||
150 | { | ||
151 | EINA_MAGIC_CHECK_ARRAY_ACCESSOR(it, EINA_FALSE); | ||
152 | |||
153 | if (!(idx < eina_array_count_get(it->array))) | ||
154 | return EINA_FALSE; | ||
155 | |||
156 | if (data) | ||
157 | *data = eina_array_data_get(it->array, idx); | ||
158 | |||
159 | return EINA_TRUE; | ||
160 | } | ||
161 | |||
162 | static Eina_Array * | ||
163 | eina_array_accessor_get_container(Eina_Accessor_Array *it) | ||
164 | { | ||
165 | EINA_MAGIC_CHECK_ARRAY_ACCESSOR(it, NULL); | ||
166 | return (Eina_Array *)it->array; | ||
167 | } | ||
168 | |||
169 | static void | ||
170 | eina_array_accessor_free(Eina_Accessor_Array *it) | ||
171 | { | ||
172 | EINA_MAGIC_CHECK_ARRAY_ACCESSOR(it); | ||
173 | MAGIC_FREE(it); | ||
174 | } | ||
175 | |||
176 | /* used from eina_inline_array.x, thus a needed symbol */ | ||
177 | EAPI Eina_Bool | ||
178 | eina_array_grow(Eina_Array *array) | ||
179 | { | ||
180 | void **tmp; | ||
181 | unsigned int total; | ||
182 | |||
183 | EINA_SAFETY_ON_NULL_RETURN_VAL(array, EINA_FALSE); | ||
184 | |||
185 | EINA_MAGIC_CHECK_ARRAY(array); | ||
186 | |||
187 | total = array->total + array->step; | ||
188 | eina_error_set(0); | ||
189 | tmp = realloc(array->data, sizeof (void *) * total); | ||
190 | if (EINA_UNLIKELY(!tmp)) | ||
191 | { | ||
192 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
193 | return 0; | ||
194 | } | ||
195 | |||
196 | array->total = total; | ||
197 | array->data = tmp; | ||
198 | |||
199 | return 1; | ||
200 | } | ||
201 | |||
202 | /** | ||
203 | * @endcond | ||
204 | */ | ||
205 | |||
206 | |||
207 | /*============================================================================* | ||
208 | * Global * | ||
209 | *============================================================================*/ | ||
210 | |||
211 | /** | ||
212 | * @internal | ||
213 | * @brief Initialize the array module. | ||
214 | * | ||
215 | * @return #EINA_TRUE on success, #EINA_FALSE on failure. | ||
216 | * | ||
217 | * This function sets up the error and magic modules or Eina. It is | ||
218 | * called by eina_init(). | ||
219 | * | ||
220 | * @see eina_init() | ||
221 | */ | ||
222 | Eina_Bool | ||
223 | eina_array_init(void) | ||
224 | { | ||
225 | _eina_array_log_dom = eina_log_domain_register("eina_array", | ||
226 | EINA_LOG_COLOR_DEFAULT); | ||
227 | if (_eina_array_log_dom < 0) | ||
228 | { | ||
229 | EINA_LOG_ERR("Could not register log domain: eina_array"); | ||
230 | return EINA_FALSE; | ||
231 | } | ||
232 | |||
233 | #define EMS(n) eina_magic_string_static_set(n, n ## _STR) | ||
234 | EMS(EINA_MAGIC_ARRAY); | ||
235 | EMS(EINA_MAGIC_ARRAY_ITERATOR); | ||
236 | EMS(EINA_MAGIC_ARRAY_ACCESSOR); | ||
237 | #undef EMS | ||
238 | return EINA_TRUE; | ||
239 | } | ||
240 | |||
241 | /** | ||
242 | * @internal | ||
243 | * @brief Shut down the array module. | ||
244 | * | ||
245 | * @return #EINA_TRUE on success, #EINA_FALSE on failure. | ||
246 | * | ||
247 | * This function shuts down the array module set up by | ||
248 | * eina_array_init(). It is called by eina_shutdown(). | ||
249 | * | ||
250 | * @see eina_shutdown() | ||
251 | */ | ||
252 | Eina_Bool | ||
253 | eina_array_shutdown(void) | ||
254 | { | ||
255 | eina_log_domain_unregister(_eina_array_log_dom); | ||
256 | _eina_array_log_dom = -1; | ||
257 | return EINA_TRUE; | ||
258 | } | ||
259 | |||
260 | /*============================================================================* | ||
261 | * API * | ||
262 | *============================================================================*/ | ||
263 | |||
264 | EAPI Eina_Array * | ||
265 | eina_array_new(unsigned int step) | ||
266 | { | ||
267 | Eina_Array *array; | ||
268 | |||
269 | eina_error_set(0); | ||
270 | array = malloc(sizeof (Eina_Array)); | ||
271 | if (!array) | ||
272 | { | ||
273 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
274 | return NULL; | ||
275 | } | ||
276 | |||
277 | EINA_MAGIC_SET(array, EINA_MAGIC_ARRAY); | ||
278 | |||
279 | array->version = EINA_ARRAY_VERSION; | ||
280 | array->data = NULL; | ||
281 | array->total = 0; | ||
282 | array->count = 0; | ||
283 | array->step = step; | ||
284 | |||
285 | return array; | ||
286 | } | ||
287 | |||
288 | EAPI void | ||
289 | eina_array_free(Eina_Array *array) | ||
290 | { | ||
291 | eina_array_flush(array); | ||
292 | |||
293 | EINA_SAFETY_ON_NULL_RETURN(array); | ||
294 | EINA_MAGIC_CHECK_ARRAY(array); | ||
295 | MAGIC_FREE(array); | ||
296 | } | ||
297 | |||
298 | EAPI void | ||
299 | eina_array_step_set(Eina_Array *array, | ||
300 | unsigned int sizeof_eina_array, | ||
301 | unsigned int step) | ||
302 | { | ||
303 | EINA_SAFETY_ON_NULL_RETURN(array); | ||
304 | |||
305 | if (sizeof (Eina_Array) != sizeof_eina_array) | ||
306 | { | ||
307 | ERR("Unknow Eina_Array size ! Got %i, expected %i !\n", | ||
308 | sizeof_eina_array, | ||
309 | (int) sizeof (Eina_Array)); | ||
310 | /* Force memory to zero to provide a small layer of security */ | ||
311 | memset(array, 0, sizeof_eina_array); | ||
312 | return ; | ||
313 | } | ||
314 | |||
315 | array->version = EINA_ARRAY_VERSION; | ||
316 | array->data = NULL; | ||
317 | array->total = 0; | ||
318 | array->count = 0; | ||
319 | array->step = step; | ||
320 | EINA_MAGIC_SET(array, EINA_MAGIC_ARRAY); | ||
321 | } | ||
322 | |||
323 | EAPI void | ||
324 | eina_array_flush(Eina_Array *array) | ||
325 | { | ||
326 | EINA_SAFETY_ON_NULL_RETURN(array); | ||
327 | EINA_MAGIC_CHECK_ARRAY(array); | ||
328 | |||
329 | array->count = 0; | ||
330 | array->total = 0; | ||
331 | |||
332 | if (!array->data) | ||
333 | return; | ||
334 | |||
335 | free(array->data); | ||
336 | array->data = NULL; | ||
337 | } | ||
338 | |||
339 | EAPI Eina_Bool | ||
340 | eina_array_remove(Eina_Array *array, Eina_Bool (*keep)(void *data, | ||
341 | void *gdata), | ||
342 | void *gdata) | ||
343 | { | ||
344 | void **tmp; | ||
345 | /* WARNING: | ||
346 | The algorithm does exit before using unitialized data. So compiler is | ||
347 | giving you a false positiv here too. | ||
348 | */ | ||
349 | void *data = NULL; | ||
350 | unsigned int total = 0; | ||
351 | unsigned int limit; | ||
352 | unsigned int i; | ||
353 | |||
354 | EINA_SAFETY_ON_NULL_RETURN_VAL(array, EINA_FALSE); | ||
355 | EINA_SAFETY_ON_NULL_RETURN_VAL(keep, EINA_FALSE); | ||
356 | EINA_MAGIC_CHECK_ARRAY(array); | ||
357 | |||
358 | if (array->total == 0) | ||
359 | return EINA_TRUE; | ||
360 | |||
361 | for (i = 0; i < array->count; ++i) | ||
362 | { | ||
363 | data = eina_array_data_get(array, i); | ||
364 | |||
365 | if (keep(data, gdata) == EINA_FALSE) | ||
366 | break; | ||
367 | } | ||
368 | limit = i; | ||
369 | if (i < array->count) | ||
370 | ++i; | ||
371 | |||
372 | for (; i < array->count; ++i) | ||
373 | { | ||
374 | data = eina_array_data_get(array, i); | ||
375 | |||
376 | if (keep(data, gdata) == EINA_TRUE) | ||
377 | break; | ||
378 | } | ||
379 | /* Special case all objects that need to stay are at the beginning of the array. */ | ||
380 | if (i == array->count) | ||
381 | { | ||
382 | array->count = limit; | ||
383 | if (array->count == 0) | ||
384 | { | ||
385 | free(array->data); | ||
386 | array->total = 0; | ||
387 | array->data = NULL; | ||
388 | } | ||
389 | |||
390 | return EINA_TRUE; | ||
391 | } | ||
392 | |||
393 | eina_error_set(0); | ||
394 | tmp = malloc(sizeof (void *) * array->total); | ||
395 | if (!tmp) | ||
396 | { | ||
397 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
398 | return EINA_FALSE; | ||
399 | } | ||
400 | |||
401 | memcpy(tmp, array->data, limit * sizeof(void *)); | ||
402 | total = limit; | ||
403 | |||
404 | if (i < array->count) | ||
405 | { | ||
406 | tmp[total] = data; | ||
407 | total++; | ||
408 | ++i; | ||
409 | } | ||
410 | |||
411 | for (; i < array->count; ++i) | ||
412 | { | ||
413 | data = eina_array_data_get(array, i); | ||
414 | |||
415 | if (keep(data, gdata)) | ||
416 | { | ||
417 | tmp[total] = data; | ||
418 | total++; | ||
419 | } | ||
420 | } | ||
421 | |||
422 | free(array->data); | ||
423 | |||
424 | /* If we do not keep any object in the array, we should have exited | ||
425 | earlier in test (i == array->count). */ | ||
426 | assert(total != 0); | ||
427 | |||
428 | array->data = tmp; | ||
429 | array->count = total; | ||
430 | return EINA_TRUE; | ||
431 | } | ||
432 | |||
433 | EAPI Eina_Iterator * | ||
434 | eina_array_iterator_new(const Eina_Array *array) | ||
435 | { | ||
436 | Eina_Iterator_Array *it; | ||
437 | |||
438 | EINA_SAFETY_ON_NULL_RETURN_VAL(array, NULL); | ||
439 | EINA_MAGIC_CHECK_ARRAY(array); | ||
440 | |||
441 | eina_error_set(0); | ||
442 | it = calloc(1, sizeof (Eina_Iterator_Array)); | ||
443 | if (!it) | ||
444 | { | ||
445 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
446 | return NULL; | ||
447 | } | ||
448 | |||
449 | EINA_MAGIC_SET(it, EINA_MAGIC_ARRAY_ITERATOR); | ||
450 | EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR); | ||
451 | |||
452 | it->array = array; | ||
453 | |||
454 | it->iterator.version = EINA_ITERATOR_VERSION; | ||
455 | it->iterator.next = FUNC_ITERATOR_NEXT(eina_array_iterator_next); | ||
456 | it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER( | ||
457 | eina_array_iterator_get_container); | ||
458 | it->iterator.free = FUNC_ITERATOR_FREE(eina_array_iterator_free); | ||
459 | |||
460 | return &it->iterator; | ||
461 | } | ||
462 | |||
463 | EAPI Eina_Accessor * | ||
464 | eina_array_accessor_new(const Eina_Array *array) | ||
465 | { | ||
466 | Eina_Accessor_Array *ac; | ||
467 | |||
468 | EINA_SAFETY_ON_NULL_RETURN_VAL(array, NULL); | ||
469 | EINA_MAGIC_CHECK_ARRAY(array); | ||
470 | |||
471 | eina_error_set(0); | ||
472 | ac = calloc(1, sizeof (Eina_Accessor_Array)); | ||
473 | if (!ac) | ||
474 | { | ||
475 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
476 | return NULL; | ||
477 | } | ||
478 | |||
479 | EINA_MAGIC_SET(ac, EINA_MAGIC_ARRAY_ACCESSOR); | ||
480 | EINA_MAGIC_SET(&ac->accessor, EINA_MAGIC_ACCESSOR); | ||
481 | |||
482 | ac->array = array; | ||
483 | |||
484 | ac->accessor.version = EINA_ACCESSOR_VERSION; | ||
485 | ac->accessor.get_at = FUNC_ACCESSOR_GET_AT(eina_array_accessor_get_at); | ||
486 | ac->accessor.get_container = FUNC_ACCESSOR_GET_CONTAINER( | ||
487 | eina_array_accessor_get_container); | ||
488 | ac->accessor.free = FUNC_ACCESSOR_FREE(eina_array_accessor_free); | ||
489 | |||
490 | return &ac->accessor; | ||
491 | } | ||