From 6a5411729539fe21117f406699a69974b320eb7e Mon Sep 17 00:00:00 2001 From: Yu Ping Date: Thu, 19 Mar 2020 03:34:52 +0800 Subject: remove nginx build directory Signed-off-by: Yu Ping Change-Id: I73aba722f06f4cc4be484e3d5f4631225d09de83 --- nginx/src/core/ngx_radix_tree.c | 488 ---------------------------------------- 1 file changed, 488 deletions(-) delete mode 100644 nginx/src/core/ngx_radix_tree.c (limited to 'nginx/src/core/ngx_radix_tree.c') diff --git a/nginx/src/core/ngx_radix_tree.c b/nginx/src/core/ngx_radix_tree.c deleted file mode 100644 index c1d8737..0000000 --- a/nginx/src/core/ngx_radix_tree.c +++ /dev/null @@ -1,488 +0,0 @@ - -/* - * Copyright (C) Igor Sysoev - * Copyright (C) Nginx, Inc. - */ - - -#include -#include - - -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; -} -- cgit 1.2.3-korg