ngx_rbtree_t红黑树

<span>typedef</span> ngx_uint_t ngx_rbtree_key_t;

<span>typedef</span><span>struct</span> ngx_rbtree_node_s ngx_rbtree_node_t;

<span>struct</span><span>struct</span> ngx_rbtree_node_s {
    <span>//无符号整型关键字</span>
    ngx_rbtree_key_t        key;
    <span>//左子节点</span>
    ngx_rbtree_node_t   *left;
    <span>//右子节点</span>
    ngx_rbtree_node_t   *right;
    <span>//父节点</span>
    ngx_rbtree_node_t   *parent;
    <span>//节点的颜色，0：黑，1：红</span>
    u_char                  color;
    <span>//仅一字节的数据</span>
    u_char              data;
    };

<span>typedef</span><span>struct</span> {
    ngx_rbtree_node_t   node;
    ngx_uint_t          num;
    }TestRBTreeBode;

<span>typedef</span><span>struct</span> ngx_rbtree_s ngx_rbtree_t;

<span>/* 为解决不同节点含有相同关键字的元素冲突问题所存在的指针*/</span><span>typedef</span><span>void</span> (*ngx_rbtree_insert_pt)(ngx_rbtree_node_t *root,ngx_rbtree_node_t *node,ngx_rbtreenode_t *sentinel);

<span>struct</span> ngx_rbtree_s {
    <span>//指向树的根节点（可以直接强制转化为数据元素）</span>
    ngx_rbtree_node_t       *root;
    <span>//指向NIL哨兵节点</span>
    ngx_rbtree_node_t       *sentinel;
    <span>//红黑树添加元素的指针</span>
    ngx_rbtree_insert_pt    insert;
    };