diff options
author | David Walter Seikel | 2012-01-04 18:41:13 +1000 |
---|---|---|
committer | David Walter Seikel | 2012-01-04 18:41:13 +1000 |
commit | dd7595a3475407a7fa96a97393bae8c5220e8762 (patch) | |
tree | e341e911d7eb911a51684a7412ef7f7c7605d28e /libraries/eina/src/lib/eina_list.c | |
parent | Add the skeleton. (diff) | |
download | SledjHamr-dd7595a3475407a7fa96a97393bae8c5220e8762.zip SledjHamr-dd7595a3475407a7fa96a97393bae8c5220e8762.tar.gz SledjHamr-dd7595a3475407a7fa96a97393bae8c5220e8762.tar.bz2 SledjHamr-dd7595a3475407a7fa96a97393bae8c5220e8762.tar.xz |
Add the base Enlightenment Foundation Libraries - eina, eet, evas, ecore, embryo, and edje.
Note that embryo wont be used, but I'm not sure yet if you can build edje without it.
Diffstat (limited to '')
-rw-r--r-- | libraries/eina/src/lib/eina_list.c | 1490 |
1 files changed, 1490 insertions, 0 deletions
diff --git a/libraries/eina/src/lib/eina_list.c b/libraries/eina/src/lib/eina_list.c new file mode 100644 index 0000000..d45cffd --- /dev/null +++ b/libraries/eina/src/lib/eina_list.c | |||
@@ -0,0 +1,1490 @@ | |||
1 | /* EINA - EFL data type library | ||
2 | * Copyright (C) 2002-2008 Carsten Haitzler, Gustavo Sverzut Barbieri, Tilman Sauerbeck, | ||
3 | * Vincent Torri, Cedric Bail, Jorge Luis Zapata Muga, | ||
4 | * Corey Donohoe, Arnaud de Turckheim, Alexandre Becoulet | ||
5 | * | ||
6 | * This library is free software; you can redistribute it and/or | ||
7 | * modify it under the terms of the GNU Lesser General Public | ||
8 | * License as published by the Free Software Foundation; either | ||
9 | * version 2.1 of the License, or (at your option) any later version. | ||
10 | * | ||
11 | * This library is distributed in the hope that it will be useful, | ||
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
14 | * Lesser General Public License for more details. | ||
15 | * | ||
16 | * You should have received a copy of the GNU Lesser General Public | ||
17 | * License along with this library; | ||
18 | * if not, see <http://www.gnu.org/licenses/>. | ||
19 | * | ||
20 | * This file incorporates work covered by the following copyright and | ||
21 | * permission notice: | ||
22 | * | ||
23 | * Copyright (C) 2004 ncn | ||
24 | * Copyright (C) 2006 Sebastian Dransfeld | ||
25 | * Copyright (C) 2007 Christopher Michael | ||
26 | * | ||
27 | * Permission is hereby granted, free of charge, to any person obtaining a copy | ||
28 | * of this software and associated documentation files (the "Software"), to | ||
29 | * deal in the Software without restriction, including without limitation the | ||
30 | * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or | ||
31 | * sell copies of the Software, and to permit persons to whom the Software is | ||
32 | * furnished to do so, subject to the following conditions: | ||
33 | |||
34 | * The above copyright notice and this permission notice shall be included in | ||
35 | * all copies of the Software and its Copyright notices. In addition publicly | ||
36 | * documented acknowledgment must be given that this software has been used if no | ||
37 | * source code of this software is made available publicly. This includes | ||
38 | * acknowledgments in either Copyright notices, Manuals, Publicity and Marketing | ||
39 | * documents or any documentation provided with any product containing this | ||
40 | * software. This License does not apply to any software that links to the | ||
41 | * libraries provided by this software (statically or dynamically), but only to | ||
42 | * the software provided. | ||
43 | |||
44 | * Please see the OLD-COPYING.PLAIN for a plain-english explanation of this notice | ||
45 | * and it's intent. | ||
46 | |||
47 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | ||
48 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | ||
49 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL | ||
50 | * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER | ||
51 | * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN | ||
52 | * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. | ||
53 | */ | ||
54 | |||
55 | |||
56 | #ifdef HAVE_CONFIG_H | ||
57 | # include "config.h" | ||
58 | #endif | ||
59 | |||
60 | #include <stdlib.h> | ||
61 | #include <stdio.h> | ||
62 | #include <string.h> | ||
63 | |||
64 | #ifdef HAVE_EVIL | ||
65 | # include <Evil.h> | ||
66 | #endif | ||
67 | |||
68 | #include "eina_config.h" | ||
69 | #include "eina_private.h" | ||
70 | #include "eina_error.h" | ||
71 | #include "eina_log.h" | ||
72 | #include "eina_mempool.h" | ||
73 | |||
74 | /* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */ | ||
75 | #include "eina_safety_checks.h" | ||
76 | #include "eina_list.h" | ||
77 | |||
78 | |||
79 | /*============================================================================* | ||
80 | * Local * | ||
81 | *============================================================================*/ | ||
82 | |||
83 | /** | ||
84 | * @cond LOCAL | ||
85 | */ | ||
86 | |||
87 | static const char EINA_MAGIC_LIST_STR[] = "Eina List"; | ||
88 | static const char EINA_MAGIC_LIST_ITERATOR_STR[] = "Eina List Iterator"; | ||
89 | static const char EINA_MAGIC_LIST_ACCESSOR_STR[] = "Eina List Accessor"; | ||
90 | static const char EINA_MAGIC_LIST_ACCOUNTING_STR[] = "Eina List Accounting"; | ||
91 | |||
92 | |||
93 | #define EINA_MAGIC_CHECK_LIST(d, ...) \ | ||
94 | do { \ | ||
95 | if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_LIST)) \ | ||
96 | { \ | ||
97 | EINA_MAGIC_FAIL(d, EINA_MAGIC_LIST); \ | ||
98 | return __VA_ARGS__; \ | ||
99 | } \ | ||
100 | } while(0) | ||
101 | |||
102 | #define EINA_MAGIC_CHECK_LIST_ITERATOR(d, ...) \ | ||
103 | do { \ | ||
104 | if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_LIST_ITERATOR)) \ | ||
105 | { \ | ||
106 | EINA_MAGIC_FAIL(d, EINA_MAGIC_LIST_ITERATOR); \ | ||
107 | return __VA_ARGS__; \ | ||
108 | } \ | ||
109 | } while(0) | ||
110 | |||
111 | #define EINA_MAGIC_CHECK_LIST_ACCESSOR(d, ...) \ | ||
112 | do { \ | ||
113 | if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_LIST_ACCESSOR)) \ | ||
114 | { \ | ||
115 | EINA_MAGIC_FAIL(d, EINA_MAGIC_LIST_ACCESSOR); \ | ||
116 | return __VA_ARGS__; \ | ||
117 | } \ | ||
118 | } while(0) | ||
119 | |||
120 | #define EINA_MAGIC_CHECK_LIST_ACCOUNTING(d) \ | ||
121 | do { \ | ||
122 | if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_LIST_ACCOUNTING)) \ | ||
123 | { \ | ||
124 | EINA_MAGIC_FAIL(d, EINA_MAGIC_LIST_ACCOUNTING); \ | ||
125 | return; \ | ||
126 | } \ | ||
127 | } while(0) | ||
128 | |||
129 | #define EINA_LIST_SORT_STACK_SIZE 32 | ||
130 | |||
131 | typedef struct _Eina_Iterator_List Eina_Iterator_List; | ||
132 | typedef struct _Eina_Accessor_List Eina_Accessor_List; | ||
133 | |||
134 | struct _Eina_Iterator_List | ||
135 | { | ||
136 | Eina_Iterator iterator; | ||
137 | |||
138 | const Eina_List *head; | ||
139 | const Eina_List *current; | ||
140 | |||
141 | EINA_MAGIC | ||
142 | }; | ||
143 | |||
144 | struct _Eina_Accessor_List | ||
145 | { | ||
146 | Eina_Accessor accessor; | ||
147 | |||
148 | const Eina_List *head; | ||
149 | const Eina_List *current; | ||
150 | |||
151 | unsigned int index; | ||
152 | |||
153 | EINA_MAGIC | ||
154 | }; | ||
155 | |||
156 | static Eina_Mempool *_eina_list_mp = NULL; | ||
157 | static Eina_Mempool *_eina_list_accounting_mp = NULL; | ||
158 | static int _eina_list_log_dom = -1; | ||
159 | |||
160 | #ifdef ERR | ||
161 | #undef ERR | ||
162 | #endif | ||
163 | #define ERR(...) EINA_LOG_DOM_ERR(_eina_list_log_dom, __VA_ARGS__) | ||
164 | |||
165 | #ifdef DBG | ||
166 | #undef DBG | ||
167 | #endif | ||
168 | #define DBG(...) EINA_LOG_DOM_DBG(_eina_list_log_dom, __VA_ARGS__) | ||
169 | |||
170 | static inline Eina_List_Accounting * | ||
171 | _eina_list_mempool_accounting_new(__UNUSED__ Eina_List *list) | ||
172 | { | ||
173 | Eina_List_Accounting *tmp; | ||
174 | |||
175 | tmp = | ||
176 | eina_mempool_malloc(_eina_list_accounting_mp, | ||
177 | sizeof (Eina_List_Accounting)); | ||
178 | if (!tmp) | ||
179 | return NULL; | ||
180 | |||
181 | EINA_MAGIC_SET(tmp, EINA_MAGIC_LIST_ACCOUNTING); | ||
182 | |||
183 | return tmp; | ||
184 | } | ||
185 | static inline void | ||
186 | _eina_list_mempool_accounting_free(Eina_List_Accounting *accounting) | ||
187 | { | ||
188 | EINA_MAGIC_CHECK_LIST_ACCOUNTING(accounting); | ||
189 | |||
190 | EINA_MAGIC_SET(accounting, EINA_MAGIC_NONE); | ||
191 | eina_mempool_free(_eina_list_accounting_mp, accounting); | ||
192 | } | ||
193 | |||
194 | static inline Eina_List * | ||
195 | _eina_list_mempool_list_new(__UNUSED__ Eina_List *list) | ||
196 | { | ||
197 | Eina_List *tmp; | ||
198 | |||
199 | tmp = eina_mempool_malloc(_eina_list_mp, sizeof (Eina_List)); | ||
200 | if (!tmp) | ||
201 | return NULL; | ||
202 | |||
203 | EINA_MAGIC_SET(tmp, EINA_MAGIC_LIST); | ||
204 | |||
205 | return tmp; | ||
206 | } | ||
207 | static inline void | ||
208 | _eina_list_mempool_list_free(Eina_List *list) | ||
209 | { | ||
210 | EINA_MAGIC_CHECK_LIST(list); | ||
211 | |||
212 | list->accounting->count--; | ||
213 | if (list->accounting->count == 0) | ||
214 | _eina_list_mempool_accounting_free(list->accounting); | ||
215 | |||
216 | EINA_MAGIC_SET(list, EINA_MAGIC_NONE); | ||
217 | eina_mempool_free(_eina_list_mp, list); | ||
218 | } | ||
219 | |||
220 | static Eina_List * | ||
221 | _eina_list_setup_accounting(Eina_List *list) | ||
222 | { | ||
223 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
224 | |||
225 | list->accounting = _eina_list_mempool_accounting_new(list); | ||
226 | if (!list->accounting) | ||
227 | goto on_error; | ||
228 | |||
229 | list->accounting->last = list; | ||
230 | list->accounting->count = 1; | ||
231 | |||
232 | return list; | ||
233 | |||
234 | on_error: | ||
235 | _eina_list_mempool_list_free(list); | ||
236 | return NULL; | ||
237 | } | ||
238 | |||
239 | static inline void | ||
240 | _eina_list_update_accounting(Eina_List *list, Eina_List *new_list) | ||
241 | { | ||
242 | EINA_MAGIC_CHECK_LIST(list); | ||
243 | EINA_MAGIC_CHECK_LIST(new_list); | ||
244 | |||
245 | list->accounting->count++; | ||
246 | new_list->accounting = list->accounting; | ||
247 | } | ||
248 | |||
249 | #if 0 | ||
250 | static Eina_Mempool2 _eina_list_mempool = | ||
251 | { | ||
252 | sizeof(Eina_List), | ||
253 | 320, | ||
254 | 0, NULL, NULL | ||
255 | }; | ||
256 | static Eina_Mempool2 _eina_list_accounting_mempool = | ||
257 | { | ||
258 | sizeof(Eina_List_Accounting), | ||
259 | 80, | ||
260 | 0, NULL, NULL | ||
261 | }; | ||
262 | #endif | ||
263 | |||
264 | static Eina_Bool | ||
265 | eina_list_iterator_next(Eina_Iterator_List *it, void **data) | ||
266 | { | ||
267 | EINA_MAGIC_CHECK_LIST_ITERATOR(it, EINA_FALSE); | ||
268 | |||
269 | if (!it->current) | ||
270 | return EINA_FALSE; | ||
271 | |||
272 | *data = eina_list_data_get(it->current); | ||
273 | |||
274 | it->current = eina_list_next(it->current); | ||
275 | |||
276 | return EINA_TRUE; | ||
277 | } | ||
278 | |||
279 | static Eina_Bool | ||
280 | eina_list_iterator_prev(Eina_Iterator_List *it, void **data) | ||
281 | { | ||
282 | EINA_MAGIC_CHECK_LIST_ITERATOR(it, EINA_FALSE); | ||
283 | |||
284 | if (!it->current) | ||
285 | return EINA_FALSE; | ||
286 | |||
287 | *data = eina_list_data_get(it->current); | ||
288 | |||
289 | it->current = eina_list_prev(it->current); | ||
290 | |||
291 | return EINA_TRUE; | ||
292 | } | ||
293 | |||
294 | static Eina_List * | ||
295 | eina_list_iterator_get_container(Eina_Iterator_List *it) | ||
296 | { | ||
297 | EINA_MAGIC_CHECK_LIST_ITERATOR(it, NULL); | ||
298 | |||
299 | return (Eina_List *)it->head; | ||
300 | } | ||
301 | |||
302 | static void | ||
303 | eina_list_iterator_free(Eina_Iterator_List *it) | ||
304 | { | ||
305 | EINA_MAGIC_CHECK_LIST_ITERATOR(it); | ||
306 | |||
307 | MAGIC_FREE(it); | ||
308 | } | ||
309 | |||
310 | static Eina_Bool | ||
311 | eina_list_accessor_get_at(Eina_Accessor_List *it, unsigned int idx, void **data) | ||
312 | { | ||
313 | const Eina_List *over; | ||
314 | unsigned int middle; | ||
315 | unsigned int i; | ||
316 | |||
317 | EINA_MAGIC_CHECK_LIST_ACCESSOR(it, EINA_FALSE); | ||
318 | |||
319 | if (idx >= eina_list_count(it->head)) | ||
320 | return EINA_FALSE; | ||
321 | |||
322 | if (it->index == idx) | ||
323 | over = it->current; | ||
324 | else if (idx > it->index) | ||
325 | { | ||
326 | /* After current position. */ | ||
327 | middle = ((eina_list_count(it->head) - it->index) >> 1) + it->index; | ||
328 | |||
329 | if (idx > middle) | ||
330 | /* Go backward from the end. */ | ||
331 | for (i = eina_list_count(it->head) - 1, | ||
332 | over = eina_list_last(it->head); | ||
333 | i > idx && over; | ||
334 | --i, over = eina_list_prev(over)) | ||
335 | ; | ||
336 | else | ||
337 | /* Go forward from current. */ | ||
338 | for (i = it->index, over = it->current; | ||
339 | i < idx && over; | ||
340 | ++i, over = eina_list_next(over)) | ||
341 | ; | ||
342 | } | ||
343 | else | ||
344 | { | ||
345 | /* Before current position. */ | ||
346 | middle = it->index >> 1; | ||
347 | |||
348 | if (idx > middle) | ||
349 | /* Go backward from current. */ | ||
350 | for (i = it->index, over = it->current; | ||
351 | i > idx && over; | ||
352 | --i, over = eina_list_prev(over)) | ||
353 | ; | ||
354 | else | ||
355 | /* Go forward from start. */ | ||
356 | for (i = 0, over = it->head; | ||
357 | i < idx && over; | ||
358 | ++i, over = eina_list_next(over)) | ||
359 | ; | ||
360 | } | ||
361 | |||
362 | if (!over) | ||
363 | return EINA_FALSE; | ||
364 | |||
365 | it->current = over; | ||
366 | it->index = idx; | ||
367 | |||
368 | *data = eina_list_data_get(it->current); | ||
369 | return EINA_TRUE; | ||
370 | } | ||
371 | |||
372 | static Eina_List * | ||
373 | eina_list_accessor_get_container(Eina_Accessor_List *it) | ||
374 | { | ||
375 | EINA_MAGIC_CHECK_LIST_ACCESSOR(it, NULL); | ||
376 | |||
377 | return (Eina_List *)it->head; | ||
378 | } | ||
379 | |||
380 | static void | ||
381 | eina_list_accessor_free(Eina_Accessor_List *it) | ||
382 | { | ||
383 | EINA_MAGIC_CHECK_LIST_ACCESSOR(it); | ||
384 | |||
385 | MAGIC_FREE(it); | ||
386 | } | ||
387 | |||
388 | static Eina_List * | ||
389 | eina_list_sort_rebuild_prev(Eina_List *list) | ||
390 | { | ||
391 | Eina_List *prev = NULL; | ||
392 | |||
393 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
394 | |||
395 | for (; list; list = list->next) | ||
396 | { | ||
397 | list->prev = prev; | ||
398 | prev = list; | ||
399 | } | ||
400 | |||
401 | return prev; | ||
402 | } | ||
403 | |||
404 | static Eina_List * | ||
405 | eina_list_sort_merge(Eina_List *a, Eina_List *b, Eina_Compare_Cb func) | ||
406 | { | ||
407 | Eina_List *first, *last; | ||
408 | |||
409 | if (func(a->data, b->data) < 0) | ||
410 | a = (last = first = a)->next; | ||
411 | else | ||
412 | b = (last = first = b)->next; | ||
413 | |||
414 | while (a && b) | ||
415 | if (func(a->data, b->data) < 0) | ||
416 | a = (last = last->next = a)->next; | ||
417 | else | ||
418 | b = (last = last->next = b)->next; | ||
419 | |||
420 | last->next = a ? a : b; | ||
421 | |||
422 | return first; | ||
423 | } | ||
424 | |||
425 | /** | ||
426 | * @endcond | ||
427 | */ | ||
428 | |||
429 | /*============================================================================* | ||
430 | * Global * | ||
431 | *============================================================================*/ | ||
432 | |||
433 | /** | ||
434 | * @internal | ||
435 | * @brief Initialize the list module. | ||
436 | * | ||
437 | * @return #EINA_TRUE on success, #EINA_FALSE on failure. | ||
438 | * | ||
439 | * This function sets up the list module of Eina. It is called by | ||
440 | * eina_init(). | ||
441 | * | ||
442 | * This function creates mempool to speed up list node and accounting | ||
443 | * management, using EINA_MEMPOOL environment variable if it is set to | ||
444 | * choose the memory pool type to use. | ||
445 | * | ||
446 | * @see eina_init() | ||
447 | */ | ||
448 | Eina_Bool | ||
449 | eina_list_init(void) | ||
450 | { | ||
451 | const char *choice, *tmp; | ||
452 | |||
453 | _eina_list_log_dom = eina_log_domain_register("eina_list", | ||
454 | EINA_LOG_COLOR_DEFAULT); | ||
455 | if (_eina_list_log_dom < 0) | ||
456 | { | ||
457 | EINA_LOG_ERR("Could not register log domain: eina_list"); | ||
458 | return EINA_FALSE; | ||
459 | } | ||
460 | |||
461 | #ifdef EINA_DEFAULT_MEMPOOL | ||
462 | choice = "pass_through"; | ||
463 | #else | ||
464 | choice = "chained_mempool"; | ||
465 | #endif | ||
466 | tmp = getenv("EINA_MEMPOOL"); | ||
467 | if (tmp && tmp[0]) | ||
468 | choice = tmp; | ||
469 | |||
470 | _eina_list_mp = eina_mempool_add | ||
471 | (choice, "list", NULL, sizeof(Eina_List), 320); | ||
472 | if (!_eina_list_mp) | ||
473 | { | ||
474 | ERR("ERROR: Mempool for list cannot be allocated in list init."); | ||
475 | goto on_init_fail; | ||
476 | } | ||
477 | |||
478 | _eina_list_accounting_mp = eina_mempool_add | ||
479 | (choice, "list_accounting", NULL, sizeof(Eina_List_Accounting), 80); | ||
480 | if (!_eina_list_accounting_mp) | ||
481 | { | ||
482 | ERR( | ||
483 | "ERROR: Mempool for list accounting cannot be allocated in list init."); | ||
484 | eina_mempool_del(_eina_list_mp); | ||
485 | goto on_init_fail; | ||
486 | } | ||
487 | |||
488 | #define EMS(n) eina_magic_string_static_set(n, n ## _STR) | ||
489 | EMS(EINA_MAGIC_LIST); | ||
490 | EMS(EINA_MAGIC_LIST_ITERATOR); | ||
491 | EMS(EINA_MAGIC_LIST_ACCESSOR); | ||
492 | EMS(EINA_MAGIC_LIST_ACCOUNTING); | ||
493 | #undef EMS | ||
494 | |||
495 | return EINA_TRUE; | ||
496 | |||
497 | on_init_fail: | ||
498 | eina_log_domain_unregister(_eina_list_log_dom); | ||
499 | _eina_list_log_dom = -1; | ||
500 | return EINA_FALSE; | ||
501 | } | ||
502 | |||
503 | /** | ||
504 | * @internal | ||
505 | * @brief Shut down the list module. | ||
506 | * | ||
507 | * @return #EINA_TRUE on success, #EINA_FALSE on failure. | ||
508 | * | ||
509 | * This function shuts down the list module set up by | ||
510 | * eina_list_init(). It is called by eina_shutdown(). | ||
511 | * | ||
512 | * @see eina_shutdown() | ||
513 | */ | ||
514 | Eina_Bool | ||
515 | eina_list_shutdown(void) | ||
516 | { | ||
517 | eina_mempool_del(_eina_list_accounting_mp); | ||
518 | eina_mempool_del(_eina_list_mp); | ||
519 | |||
520 | eina_log_domain_unregister(_eina_list_log_dom); | ||
521 | _eina_list_log_dom = -1; | ||
522 | return EINA_TRUE; | ||
523 | } | ||
524 | |||
525 | /*============================================================================* | ||
526 | * API * | ||
527 | *============================================================================*/ | ||
528 | |||
529 | EAPI Eina_List * | ||
530 | eina_list_append(Eina_List *list, const void *data) | ||
531 | { | ||
532 | Eina_List *l, *new_l; | ||
533 | |||
534 | eina_error_set(0); | ||
535 | new_l = _eina_list_mempool_list_new(list); | ||
536 | if (!new_l) | ||
537 | return list; | ||
538 | |||
539 | new_l->next = NULL; | ||
540 | new_l->data = (void *)data; | ||
541 | if (!list) | ||
542 | { | ||
543 | new_l->prev = NULL; | ||
544 | return _eina_list_setup_accounting(new_l); | ||
545 | } | ||
546 | |||
547 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
548 | |||
549 | l = list->accounting->last; | ||
550 | list->accounting->last = new_l; | ||
551 | |||
552 | l->next = new_l; | ||
553 | new_l->prev = l; | ||
554 | |||
555 | _eina_list_update_accounting(list, new_l); | ||
556 | return list; | ||
557 | } | ||
558 | |||
559 | EAPI Eina_List * | ||
560 | eina_list_prepend(Eina_List *list, const void *data) | ||
561 | { | ||
562 | Eina_List *new_l; | ||
563 | |||
564 | eina_error_set(0); | ||
565 | new_l = _eina_list_mempool_list_new(list); | ||
566 | if (!new_l) | ||
567 | return list; | ||
568 | |||
569 | new_l->prev = NULL; | ||
570 | new_l->next = list; | ||
571 | new_l->data = (void *)data; | ||
572 | |||
573 | if (!list) | ||
574 | return _eina_list_setup_accounting(new_l); | ||
575 | |||
576 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
577 | |||
578 | list->prev = new_l; | ||
579 | |||
580 | _eina_list_update_accounting(list, new_l); | ||
581 | |||
582 | return new_l; | ||
583 | } | ||
584 | |||
585 | EAPI Eina_List * | ||
586 | eina_list_append_relative(Eina_List *list, | ||
587 | const void *data, | ||
588 | const void *relative) | ||
589 | { | ||
590 | Eina_List *l; | ||
591 | void *list_data; | ||
592 | |||
593 | if (list) | ||
594 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
595 | |||
596 | EINA_LIST_FOREACH(list, l, list_data) | ||
597 | { | ||
598 | if (list_data == relative) | ||
599 | return eina_list_append_relative_list(list, data, l); | ||
600 | } | ||
601 | |||
602 | return eina_list_append(list, data); | ||
603 | } | ||
604 | |||
605 | EAPI Eina_List * | ||
606 | eina_list_append_relative_list(Eina_List *list, | ||
607 | const void *data, | ||
608 | Eina_List *relative) | ||
609 | { | ||
610 | Eina_List *new_l; | ||
611 | |||
612 | if ((!list) || (!relative)) | ||
613 | return eina_list_append(list, data); | ||
614 | |||
615 | eina_error_set(0); | ||
616 | new_l = _eina_list_mempool_list_new(list); | ||
617 | if (!new_l) | ||
618 | return list; | ||
619 | |||
620 | EINA_MAGIC_CHECK_LIST(relative, NULL); | ||
621 | new_l->next = relative->next; | ||
622 | new_l->data = (void *)data; | ||
623 | |||
624 | if (relative->next) | ||
625 | relative->next->prev = new_l; | ||
626 | |||
627 | relative->next = new_l; | ||
628 | new_l->prev = relative; | ||
629 | |||
630 | _eina_list_update_accounting(list, new_l); | ||
631 | |||
632 | if (!new_l->next) | ||
633 | new_l->accounting->last = new_l; | ||
634 | |||
635 | return list; | ||
636 | } | ||
637 | |||
638 | EAPI Eina_List * | ||
639 | eina_list_prepend_relative(Eina_List *list, | ||
640 | const void *data, | ||
641 | const void *relative) | ||
642 | { | ||
643 | Eina_List *l; | ||
644 | void *list_data; | ||
645 | |||
646 | if (list) | ||
647 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
648 | |||
649 | EINA_LIST_FOREACH(list, l, list_data) | ||
650 | { | ||
651 | if (list_data == relative) | ||
652 | return eina_list_prepend_relative_list(list, data, l); | ||
653 | } | ||
654 | return eina_list_prepend(list, data); | ||
655 | } | ||
656 | |||
657 | EAPI Eina_List * | ||
658 | eina_list_prepend_relative_list(Eina_List *list, | ||
659 | const void *data, | ||
660 | Eina_List *relative) | ||
661 | { | ||
662 | Eina_List *new_l; | ||
663 | |||
664 | if ((!list) || (!relative)) | ||
665 | return eina_list_prepend(list, data); | ||
666 | |||
667 | eina_error_set(0); | ||
668 | new_l = _eina_list_mempool_list_new(list); | ||
669 | if (!new_l) | ||
670 | return list; | ||
671 | |||
672 | EINA_MAGIC_CHECK_LIST(relative, NULL); | ||
673 | |||
674 | new_l->prev = relative->prev; | ||
675 | new_l->next = relative; | ||
676 | new_l->data = (void *)data; | ||
677 | |||
678 | if (relative->prev) | ||
679 | relative->prev->next = new_l; | ||
680 | |||
681 | relative->prev = new_l; | ||
682 | |||
683 | _eina_list_update_accounting(list, new_l); | ||
684 | |||
685 | if (new_l->prev) | ||
686 | return list; | ||
687 | |||
688 | return new_l; | ||
689 | } | ||
690 | |||
691 | EAPI Eina_List * | ||
692 | eina_list_sorted_insert(Eina_List *list, Eina_Compare_Cb func, const void *data) | ||
693 | { | ||
694 | Eina_List *lnear; | ||
695 | int cmp; | ||
696 | |||
697 | if (!list) | ||
698 | return eina_list_append(NULL, data); | ||
699 | |||
700 | lnear = eina_list_search_sorted_near_list(list, func, data, &cmp); | ||
701 | if (cmp < 0) | ||
702 | return eina_list_append_relative_list(list, data, lnear); | ||
703 | else | ||
704 | return eina_list_prepend_relative_list(list, data, lnear); | ||
705 | } | ||
706 | |||
707 | EAPI Eina_List * | ||
708 | eina_list_remove(Eina_List *list, const void *data) | ||
709 | { | ||
710 | Eina_List *l; | ||
711 | |||
712 | if (list) | ||
713 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
714 | |||
715 | l = eina_list_data_find_list(list, data); | ||
716 | return eina_list_remove_list(list, l); | ||
717 | } | ||
718 | |||
719 | EAPI Eina_List * | ||
720 | eina_list_remove_list(Eina_List *list, Eina_List *remove_list) | ||
721 | { | ||
722 | Eina_List *return_l; | ||
723 | |||
724 | if (!list) | ||
725 | return NULL; | ||
726 | |||
727 | if (!remove_list) | ||
728 | return list; | ||
729 | |||
730 | EINA_MAGIC_CHECK_LIST(remove_list, NULL); | ||
731 | |||
732 | if (remove_list->next) | ||
733 | remove_list->next->prev = remove_list->prev; | ||
734 | |||
735 | if (remove_list->prev) | ||
736 | { | ||
737 | remove_list->prev->next = remove_list->next; | ||
738 | return_l = list; | ||
739 | } | ||
740 | else | ||
741 | return_l = remove_list->next; | ||
742 | |||
743 | if (remove_list == remove_list->accounting->last) | ||
744 | { | ||
745 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
746 | list->accounting->last = remove_list->prev; | ||
747 | } | ||
748 | |||
749 | _eina_list_mempool_list_free(remove_list); | ||
750 | return return_l; | ||
751 | } | ||
752 | |||
753 | EAPI Eina_List * | ||
754 | eina_list_free(Eina_List *list) | ||
755 | { | ||
756 | Eina_List *l, *free_l; | ||
757 | |||
758 | if (!list) | ||
759 | return NULL; | ||
760 | |||
761 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
762 | |||
763 | for (l = list; l; ) | ||
764 | { | ||
765 | free_l = l; | ||
766 | l = l->next; | ||
767 | |||
768 | _eina_list_mempool_list_free(free_l); | ||
769 | } | ||
770 | |||
771 | return NULL; | ||
772 | } | ||
773 | |||
774 | EAPI Eina_List * | ||
775 | eina_list_promote_list(Eina_List *list, Eina_List *move_list) | ||
776 | { | ||
777 | if (!list) | ||
778 | return NULL; | ||
779 | |||
780 | if (!move_list) | ||
781 | { | ||
782 | return list; /* Promoting head to be head. */ | ||
783 | |||
784 | } | ||
785 | |||
786 | if (move_list == list) | ||
787 | return list; | ||
788 | |||
789 | if (move_list->next == list) | ||
790 | return move_list; | ||
791 | |||
792 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
793 | EINA_MAGIC_CHECK_LIST(move_list, NULL); | ||
794 | |||
795 | /* Remove the promoted item from the list. */ | ||
796 | if (!move_list->prev) | ||
797 | move_list->next->prev = NULL; | ||
798 | else | ||
799 | { | ||
800 | move_list->prev->next = move_list->next; | ||
801 | if (move_list == list->accounting->last) | ||
802 | list->accounting->last = move_list->prev; | ||
803 | else | ||
804 | move_list->next->prev = move_list->prev; | ||
805 | } | ||
806 | |||
807 | /* Add the promoted item in the list. */ | ||
808 | move_list->next = list; | ||
809 | move_list->prev = list->prev; | ||
810 | list->prev = move_list; | ||
811 | if (move_list->prev) | ||
812 | move_list->prev->next = move_list; | ||
813 | |||
814 | return move_list; | ||
815 | } | ||
816 | |||
817 | EAPI Eina_List * | ||
818 | eina_list_demote_list(Eina_List *list, Eina_List *move_list) | ||
819 | { | ||
820 | if (!list) | ||
821 | return NULL; | ||
822 | |||
823 | if (!move_list) | ||
824 | { | ||
825 | return list; /* Demoting tail to be tail. */ | ||
826 | |||
827 | } | ||
828 | |||
829 | if (move_list == list->accounting->last) | ||
830 | return list; | ||
831 | |||
832 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
833 | EINA_MAGIC_CHECK_LIST(move_list, NULL); | ||
834 | |||
835 | /* Update pointer list if necessary. */ | ||
836 | if (list == move_list) | ||
837 | { | ||
838 | list = move_list->next; /* Remove the demoted item from the list. */ | ||
839 | |||
840 | } | ||
841 | |||
842 | if (move_list->prev) | ||
843 | move_list->prev->next = move_list->next; | ||
844 | |||
845 | move_list->next->prev = move_list->prev; | ||
846 | /* Add the demoted item in the list. */ | ||
847 | move_list->prev = list->accounting->last; | ||
848 | move_list->prev->next = move_list; | ||
849 | move_list->next = NULL; | ||
850 | list->accounting->last = move_list; | ||
851 | |||
852 | return list; | ||
853 | } | ||
854 | |||
855 | EAPI void * | ||
856 | eina_list_data_find(const Eina_List *list, const void *data) | ||
857 | { | ||
858 | if (eina_list_data_find_list(list, data)) | ||
859 | return (void *)data; | ||
860 | |||
861 | return NULL; | ||
862 | } | ||
863 | |||
864 | EAPI Eina_Bool | ||
865 | eina_list_move(Eina_List **to, Eina_List **from, void *data) | ||
866 | { | ||
867 | Eina_List *l; | ||
868 | |||
869 | EINA_SAFETY_ON_NULL_RETURN_VAL(to, EINA_FALSE); | ||
870 | EINA_SAFETY_ON_NULL_RETURN_VAL(from, EINA_FALSE); | ||
871 | EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE); | ||
872 | |||
873 | if (*to) EINA_MAGIC_CHECK_LIST(*to, EINA_FALSE); | ||
874 | EINA_MAGIC_CHECK_LIST(*from, EINA_FALSE); | ||
875 | |||
876 | l = eina_list_data_find_list(*from, data); | ||
877 | EINA_SAFETY_ON_NULL_RETURN_VAL(l, EINA_FALSE); | ||
878 | |||
879 | *to = eina_list_append(*to, data); | ||
880 | *from = eina_list_remove_list(*from, l); | ||
881 | return EINA_TRUE; | ||
882 | } | ||
883 | |||
884 | EAPI Eina_Bool | ||
885 | eina_list_move_list(Eina_List **to, Eina_List **from, Eina_List *data) | ||
886 | { | ||
887 | EINA_SAFETY_ON_NULL_RETURN_VAL(to, EINA_FALSE); | ||
888 | EINA_SAFETY_ON_NULL_RETURN_VAL(from, EINA_FALSE); | ||
889 | |||
890 | if (*to) EINA_MAGIC_CHECK_LIST(*to, EINA_FALSE); | ||
891 | EINA_MAGIC_CHECK_LIST(*from, EINA_FALSE); | ||
892 | EINA_MAGIC_CHECK_LIST(data, EINA_FALSE); | ||
893 | |||
894 | *to = eina_list_append(*to, data->data); | ||
895 | *from = eina_list_remove_list(*from, data); | ||
896 | return EINA_TRUE; | ||
897 | } | ||
898 | |||
899 | EAPI Eina_List * | ||
900 | eina_list_data_find_list(const Eina_List *list, const void *data) | ||
901 | { | ||
902 | const Eina_List *l; | ||
903 | void *list_data; | ||
904 | |||
905 | if (list) | ||
906 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
907 | |||
908 | EINA_LIST_FOREACH(list, l, list_data) | ||
909 | { | ||
910 | if (list_data == data) | ||
911 | return (Eina_List *)l; | ||
912 | } | ||
913 | |||
914 | return NULL; | ||
915 | } | ||
916 | |||
917 | EAPI void * | ||
918 | eina_list_nth(const Eina_List *list, unsigned int n) | ||
919 | { | ||
920 | Eina_List *l; | ||
921 | |||
922 | l = eina_list_nth_list(list, n); | ||
923 | return l ? l->data : NULL; | ||
924 | } | ||
925 | |||
926 | EAPI Eina_List * | ||
927 | eina_list_nth_list(const Eina_List *list, unsigned int n) | ||
928 | { | ||
929 | const Eina_List *l; | ||
930 | unsigned int i; | ||
931 | |||
932 | if (list) | ||
933 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
934 | |||
935 | /* check for non-existing nodes */ | ||
936 | if ((!list) || (n > (list->accounting->count - 1))) | ||
937 | return NULL; | ||
938 | |||
939 | /* if the node is in the 2nd half of the list, search from the end | ||
940 | * else, search from the beginning. | ||
941 | */ | ||
942 | if (n > (list->accounting->count / 2)) | ||
943 | for (i = list->accounting->count - 1, | ||
944 | l = list->accounting->last; | ||
945 | l; | ||
946 | l = l->prev, i--) | ||
947 | { | ||
948 | if (i == n) | ||
949 | return (Eina_List *)l; | ||
950 | } | ||
951 | else | ||
952 | for (i = 0, l = list; l; l = l->next, i++) | ||
953 | { | ||
954 | if (i == n) | ||
955 | return (Eina_List *)l; | ||
956 | } | ||
957 | |||
958 | abort(); | ||
959 | } | ||
960 | |||
961 | EAPI Eina_List * | ||
962 | eina_list_reverse(Eina_List *list) | ||
963 | { | ||
964 | Eina_List *l1, *l2; | ||
965 | |||
966 | if (!list) | ||
967 | return NULL; | ||
968 | |||
969 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
970 | |||
971 | l1 = list; | ||
972 | l2 = list->accounting->last; | ||
973 | while (l1 != l2) | ||
974 | { | ||
975 | void *data; | ||
976 | |||
977 | data = l1->data; | ||
978 | l1->data = l2->data; | ||
979 | l2->data = data; | ||
980 | l1 = l1->next; | ||
981 | if (l1 == l2) | ||
982 | break; | ||
983 | |||
984 | l2 = l2->prev; | ||
985 | } | ||
986 | |||
987 | return list; | ||
988 | } | ||
989 | |||
990 | EAPI Eina_List * | ||
991 | eina_list_reverse_clone(const Eina_List *list) | ||
992 | { | ||
993 | const Eina_List *l; | ||
994 | Eina_List *lclone; | ||
995 | void *data; | ||
996 | |||
997 | if (!list) | ||
998 | return NULL; | ||
999 | |||
1000 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
1001 | |||
1002 | lclone = NULL; | ||
1003 | EINA_LIST_FOREACH(list, l, data) | ||
1004 | lclone = eina_list_prepend(lclone, data); | ||
1005 | |||
1006 | return lclone; | ||
1007 | } | ||
1008 | |||
1009 | EAPI Eina_List * | ||
1010 | eina_list_clone(const Eina_List *list) | ||
1011 | { | ||
1012 | const Eina_List *l; | ||
1013 | Eina_List *lclone; | ||
1014 | void *data; | ||
1015 | |||
1016 | if (!list) | ||
1017 | return NULL; | ||
1018 | |||
1019 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
1020 | |||
1021 | lclone = NULL; | ||
1022 | EINA_LIST_FOREACH(list, l, data) | ||
1023 | lclone = eina_list_append(lclone, data); | ||
1024 | |||
1025 | return lclone; | ||
1026 | } | ||
1027 | |||
1028 | EAPI Eina_List * | ||
1029 | eina_list_sort(Eina_List *list, unsigned int size, Eina_Compare_Cb func) | ||
1030 | { | ||
1031 | unsigned int i = 0; | ||
1032 | unsigned int n = 0; | ||
1033 | Eina_List *tail = list; | ||
1034 | Eina_List *unsort = NULL; | ||
1035 | Eina_List *stack[EINA_LIST_SORT_STACK_SIZE]; | ||
1036 | |||
1037 | EINA_SAFETY_ON_NULL_RETURN_VAL(func, list); | ||
1038 | if (!list) | ||
1039 | return NULL; | ||
1040 | |||
1041 | EINA_MAGIC_CHECK_LIST(list, NULL); | ||
1042 | |||
1043 | /* if the caller specified an invalid size, sort the whole list */ | ||
1044 | if ((size == 0) || | ||
1045 | (size > list->accounting->count)) | ||
1046 | size = list->accounting->count; | ||
1047 | |||
1048 | if (size != list->accounting->count) | ||
1049 | { | ||
1050 | unsort = eina_list_nth_list(list, size); | ||
1051 | if (unsort) | ||
1052 | unsort->prev->next = NULL; | ||
1053 | } | ||
1054 | |||
1055 | while (tail) | ||
1056 | { | ||
1057 | unsigned int idx, tmp; | ||
1058 | |||
1059 | Eina_List *a = tail; | ||
1060 | Eina_List *b = tail->next; | ||
1061 | |||
1062 | if (!b) | ||
1063 | { | ||
1064 | stack[i++] = a; | ||
1065 | break; | ||
1066 | } | ||
1067 | |||
1068 | tail = b->next; | ||
1069 | |||
1070 | if (func(a->data, b->data) < 0) | ||
1071 | ((stack[i++] = a)->next = b)->next = 0; | ||
1072 | else | ||
1073 | ((stack[i++] = b)->next = a)->next = 0; | ||
1074 | |||
1075 | tmp = n++; | ||
1076 | for (idx = n ^ tmp; idx &= idx - 1; i--) | ||
1077 | stack[i - 2] = eina_list_sort_merge(stack[i - 2], stack[i - 1], func); | ||
1078 | } | ||
1079 | |||
1080 | while (i-- > 1) | ||
1081 | stack[i - 1] = eina_list_sort_merge(stack[i - 1], stack[i], func); | ||
1082 | |||
1083 | list = stack[0]; | ||
1084 | tail = eina_list_sort_rebuild_prev(list); | ||
1085 | |||
1086 | if (unsort) | ||
1087 | { | ||
1088 | tail->next = unsort; | ||
1089 | unsort->prev = tail; | ||
1090 | } | ||
1091 | else | ||
1092 | list->accounting->last = tail; | ||
1093 | |||
1094 | return list; | ||
1095 | } | ||
1096 | |||
1097 | EAPI Eina_List * | ||
1098 | eina_list_merge(Eina_List *left, Eina_List *right) | ||
1099 | { | ||
1100 | unsigned int n_left, n_right; | ||
1101 | |||
1102 | if (!left) | ||
1103 | return right; | ||
1104 | |||
1105 | if (!right) | ||
1106 | return left; | ||
1107 | |||
1108 | left->accounting->last->next = right; | ||
1109 | right->prev = left->accounting->last; | ||
1110 | |||
1111 | n_left = left->accounting->count; | ||
1112 | n_right = right->accounting->count; | ||
1113 | |||
1114 | if (n_left >= n_right) | ||
1115 | { | ||
1116 | Eina_List *itr = right; | ||
1117 | left->accounting->last = right->accounting->last; | ||
1118 | left->accounting->count += n_right; | ||
1119 | |||
1120 | _eina_list_mempool_accounting_free(right->accounting); | ||
1121 | |||
1122 | do | ||
1123 | { | ||
1124 | itr->accounting = left->accounting; | ||
1125 | itr = itr->next; | ||
1126 | } | ||
1127 | while (itr); | ||
1128 | } | ||
1129 | else | ||
1130 | { | ||
1131 | Eina_List *itr = left->accounting->last; | ||
1132 | right->accounting->count += n_left; | ||
1133 | |||
1134 | _eina_list_mempool_accounting_free(left->accounting); | ||
1135 | |||
1136 | do | ||
1137 | { | ||
1138 | itr->accounting = right->accounting; | ||
1139 | itr = itr->prev; | ||
1140 | } | ||
1141 | while (itr); | ||
1142 | } | ||
1143 | |||
1144 | return left; | ||
1145 | } | ||
1146 | |||
1147 | |||
1148 | EAPI Eina_List * | ||
1149 | eina_list_split_list(Eina_List *list, Eina_List *relative, Eina_List **right) | ||
1150 | { | ||
1151 | Eina_List *next; | ||
1152 | Eina_List *itr; | ||
1153 | |||
1154 | if(!right) | ||
1155 | return list; | ||
1156 | |||
1157 | *right = NULL; | ||
1158 | |||
1159 | if (!list) | ||
1160 | return NULL; | ||
1161 | |||
1162 | if (!relative) | ||
1163 | { | ||
1164 | *right = list; | ||
1165 | return NULL; | ||
1166 | } | ||
1167 | |||
1168 | if (relative == eina_list_last(list)) | ||
1169 | return list; | ||
1170 | |||
1171 | next = eina_list_next(relative); | ||
1172 | next->prev = NULL; | ||
1173 | next->accounting = _eina_list_mempool_accounting_new(next); | ||
1174 | next->accounting->last = list->accounting->last; | ||
1175 | *right = next; | ||
1176 | |||
1177 | itr = next; | ||
1178 | do | ||
1179 | { | ||
1180 | itr->accounting = next->accounting; | ||
1181 | next->accounting->count++; | ||
1182 | itr = itr->next; | ||
1183 | } | ||
1184 | while (itr); | ||
1185 | |||
1186 | relative->next = NULL; | ||
1187 | list->accounting->last = relative; | ||
1188 | list->accounting->count = list->accounting->count - next->accounting->count; | ||
1189 | |||
1190 | return list; | ||
1191 | } | ||
1192 | |||
1193 | EAPI Eina_List * | ||
1194 | eina_list_sorted_merge(Eina_List *left, Eina_List *right, Eina_Compare_Cb func) | ||
1195 | { | ||
1196 | Eina_List *ret; | ||
1197 | Eina_List *current; | ||
1198 | |||
1199 | EINA_SAFETY_ON_NULL_RETURN_VAL(func, NULL); | ||
1200 | |||
1201 | if (!left) | ||
1202 | return right; | ||
1203 | |||
1204 | if (!right) | ||
1205 | return left; | ||
1206 | |||
1207 | if (func(left->data, right->data) < 0) | ||
1208 | { | ||
1209 | ret = left; | ||
1210 | current = left; | ||
1211 | left = left->next; | ||
1212 | ret->accounting->count += right->accounting->count; | ||
1213 | |||
1214 | _eina_list_mempool_accounting_free(right->accounting); | ||
1215 | } | ||
1216 | else | ||
1217 | { | ||
1218 | ret = right; | ||
1219 | current = right; | ||
1220 | right = right->next; | ||
1221 | ret->accounting->count += left->accounting->count; | ||
1222 | |||
1223 | _eina_list_mempool_accounting_free(left->accounting); | ||
1224 | } | ||
1225 | |||
1226 | while (left && right) | ||
1227 | { | ||
1228 | if (func(left->data, right->data) < 0) | ||
1229 | { | ||
1230 | current->next = left; | ||
1231 | left->prev = current; | ||
1232 | left = left->next; | ||
1233 | } | ||
1234 | else | ||
1235 | { | ||
1236 | current->next = right; | ||
1237 | right->prev = current; | ||
1238 | right = right->next; | ||
1239 | } | ||
1240 | |||
1241 | current = current->next; | ||
1242 | current->accounting = ret->accounting; | ||
1243 | } | ||
1244 | |||
1245 | if (left) | ||
1246 | { | ||
1247 | current->next = left; | ||
1248 | left->prev = current; | ||
1249 | current->accounting = ret->accounting; | ||
1250 | } | ||
1251 | |||
1252 | if (right) | ||
1253 | { | ||
1254 | current->next = right; | ||
1255 | right->prev = current; | ||
1256 | current->accounting = ret->accounting; | ||
1257 | } | ||
1258 | |||
1259 | while (current->next) | ||
1260 | { | ||
1261 | current = current->next; | ||
1262 | current->accounting = ret->accounting; | ||
1263 | } | ||
1264 | |||
1265 | ret->accounting->last = current; | ||
1266 | |||
1267 | return ret; | ||
1268 | } | ||
1269 | |||
1270 | EAPI Eina_List * | ||
1271 | eina_list_search_sorted_near_list(const Eina_List *list, | ||
1272 | Eina_Compare_Cb func, | ||
1273 | const void *data, | ||
1274 | int *result_cmp) | ||
1275 | { | ||
1276 | const Eina_List *ct; | ||
1277 | unsigned int inf, sup, cur; | ||
1278 | int cmp; | ||
1279 | |||
1280 | if (!list) | ||
1281 | { | ||
1282 | if (result_cmp) | ||
1283 | *result_cmp = 0; | ||
1284 | |||
1285 | return NULL; | ||
1286 | } | ||
1287 | |||
1288 | if (list->accounting->count == 1) | ||
1289 | { | ||
1290 | if (result_cmp) | ||
1291 | *result_cmp = func(list->data, data); | ||
1292 | |||
1293 | return (Eina_List *)list; | ||
1294 | } | ||
1295 | |||
1296 | /* list walk is expensive, do quick check: tail */ | ||
1297 | ct = list->accounting->last; | ||
1298 | cmp = func(ct->data, data); | ||
1299 | if (cmp <= 0) | ||
1300 | goto end; | ||
1301 | |||
1302 | /* list walk is expensive, do quick check: head */ | ||
1303 | ct = list; | ||
1304 | cmp = func(ct->data, data); | ||
1305 | if (cmp >= 0) | ||
1306 | goto end; | ||
1307 | |||
1308 | /* inclusive bounds */ | ||
1309 | inf = 1; | ||
1310 | sup = list->accounting->count - 2; | ||
1311 | cur = 1; | ||
1312 | ct = list->next; | ||
1313 | |||
1314 | /* no loop, just compare if comparison value is important to caller */ | ||
1315 | if (inf > sup) | ||
1316 | { | ||
1317 | if (result_cmp) | ||
1318 | cmp = func(ct->data, data); | ||
1319 | |||
1320 | goto end; | ||
1321 | } | ||
1322 | |||
1323 | while (inf <= sup) | ||
1324 | { | ||
1325 | unsigned int tmp = cur; | ||
1326 | cur = inf + ((sup - inf) >> 1); | ||
1327 | if (tmp < cur) | ||
1328 | for (; tmp != cur; tmp++, ct = ct->next) ; | ||
1329 | else if (tmp > cur) | ||
1330 | for (; tmp != cur; tmp--, ct = ct->prev) ; | ||
1331 | |||
1332 | cmp = func(ct->data, data); | ||
1333 | if (cmp == 0) | ||
1334 | break; | ||
1335 | else if (cmp < 0) | ||
1336 | inf = cur + 1; | ||
1337 | else if (cmp > 0) | ||
1338 | { | ||
1339 | if (cur > 0) | ||
1340 | sup = cur - 1; | ||
1341 | else | ||
1342 | break; | ||
1343 | } | ||
1344 | else | ||
1345 | break; | ||
1346 | } | ||
1347 | |||
1348 | end: | ||
1349 | if (result_cmp) | ||
1350 | *result_cmp = cmp; | ||
1351 | |||
1352 | return (Eina_List *)ct; | ||
1353 | } | ||
1354 | |||
1355 | EAPI Eina_List * | ||
1356 | eina_list_search_sorted_list(const Eina_List *list, | ||
1357 | Eina_Compare_Cb func, | ||
1358 | const void *data) | ||
1359 | { | ||
1360 | Eina_List *lnear; | ||
1361 | int cmp; | ||
1362 | |||
1363 | lnear = eina_list_search_sorted_near_list(list, func, data, &cmp); | ||
1364 | if (!lnear) | ||
1365 | return NULL; | ||
1366 | |||
1367 | if (cmp == 0) | ||
1368 | return lnear; | ||
1369 | |||
1370 | return NULL; | ||
1371 | } | ||
1372 | |||
1373 | |||
1374 | EAPI void * | ||
1375 | eina_list_search_sorted(const Eina_List *list, | ||
1376 | Eina_Compare_Cb func, | ||
1377 | const void *data) | ||
1378 | { | ||
1379 | return eina_list_data_get(eina_list_search_sorted_list(list, func, data)); | ||
1380 | } | ||
1381 | |||
1382 | EAPI Eina_List * | ||
1383 | eina_list_search_unsorted_list(const Eina_List *list, | ||
1384 | Eina_Compare_Cb func, | ||
1385 | const void *data) | ||
1386 | { | ||
1387 | const Eina_List *l; | ||
1388 | void *d; | ||
1389 | |||
1390 | EINA_LIST_FOREACH(list, l, d) | ||
1391 | { | ||
1392 | if (!func(d, data)) | ||
1393 | return (Eina_List *)l; | ||
1394 | } | ||
1395 | return NULL; | ||
1396 | } | ||
1397 | |||
1398 | EAPI void * | ||
1399 | eina_list_search_unsorted(const Eina_List *list, | ||
1400 | Eina_Compare_Cb func, | ||
1401 | const void *data) | ||
1402 | { | ||
1403 | return eina_list_data_get(eina_list_search_unsorted_list(list, func, data)); | ||
1404 | } | ||
1405 | |||
1406 | |||
1407 | EAPI Eina_Iterator * | ||
1408 | eina_list_iterator_new(const Eina_List *list) | ||
1409 | { | ||
1410 | Eina_Iterator_List *it; | ||
1411 | |||
1412 | eina_error_set(0); | ||
1413 | it = calloc(1, sizeof (Eina_Iterator_List)); | ||
1414 | if (!it) | ||
1415 | { | ||
1416 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
1417 | return NULL; | ||
1418 | } | ||
1419 | |||
1420 | EINA_MAGIC_SET(it, EINA_MAGIC_LIST_ITERATOR); | ||
1421 | EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR); | ||
1422 | |||
1423 | it->head = list; | ||
1424 | it->current = list; | ||
1425 | |||
1426 | it->iterator.version = EINA_ITERATOR_VERSION; | ||
1427 | it->iterator.next = FUNC_ITERATOR_NEXT(eina_list_iterator_next); | ||
1428 | it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER( | ||
1429 | eina_list_iterator_get_container); | ||
1430 | it->iterator.free = FUNC_ITERATOR_FREE(eina_list_iterator_free); | ||
1431 | |||
1432 | return &it->iterator; | ||
1433 | } | ||
1434 | |||
1435 | EAPI Eina_Iterator * | ||
1436 | eina_list_iterator_reversed_new(const Eina_List *list) | ||
1437 | { | ||
1438 | Eina_Iterator_List *it; | ||
1439 | |||
1440 | eina_error_set(0); | ||
1441 | it = calloc(1, sizeof (Eina_Iterator_List)); | ||
1442 | if (!it) | ||
1443 | { | ||
1444 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
1445 | return NULL; | ||
1446 | } | ||
1447 | |||
1448 | EINA_MAGIC_SET(it, EINA_MAGIC_LIST_ITERATOR); | ||
1449 | EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR); | ||
1450 | |||
1451 | it->head = eina_list_last(list); | ||
1452 | it->current = it->head; | ||
1453 | |||
1454 | it->iterator.version = EINA_ITERATOR_VERSION; | ||
1455 | it->iterator.next = FUNC_ITERATOR_NEXT(eina_list_iterator_prev); | ||
1456 | it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER( | ||
1457 | eina_list_iterator_get_container); | ||
1458 | it->iterator.free = FUNC_ITERATOR_FREE(eina_list_iterator_free); | ||
1459 | |||
1460 | return &it->iterator; | ||
1461 | } | ||
1462 | |||
1463 | EAPI Eina_Accessor * | ||
1464 | eina_list_accessor_new(const Eina_List *list) | ||
1465 | { | ||
1466 | Eina_Accessor_List *ac; | ||
1467 | |||
1468 | eina_error_set(0); | ||
1469 | ac = calloc(1, sizeof (Eina_Accessor_List)); | ||
1470 | if (!ac) | ||
1471 | { | ||
1472 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
1473 | return NULL; | ||
1474 | } | ||
1475 | |||
1476 | EINA_MAGIC_SET(ac, EINA_MAGIC_LIST_ACCESSOR); | ||
1477 | EINA_MAGIC_SET(&ac->accessor, EINA_MAGIC_ACCESSOR); | ||
1478 | |||
1479 | ac->head = list; | ||
1480 | ac->current = list; | ||
1481 | ac->index = 0; | ||
1482 | |||
1483 | ac->accessor.version = EINA_ACCESSOR_VERSION; | ||
1484 | ac->accessor.get_at = FUNC_ACCESSOR_GET_AT(eina_list_accessor_get_at); | ||
1485 | ac->accessor.get_container = FUNC_ACCESSOR_GET_CONTAINER( | ||
1486 | eina_list_accessor_get_container); | ||
1487 | ac->accessor.free = FUNC_ACCESSOR_FREE(eina_list_accessor_free); | ||
1488 | |||
1489 | return &ac->accessor; | ||
1490 | } | ||