From 1bfa7bc78a23c0150e0bbf854e778dba4df30031 Mon Sep 17 00:00:00 2001 From: Igor Sysoev Date: Mon, 10 Oct 2005 12:59:41 +0000 Subject: nginx-0.3.1-RELEASE import *) Bugfix: the segmentation fault occurred when the signal queue overflowed if the "rtsig" method was used; the bug had appeared in 0.2.0. *) Change: correct handling of the "\\", "\"", "\'", and "\$" pairs in SSI. --- src/core/nginx.h | 2 +- src/core/ngx_core.h | 4 ++-- src/core/ngx_rbtree.c | 55 +++++++++++++++++++++++++++++++++------------------ src/core/ngx_rbtree.h | 34 ++++++++++++++++++++----------- 4 files changed, 62 insertions(+), 33 deletions(-) (limited to 'src/core') diff --git a/src/core/nginx.h b/src/core/nginx.h index 734c4016f..22c632ff3 100644 --- a/src/core/nginx.h +++ b/src/core/nginx.h @@ -8,7 +8,7 @@ #define _NGINX_H_INCLUDED_ -#define NGINX_VER "nginx/0.3.0" +#define NGINX_VER "nginx/0.3.1" #define NGINX_VAR "NGINX" #define NGX_OLDPID_EXT ".oldbin" diff --git a/src/core/ngx_core.h b/src/core/ngx_core.h index 27058bfc2..9efbecd4d 100644 --- a/src/core/ngx_core.h +++ b/src/core/ngx_core.h @@ -35,15 +35,15 @@ typedef void (*ngx_connection_handler_pt)(ngx_connection_t *c); #define NGX_ABORT -6 +#include #include +#include #include #include #include -#include #include #include #include -#include #include #include #include diff --git a/src/core/ngx_rbtree.c b/src/core/ngx_rbtree.c index 1ebc56a3b..3c42be402 100644 --- a/src/core/ngx_rbtree.c +++ b/src/core/ngx_rbtree.c @@ -9,8 +9,8 @@ /* - * The code is based on the algorithm described in the "Introduction - * to Algorithms" by Cormen, Leiserson and Rivest. + * The red-black tree code is based on the algorithm described in + * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest. */ #define ngx_rbt_red(node) ((node)->color = 1) @@ -20,20 +20,23 @@ #define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color) -static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, - ngx_rbtree_t *sentinel, ngx_rbtree_t *node); -static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, - ngx_rbtree_t *sentinel, ngx_rbtree_t *node); +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 **root, ngx_rbtree_t *sentinel, - ngx_rbtree_t *node) +ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree, + ngx_rbtree_node_t *node) { - ngx_rbtree_t *temp; + ngx_rbtree_node_t **root, *temp, *sentinel; /* a binary tree insert */ + root = (ngx_rbtree_node_t **) &tree->root; + sentinel = tree->sentinel; + if (*root == sentinel) { node->parent = NULL; node->left = sentinel; @@ -44,6 +47,17 @@ ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, return; } + /* + * The rbtree is currently used by event timers only. 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 below comparison takes into account that overflow. + * + * If there will be a necessity to use the rbtree for values with + * other comparison rules, then a whole "for ( ;; )" loop should + * be made as tree->insert() function. + */ + temp = *root; for ( ;; ) { @@ -130,14 +144,17 @@ ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, void -ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, - ngx_rbtree_t *node) +ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, + ngx_rbtree_node_t *node) { - ngx_int_t is_red; - ngx_rbtree_t *subst, *temp, *w; + ngx_int_t is_red; + ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; /* a binary tree delete */ + root = (ngx_rbtree_node_t **) &tree->root; + sentinel = tree->sentinel; + if (node->left == sentinel) { temp = node->right; subst = node; @@ -295,10 +312,10 @@ ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, static ngx_inline void -ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, - ngx_rbtree_t *node) +ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, + ngx_rbtree_node_t *node) { - ngx_rbtree_t *temp; + ngx_rbtree_node_t *temp; temp = node->right; node->right = temp->left; @@ -325,10 +342,10 @@ ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, static ngx_inline void -ngx_rbtree_right_rotate(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, - ngx_rbtree_t *node) +ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, + ngx_rbtree_node_t *node) { - ngx_rbtree_t *temp; + ngx_rbtree_node_t *temp; temp = node->left; node->left = temp->right; diff --git a/src/core/ngx_rbtree.h b/src/core/ngx_rbtree.h index d6803f912..1b1322d3c 100644 --- a/src/core/ngx_rbtree.h +++ b/src/core/ngx_rbtree.h @@ -16,25 +16,37 @@ typedef ngx_uint_t ngx_rbtree_key_t; typedef ngx_int_t ngx_rbtree_key_int_t; +typedef struct ngx_rbtree_node_s ngx_rbtree_node_t; + +struct ngx_rbtree_node_s { + ngx_rbtree_key_t key; + ngx_rbtree_node_t *left; + ngx_rbtree_node_t *right; + ngx_rbtree_node_t *parent; + char color; +}; + + typedef struct ngx_rbtree_s ngx_rbtree_t; +typedef ngx_rbtree_t *(*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root, + ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel); + struct ngx_rbtree_s { - ngx_rbtree_key_t key; - ngx_rbtree_t *left; - ngx_rbtree_t *right; - ngx_rbtree_t *parent; - char color; + ngx_rbtree_node_t *root; + ngx_rbtree_node_t *sentinel; + /* ngx_rbtree_insert_pt insert; */ }; -void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, - ngx_rbtree_t *node); -void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, - ngx_rbtree_t *node); +void ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree, + ngx_rbtree_node_t *node); +void ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, + ngx_rbtree_node_t *node); -static ngx_inline ngx_rbtree_t * -ngx_rbtree_min(ngx_rbtree_t *node, ngx_rbtree_t *sentinel) +static ngx_inline ngx_rbtree_node_t * +ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) { while (node->left != sentinel) { node = node->left; -- cgit v1.2.3