Mercurial > hg > nginx
view src/core/ngx_rbtree.c @ 7690:8253424d1aff
Added size check to ngx_http_alloc_large_header_buffer().
This ensures that copying won't write more than the buffer size
even if the buffer comes from hc->free and it is smaller than the large
client header buffer size in the virtual host configuration. This might
happen if size of large client header buffers is different in name-based
virtual hosts, similarly to the problem with number of buffers fixed
in 6926:e662cbf1b932.
author | Maxim Dounin <mdounin@mdounin.ru> |
---|---|
date | Thu, 06 Aug 2020 05:02:22 +0300 |
parents | 7fdcf308e0f0 |
children |
line wrap: on
line source
/* * Copyright (C) Igor Sysoev * Copyright (C) Nginx, Inc. */ #include <ngx_config.h> #include <ngx_core.h> /* * The red-black tree code is based on the algorithm described in * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest. */ static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node); static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node); void ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node) { ngx_rbtree_node_t **root, *temp, *sentinel; /* a binary tree insert */ root = &tree->root; sentinel = tree->sentinel; if (*root == sentinel) { node->parent = NULL; node->left = sentinel; node->right = sentinel; ngx_rbt_black(node); *root = node; return; } tree->insert(*root, node, sentinel); /* re-balance tree */ while (node != *root && ngx_rbt_is_red(node->parent)) { if (node->parent == node->parent->parent->left) { temp = node->parent->parent->right; if (ngx_rbt_is_red(temp)) { ngx_rbt_black(node->parent); ngx_rbt_black(temp); ngx_rbt_red(node->parent->parent); node = node->parent->parent; } else { if (node == node->parent->right) { node = node->parent; ngx_rbtree_left_rotate(root, sentinel, node); } ngx_rbt_black(node->parent); ngx_rbt_red(node->parent->parent); ngx_rbtree_right_rotate(root, sentinel, node->parent->parent); } } else { temp = node->parent->parent->left; if (ngx_rbt_is_red(temp)) { ngx_rbt_black(node->parent); ngx_rbt_black(temp); ngx_rbt_red(node->parent->parent); node = node->parent->parent; } else { if (node == node->parent->left) { node = node->parent; ngx_rbtree_right_rotate(root, sentinel, node); } ngx_rbt_black(node->parent); ngx_rbt_red(node->parent->parent); ngx_rbtree_left_rotate(root, sentinel, node->parent->parent); } } } ngx_rbt_black(*root); } void ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) { ngx_rbtree_node_t **p; for ( ;; ) { p = (node->key < temp->key) ? &temp->left : &temp->right; if (*p == sentinel) { break; } temp = *p; } *p = node; node->parent = temp; node->left = sentinel; node->right = sentinel; ngx_rbt_red(node); } void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) { ngx_rbtree_node_t **p; for ( ;; ) { /* * Timer values * 1) are spread in small range, usually several minutes, * 2) and overflow each 49 days, if milliseconds are stored in 32 bits. * The comparison takes into account that overflow. */ /* node->key < temp->key */ p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0) ? &temp->left : &temp->right; if (*p == sentinel) { break; } temp = *p; } *p = node; node->parent = temp; node->left = sentinel; node->right = sentinel; ngx_rbt_red(node); } void ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node) { ngx_uint_t red; ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; /* a binary tree delete */ root = &tree->root; sentinel = tree->sentinel; if (node->left == sentinel) { temp = node->right; subst = node; } else if (node->right == sentinel) { temp = node->left; subst = node; } else { subst = ngx_rbtree_min(node->right, sentinel); temp = subst->right; } if (subst == *root) { *root = temp; ngx_rbt_black(temp); /* DEBUG stuff */ node->left = NULL; node->right = NULL; node->parent = NULL; node->key = 0; return; } red = ngx_rbt_is_red(subst); if (subst == subst->parent->left) { subst->parent->left = temp; } else { subst->parent->right = temp; } if (subst == node) { temp->parent = subst->parent; } else { if (subst->parent == node) { temp->parent = subst; } else { temp->parent = subst->parent; } subst->left = node->left; subst->right = node->right; subst->parent = node->parent; ngx_rbt_copy_color(subst, node); if (node == *root) { *root = subst; } else { if (node == node->parent->left) { node->parent->left = subst; } else { node->parent->right = subst; } } if (subst->left != sentinel) { subst->left->parent = subst; } if (subst->right != sentinel) { subst->right->parent = subst; } } /* DEBUG stuff */ node->left = NULL; node->right = NULL; node->parent = NULL; node->key = 0; if (red) { return; } /* a delete fixup */ while (temp != *root && ngx_rbt_is_black(temp)) { if (temp == temp->parent->left) { w = temp->parent->right; if (ngx_rbt_is_red(w)) { ngx_rbt_black(w); ngx_rbt_red(temp->parent); ngx_rbtree_left_rotate(root, sentinel, temp->parent); w = temp->parent->right; } if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) { ngx_rbt_red(w); temp = temp->parent; } else { if (ngx_rbt_is_black(w->right)) { ngx_rbt_black(w->left); ngx_rbt_red(w); ngx_rbtree_right_rotate(root, sentinel, w); w = temp->parent->right; } ngx_rbt_copy_color(w, temp->parent); ngx_rbt_black(temp->parent); ngx_rbt_black(w->right); ngx_rbtree_left_rotate(root, sentinel, temp->parent); temp = *root; } } else { w = temp->parent->left; if (ngx_rbt_is_red(w)) { ngx_rbt_black(w); ngx_rbt_red(temp->parent); ngx_rbtree_right_rotate(root, sentinel, temp->parent); w = temp->parent->left; } if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) { ngx_rbt_red(w); temp = temp->parent; } else { if (ngx_rbt_is_black(w->left)) { ngx_rbt_black(w->right); ngx_rbt_red(w); ngx_rbtree_left_rotate(root, sentinel, w); w = temp->parent->left; } ngx_rbt_copy_color(w, temp->parent); ngx_rbt_black(temp->parent); ngx_rbt_black(w->left); ngx_rbtree_right_rotate(root, sentinel, temp->parent); temp = *root; } } } ngx_rbt_black(temp); } static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node) { ngx_rbtree_node_t *temp; temp = node->right; node->right = temp->left; if (temp->left != sentinel) { temp->left->parent = node; } temp->parent = node->parent; if (node == *root) { *root = temp; } else if (node == node->parent->left) { node->parent->left = temp; } else { node->parent->right = temp; } temp->left = node; node->parent = temp; } static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node) { ngx_rbtree_node_t *temp; temp = node->left; node->left = temp->right; if (temp->right != sentinel) { temp->right->parent = node; } temp->parent = node->parent; if (node == *root) { *root = temp; } else if (node == node->parent->right) { node->parent->right = temp; } else { node->parent->left = temp; } temp->right = node; node->parent = temp; } ngx_rbtree_node_t * ngx_rbtree_next(ngx_rbtree_t *tree, ngx_rbtree_node_t *node) { ngx_rbtree_node_t *root, *sentinel, *parent; sentinel = tree->sentinel; if (node->right != sentinel) { return ngx_rbtree_min(node->right, sentinel); } root = tree->root; for ( ;; ) { parent = node->parent; if (node == root) { return NULL; } if (node == parent->left) { return parent; } node = parent; } }