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