annotate src/core/ngx_rbtree.h @ 506:b9fdcaf2062b NGINX_0_7_65

nginx 0.7.65 *) Security: now nginx/Windows ignores trailing spaces in URI. Thanks to Dan Crowley, Core Security Technologies. *) Security: now nginx/Windows ignores short files names. Thanks to Dan Crowley, Core Security Technologies. *) Change: now the "009" status code is written to an access log for proxied HTTP/0.9 responses. *) Change: now the default buffer size of the "large_client_header_buffers" directive is 8K. Thanks to Andrew Cholakian. *) Change: now default SSL ciphers are "HIGH:!ADH:!MD5". *) Change: now SSLv2 protocol is disabled by default. *) Change: now $host variable value is always low case. *) Feature: the conf/fastcgi.conf for simple FastCGI configurations. *) Feature: now URI part is not required a "proxy_pass" directive if variables are used. *) Feature: the $ssl_session_id variable. *) Bugfix: if a proxied or FastCGI request was internally redirected to another proxied or FastCGI location, then $upstream_response_time variable may have abnormally large value; the bug had appeared in 0.7.63. *) Bugfix: if the "expires modified" set date in the past, then a negative number was set in the "Cache-Control" response header line. Thanks to Alex Kapranoff. *) Bugfix: nginx closed a connection if a cached response had an empty body. Thanks to Piotr Sikora. *) Bugfix: nginx cached a 304 response if there was the "If-None-Match" header line in a proxied request. Thanks to Tim Dettrick and David Kostal. *) Bugfix: nginx did not treat a comma as separator in the "Cache-Control" backend response header line. *) Bugfix: cached HTTP/0.9 responses were handled incorrectly. *) Bugfix: nginx sent gzipped responses to clients those do not support gzip, if "gzip_static on" and "gzip_vary off"; the bug had appeared in 0.8.16. *) Bugfix: nginx always added "Content-Encoding: gzip" response header line in 304 responses sent by ngx_http_gzip_static_module. *) Bugfix: the "!-x" operator did not work. Thanks to Maxim Dounin. *) Bugfix: a segmentation fault might occur in a worker process, if limit_rate was used in HTTPS server. Thanks to Maxim Dounin. *) Bugfix: a segmentation fault might occur in a worker process while $limit_rate logging. Thanks to Maxim Dounin. *) Bugfix: nginx did not support dates in 2038 year on 32-bit platforms; *) Bugfix: nginx/Windows tried to delete a temporary file twice if the file should replace an already existent file. *) Bugfix: nginx/Windows tried to rename a temporary file twice if the file should replace an already existent file. *) Bugfix: nginx/Windows might not create temporary file, a cache file, or "proxy/fastcgi_store"d file if a worker had no enough access rights for top level directories. *) Bugfix: in UTF-8 encoding support by "try_files" directive in nginx/Windows. *) Bugfix: UTF-8 encoding usage in the ngx_http_autoindex_module. Thanks to Maxim Dounin. *) Bugfix: the ngx_http_autoindex_module did not show the trailing slash in links to a directory; the bug had appeared in 0.7.15. *) Bugfix: nginx did not close a log file set by the --error-log-path configuration option; the bug had appeared in 0.7.53. *) Bugfix: "addition_types" directive was incorrectly named "addtion_types". *) Bugfix: invalid request line in $request variable was written in access_log only if error_log was set to "info" or "debug" level.
author Igor Sysoev <http://sysoev.ru>
date Mon, 01 Feb 2010 00:00:00 +0000
parents 583decdb82a4
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
1
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
2 /*
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
3 * Copyright (C) Igor Sysoev
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
4 */
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
5
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
6
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
7 #ifndef _NGX_RBTREE_H_INCLUDED_
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
8 #define _NGX_RBTREE_H_INCLUDED_
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
9
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
10
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
11 #include <ngx_config.h>
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
12 #include <ngx_core.h>
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
13
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
14
106
45f7329b4bd0 nginx 0.3.0
Igor Sysoev <http://sysoev.ru>
parents: 42
diff changeset
15 typedef ngx_uint_t ngx_rbtree_key_t;
45f7329b4bd0 nginx 0.3.0
Igor Sysoev <http://sysoev.ru>
parents: 42
diff changeset
16 typedef ngx_int_t ngx_rbtree_key_int_t;
45f7329b4bd0 nginx 0.3.0
Igor Sysoev <http://sysoev.ru>
parents: 42
diff changeset
17
45f7329b4bd0 nginx 0.3.0
Igor Sysoev <http://sysoev.ru>
parents: 42
diff changeset
18
108
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
19 typedef struct ngx_rbtree_node_s ngx_rbtree_node_t;
0
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
20
108
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
21 struct ngx_rbtree_node_s {
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
22 ngx_rbtree_key_t key;
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
23 ngx_rbtree_node_t *left;
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
24 ngx_rbtree_node_t *right;
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
25 ngx_rbtree_node_t *parent;
258
6ae1357b7b7c nginx 0.4.14
Igor Sysoev <http://sysoev.ru>
parents: 132
diff changeset
26 u_char color;
6ae1357b7b7c nginx 0.4.14
Igor Sysoev <http://sysoev.ru>
parents: 132
diff changeset
27 u_char data;
0
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
28 };
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
29
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
30
108
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
31 typedef struct ngx_rbtree_s ngx_rbtree_t;
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
32
258
6ae1357b7b7c nginx 0.4.14
Igor Sysoev <http://sysoev.ru>
parents: 132
diff changeset
33 typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
108
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
34 ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
35
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
36 struct ngx_rbtree_s {
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
37 ngx_rbtree_node_t *root;
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
38 ngx_rbtree_node_t *sentinel;
258
6ae1357b7b7c nginx 0.4.14
Igor Sysoev <http://sysoev.ru>
parents: 132
diff changeset
39 ngx_rbtree_insert_pt insert;
108
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
40 };
0
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
41
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
42
354
583decdb82a4 nginx 0.6.21
Igor Sysoev <http://sysoev.ru>
parents: 274
diff changeset
43 #define ngx_rbtree_init(tree, s, i) \
583decdb82a4 nginx 0.6.21
Igor Sysoev <http://sysoev.ru>
parents: 274
diff changeset
44 ngx_rbtree_sentinel_init(s); \
583decdb82a4 nginx 0.6.21
Igor Sysoev <http://sysoev.ru>
parents: 274
diff changeset
45 (tree)->root = s; \
583decdb82a4 nginx 0.6.21
Igor Sysoev <http://sysoev.ru>
parents: 274
diff changeset
46 (tree)->sentinel = s; \
583decdb82a4 nginx 0.6.21
Igor Sysoev <http://sysoev.ru>
parents: 274
diff changeset
47 (tree)->insert = i
583decdb82a4 nginx 0.6.21
Igor Sysoev <http://sysoev.ru>
parents: 274
diff changeset
48
583decdb82a4 nginx 0.6.21
Igor Sysoev <http://sysoev.ru>
parents: 274
diff changeset
49
108
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
50 void ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree,
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
51 ngx_rbtree_node_t *node);
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
52 void ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree,
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
53 ngx_rbtree_node_t *node);
258
6ae1357b7b7c nginx 0.4.14
Igor Sysoev <http://sysoev.ru>
parents: 132
diff changeset
54 void ngx_rbtree_insert_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node,
6ae1357b7b7c nginx 0.4.14
Igor Sysoev <http://sysoev.ru>
parents: 132
diff changeset
55 ngx_rbtree_node_t *sentinel);
6ae1357b7b7c nginx 0.4.14
Igor Sysoev <http://sysoev.ru>
parents: 132
diff changeset
56 void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root,
6ae1357b7b7c nginx 0.4.14
Igor Sysoev <http://sysoev.ru>
parents: 132
diff changeset
57 ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
108
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
58
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
59
274
052a7b1d40e5 nginx 0.5.7
Igor Sysoev <http://sysoev.ru>
parents: 272
diff changeset
60 #define ngx_rbt_red(node) ((node)->color = 1)
052a7b1d40e5 nginx 0.5.7
Igor Sysoev <http://sysoev.ru>
parents: 272
diff changeset
61 #define ngx_rbt_black(node) ((node)->color = 0)
052a7b1d40e5 nginx 0.5.7
Igor Sysoev <http://sysoev.ru>
parents: 272
diff changeset
62 #define ngx_rbt_is_red(node) ((node)->color)
052a7b1d40e5 nginx 0.5.7
Igor Sysoev <http://sysoev.ru>
parents: 272
diff changeset
63 #define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node))
052a7b1d40e5 nginx 0.5.7
Igor Sysoev <http://sysoev.ru>
parents: 272
diff changeset
64 #define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color)
052a7b1d40e5 nginx 0.5.7
Igor Sysoev <http://sysoev.ru>
parents: 272
diff changeset
65
052a7b1d40e5 nginx 0.5.7
Igor Sysoev <http://sysoev.ru>
parents: 272
diff changeset
66
272
29a6403156b0 nginx 0.5.6
Igor Sysoev <http://sysoev.ru>
parents: 258
diff changeset
67 /* a sentinel must be black */
29a6403156b0 nginx 0.5.6
Igor Sysoev <http://sysoev.ru>
parents: 258
diff changeset
68
274
052a7b1d40e5 nginx 0.5.7
Igor Sysoev <http://sysoev.ru>
parents: 272
diff changeset
69 #define ngx_rbtree_sentinel_init(node) ngx_rbt_black(node)
272
29a6403156b0 nginx 0.5.6
Igor Sysoev <http://sysoev.ru>
parents: 258
diff changeset
70
29a6403156b0 nginx 0.5.6
Igor Sysoev <http://sysoev.ru>
parents: 258
diff changeset
71
108
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
72 static ngx_inline ngx_rbtree_node_t *
cf3d6edb3ad6 nginx 0.3.1
Igor Sysoev <http://sysoev.ru>
parents: 106
diff changeset
73 ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
0
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
74 {
106
45f7329b4bd0 nginx 0.3.0
Igor Sysoev <http://sysoev.ru>
parents: 42
diff changeset
75 while (node->left != sentinel) {
45f7329b4bd0 nginx 0.3.0
Igor Sysoev <http://sysoev.ru>
parents: 42
diff changeset
76 node = node->left;
45f7329b4bd0 nginx 0.3.0
Igor Sysoev <http://sysoev.ru>
parents: 42
diff changeset
77 }
0
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
78
106
45f7329b4bd0 nginx 0.3.0
Igor Sysoev <http://sysoev.ru>
parents: 42
diff changeset
79 return node;
0
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
80 }
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
81
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
82
f0b350454894 nginx 0.1.0
Igor Sysoev <http://sysoev.ru>
parents:
diff changeset
83 #endif /* _NGX_RBTREE_H_INCLUDED_ */