Mercurial > hg > nginx

annotate src/core/ngx_rbtree.h @ 6741:79ac653ae2d0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Version bump.
author Ruslan Ermilov <ru@nginx.com>
date Thu, 13 Oct 2016 15:35:48 +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_ */