Commit | Line | Data |
---|---|---|
6eb42155 ADB |
1 | /* |
2 | * blktrace output analysis: generate a timeline & gather statistics | |
3 | * | |
4 | * Copyright (C) 2006 Alan D. Brunelle <Alan.Brunelle@hp.com> | |
5 | * | |
6 | * This program is free software; you can redistribute it and/or modify | |
7 | * it under the terms of the GNU General Public License as published by | |
8 | * the Free Software Foundation; either version 2 of the License, or | |
9 | * (at your option) any later version. | |
10 | * | |
11 | * This program is distributed in the hope that it will be useful, | |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | * GNU General Public License for more details. | |
15 | * | |
16 | * You should have received a copy of the GNU General Public License | |
17 | * along with this program; if not, write to the Free Software | |
18 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
19 | * | |
20 | */ | |
21 | #include <stdio.h> | |
22 | #include "globals.h" | |
23 | ||
095181f2 | 24 | int rb_insert(struct rb_root *root, struct io *iop) |
6eb42155 ADB |
25 | { |
26 | struct io *__iop; | |
27 | struct rb_node *parent = NULL; | |
28 | struct rb_node **p = &root->rb_node; | |
29 | __u64 __s, s = BIT_START(iop); | |
30 | ||
6eb42155 ADB |
31 | while (*p) { |
32 | parent = *p; | |
33 | __iop = rb_entry(parent, struct io, rb_node); | |
34 | __s = BIT_START(__iop); | |
35 | ||
36 | if (s < __s) | |
37 | p = &(*p)->rb_left; | |
38 | else if (s > __s) | |
39 | p = &(*p)->rb_right; | |
1200fd07 JK |
40 | else { |
41 | rb_replace_node(parent, &iop->rb_node, root); | |
42 | return 1; | |
43 | } | |
6eb42155 ADB |
44 | } |
45 | ||
46 | rb_link_node(&iop->rb_node, parent, p); | |
47 | rb_insert_color(&iop->rb_node, root); | |
095181f2 | 48 | return 1; |
6eb42155 ADB |
49 | } |
50 | ||
51 | struct io *rb_find_sec(struct rb_root *root, __u64 sec) | |
52 | { | |
53 | struct io *__iop; | |
54 | struct rb_node *n = root->rb_node; | |
55 | ||
56 | while (n) { | |
57 | __iop = rb_entry(n, struct io, rb_node); | |
58 | if (sec < BIT_START(__iop)) | |
59 | n = n->rb_left; | |
60 | else if (sec >= BIT_END(__iop)) | |
61 | n = n->rb_right; | |
62 | else | |
63 | return __iop; | |
64 | } | |
65 | ||
66 | return NULL; | |
67 | } | |
68 | ||
8b10aae0 | 69 | void rb_foreach(struct rb_node *n, struct io *iop, |
6eb42155 ADB |
70 | void (*fnc)(struct io *iop, struct io *this), |
71 | struct list_head *head) | |
72 | { | |
73 | if (n) { | |
74 | struct io *this = rb_entry(n, struct io, rb_node); | |
75 | __u64 iop_s = BIT_START(iop), iop_e = BIT_END(iop); | |
76 | __u64 this_s = BIT_START(this), this_e = BIT_END(this); | |
77 | ||
78 | if ((iop_s <= this_s) && (this_e <= iop_e)) { | |
79 | if (fnc) fnc(iop, this); | |
8b10aae0 | 80 | if (head) |
d76c5b81 | 81 | list_add_tail(&this->f_head, head); |
6eb42155 ADB |
82 | } |
83 | if (iop_s < this_s) | |
84 | rb_foreach(n->rb_left, iop, fnc, head); | |
85 | if (this_e < iop_e) | |
86 | rb_foreach(n->rb_right, iop, fnc, head); | |
87 | } | |
88 | } |