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; | |
40 | else | |
095181f2 | 41 | return 0; |
6eb42155 ADB |
42 | } |
43 | ||
44 | rb_link_node(&iop->rb_node, parent, p); | |
45 | rb_insert_color(&iop->rb_node, root); | |
095181f2 | 46 | return 1; |
6eb42155 ADB |
47 | } |
48 | ||
49 | struct io *rb_find_sec(struct rb_root *root, __u64 sec) | |
50 | { | |
51 | struct io *__iop; | |
52 | struct rb_node *n = root->rb_node; | |
53 | ||
54 | while (n) { | |
55 | __iop = rb_entry(n, struct io, rb_node); | |
56 | if (sec < BIT_START(__iop)) | |
57 | n = n->rb_left; | |
58 | else if (sec >= BIT_END(__iop)) | |
59 | n = n->rb_right; | |
60 | else | |
61 | return __iop; | |
62 | } | |
63 | ||
64 | return NULL; | |
65 | } | |
66 | ||
8b10aae0 | 67 | void rb_foreach(struct rb_node *n, struct io *iop, |
6eb42155 ADB |
68 | void (*fnc)(struct io *iop, struct io *this), |
69 | struct list_head *head) | |
70 | { | |
71 | if (n) { | |
72 | struct io *this = rb_entry(n, struct io, rb_node); | |
73 | __u64 iop_s = BIT_START(iop), iop_e = BIT_END(iop); | |
74 | __u64 this_s = BIT_START(this), this_e = BIT_END(this); | |
75 | ||
76 | if ((iop_s <= this_s) && (this_e <= iop_e)) { | |
77 | if (fnc) fnc(iop, this); | |
8b10aae0 | 78 | if (head) |
d76c5b81 | 79 | list_add_tail(&this->f_head, head); |
6eb42155 ADB |
80 | } |
81 | if (iop_s < this_s) | |
82 | rb_foreach(n->rb_left, iop, fnc, head); | |
83 | if (this_e < iop_e) | |
84 | rb_foreach(n->rb_right, iop, fnc, head); | |
85 | } | |
86 | } |