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