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