1 /* 2 * blktrace output analysis: generate a timeline & gather statistics 3 * 4 * Copyright (C) 2006 Alan D. Brunelle <Alan.Brunelle (at) 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 24 int rb_insert(struct rb_root *root, struct io *iop) 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 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 41 return 0; 42 } 43 44 rb_link_node(&iop->rb_node, parent, p); 45 rb_insert_color(&iop->rb_node, root); 46 return 1; 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 67 void rb_foreach(struct rb_node *n, struct io *iop, 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); 78 if (head) 79 list_add_tail(&this->f_head, head); 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 } 87
