diff options
author | David Walter Seikel | 2012-04-22 09:19:23 +1000 |
---|---|---|
committer | David Walter Seikel | 2012-04-22 09:19:23 +1000 |
commit | c963d75dfdeec11f82e79e727062fbf89afa2c04 (patch) | |
tree | 895633dbf641110be46f117c29890c49b3ffc0bd /libraries/eina/src/lib/eina_rbtree.c | |
parent | Adding the new extantz viewer and grid manager. (diff) | |
download | SledjHamr-c963d75dfdeec11f82e79e727062fbf89afa2c04.zip SledjHamr-c963d75dfdeec11f82e79e727062fbf89afa2c04.tar.gz SledjHamr-c963d75dfdeec11f82e79e727062fbf89afa2c04.tar.bz2 SledjHamr-c963d75dfdeec11f82e79e727062fbf89afa2c04.tar.xz |
Update EFL to latest beta.
Diffstat (limited to 'libraries/eina/src/lib/eina_rbtree.c')
-rw-r--r-- | libraries/eina/src/lib/eina_rbtree.c | 365 |
1 files changed, 183 insertions, 182 deletions
diff --git a/libraries/eina/src/lib/eina_rbtree.c b/libraries/eina/src/lib/eina_rbtree.c index 5f1232c..a9d777a 100644 --- a/libraries/eina/src/lib/eina_rbtree.c +++ b/libraries/eina/src/lib/eina_rbtree.c | |||
@@ -1,5 +1,6 @@ | |||
1 | /* EINA - EFL data type library | 1 | /* EINA - EFL data type library |
2 | * Copyright (C) 2008 Cedric Bail | 2 | * Copyright (C) 2008 Cedric Bail |
3 | * Copyright (C) 2011 Alexandre Becoulet | ||
3 | * | 4 | * |
4 | * This library is free software; you can redistribute it and/or | 5 | * This library is free software; you can redistribute it and/or |
5 | * modify it under the terms of the GNU Lesser General Public | 6 | * modify it under the terms of the GNU Lesser General Public |
@@ -23,6 +24,7 @@ | |||
23 | #include <stdlib.h> | 24 | #include <stdlib.h> |
24 | #include <stdio.h> | 25 | #include <stdio.h> |
25 | #include <string.h> | 26 | #include <string.h> |
27 | #include <stdint.h> | ||
26 | 28 | ||
27 | #include "eina_config.h" | 29 | #include "eina_config.h" |
28 | #include "eina_private.h" | 30 | #include "eina_private.h" |
@@ -244,9 +246,9 @@ static inline Eina_Rbtree * | |||
244 | _eina_rbtree_inline_single_rotation(Eina_Rbtree *node, | 246 | _eina_rbtree_inline_single_rotation(Eina_Rbtree *node, |
245 | Eina_Rbtree_Direction dir) | 247 | Eina_Rbtree_Direction dir) |
246 | { | 248 | { |
247 | Eina_Rbtree *save = node->son[!dir]; | 249 | Eina_Rbtree *save = node->son[dir ^ 1]; |
248 | 250 | ||
249 | node->son[!dir] = save->son[dir]; | 251 | node->son[dir ^ 1] = save->son[dir]; |
250 | save->son[dir] = node; | 252 | save->son[dir] = node; |
251 | 253 | ||
252 | node->color = EINA_RBTREE_RED; | 254 | node->color = EINA_RBTREE_RED; |
@@ -259,7 +261,7 @@ static inline Eina_Rbtree * | |||
259 | _eina_rbtree_inline_double_rotation(Eina_Rbtree *node, | 261 | _eina_rbtree_inline_double_rotation(Eina_Rbtree *node, |
260 | Eina_Rbtree_Direction dir) | 262 | Eina_Rbtree_Direction dir) |
261 | { | 263 | { |
262 | node->son[!dir] = _eina_rbtree_inline_single_rotation(node->son[!dir], !dir); | 264 | node->son[dir ^ 1] = _eina_rbtree_inline_single_rotation(node->son[dir ^ 1], dir ^ 1); |
263 | return _eina_rbtree_inline_single_rotation(node, dir); | 265 | return _eina_rbtree_inline_single_rotation(node, dir); |
264 | } | 266 | } |
265 | 267 | ||
@@ -277,87 +279,64 @@ eina_rbtree_inline_insert(Eina_Rbtree *root, | |||
277 | Eina_Rbtree_Cmp_Node_Cb cmp, | 279 | Eina_Rbtree_Cmp_Node_Cb cmp, |
278 | const void *data) | 280 | const void *data) |
279 | { | 281 | { |
280 | Eina_Rbtree head; | 282 | Eina_Rbtree **r = &root; |
281 | Eina_Rbtree *g, *t; /* Grandparent & parent */ | 283 | Eina_Rbtree *q = root; |
282 | Eina_Rbtree *p, *q; /* Iterator & parent */ | 284 | uintptr_t stack[48]; |
283 | /* WARNING: | 285 | unsigned int s = 0; |
284 | Compiler is not able to understand the underlying algorithm and don't know that | ||
285 | first top node is always black, so it will never use last before running the loop | ||
286 | one time. | ||
287 | */ | ||
288 | Eina_Rbtree_Direction dir, last; | ||
289 | 286 | ||
290 | EINA_SAFETY_ON_NULL_RETURN_VAL(node, root); | 287 | EINA_SAFETY_ON_NULL_RETURN_VAL(node, root); |
291 | EINA_SAFETY_ON_NULL_RETURN_VAL( cmp, root); | 288 | EINA_SAFETY_ON_NULL_RETURN_VAL( cmp, root); |
292 | 289 | ||
293 | if (!node) | 290 | /* Find insertion leaf */ |
294 | return root; | 291 | while (q != NULL) |
295 | 292 | { | |
296 | _eina_rbtree_node_init(node); | 293 | Eina_Rbtree_Direction dir = cmp(q, node, (void *)data); |
297 | |||
298 | if (!root) | ||
299 | { | ||
300 | root = node; | ||
301 | goto end_add; | ||
302 | } | ||
303 | |||
304 | memset(&head, 0, sizeof (Eina_Rbtree)); | ||
305 | last = dir = EINA_RBTREE_LEFT; | ||
306 | |||
307 | /* Set up helpers */ | ||
308 | t = &head; | ||
309 | g = p = NULL; | ||
310 | q = t->son[1] = root; | ||
311 | |||
312 | /* Search down the tree */ | ||
313 | for (;; ) | ||
314 | { | ||
315 | if (!q) | ||
316 | /* Insert new node at the bottom */ | ||
317 | p->son[dir] = q = node; | ||
318 | else if (_eina_rbtree_is_red(q->son[0]) | ||
319 | && _eina_rbtree_is_red(q->son[1])) | ||
320 | { | ||
321 | /* Color flip */ | ||
322 | q->color = EINA_RBTREE_RED; | ||
323 | q->son[0]->color = EINA_RBTREE_BLACK; | ||
324 | q->son[1]->color = EINA_RBTREE_BLACK; | ||
325 | } | ||
326 | |||
327 | /* Fix red violation */ | ||
328 | if (_eina_rbtree_is_red(q) && _eina_rbtree_is_red(p)) | ||
329 | { | ||
330 | Eina_Rbtree_Direction dir2; | ||
331 | 294 | ||
332 | dir2 = (t->son[1] == g) ? EINA_RBTREE_RIGHT : EINA_RBTREE_LEFT; | 295 | /* Keep path in stack */ |
296 | stack[s++] = (uintptr_t)r | dir; | ||
333 | 297 | ||
334 | if (q == p->son[last]) | 298 | r = q->son + dir; |
335 | t->son[dir2] = _eina_rbtree_inline_single_rotation(g, !last); | 299 | q = *r; |
336 | else | 300 | } |
337 | t->son[dir2] = _eina_rbtree_inline_double_rotation(g, !last); | ||
338 | } | ||
339 | |||
340 | /* Stop if found */ | ||
341 | if (q == node) | ||
342 | break; | ||
343 | |||
344 | last = dir; | ||
345 | dir = cmp(q, node, (void *)data); | ||
346 | 301 | ||
347 | /* Update helpers */ | 302 | /* Insert */ |
348 | if ( g ) | 303 | *r = node; |
349 | t = g; | 304 | _eina_rbtree_node_init(node); |
350 | |||
351 | g = p, p = q; | ||
352 | q = q->son[dir]; | ||
353 | } | ||
354 | 305 | ||
355 | root = head.son[1]; | 306 | /* Rebalance */ |
307 | while (s > 0) | ||
308 | { | ||
309 | Eina_Rbtree *a, *b; | ||
310 | uintptr_t top = stack[--s]; /* Pop link pointer and direction */ | ||
311 | Eina_Rbtree_Direction dir = top & 1; | ||
312 | |||
313 | r = (Eina_Rbtree **)(top & ~(uintptr_t)1); | ||
314 | q = *r; | ||
315 | |||
316 | a = q->son[dir]; | ||
317 | /* Rebalance done ? */ | ||
318 | if (a == NULL || a->color == EINA_RBTREE_BLACK) | ||
319 | break; | ||
320 | |||
321 | b = q->son[dir ^ 1]; | ||
322 | if (b != NULL && b->color == EINA_RBTREE_RED) | ||
323 | { | ||
324 | q->color = EINA_RBTREE_RED; | ||
325 | b->color = a->color = EINA_RBTREE_BLACK; | ||
326 | } | ||
327 | else | ||
328 | { | ||
329 | Eina_Rbtree *c = a->son[dir]; | ||
330 | Eina_Rbtree *d = a->son[dir ^ 1]; | ||
331 | |||
332 | if (c != NULL && c->color == EINA_RBTREE_RED) | ||
333 | *r = _eina_rbtree_inline_single_rotation(*r, dir ^ 1); | ||
334 | else if (d != NULL && d->color == EINA_RBTREE_RED) | ||
335 | *r = _eina_rbtree_inline_double_rotation(*r, dir ^ 1); | ||
336 | } | ||
337 | } | ||
356 | 338 | ||
357 | end_add: | ||
358 | /* Make root black */ | ||
359 | root->color = EINA_RBTREE_BLACK; | 339 | root->color = EINA_RBTREE_BLACK; |
360 | |||
361 | return root; | 340 | return root; |
362 | } | 341 | } |
363 | 342 | ||
@@ -367,122 +346,144 @@ eina_rbtree_inline_remove(Eina_Rbtree *root, | |||
367 | Eina_Rbtree_Cmp_Node_Cb cmp, | 346 | Eina_Rbtree_Cmp_Node_Cb cmp, |
368 | const void *data) | 347 | const void *data) |
369 | { | 348 | { |
370 | Eina_Rbtree head; | 349 | Eina_Rbtree *l0, *l1, *r, **rt = &root; |
371 | Eina_Rbtree *q, *p; | ||
372 | Eina_Rbtree *f = NULL; | ||
373 | Eina_Rbtree_Direction dir; | 350 | Eina_Rbtree_Direction dir; |
351 | uintptr_t stack[48]; | ||
352 | unsigned int s = 0; | ||
374 | 353 | ||
375 | EINA_SAFETY_ON_NULL_RETURN_VAL(node, root); | 354 | EINA_SAFETY_ON_NULL_RETURN_VAL(node, root); |
376 | EINA_SAFETY_ON_NULL_RETURN_VAL( cmp, root); | 355 | EINA_SAFETY_ON_NULL_RETURN_VAL( cmp, root); |
377 | 356 | ||
378 | if (!root || !node) | 357 | /* Item search loop */ |
379 | return root; | 358 | for (r = *rt; r != NULL; r = *rt) |
380 | 359 | { | |
381 | memset(&head, 0, sizeof(Eina_Rbtree)); | 360 | if (r == node) |
382 | 361 | goto found; | |
383 | dir = EINA_RBTREE_RIGHT; | ||
384 | q = &head; | ||
385 | p = NULL; | ||
386 | q->son[EINA_RBTREE_RIGHT] = root; | ||
387 | |||
388 | /* Search and push a red down */ | ||
389 | while (q->son[dir]) | ||
390 | { | ||
391 | Eina_Rbtree_Direction last = dir; | ||
392 | Eina_Rbtree *g; | ||
393 | |||
394 | /* Update helpers */ | ||
395 | g = p; p = q; | ||
396 | q = q->son[dir]; | ||
397 | dir = cmp(q, node, (void *)data); | ||
398 | |||
399 | /* Save parent node found */ | ||
400 | if (q == node) | ||
401 | f = p; | ||
402 | 362 | ||
403 | /* Push the red node down */ | 363 | dir = cmp(r, node, (void*)data); |
404 | if (!_eina_rbtree_is_red(q) | 364 | stack[s++] = (uintptr_t)rt | dir; |
405 | && !_eina_rbtree_is_red(q->son[dir])) | 365 | rt = r->son + dir; |
406 | { | 366 | } |
407 | if (_eina_rbtree_is_red(q->son[!dir])) | 367 | return root; |
408 | q = p->son[last] = _eina_rbtree_inline_single_rotation(q, dir); | ||
409 | else if (!_eina_rbtree_is_red(q->son[!dir])) | ||
410 | { | ||
411 | Eina_Rbtree *s = p->son[!last]; | ||
412 | |||
413 | if (s) | ||
414 | { | ||
415 | if (!_eina_rbtree_is_red(s->son[EINA_RBTREE_LEFT]) | ||
416 | && !_eina_rbtree_is_red(s->son[EINA_RBTREE_RIGHT])) | ||
417 | { | ||
418 | /* Color flip */ | ||
419 | p->color = EINA_RBTREE_BLACK; | ||
420 | p->son[EINA_RBTREE_LEFT]->color = EINA_RBTREE_RED; | ||
421 | p->son[EINA_RBTREE_RIGHT]->color = EINA_RBTREE_RED; | ||
422 | } | ||
423 | else | ||
424 | { | ||
425 | Eina_Rbtree_Direction dir2; | ||
426 | |||
427 | dir2 = g->son[1] == | ||
428 | p ? EINA_RBTREE_RIGHT : EINA_RBTREE_LEFT; | ||
429 | |||
430 | if (_eina_rbtree_is_red(s->son[last])) | ||
431 | { | ||
432 | g->son[dir2] = | ||
433 | _eina_rbtree_inline_double_rotation(p, last); | ||
434 | if (f == g) | ||
435 | { | ||
436 | p = g->son[dir2]->son[last]; | ||
437 | f = g->son[dir2]; | ||
438 | } | ||
439 | } | ||
440 | else if (_eina_rbtree_is_red(s->son[!last])) | ||
441 | { | ||
442 | g->son[dir2] = | ||
443 | _eina_rbtree_inline_single_rotation(p, last); | ||
444 | if (f == g) | ||
445 | { | ||
446 | p = g->son[dir2]->son[last]; | ||
447 | f = g->son[dir2]; | ||
448 | } | ||
449 | } | ||
450 | |||
451 | /* Ensure correct coloring */ | ||
452 | q->color = g->son[dir2]->color = EINA_RBTREE_RED; | ||
453 | g->son[dir2]->son[EINA_RBTREE_LEFT]->color = | ||
454 | EINA_RBTREE_BLACK; | ||
455 | g->son[dir2]->son[EINA_RBTREE_RIGHT]->color = | ||
456 | EINA_RBTREE_BLACK; | ||
457 | } | ||
458 | } | ||
459 | } | ||
460 | } | ||
461 | } | ||
462 | |||
463 | /* Replace and remove if found */ | ||
464 | if (f) | ||
465 | { | ||
466 | /* 'q' should take the place of 'node' parent */ | ||
467 | f->son[f->son[1] == node] = q; | ||
468 | |||
469 | /* Switch the link from the parent to q's son */ | ||
470 | p->son[p->son[1] == q] = q->son[!q->son[0]]; | ||
471 | |||
472 | /* Put q at the place of node */ | ||
473 | q->son[0] = node->son[0]; | ||
474 | q->son[1] = node->son[1]; | ||
475 | q->color = node->color; | ||
476 | |||
477 | /* Reset node link */ | ||
478 | node->son[0] = NULL; | ||
479 | node->son[1] = NULL; | ||
480 | } | ||
481 | 368 | ||
482 | root = head.son[1]; | 369 | found: |
483 | if (root) | 370 | /* remove entry */ |
371 | l0 = node->son[0]; | ||
372 | l1 = node->son[1]; | ||
373 | |||
374 | if (l0 != NULL && l1 != NULL) /* two links case */ | ||
375 | { | ||
376 | Eina_Rbtree *q, **t, **p; | ||
377 | uintptr_t ss; | ||
378 | |||
379 | stack[s++] = (uintptr_t)rt | 1; | ||
380 | ss = s; /* keep predecessor right link stack index */ | ||
381 | |||
382 | /* find predecessor */ | ||
383 | p = node->son + 1; | ||
384 | q = *p; | ||
385 | |||
386 | while (1) | ||
387 | { | ||
388 | t = q->son; | ||
389 | q = *t; | ||
390 | if (q == NULL) | ||
391 | break; | ||
392 | stack[s++] = (uintptr_t)p | 0; | ||
393 | p = t; | ||
394 | } | ||
395 | |||
396 | /* detach predecessor */ | ||
397 | q = *p; | ||
398 | *p = q->son[1]; | ||
399 | |||
400 | int c = q->color; | ||
401 | |||
402 | /* replace entry by predecessor */ | ||
403 | memcpy(q, node, sizeof(Eina_Rbtree)); | ||
404 | *rt = q; | ||
405 | |||
406 | if (c == EINA_RBTREE_RED) | ||
407 | goto end; | ||
408 | |||
409 | /* fix stack for replaced entry */ | ||
410 | if (s > ss) | ||
411 | stack[ss] = (uintptr_t)(q->son + 1) | 0; | ||
412 | } | ||
413 | else /* single link case */ | ||
414 | { | ||
415 | if (l0 == NULL) | ||
416 | l0 = l1; | ||
417 | |||
418 | *rt = l0; | ||
419 | |||
420 | if (node->color == EINA_RBTREE_RED) | ||
421 | goto end; /* removed red */ | ||
422 | |||
423 | if (l0 != NULL && l0->color == EINA_RBTREE_RED) | ||
424 | { | ||
425 | /* red child replace removed black */ | ||
426 | l0->color = EINA_RBTREE_BLACK; | ||
427 | goto end; | ||
428 | } | ||
429 | } | ||
430 | |||
431 | /* rebalance */ | ||
432 | while (s > 0) | ||
433 | { | ||
434 | Eina_Rbtree *q; | ||
435 | uintptr_t st = stack[--s]; | ||
436 | |||
437 | rt = (Eina_Rbtree**)(st & ~(uintptr_t)1); | ||
438 | dir = st & 1; | ||
439 | r = *rt; | ||
440 | q = r->son[dir ^ 1]; | ||
441 | |||
442 | if (q != NULL && q->color == EINA_RBTREE_RED) | ||
443 | { | ||
444 | *rt = _eina_rbtree_inline_single_rotation(*rt, dir); | ||
445 | q = r->son[dir ^ 1]; | ||
446 | rt = (*rt)->son + dir; | ||
447 | } | ||
448 | |||
449 | if (q != NULL) | ||
450 | { | ||
451 | int r_color = r->color; | ||
452 | Eina_Rbtree *nd = q->son[dir ^ 1]; | ||
453 | |||
454 | if (nd != NULL && nd->color == EINA_RBTREE_RED) | ||
455 | { | ||
456 | *rt = _eina_rbtree_inline_single_rotation(*rt, dir); | ||
457 | } | ||
458 | else | ||
459 | { | ||
460 | Eina_Rbtree *d = q->son[dir]; | ||
461 | |||
462 | if (d != NULL && d->color == EINA_RBTREE_RED) | ||
463 | { | ||
464 | *rt = _eina_rbtree_inline_double_rotation(*rt, dir); | ||
465 | } | ||
466 | else | ||
467 | { | ||
468 | r->color = EINA_RBTREE_BLACK; | ||
469 | q->color = EINA_RBTREE_RED; | ||
470 | if (r_color == EINA_RBTREE_RED) | ||
471 | break; | ||
472 | continue; | ||
473 | } | ||
474 | } | ||
475 | |||
476 | r = *rt; | ||
477 | r->color = r_color; | ||
478 | r->son[1]->color = r->son[0]->color = EINA_RBTREE_BLACK; | ||
479 | |||
480 | break; | ||
481 | } | ||
482 | } | ||
483 | |||
484 | end: | ||
485 | if (root != NULL) | ||
484 | root->color = EINA_RBTREE_BLACK; | 486 | root->color = EINA_RBTREE_BLACK; |
485 | |||
486 | return root; | 487 | return root; |
487 | } | 488 | } |
488 | 489 | ||