nginx_sys/
rbtree.rs

1use core::ptr;
2
3use crate::bindings::{ngx_rbtree_insert_pt, ngx_rbtree_node_t, ngx_rbtree_t};
4
5/// Get a reference to the beginning of a tree element data structure,
6/// considering the link field offset in it.
7///
8/// # Safety
9///
10/// `$node` must be a valid pointer to the field `$link` in the struct `$type`
11#[macro_export]
12macro_rules! ngx_rbtree_data {
13    ($node:expr, $type:path, $link:ident) => {
14        $node
15            .byte_sub(::core::mem::offset_of!($type, $link))
16            .cast::<$type>()
17    };
18}
19
20/// Initializes the RbTree with specified sentinel and insert function.
21///
22/// # Safety
23///
24/// All of the pointers passed must be valid.
25/// `sentinel` is expected to be valid for the whole lifetime of the `tree`.
26///
27pub unsafe fn ngx_rbtree_init(
28    tree: *mut ngx_rbtree_t,
29    sentinel: *mut ngx_rbtree_node_t,
30    insert: ngx_rbtree_insert_pt,
31) {
32    ngx_rbtree_sentinel_init(sentinel);
33    (*tree).root = sentinel;
34    (*tree).sentinel = sentinel;
35    (*tree).insert = insert;
36}
37
38/// Marks the tree node as red.
39///
40/// # Safety
41///
42/// `node` must be a valid pointer to a [ngx_rbtree_node_t].
43#[inline]
44pub unsafe fn ngx_rbt_red(node: *mut ngx_rbtree_node_t) {
45    (*node).color = 1
46}
47
48/// Marks the tree node as black.
49///
50/// # Safety
51///
52/// `node` must be a valid pointer to a [ngx_rbtree_node_t].
53#[inline]
54pub unsafe fn ngx_rbt_black(node: *mut ngx_rbtree_node_t) {
55    (*node).color = 0
56}
57
58/// Initializes the sentinel node.
59///
60/// # Safety
61///
62/// `node` must be a valid pointer to a [ngx_rbtree_node_t].
63#[inline]
64pub unsafe fn ngx_rbtree_sentinel_init(node: *mut ngx_rbtree_node_t) {
65    ngx_rbt_black(node)
66}
67
68/// Returns the least (leftmost) node of the tree.
69///
70/// # Safety
71///
72/// `node` must be a valid pointer to a [ngx_rbtree_node_t].
73/// `sentinel` must be a valid pointer to the sentinel node in the same Red-Black tree.
74#[inline]
75pub unsafe fn ngx_rbtree_min(
76    mut node: *mut ngx_rbtree_node_t,
77    sentinel: *mut ngx_rbtree_node_t,
78) -> *mut ngx_rbtree_node_t {
79    while !ptr::addr_eq((*node).left, sentinel) {
80        node = (*node).left;
81    }
82
83    node
84}
nginx_sys/rbtree.rs

nginx_sys/
rbtree.rs
