Rev 2416 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
| Rev 2416 | Rev 2421 | ||
|---|---|---|---|
| Line 58... | Line 58... | ||
| 58 | #define AVLTREE_LEFT 0 |
58 | #define AVLTREE_LEFT 0 |
| 59 | #define AVLTREE_RIGHT 1 |
59 | #define AVLTREE_RIGHT 1 |
| 60 | 60 | ||
| 61 | 61 | ||
| 62 | /* Returns height of tree -1 */ |
62 | /* Returns height of tree -1 */ |
| 63 | #define extavlreltree_tree_height(node) ((node) == NULL) ? (-1) : max(((node)->lft_height),((node)->rgt_height)) |
63 | #define extavlreltree_tree_height(node) (((node) == NULL) ? (-1) : (((node)->lft_height>(node)->rgt_height)?(node)->lft_height:(node)->rgt_height)) |
| 64 | 64 | ||
| 65 | /** Search first occurence (oldest node with this real key) of given key in ExtAVLrel tree. |
65 | /** Search first occurence (oldest node with this real key) of given key in ExtAVLrel tree. |
| 66 | * |
66 | * |
| 67 | * @param t ExtAVLrel tree. |
67 | * @param t ExtAVLrel tree. |
| 68 | * @param key Key to be searched. |
68 | * @param key Key to be searched. |
| 69 | * |
69 | * |
| 70 | * @return Pointer to value or NULL if there is no such key. |
70 | * @return Pointer to node or NULL if there is no such key. |
| 71 | */ |
71 | */ |
| 72 | extavlreltree_node_t *extavlreltree_search(extavlreltree_t t, uint64_t key) |
72 | extavlreltree_node_t *extavlreltree_search(extavlreltree_t *t, uint64_t key) |
| 73 | { |
73 | { |
| 74 | extavlreltree_node_t *cur; |
74 | extavlreltree_node_t *cur; |
| 75 | uint64_t sum, s; |
75 | uint64_t sum, s; |
| 76 | 76 | ||
| 77 | /* |
77 | /* |
| Line 490... | Line 490... | ||
| 490 | extavlreltree_node_t *cur; |
490 | extavlreltree_node_t *cur; |
| 491 | extavlreltree_node_t *par; |
491 | extavlreltree_node_t *par; |
| 492 | extavlreltree_node_t *gpa; |
492 | extavlreltree_node_t *gpa; |
| 493 | int8_t dir; |
493 | int8_t dir; |
| 494 | int8_t dir2=0; |
494 | int8_t dir2=0; |
| 495 | uint64_t key; |
495 | uint64_t key=0; |
| 496 | int16_t balance; |
496 | int16_t balance; |
| 497 | /* |
497 | /* |
| 498 | * Condition var - if true then all rgt_sums in the way down to root must be repaired in condition |
498 | * Condition var - if true then all rgt_sums in the way down to root must be repaired in condition |
| 499 | * that we came there from right and on the way from repaired node to new node we |
499 | * that we came there from right and on the way from repaired node to new node we |
| 500 | * never turn to the left. Reparation is done in the reparation cycle. |
500 | * never turn to the left. Reparation is done in the reparation cycle. |
| Line 698... | Line 698... | ||
| 698 | gpapar = &(t->root); |
698 | gpapar = &(t->root); |
| 699 | else { |
699 | else { |
| 700 | if (gpa->par->lft == gpa) { |
700 | if (gpa->par->lft == gpa) { |
| 701 | gpapar = &(gpa->par->lft); |
701 | gpapar = &(gpa->par->lft); |
| 702 | dir2 = AVLTREE_LEFT; |
702 | dir2 = AVLTREE_LEFT; |
| 703 | repair_rgt_sum = falsi; |
703 | repair_rgt_sum = false; |
| 704 | } else { |
704 | } else { |
| 705 | gpapar = &(gpa->par->rgt); |
705 | gpapar = &(gpa->par->rgt); |
| 706 | dir2 = AVLTREE_RIGHT; |
706 | dir2 = AVLTREE_RIGHT; |
| 707 | } |
707 | } |
| 708 | } |
708 | } |