Mercurial > hg > octave-kai > gnulib-hg

comparison lib/gl_anyavltree_list2.h @ 12421:e8d2c6fc33ad

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Use spaces for indentation, not tabs.
author Bruno Haible <bruno@clisp.org>
date Thu, 10 Dec 2009 20:28:30 +0100
parents bbbbbf4cd1c5
children a8c91b846640
comparison
equal deleted inserted replaced
12420:5850b9a81029 12421:e8d2c6fc33ad
58 return node; 58 return node;
59 } 59 }
60 60
61 static gl_list_t 61 static gl_list_t
62 gl_tree_create (gl_list_implementation_t implementation, 62 gl_tree_create (gl_list_implementation_t implementation,
63 gl_listelement_equals_fn equals_fn, 63 gl_listelement_equals_fn equals_fn,
64 gl_listelement_hashcode_fn hashcode_fn, 64 gl_listelement_hashcode_fn hashcode_fn,
65 gl_listelement_dispose_fn dispose_fn, 65 gl_listelement_dispose_fn dispose_fn,
66 bool allow_duplicates, 66 bool allow_duplicates,
67 size_t count, const void **contents) 67 size_t count, const void **contents)
68 { 68 {
69 struct gl_list_impl *list = XMALLOC (struct gl_list_impl); 69 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
70 70
71 list->base.vtable = implementation; 71 list->base.vtable = implementation;
72 list->base.equals_fn = equals_fn; 72 list->base.equals_fn = equals_fn;
87 list->root = create_subtree_with_contents (count, contents); 87 list->root = create_subtree_with_contents (count, contents);
88 list->root->parent = NULL; 88 list->root->parent = NULL;
89 89
90 #if WITH_HASHTABLE 90 #if WITH_HASHTABLE
91 /* Now that the tree is built, node_position() works. Now we can 91 /* Now that the tree is built, node_position() works. Now we can
92 add the nodes to the hash table. */ 92 add the nodes to the hash table. */
93 add_nodes_to_buckets (list); 93 add_nodes_to_buckets (list);
94 #endif 94 #endif
95 } 95 }
96 else 96 else
97 list->root = NULL; 97 list->root = NULL;
103 The height of NODE is incremented by HEIGHT_DIFF (1 or -1). 103 The height of NODE is incremented by HEIGHT_DIFF (1 or -1).
104 PARENT = NODE->parent. (NODE can also be NULL. But PARENT is non-NULL.) 104 PARENT = NODE->parent. (NODE can also be NULL. But PARENT is non-NULL.)
105 Rotation operations are performed starting at PARENT (not NODE itself!). */ 105 Rotation operations are performed starting at PARENT (not NODE itself!). */
106 static void 106 static void
107 rebalance (gl_list_t list, 107 rebalance (gl_list_t list,
108 gl_list_node_t node, int height_diff, gl_list_node_t parent) 108 gl_list_node_t node, int height_diff, gl_list_node_t parent)
109 { 109 {
110 for (;;) 110 for (;;)
111 { 111 {
112 gl_list_node_t child; 112 gl_list_node_t child;
113 int previous_balance; 113 int previous_balance;
119 node = parent; 119 node = parent;
120 120
121 previous_balance = node->balance; 121 previous_balance = node->balance;
122 122
123 /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right 123 /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right
124 branch's height has increased by 1 or the left branch's height has 124 branch's height has increased by 1 or the left branch's height has
125 decreased by 1, -1 if the right branch's height has decreased by 1 or 125 decreased by 1, -1 if the right branch's height has decreased by 1 or
126 the left branch's height has increased by 1, 0 if no height change. */ 126 the left branch's height has increased by 1, 0 if no height change. */
127 if (node->left != NULL || node->right != NULL) 127 if (node->left != NULL || node->right != NULL)
128 balance_diff = (child == node->right ? height_diff : -height_diff); 128 balance_diff = (child == node->right ? height_diff : -height_diff);
129 else 129 else
130 /* Special case where above formula doesn't work, because the caller 130 /* Special case where above formula doesn't work, because the caller
131 didn't tell whether node's left or right branch shrunk from height 1 131 didn't tell whether node's left or right branch shrunk from height 1
132 to NULL. */ 132 to NULL. */
133 balance_diff = - previous_balance; 133 balance_diff = - previous_balance;
134 134
135 node->balance += balance_diff; 135 node->balance += balance_diff;
136 if (balance_diff == previous_balance) 136 if (balance_diff == previous_balance)
137 { 137 {
138 /* node->balance is outside the range [-1,1]. Must rotate. */ 138 /* node->balance is outside the range [-1,1]. Must rotate. */
139 gl_list_node_t *nodep; 139 gl_list_node_t *nodep;
140 140
141 if (node->parent == NULL) 141 if (node->parent == NULL)
142 /* node == list->root */ 142 /* node == list->root */
143 nodep = &list->root; 143 nodep = &list->root;
144 else if (node->parent->left == node) 144 else if (node->parent->left == node)
145 nodep = &node->parent->left; 145 nodep = &node->parent->left;
146 else if (node->parent->right == node) 146 else if (node->parent->right == node)
147 nodep = &node->parent->right; 147 nodep = &node->parent->right;
148 else 148 else
149 abort (); 149 abort ();
150 150
151 nodeleft = node->left; 151 nodeleft = node->left;
152 noderight = node->right; 152 noderight = node->right;
153 153
154 if (balance_diff < 0) 154 if (balance_diff < 0)
155 { 155 {
156 /* node->balance = -2. The subtree is heavier on the left side. 156 /* node->balance = -2. The subtree is heavier on the left side.
157 Rotate from left to right: 157 Rotate from left to right:
158 158
159 * 159 *
160 / \ 160 / \
161 h+2 h 161 h+2 h
162 */ 162 */
163 gl_list_node_t nodeleftleft = nodeleft->left; 163 gl_list_node_t nodeleftleft = nodeleft->left;
164 gl_list_node_t nodeleftright = nodeleft->right; 164 gl_list_node_t nodeleftright = nodeleft->right;
165 if (nodeleft->balance <= 0) 165 if (nodeleft->balance <= 0)
166 { 166 {
167 /* 167 /*
168 * h+2|h+3 168 * h+2|h+3
169 / \ / \ 169 / \ / \
170 h+2 h --> / h+1|h+2 170 h+2 h --> / h+1|h+2
171 / \ | / \ 171 / \ | / \
172 h+1 h|h+1 h+1 h|h+1 h 172 h+1 h|h+1 h+1 h|h+1 h
173 */ 173 */
174 node->left = nodeleftright; 174 node->left = nodeleftright;
175 nodeleft->right = node; 175 nodeleft->right = node;
176 176
177 nodeleft->parent = node->parent; 177 nodeleft->parent = node->parent;
178 node->parent = nodeleft; 178 node->parent = nodeleft;
179 if (nodeleftright != NULL) 179 if (nodeleftright != NULL)
180 nodeleftright->parent = node; 180 nodeleftright->parent = node;
181 181
182 nodeleft->balance += 1; 182 nodeleft->balance += 1;
183 node->balance = - nodeleft->balance; 183 node->balance = - nodeleft->balance;
184 184
185 node->branch_size = 185 node->branch_size =
186 (nodeleftright != NULL ? nodeleftright->branch_size : 0) 186 (nodeleftright != NULL ? nodeleftright->branch_size : 0)
187 + 1 + (noderight != NULL ? noderight->branch_size : 0); 187 + 1 + (noderight != NULL ? noderight->branch_size : 0);
188 nodeleft->branch_size = 188 nodeleft->branch_size =
189 nodeleftleft->branch_size + 1 + node->branch_size; 189 nodeleftleft->branch_size + 1 + node->branch_size;
190 190
191 *nodep = nodeleft; 191 *nodep = nodeleft;
192 height_diff = (height_diff < 0 192 height_diff = (height_diff < 0
193 ? /* noderight's height had been decremented from 193 ? /* noderight's height had been decremented from
194 h+1 to h. The subtree's height changes from 194 h+1 to h. The subtree's height changes from
195 h+3 to h+2|h+3. */ 195 h+3 to h+2|h+3. */
196 nodeleft->balance - 1 196 nodeleft->balance - 1
197 : /* nodeleft's height had been incremented from 197 : /* nodeleft's height had been incremented from
198 h+1 to h+2. The subtree's height changes from 198 h+1 to h+2. The subtree's height changes from
199 h+2 to h+2|h+3. */ 199 h+2 to h+2|h+3. */
200 nodeleft->balance); 200 nodeleft->balance);
201 } 201 }
202 else 202 else
203 { 203 {
204 /* 204 /*
205 * h+2 205 * h+2
206 / \ / \ 206 / \ / \
207 h+2 h --> h+1 h+1 207 h+2 h --> h+1 h+1
208 / \ / \ / \ 208 / \ / \ / \
209 h h+1 h L R h 209 h h+1 h L R h
210 / \ 210 / \
211 L R 211 L R
212 212
213 */ 213 */
214 gl_list_node_t L = nodeleft->right = nodeleftright->left; 214 gl_list_node_t L = nodeleft->right = nodeleftright->left;
215 gl_list_node_t R = node->left = nodeleftright->right; 215 gl_list_node_t R = node->left = nodeleftright->right;
216 nodeleftright->left = nodeleft; 216 nodeleftright->left = nodeleft;
217 nodeleftright->right = node; 217 nodeleftright->right = node;
218 218
219 nodeleftright->parent = node->parent; 219 nodeleftright->parent = node->parent;
220 if (L != NULL) 220 if (L != NULL)
221 L->parent = nodeleft; 221 L->parent = nodeleft;
222 if (R != NULL) 222 if (R != NULL)
223 R->parent = node; 223 R->parent = node;
224 nodeleft->parent = nodeleftright; 224 nodeleft->parent = nodeleftright;
225 node->parent = nodeleftright; 225 node->parent = nodeleftright;
226 226
227 nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0); 227 nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0);
228 node->balance = (nodeleftright->balance < 0 ? 1 : 0); 228 node->balance = (nodeleftright->balance < 0 ? 1 : 0);
229 nodeleftright->balance = 0; 229 nodeleftright->balance = 0;
230 230
231 nodeleft->branch_size = 231 nodeleft->branch_size =
232 (nodeleft->left != NULL ? nodeleft->left->branch_size : 0) 232 (nodeleft->left != NULL ? nodeleft->left->branch_size : 0)
233 + 1 + (nodeleft->right != NULL ? nodeleft->right->branch_size : 0); 233 + 1 + (nodeleft->right != NULL ? nodeleft->right->branch_size : 0);
234 node->branch_size = 234 node->branch_size =
235 (node->left != NULL ? node->left->branch_size : 0) 235 (node->left != NULL ? node->left->branch_size : 0)
236 + 1 + (node->right != NULL ? node->right->branch_size : 0); 236 + 1 + (node->right != NULL ? node->right->branch_size : 0);
237 nodeleftright->branch_size = 237 nodeleftright->branch_size =
238 nodeleft->branch_size + 1 + node->branch_size; 238 nodeleft->branch_size + 1 + node->branch_size;
239 239
240 *nodep = nodeleftright; 240 *nodep = nodeleftright;
241 height_diff = (height_diff < 0 241 height_diff = (height_diff < 0
242 ? /* noderight's height had been decremented from 242 ? /* noderight's height had been decremented from
243 h+1 to h. The subtree's height changes from 243 h+1 to h. The subtree's height changes from
244 h+3 to h+2. */ 244 h+3 to h+2. */
245 -1 245 -1
246 : /* nodeleft's height had been incremented from 246 : /* nodeleft's height had been incremented from
247 h+1 to h+2. The subtree's height changes from 247 h+1 to h+2. The subtree's height changes from
248 h+2 to h+2. */ 248 h+2 to h+2. */
249 0); 249 0);
250 } 250 }
251 } 251 }
252 else 252 else
253 { 253 {
254 /* node->balance = 2. The subtree is heavier on the right side. 254 /* node->balance = 2. The subtree is heavier on the right side.
255 Rotate from right to left: 255 Rotate from right to left:
256 256
257 * 257 *
258 / \ 258 / \
259 h h+2 259 h h+2
260 */ 260 */
261 gl_list_node_t noderightleft = noderight->left; 261 gl_list_node_t noderightleft = noderight->left;
262 gl_list_node_t noderightright = noderight->right; 262 gl_list_node_t noderightright = noderight->right;
263 if (noderight->balance >= 0) 263 if (noderight->balance >= 0)
264 { 264 {
265 /* 265 /*
266 * h+2|h+3 266 * h+2|h+3
267 / \ / \ 267 / \ / \
268 h h+2 --> h+1|h+2 \ 268 h h+2 --> h+1|h+2 \
269 / \ / \ | 269 / \ / \ |
270 h|h+1 h+1 h h|h+1 h+1 270 h|h+1 h+1 h h|h+1 h+1
271 */ 271 */
272 node->right = noderightleft; 272 node->right = noderightleft;
273 noderight->left = node; 273 noderight->left = node;
274 274
275 noderight->parent = node->parent; 275 noderight->parent = node->parent;
276 node->parent = noderight; 276 node->parent = noderight;
277 if (noderightleft != NULL) 277 if (noderightleft != NULL)
278 noderightleft->parent = node; 278 noderightleft->parent = node;
279 279
280 noderight->balance -= 1; 280 noderight->balance -= 1;
281 node->balance = - noderight->balance; 281 node->balance = - noderight->balance;
282 282
283 node->branch_size = 283 node->branch_size =
284 (nodeleft != NULL ? nodeleft->branch_size : 0) 284 (nodeleft != NULL ? nodeleft->branch_size : 0)
285 + 1 + (noderightleft != NULL ? noderightleft->branch_size : 0); 285 + 1 + (noderightleft != NULL ? noderightleft->branch_size : 0);
286 noderight->branch_size = 286 noderight->branch_size =
287 node->branch_size + 1 + noderightright->branch_size; 287 node->branch_size + 1 + noderightright->branch_size;
288 288
289 *nodep = noderight; 289 *nodep = noderight;
290 height_diff = (height_diff < 0 290 height_diff = (height_diff < 0
291 ? /* nodeleft's height had been decremented from 291 ? /* nodeleft's height had been decremented from
292 h+1 to h. The subtree's height changes from 292 h+1 to h. The subtree's height changes from
293 h+3 to h+2|h+3. */ 293 h+3 to h+2|h+3. */
294 - noderight->balance - 1 294 - noderight->balance - 1
295 : /* noderight's height had been incremented from 295 : /* noderight's height had been incremented from
296 h+1 to h+2. The subtree's height changes from 296 h+1 to h+2. The subtree's height changes from
297 h+2 to h+2|h+3. */ 297 h+2 to h+2|h+3. */
298 - noderight->balance); 298 - noderight->balance);
299 } 299 }
300 else 300 else
301 { 301 {
302 /* 302 /*
303 * h+2 303 * h+2
304 / \ / \ 304 / \ / \
305 h h+2 --> h+1 h+1 305 h h+2 --> h+1 h+1
306 / \ / \ / \ 306 / \ / \ / \
307 h+1 h h L R h 307 h+1 h h L R h
308 / \ 308 / \
309 L R 309 L R
310 310
311 */ 311 */
312 gl_list_node_t L = node->right = noderightleft->left; 312 gl_list_node_t L = node->right = noderightleft->left;
313 gl_list_node_t R = noderight->left = noderightleft->right; 313 gl_list_node_t R = noderight->left = noderightleft->right;
314 noderightleft->left = node; 314 noderightleft->left = node;
315 noderightleft->right = noderight; 315 noderightleft->right = noderight;
316 316
317 noderightleft->parent = node->parent; 317 noderightleft->parent = node->parent;
318 if (L != NULL) 318 if (L != NULL)
319 L->parent = node; 319 L->parent = node;
320 if (R != NULL) 320 if (R != NULL)
321 R->parent = noderight; 321 R->parent = noderight;
322 node->parent = noderightleft; 322 node->parent = noderightleft;
323 noderight->parent = noderightleft; 323 noderight->parent = noderightleft;
324 324
325 node->balance = (noderightleft->balance > 0 ? -1 : 0); 325 node->balance = (noderightleft->balance > 0 ? -1 : 0);
326 noderight->balance = (noderightleft->balance < 0 ? 1 : 0); 326 noderight->balance = (noderightleft->balance < 0 ? 1 : 0);
327 noderightleft->balance = 0; 327 noderightleft->balance = 0;
328 328
329 node->branch_size = 329 node->branch_size =
330 (node->left != NULL ? node->left->branch_size : 0) 330 (node->left != NULL ? node->left->branch_size : 0)
331 + 1 + (node->right != NULL ? node->right->branch_size : 0); 331 + 1 + (node->right != NULL ? node->right->branch_size : 0);
332 noderight->branch_size = 332 noderight->branch_size =
333 (noderight->left != NULL ? noderight->left->branch_size : 0) 333 (noderight->left != NULL ? noderight->left->branch_size : 0)
334 + 1 + (noderight->right != NULL ? noderight->right->branch_size : 0); 334 + 1 + (noderight->right != NULL ? noderight->right->branch_size : 0);
335 noderightleft->branch_size = 335 noderightleft->branch_size =
336 node->branch_size + 1 + noderight->branch_size; 336 node->branch_size + 1 + noderight->branch_size;
337 337
338 *nodep = noderightleft; 338 *nodep = noderightleft;
339 height_diff = (height_diff < 0 339 height_diff = (height_diff < 0
340 ? /* nodeleft's height had been decremented from 340 ? /* nodeleft's height had been decremented from
341 h+1 to h. The subtree's height changes from 341 h+1 to h. The subtree's height changes from
342 h+3 to h+2. */ 342 h+3 to h+2. */
343 -1 343 -1
344 : /* noderight's height had been incremented from 344 : /* noderight's height had been incremented from
345 h+1 to h+2. The subtree's height changes from 345 h+1 to h+2. The subtree's height changes from
346 h+2 to h+2. */ 346 h+2 to h+2. */
347 0); 347 0);
348 } 348 }
349 } 349 }
350 node = *nodep; 350 node = *nodep;
351 } 351 }
352 else 352 else
353 { 353 {
354 /* No rotation needed. Only propagation of the height change to the 354 /* No rotation needed. Only propagation of the height change to the
355 next higher level. */ 355 next higher level. */
356 if (height_diff < 0) 356 if (height_diff < 0)
357 height_diff = (previous_balance == 0 ? 0 : -1); 357 height_diff = (previous_balance == 0 ? 0 : -1);
358 else 358 else
359 height_diff = (node->balance == 0 ? 0 : 1); 359 height_diff = (node->balance == 0 ? 0 : 1);
360 } 360 }
361 361
362 if (height_diff == 0) 362 if (height_diff == 0)
363 break; 363 break;
364 364
365 parent = node->parent; 365 parent = node->parent;
366 if (parent == NULL) 366 if (parent == NULL)
367 break; 367 break;
368 } 368 }
369 } 369 }
370 370
371 static gl_list_node_t 371 static gl_list_node_t
372 gl_tree_add_first (gl_list_t list, const void *elt) 372 gl_tree_add_first (gl_list_t list, const void *elt)
395 else 395 else
396 { 396 {
397 gl_list_node_t node; 397 gl_list_node_t node;
398 398
399 for (node = list->root; node->left != NULL; ) 399 for (node = list->root; node->left != NULL; )
400 node = node->left; 400 node = node->left;
401 401
402 node->left = new_node; 402 node->left = new_node;
403 new_node->parent = node; 403 new_node->parent = node;
404 node->balance--; 404 node->balance--;
405 405
406 /* Update branch_size fields of the parent nodes. */ 406 /* Update branch_size fields of the parent nodes. */
407 { 407 {
408 gl_list_node_t p; 408 gl_list_node_t p;
409 409
410 for (p = node; p != NULL; p = p->parent) 410 for (p = node; p != NULL; p = p->parent)
411 p->branch_size++; 411 p->branch_size++;
412 } 412 }
413 413
414 /* Rebalance. */ 414 /* Rebalance. */
415 if (node->right == NULL && node->parent != NULL) 415 if (node->right == NULL && node->parent != NULL)
416 rebalance (list, node, 1, node->parent); 416 rebalance (list, node, 1, node->parent);
417 } 417 }
418 418
419 #if WITH_HASHTABLE 419 #if WITH_HASHTABLE
420 /* Add node to the hash table. 420 /* Add node to the hash table.
421 Note that this is only possible _after_ the node has been added to the 421 Note that this is only possible _after_ the node has been added to the
454 else 454 else
455 { 455 {
456 gl_list_node_t node; 456 gl_list_node_t node;
457 457
458 for (node = list->root; node->right != NULL; ) 458 for (node = list->root; node->right != NULL; )
459 node = node->right; 459 node = node->right;
460 460
461 node->right = new_node; 461 node->right = new_node;
462 new_node->parent = node; 462 new_node->parent = node;
463 node->balance++; 463 node->balance++;
464 464
465 /* Update branch_size fields of the parent nodes. */ 465 /* Update branch_size fields of the parent nodes. */
466 { 466 {
467 gl_list_node_t p; 467 gl_list_node_t p;
468 468
469 for (p = node; p != NULL; p = p->parent) 469 for (p = node; p != NULL; p = p->parent)
470 p->branch_size++; 470 p->branch_size++;
471 } 471 }
472 472
473 /* Rebalance. */ 473 /* Rebalance. */
474 if (node->left == NULL && node->parent != NULL) 474 if (node->left == NULL && node->parent != NULL)
475 rebalance (list, node, 1, node->parent); 475 rebalance (list, node, 1, node->parent);
476 } 476 }
477 477
478 #if WITH_HASHTABLE 478 #if WITH_HASHTABLE
479 /* Add node to the hash table. 479 /* Add node to the hash table.
480 Note that this is only possible _after_ the node has been added to the 480 Note that this is only possible _after_ the node has been added to the
513 height_inc = (node->right == NULL); 513 height_inc = (node->right == NULL);
514 } 514 }
515 else 515 else
516 { 516 {
517 for (node = node->left; node->right != NULL; ) 517 for (node = node->left; node->right != NULL; )
518 node = node->right; 518 node = node->right;
519 node->right = new_node; 519 node->right = new_node;
520 node->balance++; 520 node->balance++;
521 height_inc = (node->left == NULL); 521 height_inc = (node->left == NULL);
522 } 522 }
523 new_node->parent = node; 523 new_node->parent = node;
572 height_inc = (node->left == NULL); 572 height_inc = (node->left == NULL);
573 } 573 }
574 else 574 else
575 { 575 {
576 for (node = node->right; node->left != NULL; ) 576 for (node = node->right; node->left != NULL; )
577 node = node->left; 577 node = node->left;
578 node->left = new_node; 578 node->left = new_node;
579 node->balance--; 579 node->balance--;
580 height_inc = (node->right == NULL); 580 height_inc = (node->right == NULL);
581 } 581 }
582 new_node->parent = node; 582 new_node->parent = node;
622 { 622 {
623 /* Replace node with node->right. */ 623 /* Replace node with node->right. */
624 gl_list_node_t child = node->right; 624 gl_list_node_t child = node->right;
625 625
626 if (child != NULL) 626 if (child != NULL)
627 child->parent = parent; 627 child->parent = parent;
628 if (parent == NULL) 628 if (parent == NULL)
629 list->root = child; 629 list->root = child;
630 else 630 else
631 { 631 {
632 if (parent->left == node) 632 if (parent->left == node)
633 parent->left = child; 633 parent->left = child;
634 else /* parent->right == node */ 634 else /* parent->right == node */
635 parent->right = child; 635 parent->right = child;
636 636
637 /* Update branch_size fields of the parent nodes. */ 637 /* Update branch_size fields of the parent nodes. */
638 { 638 {
639 gl_list_node_t p; 639 gl_list_node_t p;
640 640
641 for (p = parent; p != NULL; p = p->parent) 641 for (p = parent; p != NULL; p = p->parent)
642 p->branch_size--; 642 p->branch_size--;
643 } 643 }
644 644
645 rebalance (list, child, -1, parent); 645 rebalance (list, child, -1, parent);
646 } 646 }
647 } 647 }
648 else if (node->right == NULL) 648 else if (node->right == NULL)
649 { 649 {
650 /* It is not absolutely necessary to treat this case. But the more 650 /* It is not absolutely necessary to treat this case. But the more
651 general case below is more complicated, hence slower. */ 651 general case below is more complicated, hence slower. */
652 /* Replace node with node->left. */ 652 /* Replace node with node->left. */
653 gl_list_node_t child = node->left; 653 gl_list_node_t child = node->left;
654 654
655 child->parent = parent; 655 child->parent = parent;
656 if (parent == NULL) 656 if (parent == NULL)
657 list->root = child; 657 list->root = child;
658 else 658 else
659 { 659 {
660 if (parent->left == node) 660 if (parent->left == node)
661 parent->left = child; 661 parent->left = child;
662 else /* parent->right == node */ 662 else /* parent->right == node */
663 parent->right = child; 663 parent->right = child;
664 664
665 /* Update branch_size fields of the parent nodes. */ 665 /* Update branch_size fields of the parent nodes. */
666 { 666 {
667 gl_list_node_t p; 667 gl_list_node_t p;
668 668
669 for (p = parent; p != NULL; p = p->parent) 669 for (p = parent; p != NULL; p = p->parent)
670 p->branch_size--; 670 p->branch_size--;
671 } 671 }
672 672
673 rebalance (list, child, -1, parent); 673 rebalance (list, child, -1, parent);
674 } 674 }
675 } 675 }
676 else 676 else
677 { 677 {
678 /* Replace node with the rightmost element of the node->left subtree. */ 678 /* Replace node with the rightmost element of the node->left subtree. */
679 gl_list_node_t subst; 679 gl_list_node_t subst;
680 gl_list_node_t subst_parent; 680 gl_list_node_t subst_parent;
681 gl_list_node_t child; 681 gl_list_node_t child;
682 682
683 for (subst = node->left; subst->right != NULL; ) 683 for (subst = node->left; subst->right != NULL; )
684 subst = subst->right; 684 subst = subst->right;
685 685
686 subst_parent = subst->parent; 686 subst_parent = subst->parent;
687 687
688 child = subst->left; 688 child = subst->left;
689 689
690 /* The case subst_parent == node is special: If we do nothing special, 690 /* The case subst_parent == node is special: If we do nothing special,
691 we get confusion about node->left, subst->left and child->parent. 691 we get confusion about node->left, subst->left and child->parent.
692 subst_parent == node 692 subst_parent == node
693 <==> The 'for' loop above terminated immediately. 693 <==> The 'for' loop above terminated immediately.
694 <==> subst == subst_parent->left 694 <==> subst == subst_parent->left
695 [otherwise subst == subst_parent->right] 695 [otherwise subst == subst_parent->right]
696 In this case, we would need to first set 696 In this case, we would need to first set
697 child->parent = node; node->left = child; 697 child->parent = node; node->left = child;
698 and later - when we copy subst into node's position - again 698 and later - when we copy subst into node's position - again
699 child->parent = subst; subst->left = child; 699 child->parent = subst; subst->left = child;
700 Altogether a no-op. */ 700 Altogether a no-op. */
701 if (subst_parent != node) 701 if (subst_parent != node)
702 { 702 {
703 if (child != NULL) 703 if (child != NULL)
704 child->parent = subst_parent; 704 child->parent = subst_parent;
705 subst_parent->right = child; 705 subst_parent->right = child;
706 } 706 }
707 707
708 /* Update branch_size fields of the parent nodes. */ 708 /* Update branch_size fields of the parent nodes. */
709 { 709 {
710 gl_list_node_t p; 710 gl_list_node_t p;
711 711
712 for (p = subst_parent; p != NULL; p = p->parent) 712 for (p = subst_parent; p != NULL; p = p->parent)
713 p->branch_size--; 713 p->branch_size--;
714 } 714 }
715 715
716 /* Copy subst into node's position. 716 /* Copy subst into node's position.
717 (This is safer than to copy subst's value into node, keep node in 717 (This is safer than to copy subst's value into node, keep node in
718 place, and free subst.) */ 718 place, and free subst.) */
719 if (subst_parent != node) 719 if (subst_parent != node)
720 { 720 {
721 subst->left = node->left; 721 subst->left = node->left;
722 subst->left->parent = subst; 722 subst->left->parent = subst;
723 } 723 }
724 subst->right = node->right; 724 subst->right = node->right;
725 subst->right->parent = subst; 725 subst->right->parent = subst;
726 subst->balance = node->balance; 726 subst->balance = node->balance;
727 subst->branch_size = node->branch_size; 727 subst->branch_size = node->branch_size;
728 subst->parent = parent; 728 subst->parent = parent;
729 if (parent == NULL) 729 if (parent == NULL)
730 list->root = subst; 730 list->root = subst;
731 else if (parent->left == node) 731 else if (parent->left == node)
732 parent->left = subst; 732 parent->left = subst;
733 else /* parent->right == node */ 733 else /* parent->right == node */
734 parent->right = subst; 734 parent->right = subst;
735 735
736 /* Rebalancing starts at child's parent, that is subst_parent - 736 /* Rebalancing starts at child's parent, that is subst_parent -
737 except when subst_parent == node. In this case, we need to use 737 except when subst_parent == node. In this case, we need to use
738 its replacement, subst. */ 738 its replacement, subst. */
739 rebalance (list, child, -1, subst_parent != node ? subst_parent : subst); 739 rebalance (list, child, -1, subst_parent != node ? subst_parent : subst);
740 } 740 }
741 741
742 if (list->base.dispose_fn != NULL) 742 if (list->base.dispose_fn != NULL)
743 list->base.dispose_fn (node->value); 743 list->base.dispose_fn (node->value);