aboutsummaryrefslogtreecommitdiffstats
path: root/app/nginx/src/core/ngx_radix_tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'app/nginx/src/core/ngx_radix_tree.c')
-rw-r--r--app/nginx/src/core/ngx_radix_tree.c488
1 files changed, 0 insertions, 488 deletions
diff --git a/app/nginx/src/core/ngx_radix_tree.c b/app/nginx/src/core/ngx_radix_tree.c
deleted file mode 100644
index c1d8737..0000000
--- a/app/nginx/src/core/ngx_radix_tree.c
+++ /dev/null
@@ -1,488 +0,0 @@
-
-/*
- * Copyright (C) Igor Sysoev
- * Copyright (C) Nginx, Inc.
- */
-
-
-#include <ngx_config.h>
-#include <ngx_core.h>
-
-
-static ngx_radix_node_t *ngx_radix_alloc(ngx_radix_tree_t *tree);
-
-
-ngx_radix_tree_t *
-ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate)
-{
- uint32_t key, mask, inc;
- ngx_radix_tree_t *tree;
-
- tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t));
- if (tree == NULL) {
- return NULL;
- }
-
- tree->pool = pool;
- tree->free = NULL;
- tree->start = NULL;
- tree->size = 0;
-
- tree->root = ngx_radix_alloc(tree);
- if (tree->root == NULL) {
- return NULL;
- }
-
- tree->root->right = NULL;
- tree->root->left = NULL;
- tree->root->parent = NULL;
- tree->root->value = NGX_RADIX_NO_VALUE;
-
- if (preallocate == 0) {
- return tree;
- }
-
- /*
- * Preallocation of first nodes : 0, 1, 00, 01, 10, 11, 000, 001, etc.
- * increases TLB hits even if for first lookup iterations.
- * On 32-bit platforms the 7 preallocated bits takes continuous 4K,
- * 8 - 8K, 9 - 16K, etc. On 64-bit platforms the 6 preallocated bits
- * takes continuous 4K, 7 - 8K, 8 - 16K, etc. There is no sense to
- * to preallocate more than one page, because further preallocation
- * distributes the only bit per page. Instead, a random insertion
- * may distribute several bits per page.
- *
- * Thus, by default we preallocate maximum
- * 6 bits on amd64 (64-bit platform and 4K pages)
- * 7 bits on i386 (32-bit platform and 4K pages)
- * 7 bits on sparc64 in 64-bit mode (8K pages)
- * 8 bits on sparc64 in 32-bit mode (8K pages)
- */
-
- if (preallocate == -1) {
- switch (ngx_pagesize / sizeof(ngx_radix_node_t)) {
-
- /* amd64 */
- case 128:
- preallocate = 6;
- break;
-
- /* i386, sparc64 */
- case 256:
- preallocate = 7;
- break;
-
- /* sparc64 in 32-bit mode */
- default:
- preallocate = 8;
- }
- }
-
- mask = 0;
- inc = 0x80000000;
-
- while (preallocate--) {
-
- key = 0;
- mask >>= 1;
- mask |= 0x80000000;
-
- do {
- if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE)
- != NGX_OK)
- {
- return NULL;
- }
-
- key += inc;
-
- } while (key);
-
- inc >>= 1;
- }
-
- return tree;
-}
-
-
-ngx_int_t
-ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
- uintptr_t value)
-{
- uint32_t bit;
- ngx_radix_node_t *node, *next;
-
- bit = 0x80000000;
-
- node = tree->root;
- next = tree->root;
-
- while (bit & mask) {
- if (key & bit) {
- next = node->right;
-
- } else {
- next = node->left;
- }
-
- if (next == NULL) {
- break;
- }
-
- bit >>= 1;
- node = next;
- }
-
- if (next) {
- if (node->value != NGX_RADIX_NO_VALUE) {
- return NGX_BUSY;
- }
-
- node->value = value;
- return NGX_OK;
- }
-
- while (bit & mask) {
- next = ngx_radix_alloc(tree);
- if (next == NULL) {
- return NGX_ERROR;
- }
-
- next->right = NULL;
- next->left = NULL;
- next->parent = node;
- next->value = NGX_RADIX_NO_VALUE;
-
- if (key & bit) {
- node->right = next;
-
- } else {
- node->left = next;
- }
-
- bit >>= 1;
- node = next;
- }
-
- node->value = value;
-
- return NGX_OK;
-}
-
-
-ngx_int_t
-ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
-{
- uint32_t bit;
- ngx_radix_node_t *node;
-
- bit = 0x80000000;
- node = tree->root;
-
- while (node && (bit & mask)) {
- if (key & bit) {
- node = node->right;
-
- } else {
- node = node->left;
- }
-
- bit >>= 1;
- }
-
- if (node == NULL) {
- return NGX_ERROR;
- }
-
- if (node->right || node->left) {
- if (node->value != NGX_RADIX_NO_VALUE) {
- node->value = NGX_RADIX_NO_VALUE;
- return NGX_OK;
- }
-
- return NGX_ERROR;
- }
-
- for ( ;; ) {
- if (node->parent->right == node) {
- node->parent->right = NULL;
-
- } else {
- node->parent->left = NULL;
- }
-
- node->right = tree->free;
- tree->free = node;
-
- node = node->parent;
-
- if (node->right || node->left) {
- break;
- }
-
- if (node->value != NGX_RADIX_NO_VALUE) {
- break;
- }
-
- if (node->parent == NULL) {
- break;
- }
- }
-
- return NGX_OK;
-}
-
-
-uintptr_t
-ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
-{
- uint32_t bit;
- uintptr_t value;
- ngx_radix_node_t *node;
-
- bit = 0x80000000;
- value = NGX_RADIX_NO_VALUE;
- node = tree->root;
-
- while (node) {
- if (node->value != NGX_RADIX_NO_VALUE) {
- value = node->value;
- }
-
- if (key & bit) {
- node = node->right;
-
- } else {
- node = node->left;
- }
-
- bit >>= 1;
- }
-
- return value;
-}
-
-
-#if (NGX_HAVE_INET6)
-
-ngx_int_t
-ngx_radix128tree_insert(ngx_radix_tree_t *tree, u_char *key, u_char *mask,
- uintptr_t value)
-{
- u_char bit;
- ngx_uint_t i;
- ngx_radix_node_t *node, *next;
-
- i = 0;
- bit = 0x80;
-
- node = tree->root;
- next = tree->root;
-
- while (bit & mask[i]) {
- if (key[i] & bit) {
- next = node->right;
-
- } else {
- next = node->left;
- }
-
- if (next == NULL) {
- break;
- }
-
- bit >>= 1;
- node = next;
-
- if (bit == 0) {
- if (++i == 16) {
- break;
- }
-
- bit = 0x80;
- }
- }
-
- if (next) {
- if (node->value != NGX_RADIX_NO_VALUE) {
- return NGX_BUSY;
- }
-
- node->value = value;
- return NGX_OK;
- }
-
- while (bit & mask[i]) {
- next = ngx_radix_alloc(tree);
- if (next == NULL) {
- return NGX_ERROR;
- }
-
- next->right = NULL;
- next->left = NULL;
- next->parent = node;
- next->value = NGX_RADIX_NO_VALUE;
-
- if (key[i] & bit) {
- node->right = next;
-
- } else {
- node->left = next;
- }
-
- bit >>= 1;
- node = next;
-
- if (bit == 0) {
- if (++i == 16) {
- break;
- }
-
- bit = 0x80;
- }
- }
-
- node->value = value;
-
- return NGX_OK;
-}
-
-
-ngx_int_t
-ngx_radix128tree_delete(ngx_radix_tree_t *tree, u_char *key, u_char *mask)
-{
- u_char bit;
- ngx_uint_t i;
- ngx_radix_node_t *node;
-
- i = 0;
- bit = 0x80;
- node = tree->root;
-
- while (node && (bit & mask[i])) {
- if (key[i] & bit) {
- node = node->right;
-
- } else {
- node = node->left;
- }
-
- bit >>= 1;
-
- if (bit == 0) {
- if (++i == 16) {
- break;
- }
-
- bit = 0x80;
- }
- }
-
- if (node == NULL) {
- return NGX_ERROR;
- }
-
- if (node->right || node->left) {
- if (node->value != NGX_RADIX_NO_VALUE) {
- node->value = NGX_RADIX_NO_VALUE;
- return NGX_OK;
- }
-
- return NGX_ERROR;
- }
-
- for ( ;; ) {
- if (node->parent->right == node) {
- node->parent->right = NULL;
-
- } else {
- node->parent->left = NULL;
- }
-
- node->right = tree->free;
- tree->free = node;
-
- node = node->parent;
-
- if (node->right || node->left) {
- break;
- }
-
- if (node->value != NGX_RADIX_NO_VALUE) {
- break;
- }
-
- if (node->parent == NULL) {
- break;
- }
- }
-
- return NGX_OK;
-}
-
-
-uintptr_t
-ngx_radix128tree_find(ngx_radix_tree_t *tree, u_char *key)
-{
- u_char bit;
- uintptr_t value;
- ngx_uint_t i;
- ngx_radix_node_t *node;
-
- i = 0;
- bit = 0x80;
- value = NGX_RADIX_NO_VALUE;
- node = tree->root;
-
- while (node) {
- if (node->value != NGX_RADIX_NO_VALUE) {
- value = node->value;
- }
-
- if (key[i] & bit) {
- node = node->right;
-
- } else {
- node = node->left;
- }
-
- bit >>= 1;
-
- if (bit == 0) {
- i++;
- bit = 0x80;
- }
- }
-
- return value;
-}
-
-#endif
-
-
-static ngx_radix_node_t *
-ngx_radix_alloc(ngx_radix_tree_t *tree)
-{
- ngx_radix_node_t *p;
-
- if (tree->free) {
- p = tree->free;
- tree->free = tree->free->right;
- return p;
- }
-
- if (tree->size < sizeof(ngx_radix_node_t)) {
- tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_pagesize);
- if (tree->start == NULL) {
- return NULL;
- }
-
- tree->size = ngx_pagesize;
- }
-
- p = (ngx_radix_node_t *) tree->start;
- tree->start += sizeof(ngx_radix_node_t);
- tree->size -= sizeof(ngx_radix_node_t);
-
- return p;
-}