diff options
Diffstat (limited to 'libraries/eina/src/lib/eina_inlist.c')
-rw-r--r-- | libraries/eina/src/lib/eina_inlist.c | 914 |
1 files changed, 0 insertions, 914 deletions
diff --git a/libraries/eina/src/lib/eina_inlist.c b/libraries/eina/src/lib/eina_inlist.c deleted file mode 100644 index c80f87b..0000000 --- a/libraries/eina/src/lib/eina_inlist.c +++ /dev/null | |||
@@ -1,914 +0,0 @@ | |||
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 | EINA_SAFETY_ON_NULL_RETURN_VAL(item, NULL); | ||
434 | |||
435 | for (l = list; l; l = l->next) { | ||
436 | if (l == item) | ||
437 | return item; | ||
438 | } | ||
439 | return NULL; | ||
440 | } | ||
441 | |||
442 | EAPI unsigned int | ||
443 | eina_inlist_count(const Eina_Inlist *list) | ||
444 | { | ||
445 | const Eina_Inlist *l; | ||
446 | unsigned int i = 0; | ||
447 | |||
448 | for (l = list; l; l = l->next) | ||
449 | i++; | ||
450 | |||
451 | return i; | ||
452 | } | ||
453 | |||
454 | EAPI int | ||
455 | eina_inlist_sorted_state_init(Eina_Inlist_Sorted_State *state, Eina_Inlist *list) | ||
456 | { | ||
457 | Eina_Inlist *ct = NULL; | ||
458 | int count = 0; | ||
459 | int jump_count = 1; | ||
460 | |||
461 | /* | ||
462 | * prepare a jump table to avoid doing unnecessary rewalk | ||
463 | * of the inlist as much as possible. | ||
464 | */ | ||
465 | for (ct = list; ct; ct = ct->next, jump_count++, count++) | ||
466 | { | ||
467 | if (jump_count == state->jump_div) | ||
468 | { | ||
469 | if (state->jump_limit == EINA_INLIST_JUMP_SIZE) | ||
470 | { | ||
471 | _eina_inlist_sorted_state_compact(state); | ||
472 | } | ||
473 | |||
474 | state->jump_table[state->jump_limit] = ct; | ||
475 | state->jump_limit++; | ||
476 | jump_count = 0; | ||
477 | } | ||
478 | } | ||
479 | |||
480 | state->inserted = count; | ||
481 | return count; | ||
482 | } | ||
483 | |||
484 | EAPI Eina_Inlist_Sorted_State * | ||
485 | eina_inlist_sorted_state_new(void) | ||
486 | { | ||
487 | Eina_Inlist_Sorted_State *r; | ||
488 | |||
489 | r = calloc(1, sizeof (Eina_Inlist_Sorted_State)); | ||
490 | if (!r) return NULL; | ||
491 | |||
492 | r->jump_div = 1; | ||
493 | |||
494 | return r; | ||
495 | } | ||
496 | |||
497 | EAPI void | ||
498 | eina_inlist_sorted_state_free(Eina_Inlist_Sorted_State *state) | ||
499 | { | ||
500 | free(state); | ||
501 | } | ||
502 | |||
503 | static void | ||
504 | _eina_inlist_sorted_state_insert(Eina_Inlist_Sorted_State *state, | ||
505 | unsigned short idx, | ||
506 | int offset) | ||
507 | { | ||
508 | Eina_Inlist *last; | ||
509 | int jump_count; | ||
510 | int start; | ||
511 | |||
512 | state->inserted++; | ||
513 | |||
514 | if (offset != 0) idx++; | ||
515 | for (; idx < state->jump_limit; idx++) | ||
516 | { | ||
517 | state->jump_table[idx] = state->jump_table[idx]->prev; | ||
518 | } | ||
519 | |||
520 | start = state->jump_limit - 3; | ||
521 | if (start < 0) | ||
522 | start = 0; | ||
523 | |||
524 | last = state->jump_table[start]; | ||
525 | start++; | ||
526 | |||
527 | /* Correctly rebuild end of list */ | ||
528 | for (jump_count = 0; last->next != NULL; last = last->next, jump_count++) | ||
529 | { | ||
530 | if (jump_count == state->jump_div) | ||
531 | { | ||
532 | if (state->jump_limit == start) | ||
533 | { | ||
534 | if (state->jump_limit == EINA_INLIST_JUMP_SIZE) | ||
535 | { | ||
536 | _eina_inlist_sorted_state_compact(state); | ||
537 | start = state->jump_limit - 1; | ||
538 | continue ; | ||
539 | } | ||
540 | else | ||
541 | { | ||
542 | state->jump_limit++; | ||
543 | } | ||
544 | } | ||
545 | |||
546 | state->jump_table[start++] = last; | ||
547 | jump_count = 0; | ||
548 | } | ||
549 | } | ||
550 | } | ||
551 | |||
552 | EAPI Eina_Inlist * | ||
553 | eina_inlist_sorted_insert(Eina_Inlist *list, | ||
554 | Eina_Inlist *item, | ||
555 | Eina_Compare_Cb func) | ||
556 | { | ||
557 | Eina_Inlist *ct = NULL; | ||
558 | Eina_Inlist_Sorted_State state; | ||
559 | int cmp = 0; | ||
560 | int inf, sup; | ||
561 | int cur = 0; | ||
562 | int count; | ||
563 | |||
564 | EINA_SAFETY_ON_NULL_RETURN_VAL(item, list); | ||
565 | EINA_SAFETY_ON_NULL_RETURN_VAL(func, list); | ||
566 | |||
567 | if (!list) return eina_inlist_append(NULL, item); | ||
568 | |||
569 | if (!list->next) | ||
570 | { | ||
571 | cmp = func(list, item); | ||
572 | |||
573 | if (cmp < 0) | ||
574 | return eina_inlist_append(list, item); | ||
575 | return eina_inlist_prepend(list, item); | ||
576 | } | ||
577 | |||
578 | state.jump_div = 1; | ||
579 | state.jump_limit = 0; | ||
580 | count = eina_inlist_sorted_state_init(&state, list); | ||
581 | |||
582 | /* | ||
583 | * now do a dychotomic search directly inside the jump_table. | ||
584 | */ | ||
585 | inf = 0; | ||
586 | sup = state.jump_limit - 1; | ||
587 | cur = 0; | ||
588 | ct = state.jump_table[cur]; | ||
589 | cmp = func(ct, item); | ||
590 | |||
591 | while (inf <= sup) | ||
592 | { | ||
593 | cur = inf + ((sup - inf) >> 1); | ||
594 | ct = state.jump_table[cur]; | ||
595 | |||
596 | cmp = func(ct, item); | ||
597 | if (cmp == 0) | ||
598 | break ; | ||
599 | else if (cmp < 0) | ||
600 | inf = cur + 1; | ||
601 | else if (cmp > 0) | ||
602 | { | ||
603 | if (cur > 0) | ||
604 | sup = cur - 1; | ||
605 | else | ||
606 | break; | ||
607 | } | ||
608 | else | ||
609 | break; | ||
610 | } | ||
611 | |||
612 | /* If at the beginning of the table and cmp < 0, | ||
613 | * insert just after the head */ | ||
614 | if (cur == 0 && cmp > 0) | ||
615 | return eina_inlist_prepend_relative(list, item, ct); | ||
616 | |||
617 | /* If at the end of the table and cmp >= 0, | ||
618 | * just append the item to the list */ | ||
619 | if (cmp < 0 && ct == list->last) | ||
620 | return eina_inlist_append(list, item); | ||
621 | |||
622 | /* | ||
623 | * Now do a dychotomic search between two entries inside the jump_table | ||
624 | */ | ||
625 | cur *= state.jump_div; | ||
626 | inf = cur - state.jump_div - 1; | ||
627 | sup = cur + state.jump_div + 1; | ||
628 | |||
629 | if (sup > count - 1) sup = count - 1; | ||
630 | if (inf < 0) inf = 0; | ||
631 | |||
632 | while (inf <= sup) | ||
633 | { | ||
634 | int tmp = cur; | ||
635 | |||
636 | cur = inf + ((sup - inf) >> 1); | ||
637 | if (tmp < cur) | ||
638 | for (; tmp != cur; tmp++, ct = ct->next); | ||
639 | else if (tmp > cur) | ||
640 | for (; tmp != cur; tmp--, ct = ct->prev); | ||
641 | |||
642 | cmp = func(ct, item); | ||
643 | if (cmp == 0) | ||
644 | break ; | ||
645 | else if (cmp < 0) | ||
646 | inf = cur + 1; | ||
647 | else if (cmp > 0) | ||
648 | { | ||
649 | if (cur > 0) | ||
650 | sup = cur - 1; | ||
651 | else | ||
652 | break; | ||
653 | } | ||
654 | else | ||
655 | break; | ||
656 | } | ||
657 | |||
658 | if (cmp <= 0) | ||
659 | return eina_inlist_append_relative(list, item, ct); | ||
660 | return eina_inlist_prepend_relative(list, item, ct); | ||
661 | } | ||
662 | |||
663 | EAPI Eina_Inlist * | ||
664 | eina_inlist_sorted_state_insert(Eina_Inlist *list, | ||
665 | Eina_Inlist *item, | ||
666 | Eina_Compare_Cb func, | ||
667 | Eina_Inlist_Sorted_State *state) | ||
668 | { | ||
669 | Eina_Inlist *ct = NULL; | ||
670 | int cmp = 0; | ||
671 | int inf, sup; | ||
672 | int cur = 0; | ||
673 | int count; | ||
674 | unsigned short head; | ||
675 | unsigned int offset; | ||
676 | |||
677 | if (!list) | ||
678 | { | ||
679 | state->inserted = 1; | ||
680 | state->jump_limit = 1; | ||
681 | state->jump_table[0] = item; | ||
682 | return eina_inlist_append(NULL, item); | ||
683 | } | ||
684 | |||
685 | if (!list->next) | ||
686 | { | ||
687 | cmp = func(list, item); | ||
688 | |||
689 | state->jump_limit = 2; | ||
690 | state->inserted = 2; | ||
691 | |||
692 | if (cmp < 0) | ||
693 | { | ||
694 | state->jump_table[1] = item; | ||
695 | return eina_inlist_append(list, item); | ||
696 | } | ||
697 | state->jump_table[1] = state->jump_table[0]; | ||
698 | state->jump_table[0] = item; | ||
699 | return eina_inlist_prepend(list, item); | ||
700 | } | ||
701 | |||
702 | count = state->inserted; | ||
703 | |||
704 | /* | ||
705 | * now do a dychotomic search directly inside the jump_table. | ||
706 | */ | ||
707 | inf = 0; | ||
708 | sup = state->jump_limit - 1; | ||
709 | cur = 0; | ||
710 | ct = state->jump_table[cur]; | ||
711 | cmp = func(ct, item); | ||
712 | |||
713 | while (inf <= sup) | ||
714 | { | ||
715 | cur = inf + ((sup - inf) >> 1); | ||
716 | ct = state->jump_table[cur]; | ||
717 | |||
718 | cmp = func(ct, item); | ||
719 | if (cmp == 0) | ||
720 | break ; | ||
721 | else if (cmp < 0) | ||
722 | inf = cur + 1; | ||
723 | else if (cmp > 0) | ||
724 | { | ||
725 | if (cur > 0) | ||
726 | sup = cur - 1; | ||
727 | else | ||
728 | break; | ||
729 | } | ||
730 | else | ||
731 | break; | ||
732 | } | ||
733 | |||
734 | /* If at the beginning of the table and cmp < 0, | ||
735 | * insert just after the head */ | ||
736 | if (cur == 0 && cmp > 0) | ||
737 | { | ||
738 | ct = eina_inlist_prepend_relative(list, item, ct); | ||
739 | _eina_inlist_sorted_state_insert(state, 0, 0); | ||
740 | return ct; | ||
741 | } | ||
742 | |||
743 | /* If at the end of the table and cmp >= 0, | ||
744 | * just append the item to the list */ | ||
745 | if (cmp < 0 && ct == list->last) | ||
746 | { | ||
747 | ct = eina_inlist_append(list, item); | ||
748 | _eina_inlist_sorted_state_insert(state, state->jump_limit - 1, 1); | ||
749 | return ct; | ||
750 | } | ||
751 | |||
752 | /* | ||
753 | * Now do a dychotomic search between two entries inside the jump_table | ||
754 | */ | ||
755 | cur *= state->jump_div; | ||
756 | inf = cur - state->jump_div - 1; | ||
757 | sup = cur + state->jump_div + 1; | ||
758 | |||
759 | if (sup > count - 1) sup = count - 1; | ||
760 | if (inf < 0) inf = 0; | ||
761 | |||
762 | while (inf <= sup) | ||
763 | { | ||
764 | int tmp = cur; | ||
765 | |||
766 | cur = inf + ((sup - inf) >> 1); | ||
767 | if (tmp < cur) | ||
768 | for (; tmp != cur; tmp++, ct = ct->next); | ||
769 | else if (tmp > cur) | ||
770 | for (; tmp != cur; tmp--, ct = ct->prev); | ||
771 | |||
772 | cmp = func(ct, item); | ||
773 | if (cmp == 0) | ||
774 | break ; | ||
775 | else if (cmp < 0) | ||
776 | inf = cur + 1; | ||
777 | else if (cmp > 0) | ||
778 | { | ||
779 | if (cur > 0) | ||
780 | sup = cur - 1; | ||
781 | else | ||
782 | break; | ||
783 | } | ||
784 | else | ||
785 | break; | ||
786 | } | ||
787 | |||
788 | if (cmp <= 0) | ||
789 | { | ||
790 | cur++; | ||
791 | |||
792 | ct = eina_inlist_append_relative(list, item, ct); | ||
793 | } | ||
794 | else | ||
795 | { | ||
796 | ct = eina_inlist_prepend_relative(list, item, ct); | ||
797 | } | ||
798 | |||
799 | head = cur / state->jump_div; | ||
800 | offset = cur % state->jump_div; | ||
801 | |||
802 | _eina_inlist_sorted_state_insert(state, head, offset); | ||
803 | return ct; | ||
804 | } | ||
805 | |||
806 | EAPI Eina_Inlist * | ||
807 | eina_inlist_sort(Eina_Inlist *head, Eina_Compare_Cb func) | ||
808 | { | ||
809 | unsigned int i = 0; | ||
810 | unsigned int n = 0; | ||
811 | Eina_Inlist *tail = head; | ||
812 | Eina_Inlist *unsort = NULL; | ||
813 | Eina_Inlist *stack[EINA_INLIST_SORT_STACK_SIZE]; | ||
814 | |||
815 | EINA_SAFETY_ON_NULL_RETURN_VAL(head, NULL); | ||
816 | EINA_SAFETY_ON_NULL_RETURN_VAL(func, head); | ||
817 | |||
818 | while (tail) | ||
819 | { | ||
820 | unsigned int idx, tmp; | ||
821 | |||
822 | Eina_Inlist *a = tail; | ||
823 | Eina_Inlist *b = tail->next; | ||
824 | |||
825 | if (!b) | ||
826 | { | ||
827 | stack[i++] = a; | ||
828 | break; | ||
829 | } | ||
830 | |||
831 | tail = b->next; | ||
832 | |||
833 | if (func(a, b) < 0) | ||
834 | ((stack[i++] = a)->next = b)->next = 0; | ||
835 | else | ||
836 | ((stack[i++] = b)->next = a)->next = 0; | ||
837 | |||
838 | tmp = n++; | ||
839 | for (idx = n ^ tmp; idx &= idx - 1; i--) | ||
840 | stack[i - 2] = eina_inlist_sort_merge(stack[i - 2], stack[i - 1], func); | ||
841 | } | ||
842 | |||
843 | while (i-- > 1) | ||
844 | stack[i - 1] = eina_inlist_sort_merge(stack[i - 1], stack[i], func); | ||
845 | |||
846 | head = stack[0]; | ||
847 | tail = eina_inlist_sort_rebuild_prev(head); | ||
848 | |||
849 | if (unsort) | ||
850 | { | ||
851 | tail->next = unsort; | ||
852 | unsort->prev = tail; | ||
853 | } | ||
854 | |||
855 | head->last = tail; | ||
856 | |||
857 | return head; | ||
858 | |||
859 | } | ||
860 | |||
861 | EAPI Eina_Iterator * | ||
862 | eina_inlist_iterator_new(const Eina_Inlist *list) | ||
863 | { | ||
864 | Eina_Iterator_Inlist *it; | ||
865 | |||
866 | eina_error_set(0); | ||
867 | it = calloc(1, sizeof (Eina_Iterator_Inlist)); | ||
868 | if (!it) | ||
869 | { | ||
870 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
871 | return NULL; | ||
872 | } | ||
873 | |||
874 | it->head = list; | ||
875 | it->current = list; | ||
876 | |||
877 | it->iterator.version = EINA_ITERATOR_VERSION; | ||
878 | it->iterator.next = FUNC_ITERATOR_NEXT(eina_inlist_iterator_next); | ||
879 | it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER( | ||
880 | eina_inlist_iterator_get_container); | ||
881 | it->iterator.free = FUNC_ITERATOR_FREE(eina_inlist_iterator_free); | ||
882 | |||
883 | EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR); | ||
884 | |||
885 | return &it->iterator; | ||
886 | } | ||
887 | |||
888 | EAPI Eina_Accessor * | ||
889 | eina_inlist_accessor_new(const Eina_Inlist *list) | ||
890 | { | ||
891 | Eina_Accessor_Inlist *ac; | ||
892 | |||
893 | eina_error_set(0); | ||
894 | ac = calloc(1, sizeof (Eina_Accessor_Inlist)); | ||
895 | if (!ac) | ||
896 | { | ||
897 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
898 | return NULL; | ||
899 | } | ||
900 | |||
901 | ac->head = list; | ||
902 | ac->current = list; | ||
903 | ac->index = 0; | ||
904 | |||
905 | ac->accessor.version = EINA_ACCESSOR_VERSION; | ||
906 | ac->accessor.get_at = FUNC_ACCESSOR_GET_AT(eina_inlist_accessor_get_at); | ||
907 | ac->accessor.get_container = FUNC_ACCESSOR_GET_CONTAINER( | ||
908 | eina_inlist_accessor_get_container); | ||
909 | ac->accessor.free = FUNC_ACCESSOR_FREE(eina_inlist_accessor_free); | ||
910 | |||
911 | EINA_MAGIC_SET(&ac->accessor, EINA_MAGIC_ACCESSOR); | ||
912 | |||
913 | return &ac->accessor; | ||
914 | } | ||