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, 488 insertions, 0 deletions
diff --git a/app/nginx/src/core/ngx_radix_tree.c b/app/nginx/src/core/ngx_radix_tree.c
new file mode 100644
index 0000000..c1d8737
--- /dev/null
+++ b/app/nginx/src/core/ngx_radix_tree.c
@@ -0,0 +1,488 @@
+
+/*
+ * 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;
+}