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