src/core/ngx_radix_tree.c

   1
   2 /*
   3  * Copyright (C) Igor Sysoev
   4  */
   5
   6
   7 #include <ngx_config.h>
   8 #include <ngx_core.h>
   9
  10
  11 static void *ngx_radix_alloc(ngx_radix_tree_t *tree);
  12
  13
  14 ngx_radix_tree_t *
  15 ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate)
  16 {
  17     uint32_t           key, mask, inc;
  18     ngx_radix_tree_t  *tree;
  19
  20     if (!(tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)))) {
  21         return NULL;
  22     }
  23
  24     tree->pool = pool;
  25     tree->free = NULL;
  26     tree->start = NULL;
  27     tree->size = 0;
  28
  29     if (!(tree->root = ngx_radix_alloc(tree))) {
  30         return NULL;
  31     }
  32
  33     tree->root->right = NULL;
  34     tree->root->left = NULL;
  35     tree->root->parent = NULL;
  36     tree->root->value = NGX_RADIX_NO_VALUE;
  37
  38     if (preallocate == 0) {
  39         return tree;
  40     }
  41
  42     /*
  43      * We preallocate the first nodes: 0, 1, 00, 01, 10, 11, 000, 001, etc.,
  44      * to increase the TLB hits even if for the first lookup iterations.
  45      * On the 32-bit platforms the 7 preallocated bits takes continuous 4K,
  46      * 8 - 8K, 9 - 16K, etc.  On the 64-bit platforms the 6 preallocated bits
  47      * takes continuous 4K, 7 - 8K, 8 - 16K, etc.  There is no sense to
  48      * to preallocate more than one page, because further preallocation
  49      * distribute the only bit per page.  Instead, the random insertion
  50      * may distribute several bits per page.
  51      *
  52      * Thus, by default we preallocate maximum
  53      *     6 bits on amd64 (64-bit platform and 4K pages)
  54      *     7 bits on i386 (32-bit platform and 4K pages)
  55      *     7 bits on sparc64 in 64-bit mode (8K pages)
  56      *     8 bits on sparc64 in 32-bit mode (8K pages)
  57      */
  58
  59     if (preallocate == -1) {
  60         switch (ngx_pagesize / sizeof(ngx_radix_tree_t)) {
  61
  62         /* amd64 */
  63         case 128:
  64             preallocate = 6;
  65             break;
  66
  67         /* i386, sparc64 */
  68         case 256:
  69             preallocate = 7;
  70             break;
  71
  72         /* sparc64 in 32-bit mode */
  73         default:
  74             preallocate = 8;
  75         }
  76     }
  77
  78     mask = 0;
  79     inc = 0x80000000;
  80
  81     while (preallocate--) {
  82
  83         key = 0;
  84         mask >>= 1;
  85         mask |= 0x80000000;
  86
  87         do {
  88             if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE)
  89                                                                      != NGX_OK)
  90             {
  91                 return NULL;
  92             }
  93
  94             key += inc;
  95
  96         } while (key);
  97
  98         inc >>= 1;
  99     }
 100
 101     return tree;
 102 }
 103
 104
 105 ngx_int_t
 106 ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
 107     uintptr_t value)
 108 {
 109     uint32_t           bit;
 110     ngx_radix_node_t  *node, *next;
 111
 112     bit = 0x80000000;
 113
 114     node = tree->root;
 115     next = tree->root;
 116
 117     while (bit & mask) {
 118         if (key & bit) {
 119             next = node->right;
 120
 121         } else {
 122             next = node->left;
 123         }
 124
 125         if (next == NULL) {
 126             break;
 127         }
 128
 129         bit >>= 1;
 130         node = next;
 131     }
 132
 133     if (next) {
 134         if (node->value != NGX_RADIX_NO_VALUE) {
 135             return NGX_BUSY;
 136         }
 137
 138         node->value = value;
 139         return NGX_OK;
 140     }
 141
 142     while (bit & mask) {
 143         if (!(next = ngx_radix_alloc(tree))) {
 144             return NGX_ERROR;
 145         }
 146
 147         next->right = NULL;
 148         next->left = NULL;
 149         next->parent = node;
 150         next->value = NGX_RADIX_NO_VALUE;
 151
 152         if (key & bit) {
 153             node->right = next;
 154
 155         } else {
 156             node->left = next;
 157         }
 158
 159         bit >>= 1;
 160         node = next;
 161     }
 162
 163     node->value = value;
 164
 165     return NGX_OK;
 166 }
 167
 168
 169 ngx_int_t
 170 ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
 171 {
 172     uint32_t           bit;
 173     ngx_radix_node_t  *node;
 174
 175     bit = 0x80000000;
 176     node = tree->root;
 177
 178     while (node && (bit & mask)) {
 179         if (key & bit) {
 180             node = node->right;
 181
 182         } else {
 183             node = node->left;
 184         }
 185
 186         bit >>= 1;
 187     }
 188
 189     if (node == NULL) {
 190         return NGX_ERROR;
 191     }
 192
 193     if (node->right || node->left) {
 194         if (node->value != NGX_RADIX_NO_VALUE) {
 195             node->value = NGX_RADIX_NO_VALUE;
 196             return NGX_OK;
 197         }
 198
 199         return NGX_ERROR;
 200     }
 201
 202     for ( ;; ) {
 203         if (node->parent->right == node) {
 204             node->parent->right = NULL;
 205         } else {
 206             node->parent->left = NULL;
 207         }
 208
 209         node->right = tree->free;
 210         tree->free = node;
 211
 212         node = node->parent;
 213
 214         if (node->right
 215             || node->left
 216             || node->value != NGX_RADIX_NO_VALUE
 217             || node->parent == NULL)
 218         {
 219             break;
 220         }
 221     }
 222
 223     return NGX_OK;
 224 }
 225
 226
 227 uintptr_t
 228 ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
 229 {
 230     uint32_t           bit;
 231     uintptr_t          value;
 232     ngx_radix_node_t  *node;
 233
 234     bit = 0x80000000;
 235     value = NGX_RADIX_NO_VALUE;
 236     node = tree->root;
 237
 238     while (node) {
 239         if (node->value != NGX_RADIX_NO_VALUE) {
 240             value = node->value;
 241         }
 242
 243         if (key & bit) {
 244             node = node->right;
 245
 246         } else {
 247             node = node->left;
 248         }
 249
 250         bit >>= 1;
 251     }
 252
 253     return value;
 254 }
 255
 256
 257 static void *
 258 ngx_radix_alloc(ngx_radix_tree_t *tree)
 259 {
 260     char  *p;
 261
 262     if (tree->free) {
 263         p = (char *) tree->free;
 264         tree->free = tree->free->right;
 265         return p;
 266     }
 267
 268     if (tree->size < sizeof(ngx_radix_node_t)) {
 269         if (!(tree->start = ngx_palloc(tree->pool, ngx_pagesize))) {
 270             return NULL;
 271         }
 272
 273         tree->size = ngx_pagesize;
 274     }
 275
 276     p = tree->start;
 277     tree->start += sizeof(ngx_radix_node_t);
 278     tree->size -= sizeof(ngx_radix_node_t);
 279
 280     return p;
 281 }