Rev 2421 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 2421 | Rev 2431 | ||
---|---|---|---|
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 implementation. |
35 | * @brief Extended AVL tree implementation. |
36 | * |
36 | * |
37 | * This file implements Extended AVL tree type and operations. |
37 | * This file implements Extended AVL tree type and operations. |
38 | * |
38 | * |
39 | * Extended AVL tree (ExtAvl tree) has the following properties: |
39 | * Extended AVL tree (ExtAvl tree) has the following properties: |
40 | * @li it is binary search tree with unique keys |
40 | * @li it is binary search tree with unique 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 keys are linked to the tree nodes of the same key, they are not tree nodes |
43 | * @li nodes with the same 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 keys |
45 | * @li nodes are connected in the list ascendentaly according to their keys |
46 | * |
46 | * |
47 | * Be careful of using this tree because of base atribute, which is added to every inserted |
47 | * Be careful of using this tree because of base atribute, which is added to every inserted |
48 | * node key. |
48 | * node key. |
49 | */ |
49 | */ |
50 | 50 | ||
51 | #include <adt/extavl.h> |
51 | #include <adt/extavl.h> |
52 | #include <debug.h> |
52 | #include <debug.h> |
53 | #include <panic.h> |
53 | #include <panic.h> |
54 | 54 | ||
55 | #define AVLTREE_LEFT 0 |
55 | #define AVLTREE_LEFT 0 |
56 | #define AVLTREE_RIGHT 1 |
56 | #define AVLTREE_RIGHT 1 |
57 | 57 | ||
58 | /* Returns height of tree -1 */ |
58 | /* Returns height of tree -1 */ |
59 | #define extavltree_tree_height(node) (((node) == NULL) ? (-1) : (((node)->lft_height>(node)->rgt_height)?(node)->lft_height:(node)->rgt_height)) |
59 | #define extavltree_tree_height(node) (((node) == NULL) ? (-1) : (((node)->lft_height>(node)->rgt_height)?(node)->lft_height:(node)->rgt_height)) |
60 | 60 | ||
61 | /** Search first occurence (oldest node with this key) of given key in Extended AVL tree. |
61 | /** Search first occurence (oldest node with this key) of given key in Extended AVL tree. |
62 | * |
62 | * |
63 | * @param t Extended AVL tree. |
63 | * @param t Extended AVL tree. |
64 | * @param key Key to be searched. |
64 | * @param key Key to be searched. |
65 | * |
65 | * |
66 | * @return Pointer to node or NULL if there is no such key. |
66 | * @return Pointer to node or NULL if there is no such key. |
67 | */ |
67 | */ |
68 | extavltree_node_t *extavltree_search(extavltree_t *t, uint64_t key) |
68 | extavltree_node_t *extavltree_search(extavltree_t *t, uint64_t key) |
69 | { |
69 | { |
70 | extavltree_node_t *cur; |
70 | extavltree_node_t *cur; |
71 | 71 | ||
72 | cur = t->root; |
72 | cur = t->root; |
73 | while (cur != NULL) { |
73 | while (cur != NULL) { |
74 | if (cur->key < key) { |
74 | if (cur->key < key) { |
75 | cur = cur->rgt; |
75 | cur = cur->rgt; |
76 | } else if (cur->key > key) { |
76 | } else if (cur->key > key) { |
77 | cur = cur->lft; |
77 | cur = cur->lft; |
78 | } else { |
78 | } else { |
79 | return cur; |
79 | return cur; |
80 | } |
80 | } |
81 | } |
81 | } |
82 | return NULL; |
82 | return NULL; |
83 | } |
83 | } |
84 | 84 | ||
85 | /** Insert new node into ExtAVL tree. |
85 | /** Insert new node into ExtAVL tree. |
86 | * |
86 | * |
87 | * New node's key must be set. |
87 | * New node's key must be set. |
88 | * |
88 | * |
89 | * @param t ExtAVL tree structure. |
89 | * @param t ExtAVL tree structure. |
90 | * @param newnode New node to be inserted. |
90 | * @param newnode New node to be inserted. |
91 | */ |
91 | */ |
92 | void extavltree_insert(extavltree_t *t, extavltree_node_t *newnode) |
92 | void extavltree_insert(extavltree_t *t, extavltree_node_t *newnode) |
93 | { |
93 | { |
94 | extavltree_node_t *cur; |
94 | extavltree_node_t *cur; |
95 | extavltree_node_t *son; |
95 | extavltree_node_t *son; |
96 | extavltree_node_t *gpa; |
96 | extavltree_node_t *gpa; |
97 | extavltree_node_t *par; |
97 | extavltree_node_t *par; |
98 | uint64_t key; |
98 | uint64_t key; |
99 | 99 | ||
100 | ASSERT(t); |
100 | ASSERT(t); |
101 | ASSERT(newnode); |
101 | ASSERT(newnode); |
102 | 102 | ||
103 | /* |
103 | /* |
104 | * Creating absolute key. |
104 | * Creating absolute key. |
105 | */ |
105 | */ |
106 | newnode->key = key = newnode->key + t->base; |
106 | newnode->key = key = newnode->key + t->base; |
107 | 107 | ||
108 | 108 | ||
109 | /* |
109 | /* |
110 | * Insert first node into empty tree. |
110 | * Insert first node into empty tree. |
111 | */ |
111 | */ |
112 | if (t->root == NULL) { |
112 | if (t->root == NULL) { |
113 | newnode->lft = NULL; |
113 | newnode->lft = NULL; |
114 | newnode->rgt = NULL; |
114 | newnode->rgt = NULL; |
115 | newnode->lft_height = 0; |
115 | newnode->lft_height = 0; |
116 | newnode->rgt_height = 0; |
116 | newnode->rgt_height = 0; |
117 | newnode->par = NULL; |
117 | newnode->par = NULL; |
118 | newnode->next = &t->head; |
118 | newnode->next = &t->head; |
119 | newnode->prev = &t->head; |
119 | newnode->prev = &t->head; |
120 | 120 | ||
121 | t->head.prev = newnode; |
121 | t->head.prev = newnode; |
122 | t->head.next = newnode; |
122 | t->head.next = newnode; |
123 | t->root = newnode; |
123 | t->root = newnode; |
124 | return; |
124 | return; |
125 | } |
125 | } |
126 | 126 | ||
127 | /* |
127 | /* |
128 | * Tree is not empty - search for the right place for new node. |
128 | * Tree is not empty - search for the right place for new node. |
129 | */ |
129 | */ |
130 | cur = t->root; |
130 | cur = t->root; |
131 | while(true) { |
131 | while(true) { |
132 | if (cur->key < key) { |
132 | if (cur->key < key) { |
133 | if (!cur->rgt) { |
133 | if (!cur->rgt) { |
134 | /* |
134 | /* |
135 | * We have reach leaf. New node will be right son. |
135 | * We have reach leaf. New node will be right son. |
136 | */ |
136 | */ |
137 | cur->rgt = newnode; |
137 | cur->rgt = newnode; |
138 | 138 | ||
139 | newnode->lft = NULL; |
139 | newnode->lft = NULL; |
140 | newnode->rgt = NULL; |
140 | newnode->rgt = NULL; |
141 | newnode->lft_height = 0; |
141 | newnode->lft_height = 0; |
142 | newnode->rgt_height = 0; |
142 | newnode->rgt_height = 0; |
143 | newnode->par = cur; |
143 | newnode->par = cur; |
144 | 144 | ||
145 | newnode->prev = cur; |
145 | newnode->prev = cur; |
146 | newnode->next = cur->next; |
146 | newnode->next = cur->next; |
147 | cur->next->prev = newnode; |
147 | cur->next->prev = newnode; |
148 | cur->next = newnode; |
148 | cur->next = newnode; |
149 | break; |
149 | break; |
150 | } |
150 | } |
151 | cur = cur->rgt; |
151 | cur = cur->rgt; |
152 | } else if (cur->key > key) { |
152 | } else if (cur->key > key) { |
153 | if (!cur->lft) { |
153 | if (!cur->lft) { |
154 | /* |
154 | /* |
155 | * We have reach leaf. New node will be left son. |
155 | * We have reach leaf. New node will be left son. |
156 | */ |
156 | */ |
157 | cur->lft = newnode; |
157 | cur->lft = newnode; |
158 | 158 | ||
159 | newnode->lft = NULL; |
159 | newnode->lft = NULL; |
160 | newnode->rgt = NULL; |
160 | newnode->rgt = NULL; |
161 | newnode->lft_height = 0; |
161 | newnode->lft_height = 0; |
162 | newnode->rgt_height = 0; |
162 | newnode->rgt_height = 0; |
163 | newnode->par = cur; |
163 | newnode->par = cur; |
164 | 164 | ||
165 | gpa = cur; |
165 | gpa = cur; |
166 | while (gpa != &t->head && gpa->key == cur->key) |
166 | while ((gpa != &t->head) && (gpa->key == cur->key)) |
167 | gpa = gpa->prev; |
167 | gpa = gpa->prev; |
168 | newnode->next = gpa->next; |
168 | newnode->next = gpa->next; |
169 | newnode->prev = gpa; |
169 | newnode->prev = gpa; |
170 | gpa->next->prev = newnode; |
170 | gpa->next->prev = newnode; |
171 | gpa->next = newnode; |
171 | gpa->next = newnode; |
172 | break; |
172 | break; |
173 | } |
173 | } |
174 | cur = cur->lft; |
174 | cur = cur->lft; |
175 | } else { |
175 | } else { |
176 | /* |
176 | /* |
177 | * Key has been previously inserted into tree. Make new node as a tree node |
177 | * Key has been previously inserted into tree. Make new node as a tree node |
178 | * and old tree node move to the prev. Old tree node will be list node. |
178 | * and old tree node move to the prev. Old tree node will be list node. |
179 | */ |
179 | */ |
180 | 180 | ||
181 | newnode->prev = cur; |
181 | newnode->prev = cur; |
182 | newnode->next = cur->next; |
182 | newnode->next = cur->next; |
183 | cur->next->prev = newnode; |
183 | cur->next->prev = newnode; |
184 | cur->next = newnode; |
184 | cur->next = newnode; |
185 | 185 | ||
186 | newnode->par = cur->par; |
186 | newnode->par = cur->par; |
187 | cur->par = NULL; |
187 | cur->par = NULL; |
188 | newnode->lft = cur->lft; |
188 | newnode->lft = cur->lft; |
189 | cur->lft = NULL; |
189 | cur->lft = NULL; |
190 | newnode->rgt = cur->rgt; |
190 | newnode->rgt = cur->rgt; |
191 | cur->rgt = NULL; |
191 | cur->rgt = NULL; |
192 | newnode->lft_height = cur->lft_height; |
192 | newnode->lft_height = cur->lft_height; |
193 | cur->lft_height = 0; |
193 | cur->lft_height = 0; |
194 | newnode->rgt_height = cur->rgt_height; |
194 | newnode->rgt_height = cur->rgt_height; |
195 | cur->rgt_height = 0; |
195 | cur->rgt_height = 0; |
196 | 196 | ||
197 | if (newnode->lft) newnode->lft->par = newnode; |
197 | if (newnode->lft) newnode->lft->par = newnode; |
198 | if (newnode->rgt) newnode->rgt->par = newnode; |
198 | if (newnode->rgt) newnode->rgt->par = newnode; |
199 | if (newnode->par) { |
199 | if (newnode->par) { |
200 | if (newnode->par->lft == cur) |
200 | if (newnode->par->lft == cur) |
201 | newnode->par->lft = newnode; |
201 | newnode->par->lft = newnode; |
202 | else |
202 | else |
203 | newnode->par->rgt = newnode; |
203 | newnode->par->rgt = newnode; |
204 | } else { |
204 | } else { |
205 | t->root = newnode; |
205 | t->root = newnode; |
206 | } |
206 | } |
207 | return; |
207 | return; |
208 | } |
208 | } |
209 | } |
209 | } |
210 | 210 | ||
211 | /* |
211 | /* |
212 | * Balancing all nodes from newnode's parent down to root. All nodes must be checked |
212 | * Balancing all nodes from newnode's parent down to root. All nodes must be checked |
213 | * because delete min operation can corrupt heights and only insert operation can |
213 | * because delete min operation can corrupt heights and only insert operation can |
214 | * repair it. |
214 | * repair it. |
215 | */ |
215 | */ |
216 | cur = newnode->par; |
216 | cur = newnode->par; |
217 | while (cur) { |
217 | while (cur) { |
218 | if (cur->key > key) { |
218 | if (cur->key > key) { |
219 | /* |
219 | /* |
220 | * Insertion was made in the left subtree - repair left height |
220 | * Insertion was made in the left subtree - repair left height |
221 | * and check balance of current node. |
221 | * and check balance of current node. |
222 | */ |
222 | */ |
223 | cur->lft_height = extavltree_tree_height(cur->lft) + 1; |
223 | cur->lft_height = extavltree_tree_height(cur->lft) + 1; |
224 | 224 | ||
225 | if ((cur->rgt_height - cur->lft_height) <= -2) { |
225 | if ((cur->rgt_height - cur->lft_height) <= -2) { |
226 | /* |
226 | /* |
227 | * Balance was corrupted, must be repaired through LL or LR rotation. |
227 | * Balance was corrupted, must be repaired through LL or LR rotation. |
228 | */ |
228 | */ |
229 | par = cur->par; |
229 | par = cur->par; |
230 | son = cur->lft; |
230 | son = cur->lft; |
231 | if ((son->rgt_height - son->lft_height) != 1) { |
231 | if ((son->rgt_height - son->lft_height) != 1) { |
232 | /* |
232 | /* |
233 | * LL rotation |
233 | * LL rotation |
234 | */ |
234 | */ |
235 | 235 | ||
236 | gpa = son; |
236 | gpa = son; |
237 | cur->lft = son->rgt; |
237 | cur->lft = son->rgt; |
238 | if (cur->lft != NULL) cur->lft->par = cur; |
238 | if (cur->lft != NULL) cur->lft->par = cur; |
239 | cur->par = son; |
239 | cur->par = son; |
240 | son->rgt = cur; |
240 | son->rgt = cur; |
241 | /* |
241 | /* |
242 | * Repair heights. |
242 | * Repair heights. |
243 | */ |
243 | */ |
244 | cur->lft_height = son->rgt_height; |
244 | cur->lft_height = son->rgt_height; |
245 | son->rgt_height = extavltree_tree_height(cur) + 1; |
245 | son->rgt_height = extavltree_tree_height(cur) + 1; |
246 | } else { |
246 | } else { |
247 | /* |
247 | /* |
248 | * LR rotation |
248 | * LR rotation |
249 | */ |
249 | */ |
250 | 250 | ||
251 | gpa = son->rgt; |
251 | gpa = son->rgt; |
252 | son->rgt = gpa->lft; |
252 | son->rgt = gpa->lft; |
253 | if (gpa->lft != NULL) gpa->lft->par = son; |
253 | if (gpa->lft != NULL) gpa->lft->par = son; |
254 | gpa->lft = son; |
254 | gpa->lft = son; |
255 | son->par = gpa; |
255 | son->par = gpa; |
256 | cur->lft = gpa->rgt; |
256 | cur->lft = gpa->rgt; |
257 | if (gpa->rgt != NULL) gpa->rgt->par = cur; |
257 | if (gpa->rgt != NULL) gpa->rgt->par = cur; |
258 | gpa->rgt = cur; |
258 | gpa->rgt = cur; |
259 | cur->par = gpa; |
259 | cur->par = gpa; |
260 | /* |
260 | /* |
261 | * Repair heights. |
261 | * Repair heights. |
262 | */ |
262 | */ |
263 | cur->lft_height = gpa->rgt_height; |
263 | cur->lft_height = gpa->rgt_height; |
264 | son->rgt_height = gpa->lft_height; |
264 | son->rgt_height = gpa->lft_height; |
265 | gpa->rgt_height = extavltree_tree_height(cur) + 1; |
265 | gpa->rgt_height = extavltree_tree_height(cur) + 1; |
266 | gpa->lft_height = extavltree_tree_height(son) + 1; |
266 | gpa->lft_height = extavltree_tree_height(son) + 1; |
267 | } |
267 | } |
268 | 268 | ||
269 | /* |
269 | /* |
270 | * Change parent pointers or if current node is root then |
270 | * Change parent pointers or if current node is root then |
271 | * change root atribute pointer. |
271 | * change root atribute pointer. |
272 | */ |
272 | */ |
273 | gpa->par = par; |
273 | gpa->par = par; |
274 | if (par) { |
274 | if (par) { |
275 | if (par->lft == cur) |
275 | if (par->lft == cur) |
276 | par->lft = gpa; |
276 | par->lft = gpa; |
277 | else |
277 | else |
278 | par->rgt = gpa; |
278 | par->rgt = gpa; |
279 | } else { |
279 | } else { |
280 | t->root = gpa; |
280 | t->root = gpa; |
281 | } |
281 | } |
282 | cur = par; |
282 | cur = par; |
283 | } else { |
283 | } else { |
284 | /* |
284 | /* |
285 | * Current node is balanced, continue balancing of its parent. |
285 | * Current node is balanced, continue balancing of its parent. |
286 | */ |
286 | */ |
287 | cur = cur->par; |
287 | cur = cur->par; |
288 | } |
288 | } |
289 | } else { |
289 | } else { |
290 | /* |
290 | /* |
291 | * Insertion was made in the right subtree - repair right height |
291 | * Insertion was made in the right subtree - repair right height |
292 | * and check balance of current node. |
292 | * and check balance of current node. |
293 | */ |
293 | */ |
294 | cur->rgt_height = extavltree_tree_height(cur->rgt) + 1; |
294 | cur->rgt_height = extavltree_tree_height(cur->rgt) + 1; |
295 | 295 | ||
296 | if ((cur->rgt_height - cur->lft_height) >= 2) { |
296 | if ((cur->rgt_height - cur->lft_height) >= 2) { |
297 | /* |
297 | /* |
298 | * Balance was corrupted, must be repaired through LL or LR rotation. |
298 | * Balance was corrupted, must be repaired through LL or LR rotation. |
299 | */ |
299 | */ |
300 | par = cur->par; |
300 | par = cur->par; |
301 | son = cur->rgt; |
301 | son = cur->rgt; |
302 | if ((son->rgt_height - son->lft_height) != -1) { |
302 | if ((son->rgt_height - son->lft_height) != -1) { |
303 | /* |
303 | /* |
304 | * RR rotation |
304 | * RR rotation |
305 | */ |
305 | */ |
306 | gpa = son; |
306 | gpa = son; |
307 | cur->rgt = son->lft; |
307 | cur->rgt = son->lft; |
308 | if (cur->rgt != NULL) cur->rgt->par = cur; |
308 | if (cur->rgt != NULL) cur->rgt->par = cur; |
309 | cur->par = son; |
309 | cur->par = son; |
310 | son->lft = cur; |
310 | son->lft = cur; |
311 | /* |
311 | /* |
312 | * Repair heights. |
312 | * Repair heights. |
313 | */ |
313 | */ |
314 | cur->rgt_height = son->lft_height; |
314 | cur->rgt_height = son->lft_height; |
315 | son->lft_height = extavltree_tree_height(cur) + 1; |
315 | son->lft_height = extavltree_tree_height(cur) + 1; |
316 | } else { |
316 | } else { |
317 | /* |
317 | /* |
318 | * RL rotation |
318 | * RL rotation |
319 | */ |
319 | */ |
320 | gpa = son->lft; |
320 | gpa = son->lft; |
321 | son->lft = gpa->rgt; |
321 | son->lft = gpa->rgt; |
322 | if (gpa->rgt != NULL) gpa->rgt->par = son; |
322 | if (gpa->rgt != NULL) gpa->rgt->par = son; |
323 | gpa->rgt = son; |
323 | gpa->rgt = son; |
324 | son->par = gpa; |
324 | son->par = gpa; |
325 | cur->rgt = gpa->lft; |
325 | cur->rgt = gpa->lft; |
326 | if (gpa->lft != NULL) gpa->lft->par = cur; |
326 | if (gpa->lft != NULL) gpa->lft->par = cur; |
327 | gpa->lft = cur; |
327 | gpa->lft = cur; |
328 | cur->par = gpa; |
328 | cur->par = gpa; |
329 | /* |
329 | /* |
330 | * Repair heights. |
330 | * Repair heights. |
331 | */ |
331 | */ |
332 | cur->rgt_height = gpa->lft_height; |
332 | cur->rgt_height = gpa->lft_height; |
333 | son->lft_height = gpa->rgt_height; |
333 | son->lft_height = gpa->rgt_height; |
334 | gpa->lft_height = extavltree_tree_height(cur) + 1; |
334 | gpa->lft_height = extavltree_tree_height(cur) + 1; |
335 | gpa->rgt_height = extavltree_tree_height(son) + 1; |
335 | gpa->rgt_height = extavltree_tree_height(son) + 1; |
336 | } |
336 | } |
337 | 337 | ||
338 | /* |
338 | /* |
339 | * Change parent pointers or if current node is root then |
339 | * Change parent pointers or if current node is root then |
340 | * change root atribute pointer. |
340 | * change root atribute pointer. |
341 | */ |
341 | */ |
342 | gpa->par = par; |
342 | gpa->par = par; |
343 | if (par) { |
343 | if (par) { |
344 | if (par->lft == cur) |
344 | if (par->lft == cur) |
345 | par->lft = gpa; |
345 | par->lft = gpa; |
346 | else |
346 | else |
347 | par->rgt = gpa; |
347 | par->rgt = gpa; |
348 | } else { |
348 | } else { |
349 | t->root = gpa; |
349 | t->root = gpa; |
350 | } |
350 | } |
351 | cur = par; |
351 | cur = par; |
352 | } else { |
352 | } else { |
353 | /* |
353 | /* |
354 | * Current node is balanced, continue balancing of its parent. |
354 | * Current node is balanced, continue balancing of its parent. |
355 | */ |
355 | */ |
356 | cur = cur->par; |
356 | cur = cur->par; |
357 | } |
357 | } |
358 | } |
358 | } |
359 | } |
359 | } |
360 | } |
360 | } |
361 | 361 | ||
362 | /** Delete node from ExtAVL tree. |
362 | /** Delete node from ExtAVL tree. |
363 | * |
363 | * |
364 | * @param t ExtAVL tree structure. |
364 | * @param t ExtAVL tree structure. |
365 | * @param node Address of node which will be deleted. |
365 | * @param node Address of node which will be deleted. |
366 | */ |
366 | */ |
367 | void extavltree_delete(extavltree_t *t, extavltree_node_t *node) |
367 | void extavltree_delete(extavltree_t *t, extavltree_node_t *node) |
368 | { |
368 | { |
369 | extavltree_node_t **gpapar; |
369 | extavltree_node_t **gpapar; |
370 | extavltree_node_t *cur; |
370 | extavltree_node_t *cur; |
371 | extavltree_node_t *par; |
371 | extavltree_node_t *par; |
372 | extavltree_node_t *gpa; |
372 | extavltree_node_t *gpa; |
373 | int8_t dir; |
373 | int8_t dir; |
374 | int8_t dir2=0; |
374 | int8_t dir2=0; |
375 | int16_t balance; |
375 | int16_t balance; |
376 | 376 | ||
377 | ASSERT(t); |
377 | ASSERT(t); |
378 | ASSERT(node); |
378 | ASSERT(node); |
379 | 379 | ||
380 | /* |
380 | /* |
381 | * Delete node from list. |
381 | * Delete node from list. |
382 | */ |
382 | */ |
383 | node->next->prev = node->prev; |
383 | node->next->prev = node->prev; |
384 | node->prev->next = node->next; |
384 | node->prev->next = node->next; |
385 | 385 | ||
386 | if (!node->par) { |
386 | if (!node->par) { |
387 | if (t->root != node) { |
387 | if (t->root != node) { |
388 | /* |
388 | /* |
389 | * It is list node (not a tree node). Needn't repair tree or anything else. |
389 | * It is list node (not a tree node). Needn't repair tree or anything else. |
390 | */ |
390 | */ |
391 | return; |
391 | return; |
392 | } |
392 | } |
393 | gpapar = &(t->root); |
393 | gpapar = &(t->root); |
394 | } else { |
394 | } else { |
395 | /* |
395 | /* |
396 | * Find tree pointer which points to node. |
396 | * Find tree pointer which points to node. |
397 | */ |
397 | */ |
398 | if (node->par->lft == node) { |
398 | if (node->par->lft == node) { |
399 | gpapar = &(node->par->lft); |
399 | gpapar = &(node->par->lft); |
400 | } else { |
400 | } else { |
401 | gpapar = &(node->par->rgt); |
401 | gpapar = &(node->par->rgt); |
402 | } |
402 | } |
403 | } |
403 | } |
404 | 404 | ||
405 | 405 | ||
406 | if (&t->head != node->prev && node->prev->key == node->key) { |
406 | if ((&t->head != node->prev) && (node->prev->key == node->key)) { |
407 | /* |
407 | /* |
408 | * Deleted node has at least one node node with the same key which is closest previous |
408 | * Deleted node has at least one node node with the same key which is closest previous |
409 | * neighbor in the list, copy node atributes into previous node and end. |
409 | * neighbor in the list, copy node atributes into previous node and end. |
410 | */ |
410 | */ |
411 | cur = node->prev; |
411 | cur = node->prev; |
412 | cur->lft = node->lft; |
412 | cur->lft = node->lft; |
413 | cur->rgt = node->rgt; |
413 | cur->rgt = node->rgt; |
414 | cur->par = node->par; |
414 | cur->par = node->par; |
415 | cur->lft_height = node->lft_height; |
415 | cur->lft_height = node->lft_height; |
416 | cur->rgt_height = node->rgt_height; |
416 | cur->rgt_height = node->rgt_height; |
417 | *gpapar = cur; |
417 | *gpapar = cur; |
418 | 418 | ||
419 | if (node->lft) node->lft->par = cur; |
419 | if (node->lft) node->lft->par = cur; |
420 | if (node->rgt) node->rgt->par = cur; |
420 | if (node->rgt) node->rgt->par = cur; |
421 | return; |
421 | return; |
422 | } |
422 | } |
423 | 423 | ||
424 | /* |
424 | /* |
425 | * Check situation in the tree around deleted node. |
425 | * Check situation in the tree around deleted node. |
426 | */ |
426 | */ |
427 | if (!node->lft) { |
427 | if (!node->lft) { |
428 | /* |
428 | /* |
429 | * Deleted node has not left son. Right son will take deleted node's place. |
429 | * Deleted node has not left son. Right son will take deleted node's place. |
430 | */ |
430 | */ |
431 | gpa = node->par; |
431 | gpa = node->par; |
432 | if (node->rgt) node->rgt->par = gpa; |
432 | if (node->rgt) node->rgt->par = gpa; |
433 | if (!gpa) { |
433 | if (!gpa) { |
434 | /* |
434 | /* |
435 | * Deleted node is root node. Balancing is finished, change only |
435 | * Deleted node is root node. Balancing is finished, change only |
436 | * root pointer in extavltree structure. |
436 | * root pointer in extavltree structure. |
437 | */ |
437 | */ |
438 | *gpapar = node->rgt; |
438 | *gpapar = node->rgt; |
439 | return; |
439 | return; |
440 | } |
440 | } |
441 | dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT; |
441 | dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT; |
442 | *gpapar = node->rgt; |
442 | *gpapar = node->rgt; |
443 | } else { |
443 | } else { |
444 | /* |
444 | /* |
445 | * Node has left son. |
445 | * Node has left son. |
446 | */ |
446 | */ |
447 | cur = node->lft; |
447 | cur = node->lft; |
448 | if (!cur->rgt) { |
448 | if (!cur->rgt) { |
449 | /* |
449 | /* |
450 | * Left son of node hasn't got right son. Left son will take deleted node's place. |
450 | * Left son of node hasn't got right son. Left son will take deleted node's place. |
451 | */ |
451 | */ |
452 | *gpapar = cur; |
452 | *gpapar = cur; |
453 | cur->par = node->par; |
453 | cur->par = node->par; |
454 | dir = AVLTREE_LEFT; |
454 | dir = AVLTREE_LEFT; |
455 | cur->rgt = node->rgt; |
455 | cur->rgt = node->rgt; |
456 | if (node->rgt) node->rgt->par = cur; |
456 | if (node->rgt) node->rgt->par = cur; |
457 | gpa = cur; |
457 | gpa = cur; |
458 | cur->rgt_height = node->rgt_height; |
458 | cur->rgt_height = node->rgt_height; |
459 | cur->lft_height = node->lft_height; |
459 | cur->lft_height = node->lft_height; |
460 | /* |
460 | /* |
461 | * cur->lft_height will be decreased in repair cycle. |
461 | * cur->lft_height will be decreased in repair cycle. |
462 | */ |
462 | */ |
463 | } else { |
463 | } else { |
464 | /* |
464 | /* |
465 | * Node has left and right son. Find a node with smallest key in left subtree |
465 | * Node has left and right son. Find a node with smallest key in left subtree |
466 | * and change that node with deleted node. |
466 | * and change that node with deleted node. |
467 | */ |
467 | */ |
468 | while (cur->rgt != NULL) |
468 | while (cur->rgt != NULL) |
469 | cur = cur->rgt; |
469 | cur = cur->rgt; |
470 | 470 | ||
471 | *gpapar = cur; |
471 | *gpapar = cur; |
472 | cur->rgt = node->rgt; |
472 | cur->rgt = node->rgt; |
473 | if (node->rgt) node->rgt->par = cur; |
473 | if (node->rgt) node->rgt->par = cur; |
474 | gpa = cur->par; |
474 | gpa = cur->par; |
475 | gpa->rgt = cur->lft; |
475 | gpa->rgt = cur->lft; |
476 | if (cur->lft) cur->lft->par = gpa; |
476 | if (cur->lft) cur->lft->par = gpa; |
477 | cur->lft = node->lft; |
477 | cur->lft = node->lft; |
478 | cur->lft->par = cur; |
478 | cur->lft->par = cur; |
479 | cur->par = node->par; |
479 | cur->par = node->par; |
480 | dir = AVLTREE_RIGHT; |
480 | dir = AVLTREE_RIGHT; |
481 | cur->lft_height = node->lft_height; |
481 | cur->lft_height = node->lft_height; |
482 | cur->rgt_height = node->rgt_height; |
482 | cur->rgt_height = node->rgt_height; |
483 | /* |
483 | /* |
484 | * gpa->rgt_height and cur->lft_height will be repaired in repair cycle. |
484 | * gpa->rgt_height and cur->lft_height will be repaired in repair cycle. |
485 | */ |
485 | */ |
486 | } |
486 | } |
487 | /* |
487 | /* |
488 | * Deleted node is root node. Balancing is finished. |
488 | * Deleted node is root node. Balancing is finished. |
489 | */ |
489 | */ |
490 | if (!gpa) return; |
490 | if (!gpa) return; |
491 | } |
491 | } |
492 | 492 | ||
493 | /* |
493 | /* |
494 | * Repair cycle which goes from gpa node down to root. |
494 | * Repair cycle which goes from gpa node down to root. |
495 | */ |
495 | */ |
496 | for(;;) { |
496 | for(;;) { |
497 | /* |
497 | /* |
498 | * Find tree pointer which points to the currently balanced node. When balanced |
498 | * Find tree pointer which points to the currently balanced node. When balanced |
499 | * node is root, root pointer from extavltree structure is taken. |
499 | * node is root, root pointer from extavltree structure is taken. |
500 | */ |
500 | */ |
501 | if (!gpa->par) |
501 | if (!gpa->par) |
502 | gpapar = &(t->root); |
502 | gpapar = &(t->root); |
503 | else { |
503 | else { |
504 | if (gpa->par->lft == gpa) { |
504 | if (gpa->par->lft == gpa) { |
505 | gpapar = &(gpa->par->lft); |
505 | gpapar = &(gpa->par->lft); |
506 | dir2 = AVLTREE_LEFT; |
506 | dir2 = AVLTREE_LEFT; |
507 | } else { |
507 | } else { |
508 | gpapar = &(gpa->par->rgt); |
508 | gpapar = &(gpa->par->rgt); |
509 | dir2 = AVLTREE_RIGHT; |
509 | dir2 = AVLTREE_RIGHT; |
510 | } |
510 | } |
511 | } |
511 | } |
512 | 512 | ||
513 | if (dir == AVLTREE_LEFT) { |
513 | if (dir == AVLTREE_LEFT) { |
514 | /* |
514 | /* |
515 | * Deletition was made in left subtree. |
515 | * Deletition was made in left subtree. |
516 | */ |
516 | */ |
517 | gpa->lft_height--; |
517 | gpa->lft_height--; |
518 | balance = gpa->rgt_height - gpa->lft_height; |
518 | balance = gpa->rgt_height - gpa->lft_height; |
519 | if (balance == 1) { |
519 | if (balance == 1) { |
520 | /* |
520 | /* |
521 | * Stop balancing, tree is balanced. |
521 | * Stop balancing, tree is balanced. |
522 | */ |
522 | */ |
523 | break; |
523 | break; |
524 | } else if (balance == 2) { |
524 | } else if (balance == 2) { |
525 | /* |
525 | /* |
526 | * Bad balance, heights of left and right subtrees differs more then is allowed. |
526 | * Bad balance, heights of left and right subtrees differs more then is allowed. |
527 | */ |
527 | */ |
528 | par = gpa->rgt; |
528 | par = gpa->rgt; |
529 | 529 | ||
530 | if ((par->rgt_height - par->lft_height) == -1) { |
530 | if ((par->rgt_height - par->lft_height) == -1) { |
531 | /* |
531 | /* |
532 | * RL rotation |
532 | * RL rotation |
533 | */ |
533 | */ |
534 | 534 | ||
535 | cur = par->lft; |
535 | cur = par->lft; |
536 | par->lft = cur->rgt; |
536 | par->lft = cur->rgt; |
537 | cur->rgt = par; |
537 | cur->rgt = par; |
538 | gpa->rgt = cur->lft; |
538 | gpa->rgt = cur->lft; |
539 | cur->lft = gpa; |
539 | cur->lft = gpa; |
540 | 540 | ||
541 | /* |
541 | /* |
542 | * Repair balances. |
542 | * Repair balances. |
543 | */ |
543 | */ |
544 | par->lft_height = cur->rgt_height; |
544 | par->lft_height = cur->rgt_height; |
545 | gpa->rgt_height = cur->lft_height; |
545 | gpa->rgt_height = cur->lft_height; |
546 | cur->lft_height = extavltree_tree_height(gpa) + 1; //POZOR nelze: cur->lft_height = gpa->lft_height + 1; - vyska cur je diky timeoutu nesttabilni |
546 | cur->lft_height = extavltree_tree_height(gpa) + 1; //POZOR nelze: cur->lft_height = gpa->lft_height + 1; - vyska cur je diky timeoutu nesttabilni |
547 | cur->rgt_height = par->rgt_height + 1; //POZOR zmena: cur->rgt_height = extavltree_tree_height(par) + 1; |
547 | cur->rgt_height = par->rgt_height + 1; //POZOR zmena: cur->rgt_height = extavltree_tree_height(par) + 1; |
548 | 548 | ||
549 | /* |
549 | /* |
550 | * Repair paternity. |
550 | * Repair paternity. |
551 | */ |
551 | */ |
552 | if (gpa->rgt) gpa->rgt->par = gpa; |
552 | if (gpa->rgt) gpa->rgt->par = gpa; |
553 | if (par->lft) par->lft->par = par; |
553 | if (par->lft) par->lft->par = par; |
554 | cur->par = gpa->par; |
554 | cur->par = gpa->par; |
555 | gpa->par = cur; |
555 | gpa->par = cur; |
556 | par->par = cur; |
556 | par->par = cur; |
557 | 557 | ||
558 | /* |
558 | /* |
559 | * Repair tree pointer which points to the current node and do the next step. |
559 | * Repair tree pointer which points to the current node and do the next step. |
560 | */ |
560 | */ |
561 | *gpapar = cur; |
561 | *gpapar = cur; |
562 | gpa = cur->par; |
562 | gpa = cur->par; |
563 | } else { |
563 | } else { |
564 | /* |
564 | /* |
565 | * RR rotation |
565 | * RR rotation |
566 | */ |
566 | */ |
567 | 567 | ||
568 | gpa->rgt = par->lft; |
568 | gpa->rgt = par->lft; |
569 | gpa->rgt_height = par->lft_height; |
569 | gpa->rgt_height = par->lft_height; |
570 | if (par->lft) par->lft->par = gpa; |
570 | if (par->lft) par->lft->par = gpa; |
571 | par->lft = gpa; |
571 | par->lft = gpa; |
572 | 572 | ||
573 | /* |
573 | /* |
574 | * Repair paternity. |
574 | * Repair paternity. |
575 | */ |
575 | */ |
576 | par->par = gpa->par; |
576 | par->par = gpa->par; |
577 | gpa->par = par; |
577 | gpa->par = par; |
578 | 578 | ||
579 | /* |
579 | /* |
580 | * Repair balances. |
580 | * Repair balances. |
581 | */ |
581 | */ |
582 | balance = par->rgt_height - par->lft_height; |
582 | balance = par->rgt_height - par->lft_height; |
583 | par->lft_height++; |
583 | par->lft_height++; |
584 | 584 | ||
585 | /* |
585 | /* |
586 | * Repair tree pointer which points to the current node, ends when tree is balanced |
586 | * Repair tree pointer which points to the current node, ends when tree is balanced |
587 | * or do the next step. |
587 | * or do the next step. |
588 | */ |
588 | */ |
589 | *gpapar = par; |
589 | *gpapar = par; |
590 | if (balance == 0) break; |
590 | if (balance == 0) break; |
591 | gpa = par->par; |
591 | gpa = par->par; |
592 | } |
592 | } |
593 | } else { |
593 | } else { |
594 | /* |
594 | /* |
595 | * Current node is balanced - perform balance check of its parent. |
595 | * Current node is balanced - perform balance check of its parent. |
596 | */ |
596 | */ |
597 | gpa = gpa->par; |
597 | gpa = gpa->par; |
598 | } |
598 | } |
599 | } else { |
599 | } else { |
600 | /* |
600 | /* |
601 | * Balance right son. |
601 | * Balance right son. |
602 | */ |
602 | */ |
603 | gpa->rgt_height--; |
603 | gpa->rgt_height--; |
604 | balance = gpa->rgt_height - gpa->lft_height; |
604 | balance = gpa->rgt_height - gpa->lft_height; |
605 | if (balance == -1) { |
605 | if (balance == -1) { |
606 | /* |
606 | /* |
607 | * Stop balancing, tree might be balanced or not, whole tree is repaired only during insertion. |
607 | * Stop balancing, tree might be balanced or not, whole tree is repaired only during insertion. |
608 | */ |
608 | */ |
609 | break; |
609 | break; |
610 | } else if (balance == -2) { |
610 | } else if (balance == -2) { |
611 | /* |
611 | /* |
612 | * Balance was corrupted - must be repaired. |
612 | * Balance was corrupted - must be repaired. |
613 | */ |
613 | */ |
614 | par = gpa->lft; |
614 | par = gpa->lft; |
615 | 615 | ||
616 | if ((par->rgt_height - par->lft_height) >= +1) { |
616 | if ((par->rgt_height - par->lft_height) >= +1) { |
617 | /* |
617 | /* |
618 | * If balance is -2 then par node always exists. |
618 | * If balance is -2 then par node always exists. |
619 | */ |
619 | */ |
620 | if ((gpa->lft_height - (extavltree_tree_height(par))) == 1) { |
620 | if ((gpa->lft_height - (extavltree_tree_height(par))) == 1) { |
621 | /* |
621 | /* |
622 | * LR rotation. Height of par subtree is not decreased due to timeout operation. |
622 | * LR rotation. Height of par subtree is not decreased due to timeout operation. |
623 | */ |
623 | */ |
624 | 624 | ||
625 | cur = par->rgt; |
625 | cur = par->rgt; |
626 | par->rgt = cur->lft; |
626 | par->rgt = cur->lft; |
627 | cur->lft = par; |
627 | cur->lft = par; |
628 | gpa->lft = cur->rgt; |
628 | gpa->lft = cur->rgt; |
629 | cur->rgt = gpa; |
629 | cur->rgt = gpa; |
630 | 630 | ||
631 | /* |
631 | /* |
632 | * Repair balances. |
632 | * Repair balances. |
633 | */ |
633 | */ |
634 | par->rgt_height = cur->lft_height; |
634 | par->rgt_height = cur->lft_height; |
635 | gpa->lft_height = cur->rgt_height; |
635 | gpa->lft_height = cur->rgt_height; |
636 | cur->rgt_height = gpa->rgt_height + 1; |
636 | cur->rgt_height = gpa->rgt_height + 1; |
637 | cur->lft_height = extavltree_tree_height(par) + 1; |
637 | cur->lft_height = extavltree_tree_height(par) + 1; |
638 | 638 | ||
639 | /* |
639 | /* |
640 | * Repair paternity. |
640 | * Repair paternity. |
641 | */ |
641 | */ |
642 | if (gpa->lft) gpa->lft->par = gpa; |
642 | if (gpa->lft) gpa->lft->par = gpa; |
643 | if (par->rgt) par->rgt->par = par; |
643 | if (par->rgt) par->rgt->par = par; |
644 | cur->par = gpa->par; |
644 | cur->par = gpa->par; |
645 | gpa->par = cur; |
645 | gpa->par = cur; |
646 | par->par = cur; |
646 | par->par = cur; |
647 | 647 | ||
648 | /* |
648 | /* |
649 | * Repair tree pointer which points to the current node and do the next step. |
649 | * Repair tree pointer which points to the current node and do the next step. |
650 | */ |
650 | */ |
651 | *gpapar = cur; |
651 | *gpapar = cur; |
652 | gpa = cur->par; |
652 | gpa = cur->par; |
653 | } else { |
653 | } else { |
654 | /* |
654 | /* |
655 | * Left subtree of cur has been already decreased by timeout operation. |
655 | * Left subtree of cur has been already decreased by timeout operation. |
656 | */ |
656 | */ |
657 | gpa = gpa->par; |
657 | gpa = gpa->par; |
658 | } |
658 | } |
659 | } else { |
659 | } else { |
660 | /* |
660 | /* |
661 | * LL rotation. |
661 | * LL rotation. |
662 | */ |
662 | */ |
663 | 663 | ||
664 | int prevlftheight = gpa->lft_height; |
664 | int prevlftheight = gpa->lft_height; |
665 | gpa->lft = par->rgt; |
665 | gpa->lft = par->rgt; |
666 | gpa->lft_height = par->rgt_height; |
666 | gpa->lft_height = par->rgt_height; |
667 | if (par->rgt) par->rgt->par = gpa; |
667 | if (par->rgt) par->rgt->par = gpa; |
668 | par->rgt = gpa; |
668 | par->rgt = gpa; |
669 | 669 | ||
670 | /* |
670 | /* |
671 | * Repair paternity. |
671 | * Repair paternity. |
672 | */ |
672 | */ |
673 | par->par = gpa->par; |
673 | par->par = gpa->par; |
674 | gpa->par = par; |
674 | gpa->par = par; |
675 | 675 | ||
676 | /* |
676 | /* |
677 | * Repair height. |
677 | * Repair height. |
678 | */ |
678 | */ |
679 | balance = par->rgt_height - par->lft_height; |
679 | balance = par->rgt_height - par->lft_height; |
680 | par->rgt_height = extavltree_tree_height(gpa) + 1; |
680 | par->rgt_height = extavltree_tree_height(gpa) + 1; |
681 | 681 | ||
682 | /* |
682 | /* |
683 | * Repair tree pointer which points to the current node, ends when heights in par nodes are |
683 | * Repair tree pointer which points to the current node, ends when heights in par nodes are |
684 | * balanced and height of par subtree wasn't decreased due to timeout operation orr do |
684 | * balanced and height of par subtree wasn't decreased due to timeout operation orr do |
685 | * the next step. |
685 | * the next step. |
686 | */ |
686 | */ |
687 | *gpapar = par; |
687 | *gpapar = par; |
688 | if (balance == 0 && par->rgt_height == prevlftheight) return; |
688 | if (balance == 0 && par->rgt_height == prevlftheight) return; |
689 | gpa = par->par; |
689 | gpa = par->par; |
690 | } |
690 | } |
691 | } else { |
691 | } else { |
692 | /* |
692 | /* |
693 | * Current node is balanced - perform balance check of its parent. |
693 | * Current node is balanced - perform balance check of its parent. |
694 | */ |
694 | */ |
695 | gpa = gpa->par; |
695 | gpa = gpa->par; |
696 | } |
696 | } |
697 | } |
697 | } |
698 | /* |
698 | /* |
699 | * When root is reached then end balancing. |
699 | * When root is reached then end balancing. |
700 | */ |
700 | */ |
701 | if (!gpa) return; |
701 | if (!gpa) return; |
702 | 702 | ||
703 | dir = dir2; |
703 | dir = dir2; |
704 | } |
704 | } |
705 | } |
705 | } |
706 | 706 | ||
707 | 707 | ||
708 | /** Delete node from ExtAVL tree with the smallest key and set base of tree to that key. |
708 | /** Delete node from ExtAVL tree with the smallest key and set base of tree to that key. |
709 | * |
709 | * |
710 | * @param t ExtAVL tree structure. |
710 | * @param t ExtAVL tree structure. |
711 | */ |
711 | */ |
712 | bool extavltree_delete_min(extavltree_t *t) |
712 | bool extavltree_delete_min(extavltree_t *t) |
713 | { |
713 | { |
714 | extavltree_node_t *expnode; |
714 | extavltree_node_t *expnode; |
715 | 715 | ||
716 | ASSERT(t); |
716 | ASSERT(t); |
717 | 717 | ||
718 | expnode = t->head.next; |
718 | expnode = t->head.next; |
719 | 719 | ||
720 | if (&t->head == expnode) return false; |
720 | if (&t->head == expnode) return false; |
721 | 721 | ||
722 | if (expnode->key != expnode->next->key) { |
722 | if (expnode->key != expnode->next->key) { |
723 | /* |
723 | /* |
724 | * Repair tree data structure. |
724 | * Repair tree data structure. |
725 | */ |
725 | */ |
726 | if (!expnode->par) { |
726 | if (!expnode->par) { |
727 | /* |
727 | /* |
728 | * Delete root node which musn't have left son. |
728 | * Delete root node which musn't have left son. |
729 | */ |
729 | */ |
730 | 730 | ||
731 | ASSERT(!expnode->lft); |
731 | ASSERT(!expnode->lft); |
732 | t->root = expnode->rgt; |
732 | t->root = expnode->rgt; |
733 | if (expnode->rgt) expnode->rgt->par = NULL; |
733 | if (expnode->rgt) expnode->rgt->par = NULL; |
734 | } else if (expnode->rgt) { |
734 | } else if (expnode->rgt) { |
735 | /* |
735 | /* |
736 | * Always delete parent of left son. |
736 | * Always delete parent of left son. |
737 | */ |
737 | */ |
738 | 738 | ||
739 | expnode->rgt->par = expnode->par; |
739 | expnode->rgt->par = expnode->par; |
740 | expnode->par->lft = expnode->rgt; |
740 | expnode->par->lft = expnode->rgt; |
741 | expnode->par->lft_height = expnode->rgt_height; |
741 | expnode->par->lft_height = expnode->rgt_height; |
742 | } else { |
742 | } else { |
743 | /* |
743 | /* |
744 | * Deleted node doesn't have right son. |
744 | * Deleted node doesn't have right son. |
745 | */ |
745 | */ |
746 | 746 | ||
747 | expnode->par->lft = NULL; |
747 | expnode->par->lft = NULL; |
748 | expnode->par->lft_height = 0; |
748 | expnode->par->lft_height = 0; |
749 | } |
749 | } |
- | 750 | } else if (expnode->next == &t->head) { |
|
- | 751 | /* |
|
- | 752 | * Special case of deleting last node with key equal 0. |
|
- | 753 | */ |
|
- | 754 | t->root = NULL; |
|
750 | } |
755 | } |
751 | 756 | ||
752 | /* |
757 | /* |
753 | * Delete node from the list. |
758 | * Delete node from the list. |
754 | */ |
759 | */ |
755 | t->head.next = expnode->next; |
760 | t->head.next = expnode->next; |
756 | expnode->next->prev = &t->head; |
761 | expnode->next->prev = &t->head; |
757 | 762 | ||
758 | return true; |
763 | return true; |
759 | } |
764 | } |
760 | 765 |