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_inlist.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 'libraries/eina/src/lib/eina_inlist.c')
-rw-r--r-- | libraries/eina/src/lib/eina_inlist.c | 909 |
1 files changed, 909 insertions, 0 deletions
diff --git a/libraries/eina/src/lib/eina_inlist.c b/libraries/eina/src/lib/eina_inlist.c new file mode 100644 index 0000000..75a2cc1 --- /dev/null +++ b/libraries/eina/src/lib/eina_inlist.c | |||
@@ -0,0 +1,909 @@ | |||
1 | /* EINA - EFL data type library | ||
2 | * Copyright (C) 2002-2008 Carsten Haitzler, Vincent Torri | ||
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 | #ifdef HAVE_CONFIG_H | ||
20 | # include "config.h" | ||
21 | #endif | ||
22 | |||
23 | #include <stdlib.h> | ||
24 | #include <assert.h> | ||
25 | |||
26 | #include <stdio.h> | ||
27 | |||
28 | #include "eina_config.h" | ||
29 | #include "eina_private.h" | ||
30 | #include "eina_error.h" | ||
31 | #include "eina_log.h" | ||
32 | |||
33 | /* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */ | ||
34 | #include "eina_safety_checks.h" | ||
35 | #include "eina_inlist.h" | ||
36 | |||
37 | /* FIXME: TODO please, refactor this :) */ | ||
38 | |||
39 | /*============================================================================* | ||
40 | * Local * | ||
41 | *============================================================================*/ | ||
42 | |||
43 | /** | ||
44 | * @cond LOCAL | ||
45 | */ | ||
46 | |||
47 | #define EINA_INLIST_SORT_STACK_SIZE 32 | ||
48 | |||
49 | typedef struct _Eina_Iterator_Inlist Eina_Iterator_Inlist; | ||
50 | typedef struct _Eina_Accessor_Inlist Eina_Accessor_Inlist; | ||
51 | |||
52 | struct _Eina_Iterator_Inlist | ||
53 | { | ||
54 | Eina_Iterator iterator; | ||
55 | const Eina_Inlist *head; | ||
56 | const Eina_Inlist *current; | ||
57 | }; | ||
58 | |||
59 | struct _Eina_Accessor_Inlist | ||
60 | { | ||
61 | Eina_Accessor accessor; | ||
62 | |||
63 | const Eina_Inlist *head; | ||
64 | const Eina_Inlist *current; | ||
65 | |||
66 | unsigned int index; | ||
67 | }; | ||
68 | |||
69 | struct _Eina_Inlist_Sorted_State | ||
70 | { | ||
71 | Eina_Inlist *jump_table[EINA_INLIST_JUMP_SIZE]; | ||
72 | |||
73 | unsigned short jump_limit; | ||
74 | int jump_div; | ||
75 | |||
76 | int inserted; | ||
77 | }; | ||
78 | |||
79 | static Eina_Bool | ||
80 | eina_inlist_iterator_next(Eina_Iterator_Inlist *it, void **data) { | ||
81 | if (!it->current) | ||
82 | return EINA_FALSE; | ||
83 | |||
84 | if (data) | ||
85 | *data = (void *)it->current; | ||
86 | |||
87 | it->current = it->current->next; | ||
88 | |||
89 | return EINA_TRUE; | ||
90 | } | ||
91 | |||
92 | static Eina_Inlist * | ||
93 | eina_inlist_iterator_get_container(Eina_Iterator_Inlist *it) { | ||
94 | return (Eina_Inlist *)it->head; | ||
95 | } | ||
96 | |||
97 | static void | ||
98 | eina_inlist_iterator_free(Eina_Iterator_Inlist *it) { | ||
99 | free(it); | ||
100 | } | ||
101 | |||
102 | static Eina_Bool | ||
103 | eina_inlist_accessor_get_at(Eina_Accessor_Inlist *it, | ||
104 | unsigned int idx, | ||
105 | void **data) { | ||
106 | const Eina_Inlist *over; | ||
107 | unsigned int middle; | ||
108 | unsigned int i; | ||
109 | |||
110 | if (it->index == idx) | ||
111 | over = it->current; | ||
112 | else if (idx > it->index) | ||
113 | /* Looking after current. */ | ||
114 | for (i = it->index, over = it->current; | ||
115 | i < idx && over; | ||
116 | ++i, over = over->next) | ||
117 | ; | ||
118 | else | ||
119 | { | ||
120 | middle = it->index >> 1; | ||
121 | |||
122 | if (idx > middle) | ||
123 | /* Looking backward from current. */ | ||
124 | for (i = it->index, over = it->current; | ||
125 | i > idx && over; | ||
126 | --i, over = over->prev) | ||
127 | ; | ||
128 | else | ||
129 | /* Looking from the start. */ | ||
130 | for (i = 0, over = it->head; | ||
131 | i < idx && over; | ||
132 | ++i, over = over->next) | ||
133 | ; | ||
134 | } | ||
135 | |||
136 | if (!over) | ||
137 | return EINA_FALSE; | ||
138 | |||
139 | it->current = over; | ||
140 | it->index = idx; | ||
141 | |||
142 | if (data) | ||
143 | *data = (void *)over; | ||
144 | |||
145 | return EINA_TRUE; | ||
146 | } | ||
147 | |||
148 | static Eina_Inlist * | ||
149 | eina_inlist_accessor_get_container(Eina_Accessor_Inlist *it) { | ||
150 | return (Eina_Inlist *)it->head; | ||
151 | } | ||
152 | |||
153 | static void | ||
154 | eina_inlist_accessor_free(Eina_Accessor_Inlist *it) { | ||
155 | free(it); | ||
156 | } | ||
157 | |||
158 | static Eina_Inlist * | ||
159 | eina_inlist_sort_merge(Eina_Inlist *a, Eina_Inlist *b, Eina_Compare_Cb func) | ||
160 | { | ||
161 | Eina_Inlist *first, *last; | ||
162 | |||
163 | if (func(a, b) < 0) | ||
164 | a = (last = first = a)->next; | ||
165 | else | ||
166 | b = (last = first = b)->next; | ||
167 | |||
168 | while (a && b) | ||
169 | if (func(a, b) < 0) | ||
170 | a = (last = last->next = a)->next; | ||
171 | else | ||
172 | b = (last = last->next = b)->next; | ||
173 | |||
174 | last->next = a ? a : b; | ||
175 | |||
176 | return first; | ||
177 | } | ||
178 | |||
179 | static Eina_Inlist * | ||
180 | eina_inlist_sort_rebuild_prev(Eina_Inlist *list) | ||
181 | { | ||
182 | Eina_Inlist *prev = NULL; | ||
183 | |||
184 | for (; list; list = list->next) | ||
185 | { | ||
186 | list->prev = prev; | ||
187 | prev = list; | ||
188 | } | ||
189 | |||
190 | return prev; | ||
191 | } | ||
192 | |||
193 | static void | ||
194 | _eina_inlist_sorted_state_compact(Eina_Inlist_Sorted_State *state) | ||
195 | { | ||
196 | unsigned short i, j; | ||
197 | |||
198 | /* compress the jump table */ | ||
199 | state->jump_div *= 2; | ||
200 | state->jump_limit /= 2; | ||
201 | |||
202 | for (i = 2, j = 1; | ||
203 | i < EINA_INLIST_JUMP_SIZE; | ||
204 | i += 2, j++) | ||
205 | state->jump_table[j] = state->jump_table[i]; | ||
206 | } | ||
207 | |||
208 | /** | ||
209 | * @endcond | ||
210 | */ | ||
211 | |||
212 | |||
213 | /*============================================================================* | ||
214 | * Global * | ||
215 | *============================================================================*/ | ||
216 | |||
217 | /*============================================================================* | ||
218 | * API * | ||
219 | *============================================================================*/ | ||
220 | |||
221 | EAPI Eina_Inlist * | ||
222 | eina_inlist_append(Eina_Inlist *list, Eina_Inlist *new_l) | ||
223 | { | ||
224 | Eina_Inlist *l; | ||
225 | |||
226 | EINA_SAFETY_ON_NULL_RETURN_VAL(new_l, list); | ||
227 | |||
228 | new_l->next = NULL; | ||
229 | if (!list) | ||
230 | { | ||
231 | new_l->prev = NULL; | ||
232 | new_l->last = new_l; | ||
233 | return new_l; | ||
234 | } | ||
235 | |||
236 | if (list->last) | ||
237 | l = list->last; | ||
238 | else | ||
239 | for (l = list; (l) && (l->next); l = l->next) | ||
240 | ; | ||
241 | |||
242 | l->next = new_l; | ||
243 | new_l->prev = l; | ||
244 | list->last = new_l; | ||
245 | return list; | ||
246 | } | ||
247 | |||
248 | EAPI Eina_Inlist * | ||
249 | eina_inlist_prepend(Eina_Inlist *list, Eina_Inlist *new_l) | ||
250 | { | ||
251 | EINA_SAFETY_ON_NULL_RETURN_VAL(new_l, list); | ||
252 | |||
253 | new_l->prev = NULL; | ||
254 | if (!list) | ||
255 | { | ||
256 | new_l->next = NULL; | ||
257 | new_l->last = new_l; | ||
258 | return new_l; | ||
259 | } | ||
260 | |||
261 | new_l->next = list; | ||
262 | list->prev = new_l; | ||
263 | new_l->last = list->last; | ||
264 | list->last = NULL; | ||
265 | return new_l; | ||
266 | } | ||
267 | |||
268 | EAPI Eina_Inlist * | ||
269 | eina_inlist_append_relative(Eina_Inlist *list, | ||
270 | Eina_Inlist *new_l, | ||
271 | Eina_Inlist *relative) | ||
272 | { | ||
273 | EINA_SAFETY_ON_NULL_RETURN_VAL(new_l, list); | ||
274 | |||
275 | if (relative) | ||
276 | { | ||
277 | if (relative->next) | ||
278 | { | ||
279 | new_l->next = relative->next; | ||
280 | relative->next->prev = new_l; | ||
281 | } | ||
282 | else | ||
283 | new_l->next = NULL; | ||
284 | |||
285 | relative->next = new_l; | ||
286 | new_l->prev = relative; | ||
287 | if (!new_l->next) | ||
288 | list->last = new_l; | ||
289 | |||
290 | return list; | ||
291 | } | ||
292 | |||
293 | return eina_inlist_append(list, new_l); | ||
294 | } | ||
295 | |||
296 | EAPI Eina_Inlist * | ||
297 | eina_inlist_prepend_relative(Eina_Inlist *list, | ||
298 | Eina_Inlist *new_l, | ||
299 | Eina_Inlist *relative) | ||
300 | { | ||
301 | EINA_SAFETY_ON_NULL_RETURN_VAL(new_l, list); | ||
302 | |||
303 | if (relative) | ||
304 | { | ||
305 | new_l->prev = relative->prev; | ||
306 | new_l->next = relative; | ||
307 | relative->prev = new_l; | ||
308 | if (new_l->prev) | ||
309 | { | ||
310 | new_l->prev->next = new_l; | ||
311 | /* new_l->next could not be NULL, as it was set to 'relative' */ | ||
312 | assert(new_l->next); | ||
313 | return list; | ||
314 | } | ||
315 | else | ||
316 | { | ||
317 | /* new_l->next could not be NULL, as it was set to 'relative' */ | ||
318 | assert(new_l->next); | ||
319 | |||
320 | new_l->last = list->last; | ||
321 | list->last = NULL; | ||
322 | return new_l; | ||
323 | } | ||
324 | } | ||
325 | |||
326 | return eina_inlist_prepend(list, new_l); | ||
327 | } | ||
328 | |||
329 | EAPI Eina_Inlist * | ||
330 | eina_inlist_remove(Eina_Inlist *list, Eina_Inlist *item) | ||
331 | { | ||
332 | Eina_Inlist *return_l; | ||
333 | |||
334 | /* checkme */ | ||
335 | EINA_SAFETY_ON_NULL_RETURN_VAL(list, NULL); | ||
336 | EINA_SAFETY_ON_NULL_RETURN_VAL(item, list); | ||
337 | if (EINA_UNLIKELY((item != list) && (!item->prev) && (!item->next))) | ||
338 | { | ||
339 | eina_error_set(EINA_ERROR_SAFETY_FAILED); | ||
340 | EINA_LOG_ERR("safety check failed: item %p does not appear to be part of an inlist!", item); | ||
341 | return list; | ||
342 | } | ||
343 | |||
344 | if (item->next) | ||
345 | item->next->prev = item->prev; | ||
346 | |||
347 | if (item->prev) | ||
348 | { | ||
349 | item->prev->next = item->next; | ||
350 | return_l = list; | ||
351 | } | ||
352 | else | ||
353 | { | ||
354 | return_l = item->next; | ||
355 | if (return_l) | ||
356 | return_l->last = list->last; | ||
357 | } | ||
358 | |||
359 | if (item == list->last) | ||
360 | list->last = item->prev; | ||
361 | |||
362 | item->next = NULL; | ||
363 | item->prev = NULL; | ||
364 | return return_l; | ||
365 | } | ||
366 | |||
367 | EAPI Eina_Inlist * | ||
368 | eina_inlist_promote(Eina_Inlist *list, Eina_Inlist *item) | ||
369 | { | ||
370 | EINA_SAFETY_ON_NULL_RETURN_VAL(list, NULL); | ||
371 | EINA_SAFETY_ON_NULL_RETURN_VAL(item, list); | ||
372 | |||
373 | if (item == list) | ||
374 | return list; | ||
375 | |||
376 | if (item->next) | ||
377 | item->next->prev = item->prev; | ||
378 | |||
379 | item->prev->next = item->next; | ||
380 | |||
381 | if (list->last == item) | ||
382 | list->last = item->prev; | ||
383 | |||
384 | item->next = list; | ||
385 | item->prev = NULL; | ||
386 | item->last = list->last; | ||
387 | |||
388 | list->prev = item; | ||
389 | list->last = NULL; | ||
390 | |||
391 | return item; | ||
392 | } | ||
393 | |||
394 | EAPI Eina_Inlist * | ||
395 | eina_inlist_demote(Eina_Inlist *list, Eina_Inlist *item) | ||
396 | { | ||
397 | Eina_Inlist *l; | ||
398 | |||
399 | EINA_SAFETY_ON_NULL_RETURN_VAL(list, NULL); | ||
400 | EINA_SAFETY_ON_NULL_RETURN_VAL(item, list); | ||
401 | |||
402 | if (list->last == item) | ||
403 | return list; | ||
404 | |||
405 | if (!list->last) | ||
406 | { | ||
407 | for (l = list; l->next; l = l->next) | ||
408 | ; | ||
409 | list->last = l; | ||
410 | } | ||
411 | |||
412 | l = list; | ||
413 | if (item->prev) | ||
414 | item->prev->next = item->next; | ||
415 | else | ||
416 | l = item->next; | ||
417 | |||
418 | item->next->prev = item->prev; | ||
419 | |||
420 | list->last->next = item; | ||
421 | item->prev = list->last; | ||
422 | item->next = NULL; | ||
423 | |||
424 | l->last = item; | ||
425 | return l; | ||
426 | } | ||
427 | |||
428 | EAPI Eina_Inlist * | ||
429 | eina_inlist_find(Eina_Inlist *list, Eina_Inlist *item) | ||
430 | { | ||
431 | Eina_Inlist *l; | ||
432 | |||
433 | for (l = list; l; l = l->next) { | ||
434 | if (l == item) | ||
435 | return item; | ||
436 | } | ||
437 | return NULL; | ||
438 | } | ||
439 | |||
440 | EAPI unsigned int | ||
441 | eina_inlist_count(const Eina_Inlist *list) | ||
442 | { | ||
443 | const Eina_Inlist *l; | ||
444 | unsigned int i = 0; | ||
445 | |||
446 | for (l = list; l; l = l->next) | ||
447 | i++; | ||
448 | |||
449 | return i; | ||
450 | } | ||
451 | |||
452 | EAPI int | ||
453 | eina_inlist_sorted_state_init(Eina_Inlist_Sorted_State *state, Eina_Inlist *list) | ||
454 | { | ||
455 | Eina_Inlist *ct = NULL; | ||
456 | int count = 0; | ||
457 | int jump_count = 1; | ||
458 | |||
459 | /* | ||
460 | * prepare a jump table to avoid doing unnecessary rewalk | ||
461 | * of the inlist as much as possible. | ||
462 | */ | ||
463 | for (ct = list; ct; ct = ct->next, jump_count++, count++) | ||
464 | { | ||
465 | if (jump_count == state->jump_div) | ||
466 | { | ||
467 | if (state->jump_limit == EINA_INLIST_JUMP_SIZE) | ||
468 | { | ||
469 | _eina_inlist_sorted_state_compact(state); | ||
470 | } | ||
471 | |||
472 | state->jump_table[state->jump_limit] = ct; | ||
473 | state->jump_limit++; | ||
474 | jump_count = 0; | ||
475 | } | ||
476 | } | ||
477 | |||
478 | state->inserted = count; | ||
479 | return count; | ||
480 | } | ||
481 | |||
482 | EAPI Eina_Inlist_Sorted_State * | ||
483 | eina_inlist_sorted_state_new(void) | ||
484 | { | ||
485 | Eina_Inlist_Sorted_State *r; | ||
486 | |||
487 | r = calloc(1, sizeof (Eina_Inlist_Sorted_State)); | ||
488 | if (!r) return NULL; | ||
489 | |||
490 | r->jump_div = 1; | ||
491 | |||
492 | return r; | ||
493 | } | ||
494 | |||
495 | EAPI void | ||
496 | eina_inlist_sorted_state_free(Eina_Inlist_Sorted_State *state) | ||
497 | { | ||
498 | free(state); | ||
499 | } | ||
500 | |||
501 | static void | ||
502 | _eina_inlist_sorted_state_insert(Eina_Inlist_Sorted_State *state, | ||
503 | unsigned short idx, | ||
504 | int offset) | ||
505 | { | ||
506 | Eina_Inlist *last; | ||
507 | int jump_count; | ||
508 | int start; | ||
509 | |||
510 | state->inserted++; | ||
511 | |||
512 | if (offset != 0) idx++; | ||
513 | for (; idx < state->jump_limit; idx++) | ||
514 | { | ||
515 | state->jump_table[idx] = state->jump_table[idx]->prev; | ||
516 | } | ||
517 | |||
518 | start = state->jump_limit - 3; | ||
519 | if (start < 0) | ||
520 | start = 0; | ||
521 | |||
522 | last = state->jump_table[start]; | ||
523 | start++; | ||
524 | |||
525 | /* Correctly rebuild end of list */ | ||
526 | for (jump_count = 0; last->next != NULL; last = last->next, jump_count++) | ||
527 | { | ||
528 | if (jump_count == state->jump_div) | ||
529 | { | ||
530 | if (state->jump_limit == start) | ||
531 | { | ||
532 | if (state->jump_limit == EINA_INLIST_JUMP_SIZE) | ||
533 | { | ||
534 | _eina_inlist_sorted_state_compact(state); | ||
535 | start = state->jump_limit - 1; | ||
536 | continue ; | ||
537 | } | ||
538 | else | ||
539 | { | ||
540 | state->jump_limit++; | ||
541 | } | ||
542 | } | ||
543 | |||
544 | state->jump_table[start++] = last; | ||
545 | jump_count = 0; | ||
546 | } | ||
547 | } | ||
548 | } | ||
549 | |||
550 | EAPI Eina_Inlist * | ||
551 | eina_inlist_sorted_insert(Eina_Inlist *list, | ||
552 | Eina_Inlist *item, | ||
553 | Eina_Compare_Cb func) | ||
554 | { | ||
555 | Eina_Inlist *ct = NULL; | ||
556 | Eina_Inlist_Sorted_State state; | ||
557 | int cmp = 0; | ||
558 | int inf, sup; | ||
559 | int cur = 0; | ||
560 | int count; | ||
561 | |||
562 | if (!list) return eina_inlist_append(NULL, item); | ||
563 | |||
564 | if (!list->next) | ||
565 | { | ||
566 | cmp = func(list, item); | ||
567 | |||
568 | if (cmp < 0) | ||
569 | return eina_inlist_append(list, item); | ||
570 | return eina_inlist_prepend(list, item); | ||
571 | } | ||
572 | |||
573 | state.jump_div = 1; | ||
574 | state.jump_limit = 0; | ||
575 | count = eina_inlist_sorted_state_init(&state, list); | ||
576 | |||
577 | /* | ||
578 | * now do a dychotomic search directly inside the jump_table. | ||
579 | */ | ||
580 | inf = 0; | ||
581 | sup = state.jump_limit - 1; | ||
582 | cur = 0; | ||
583 | ct = state.jump_table[cur]; | ||
584 | cmp = func(ct, item); | ||
585 | |||
586 | while (inf <= sup) | ||
587 | { | ||
588 | cur = inf + ((sup - inf) >> 1); | ||
589 | ct = state.jump_table[cur]; | ||
590 | |||
591 | cmp = func(ct, item); | ||
592 | if (cmp == 0) | ||
593 | break ; | ||
594 | else if (cmp < 0) | ||
595 | inf = cur + 1; | ||
596 | else if (cmp > 0) | ||
597 | { | ||
598 | if (cur > 0) | ||
599 | sup = cur - 1; | ||
600 | else | ||
601 | break; | ||
602 | } | ||
603 | else | ||
604 | break; | ||
605 | } | ||
606 | |||
607 | /* If at the beginning of the table and cmp < 0, | ||
608 | * insert just after the head */ | ||
609 | if (cur == 0 && cmp > 0) | ||
610 | return eina_inlist_prepend_relative(list, item, ct); | ||
611 | |||
612 | /* If at the end of the table and cmp >= 0, | ||
613 | * just append the item to the list */ | ||
614 | if (cmp < 0 && ct == list->last) | ||
615 | return eina_inlist_append(list, item); | ||
616 | |||
617 | /* | ||
618 | * Now do a dychotomic search between two entries inside the jump_table | ||
619 | */ | ||
620 | cur *= state.jump_div; | ||
621 | inf = cur - state.jump_div - 1; | ||
622 | sup = cur + state.jump_div + 1; | ||
623 | |||
624 | if (sup > count - 1) sup = count - 1; | ||
625 | if (inf < 0) inf = 0; | ||
626 | |||
627 | while (inf <= sup) | ||
628 | { | ||
629 | int tmp = cur; | ||
630 | |||
631 | cur = inf + ((sup - inf) >> 1); | ||
632 | if (tmp < cur) | ||
633 | for (; tmp != cur; tmp++, ct = ct->next); | ||
634 | else if (tmp > cur) | ||
635 | for (; tmp != cur; tmp--, ct = ct->prev); | ||
636 | |||
637 | cmp = func(ct, item); | ||
638 | if (cmp == 0) | ||
639 | break ; | ||
640 | else if (cmp < 0) | ||
641 | inf = cur + 1; | ||
642 | else if (cmp > 0) | ||
643 | { | ||
644 | if (cur > 0) | ||
645 | sup = cur - 1; | ||
646 | else | ||
647 | break; | ||
648 | } | ||
649 | else | ||
650 | break; | ||
651 | } | ||
652 | |||
653 | if (cmp <= 0) | ||
654 | return eina_inlist_append_relative(list, item, ct); | ||
655 | return eina_inlist_prepend_relative(list, item, ct); | ||
656 | } | ||
657 | |||
658 | EAPI Eina_Inlist * | ||
659 | eina_inlist_sorted_state_insert(Eina_Inlist *list, | ||
660 | Eina_Inlist *item, | ||
661 | Eina_Compare_Cb func, | ||
662 | Eina_Inlist_Sorted_State *state) | ||
663 | { | ||
664 | Eina_Inlist *ct = NULL; | ||
665 | int cmp = 0; | ||
666 | int inf, sup; | ||
667 | int cur = 0; | ||
668 | int count; | ||
669 | unsigned short head; | ||
670 | unsigned int offset; | ||
671 | |||
672 | if (!list) | ||
673 | { | ||
674 | state->inserted = 1; | ||
675 | state->jump_limit = 1; | ||
676 | state->jump_table[0] = item; | ||
677 | return eina_inlist_append(NULL, item); | ||
678 | } | ||
679 | |||
680 | if (!list->next) | ||
681 | { | ||
682 | cmp = func(list, item); | ||
683 | |||
684 | state->jump_limit = 2; | ||
685 | state->inserted = 2; | ||
686 | |||
687 | if (cmp < 0) | ||
688 | { | ||
689 | state->jump_table[1] = item; | ||
690 | return eina_inlist_append(list, item); | ||
691 | } | ||
692 | state->jump_table[1] = state->jump_table[0]; | ||
693 | state->jump_table[0] = item; | ||
694 | return eina_inlist_prepend(list, item); | ||
695 | } | ||
696 | |||
697 | count = state->inserted; | ||
698 | |||
699 | /* | ||
700 | * now do a dychotomic search directly inside the jump_table. | ||
701 | */ | ||
702 | inf = 0; | ||
703 | sup = state->jump_limit - 1; | ||
704 | cur = 0; | ||
705 | ct = state->jump_table[cur]; | ||
706 | cmp = func(ct, item); | ||
707 | |||
708 | while (inf <= sup) | ||
709 | { | ||
710 | cur = inf + ((sup - inf) >> 1); | ||
711 | ct = state->jump_table[cur]; | ||
712 | |||
713 | cmp = func(ct, item); | ||
714 | if (cmp == 0) | ||
715 | break ; | ||
716 | else if (cmp < 0) | ||
717 | inf = cur + 1; | ||
718 | else if (cmp > 0) | ||
719 | { | ||
720 | if (cur > 0) | ||
721 | sup = cur - 1; | ||
722 | else | ||
723 | break; | ||
724 | } | ||
725 | else | ||
726 | break; | ||
727 | } | ||
728 | |||
729 | /* If at the beginning of the table and cmp < 0, | ||
730 | * insert just after the head */ | ||
731 | if (cur == 0 && cmp > 0) | ||
732 | { | ||
733 | ct = eina_inlist_prepend_relative(list, item, ct); | ||
734 | _eina_inlist_sorted_state_insert(state, 0, 0); | ||
735 | return ct; | ||
736 | } | ||
737 | |||
738 | /* If at the end of the table and cmp >= 0, | ||
739 | * just append the item to the list */ | ||
740 | if (cmp < 0 && ct == list->last) | ||
741 | { | ||
742 | ct = eina_inlist_append(list, item); | ||
743 | _eina_inlist_sorted_state_insert(state, state->jump_limit - 1, 1); | ||
744 | return ct; | ||
745 | } | ||
746 | |||
747 | /* | ||
748 | * Now do a dychotomic search between two entries inside the jump_table | ||
749 | */ | ||
750 | cur *= state->jump_div; | ||
751 | inf = cur - state->jump_div - 1; | ||
752 | sup = cur + state->jump_div + 1; | ||
753 | |||
754 | if (sup > count - 1) sup = count - 1; | ||
755 | if (inf < 0) inf = 0; | ||
756 | |||
757 | while (inf <= sup) | ||
758 | { | ||
759 | int tmp = cur; | ||
760 | |||
761 | cur = inf + ((sup - inf) >> 1); | ||
762 | if (tmp < cur) | ||
763 | for (; tmp != cur; tmp++, ct = ct->next); | ||
764 | else if (tmp > cur) | ||
765 | for (; tmp != cur; tmp--, ct = ct->prev); | ||
766 | |||
767 | cmp = func(ct, item); | ||
768 | if (cmp == 0) | ||
769 | break ; | ||
770 | else if (cmp < 0) | ||
771 | inf = cur + 1; | ||
772 | else if (cmp > 0) | ||
773 | { | ||
774 | if (cur > 0) | ||
775 | sup = cur - 1; | ||
776 | else | ||
777 | break; | ||
778 | } | ||
779 | else | ||
780 | break; | ||
781 | } | ||
782 | |||
783 | if (cmp <= 0) | ||
784 | { | ||
785 | cur++; | ||
786 | |||
787 | ct = eina_inlist_append_relative(list, item, ct); | ||
788 | } | ||
789 | else | ||
790 | { | ||
791 | ct = eina_inlist_prepend_relative(list, item, ct); | ||
792 | } | ||
793 | |||
794 | head = cur / state->jump_div; | ||
795 | offset = cur % state->jump_div; | ||
796 | |||
797 | _eina_inlist_sorted_state_insert(state, head, offset); | ||
798 | return ct; | ||
799 | } | ||
800 | |||
801 | EAPI Eina_Inlist * | ||
802 | eina_inlist_sort(Eina_Inlist *head, Eina_Compare_Cb func) | ||
803 | { | ||
804 | unsigned int i = 0; | ||
805 | unsigned int n = 0; | ||
806 | Eina_Inlist *tail = head; | ||
807 | Eina_Inlist *unsort = NULL; | ||
808 | Eina_Inlist *stack[EINA_INLIST_SORT_STACK_SIZE]; | ||
809 | |||
810 | EINA_SAFETY_ON_NULL_RETURN_VAL(head, NULL); | ||
811 | EINA_SAFETY_ON_NULL_RETURN_VAL(func, head); | ||
812 | |||
813 | while (tail) | ||
814 | { | ||
815 | unsigned int idx, tmp; | ||
816 | |||
817 | Eina_Inlist *a = tail; | ||
818 | Eina_Inlist *b = tail->next; | ||
819 | |||
820 | if (!b) | ||
821 | { | ||
822 | stack[i++] = a; | ||
823 | break; | ||
824 | } | ||
825 | |||
826 | tail = b->next; | ||
827 | |||
828 | if (func(a, b) < 0) | ||
829 | ((stack[i++] = a)->next = b)->next = 0; | ||
830 | else | ||
831 | ((stack[i++] = b)->next = a)->next = 0; | ||
832 | |||
833 | tmp = n++; | ||
834 | for (idx = n ^ tmp; idx &= idx - 1; i--) | ||
835 | stack[i - 2] = eina_inlist_sort_merge(stack[i - 2], stack[i - 1], func); | ||
836 | } | ||
837 | |||
838 | while (i-- > 1) | ||
839 | stack[i - 1] = eina_inlist_sort_merge(stack[i - 1], stack[i], func); | ||
840 | |||
841 | head = stack[0]; | ||
842 | tail = eina_inlist_sort_rebuild_prev(head); | ||
843 | |||
844 | if (unsort) | ||
845 | { | ||
846 | tail->next = unsort; | ||
847 | unsort->prev = tail; | ||
848 | } | ||
849 | |||
850 | head->last = tail; | ||
851 | |||
852 | return head; | ||
853 | |||
854 | } | ||
855 | |||
856 | EAPI Eina_Iterator * | ||
857 | eina_inlist_iterator_new(const Eina_Inlist *list) | ||
858 | { | ||
859 | Eina_Iterator_Inlist *it; | ||
860 | |||
861 | eina_error_set(0); | ||
862 | it = calloc(1, sizeof (Eina_Iterator_Inlist)); | ||
863 | if (!it) | ||
864 | { | ||
865 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
866 | return NULL; | ||
867 | } | ||
868 | |||
869 | it->head = list; | ||
870 | it->current = list; | ||
871 | |||
872 | it->iterator.version = EINA_ITERATOR_VERSION; | ||
873 | it->iterator.next = FUNC_ITERATOR_NEXT(eina_inlist_iterator_next); | ||
874 | it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER( | ||
875 | eina_inlist_iterator_get_container); | ||
876 | it->iterator.free = FUNC_ITERATOR_FREE(eina_inlist_iterator_free); | ||
877 | |||
878 | EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR); | ||
879 | |||
880 | return &it->iterator; | ||
881 | } | ||
882 | |||
883 | EAPI Eina_Accessor * | ||
884 | eina_inlist_accessor_new(const Eina_Inlist *list) | ||
885 | { | ||
886 | Eina_Accessor_Inlist *ac; | ||
887 | |||
888 | eina_error_set(0); | ||
889 | ac = calloc(1, sizeof (Eina_Accessor_Inlist)); | ||
890 | if (!ac) | ||
891 | { | ||
892 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
893 | return NULL; | ||
894 | } | ||
895 | |||
896 | ac->head = list; | ||
897 | ac->current = list; | ||
898 | ac->index = 0; | ||
899 | |||
900 | ac->accessor.version = EINA_ACCESSOR_VERSION; | ||
901 | ac->accessor.get_at = FUNC_ACCESSOR_GET_AT(eina_inlist_accessor_get_at); | ||
902 | ac->accessor.get_container = FUNC_ACCESSOR_GET_CONTAINER( | ||
903 | eina_inlist_accessor_get_container); | ||
904 | ac->accessor.free = FUNC_ACCESSOR_FREE(eina_inlist_accessor_free); | ||
905 | |||
906 | EINA_MAGIC_SET(&ac->accessor, EINA_MAGIC_ACCESSOR); | ||
907 | |||
908 | return &ac->accessor; | ||
909 | } | ||