Mercurial > hg > nginx

annotate src/core/ngx_rbtree.h @ 7682:2ab0ecfe5a5f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
release-1.19.1 tag
author Maxim Dounin <mdounin@mdounin.ru>
date Tue, 07 Jul 2020 18:56:06 +0300
parents e0cc454aafe4
children 0c5e84096d99
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);
6928
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 5894
diff changeset
57 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
58 ngx_rbtree_node_t *node);
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
59
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
60
1023
68cc5e2e1a5d make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents: 965
diff changeset
61 #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
62 #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
63 #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
64 #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
65 #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
66
68cc5e2e1a5d make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents: 965
diff changeset
67
965
2e3754f37606 a sentinel must be black
Igor Sysoev <igor@sysoev.ru>
parents: 861
diff changeset
68 /* a sentinel must be black */
2e3754f37606 a sentinel must be black
Igor Sysoev <igor@sysoev.ru>
parents: 861
diff changeset
69
1023
68cc5e2e1a5d make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents: 965
diff changeset
70 #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
71
2e3754f37606 a sentinel must be black
Igor Sysoev <igor@sysoev.ru>
parents: 861
diff changeset
72
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
73 static ngx_inline ngx_rbtree_node_t *
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
74 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
75 {
557
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
76 while (node->left != sentinel) {
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
77 node = node->left;
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
78 }
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
79
557
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
80 return node;
205
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
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
83
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
84 #endif /* _NGX_RBTREE_H_INCLUDED_ */