Mercurial > hg > nginx
annotate src/core/ngx_rbtree.h @ 7981:0b5f12d5c531
PCRE2 library support.
The PCRE2 library is now used by default if found, instead of the
original PCRE library. If needed for some reason, this can be disabled
with the --without-pcre2 configure option.
To make it possible to specify paths to the library and include files
via --with-cc-opt / --with-ld-opt, the library is first tested without
any additional paths and options. If this fails, the pcre2-config script
is used.
Similarly to the original PCRE library, it is now possible to build PCRE2
from sources with nginx configure, by using the --with-pcre= option.
It automatically detects if PCRE or PCRE2 sources are provided.
Note that compiling PCRE2 10.33 and later requires inttypes.h. When
compiling on Windows with MSVC, inttypes.h is only available starting
with MSVC 2013. In older versions some replacement needs to be provided
("echo '#include <stdint.h>' > pcre2-10.xx/src/inttypes.h" is good enough
for MSVC 2010).
The interface on nginx side remains unchanged.
| author | Maxim Dounin <mdounin@mdounin.ru> |
|---|---|
| date | Sat, 25 Dec 2021 01:07:15 +0300 |
| parents | 0c5e84096d99 |
| children |
| 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 | 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 | 16 typedef ngx_uint_t ngx_rbtree_key_t; |
| 17 typedef ngx_int_t ngx_rbtree_key_int_t; | |
| 18 | |
| 19 | |
| 559 | 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 | 22 struct ngx_rbtree_node_s { |
| 23 ngx_rbtree_key_t key; | |
| 24 ngx_rbtree_node_t *left; | |
| 25 ngx_rbtree_node_t *right; | |
| 26 ngx_rbtree_node_t *parent; | |
| 853 | 27 u_char color; |
| 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 | 32 typedef struct ngx_rbtree_s ngx_rbtree_t; |
| 33 | |
| 853 | 34 typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root, |
| 559 | 35 ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel); |
| 36 | |
| 37 struct ngx_rbtree_s { | |
| 38 ngx_rbtree_node_t *root; | |
| 39 ngx_rbtree_node_t *sentinel; | |
| 853 | 40 ngx_rbtree_insert_pt insert; |
| 559 | 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 | 44 #define ngx_rbtree_init(tree, s, i) \ |
| 45 ngx_rbtree_sentinel_init(s); \ | |
| 46 (tree)->root = s; \ | |
| 47 (tree)->sentinel = s; \ | |
| 48 (tree)->insert = i | |
| 49 | |
|
7875
0c5e84096d99
Core: added the ngx_rbtree_data() macro.
Vladimir Homutov <vl@nginx.com>
parents:
6928
diff
changeset
|
50 #define ngx_rbtree_data(node, type, link) \ |
|
0c5e84096d99
Core: added the ngx_rbtree_data() macro.
Vladimir Homutov <vl@nginx.com>
parents:
6928
diff
changeset
|
51 (type *) ((u_char *) (node) - offsetof(type, link)) |
|
0c5e84096d99
Core: added the ngx_rbtree_data() macro.
Vladimir Homutov <vl@nginx.com>
parents:
6928
diff
changeset
|
52 |
| 1686 | 53 |
|
5894
1f513d7f1b45
Events: removed broken thread support from event timers.
Valentin Bartenev <vbart@nginx.com>
parents:
4412
diff
changeset
|
54 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
|
55 void ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node); |
| 861 | 56 void ngx_rbtree_insert_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node, |
| 57 ngx_rbtree_node_t *sentinel); | |
| 853 | 58 void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root, |
| 59 ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel); | |
|
6928
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
5894
diff
changeset
|
60 ngx_rbtree_node_t *ngx_rbtree_next(ngx_rbtree_t *tree, |
|
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
5894
diff
changeset
|
61 ngx_rbtree_node_t *node); |
| 559 | 62 |
| 63 | |
|
1023
68cc5e2e1a5d
make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents:
965
diff
changeset
|
64 #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
|
65 #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
|
66 #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
|
67 #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
|
68 #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
|
69 |
|
68cc5e2e1a5d
make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents:
965
diff
changeset
|
70 |
| 965 | 71 /* a sentinel must be black */ |
| 72 | |
|
1023
68cc5e2e1a5d
make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents:
965
diff
changeset
|
73 #define ngx_rbtree_sentinel_init(node) ngx_rbt_black(node) |
| 965 | 74 |
| 75 | |
| 559 | 76 static ngx_inline ngx_rbtree_node_t * |
| 77 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
|
78 { |
| 557 | 79 while (node->left != sentinel) { |
| 80 node = node->left; | |
| 81 } | |
|
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
82 |
| 557 | 83 return node; |
|
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
84 } |
|
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
85 |
|
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
86 |
|
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
87 #endif /* _NGX_RBTREE_H_INCLUDED_ */ |