00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00044 #include <ldns/config.h>
00045 #include <ldns/rbtree.h>
00046 #include <stdlib.h>
00047
00049 #define BLACK 0
00050
00051 #define RED 1
00052
00054 ldns_rbnode_t ldns_rbtree_null_node = {
00055 LDNS_RBTREE_NULL,
00056 LDNS_RBTREE_NULL,
00057 LDNS_RBTREE_NULL,
00058 NULL,
00059 NULL,
00060 BLACK
00061 };
00062
00064 static void ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
00066 static void ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
00068 static void ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
00070 static void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* child_parent);
00071
00072
00073
00074
00075
00076
00077
00078 ldns_rbtree_t *
00079 ldns_rbtree_create (int (*cmpf)(const void *, const void *))
00080 {
00081 ldns_rbtree_t *rbtree;
00082
00083
00084 rbtree = (ldns_rbtree_t *) malloc(sizeof(ldns_rbtree_t));
00085 if (!rbtree) {
00086 return NULL;
00087 }
00088
00089
00090 ldns_rbtree_init(rbtree, cmpf);
00091
00092 return rbtree;
00093 }
00094
00095 void
00096 ldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *))
00097 {
00098
00099 rbtree->root = LDNS_RBTREE_NULL;
00100 rbtree->count = 0;
00101 rbtree->cmp = cmpf;
00102 }
00103
00104 void
00105 ldns_rbtree_free(ldns_rbtree_t *rbtree)
00106 {
00107 free(rbtree);
00108 }
00109
00110
00111
00112
00113
00114 static void
00115 ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
00116 {
00117 ldns_rbnode_t *right = node->right;
00118 node->right = right->left;
00119 if (right->left != LDNS_RBTREE_NULL)
00120 right->left->parent = node;
00121
00122 right->parent = node->parent;
00123
00124 if (node->parent != LDNS_RBTREE_NULL) {
00125 if (node == node->parent->left) {
00126 node->parent->left = right;
00127 } else {
00128 node->parent->right = right;
00129 }
00130 } else {
00131 rbtree->root = right;
00132 }
00133 right->left = node;
00134 node->parent = right;
00135 }
00136
00137
00138
00139
00140
00141 static void
00142 ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
00143 {
00144 ldns_rbnode_t *left = node->left;
00145 node->left = left->right;
00146 if (left->right != LDNS_RBTREE_NULL)
00147 left->right->parent = node;
00148
00149 left->parent = node->parent;
00150
00151 if (node->parent != LDNS_RBTREE_NULL) {
00152 if (node == node->parent->right) {
00153 node->parent->right = left;
00154 } else {
00155 node->parent->left = left;
00156 }
00157 } else {
00158 rbtree->root = left;
00159 }
00160 left->right = node;
00161 node->parent = left;
00162 }
00163
00164 static void
00165 ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
00166 {
00167 ldns_rbnode_t *uncle;
00168
00169
00170 while (node != rbtree->root && node->parent->color == RED) {
00171
00172 if (node->parent == node->parent->parent->left) {
00173 uncle = node->parent->parent->right;
00174
00175
00176 if (uncle->color == RED) {
00177
00178 node->parent->color = BLACK;
00179 uncle->color = BLACK;
00180
00181
00182 node->parent->parent->color = RED;
00183
00184
00185 node = node->parent->parent;
00186 } else {
00187
00188 if (node == node->parent->right) {
00189 node = node->parent;
00190 ldns_rbtree_rotate_left(rbtree, node);
00191 }
00192
00193 node->parent->color = BLACK;
00194 node->parent->parent->color = RED;
00195 ldns_rbtree_rotate_right(rbtree, node->parent->parent);
00196 }
00197 } else {
00198 uncle = node->parent->parent->left;
00199
00200
00201 if (uncle->color == RED) {
00202
00203 node->parent->color = BLACK;
00204 uncle->color = BLACK;
00205
00206
00207 node->parent->parent->color = RED;
00208
00209
00210 node = node->parent->parent;
00211 } else {
00212
00213 if (node == node->parent->left) {
00214 node = node->parent;
00215 ldns_rbtree_rotate_right(rbtree, node);
00216 }
00217
00218 node->parent->color = BLACK;
00219 node->parent->parent->color = RED;
00220 ldns_rbtree_rotate_left(rbtree, node->parent->parent);
00221 }
00222 }
00223 }
00224 rbtree->root->color = BLACK;
00225 }
00226
00227 void
00228 ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree)
00229 {
00230 (void) ldns_rbtree_insert((ldns_rbtree_t *) rbtree,
00231 data);
00232 }
00233
00234
00235
00236
00237
00238
00239
00240 ldns_rbnode_t *
00241 ldns_rbtree_insert (ldns_rbtree_t *rbtree, ldns_rbnode_t *data)
00242 {
00243
00244 int r = 0;
00245
00246
00247 ldns_rbnode_t *node = rbtree->root;
00248 ldns_rbnode_t *parent = LDNS_RBTREE_NULL;
00249
00250
00251 while (node != LDNS_RBTREE_NULL) {
00252
00253 if ((r = rbtree->cmp(data->key, node->key)) == 0) {
00254 return NULL;
00255 }
00256 parent = node;
00257
00258 if (r < 0) {
00259 node = node->left;
00260 } else {
00261 node = node->right;
00262 }
00263 }
00264
00265
00266 data->parent = parent;
00267 data->left = data->right = LDNS_RBTREE_NULL;
00268 data->color = RED;
00269 rbtree->count++;
00270
00271
00272 if (parent != LDNS_RBTREE_NULL) {
00273 if (r < 0) {
00274 parent->left = data;
00275 } else {
00276 parent->right = data;
00277 }
00278 } else {
00279 rbtree->root = data;
00280 }
00281
00282
00283 ldns_rbtree_insert_fixup(rbtree, data);
00284
00285 return data;
00286 }
00287
00288
00289
00290
00291
00292 ldns_rbnode_t *
00293 ldns_rbtree_search (ldns_rbtree_t *rbtree, const void *key)
00294 {
00295 ldns_rbnode_t *node;
00296
00297 if (ldns_rbtree_find_less_equal(rbtree, key, &node)) {
00298 return node;
00299 } else {
00300 return NULL;
00301 }
00302 }
00303
00305 static void swap_int8(uint8_t* x, uint8_t* y)
00306 {
00307 uint8_t t = *x; *x = *y; *y = t;
00308 }
00309
00311 static void swap_np(ldns_rbnode_t** x, ldns_rbnode_t** y)
00312 {
00313 ldns_rbnode_t* t = *x; *x = *y; *y = t;
00314 }
00315
00317 static void change_parent_ptr(ldns_rbtree_t* rbtree, ldns_rbnode_t* parent, ldns_rbnode_t* old, ldns_rbnode_t* new)
00318 {
00319 if(parent == LDNS_RBTREE_NULL)
00320 {
00321 if(rbtree->root == old) rbtree->root = new;
00322 return;
00323 }
00324 if(parent->left == old) parent->left = new;
00325 if(parent->right == old) parent->right = new;
00326 }
00328 static void change_child_ptr(ldns_rbnode_t* child, ldns_rbnode_t* old, ldns_rbnode_t* new)
00329 {
00330 if(child == LDNS_RBTREE_NULL) return;
00331 if(child->parent == old) child->parent = new;
00332 }
00333
00334 ldns_rbnode_t*
00335 ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key)
00336 {
00337 ldns_rbnode_t *to_delete;
00338 ldns_rbnode_t *child;
00339 if((to_delete = ldns_rbtree_search(rbtree, key)) == 0) return 0;
00340 rbtree->count--;
00341
00342
00343 if(to_delete->left != LDNS_RBTREE_NULL &&
00344 to_delete->right != LDNS_RBTREE_NULL)
00345 {
00346
00347 ldns_rbnode_t *smright = to_delete->right;
00348 while(smright->left != LDNS_RBTREE_NULL)
00349 smright = smright->left;
00350
00351
00352
00353
00354
00355
00356 swap_int8(&to_delete->color, &smright->color);
00357
00358
00359 change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);
00360 if(to_delete->right != smright)
00361 change_parent_ptr(rbtree, smright->parent, smright, to_delete);
00362
00363
00364 change_child_ptr(smright->left, smright, to_delete);
00365 change_child_ptr(smright->left, smright, to_delete);
00366 change_child_ptr(smright->right, smright, to_delete);
00367 change_child_ptr(smright->right, smright, to_delete);
00368 change_child_ptr(to_delete->left, to_delete, smright);
00369 if(to_delete->right != smright)
00370 change_child_ptr(to_delete->right, to_delete, smright);
00371 if(to_delete->right == smright)
00372 {
00373
00374 to_delete->right = to_delete;
00375 smright->parent = smright;
00376 }
00377
00378
00379 swap_np(&to_delete->parent, &smright->parent);
00380 swap_np(&to_delete->left, &smright->left);
00381 swap_np(&to_delete->right, &smright->right);
00382
00383
00384 }
00385
00386 if(to_delete->left != LDNS_RBTREE_NULL) child = to_delete->left;
00387 else child = to_delete->right;
00388
00389
00390 change_parent_ptr(rbtree, to_delete->parent, to_delete, child);
00391 change_child_ptr(child, to_delete, to_delete->parent);
00392
00393 if(to_delete->color == RED)
00394 {
00395
00396 }
00397 else if(child->color == RED)
00398 {
00399
00400 if(child!=LDNS_RBTREE_NULL) child->color = BLACK;
00401 }
00402 else ldns_rbtree_delete_fixup(rbtree, child, to_delete->parent);
00403
00404
00405 to_delete->parent = LDNS_RBTREE_NULL;
00406 to_delete->left = LDNS_RBTREE_NULL;
00407 to_delete->right = LDNS_RBTREE_NULL;
00408 to_delete->color = BLACK;
00409 return to_delete;
00410 }
00411
00412 static void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* child_parent)
00413 {
00414 ldns_rbnode_t* sibling;
00415 int go_up = 1;
00416
00417
00418 if(child_parent->right == child) sibling = child_parent->left;
00419 else sibling = child_parent->right;
00420
00421 while(go_up)
00422 {
00423 if(child_parent == LDNS_RBTREE_NULL)
00424 {
00425
00426 return;
00427 }
00428
00429 if(sibling->color == RED)
00430 {
00431 child_parent->color = RED;
00432 sibling->color = BLACK;
00433 if(child_parent->right == child)
00434 ldns_rbtree_rotate_right(rbtree, child_parent);
00435 else ldns_rbtree_rotate_left(rbtree, child_parent);
00436
00437 if(child_parent->right == child) sibling = child_parent->left;
00438 else sibling = child_parent->right;
00439 }
00440
00441 if(child_parent->color == BLACK
00442 && sibling->color == BLACK
00443 && sibling->left->color == BLACK
00444 && sibling->right->color == BLACK)
00445 {
00446 if(sibling != LDNS_RBTREE_NULL)
00447 sibling->color = RED;
00448
00449 child = child_parent;
00450 child_parent = child_parent->parent;
00451
00452 if(child_parent->right == child) sibling = child_parent->left;
00453 else sibling = child_parent->right;
00454 }
00455 else go_up = 0;
00456 }
00457
00458 if(child_parent->color == RED
00459 && sibling->color == BLACK
00460 && sibling->left->color == BLACK
00461 && sibling->right->color == BLACK)
00462 {
00463
00464 if(sibling != LDNS_RBTREE_NULL)
00465 sibling->color = RED;
00466 child_parent->color = BLACK;
00467 return;
00468 }
00469
00470
00471
00472 if(child_parent->right == child
00473 && sibling->color == BLACK
00474 && sibling->right->color == RED
00475 && sibling->left->color == BLACK)
00476 {
00477 sibling->color = RED;
00478 sibling->right->color = BLACK;
00479 ldns_rbtree_rotate_left(rbtree, sibling);
00480
00481 if(child_parent->right == child) sibling = child_parent->left;
00482 else sibling = child_parent->right;
00483 }
00484 else if(child_parent->left == child
00485 && sibling->color == BLACK
00486 && sibling->left->color == RED
00487 && sibling->right->color == BLACK)
00488 {
00489 sibling->color = RED;
00490 sibling->left->color = BLACK;
00491 ldns_rbtree_rotate_right(rbtree, sibling);
00492
00493 if(child_parent->right == child) sibling = child_parent->left;
00494 else sibling = child_parent->right;
00495 }
00496
00497
00498 sibling->color = child_parent->color;
00499 child_parent->color = BLACK;
00500 if(child_parent->right == child)
00501 {
00502 sibling->left->color = BLACK;
00503 ldns_rbtree_rotate_right(rbtree, child_parent);
00504 }
00505 else
00506 {
00507 sibling->right->color = BLACK;
00508 ldns_rbtree_rotate_left(rbtree, child_parent);
00509 }
00510 }
00511
00512 int
00513 ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key, ldns_rbnode_t **result)
00514 {
00515 int r;
00516 ldns_rbnode_t *node;
00517
00518
00519 node = rbtree->root;
00520
00521 *result = NULL;
00522
00523
00524 while (node != LDNS_RBTREE_NULL) {
00525 r = rbtree->cmp(key, node->key);
00526 if (r == 0) {
00527
00528 *result = node;
00529 return 1;
00530 }
00531 if (r < 0) {
00532 node = node->left;
00533 } else {
00534
00535 *result = node;
00536 node = node->right;
00537 }
00538 }
00539 return 0;
00540 }
00541
00542
00543
00544
00545
00546 ldns_rbnode_t *
00547 ldns_rbtree_first (ldns_rbtree_t *rbtree)
00548 {
00549 ldns_rbnode_t *node = rbtree->root;
00550
00551 if (rbtree->root != LDNS_RBTREE_NULL) {
00552 for (node = rbtree->root; node->left != LDNS_RBTREE_NULL; node = node->left);
00553 }
00554 return node;
00555 }
00556
00557 ldns_rbnode_t *
00558 ldns_rbtree_last (ldns_rbtree_t *rbtree)
00559 {
00560 ldns_rbnode_t *node = rbtree->root;
00561
00562 if (rbtree->root != LDNS_RBTREE_NULL) {
00563 for (node = rbtree->root; node->right != LDNS_RBTREE_NULL; node = node->right);
00564 }
00565 return node;
00566 }
00567
00568
00569
00570
00571
00572 ldns_rbnode_t *
00573 ldns_rbtree_next (ldns_rbnode_t *node)
00574 {
00575 ldns_rbnode_t *parent;
00576
00577 if (node->right != LDNS_RBTREE_NULL) {
00578
00579 for (node = node->right;
00580 node->left != LDNS_RBTREE_NULL;
00581 node = node->left);
00582 } else {
00583 parent = node->parent;
00584 while (parent != LDNS_RBTREE_NULL && node == parent->right) {
00585 node = parent;
00586 parent = parent->parent;
00587 }
00588 node = parent;
00589 }
00590 return node;
00591 }
00592
00593 ldns_rbnode_t *
00594 ldns_rbtree_previous(ldns_rbnode_t *node)
00595 {
00596 ldns_rbnode_t *parent;
00597
00598 if (node->left != LDNS_RBTREE_NULL) {
00599
00600 for (node = node->left;
00601 node->right != LDNS_RBTREE_NULL;
00602 node = node->right);
00603 } else {
00604 parent = node->parent;
00605 while (parent != LDNS_RBTREE_NULL && node == parent->left) {
00606 node = parent;
00607 parent = parent->parent;
00608 }
00609 node = parent;
00610 }
00611 return node;
00612 }
00613
00618 ldns_rbtree_t *
00619 ldns_rbtree_split(ldns_rbtree_t *tree,
00620 size_t elements)
00621 {
00622 ldns_rbtree_t *new_tree;
00623 ldns_rbnode_t *cur_node;
00624 ldns_rbnode_t *move_node;
00625 size_t count = 0;
00626
00627 new_tree = ldns_rbtree_create(tree->cmp);
00628
00629 cur_node = ldns_rbtree_first(tree);
00630 while (count < elements && cur_node != LDNS_RBTREE_NULL) {
00631 move_node = ldns_rbtree_delete(tree, cur_node->key);
00632 (void)ldns_rbtree_insert(new_tree, move_node);
00633 cur_node = ldns_rbtree_first(tree);
00634 count++;
00635 }
00636
00637 return new_tree;
00638 }
00639
00640
00641
00642
00643
00644 void
00645 ldns_rbtree_join(ldns_rbtree_t *tree1, ldns_rbtree_t *tree2)
00646 {
00647 ldns_traverse_postorder(tree2, ldns_rbtree_insert_vref, tree1);
00648 }
00649
00651 static void
00652 traverse_post(void (*func)(ldns_rbnode_t*, void*), void* arg,
00653 ldns_rbnode_t* node)
00654 {
00655 if(!node || node == LDNS_RBTREE_NULL)
00656 return;
00657
00658 traverse_post(func, arg, node->left);
00659 traverse_post(func, arg, node->right);
00660
00661 (*func)(node, arg);
00662 }
00663
00664 void
00665 ldns_traverse_postorder(ldns_rbtree_t* tree,
00666 void (*func)(ldns_rbnode_t*, void*), void* arg)
00667 {
00668 traverse_post(func, arg, tree->root);
00669 }