1e18a033bSKonstantin Ananyev
2e18a033bSKonstantin Ananyev/*
3e18a033bSKonstantin Ananyev * Copyright (C) Igor Sysoev
4e18a033bSKonstantin Ananyev * Copyright (C) Nginx, Inc.
5e18a033bSKonstantin Ananyev */
6e18a033bSKonstantin Ananyev
7e18a033bSKonstantin Ananyev
8e18a033bSKonstantin Ananyev#ifndef _NGX_RADIX_TREE_H_INCLUDED_
9e18a033bSKonstantin Ananyev#define _NGX_RADIX_TREE_H_INCLUDED_
10e18a033bSKonstantin Ananyev
11e18a033bSKonstantin Ananyev
12e18a033bSKonstantin Ananyev#include <ngx_config.h>
13e18a033bSKonstantin Ananyev#include <ngx_core.h>
14e18a033bSKonstantin Ananyev
15e18a033bSKonstantin Ananyev
16e18a033bSKonstantin Ananyev#define NGX_RADIX_NO_VALUE   (uintptr_t) -1
17e18a033bSKonstantin Ananyev
18e18a033bSKonstantin Ananyevtypedef struct ngx_radix_node_s  ngx_radix_node_t;
19e18a033bSKonstantin Ananyev
20e18a033bSKonstantin Ananyevstruct ngx_radix_node_s {
21e18a033bSKonstantin Ananyev    ngx_radix_node_t  *right;
22e18a033bSKonstantin Ananyev    ngx_radix_node_t  *left;
23e18a033bSKonstantin Ananyev    ngx_radix_node_t  *parent;
24e18a033bSKonstantin Ananyev    uintptr_t          value;
25e18a033bSKonstantin Ananyev};
26e18a033bSKonstantin Ananyev
27e18a033bSKonstantin Ananyev
28e18a033bSKonstantin Ananyevtypedef struct {
29e18a033bSKonstantin Ananyev    ngx_radix_node_t  *root;
30e18a033bSKonstantin Ananyev    ngx_pool_t        *pool;
31e18a033bSKonstantin Ananyev    ngx_radix_node_t  *free;
32e18a033bSKonstantin Ananyev    char              *start;
33e18a033bSKonstantin Ananyev    size_t             size;
34e18a033bSKonstantin Ananyev} ngx_radix_tree_t;
35e18a033bSKonstantin Ananyev
36e18a033bSKonstantin Ananyev
37e18a033bSKonstantin Ananyevngx_radix_tree_t *ngx_radix_tree_create(ngx_pool_t *pool,
38e18a033bSKonstantin Ananyev    ngx_int_t preallocate);
39e18a033bSKonstantin Ananyev
40e18a033bSKonstantin Ananyevngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree,
41e18a033bSKonstantin Ananyev    uint32_t key, uint32_t mask, uintptr_t value);
42e18a033bSKonstantin Ananyevngx_int_t ngx_radix32tree_delete(ngx_radix_tree_t *tree,
43e18a033bSKonstantin Ananyev    uint32_t key, uint32_t mask);
44e18a033bSKonstantin Ananyevuintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key);
45e18a033bSKonstantin Ananyev
46e18a033bSKonstantin Ananyev#if (NGX_HAVE_INET6)
47e18a033bSKonstantin Ananyevngx_int_t ngx_radix128tree_insert(ngx_radix_tree_t *tree,
48e18a033bSKonstantin Ananyev    u_char *key, u_char *mask, uintptr_t value);
49e18a033bSKonstantin Ananyevngx_int_t ngx_radix128tree_delete(ngx_radix_tree_t *tree,
50e18a033bSKonstantin Ananyev    u_char *key, u_char *mask);
51e18a033bSKonstantin Ananyevuintptr_t ngx_radix128tree_find(ngx_radix_tree_t *tree, u_char *key);
52e18a033bSKonstantin Ananyev#endif
53e18a033bSKonstantin Ananyev
54e18a033bSKonstantin Ananyev
55e18a033bSKonstantin Ananyev#endif /* _NGX_RADIX_TREE_H_INCLUDED_ */
56