Implementation of a redblack tree. More...
Macros | |
| #define | BLACK 0 |
| Node colour black. | |
| #define | RED 1 |
| Node colour red. | |
Functions | |
| static void | rbtree_rotate_left (rbtree_type *rbtree, rbnode_type *node) |
| rotate subtree left (to preserve redblack property) | |
| static void | rbtree_rotate_right (rbtree_type *rbtree, rbnode_type *node) |
| rotate subtree right (to preserve redblack property) | |
| static void | rbtree_insert_fixup (rbtree_type *rbtree, rbnode_type *node) |
| Fixup node colours when insert happened. | |
| static void | rbtree_delete_fixup (rbtree_type *rbtree, rbnode_type *child, rbnode_type *child_parent) |
| Fixup node colours when delete happened. | |
| rbtree_type * | rbtree_create (int(*cmpf)(const void *, const void *)) |
| Create new tree (malloced) with given key compare function. More... | |
| void | rbtree_init (rbtree_type *rbtree, int(*cmpf)(const void *, const void *)) |
| Init a new tree (malloced by caller) with given key compare function. More... | |
| rbnode_type * | rbtree_insert (rbtree_type *rbtree, rbnode_type *data) |
| Insert data into the tree. More... | |
| rbnode_type * | rbtree_search (rbtree_type *rbtree, const void *key) |
| Find key in tree. More... | |
| static void | swap_int8 (uint8_t *x, uint8_t *y) |
| helpers for delete: swap node colours | |
| static void | swap_np (rbnode_type **x, rbnode_type **y) |
| helpers for delete: swap node pointers | |
| static void | change_parent_ptr (rbtree_type *rbtree, rbnode_type *parent, rbnode_type *old, rbnode_type *new) |
| Update parent pointers of child trees of 'parent'. | |
| static void | change_child_ptr (rbnode_type *child, rbnode_type *old, rbnode_type *new) |
| Update parent pointer of a node 'child'. | |
| rbnode_type * | rbtree_delete (rbtree_type *rbtree, const void *key) |
| Delete element from tree. More... | |
| int | rbtree_find_less_equal (rbtree_type *rbtree, const void *key, rbnode_type **result) |
| Find, but match does not have to be exact. More... | |
| rbnode_type * | rbtree_first (rbtree_type *rbtree) |
| Returns first (smallest) node in the tree. More... | |
| rbnode_type * | rbtree_last (rbtree_type *rbtree) |
| Returns last (largest) node in the tree. More... | |
| rbnode_type * | rbtree_next (rbnode_type *node) |
| Returns next larger node in the tree. More... | |
| rbnode_type * | rbtree_previous (rbnode_type *node) |
| Returns previous smaller node in the tree. More... | |
| static void | traverse_post (void(*func)(rbnode_type *, void *), void *arg, rbnode_type *node) |
| recursive descent traverse | |
| void | traverse_postorder (rbtree_type *tree, void(*func)(rbnode_type *, void *), void *arg) |
| Call function for all elements in the redblack tree, such that leaf elements are called before parent elements. More... | |
Variables | |
| rbnode_type | rbtree_null_node |
| the NULL node, global alloc More... | |
Implementation of a redblack tree.
| rbtree_type* rbtree_create | ( | int(*)(const void *, const void *) | cmpf | ) |
Create new tree (malloced) with given key compare function.
| cmpf | compare function (like strcmp) takes pointers to two keys. |
References rbtree_init().
Referenced by anchors_create(), iter_apply_cfg(), macro_store_create(), main(), and outside_network_create().
| void rbtree_init | ( | rbtree_type * | rbtree, |
| int(*)(const void *, const void *) | cmpf | ||
| ) |
Init a new tree (malloced by caller) with given key compare function.
| rbtree | uninitialised memory for new tree, returned empty. |
| cmpf | compare function (like strcmp) takes pointers to two keys. |
References rbtree_type::cmp, rbtree_type::count, RBTREE_NULL, and rbtree_type::root.
Referenced by addr_tree_addrport_init(), addr_tree_init(), apply_axfr(), apply_http(), auth_zone_create(), auth_zone_read_zonefile(), auth_zones_create(), autr_global_create(), local_zone_create(), local_zones_create(), mesh_create(), mesh_delete_all(), mesh_detach_subs(), mesh_state_create(), name_tree_init(), neg_setup_zone_node(), nsec3_cache_table_init(), outside_network_create(), outside_network_delete(), rbtree_create(), reuse_cb_and_decommission(), reuse_del_readwait(), rrset_canonical(), rrset_canonical_equal(), rrset_canonicalize_to_buffer(), tcp_reuse_tree_list_test(), tcpid_fillup(), tcpid_test(), ub_ctx_create_nopipe(), val_neg_create(), and views_create().
| rbnode_type* rbtree_insert | ( | rbtree_type * | rbtree, |
| rbnode_type * | data | ||
| ) |
Insert data into the tree.
| rbtree | tree to insert to. |
| data | element to insert. |
References rbtree_type::cmp, rbnode_type::color, rbtree_type::count, fptr_ok, fptr_whitelist_rbtree_cmp(), rbnode_type::key, rbnode_type::left, rbnode_type::parent, rbtree_insert_fixup(), RBTREE_NULL, RED, rbnode_type::right, and rbtree_type::root.
Referenced by addr_tree_insert(), anchor_new_ta(), auth_xfer_create(), auth_zone_create(), autr_tp_create(), az_domain_create(), canonical_sort(), forwards_insert_data(), get_codeline(), lz_enter_zone_dname(), lz_find_create_node(), macro_assign(), mesh_add_sub(), mesh_new_callback(), mesh_state_attachment(), mesh_walk_supers(), name_tree_insert(), neg_create_zone(), neg_insert_data(), nsec3_hash_name(), parse_var_line(), reuse_tcp_insert(), reuse_tree_by_id_insert(), serviced_create(), set_next_probe(), todo_probe(), and views_enter_view_name().
| rbnode_type* rbtree_search | ( | rbtree_type * | rbtree, |
| const void * | key | ||
| ) |
Find key in tree.
Returns NULL if not found.
| rbtree | tree to find in. |
| key | key that must match. |
References rbtree_find_less_equal().
Referenced by addr_tree_find(), anchor_find(), anchors_add_insecure(), anchors_delete_insecure(), auth_xfer_find(), auth_zone_find(), auth_zones_pickup_zonemd_verify(), az_find_name(), find_id(), forwards_find(), get_codeline(), local_zone_does_not_cover(), local_zone_find_data(), local_zones_find(), lookup_serviced(), lz_exists(), macro_getvar(), mesh_area_find(), name_tree_find(), neg_find_data(), neg_find_zone(), nsec3_hash_name(), rbtree_delete(), reuse_tcp_by_id_find(), set_next_probe(), ub_cancel(), and views_find_view().
| rbnode_type* rbtree_delete | ( | rbtree_type * | rbtree, |
| const void * | key | ||
| ) |
Delete element from tree.
| rbtree | tree to delete from. |
| key | key of item to delete. |
References BLACK, change_child_ptr(), change_parent_ptr(), rbnode_type::color, rbtree_type::count, rbnode_type::left, log_assert, rbnode_type::parent, rbtree_delete_fixup(), RBTREE_NULL, rbtree_search(), RED, rbnode_type::right, swap_int8(), and swap_np().
Referenced by add_bg_result(), anchors_delete_insecure(), autr_tp_create(), az_delete_deleted_zones(), az_remove_rr(), del_empty_term(), hints_add_stub(), hints_delete_stub(), libworker_bg_done_cb(), local_zones_del_zone(), mesh_detach_subs(), mesh_run(), mesh_state_delete(), neg_delete_data(), neg_delete_zone(), outnet_serviced_query(), outnet_serviced_query_stop(), parse_var_line(), pending_delete(), respip_sockaddr_delete(), reuse_tcp_remove_tree_list(), reuse_tree_by_id_delete(), serviced_callbacks(), set_next_probe(), todo_probe(), ub_cancel(), ub_resolve(), and ub_resolve_async().
| int rbtree_find_less_equal | ( | rbtree_type * | rbtree, |
| const void * | key, | ||
| rbnode_type ** | result | ||
| ) |
Find, but match does not have to be exact.
| rbtree | tree to find in. |
| key | key to find position of. |
| result | set to the exact node if present, otherwise to element that precedes the position of key in the tree. NULL if no smaller element. |
References rbtree_type::cmp, fptr_ok, fptr_whitelist_rbtree_cmp(), rbnode_type::key, rbnode_type::left, log_assert, RBTREE_NULL, rbnode_type::right, and rbtree_type::root.
Referenced by addr_tree_lookup(), anchors_lookup(), auth_zone_find_less_equal(), az_find_domain(), forwards_lookup(), local_zones_find_le(), local_zones_tags_lookup(), name_tree_lookup(), name_tree_next_root(), neg_closest_data(), neg_closest_data_parent(), neg_closest_zone_parent(), rbtree_search(), and reuse_tcp_find().
| rbnode_type* rbtree_first | ( | rbtree_type * | rbtree | ) |
Returns first (smallest) node in the tree.
| rbtree | tree |
References rbnode_type::left, RBTREE_NULL, and rbtree_type::root.
Referenced by addr_tree_init_parents(), anchors_assemble_rrsets(), anchors_find_any_noninsecure(), az_empty_nonterminal(), name_tree_next_root(), remove_item(), reuse_cb_readwait_for_failure(), reuse_tcp_find(), reuse_tcp_select_id(), rrset_canonical_equal(), sumtrees_inuse(), todo_probe(), and wait_probe_time().
| rbnode_type* rbtree_last | ( | rbtree_type * | rbtree | ) |
Returns last (largest) node in the tree.
| rbtree | tree |
References RBTREE_NULL, rbnode_type::right, and rbtree_type::root.
Referenced by az_nsec3_find_cover(), neg_nsec3_getnc(), and reuse_tcp_select_id().
| rbnode_type* rbtree_next | ( | rbnode_type * | rbtree | ) |
Returns next larger node in the tree.
| rbtree | tree |
References rbnode_type::left, rbnode_type::parent, RBTREE_NULL, and rbnode_type::right.
Referenced by addr_tree_init_parents_node(), anchors_assemble_rrsets(), anchors_find_any_noninsecure(), az_empty_nonterminal(), is_terminal(), name_tree_next_root(), remove_item(), reuse_cb_readwait_for_failure(), reuse_tcp_find(), reuse_tcp_select_id(), rrset_canonical_equal(), and set_kiddo_parents().
| rbnode_type* rbtree_previous | ( | rbnode_type * | rbtree | ) |
Returns previous smaller node in the tree.
| rbtree | tree |
References rbnode_type::left, rbnode_type::parent, RBTREE_NULL, and rbnode_type::right.
Referenced by neg_find_nsec(), respip_sockaddr_delete(), and reuse_tcp_find().
| void traverse_postorder | ( | rbtree_type * | tree, |
| void(*)(rbnode_type *, void *) | func, | ||
| void * | arg | ||
| ) |
Call function for all elements in the redblack tree, such that leaf elements are called before parent elements.
So that all elements can be safely free()d. Note that your function must not remove the nodes from the tree. Since that may trigger rebalances of the rbtree.
| tree | the tree |
| func | function called with element and user arg. The function must not alter the rbtree. |
| arg | user argument. |
References rbtree_type::root, and traverse_post().
Referenced by anchors_delete(), apply_axfr(), apply_http(), auth_zone_delete(), auth_zone_read_zonefile(), auth_zones_delete(), dns64_deinit(), infra_adjust(), infra_delete(), iter_deinit(), local_zones_delete(), locks_free(), macro_store_delete(), neg_cache_delete(), outside_network_delete(), respip_set_delete(), reuse_cb_and_decommission(), reuse_del_readwait(), tcl_list_delete(), and views_delete().
| rbnode_type rbtree_null_node |
the NULL node, global alloc
the global empty node