Rev 2416 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 2416 | Rev 2421 | ||
---|---|---|---|
1 | /* |
1 | /* |
2 | * Copyright (c) 2007 Vojtech Mencl |
2 | * Copyright (c) 2007 Vojtech Mencl |
3 | * All rights reserved. |
3 | * All rights reserved. |
4 | * |
4 | * |
5 | * Redistribution and use in source and binary forms, with or without |
5 | * Redistribution and use in source and binary forms, with or without |
6 | * modification, are permitted provided that the following conditions |
6 | * modification, are permitted provided that the following conditions |
7 | * are met: |
7 | * are met: |
8 | * |
8 | * |
9 | * - Redistributions of source code must retain the above copyright |
9 | * - Redistributions of source code must retain the above copyright |
10 | * notice, this list of conditions and the following disclaimer. |
10 | * notice, this list of conditions and the following disclaimer. |
11 | * - Redistributions in binary form must reproduce the above copyright |
11 | * - Redistributions in binary form must reproduce the above copyright |
12 | * notice, this list of conditions and the following disclaimer in the |
12 | * notice, this list of conditions and the following disclaimer in the |
13 | * documentation and/or other materials provided with the distribution. |
13 | * documentation and/or other materials provided with the distribution. |
14 | * - The name of the author may not be used to endorse or promote products |
14 | * - The name of the author may not be used to endorse or promote products |
15 | * derived from this software without specific prior written permission. |
15 | * derived from this software without specific prior written permission. |
16 | * |
16 | * |
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | */ |
27 | */ |
28 | 28 | ||
29 | /** @addtogroup genericadt |
29 | /** @addtogroup genericadt |
30 | * @{ |
30 | * @{ |
31 | */ |
31 | */ |
32 | 32 | ||
33 | /** |
33 | /** |
34 | * @file |
34 | * @file |
35 | * @brief Extended AVL tree with relative keys implementation. |
35 | * @brief Extended AVL tree with relative keys implementation. |
36 | * |
36 | * |
37 | * This file implements Extended AVL tree with relative keys type and operations. |
37 | * This file implements Extended AVL tree with relative keys type and operations. |
38 | * |
38 | * |
39 | * Extended AVL tree with relative keys (ExtAvlrel tree) has the following properties: |
39 | * Extended AVL tree with relative keys (ExtAvlrel tree) has the following properties: |
40 | * @li it is binary search tree with unique real keys |
40 | * @li it is binary search tree with unique real keys |
41 | * @li right subtree of every node is Avl tree |
41 | * @li right subtree of every node is Avl tree |
42 | * @li height of left subtree of every node is not greater then height of right subtree + 1 |
42 | * @li height of left subtree of every node is not greater then height of right subtree + 1 |
43 | * @li nodes with the same real keys are linked to the tree nodes of the same key, they are not tree nodes |
43 | * @li nodes with the same real keys are linked to the tree nodes of the same key, they are not tree nodes |
44 | * @li every node is part of doubly linked list with head |
44 | * @li every node is part of doubly linked list with head |
45 | * @li nodes are connected in the list ascendentaly according to their real keys, node key is |
45 | * @li nodes are connected in the list ascendentaly according to their real keys, node key is |
46 | * only difference between previous real node's key and its real node's key |
46 | * only difference between previous real node's key and its real node's key |
47 | * @li real key is either equal node key if node is leftmost node in tree or sum of all |
47 | * @li real key is either equal node key if node is leftmost node in tree or sum of all |
48 | * node keys with smaller real key |
48 | * node keys with smaller real key |
49 | * |
49 | * |
50 | * Be careful of using this tree because node keys are not equal real keys (except leftmost node). |
50 | * Be careful of using this tree because node keys are not equal real keys (except leftmost node). |
51 | */ |
51 | */ |
52 | 52 | ||
53 | #include <adt/extavlrel.h> |
53 | #include <adt/extavlrel.h> |
54 | #include <debug.h> |
54 | #include <debug.h> |
55 | #include <panic.h> |
55 | #include <panic.h> |
56 | 56 | ||
57 | 57 | ||
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 | /* |
78 | * Find right subtree in way up to the root where can be node with given key. |
78 | * Find right subtree in way up to the root where can be node with given key. |
79 | * Root node is the last node in the way up, when we reach root, it means, |
79 | * Root node is the last node in the way up, when we reach root, it means, |
80 | * that searched node belongs to the right subtree of root. |
80 | * that searched node belongs to the right subtree of root. |
81 | */ |
81 | */ |
82 | sum = 0; |
82 | sum = 0; |
83 | cur = t->head.next; |
83 | cur = t->head.next; |
84 | while (1) { |
84 | while (1) { |
85 | sum += cur->key + cur->rgt_sum; |
85 | sum += cur->key + cur->rgt_sum; |
86 | if ((key <= sum) || (cur == t->root)) |
86 | if ((key <= sum) || (cur == t->root)) |
87 | break; |
87 | break; |
88 | else |
88 | else |
89 | cur = cur->par; |
89 | cur = cur->par; |
90 | } |
90 | } |
91 | 91 | ||
92 | /* |
92 | /* |
93 | * Sorting for cycle. |
93 | * Sorting for cycle. |
94 | * Search for key in choosen subtree. Searching start at cur node which we have found |
94 | * Search for key in choosen subtree. Searching start at cur node which we have found |
95 | * in previous step. It is common search algorithm for binary search tree. |
95 | * in previous step. It is common search algorithm for binary search tree. |
96 | */ |
96 | */ |
97 | while (cur != NULL) { |
97 | while (cur != NULL) { |
98 | s = sum - cur->rgt_sum; |
98 | s = sum - cur->rgt_sum; |
99 | if (key < s) { |
99 | if (key < s) { |
100 | /* |
100 | /* |
101 | * Left subtree. Find max value in left subtree of cur. |
101 | * Left subtree. Find max value in left subtree of cur. |
102 | */ |
102 | */ |
103 | sum -= cur->key + cur->rgt_sum; |
103 | sum -= cur->key + cur->rgt_sum; |
104 | cur = cur->lft; |
104 | cur = cur->lft; |
105 | } else if (key > s) { |
105 | } else if (key > s) { |
106 | /* |
106 | /* |
107 | * Right subtree. sum has still max value in the right subtree of cur. |
107 | * Right subtree. sum has still max value in the right subtree of cur. |
108 | */ |
108 | */ |
109 | cur = cur->rgt; |
109 | cur = cur->rgt; |
110 | } else { |
110 | } else { |
111 | /* |
111 | /* |
112 | * Equal values. We have found node with given key. |
112 | * Equal values. We have found node with given key. |
113 | */ |
113 | */ |
114 | return cur; |
114 | return cur; |
115 | } |
115 | } |
116 | } |
116 | } |
117 | return NULL; |
117 | return NULL; |
118 | } |
118 | } |
119 | 119 | ||
120 | 120 | ||
121 | /** Insert new node into ExtAVL tree. |
121 | /** Insert new node into ExtAVL tree. |
122 | * |
122 | * |
123 | * New node's key must be set. |
123 | * New node's key must be set. |
124 | * |
124 | * |
125 | * @param t ExtAVL tree structure. |
125 | * @param t ExtAVL tree structure. |
126 | * @param newnode New node to be inserted. |
126 | * @param newnode New node to be inserted. |
127 | */ |
127 | */ |
128 | void extavlreltree_insert(extavlreltree_t *t, extavlreltree_node_t *newnode) |
128 | void extavlreltree_insert(extavlreltree_t *t, extavlreltree_node_t *newnode) |
129 | { |
129 | { |
130 | extavlreltree_node_t *cur; |
130 | extavlreltree_node_t *cur; |
131 | extavlreltree_node_t *son; |
131 | extavlreltree_node_t *son; |
132 | extavlreltree_node_t *gpa; |
132 | extavlreltree_node_t *gpa; |
133 | extavlreltree_node_t *par; |
133 | extavlreltree_node_t *par; |
134 | uint64_t sum, s; |
134 | uint64_t sum, s; |
135 | uint8_t dir; |
135 | uint8_t dir; |
136 | /* |
136 | /* |
137 | * Condition var - all rgt_sums in the way down to root must be repaired in condition |
137 | * Condition var - all rgt_sums in the way down to root must be repaired in condition |
138 | * that we came there from right and on the way from repaired node to new node we |
138 | * that we came there from right and on the way from repaired node to new node we |
139 | * never turn to the left. Reparation is done in the reparation cycle. |
139 | * never turn to the left. Reparation is done in the reparation cycle. |
140 | */ |
140 | */ |
141 | bool repair_rgt_sum; |
141 | bool repair_rgt_sum; |
142 | 142 | ||
143 | ASSERT(t); |
143 | ASSERT(t); |
144 | ASSERT(newnode); |
144 | ASSERT(newnode); |
145 | 145 | ||
146 | /* |
146 | /* |
147 | * Insert first node into empty tree. Key is left without change (according to definition). |
147 | * Insert first node into empty tree. Key is left without change (according to definition). |
148 | */ |
148 | */ |
149 | cur = t->head.next; |
149 | cur = t->head.next; |
150 | if (cur == &t->head) { |
150 | if (cur == &t->head) { |
151 | newnode->lft = NULL; |
151 | newnode->lft = NULL; |
152 | newnode->rgt = NULL; |
152 | newnode->rgt = NULL; |
153 | newnode->lft_height = 0; |
153 | newnode->lft_height = 0; |
154 | newnode->rgt_height = 0; |
154 | newnode->rgt_height = 0; |
155 | newnode->par = NULL; |
155 | newnode->par = NULL; |
156 | newnode->next = &t->head; |
156 | newnode->next = &t->head; |
157 | newnode->prev = &t->head; |
157 | newnode->prev = &t->head; |
158 | newnode->rgt_sum = 0; |
158 | newnode->rgt_sum = 0; |
159 | 159 | ||
160 | t->head.prev = newnode; |
160 | t->head.prev = newnode; |
161 | t->head.next = newnode; |
161 | t->head.next = newnode; |
162 | t->root = newnode; |
162 | t->root = newnode; |
163 | return; |
163 | return; |
164 | } |
164 | } |
165 | 165 | ||
166 | /* |
166 | /* |
167 | * Find right subtree in way up to the root where newnode will be placed. |
167 | * Find right subtree in way up to the root where newnode will be placed. |
168 | * Root node is the last node in the way up, when we reach root, it means, |
168 | * Root node is the last node in the way up, when we reach root, it means, |
169 | * that newnode belongs to the right subtree of root. |
169 | * that newnode belongs to the right subtree of root. |
170 | * |
170 | * |
171 | * When max key of cur's right subtree is inserted, while cycle overjumps |
171 | * When max key of cur's right subtree is inserted, while cycle overjumps |
172 | * right node and stops. But in the next sorting for cycle is this situation |
172 | * right node and stops. But in the next sorting for cycle is this situation |
173 | * solved (for cycle jumps back to the left child). |
173 | * solved (for cycle jumps back to the left child). |
174 | */ |
174 | */ |
175 | sum = 0; |
175 | sum = 0; |
176 | while (1) { |
176 | while (1) { |
177 | sum += cur->key + cur->rgt_sum; |
177 | sum += cur->key + cur->rgt_sum; |
178 | if ((newnode->key <= sum) || (cur == t->root)) |
178 | if ((newnode->key <= sum) || (cur == t->root)) |
179 | break; |
179 | break; |
180 | else |
180 | else |
181 | cur = cur->par; |
181 | cur = cur->par; |
182 | } |
182 | } |
183 | 183 | ||
184 | 184 | ||
185 | /* |
185 | /* |
186 | * Sorting for cycle. |
186 | * Sorting for cycle. |
187 | * Find a place for newnode. Searching start at cur node which we have found |
187 | * Find a place for newnode. Searching start at cur node which we have found |
188 | * in previous step. It is common search algorithm for binary search tree. |
188 | * in previous step. It is common search algorithm for binary search tree. |
189 | */ |
189 | */ |
190 | for (;;) { |
190 | for (;;) { |
191 | s = sum - cur->rgt_sum; |
191 | s = sum - cur->rgt_sum; |
192 | if (newnode->key < s) { |
192 | if (newnode->key < s) { |
193 | /* |
193 | /* |
194 | * Left subtree. Find max value in left subtree of cur. |
194 | * Left subtree. Find max value in left subtree of cur. |
195 | */ |
195 | */ |
196 | sum -= cur->key + cur->rgt_sum; |
196 | sum -= cur->key + cur->rgt_sum; |
197 | 197 | ||
198 | if (!cur->lft) { |
198 | if (!cur->lft) { |
199 | /* |
199 | /* |
200 | * Insert new node to the left. |
200 | * Insert new node to the left. |
201 | */ |
201 | */ |
202 | cur->lft = newnode; |
202 | cur->lft = newnode; |
203 | 203 | ||
204 | newnode->lft = NULL; |
204 | newnode->lft = NULL; |
205 | newnode->rgt = NULL; |
205 | newnode->rgt = NULL; |
206 | newnode->lft_height = 0; |
206 | newnode->lft_height = 0; |
207 | newnode->rgt_height = 0; |
207 | newnode->rgt_height = 0; |
208 | newnode->par = cur; |
208 | newnode->par = cur; |
209 | /* |
209 | /* |
210 | * Insert newnode to list. |
210 | * Insert newnode to list. |
211 | */ |
211 | */ |
212 | newnode->next = cur; |
212 | newnode->next = cur; |
213 | newnode->prev = cur->prev; |
213 | newnode->prev = cur->prev; |
214 | cur->prev->next = newnode; |
214 | cur->prev->next = newnode; |
215 | cur->prev = newnode; |
215 | cur->prev = newnode; |
216 | 216 | ||
217 | newnode->key -= sum; |
217 | newnode->key -= sum; |
218 | newnode->rgt_sum = 0; |
218 | newnode->rgt_sum = 0; |
219 | /* |
219 | /* |
220 | * Repair key of next value (next node always exists). newnode->key |
220 | * Repair key of next value (next node always exists). newnode->key |
221 | * has been already set. Needn't check whether newnode->next is head |
221 | * has been already set. Needn't check whether newnode->next is head |
222 | * beacause newnode is left child (next node is his father). |
222 | * beacause newnode is left child (next node is his father). |
223 | */ |
223 | */ |
224 | newnode->next->key -= newnode->key; |
224 | newnode->next->key -= newnode->key; |
225 | 225 | ||
226 | repair_rgt_sum = false; |
226 | repair_rgt_sum = false; |
227 | dir = AVLTREE_LEFT; |
227 | dir = AVLTREE_LEFT; |
228 | break; |
228 | break; |
229 | } |
229 | } |
230 | cur = cur->lft; |
230 | cur = cur->lft; |
231 | } else if (newnode->key > s) { |
231 | } else if (newnode->key > s) { |
232 | /* |
232 | /* |
233 | * Right subtree. sum has still max value in the right subtree of cur. |
233 | * Right subtree. sum has still max value in the right subtree of cur. |
234 | */ |
234 | */ |
235 | 235 | ||
236 | if (!cur->rgt) { |
236 | if (!cur->rgt) { |
237 | cur->rgt = newnode; |
237 | cur->rgt = newnode; |
238 | 238 | ||
239 | newnode->lft = NULL; |
239 | newnode->lft = NULL; |
240 | newnode->rgt = NULL; |
240 | newnode->rgt = NULL; |
241 | newnode->lft_height = 0; |
241 | newnode->lft_height = 0; |
242 | newnode->rgt_height = 0; |
242 | newnode->rgt_height = 0; |
243 | newnode->par = cur; |
243 | newnode->par = cur; |
244 | 244 | ||
245 | /* |
245 | /* |
246 | * Find last node in the chain with the same key as cur node. |
246 | * Find last node in the chain with the same key as cur node. |
247 | */ |
247 | */ |
248 | gpa = cur->next; |
248 | gpa = cur->next; |
249 | while (gpa != &t->head && gpa->key == 0) |
249 | while (gpa != &t->head && gpa->key == 0) |
250 | gpa = gpa->next; |
250 | gpa = gpa->next; |
251 | 251 | ||
252 | /* |
252 | /* |
253 | * Insert new node to list. Right place in the list was found in |
253 | * Insert new node to list. Right place in the list was found in |
254 | * previous cycle. |
254 | * previous cycle. |
255 | */ |
255 | */ |
256 | newnode->prev = gpa->prev; |
256 | newnode->prev = gpa->prev; |
257 | newnode->next = gpa; |
257 | newnode->next = gpa; |
258 | gpa->prev->next = newnode; |
258 | gpa->prev->next = newnode; |
259 | gpa->prev = newnode; |
259 | gpa->prev = newnode; |
260 | 260 | ||
261 | newnode->key -= sum; |
261 | newnode->key -= sum; |
262 | newnode->rgt_sum = 0; |
262 | newnode->rgt_sum = 0; |
263 | /* |
263 | /* |
264 | * Repair key of next value (next node always exists). newnode->key |
264 | * Repair key of next value (next node always exists). newnode->key |
265 | * has been already set. |
265 | * has been already set. |
266 | */ |
266 | */ |
267 | if (newnode->next != &t->head) |
267 | if (newnode->next != &t->head) |
268 | newnode->next->key -= newnode->key; |
268 | newnode->next->key -= newnode->key; |
269 | /* |
269 | /* |
270 | * All rgt_sums in the way down to root must be repaired in condition |
270 | * All rgt_sums in the way down to root must be repaired in condition |
271 | * that we came there from right and on the way from node to new node we |
271 | * that we came there from right and on the way from node to new node we |
272 | * never turn left. |
272 | * never turn left. |
273 | */ |
273 | */ |
274 | repair_rgt_sum = true; |
274 | repair_rgt_sum = true; |
275 | dir = AVLTREE_RIGHT; |
275 | dir = AVLTREE_RIGHT; |
276 | break; |
276 | break; |
277 | } |
277 | } |
278 | cur = cur->rgt; |
278 | cur = cur->rgt; |
279 | 279 | ||
280 | } else { |
280 | } else { |
281 | /* |
281 | /* |
282 | * Equal values. Give newnode to the last position of chain with the cur head and |
282 | * Equal values. Give newnode to the last position of chain with the cur head and |
283 | * end insertion. |
283 | * end insertion. |
284 | */ |
284 | */ |
285 | gpa = cur->next; |
285 | gpa = cur->next; |
286 | while (gpa != &t->head && gpa->key == 0) |
286 | while (gpa != &t->head && gpa->key == 0) |
287 | gpa = gpa->next; |
287 | gpa = gpa->next; |
288 | /* |
288 | /* |
289 | * Insert new node to list in right place. |
289 | * Insert new node to list in right place. |
290 | */ |
290 | */ |
291 | newnode->prev = gpa->prev; |
291 | newnode->prev = gpa->prev; |
292 | newnode->next = gpa; |
292 | newnode->next = gpa; |
293 | gpa->prev->next = newnode; |
293 | gpa->prev->next = newnode; |
294 | gpa->prev = newnode; |
294 | gpa->prev = newnode; |
295 | 295 | ||
296 | newnode->par = NULL; |
296 | newnode->par = NULL; |
297 | newnode->lft = NULL; |
297 | newnode->lft = NULL; |
298 | newnode->rgt = NULL; |
298 | newnode->rgt = NULL; |
299 | newnode->lft_height = 0; |
299 | newnode->lft_height = 0; |
300 | newnode->rgt_height = 0; |
300 | newnode->rgt_height = 0; |
301 | 301 | ||
302 | /* |
302 | /* |
303 | * Nodes in chains has key equal 0, because difference between previous node and them is 0. |
303 | * Nodes in chains has key equal 0, because difference between previous node and them is 0. |
304 | */ |
304 | */ |
305 | newnode->key = 0; |
305 | newnode->key = 0; |
306 | newnode->rgt_sum = 0; |
306 | newnode->rgt_sum = 0; |
307 | return; |
307 | return; |
308 | } |
308 | } |
309 | } |
309 | } |
310 | 310 | ||
311 | /* |
311 | /* |
312 | * Balancing all nodes from newnode's parent down to root. |
312 | * Balancing all nodes from newnode's parent down to root. |
313 | */ |
313 | */ |
314 | cur = newnode->par; |
314 | cur = newnode->par; |
315 | while (true) { |
315 | while (true) { |
316 | if (dir == AVLTREE_LEFT) { |
316 | if (dir == AVLTREE_LEFT) { |
317 | /* |
317 | /* |
318 | * Insertion was made in the left subtree - repair left height, stop |
318 | * Insertion was made in the left subtree - repair left height, stop |
319 | * repairing rgt_sum and check balance of current node. |
319 | * repairing rgt_sum and check balance of current node. |
320 | */ |
320 | */ |
321 | cur->lft_height = extavlreltree_tree_height(cur->lft) + 1; |
321 | cur->lft_height = extavlreltree_tree_height(cur->lft) + 1; |
322 | 322 | ||
323 | repair_rgt_sum = false; |
323 | repair_rgt_sum = false; |
324 | 324 | ||
325 | if ((cur->rgt_height - cur->lft_height) <= -2) { |
325 | if ((cur->rgt_height - cur->lft_height) <= -2) { |
326 | /* |
326 | /* |
327 | * Balance was corrupted, must be repaired through LL or LR rotation. |
327 | * Balance was corrupted, must be repaired through LL or LR rotation. |
328 | */ |
328 | */ |
329 | par = cur->par; |
329 | par = cur->par; |
330 | son = cur->lft; |
330 | son = cur->lft; |
331 | if ((son->rgt_height - son->lft_height) != 1) { |
331 | if ((son->rgt_height - son->lft_height) != 1) { |
332 | /* |
332 | /* |
333 | * LL rotation. |
333 | * LL rotation. |
334 | */ |
334 | */ |
335 | gpa = son; |
335 | gpa = son; |
336 | cur->lft = son->rgt; |
336 | cur->lft = son->rgt; |
337 | if (cur->lft != NULL) cur->lft->par = cur; |
337 | if (cur->lft != NULL) cur->lft->par = cur; |
338 | cur->par = son; |
338 | cur->par = son; |
339 | son->rgt = cur; |
339 | son->rgt = cur; |
340 | /* |
340 | /* |
341 | * Repair heights. |
341 | * Repair heights. |
342 | */ |
342 | */ |
343 | cur->lft_height = son->rgt_height; |
343 | cur->lft_height = son->rgt_height; |
344 | son->rgt_height = extavlreltree_tree_height(cur) + 1; |
344 | son->rgt_height = extavlreltree_tree_height(cur) + 1; |
345 | /* |
345 | /* |
346 | * Repair rgt_sum. |
346 | * Repair rgt_sum. |
347 | */ |
347 | */ |
348 | son->rgt_sum += cur->key + cur->rgt_sum; |
348 | son->rgt_sum += cur->key + cur->rgt_sum; |
349 | } else { |
349 | } else { |
350 | /* |
350 | /* |
351 | * LR rotation. |
351 | * LR rotation. |
352 | */ |
352 | */ |
353 | gpa = son->rgt; |
353 | gpa = son->rgt; |
354 | son->rgt = gpa->lft; |
354 | son->rgt = gpa->lft; |
355 | if (gpa->lft != NULL) gpa->lft->par = son; |
355 | if (gpa->lft != NULL) gpa->lft->par = son; |
356 | gpa->lft = son; |
356 | gpa->lft = son; |
357 | son->par = gpa; |
357 | son->par = gpa; |
358 | cur->lft = gpa->rgt; |
358 | cur->lft = gpa->rgt; |
359 | if (gpa->rgt != NULL) gpa->rgt->par = cur; |
359 | if (gpa->rgt != NULL) gpa->rgt->par = cur; |
360 | gpa->rgt = cur; |
360 | gpa->rgt = cur; |
361 | cur->par = gpa; |
361 | cur->par = gpa; |
362 | /* |
362 | /* |
363 | * Repair heights. |
363 | * Repair heights. |
364 | */ |
364 | */ |
365 | cur->lft_height = gpa->rgt_height; |
365 | cur->lft_height = gpa->rgt_height; |
366 | son->rgt_height = gpa->lft_height; |
366 | son->rgt_height = gpa->lft_height; |
367 | gpa->rgt_height = extavlreltree_tree_height(cur) + 1; |
367 | gpa->rgt_height = extavlreltree_tree_height(cur) + 1; |
368 | gpa->lft_height = extavlreltree_tree_height(son) + 1; |
368 | gpa->lft_height = extavlreltree_tree_height(son) + 1; |
369 | /* |
369 | /* |
370 | * Repair rgt_sums. |
370 | * Repair rgt_sums. |
371 | */ |
371 | */ |
372 | son->rgt_sum -= gpa->key + gpa->rgt_sum; |
372 | son->rgt_sum -= gpa->key + gpa->rgt_sum; |
373 | gpa->rgt_sum += cur->key + cur->rgt_sum; |
373 | gpa->rgt_sum += cur->key + cur->rgt_sum; |
374 | } |
374 | } |
375 | /* |
375 | /* |
376 | * Repair parent of current node. |
376 | * Repair parent of current node. |
377 | */ |
377 | */ |
378 | gpa->par = par; |
378 | gpa->par = par; |
379 | } else { |
379 | } else { |
380 | /* |
380 | /* |
381 | * Balance is correct, continue balancing at parent node. |
381 | * Balance is correct, continue balancing at parent node. |
382 | */ |
382 | */ |
383 | par = cur->par; |
383 | par = cur->par; |
384 | gpa = cur; |
384 | gpa = cur; |
385 | } |
385 | } |
386 | } else { |
386 | } else { |
387 | /* |
387 | /* |
388 | * Insertion was made in the right subtree - repair right height, try to |
388 | * Insertion was made in the right subtree - repair right height, try to |
389 | * repair rgt_sum and check balance of current node. |
389 | * repair rgt_sum and check balance of current node. |
390 | */ |
390 | */ |
391 | cur->rgt_height = extavlreltree_tree_height(cur->rgt) + 1; |
391 | cur->rgt_height = extavlreltree_tree_height(cur->rgt) + 1; |
392 | 392 | ||
393 | if (repair_rgt_sum) { |
393 | if (repair_rgt_sum) { |
394 | cur->rgt_sum += newnode->key; |
394 | cur->rgt_sum += newnode->key; |
395 | } |
395 | } |
396 | 396 | ||
397 | if ((cur->rgt_height - cur->lft_height) >= 2) { |
397 | if ((cur->rgt_height - cur->lft_height) >= 2) { |
398 | /* |
398 | /* |
399 | * Balance was corrupted, must be repaired through RL or RR rotation. |
399 | * Balance was corrupted, must be repaired through RL or RR rotation. |
400 | */ |
400 | */ |
401 | par = cur->par; |
401 | par = cur->par; |
402 | son = cur->rgt; |
402 | son = cur->rgt; |
403 | if ((son->rgt_height - son->lft_height) != -1) { |
403 | if ((son->rgt_height - son->lft_height) != -1) { |
404 | /* |
404 | /* |
405 | * RR rotation. |
405 | * RR rotation. |
406 | */ |
406 | */ |
407 | gpa = son; |
407 | gpa = son; |
408 | cur->rgt = son->lft; |
408 | cur->rgt = son->lft; |
409 | if (cur->rgt != NULL) cur->rgt->par = cur; |
409 | if (cur->rgt != NULL) cur->rgt->par = cur; |
410 | cur->par = son; |
410 | cur->par = son; |
411 | son->lft = cur; |
411 | son->lft = cur; |
412 | /* |
412 | /* |
413 | * Repair heights. |
413 | * Repair heights. |
414 | */ |
414 | */ |
415 | cur->rgt_height = son->lft_height; |
415 | cur->rgt_height = son->lft_height; |
416 | son->lft_height = extavlreltree_tree_height(cur) + 1; |
416 | son->lft_height = extavlreltree_tree_height(cur) + 1; |
417 | /* |
417 | /* |
418 | * Repair rgt_sum. |
418 | * Repair rgt_sum. |
419 | */ |
419 | */ |
420 | cur->rgt_sum -= son->rgt_sum + son->key; |
420 | cur->rgt_sum -= son->rgt_sum + son->key; |
421 | } else { |
421 | } else { |
422 | /* |
422 | /* |
423 | * RL rotation. |
423 | * RL rotation. |
424 | */ |
424 | */ |
425 | gpa = son->lft; |
425 | gpa = son->lft; |
426 | son->lft = gpa->rgt; |
426 | son->lft = gpa->rgt; |
427 | if (gpa->rgt != NULL) gpa->rgt->par = son; |
427 | if (gpa->rgt != NULL) gpa->rgt->par = son; |
428 | gpa->rgt = son; |
428 | gpa->rgt = son; |
429 | son->par = gpa; |
429 | son->par = gpa; |
430 | cur->rgt = gpa->lft; |
430 | cur->rgt = gpa->lft; |
431 | if (gpa->lft != NULL) gpa->lft->par = cur; |
431 | if (gpa->lft != NULL) gpa->lft->par = cur; |
432 | gpa->lft = cur; |
432 | gpa->lft = cur; |
433 | cur->par = gpa; |
433 | cur->par = gpa; |
434 | /* |
434 | /* |
435 | * Repair heights. |
435 | * Repair heights. |
436 | */ |
436 | */ |
437 | cur->rgt_height = gpa->lft_height; |
437 | cur->rgt_height = gpa->lft_height; |
438 | son->lft_height = gpa->rgt_height; |
438 | son->lft_height = gpa->rgt_height; |
439 | gpa->lft_height = extavlreltree_tree_height(cur) + 1; |
439 | gpa->lft_height = extavlreltree_tree_height(cur) + 1; |
440 | gpa->rgt_height = extavlreltree_tree_height(son) + 1; |
440 | gpa->rgt_height = extavlreltree_tree_height(son) + 1; |
441 | /* |
441 | /* |
442 | * Repair rgt_sums. |
442 | * Repair rgt_sums. |
443 | */ |
443 | */ |
444 | cur->rgt_sum -= son->key + son->rgt_sum + gpa->key + gpa->rgt_sum; |
444 | cur->rgt_sum -= son->key + son->rgt_sum + gpa->key + gpa->rgt_sum; |
445 | gpa->rgt_sum += son->key + son->rgt_sum; |
445 | gpa->rgt_sum += son->key + son->rgt_sum; |
446 | } |
446 | } |
447 | 447 | ||
448 | /* |
448 | /* |
449 | * Repair parent of current node. |
449 | * Repair parent of current node. |
450 | */ |
450 | */ |
451 | gpa->par = par; |
451 | gpa->par = par; |
452 | } else { |
452 | } else { |
453 | /* |
453 | /* |
454 | * Balance is correct, continue balancing at parent node. |
454 | * Balance is correct, continue balancing at parent node. |
455 | */ |
455 | */ |
456 | par = cur->par; |
456 | par = cur->par; |
457 | gpa = cur; |
457 | gpa = cur; |
458 | } |
458 | } |
459 | } |
459 | } |
460 | /* |
460 | /* |
461 | * Change parent pointers, set direction where is newnode and |
461 | * Change parent pointers, set direction where is newnode and |
462 | * continue balancing at parent node or if current node |
462 | * continue balancing at parent node or if current node |
463 | * is root then change root atribute pointer and stop |
463 | * is root then change root atribute pointer and stop |
464 | */ |
464 | */ |
465 | if (par) { |
465 | if (par) { |
466 | if (par->lft == cur) { |
466 | if (par->lft == cur) { |
467 | par->lft = gpa; |
467 | par->lft = gpa; |
468 | dir = AVLTREE_LEFT; |
468 | dir = AVLTREE_LEFT; |
469 | } else { |
469 | } else { |
470 | par->rgt = gpa; |
470 | par->rgt = gpa; |
471 | dir = AVLTREE_RIGHT; |
471 | dir = AVLTREE_RIGHT; |
472 | } |
472 | } |
473 | } else { |
473 | } else { |
474 | t->root = gpa; |
474 | t->root = gpa; |
475 | break; |
475 | break; |
476 | } |
476 | } |
477 | cur = par; |
477 | cur = par; |
478 | } |
478 | } |
479 | } |
479 | } |
480 | 480 | ||
481 | 481 | ||
482 | /** Delete node from ExtAVLrel tree. |
482 | /** Delete node from ExtAVLrel tree. |
483 | * |
483 | * |
484 | * @param t ExtAVLrel tree structure. |
484 | * @param t ExtAVLrel tree structure. |
485 | * @param node Address of node which will be deleted. |
485 | * @param node Address of node which will be deleted. |
486 | */ |
486 | */ |
487 | void extavlreltree_delete(extavlreltree_t *t, extavlreltree_node_t *node) |
487 | void extavlreltree_delete(extavlreltree_t *t, extavlreltree_node_t *node) |
488 | { |
488 | { |
489 | extavlreltree_node_t **gpapar; |
489 | extavlreltree_node_t **gpapar; |
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. |
501 | */ |
501 | */ |
502 | bool repair_rgt_sum; |
502 | bool repair_rgt_sum; |
503 | 503 | ||
504 | 504 | ||
505 | ASSERT(t); |
505 | ASSERT(t); |
506 | ASSERT(node); |
506 | ASSERT(node); |
507 | 507 | ||
508 | /* |
508 | /* |
509 | * Delete node from list. |
509 | * Delete node from list. |
510 | */ |
510 | */ |
511 | node->next->prev = node->prev; |
511 | node->next->prev = node->prev; |
512 | node->prev->next = node->next; |
512 | node->prev->next = node->next; |
513 | 513 | ||
514 | if (!node->par) { |
514 | if (!node->par) { |
515 | if (t->root != node) { |
515 | if (t->root != node) { |
516 | /* |
516 | /* |
517 | * It is list node (not a tree node). Needn't repair tree or anything else. |
517 | * It is list node (not a tree node). Needn't repair tree or anything else. |
518 | */ |
518 | */ |
519 | return; |
519 | return; |
520 | } |
520 | } |
521 | repair_rgt_sum = false; |
521 | repair_rgt_sum = false; |
522 | gpapar = &(t->root); |
522 | gpapar = &(t->root); |
523 | } else { |
523 | } else { |
524 | /* |
524 | /* |
525 | * Find tree pointer which points to node. |
525 | * Find tree pointer which points to node. |
526 | */ |
526 | */ |
527 | if (node->par->lft == node) { |
527 | if (node->par->lft == node) { |
528 | gpapar = &(node->par->lft); |
528 | gpapar = &(node->par->lft); |
529 | repair_rgt_sum = false; |
529 | repair_rgt_sum = false; |
530 | } else { |
530 | } else { |
531 | gpapar = &(node->par->rgt); |
531 | gpapar = &(node->par->rgt); |
532 | /* |
532 | /* |
533 | * Node is right child - rgt_sum might be repaired. |
533 | * Node is right child - rgt_sum might be repaired. |
534 | */ |
534 | */ |
535 | repair_rgt_sum = true; |
535 | repair_rgt_sum = true; |
536 | } |
536 | } |
537 | } |
537 | } |
538 | 538 | ||
539 | 539 | ||
540 | if (&t->head != node->next && node->next->key == 0) { |
540 | if (&t->head != node->next && node->next->key == 0) { |
541 | /* |
541 | /* |
542 | * Deleted node has at least one node node with the same key which is closest next |
542 | * Deleted node has at least one node node with the same key which is closest next |
543 | * neighbor in the list, copy node atributes into next node and end. |
543 | * neighbor in the list, copy node atributes into next node and end. |
544 | */ |
544 | */ |
545 | cur = node->next; |
545 | cur = node->next; |
546 | cur->lft = node->lft; |
546 | cur->lft = node->lft; |
547 | cur->rgt = node->rgt; |
547 | cur->rgt = node->rgt; |
548 | cur->par = node->par; |
548 | cur->par = node->par; |
549 | cur->lft_height = node->lft_height; |
549 | cur->lft_height = node->lft_height; |
550 | cur->rgt_height = node->rgt_height; |
550 | cur->rgt_height = node->rgt_height; |
551 | *gpapar = cur; |
551 | *gpapar = cur; |
552 | 552 | ||
553 | if (node->lft) node->lft->par = cur; |
553 | if (node->lft) node->lft->par = cur; |
554 | if (node->rgt) node->rgt->par = cur; |
554 | if (node->rgt) node->rgt->par = cur; |
555 | 555 | ||
556 | cur->key = node->key; |
556 | cur->key = node->key; |
557 | cur->rgt_sum = node->rgt_sum; |
557 | cur->rgt_sum = node->rgt_sum; |
558 | return; |
558 | return; |
559 | } |
559 | } |
560 | 560 | ||
561 | /* |
561 | /* |
562 | * Repair next node's key (it must be difference between previous key and its key). |
562 | * Repair next node's key (it must be difference between previous key and its key). |
563 | */ |
563 | */ |
564 | if (node->next != &t->head) { |
564 | if (node->next != &t->head) { |
565 | node->next->key += node->key; |
565 | node->next->key += node->key; |
566 | } |
566 | } |
567 | 567 | ||
568 | /* |
568 | /* |
569 | * Check situation in the tree around deleted node. |
569 | * Check situation in the tree around deleted node. |
570 | */ |
570 | */ |
571 | if (!node->lft) { |
571 | if (!node->lft) { |
572 | /* |
572 | /* |
573 | * Deleted node has not left son. Right son will take deleted node's place. |
573 | * Deleted node has not left son. Right son will take deleted node's place. |
574 | */ |
574 | */ |
575 | gpa = node->par; |
575 | gpa = node->par; |
576 | if (node->rgt) { |
576 | if (node->rgt) { |
577 | /* |
577 | /* |
578 | * rgt_sum is not corrupted because the biggest key is in right subtree of node |
578 | * rgt_sum is not corrupted because the biggest key is in right subtree of node |
579 | */ |
579 | */ |
580 | node->rgt->par = gpa; |
580 | node->rgt->par = gpa; |
581 | repair_rgt_sum = false; |
581 | repair_rgt_sum = false; |
582 | } else { |
582 | } else { |
583 | /* |
583 | /* |
584 | * node is the biggest key and rgt_sum might be repaired according to which |
584 | * node is the biggest key and rgt_sum might be repaired according to which |
585 | * child is node. |
585 | * child is node. |
586 | */ |
586 | */ |
587 | key = node->key; |
587 | key = node->key; |
588 | } |
588 | } |
589 | 589 | ||
590 | if (!gpa) { |
590 | if (!gpa) { |
591 | /* |
591 | /* |
592 | * Deleted node is root node. Balancing is finished, change only |
592 | * Deleted node is root node. Balancing is finished, change only |
593 | * root pointer in extavltree structure. |
593 | * root pointer in extavltree structure. |
594 | */ |
594 | */ |
595 | *gpapar = node->rgt; |
595 | *gpapar = node->rgt; |
596 | return; |
596 | return; |
597 | } |
597 | } |
598 | dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT; |
598 | dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT; |
599 | 599 | ||
600 | *gpapar = node->rgt; |
600 | *gpapar = node->rgt; |
601 | } else { |
601 | } else { |
602 | /* |
602 | /* |
603 | * Node has left son. |
603 | * Node has left son. |
604 | */ |
604 | */ |
605 | cur = node->lft; |
605 | cur = node->lft; |
606 | if (!cur->rgt) { |
606 | if (!cur->rgt) { |
607 | /* |
607 | /* |
608 | * Left son of node hasn't got right son. Left son will take deleted node's place. |
608 | * Left son of node hasn't got right son. Left son will take deleted node's place. |
609 | */ |
609 | */ |
610 | *gpapar = cur; |
610 | *gpapar = cur; |
611 | cur->par = node->par; |
611 | cur->par = node->par; |
612 | dir = AVLTREE_LEFT; |
612 | dir = AVLTREE_LEFT; |
613 | cur->rgt = node->rgt; |
613 | cur->rgt = node->rgt; |
614 | if (node->rgt) node->rgt->par = cur; |
614 | if (node->rgt) node->rgt->par = cur; |
615 | gpa = cur; |
615 | gpa = cur; |
616 | cur->rgt_height = node->rgt_height; |
616 | cur->rgt_height = node->rgt_height; |
617 | cur->lft_height = node->lft_height; |
617 | cur->lft_height = node->lft_height; |
618 | /* |
618 | /* |
619 | * cur->lft_height will be decreased in repair cycle. |
619 | * cur->lft_height will be decreased in repair cycle. |
620 | */ |
620 | */ |
621 | 621 | ||
622 | if (repair_rgt_sum == false && node->rgt_sum == 0) { |
622 | if (repair_rgt_sum == false && node->rgt_sum == 0) { |
623 | /* |
623 | /* |
624 | * node hasn't got right son so right sum is 0. |
624 | * node hasn't got right son so right sum is 0. |
625 | */ |
625 | */ |
626 | cur->rgt_sum = 0; |
626 | cur->rgt_sum = 0; |
627 | } else { |
627 | } else { |
628 | cur->rgt_sum = node->rgt_sum + node->key; //pri node->rgt_sum == 0 bude opraveno v cyklu |
628 | cur->rgt_sum = node->rgt_sum + node->key; //pri node->rgt_sum == 0 bude opraveno v cyklu |
629 | if (repair_rgt_sum == true && node->rgt_sum != 0) { |
629 | if (repair_rgt_sum == true && node->rgt_sum != 0) { |
630 | /* |
630 | /* |
631 | * node has got right son so node's key is not the biggest key in any subtree. |
631 | * node has got right son so node's key is not the biggest key in any subtree. |
632 | */ |
632 | */ |
633 | repair_rgt_sum = false; |
633 | repair_rgt_sum = false; |
634 | } else { |
634 | } else { |
635 | /* |
635 | /* |
636 | * node is the biggest key and predecessors might be repaired. |
636 | * node is the biggest key and predecessors might be repaired. |
637 | */ |
637 | */ |
638 | key = node->key; |
638 | key = node->key; |
639 | } |
639 | } |
640 | } |
640 | } |
641 | } else { |
641 | } else { |
642 | /* |
642 | /* |
643 | * Node has left and right son. Find a node with smallest key in left subtree |
643 | * Node has left and right son. Find a node with smallest key in left subtree |
644 | * and change that node with deleted node. |
644 | * and change that node with deleted node. |
645 | */ |
645 | */ |
646 | while (cur->rgt != NULL) |
646 | while (cur->rgt != NULL) |
647 | cur = cur->rgt; |
647 | cur = cur->rgt; |
648 | 648 | ||
649 | *gpapar = cur; |
649 | *gpapar = cur; |
650 | cur->rgt = node->rgt; |
650 | cur->rgt = node->rgt; |
651 | if (node->rgt) node->rgt->par = cur; |
651 | if (node->rgt) node->rgt->par = cur; |
652 | gpa = cur->par; |
652 | gpa = cur->par; |
653 | gpa->rgt = cur->lft; |
653 | gpa->rgt = cur->lft; |
654 | if (cur->lft) cur->lft->par = gpa; |
654 | if (cur->lft) cur->lft->par = gpa; |
655 | cur->lft = node->lft; |
655 | cur->lft = node->lft; |
656 | cur->lft->par = cur; |
656 | cur->lft->par = cur; |
657 | cur->par = node->par; |
657 | cur->par = node->par; |
658 | dir = AVLTREE_RIGHT; |
658 | dir = AVLTREE_RIGHT; |
659 | cur->lft_height = node->lft_height; |
659 | cur->lft_height = node->lft_height; |
660 | cur->rgt_height = node->rgt_height; |
660 | cur->rgt_height = node->rgt_height; |
661 | /* |
661 | /* |
662 | * gpa->rgt_height and cur->lft_height will be repaired in repair cycle. |
662 | * gpa->rgt_height and cur->lft_height will be repaired in repair cycle. |
663 | */ |
663 | */ |
664 | 664 | ||
665 | /* |
665 | /* |
666 | * node must have always rgt child otherwise its malfunction of extavltree definition |
666 | * node must have always rgt child otherwise its malfunction of extavltree definition |
667 | * so we can add node->key. If it was to the contrary, we wouldn't know where |
667 | * so we can add node->key. If it was to the contrary, we wouldn't know where |
668 | */ |
668 | */ |
669 | cur->rgt_sum = node->rgt_sum + node->key; |
669 | cur->rgt_sum = node->rgt_sum + node->key; |
670 | /* |
670 | /* |
671 | * The biggest key in at least one subtree was changed - rgt_sum must be repaired. |
671 | * The biggest key in at least one subtree was changed - rgt_sum must be repaired. |
672 | */ |
672 | */ |
673 | repair_rgt_sum = true; |
673 | repair_rgt_sum = true; |
674 | key = cur->key; |
674 | key = cur->key; |
675 | } |
675 | } |
676 | /* |
676 | /* |
677 | * Deleted node is root node. Balancing is finished. |
677 | * Deleted node is root node. Balancing is finished. |
678 | */ |
678 | */ |
679 | if (!gpa) return; |
679 | if (!gpa) return; |
680 | } |
680 | } |
681 | 681 | ||
682 | /* |
682 | /* |
683 | * Repair cycle which goes from gpa node down to root. |
683 | * Repair cycle which goes from gpa node down to root. |
684 | */ |
684 | */ |
685 | for(;;) { |
685 | for(;;) { |
686 | if (repair_rgt_sum) { |
686 | if (repair_rgt_sum) { |
687 | /* |
687 | /* |
688 | * The biggest key in right subtree was deleted so rgt_sum must be changed. |
688 | * The biggest key in right subtree was deleted so rgt_sum must be changed. |
689 | */ |
689 | */ |
690 | gpa->rgt_sum -= key; |
690 | gpa->rgt_sum -= key; |
691 | } |
691 | } |
692 | 692 | ||
693 | /* |
693 | /* |
694 | * Find tree pointer which points to the currently balanced node. When balanced |
694 | * Find tree pointer which points to the currently balanced node. When balanced |
695 | * node is root, root pointer from extavltree structure is taken. |
695 | * node is root, root pointer from extavltree structure is taken. |
696 | */ |
696 | */ |
697 | if (!gpa->par) |
697 | if (!gpa->par) |
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 | } |
709 | 709 | ||
710 | if (dir == AVLTREE_LEFT) { |
710 | if (dir == AVLTREE_LEFT) { |
711 | /* |
711 | /* |
712 | * Deletition was made in left subtree. |
712 | * Deletition was made in left subtree. |
713 | */ |
713 | */ |
714 | gpa->lft_height--; |
714 | gpa->lft_height--; |
715 | balance = gpa->rgt_height - gpa->lft_height; |
715 | balance = gpa->rgt_height - gpa->lft_height; |
716 | if (balance == 1) { |
716 | if (balance == 1) { |
717 | /* |
717 | /* |
718 | * Stop balancing, tree is balanced. |
718 | * Stop balancing, tree is balanced. |
719 | */ |
719 | */ |
720 | break; |
720 | break; |
721 | } else if (balance == 2) { |
721 | } else if (balance == 2) { |
722 | /* |
722 | /* |
723 | * Bad balance, heights of left and right subtrees differs more then is allowed. |
723 | * Bad balance, heights of left and right subtrees differs more then is allowed. |
724 | */ |
724 | */ |
725 | par = gpa->rgt; |
725 | par = gpa->rgt; |
726 | 726 | ||
727 | if ((par->rgt_height - par->lft_height) == -1) { |
727 | if ((par->rgt_height - par->lft_height) == -1) { |
728 | /* |
728 | /* |
729 | * RL rotation |
729 | * RL rotation |
730 | */ |
730 | */ |
731 | 731 | ||
732 | cur = par->lft; |
732 | cur = par->lft; |
733 | par->lft = cur->rgt; |
733 | par->lft = cur->rgt; |
734 | cur->rgt = par; |
734 | cur->rgt = par; |
735 | gpa->rgt = cur->lft; |
735 | gpa->rgt = cur->lft; |
736 | cur->lft = gpa; |
736 | cur->lft = gpa; |
737 | 737 | ||
738 | /* |
738 | /* |
739 | * Repair balances. |
739 | * Repair balances. |
740 | */ |
740 | */ |
741 | par->lft_height = cur->rgt_height; |
741 | par->lft_height = cur->rgt_height; |
742 | gpa->rgt_height = cur->lft_height; |
742 | gpa->rgt_height = cur->lft_height; |
743 | cur->lft_height = extavlreltree_tree_height(gpa) + 1; |
743 | cur->lft_height = extavlreltree_tree_height(gpa) + 1; |
744 | cur->rgt_height = par->rgt_height + 1; |
744 | cur->rgt_height = par->rgt_height + 1; |
745 | 745 | ||
746 | /* |
746 | /* |
747 | * Repair paternity. |
747 | * Repair paternity. |
748 | */ |
748 | */ |
749 | if (gpa->rgt) gpa->rgt->par = gpa; |
749 | if (gpa->rgt) gpa->rgt->par = gpa; |
750 | if (par->lft) par->lft->par = par; |
750 | if (par->lft) par->lft->par = par; |
751 | cur->par = gpa->par; |
751 | cur->par = gpa->par; |
752 | gpa->par = cur; |
752 | gpa->par = cur; |
753 | par->par = cur; |
753 | par->par = cur; |
754 | 754 | ||
755 | /* |
755 | /* |
756 | * Repair tree pointer which points to the current node. |
756 | * Repair tree pointer which points to the current node. |
757 | */ |
757 | */ |
758 | *gpapar = cur; |
758 | *gpapar = cur; |
759 | 759 | ||
760 | /* |
760 | /* |
761 | * Repair rgt_sums after rotation was done. |
761 | * Repair rgt_sums after rotation was done. |
762 | */ |
762 | */ |
763 | gpa->rgt_sum -= par->key + par->rgt_sum + cur->key + cur->rgt_sum; |
763 | gpa->rgt_sum -= par->key + par->rgt_sum + cur->key + cur->rgt_sum; |
764 | cur->rgt_sum += par->key + par->rgt_sum; |
764 | cur->rgt_sum += par->key + par->rgt_sum; |
765 | 765 | ||
766 | /* |
766 | /* |
767 | * Next balancing at parent node. |
767 | * Next balancing at parent node. |
768 | */ |
768 | */ |
769 | gpa = cur->par; |
769 | gpa = cur->par; |
770 | } else { |
770 | } else { |
771 | /* |
771 | /* |
772 | * RR rotation |
772 | * RR rotation |
773 | */ |
773 | */ |
774 | gpa->rgt = par->lft; |
774 | gpa->rgt = par->lft; |
775 | gpa->rgt_height = par->lft_height; |
775 | gpa->rgt_height = par->lft_height; |
776 | if (par->lft) par->lft->par = gpa; |
776 | if (par->lft) par->lft->par = gpa; |
777 | par->lft = gpa; |
777 | par->lft = gpa; |
778 | 778 | ||
779 | /* |
779 | /* |
780 | * Repair paternity. |
780 | * Repair paternity. |
781 | */ |
781 | */ |
782 | par->par = gpa->par; |
782 | par->par = gpa->par; |
783 | gpa->par = par; |
783 | gpa->par = par; |
784 | 784 | ||
785 | /* |
785 | /* |
786 | * Repair heights and tree pointer which points to the current node. |
786 | * Repair heights and tree pointer which points to the current node. |
787 | */ |
787 | */ |
788 | balance = par->rgt_height - par->lft_height; |
788 | balance = par->rgt_height - par->lft_height; |
789 | par->lft_height++; |
789 | par->lft_height++; |
790 | *gpapar = par; |
790 | *gpapar = par; |
791 | 791 | ||
792 | /* |
792 | /* |
793 | * Repair rgt_sums after rotation was done. |
793 | * Repair rgt_sums after rotation was done. |
794 | */ |
794 | */ |
795 | gpa->rgt_sum -= par->key + par->rgt_sum; |
795 | gpa->rgt_sum -= par->key + par->rgt_sum; |
796 | 796 | ||
797 | /* |
797 | /* |
798 | * Ends when tree is balanced or do the next step. |
798 | * Ends when tree is balanced or do the next step. |
799 | */ |
799 | */ |
800 | if (balance == 0) return; |
800 | if (balance == 0) return; |
801 | gpa = par->par; |
801 | gpa = par->par; |
802 | } |
802 | } |
803 | } else { |
803 | } else { |
804 | /* |
804 | /* |
805 | * Current node is balanced - perform balance check of its parent. |
805 | * Current node is balanced - perform balance check of its parent. |
806 | */ |
806 | */ |
807 | gpa = gpa->par; |
807 | gpa = gpa->par; |
808 | } |
808 | } |
809 | } else { |
809 | } else { |
810 | /* |
810 | /* |
811 | * Balance right son. |
811 | * Balance right son. |
812 | */ |
812 | */ |
813 | gpa->rgt_height--; |
813 | gpa->rgt_height--; |
814 | balance = gpa->rgt_height - gpa->lft_height; |
814 | balance = gpa->rgt_height - gpa->lft_height; |
815 | if (balance == -1) { |
815 | if (balance == -1) { |
816 | /* |
816 | /* |
817 | * Stop balancing, tree might be balanced or not, whole tree is repaired only during insertion. |
817 | * Stop balancing, tree might be balanced or not, whole tree is repaired only during insertion. |
818 | */ |
818 | */ |
819 | break; |
819 | break; |
820 | } else if (balance == -2) { |
820 | } else if (balance == -2) { |
821 | /* |
821 | /* |
822 | * Balance was corrupted - must be repaired. |
822 | * Balance was corrupted - must be repaired. |
823 | */ |
823 | */ |
824 | par = gpa->lft; |
824 | par = gpa->lft; |
825 | 825 | ||
826 | if ((par->rgt_height - par->lft_height) >= +1) { |
826 | if ((par->rgt_height - par->lft_height) >= +1) { |
827 | /* |
827 | /* |
828 | * If balance is -2 then par node always exists. |
828 | * If balance is -2 then par node always exists. |
829 | */ |
829 | */ |
830 | if ((gpa->lft_height - (extavlreltree_tree_height(par))) == 1) { |
830 | if ((gpa->lft_height - (extavlreltree_tree_height(par))) == 1) { |
831 | /* |
831 | /* |
832 | * LR rotation. Height of par subtree is not decreased due to timeout operation. |
832 | * LR rotation. Height of par subtree is not decreased due to timeout operation. |
833 | */ |
833 | */ |
834 | 834 | ||
835 | cur = par->rgt; |
835 | cur = par->rgt; |
836 | par->rgt = cur->lft; |
836 | par->rgt = cur->lft; |
837 | cur->lft = par; |
837 | cur->lft = par; |
838 | gpa->lft = cur->rgt; |
838 | gpa->lft = cur->rgt; |
839 | cur->rgt = gpa; |
839 | cur->rgt = gpa; |
840 | 840 | ||
841 | /* |
841 | /* |
842 | * Repair balances. |
842 | * Repair balances. |
843 | */ |
843 | */ |
844 | par->rgt_height = cur->lft_height; |
844 | par->rgt_height = cur->lft_height; |
845 | gpa->lft_height = cur->rgt_height; |
845 | gpa->lft_height = cur->rgt_height; |
846 | cur->rgt_height = gpa->rgt_height + 1; |
846 | cur->rgt_height = gpa->rgt_height + 1; |
847 | cur->lft_height = extavlreltree_tree_height(par) + 1; |
847 | cur->lft_height = extavlreltree_tree_height(par) + 1; |
848 | 848 | ||
849 | /* |
849 | /* |
850 | * Repair paternity. |
850 | * Repair paternity. |
851 | */ |
851 | */ |
852 | if (gpa->lft) gpa->lft->par = gpa; |
852 | if (gpa->lft) gpa->lft->par = gpa; |
853 | if (par->rgt) par->rgt->par = par; |
853 | if (par->rgt) par->rgt->par = par; |
854 | cur->par = gpa->par; |
854 | cur->par = gpa->par; |
855 | gpa->par = cur; |
855 | gpa->par = cur; |
856 | par->par = cur; |
856 | par->par = cur; |
857 | 857 | ||
858 | /* |
858 | /* |
859 | * Repair tree pointer which points to the current node. |
859 | * Repair tree pointer which points to the current node. |
860 | */ |
860 | */ |
861 | *gpapar = cur; |
861 | *gpapar = cur; |
862 | 862 | ||
863 | /* |
863 | /* |
864 | * Repair rgt_sums after rotation was done. |
864 | * Repair rgt_sums after rotation was done. |
865 | */ |
865 | */ |
866 | par->rgt_sum -= cur->key + cur->rgt_sum; |
866 | par->rgt_sum -= cur->key + cur->rgt_sum; |
867 | cur->rgt_sum += gpa->key + gpa->rgt_sum; |
867 | cur->rgt_sum += gpa->key + gpa->rgt_sum; |
868 | 868 | ||
869 | /* |
869 | /* |
870 | * Next balancing at parent node. |
870 | * Next balancing at parent node. |
871 | */ |
871 | */ |
872 | gpa = cur->par; |
872 | gpa = cur->par; |
873 | } else { |
873 | } else { |
874 | /* |
874 | /* |
875 | * Left subtree of cur has been already decreased by timeout operation. |
875 | * Left subtree of cur has been already decreased by timeout operation. |
876 | */ |
876 | */ |
877 | gpa = gpa->par; |
877 | gpa = gpa->par; |
878 | } |
878 | } |
879 | } else { |
879 | } else { |
880 | /* |
880 | /* |
881 | * LL rotation. |
881 | * LL rotation. |
882 | */ |
882 | */ |
883 | 883 | ||
884 | int prevlftheight = gpa->lft_height; |
884 | int prevlftheight = gpa->lft_height; |
885 | gpa->lft = par->rgt; |
885 | gpa->lft = par->rgt; |
886 | gpa->lft_height = par->rgt_height; |
886 | gpa->lft_height = par->rgt_height; |
887 | if (par->rgt) par->rgt->par = gpa; |
887 | if (par->rgt) par->rgt->par = gpa; |
888 | par->rgt = gpa; |
888 | par->rgt = gpa; |
889 | 889 | ||
890 | /* |
890 | /* |
891 | * Repair paternity. |
891 | * Repair paternity. |
892 | */ |
892 | */ |
893 | par->par = gpa->par; |
893 | par->par = gpa->par; |
894 | gpa->par = par; |
894 | gpa->par = par; |
895 | 895 | ||
896 | /* |
896 | /* |
897 | * Repair heights and tree pointer which points to the current node. |
897 | * Repair heights and tree pointer which points to the current node. |
898 | */ |
898 | */ |
899 | balance = par->rgt_height - par->lft_height; |
899 | balance = par->rgt_height - par->lft_height; |
900 | par->rgt_height = extavlreltree_tree_height(gpa) + 1; |
900 | par->rgt_height = extavlreltree_tree_height(gpa) + 1; |
901 | *gpapar = par; |
901 | *gpapar = par; |
902 | 902 | ||
903 | /* |
903 | /* |
904 | * Repair rgt_sums after rotation was done. |
904 | * Repair rgt_sums after rotation was done. |
905 | */ |
905 | */ |
906 | par->rgt_sum += gpa->key + gpa->rgt_sum; |
906 | par->rgt_sum += gpa->key + gpa->rgt_sum; |
907 | 907 | ||
908 | /* |
908 | /* |
909 | * Ends balancing when heights in par nodes are balanced and height |
909 | * Ends balancing when heights in par nodes are balanced and height |
910 | * of par subtree wasn't decreased due to timeout operation or do |
910 | * of par subtree wasn't decreased due to timeout operation or do |
911 | * the next step. |
911 | * the next step. |
912 | */ |
912 | */ |
913 | if (balance == 0 && par->rgt_height == prevlftheight) { |
913 | if (balance == 0 && par->rgt_height == prevlftheight) { |
914 | gpa = par; |
914 | gpa = par; |
915 | break; |
915 | break; |
916 | } |
916 | } |
917 | gpa = par->par; |
917 | gpa = par->par; |
918 | } |
918 | } |
919 | } else { |
919 | } else { |
920 | /* |
920 | /* |
921 | * Current node is balanced - perform balance check of its parent. |
921 | * Current node is balanced - perform balance check of its parent. |
922 | */ |
922 | */ |
923 | gpa = gpa->par; |
923 | gpa = gpa->par; |
924 | } |
924 | } |
925 | } |
925 | } |
926 | /* |
926 | /* |
927 | * When root is reached then end balancing. |
927 | * When root is reached then end balancing. |
928 | */ |
928 | */ |
929 | if (!gpa) return; |
929 | if (!gpa) return; |
930 | 930 | ||
931 | dir = dir2; |
931 | dir = dir2; |
932 | } |
932 | } |
933 | 933 | ||
934 | /* |
934 | /* |
935 | * End balancing. We must continue in repairing rgt_sum until we |
935 | * End balancing. We must continue in repairing rgt_sum until we |
936 | * reach first left child. |
936 | * reach first left child. |
937 | */ |
937 | */ |
938 | if (repair_rgt_sum) { |
938 | if (repair_rgt_sum) { |
939 | cur = gpa; |
939 | cur = gpa; |
940 | gpa = gpa->par; |
940 | gpa = gpa->par; |
941 | while (gpa) { |
941 | while (gpa) { |
942 | if (gpa->lft == cur) |
942 | if (gpa->lft == cur) |
943 | break; |
943 | break; |
944 | gpa->rgt_sum -= key; |
944 | gpa->rgt_sum -= key; |
945 | cur = gpa; |
945 | cur = gpa; |
946 | gpa = gpa->par; |
946 | gpa = gpa->par; |
947 | } |
947 | } |
948 | } |
948 | } |
949 | } |
949 | } |
950 | 950 | ||
951 | 951 | ||
952 | /** Delete node from ExtAVLirel tree with the smallest key. |
952 | /** Delete node from ExtAVLirel tree with the smallest key. |
953 | * |
953 | * |
954 | * Be careful deleted node must have key equal 0 to perform regular timeout. |
954 | * Be careful deleted node must have key equal 0 to perform regular timeout. |
955 | * |
955 | * |
956 | * @param t ExtAVLrel tree structure. |
956 | * @param t ExtAVLrel tree structure. |
957 | */ |
957 | */ |
958 | bool extavlreltree_delete_min(extavlreltree_t *t) |
958 | bool extavlreltree_delete_min(extavlreltree_t *t) |
959 | { |
959 | { |
960 | extavlreltree_node_t *expnode; |
960 | extavlreltree_node_t *expnode; |
961 | extavlreltree_node_t *nextnode; |
961 | extavlreltree_node_t *nextnode; |
962 | 962 | ||
963 | ASSERT(t); |
963 | ASSERT(t); |
964 | 964 | ||
965 | expnode = t->head.next; |
965 | expnode = t->head.next; |
966 | nextnode = expnode->next; |
966 | nextnode = expnode->next; |
967 | 967 | ||
968 | if (&t->head == expnode) return false; |
968 | if (&t->head == expnode) return false; |
969 | 969 | ||
970 | if (nextnode != &t->head) { |
970 | if (nextnode != &t->head) { |
971 | /* |
971 | /* |
972 | * Only first node in the list can be tree node and its key can be 0 (nextnode is the second). |
972 | * Only first node in the list can be tree node and its key can be 0 (nextnode is the second). |
973 | */ |
973 | */ |
974 | if (nextnode->key == 0) { |
974 | if (nextnode->key == 0) { |
975 | /* |
975 | /* |
976 | * Next node of expnode is its chain node. Copy expnode into nextnode. |
976 | * Next node of expnode is its chain node. Copy expnode into nextnode. |
977 | */ |
977 | */ |
978 | 978 | ||
979 | nextnode->lft = expnode->lft; |
979 | nextnode->lft = expnode->lft; |
980 | nextnode->rgt = expnode->rgt; |
980 | nextnode->rgt = expnode->rgt; |
981 | nextnode->par = expnode->par; |
981 | nextnode->par = expnode->par; |
982 | nextnode->lft_height = expnode->lft_height; |
982 | nextnode->lft_height = expnode->lft_height; |
983 | nextnode->rgt_height = expnode->rgt_height; |
983 | nextnode->rgt_height = expnode->rgt_height; |
984 | if (t->root == expnode) |
984 | if (t->root == expnode) |
985 | t->root = nextnode; |
985 | t->root = nextnode; |
986 | else |
986 | else |
987 | if (expnode->par->lft == expnode) |
987 | if (expnode->par->lft == expnode) |
988 | expnode->par->lft = nextnode; |
988 | expnode->par->lft = nextnode; |
989 | else |
989 | else |
990 | expnode->par->rgt = nextnode; |
990 | expnode->par->rgt = nextnode; |
991 | 991 | ||
992 | if (expnode->lft) expnode->lft->par = nextnode; |
992 | if (expnode->lft) expnode->lft->par = nextnode; |
993 | if (expnode->rgt) expnode->rgt->par = nextnode; |
993 | if (expnode->rgt) expnode->rgt->par = nextnode; |
994 | 994 | ||
995 | nextnode->rgt_sum = expnode->rgt_sum; |
995 | nextnode->rgt_sum = expnode->rgt_sum; |
996 | } else if (!expnode->par) { |
996 | } else if (!expnode->par) { |
997 | /* |
997 | /* |
998 | * Delete root node which musn't have left son. |
998 | * Delete root node which musn't have left son. |
999 | */ |
999 | */ |
1000 | 1000 | ||
1001 | t->root = expnode->rgt; |
1001 | t->root = expnode->rgt; |
1002 | if (expnode->rgt) expnode->rgt->par = NULL; |
1002 | if (expnode->rgt) expnode->rgt->par = NULL; |
1003 | } else if (expnode->rgt) { |
1003 | } else if (expnode->rgt) { |
1004 | /* |
1004 | /* |
1005 | * Always delete parent of left son. |
1005 | * Always delete parent of left son. |
1006 | */ |
1006 | */ |
1007 | 1007 | ||
1008 | expnode->rgt->par = expnode->par; |
1008 | expnode->rgt->par = expnode->par; |
1009 | expnode->par->lft = expnode->rgt; |
1009 | expnode->par->lft = expnode->rgt; |
1010 | expnode->par->lft_height = expnode->rgt_height; |
1010 | expnode->par->lft_height = expnode->rgt_height; |
1011 | } else { |
1011 | } else { |
1012 | /* |
1012 | /* |
1013 | * Deleted node doesn't have right son. |
1013 | * Deleted node doesn't have right son. |
1014 | */ |
1014 | */ |
1015 | 1015 | ||
1016 | expnode->par->lft = NULL; |
1016 | expnode->par->lft = NULL; |
1017 | expnode->par->lft_height = 0; |
1017 | expnode->par->lft_height = 0; |
1018 | } |
1018 | } |
1019 | nextnode->key += expnode->key; |
1019 | nextnode->key += expnode->key; |
1020 | } |
1020 | } |
1021 | 1021 | ||
1022 | /* |
1022 | /* |
1023 | * Delete node from the list. |
1023 | * Delete node from the list. |
1024 | */ |
1024 | */ |
1025 | t->head.next = nextnode; |
1025 | t->head.next = nextnode; |
1026 | nextnode->prev = &t->head; |
1026 | nextnode->prev = &t->head; |
1027 | 1027 | ||
1028 | return true; |
1028 | return true; |
1029 | } |
1029 | } |
1030 | 1030 |