Mercurial > gnulib
annotate lib/gl_avltree_ordered.h @ 40186:8964917f9574
autoupdate
| author | Karl Berry <karl@freefriends.org> |
|---|---|
| date | Mon, 18 Feb 2019 08:02:49 -0800 |
| parents | b06060465f09 |
| children |
| rev | line source |
|---|---|
| 40006 | 1 /* Ordered {set,map} data type implemented by a binary tree. |
|
40057
b06060465f09
maint: Run 'make update-copyright'
Paul Eggert <eggert@cs.ucla.edu>
parents:
40006
diff
changeset
|
2 Copyright (C) 2006-2007, 2009-2019 Free Software Foundation, Inc. |
| 40006 | 3 Written by Bruno Haible <bruno@clisp.org>, 2006. |
| 4 | |
| 5 This program is free software: you can redistribute it and/or modify | |
| 6 it under the terms of the GNU General Public License as published by | |
| 7 the Free Software Foundation; either version 3 of the License, or | |
| 8 (at your option) any later version. | |
| 9 | |
| 10 This program is distributed in the hope that it will be useful, | |
| 11 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 13 GNU General Public License for more details. | |
| 14 | |
| 15 You should have received a copy of the GNU General Public License | |
| 16 along with this program. If not, see <https://www.gnu.org/licenses/>. */ | |
| 17 | |
| 18 /* An AVL tree is a binary tree where | |
| 19 1. The height of each node is calculated as | |
| 20 heightof(node) = 1 + max (heightof(node.left), heightof(node.right)). | |
| 21 2. The heights of the subtrees of each node differ by at most 1: | |
| 22 | heightof(right) - heightof(left) | <= 1. | |
| 23 3. The index of the elements in the node.left subtree are smaller than | |
| 24 the index of node. | |
| 25 The index of the elements in the node.right subtree are larger than | |
| 26 the index of node. | |
| 27 */ | |
| 28 | |
| 29 /* Tree node implementation, valid for this file only. */ | |
| 30 struct NODE_IMPL | |
| 31 { | |
| 32 struct NODE_IMPL *left; /* left branch, or NULL */ | |
| 33 struct NODE_IMPL *right; /* right branch, or NULL */ | |
| 34 /* Parent pointer, or NULL. The parent pointer is not needed for most | |
| 35 operations. It is needed so that a NODE_T can be returned without | |
| 36 memory allocation, on which the functions <container>_remove_node, | |
| 37 <container>_add_before, <container>_add_after can be implemented. */ | |
| 38 struct NODE_IMPL *parent; | |
| 39 int balance; /* heightof(right) - heightof(left), | |
| 40 always = -1 or 0 or 1 */ | |
| 41 NODE_PAYLOAD_FIELDS | |
| 42 }; | |
| 43 typedef struct NODE_IMPL * NODE_T; | |
| 44 | |
| 45 /* Concrete CONTAINER_IMPL type, valid for this file only. */ | |
| 46 struct CONTAINER_IMPL | |
| 47 { | |
| 48 struct CONTAINER_IMPL_BASE base; | |
| 49 struct NODE_IMPL *root; /* root node or NULL */ | |
| 50 size_t count; /* number of nodes */ | |
| 51 }; | |
| 52 | |
| 53 /* An AVL tree of height h has at least F_(h+2) - 1 [Fibonacci number] and at | |
| 54 most 2^h - 1 elements. So, h <= 84 (because a tree of height h >= 85 would | |
| 55 have at least F_87 - 1 elements, and because even on 64-bit machines, | |
| 56 sizeof (NODE_IMPL) * (F_87 - 1) > 2^64 | |
| 57 this would exceed the address space of the machine. */ | |
| 58 #define MAXHEIGHT 83 | |
| 59 | |
| 60 /* Ensure the tree is balanced, after an insertion or deletion operation. | |
| 61 The height of NODE is incremented by HEIGHT_DIFF (1 or -1). | |
| 62 PARENT = NODE->parent. (NODE can also be NULL. But PARENT is non-NULL.) | |
| 63 Rotation operations are performed starting at PARENT (not NODE itself!). */ | |
| 64 static void | |
| 65 rebalance (CONTAINER_T container, | |
| 66 NODE_T node, int height_diff, NODE_T parent) | |
| 67 { | |
| 68 for (;;) | |
| 69 { | |
| 70 NODE_T child; | |
| 71 int previous_balance; | |
| 72 int balance_diff; | |
| 73 NODE_T nodeleft; | |
| 74 NODE_T noderight; | |
| 75 | |
| 76 child = node; | |
| 77 node = parent; | |
| 78 | |
| 79 previous_balance = node->balance; | |
| 80 | |
| 81 /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right | |
| 82 branch's height has increased by 1 or the left branch's height has | |
| 83 decreased by 1, -1 if the right branch's height has decreased by 1 or | |
| 84 the left branch's height has increased by 1, 0 if no height change. */ | |
| 85 if (node->left != NULL || node->right != NULL) | |
| 86 balance_diff = (child == node->right ? height_diff : -height_diff); | |
| 87 else | |
| 88 /* Special case where above formula doesn't work, because the caller | |
| 89 didn't tell whether node's left or right branch shrunk from height 1 | |
| 90 to NULL. */ | |
| 91 balance_diff = - previous_balance; | |
| 92 | |
| 93 node->balance += balance_diff; | |
| 94 if (balance_diff == previous_balance) | |
| 95 { | |
| 96 /* node->balance is outside the range [-1,1]. Must rotate. */ | |
| 97 NODE_T *nodep; | |
| 98 | |
| 99 if (node->parent == NULL) | |
| 100 /* node == container->root */ | |
| 101 nodep = &container->root; | |
| 102 else if (node->parent->left == node) | |
| 103 nodep = &node->parent->left; | |
| 104 else if (node->parent->right == node) | |
| 105 nodep = &node->parent->right; | |
| 106 else | |
| 107 abort (); | |
| 108 | |
| 109 nodeleft = node->left; | |
| 110 noderight = node->right; | |
| 111 | |
| 112 if (balance_diff < 0) | |
| 113 { | |
| 114 /* node->balance = -2. The subtree is heavier on the left side. | |
| 115 Rotate from left to right: | |
| 116 | |
| 117 * | |
| 118 / \ | |
| 119 h+2 h | |
| 120 */ | |
| 121 NODE_T nodeleftright = nodeleft->right; | |
| 122 if (nodeleft->balance <= 0) | |
| 123 { | |
| 124 /* | |
| 125 * h+2|h+3 | |
| 126 / \ / \ | |
| 127 h+2 h --> / h+1|h+2 | |
| 128 / \ | / \ | |
| 129 h+1 h|h+1 h+1 h|h+1 h | |
| 130 */ | |
| 131 node->left = nodeleftright; | |
| 132 nodeleft->right = node; | |
| 133 | |
| 134 nodeleft->parent = node->parent; | |
| 135 node->parent = nodeleft; | |
| 136 if (nodeleftright != NULL) | |
| 137 nodeleftright->parent = node; | |
| 138 | |
| 139 nodeleft->balance += 1; | |
| 140 node->balance = - nodeleft->balance; | |
| 141 | |
| 142 *nodep = nodeleft; | |
| 143 height_diff = (height_diff < 0 | |
| 144 ? /* noderight's height had been decremented from | |
| 145 h+1 to h. The subtree's height changes from | |
| 146 h+3 to h+2|h+3. */ | |
| 147 nodeleft->balance - 1 | |
| 148 : /* nodeleft's height had been incremented from | |
| 149 h+1 to h+2. The subtree's height changes from | |
| 150 h+2 to h+2|h+3. */ | |
| 151 nodeleft->balance); | |
| 152 } | |
| 153 else | |
| 154 { | |
| 155 /* | |
| 156 * h+2 | |
| 157 / \ / \ | |
| 158 h+2 h --> h+1 h+1 | |
| 159 / \ / \ / \ | |
| 160 h h+1 h L R h | |
| 161 / \ | |
| 162 L R | |
| 163 | |
| 164 */ | |
| 165 NODE_T L = nodeleft->right = nodeleftright->left; | |
| 166 NODE_T R = node->left = nodeleftright->right; | |
| 167 nodeleftright->left = nodeleft; | |
| 168 nodeleftright->right = node; | |
| 169 | |
| 170 nodeleftright->parent = node->parent; | |
| 171 if (L != NULL) | |
| 172 L->parent = nodeleft; | |
| 173 if (R != NULL) | |
| 174 R->parent = node; | |
| 175 nodeleft->parent = nodeleftright; | |
| 176 node->parent = nodeleftright; | |
| 177 | |
| 178 nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0); | |
| 179 node->balance = (nodeleftright->balance < 0 ? 1 : 0); | |
| 180 nodeleftright->balance = 0; | |
| 181 | |
| 182 *nodep = nodeleftright; | |
| 183 height_diff = (height_diff < 0 | |
| 184 ? /* noderight's height had been decremented from | |
| 185 h+1 to h. The subtree's height changes from | |
| 186 h+3 to h+2. */ | |
| 187 -1 | |
| 188 : /* nodeleft's height had been incremented from | |
| 189 h+1 to h+2. The subtree's height changes from | |
| 190 h+2 to h+2. */ | |
| 191 0); | |
| 192 } | |
| 193 } | |
| 194 else | |
| 195 { | |
| 196 /* node->balance = 2. The subtree is heavier on the right side. | |
| 197 Rotate from right to left: | |
| 198 | |
| 199 * | |
| 200 / \ | |
| 201 h h+2 | |
| 202 */ | |
| 203 NODE_T noderightleft = noderight->left; | |
| 204 if (noderight->balance >= 0) | |
| 205 { | |
| 206 /* | |
| 207 * h+2|h+3 | |
| 208 / \ / \ | |
| 209 h h+2 --> h+1|h+2 \ | |
| 210 / \ / \ | | |
| 211 h|h+1 h+1 h h|h+1 h+1 | |
| 212 */ | |
| 213 node->right = noderightleft; | |
| 214 noderight->left = node; | |
| 215 | |
| 216 noderight->parent = node->parent; | |
| 217 node->parent = noderight; | |
| 218 if (noderightleft != NULL) | |
| 219 noderightleft->parent = node; | |
| 220 | |
| 221 noderight->balance -= 1; | |
| 222 node->balance = - noderight->balance; | |
| 223 | |
| 224 *nodep = noderight; | |
| 225 height_diff = (height_diff < 0 | |
| 226 ? /* nodeleft's height had been decremented from | |
| 227 h+1 to h. The subtree's height changes from | |
| 228 h+3 to h+2|h+3. */ | |
| 229 - noderight->balance - 1 | |
| 230 : /* noderight's height had been incremented from | |
| 231 h+1 to h+2. The subtree's height changes from | |
| 232 h+2 to h+2|h+3. */ | |
| 233 - noderight->balance); | |
| 234 } | |
| 235 else | |
| 236 { | |
| 237 /* | |
| 238 * h+2 | |
| 239 / \ / \ | |
| 240 h h+2 --> h+1 h+1 | |
| 241 / \ / \ / \ | |
| 242 h+1 h h L R h | |
| 243 / \ | |
| 244 L R | |
| 245 | |
| 246 */ | |
| 247 NODE_T L = node->right = noderightleft->left; | |
| 248 NODE_T R = noderight->left = noderightleft->right; | |
| 249 noderightleft->left = node; | |
| 250 noderightleft->right = noderight; | |
| 251 | |
| 252 noderightleft->parent = node->parent; | |
| 253 if (L != NULL) | |
| 254 L->parent = node; | |
| 255 if (R != NULL) | |
| 256 R->parent = noderight; | |
| 257 node->parent = noderightleft; | |
| 258 noderight->parent = noderightleft; | |
| 259 | |
| 260 node->balance = (noderightleft->balance > 0 ? -1 : 0); | |
| 261 noderight->balance = (noderightleft->balance < 0 ? 1 : 0); | |
| 262 noderightleft->balance = 0; | |
| 263 | |
| 264 *nodep = noderightleft; | |
| 265 height_diff = (height_diff < 0 | |
| 266 ? /* nodeleft's height had been decremented from | |
| 267 h+1 to h. The subtree's height changes from | |
| 268 h+3 to h+2. */ | |
| 269 -1 | |
| 270 : /* noderight's height had been incremented from | |
| 271 h+1 to h+2. The subtree's height changes from | |
| 272 h+2 to h+2. */ | |
| 273 0); | |
| 274 } | |
| 275 } | |
| 276 node = *nodep; | |
| 277 } | |
| 278 else | |
| 279 { | |
| 280 /* No rotation needed. Only propagation of the height change to the | |
| 281 next higher level. */ | |
| 282 if (height_diff < 0) | |
| 283 height_diff = (previous_balance == 0 ? 0 : -1); | |
| 284 else | |
| 285 height_diff = (node->balance == 0 ? 0 : 1); | |
| 286 } | |
| 287 | |
| 288 if (height_diff == 0) | |
| 289 break; | |
| 290 | |
| 291 parent = node->parent; | |
| 292 if (parent == NULL) | |
| 293 break; | |
| 294 } | |
| 295 } | |
| 296 | |
| 297 static NODE_T | |
| 298 gl_tree_nx_add_first (CONTAINER_T container, NODE_PAYLOAD_PARAMS) | |
| 299 { | |
| 300 /* Create new node. */ | |
| 301 NODE_T new_node = | |
| 302 (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL)); | |
| 303 | |
| 304 if (new_node == NULL) | |
| 305 return NULL; | |
| 306 | |
| 307 new_node->left = NULL; | |
| 308 new_node->right = NULL; | |
| 309 new_node->balance = 0; | |
| 310 NODE_PAYLOAD_ASSIGN(new_node) | |
| 311 | |
| 312 /* Add it to the tree. */ | |
| 313 if (container->root == NULL) | |
| 314 { | |
| 315 container->root = new_node; | |
| 316 new_node->parent = NULL; | |
| 317 } | |
| 318 else | |
| 319 { | |
| 320 NODE_T node; | |
| 321 | |
| 322 for (node = container->root; node->left != NULL; ) | |
| 323 node = node->left; | |
| 324 | |
| 325 node->left = new_node; | |
| 326 new_node->parent = node; | |
| 327 node->balance--; | |
| 328 | |
| 329 /* Rebalance. */ | |
| 330 if (node->right == NULL && node->parent != NULL) | |
| 331 rebalance (container, node, 1, node->parent); | |
| 332 } | |
| 333 | |
| 334 container->count++; | |
| 335 return new_node; | |
| 336 } | |
| 337 | |
| 338 static NODE_T | |
| 339 gl_tree_nx_add_before (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) | |
| 340 { | |
| 341 /* Create new node. */ | |
| 342 NODE_T new_node = | |
| 343 (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL)); | |
| 344 bool height_inc; | |
| 345 | |
| 346 if (new_node == NULL) | |
| 347 return NULL; | |
| 348 | |
| 349 new_node->left = NULL; | |
| 350 new_node->right = NULL; | |
| 351 new_node->balance = 0; | |
| 352 NODE_PAYLOAD_ASSIGN(new_node) | |
| 353 | |
| 354 /* Add it to the tree. */ | |
| 355 if (node->left == NULL) | |
| 356 { | |
| 357 node->left = new_node; | |
| 358 node->balance--; | |
| 359 height_inc = (node->right == NULL); | |
| 360 } | |
| 361 else | |
| 362 { | |
| 363 for (node = node->left; node->right != NULL; ) | |
| 364 node = node->right; | |
| 365 node->right = new_node; | |
| 366 node->balance++; | |
| 367 height_inc = (node->left == NULL); | |
| 368 } | |
| 369 new_node->parent = node; | |
| 370 | |
| 371 /* Rebalance. */ | |
| 372 if (height_inc && node->parent != NULL) | |
| 373 rebalance (container, node, 1, node->parent); | |
| 374 | |
| 375 container->count++; | |
| 376 return new_node; | |
| 377 } | |
| 378 | |
| 379 static NODE_T | |
| 380 gl_tree_nx_add_after (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) | |
| 381 { | |
| 382 /* Create new node. */ | |
| 383 NODE_T new_node = | |
| 384 (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL)); | |
| 385 bool height_inc; | |
| 386 | |
| 387 if (new_node == NULL) | |
| 388 return NULL; | |
| 389 | |
| 390 new_node->left = NULL; | |
| 391 new_node->right = NULL; | |
| 392 new_node->balance = 0; | |
| 393 NODE_PAYLOAD_ASSIGN(new_node) | |
| 394 | |
| 395 /* Add it to the tree. */ | |
| 396 if (node->right == NULL) | |
| 397 { | |
| 398 node->right = new_node; | |
| 399 node->balance++; | |
| 400 height_inc = (node->left == NULL); | |
| 401 } | |
| 402 else | |
| 403 { | |
| 404 for (node = node->right; node->left != NULL; ) | |
| 405 node = node->left; | |
| 406 node->left = new_node; | |
| 407 node->balance--; | |
| 408 height_inc = (node->right == NULL); | |
| 409 } | |
| 410 new_node->parent = node; | |
| 411 | |
| 412 /* Rebalance. */ | |
| 413 if (height_inc && node->parent != NULL) | |
| 414 rebalance (container, node, 1, node->parent); | |
| 415 | |
| 416 container->count++; | |
| 417 return new_node; | |
| 418 } | |
| 419 | |
| 420 static bool | |
| 421 gl_tree_remove_node (CONTAINER_T container, NODE_T node) | |
| 422 { | |
| 423 NODE_T parent = node->parent; | |
| 424 | |
| 425 if (node->left == NULL) | |
| 426 { | |
| 427 /* Replace node with node->right. */ | |
| 428 NODE_T child = node->right; | |
| 429 | |
| 430 if (child != NULL) | |
| 431 child->parent = parent; | |
| 432 if (parent == NULL) | |
| 433 container->root = child; | |
| 434 else | |
| 435 { | |
| 436 if (parent->left == node) | |
| 437 parent->left = child; | |
| 438 else /* parent->right == node */ | |
| 439 parent->right = child; | |
| 440 | |
| 441 rebalance (container, child, -1, parent); | |
| 442 } | |
| 443 } | |
| 444 else if (node->right == NULL) | |
| 445 { | |
| 446 /* It is not absolutely necessary to treat this case. But the more | |
| 447 general case below is more complicated, hence slower. */ | |
| 448 /* Replace node with node->left. */ | |
| 449 NODE_T child = node->left; | |
| 450 | |
| 451 child->parent = parent; | |
| 452 if (parent == NULL) | |
| 453 container->root = child; | |
| 454 else | |
| 455 { | |
| 456 if (parent->left == node) | |
| 457 parent->left = child; | |
| 458 else /* parent->right == node */ | |
| 459 parent->right = child; | |
| 460 | |
| 461 rebalance (container, child, -1, parent); | |
| 462 } | |
| 463 } | |
| 464 else | |
| 465 { | |
| 466 /* Replace node with the rightmost element of the node->left subtree. */ | |
| 467 NODE_T subst; | |
| 468 NODE_T subst_parent; | |
| 469 NODE_T child; | |
| 470 | |
| 471 for (subst = node->left; subst->right != NULL; ) | |
| 472 subst = subst->right; | |
| 473 | |
| 474 subst_parent = subst->parent; | |
| 475 | |
| 476 child = subst->left; | |
| 477 | |
| 478 /* The case subst_parent == node is special: If we do nothing special, | |
| 479 we get confusion about node->left, subst->left and child->parent. | |
| 480 subst_parent == node | |
| 481 <==> The 'for' loop above terminated immediately. | |
| 482 <==> subst == subst_parent->left | |
| 483 [otherwise subst == subst_parent->right] | |
| 484 In this case, we would need to first set | |
| 485 child->parent = node; node->left = child; | |
| 486 and later - when we copy subst into node's position - again | |
| 487 child->parent = subst; subst->left = child; | |
| 488 Altogether a no-op. */ | |
| 489 if (subst_parent != node) | |
| 490 { | |
| 491 if (child != NULL) | |
| 492 child->parent = subst_parent; | |
| 493 subst_parent->right = child; | |
| 494 } | |
| 495 | |
| 496 /* Copy subst into node's position. | |
| 497 (This is safer than to copy subst's value into node, keep node in | |
| 498 place, and free subst.) */ | |
| 499 if (subst_parent != node) | |
| 500 { | |
| 501 subst->left = node->left; | |
| 502 subst->left->parent = subst; | |
| 503 } | |
| 504 subst->right = node->right; | |
| 505 subst->right->parent = subst; | |
| 506 subst->balance = node->balance; | |
| 507 subst->parent = parent; | |
| 508 if (parent == NULL) | |
| 509 container->root = subst; | |
| 510 else if (parent->left == node) | |
| 511 parent->left = subst; | |
| 512 else /* parent->right == node */ | |
| 513 parent->right = subst; | |
| 514 | |
| 515 /* Rebalancing starts at child's parent, that is subst_parent - | |
| 516 except when subst_parent == node. In this case, we need to use | |
| 517 its replacement, subst. */ | |
| 518 rebalance (container, child, -1, subst_parent != node ? subst_parent : subst); | |
| 519 } | |
| 520 | |
| 521 container->count--; | |
| 522 NODE_PAYLOAD_DISPOSE | |
| 523 free (node); | |
| 524 return true; | |
| 525 } | |
| 526 | |
| 527 /* For debugging. */ | |
| 528 static unsigned int | |
| 529 check_invariants (NODE_T node, NODE_T parent, size_t *counterp) | |
| 530 { | |
| 531 unsigned int left_height = | |
| 532 (node->left != NULL ? check_invariants (node->left, node, counterp) : 0); | |
| 533 unsigned int right_height = | |
| 534 (node->right != NULL ? check_invariants (node->right, node, counterp) : 0); | |
| 535 int balance = (int)right_height - (int)left_height; | |
| 536 | |
| 537 if (!(node->parent == parent)) | |
| 538 abort (); | |
| 539 if (!(balance >= -1 && balance <= 1)) | |
| 540 abort (); | |
| 541 if (!(node->balance == balance)) | |
| 542 abort (); | |
| 543 | |
| 544 (*counterp)++; | |
| 545 | |
| 546 return 1 + (left_height > right_height ? left_height : right_height); | |
| 547 } |