Mercurial > hg > nginx

annotate src/core/ngx_rbtree.h @ 6862:abb0a4189cf7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Win32: compatiblity with OpenSSL 1.1.0. OpenSSL 1.1.0 now uses normal "nmake; nmake install" instead of using custom "ms\do_ms.bat" script and "ms\nt.mak" makefile. And Configure now requires --prefix to be absolute, and no longer derives --openssldir from prefix (so it's specified explicitly). Generated libraries are now called "libcrypto.lib" and "libssl.lib" instead of "libeay32.lib" and "ssleay32.lib". Appropriate tests added to support both old and new variants. Additionally, openssl/lhash.h now triggers warning C4090 ('function' : different 'const' qualifiers), so the warning was disabled.
author Maxim Dounin <mdounin@mdounin.ru>
date Sat, 24 Dec 2016 18:01:14 +0300
parents 1f513d7f1b45
children e0cc454aafe4
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
441
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 209
diff changeset
1
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 209
diff changeset
2 /*
444
42d11f017717 nginx-0.1.0-2004-09-29-20:00:49 import; remove years from copyright
Igor Sysoev <igor@sysoev.ru>
parents: 441
diff changeset
3 * Copyright (C) Igor Sysoev
4412
d620f497c50f Copyright updated.
Maxim Konovalov <maxim@nginx.com>
parents: 1686
diff changeset
4 * Copyright (C) Nginx, Inc.
441
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 209
diff changeset
5 */
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 209
diff changeset
6
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 209
diff changeset
7
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
8 #ifndef _NGX_RBTREE_H_INCLUDED_
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
9 #define _NGX_RBTREE_H_INCLUDED_
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
10
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
11
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
12 #include <ngx_config.h>
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
13 #include <ngx_core.h>
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
14
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
15
557
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
16 typedef ngx_uint_t ngx_rbtree_key_t;
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
17 typedef ngx_int_t ngx_rbtree_key_int_t;
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
18
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
19
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
20 typedef struct ngx_rbtree_node_s ngx_rbtree_node_t;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
21
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
22 struct ngx_rbtree_node_s {
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
23 ngx_rbtree_key_t key;
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
24 ngx_rbtree_node_t *left;
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
25 ngx_rbtree_node_t *right;
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
26 ngx_rbtree_node_t *parent;
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 826
diff changeset
27 u_char color;
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 826
diff changeset
28 u_char data;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
29 };
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
30
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
31
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
32 typedef struct ngx_rbtree_s ngx_rbtree_t;
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
33
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 826
diff changeset
34 typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
35 ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
36
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
37 struct ngx_rbtree_s {
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
38 ngx_rbtree_node_t *root;
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
39 ngx_rbtree_node_t *sentinel;
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 826
diff changeset
40 ngx_rbtree_insert_pt insert;
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
41 };
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
42
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
43
1686
33c2e3c6f02c ngx_rbtree_init()
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
44 #define ngx_rbtree_init(tree, s, i) \
33c2e3c6f02c ngx_rbtree_init()
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
45 ngx_rbtree_sentinel_init(s); \
33c2e3c6f02c ngx_rbtree_init()
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
46 (tree)->root = s; \
33c2e3c6f02c ngx_rbtree_init()
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
47 (tree)->sentinel = s; \
33c2e3c6f02c ngx_rbtree_init()
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
48 (tree)->insert = i
33c2e3c6f02c ngx_rbtree_init()
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
49
33c2e3c6f02c ngx_rbtree_init()
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
50
5894
1f513d7f1b45 Events: removed broken thread support from event timers.
Valentin Bartenev <vbart@nginx.com>
parents: 4412
diff changeset
51 void ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
1f513d7f1b45 Events: removed broken thread support from event timers.
Valentin Bartenev <vbart@nginx.com>
parents: 4412
diff changeset
52 void ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
861
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
53 void ngx_rbtree_insert_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node,
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
54 ngx_rbtree_node_t *sentinel);
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 826
diff changeset
55 void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root,
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 826
diff changeset
56 ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
57
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
58
1023
68cc5e2e1a5d make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents: 965
diff changeset
59 #define ngx_rbt_red(node) ((node)->color = 1)
68cc5e2e1a5d make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents: 965
diff changeset
60 #define ngx_rbt_black(node) ((node)->color = 0)
68cc5e2e1a5d make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents: 965
diff changeset
61 #define ngx_rbt_is_red(node) ((node)->color)
68cc5e2e1a5d make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents: 965
diff changeset
62 #define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node))
68cc5e2e1a5d make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents: 965
diff changeset
63 #define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color)
68cc5e2e1a5d make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents: 965
diff changeset
64
68cc5e2e1a5d make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents: 965
diff changeset
65
965
2e3754f37606 a sentinel must be black
Igor Sysoev <igor@sysoev.ru>
parents: 861
diff changeset
66 /* a sentinel must be black */
2e3754f37606 a sentinel must be black
Igor Sysoev <igor@sysoev.ru>
parents: 861
diff changeset
67
1023
68cc5e2e1a5d make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents: 965
diff changeset
68 #define ngx_rbtree_sentinel_init(node) ngx_rbt_black(node)
965
2e3754f37606 a sentinel must be black
Igor Sysoev <igor@sysoev.ru>
parents: 861
diff changeset
69
2e3754f37606 a sentinel must be black
Igor Sysoev <igor@sysoev.ru>
parents: 861
diff changeset
70
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
71 static ngx_inline ngx_rbtree_node_t *
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
72 ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
73 {
557
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
74 while (node->left != sentinel) {
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
75 node = node->left;
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
76 }
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
77
557
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
78 return node;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
79 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
80
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
81
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
82 #endif /* _NGX_RBTREE_H_INCLUDED_ */