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