Mercurial > hg > nginx

annotate src/core/ngx_rbtree.h @ 1686:33c2e3c6f02c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ngx_rbtree_init()
author Igor Sysoev <igor@sysoev.ru>
date Mon, 03 Dec 2007 12:17:15 +0000
parents 68cc5e2e1a5d
children d620f497c50f
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
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
4 */
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
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
7 #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
8 #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
9
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 #include <ngx_config.h>
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
12 #include <ngx_core.h>
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
13
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
14
557
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
15 typedef ngx_uint_t ngx_rbtree_key_t;
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
16 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
17
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
18
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
19 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
20
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
21 struct ngx_rbtree_node_s {
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
22 ngx_rbtree_key_t key;
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
23 ngx_rbtree_node_t *left;
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
24 ngx_rbtree_node_t *right;
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
25 ngx_rbtree_node_t *parent;
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 826
diff changeset
26 u_char color;
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 826
diff changeset
27 u_char data;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
28 };
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
29
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
30
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
31 typedef struct ngx_rbtree_s ngx_rbtree_t;
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
32
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 826
diff changeset
33 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
34 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
35
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
36 struct ngx_rbtree_s {
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
37 ngx_rbtree_node_t *root;
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
38 ngx_rbtree_node_t *sentinel;
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 826
diff changeset
39 ngx_rbtree_insert_pt insert;
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
40 };
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
41
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
42
1686
33c2e3c6f02c ngx_rbtree_init()
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
43 #define ngx_rbtree_init(tree, s, i) \
33c2e3c6f02c ngx_rbtree_init()
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
44 ngx_rbtree_sentinel_init(s); \
33c2e3c6f02c ngx_rbtree_init()
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
45 (tree)->root = s; \
33c2e3c6f02c ngx_rbtree_init()
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
46 (tree)->sentinel = s; \
33c2e3c6f02c ngx_rbtree_init()
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
47 (tree)->insert = i
33c2e3c6f02c ngx_rbtree_init()
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
48
33c2e3c6f02c ngx_rbtree_init()
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
49
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
50 void ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree,
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
51 ngx_rbtree_node_t *node);
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
52 void ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree,
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
53 ngx_rbtree_node_t *node);
861
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
54 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
55 ngx_rbtree_node_t *sentinel);
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 826
diff changeset
56 void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root,
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 826
diff changeset
57 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
58
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
59
1023
68cc5e2e1a5d make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents: 965
diff changeset
60 #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
61 #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
62 #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
63 #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
64 #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
65
68cc5e2e1a5d make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents: 965
diff changeset
66
965
2e3754f37606 a sentinel must be black
Igor Sysoev <igor@sysoev.ru>
parents: 861
diff changeset
67 /* a sentinel must be black */
2e3754f37606 a sentinel must be black
Igor Sysoev <igor@sysoev.ru>
parents: 861
diff changeset
68
1023
68cc5e2e1a5d make global the rbtree color handling macros
Igor Sysoev <igor@sysoev.ru>
parents: 965
diff changeset
69 #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
70
2e3754f37606 a sentinel must be black
Igor Sysoev <igor@sysoev.ru>
parents: 861
diff changeset
71
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
72 static ngx_inline ngx_rbtree_node_t *
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
73 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
74 {
557
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
75 while (node->left != sentinel) {
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
76 node = node->left;
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
77 }
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
78
557
ecd9c160f25b nginx-0.3.0-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 493
diff changeset
79 return node;
205
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
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
83 #endif /* _NGX_RBTREE_H_INCLUDED_ */