src/core/ngx_radix_tree.h

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