Home | History | Annotate | Download | only in fio
      1 /*
      2  * gfio - gui front end for fio - the flexible io tester
      3  *
      4  * Copyright (C) 2012 Stephen M. Cameron <stephenmcameron (at) gmail.com>
      5  *
      6  * The license below covers all files distributed with fio unless otherwise
      7  * noted in the file itself.
      8  *
      9  *  This program is free software; you can redistribute it and/or modify
     10  *  it under the terms of the GNU General Public License version 2 as
     11  *  published by the Free Software Foundation.
     12  *
     13  *  This program is distributed in the hope that it will be useful,
     14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
     15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     16  *  GNU General Public License for more details.
     17  *
     18  *  You should have received a copy of the GNU General Public License
     19  *  along with this program; if not, write to the Free Software
     20  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
     21  *
     22  */
     23 #include <string.h>
     24 #include <malloc.h>
     25 #include <math.h>
     26 #include <assert.h>
     27 #include <stdlib.h>
     28 
     29 #include <cairo.h>
     30 #include <gtk/gtk.h>
     31 
     32 #include "tickmarks.h"
     33 #include "graph.h"
     34 #include "flist.h"
     35 #include "lib/prio_tree.h"
     36 #include "cairo_text_helpers.h"
     37 
     38 /*
     39  * Allowable difference to show tooltip
     40  */
     41 #define TOOLTIP_DELTA	0.08
     42 
     43 struct xyvalue {
     44 	double x, y;
     45 };
     46 
     47 enum {
     48 	GV_F_ON_PRIO	= 1,
     49 	GV_F_PRIO_SKIP	= 2,
     50 };
     51 
     52 struct graph_value {
     53 	struct flist_head list;
     54 	struct prio_tree_node node;
     55 	struct flist_head alias;
     56 	unsigned int flags;
     57 	char *tooltip;
     58 	void *value;
     59 };
     60 
     61 struct graph_label {
     62 	struct flist_head list;
     63 	char *label;
     64 	struct flist_head value_list;
     65 	struct prio_tree_root prio_tree;
     66 	double r, g, b;
     67 	int hide;
     68 	int value_count;
     69 	struct graph *parent;
     70 };
     71 
     72 struct tick_value {
     73 	unsigned int offset;
     74 	double value;
     75 };
     76 
     77 struct graph {
     78 	char *title;
     79 	char *xtitle;
     80 	char *ytitle;
     81 	unsigned int xdim, ydim;
     82 	double xoffset, yoffset;
     83 	struct flist_head label_list;
     84 	int per_label_limit;
     85 	const char *font;
     86 	graph_axis_unit_change_callback x_axis_unit_change_callback;
     87 	graph_axis_unit_change_callback y_axis_unit_change_callback;
     88 	unsigned int base_offset;
     89 	unsigned int dont_graph_all_zeroes;
     90 	double left_extra;
     91 	double right_extra;
     92 	double top_extra;
     93 	double bottom_extra;
     94 
     95 	double xtick_zero;
     96 	double xtick_delta;
     97 	double xtick_zero_val;
     98 	double xtick_one_val;
     99 	double ytick_zero;
    100 	double ytick_delta;
    101 	double ytick_zero_val;
    102 	double ytick_one_val;
    103 };
    104 
    105 void graph_set_size(struct graph *g, unsigned int xdim, unsigned int ydim)
    106 {
    107 	g->xdim = xdim;
    108 	g->ydim = ydim;
    109 }
    110 
    111 void graph_set_position(struct graph *g, double xoffset, double yoffset)
    112 {
    113 	g->xoffset = xoffset;
    114 	g->yoffset = yoffset;
    115 }
    116 
    117 struct graph *graph_new(unsigned int xdim, unsigned int ydim, const char *font)
    118 {
    119 	struct graph *g;
    120 
    121 	g = calloc(1, sizeof(*g));
    122 	INIT_FLIST_HEAD(&g->label_list);
    123 	graph_set_size(g, xdim, ydim);
    124 	g->per_label_limit = -1;
    125 	g->font = font;
    126 	if (!g->font)
    127 		g->font = GRAPH_DEFAULT_FONT;
    128 	return g;
    129 }
    130 
    131 void graph_set_font(struct graph *g, const char *font)
    132 {
    133 	g->font = font;
    134 }
    135 
    136 void graph_x_axis_unit_change_notify(struct graph *g, graph_axis_unit_change_callback f)
    137 {
    138 	g->x_axis_unit_change_callback = f;
    139 }
    140 
    141 void graph_y_axis_unit_change_notify(struct graph *g, graph_axis_unit_change_callback f)
    142 {
    143 	g->y_axis_unit_change_callback = f;
    144 }
    145 
    146 static int count_labels(struct graph *g)
    147 {
    148 	struct flist_head *entry;
    149 	int count = 0;
    150 
    151 	flist_for_each(entry, &g->label_list)
    152 		count++;
    153 
    154 	return count;
    155 }
    156 
    157 static int count_values(struct graph_label *l)
    158 {
    159 	struct flist_head *entry;
    160 	int count = 0;
    161 
    162 	flist_for_each(entry, &l->value_list)
    163 		count++;
    164 
    165 	return count;
    166 }
    167 
    168 typedef double (*double_comparator)(double a, double b);
    169 
    170 static double mindouble(double a, double b)
    171 {
    172 	return a < b ? a : b;
    173 }
    174 
    175 static double maxdouble(double a, double b)
    176 {
    177 	return a < b ? b : a;
    178 }
    179 
    180 static double find_double_values(struct graph_label *l, double_comparator cmp)
    181 {
    182 	struct flist_head *entry;
    183 	double answer = 0.0, tmp;
    184 	int first = 1;
    185 
    186 	if (flist_empty(&l->value_list))
    187 		return 0.0;
    188 
    189 	flist_for_each(entry, &l->value_list) {
    190 		struct graph_value *i;
    191 
    192 		i = flist_entry(entry, struct graph_value, list);
    193 		tmp = *(double *) i->value;
    194 		if (first) {
    195 			answer = tmp;
    196 			first = 0;
    197 		} else {
    198 			answer = cmp(answer, tmp);
    199 		}
    200 	}
    201 	return answer;
    202 }
    203 
    204 static double find_double_data(struct graph *g, double_comparator cmp)
    205 {
    206 	struct flist_head *entry;
    207 	struct graph_label *i;
    208 	int first = 1;
    209 	double answer, tmp;
    210 
    211 	if (flist_empty(&g->label_list))
    212 		return 0.0;
    213 
    214 	flist_for_each(entry, &g->label_list) {
    215 		i = flist_entry(entry, struct graph_label, list);
    216 		tmp = find_double_values(i, cmp);
    217 		if (first) {
    218 			answer = tmp;
    219 			first = 0;
    220 		} else {
    221 			answer = cmp(tmp, answer);
    222 		}
    223 	}
    224 	return answer;
    225 }
    226 
    227 static double find_min_data(struct graph *g)
    228 {
    229 	return find_double_data(g, mindouble);
    230 }
    231 
    232 static double find_max_data(struct graph *g)
    233 {
    234 	return find_double_data(g, maxdouble);
    235 }
    236 
    237 static void draw_bars(struct graph *bg, cairo_t *cr, struct graph_label *lb,
    238 			double label_offset, double bar_width,
    239 			double mindata, double maxdata)
    240 {
    241 	struct flist_head *entry;
    242 	double x1, y1, x2, y2;
    243 	int bar_num = 0;
    244 	double domain, range, v;
    245 
    246 	domain = (maxdata - mindata);
    247 	range = (double) bg->ydim * 0.80; /* FIXME */
    248 	cairo_stroke(cr);
    249 	flist_for_each(entry, &lb->value_list) {
    250 		struct graph_value *i;
    251 
    252 		i = flist_entry(entry, struct graph_value, list);
    253 
    254 		x1 = label_offset + (double) bar_num * bar_width + (bar_width * 0.05);
    255 		x2 = x1 + bar_width * 0.90;
    256 		y2 = bg->ydim * 0.90;
    257 		v = *(double *) i->value;
    258 		y1 = y2 - (((v - mindata) / domain) * range);
    259 		cairo_move_to(cr, x1, y1);
    260 		cairo_line_to(cr, x1, y2);
    261 		cairo_line_to(cr, x2, y2);
    262 		cairo_line_to(cr, x2, y1);
    263 		cairo_close_path(cr);
    264 		cairo_fill(cr);
    265 		cairo_stroke(cr);
    266 		bar_num++;
    267 	}
    268 }
    269 
    270 static void graph_draw_common(struct graph *g, cairo_t *cr, double *x1,
    271 			      double *y1, double *x2, double *y2)
    272 {
    273 	const double shade_col[3][3] = { { 0.55, 0.54, 0.54 },
    274 					 { 0.80, 0.78, 0.78 },
    275 					 { 0.93, 0.91, 0.91 } };
    276 	int i;
    277 
    278 	*x1 = 0.10 * g->xdim;
    279 	*x2 = 0.95 * g->xdim;
    280 	*y1 = 0.10 * g->ydim;
    281 	*y2 = 0.90 * g->ydim;
    282 
    283 	/*
    284 	 * Add shade
    285 	 */
    286 	cairo_set_line_width(cr, 1.0);
    287 	for (i = 0; i < 3; i++) {
    288 		float offset = i + 1.0;
    289 
    290 		cairo_set_source_rgb(cr, shade_col[i][0], shade_col[i][1], shade_col[i][2]);
    291 		cairo_move_to(cr, offset + *x1, *y1 - offset);
    292 		cairo_line_to(cr, *x2 + offset, *y1 - offset);
    293 		cairo_line_to(cr, *x2 + offset, *y2 - offset);
    294 		cairo_stroke(cr);
    295 	}
    296 
    297 	cairo_set_source_rgb(cr, 0, 0, 0);
    298 	cairo_set_line_width(cr, 1.2);
    299 
    300 	cairo_move_to(cr, *x1, *y1);
    301 	cairo_line_to(cr, *x1, *y2);
    302 	cairo_line_to(cr, *x2, *y2);
    303 	cairo_line_to(cr, *x2, *y1);
    304 	cairo_line_to(cr, *x1, *y1);
    305 	cairo_stroke(cr);
    306 
    307 	draw_centered_text(cr, g->font, g->xdim / 2, g->ydim / 20, 20.0, g->title);
    308 	draw_centered_text(cr, g->font, g->xdim / 2, g->ydim * 0.97, 14.0, g->xtitle);
    309 	draw_vertical_centered_text(cr, g->font, g->xdim * 0.02, g->ydim / 2, 14.0, g->ytitle);
    310 	cairo_stroke(cr);
    311 }
    312 
    313 static void graph_draw_x_ticks(struct graph *g, cairo_t *cr,
    314 	double x1, double y1, double x2, double y2,
    315 	double minx, double maxx, int nticks, int add_tm_text)
    316 {
    317 	struct tickmark *tm;
    318 	double tx;
    319 	int i, power_of_ten;
    320 	static double dash[] = { 1.0, 2.0 };
    321 
    322 	nticks = calc_tickmarks(minx, maxx, nticks, &tm, &power_of_ten,
    323 		g->x_axis_unit_change_callback == NULL, g->base_offset);
    324 	if (g->x_axis_unit_change_callback)
    325 		g->x_axis_unit_change_callback(g, power_of_ten);
    326 
    327 	for (i = 0; i < nticks; i++) {
    328 		tx = (((tm[i].value) - minx) / (maxx - minx)) * (x2 - x1) + x1;
    329 
    330 		/*
    331 		 * Update tick delta
    332 		 */
    333 		if (!i) {
    334 			g->xtick_zero = tx;
    335 			g->xtick_zero_val = tm[0].value;
    336 		} else if (i == 1) {
    337 			g->xtick_delta = (tm[1].value - tm[0].value) / (tx - g->xtick_zero);
    338 			g->xtick_one_val = tm[1].value;
    339 		}
    340 
    341 		/* really tx < yx || tx > x2, but protect against rounding */
    342 		if (x1 - tx > 0.01 || tx - x2 > 0.01)
    343 			continue;
    344 
    345 		/* Draw tick mark */
    346 		cairo_set_line_width(cr, 1.0);
    347 		cairo_move_to(cr, tx, y2);
    348 		cairo_line_to(cr, tx, y2 + (y2 - y1) * 0.03);
    349 		cairo_stroke(cr);
    350 
    351 		/* draw grid lines */
    352 		cairo_save(cr);
    353 		cairo_set_dash(cr, dash, 2, 0.66);
    354 		cairo_set_line_width(cr, 0.33);
    355 		cairo_move_to(cr, tx, y1);
    356 		cairo_line_to(cr, tx, y2);
    357 		cairo_stroke(cr);
    358 		cairo_restore(cr);
    359 
    360 		if (!add_tm_text)
    361 			continue;
    362 
    363 		/* draw tickmark label */
    364 		draw_centered_text(cr, g->font, tx, y2 * 1.04, 12.0, tm[i].string);
    365 		cairo_stroke(cr);
    366 	}
    367 }
    368 
    369 static double graph_draw_y_ticks(struct graph *g, cairo_t *cr,
    370 	double x1, double y1, double x2, double y2,
    371 	double miny, double maxy, int nticks, int add_tm_text)
    372 {
    373 	struct tickmark *tm;
    374 	double ty;
    375 	int i, power_of_ten;
    376 	static double dash[] = { 1.0, 2.0 };
    377 
    378 	nticks = calc_tickmarks(miny, maxy, nticks, &tm, &power_of_ten,
    379 		g->y_axis_unit_change_callback == NULL, g->base_offset);
    380 	if (g->y_axis_unit_change_callback)
    381 		g->y_axis_unit_change_callback(g, power_of_ten);
    382 
    383 	/*
    384 	 * Use highest tickmark as top of graph, not highest value. Otherwise
    385 	 * it's impossible to see what the max value is, if the graph is
    386 	 * fairly flat.
    387 	 */
    388 	maxy = tm[nticks - 1].value;
    389 
    390 	for (i = 0; i < nticks; i++) {
    391 		ty = y2 - (((tm[i].value) - miny) / (maxy - miny)) * (y2 - y1);
    392 
    393 		/*
    394 		 * Update tick delta
    395 		 */
    396 		if (!i) {
    397 			g->ytick_zero = ty;
    398 			g->ytick_zero_val = tm[0].value;
    399 		} else if (i == 1) {
    400 			g->ytick_delta = (tm[1].value - tm[0].value) / (ty - g->ytick_zero);
    401 			g->ytick_one_val = tm[1].value;
    402 		}
    403 
    404 		/* really ty < y1 || ty > y2, but protect against rounding */
    405 		if (y1 - ty > 0.01 || ty - y2 > 0.01)
    406 			continue;
    407 
    408 		/* draw tick mark */
    409 		cairo_move_to(cr, x1, ty);
    410 		cairo_line_to(cr, x1 - (x2 - x1) * 0.02, ty);
    411 		cairo_stroke(cr);
    412 
    413 		/* draw grid lines */
    414 		cairo_save(cr);
    415 		cairo_set_dash(cr, dash, 2, 0.66);
    416 		cairo_set_line_width(cr, 0.33);
    417 		cairo_move_to(cr, x1, ty);
    418 		cairo_line_to(cr, x2, ty);
    419 		cairo_stroke(cr);
    420 		cairo_restore(cr);
    421 
    422 		if (!add_tm_text)
    423 			continue;
    424 
    425 		/* draw tickmark label */
    426 		draw_right_justified_text(cr, g->font, x1 - (x2 - x1) * 0.025, ty, 12.0, tm[i].string);
    427 		cairo_stroke(cr);
    428 	}
    429 
    430 	/*
    431 	 * Return new max to use
    432 	 */
    433 	return maxy;
    434 }
    435 
    436 void bar_graph_draw(struct graph *bg, cairo_t *cr)
    437 {
    438 	double x1, y1, x2, y2;
    439 	double space_per_label, bar_width;
    440 	double label_offset, mindata, maxdata;
    441 	int i, nlabels;
    442 	struct graph_label *lb;
    443 	struct flist_head *entry;
    444 
    445 	cairo_save(cr);
    446 	cairo_translate(cr, bg->xoffset, bg->yoffset);
    447 	graph_draw_common(bg, cr, &x1, &y1, &x2, &y2);
    448 
    449 	nlabels = count_labels(bg);
    450 	space_per_label = (x2 - x1) / (double) nlabels;
    451 
    452 	/*
    453 	 * Start bars at 0 unless we have negative values, otherwise we
    454 	 * present a skewed picture comparing label X and X+1.
    455 	 */
    456 	mindata = find_min_data(bg);
    457 	if (mindata > 0)
    458 		mindata = 0;
    459 
    460 	maxdata = find_max_data(bg);
    461 
    462 	if (fabs(maxdata - mindata) < 1e-20) {
    463 		draw_centered_text(cr, bg->font,
    464 			x1 + (x2 - x1) / 2.0,
    465 			y1 + (y2 - y1) / 2.0, 20.0, "No good data");
    466 		return;
    467 	}
    468 
    469 	maxdata = graph_draw_y_ticks(bg, cr, x1, y1, x2, y2, mindata, maxdata, 10, 1);
    470 	i = 0;
    471 	flist_for_each(entry, &bg->label_list) {
    472 		int nvalues;
    473 
    474 		lb = flist_entry(entry, struct graph_label, list);
    475 		nvalues = count_values(lb);
    476 		bar_width = (space_per_label - space_per_label * 0.2) / (double) nvalues;
    477 		label_offset = bg->xdim * 0.1 + space_per_label * (double) i + space_per_label * 0.1;
    478 		draw_bars(bg, cr, lb, label_offset, bar_width, mindata, maxdata);
    479 		// draw_centered_text(cr, label_offset + (bar_width / 2.0 + bar_width * 0.1), bg->ydim * 0.93,
    480 		draw_centered_text(cr, bg->font, x1 + space_per_label * (i + 0.5), bg->ydim * 0.93,
    481 			12.0, lb->label);
    482 		i++;
    483 	}
    484 	cairo_stroke(cr);
    485 	cairo_restore(cr);
    486 }
    487 
    488 typedef double (*xy_value_extractor)(struct graph_value *v);
    489 
    490 static double getx(struct graph_value *v)
    491 {
    492 	struct xyvalue *xy = v->value;
    493 	return xy->x;
    494 }
    495 
    496 static double gety(struct graph_value *v)
    497 {
    498 	struct xyvalue *xy = v->value;
    499 	return xy->y;
    500 }
    501 
    502 static double find_xy_value(struct graph *g, xy_value_extractor getvalue, double_comparator cmp)
    503 {
    504 	double tmp, answer = 0.0;
    505 	struct graph_label *i;
    506 	struct graph_value *j;
    507 	struct flist_head *jentry, *entry;
    508 	int first = 1;
    509 
    510 	flist_for_each(entry, &g->label_list) {
    511 		i = flist_entry(entry, struct graph_label, list);
    512 
    513 		flist_for_each(jentry, &i->value_list) {
    514 			j = flist_entry(jentry, struct graph_value, list);
    515 			tmp = getvalue(j);
    516 			if (first) {
    517 				first = 0;
    518 				answer = tmp;
    519 			}
    520 			answer = cmp(tmp, answer);
    521 		}
    522 	}
    523 
    524 	return answer;
    525 }
    526 
    527 void line_graph_draw(struct graph *g, cairo_t *cr)
    528 {
    529 	double x1, y1, x2, y2;
    530 	double minx, miny, maxx, maxy, gminx, gminy, gmaxx, gmaxy;
    531 	double tx, ty, top_extra, bottom_extra, left_extra, right_extra;
    532 	struct graph_label *i;
    533 	struct graph_value *j;
    534 	int good_data = 1, first = 1;
    535 	struct flist_head *entry, *lentry;
    536 
    537 	cairo_save(cr);
    538 	cairo_translate(cr, g->xoffset, g->yoffset);
    539 	graph_draw_common(g, cr, &x1, &y1, &x2, &y2);
    540 
    541 	minx = find_xy_value(g, getx, mindouble);
    542 	maxx = find_xy_value(g, getx, maxdouble);
    543 	miny = find_xy_value(g, gety, mindouble);
    544 
    545 	/*
    546 	 * Start graphs at zero, unless we have a value below. Otherwise
    547 	 * it's hard to visually compare the read and write graph, since
    548 	 * the lowest valued one will be the floor of the graph view.
    549 	 */
    550 	if (miny > 0)
    551 		miny = 0;
    552 
    553 	maxy = find_xy_value(g, gety, maxdouble);
    554 
    555 	if (fabs(maxx - minx) < 1e-20 || fabs(maxy - miny) < 1e-20) {
    556 		good_data = 0;
    557 		minx = 0.0;
    558 		miny = 0.0;
    559 		maxx = 10.0;
    560 		maxy = 100.0;
    561 	}
    562 
    563 	top_extra = 0.0;
    564 	bottom_extra = 0.0;
    565 	left_extra = 0.0;
    566 	right_extra = 0.0;
    567 
    568 	if (g->top_extra > 0.001)
    569 		top_extra = fabs(maxy - miny) * g->top_extra;
    570 	if (g->bottom_extra > 0.001)
    571 		bottom_extra = fabs(maxy - miny) * g->bottom_extra;
    572 	if (g->left_extra > 0.001)
    573 		left_extra = fabs(maxx - minx) * g->left_extra;
    574 	if (g->right_extra > 0.001)
    575 		right_extra = fabs(maxx - minx) * g->right_extra;
    576 
    577 	gminx = minx - left_extra;
    578 	gmaxx = maxx + right_extra;
    579 	gminy = miny - bottom_extra;
    580 	gmaxy = maxy + top_extra;
    581 
    582 	graph_draw_x_ticks(g, cr, x1, y1, x2, y2, gminx, gmaxx, 10, good_data);
    583 	gmaxy = graph_draw_y_ticks(g, cr, x1, y1, x2, y2, gminy, gmaxy, 10, good_data);
    584 
    585 	if (!good_data)
    586 		goto skip_data;
    587 
    588 	cairo_set_line_width(cr, 1.5);
    589 	cairo_set_line_join(cr, CAIRO_LINE_JOIN_ROUND);
    590 
    591 	flist_for_each(lentry, &g->label_list) {
    592 		i = flist_entry(lentry, struct graph_label, list);
    593 		first = 1;
    594 		if (i->hide || i->r < 0) /* invisible data */
    595 			continue;
    596 
    597 		cairo_set_source_rgb(cr, i->r, i->g, i->b);
    598 		flist_for_each(entry, &i->value_list) {
    599 			j = flist_entry(entry, struct graph_value, list);
    600 			tx = ((getx(j) - gminx) / (gmaxx - gminx)) * (x2 - x1) + x1;
    601 			ty = y2 - ((gety(j) - gminy) / (gmaxy - gminy)) * (y2 - y1);
    602 			if (first) {
    603 				cairo_move_to(cr, tx, ty);
    604 				first = 0;
    605 			} else
    606 				cairo_line_to(cr, tx, ty);
    607 		}
    608 		cairo_stroke(cr);
    609 	}
    610 
    611 skip_data:
    612 	cairo_restore(cr);
    613 }
    614 
    615 static void setstring(char **str, const char *value)
    616 {
    617 	free(*str);
    618 	*str = strdup(value);
    619 }
    620 
    621 void graph_title(struct graph *bg, const char *title)
    622 {
    623 	setstring(&bg->title, title);
    624 }
    625 
    626 void graph_x_title(struct graph *bg, const char *title)
    627 {
    628 	setstring(&bg->xtitle, title);
    629 }
    630 
    631 void graph_y_title(struct graph *bg, const char *title)
    632 {
    633 	setstring(&bg->ytitle, title);
    634 }
    635 
    636 static struct graph_label *graph_find_label(struct graph *bg,
    637 				const char *label)
    638 {
    639 	struct flist_head *entry;
    640 	struct graph_label *i;
    641 
    642 	flist_for_each(entry, &bg->label_list) {
    643 		i = flist_entry(entry, struct graph_label, list);
    644 
    645 		if (strcmp(label, i->label) == 0)
    646 			return i;
    647 	}
    648 
    649 	return NULL;
    650 }
    651 
    652 graph_label_t graph_add_label(struct graph *bg, const char *label)
    653 {
    654 	struct graph_label *i;
    655 
    656 	i = graph_find_label(bg, label);
    657 	if (i)
    658 		return i; /* already present. */
    659 	i = calloc(1, sizeof(*i));
    660 	INIT_FLIST_HEAD(&i->value_list);
    661 	i->parent = bg;
    662 	setstring(&i->label, label);
    663 	flist_add_tail(&i->list, &bg->label_list);
    664 	INIT_PRIO_TREE_ROOT(&i->prio_tree);
    665 	return i;
    666 }
    667 
    668 static void __graph_value_drop(struct graph_label *l, struct graph_value *v)
    669 {
    670 	flist_del_init(&v->list);
    671 	if (v->tooltip)
    672 		free(v->tooltip);
    673 	free(v->value);
    674 	free(v);
    675 	l->value_count--;
    676 }
    677 
    678 static void graph_value_drop(struct graph_label *l, struct graph_value *v)
    679 {
    680 	if (v->flags & GV_F_PRIO_SKIP) {
    681 		__graph_value_drop(l, v);
    682 		return;
    683 	}
    684 
    685 	/*
    686 	 * Find head, the guy that's on the prio tree
    687 	 */
    688 	while (!(v->flags & GV_F_ON_PRIO)) {
    689 		assert(!flist_empty(&v->alias));
    690 		v = flist_entry(v->alias.next, struct graph_value, alias);
    691 	}
    692 
    693 	prio_tree_remove(&l->prio_tree, &v->node);
    694 
    695 	/*
    696 	 * Free aliases
    697 	 */
    698 	while (!flist_empty(&v->alias)) {
    699 		struct graph_value *a;
    700 
    701 		a = flist_entry(v->alias.next, struct graph_value, alias);
    702 		flist_del_init(&a->alias);
    703 
    704 		__graph_value_drop(l, a);
    705 	}
    706 
    707 	__graph_value_drop(l, v);
    708 }
    709 
    710 static void graph_label_add_value(struct graph_label *i, void *value,
    711 				  const char *tooltip)
    712 {
    713 	struct graph *g = i->parent;
    714 	struct graph_value *x;
    715 
    716 	x = malloc(sizeof(*x));
    717 	memset(x, 0, sizeof(*x));
    718 	INIT_FLIST_HEAD(&x->alias);
    719 	INIT_FLIST_HEAD(&x->list);
    720 	flist_add_tail(&x->list, &i->value_list);
    721 	i->value_count++;
    722 	x->value = value;
    723 
    724 	if (tooltip) {
    725 		double xval = getx(x);
    726 		double minx = xval - (g->xtick_one_val * TOOLTIP_DELTA);
    727 		double maxx = xval + (g->xtick_one_val * TOOLTIP_DELTA);
    728 		struct prio_tree_node *ret;
    729 
    730 		/*
    731 		 * use msec to avoid dropping too much precision when
    732 		 * storing as an integer.
    733 		 */
    734 		minx = minx * 1000.0;
    735 		maxx = maxx * 1000.0;
    736 
    737 		INIT_PRIO_TREE_NODE(&x->node);
    738 		x->node.start = minx;
    739 		x->node.last = maxx;
    740 		x->tooltip = strdup(tooltip);
    741 		if (x->node.last == x->node.start) {
    742 			x->node.last += fabs(g->xtick_delta);
    743 			if (x->node.last == x->node.start)
    744 				x->node.last++;
    745 		}
    746 
    747 		/*
    748 		 * If ret != &x->node, we have an alias. Since the values
    749 		 * should be identical, we can drop it
    750 		 */
    751 		ret = prio_tree_insert(&i->prio_tree, &x->node);
    752 		if (ret != &x->node) {
    753 			struct graph_value *alias;
    754 
    755 			alias = container_of(ret, struct graph_value, node);
    756 			flist_add_tail(&x->alias, &alias->alias);
    757 		} else
    758 			x->flags = GV_F_ON_PRIO;
    759 	} else
    760 		x->flags = GV_F_PRIO_SKIP;
    761 
    762 	if (g->per_label_limit != -1 &&
    763 		i->value_count > g->per_label_limit) {
    764 		int to_drop = 1;
    765 
    766 		/*
    767 		 * If the limit was dynamically reduced, making us more
    768 		 * than 1 entry ahead after adding this one, drop two
    769 		 * entries. This will make us (eventually) reach the
    770 		 * specified limit.
    771 		 */
    772 		if (i->value_count - g->per_label_limit >= 2)
    773 			to_drop = 2;
    774 
    775 		while (to_drop-- && !flist_empty(&i->value_list)) {
    776 			x = flist_entry(i->value_list.next, struct graph_value, list);
    777 			graph_value_drop(i, x);
    778 
    779 			/*
    780 			 * If we have aliases, we could drop > 1 above.
    781 			 */
    782 			if (i->value_count <= g->per_label_limit)
    783 				break;
    784 		}
    785 	}
    786 }
    787 
    788 int graph_add_data(struct graph *bg, graph_label_t label, const double value)
    789 {
    790 	struct graph_label *i = label;
    791 	double *d;
    792 
    793 	d = malloc(sizeof(*d));
    794 	*d = value;
    795 
    796 	graph_label_add_value(i, d, NULL);
    797 	return 0;
    798 }
    799 
    800 static int graph_nonzero_y(struct graph_label *l)
    801 {
    802 	struct flist_head *entry;
    803 
    804 	flist_for_each(entry, &l->value_list) {
    805 		struct graph_value *v;
    806 
    807 		v = flist_entry(entry, struct graph_value, list);
    808 		if (gety(v) != 0.0)
    809 			return 1;
    810 	}
    811 
    812 	return 0;
    813 }
    814 
    815 int graph_add_xy_data(struct graph *bg, graph_label_t label,
    816 		      const double x, const double y, const char *tooltip)
    817 {
    818 	struct graph_label *i = label;
    819 	struct xyvalue *xy;
    820 
    821 	if (bg->dont_graph_all_zeroes && y == 0.0 && !graph_nonzero_y(i))
    822 		i->hide = 1;
    823 	else
    824 		i->hide = 0;
    825 
    826 	xy = malloc(sizeof(*xy));
    827 	xy->x = x;
    828 	xy->y = y;
    829 
    830 	graph_label_add_value(i, xy, tooltip);
    831 	return 0;
    832 }
    833 
    834 static void graph_free_values(struct graph_label *l)
    835 {
    836 	struct graph_value *i;
    837 
    838 	while (!flist_empty(&l->value_list)) {
    839 		i = flist_entry(l->value_list.next, struct graph_value, list);
    840 		graph_value_drop(l, i);
    841 	}
    842 }
    843 
    844 static void graph_free_labels(struct graph *g)
    845 {
    846 	struct graph_label *i;
    847 
    848 	while (!flist_empty(&g->label_list)) {
    849 		i = flist_entry(g->label_list.next, struct graph_label, list);
    850 		flist_del(&i->list);
    851 		graph_free_values(i);
    852 		free(i);
    853 	}
    854 }
    855 
    856 void graph_clear_values(struct graph *g)
    857 {
    858 	struct flist_head *node;
    859 	struct graph_label *i;
    860 
    861 	flist_for_each(node, &g->label_list) {
    862 		i = flist_entry(node, struct graph_label, list);
    863 		graph_free_values(i);
    864 	}
    865 }
    866 
    867 void graph_set_color(struct graph *gr, graph_label_t label, double red,
    868 		     double green, double blue)
    869 {
    870 	struct graph_label *i = label;
    871 	double r, g, b;
    872 
    873 	if (red < 0.0) { /* invisible color */
    874 		r = -1.0;
    875 		g = -1.0;
    876 		b = -1.0;
    877 	} else {
    878 		r = fabs(red);
    879 		g = fabs(green);
    880 		b = fabs(blue);
    881 
    882 		if (r > 1.0)
    883 			r = 1.0;
    884 		if (g > 1.0)
    885 			g = 1.0;
    886 		if (b > 1.0)
    887 			b = 1.0;
    888 	}
    889 
    890 	i->r = r;
    891 	i->g = g;
    892 	i->b = b;
    893 }
    894 
    895 void graph_free(struct graph *bg)
    896 {
    897 	free(bg->title);
    898 	free(bg->xtitle);
    899 	free(bg->ytitle);
    900 	graph_free_labels(bg);
    901 }
    902 
    903 /* For each line in the line graph, up to per_label_limit segments may
    904  * be added.  After that, adding more data to the end of the line
    905  * causes data to drop off of the front of the line.
    906  */
    907 void line_graph_set_data_count_limit(struct graph *g, int per_label_limit)
    908 {
    909 	g->per_label_limit = per_label_limit;
    910 }
    911 
    912 void graph_add_extra_space(struct graph *g, double left_percent,
    913 			   double right_percent, double top_percent,
    914 			   double bottom_percent)
    915 {
    916 	g->left_extra = left_percent;
    917 	g->right_extra = right_percent;
    918 	g->top_extra = top_percent;
    919 	g->bottom_extra = bottom_percent;
    920 }
    921 
    922 /*
    923  * Normally values are logged in a base unit of 0, but for other purposes
    924  * it makes more sense to log in higher unit. For instance for bandwidth
    925  * purposes, you may want to log in KB/sec (or MB/sec) rather than bytes/sec.
    926  */
    927 void graph_set_base_offset(struct graph *g, unsigned int base_offset)
    928 {
    929 	g->base_offset = base_offset;
    930 }
    931 
    932 int graph_has_tooltips(struct graph *g)
    933 {
    934 	struct flist_head *entry;
    935 	struct graph_label *i;
    936 
    937 	flist_for_each(entry, &g->label_list) {
    938 		i = flist_entry(entry, struct graph_label, list);
    939 
    940 		if (!prio_tree_empty(&i->prio_tree))
    941 			return 1;
    942 	}
    943 
    944 	return 0;
    945 }
    946 
    947 int graph_contains_xy(struct graph *g, int x, int y)
    948 {
    949 	int first_x = g->xoffset;
    950 	int last_x = g->xoffset + g->xdim;
    951 	int first_y = g->yoffset;
    952 	int last_y = g->yoffset + g->ydim;
    953 
    954 	return (x >= first_x && x <= last_x) && (y >= first_y && y <= last_y);
    955 }
    956 
    957 const char *graph_find_tooltip(struct graph *g, int ix, int iy)
    958 {
    959 	double x = ix, y = iy;
    960 	struct prio_tree_iter iter;
    961 	struct prio_tree_node *n;
    962 	struct graph_value *best = NULL;
    963 	struct flist_head *entry;
    964 	double best_delta;
    965 	double maxy, miny;
    966 
    967 	x -= g->xoffset;
    968 	y -= g->yoffset;
    969 
    970 	x = g->xtick_zero_val + ((x - g->xtick_zero) * g->xtick_delta);
    971 	y = g->ytick_zero_val + ((y - g->ytick_zero) * g->ytick_delta);
    972 
    973 	x = x * 1000.0;
    974 	maxy = y + (g->ytick_one_val * TOOLTIP_DELTA);
    975 	miny = y - (g->ytick_one_val * TOOLTIP_DELTA);
    976 	best_delta = UINT_MAX;
    977 	flist_for_each(entry, &g->label_list) {
    978 		struct graph_label *i;
    979 
    980 		i = flist_entry(entry, struct graph_label, list);
    981 		if (i->hide)
    982 			continue;
    983 
    984 		INIT_PRIO_TREE_ITER(&iter);
    985 		prio_tree_iter_init(&iter, &i->prio_tree, x, x);
    986 
    987 		n = prio_tree_next(&iter);
    988 		if (!n)
    989 			continue;
    990 
    991 		do {
    992 			struct graph_value *v, *rootv;
    993 			double yval, ydiff;
    994 
    995 			v = container_of(n, struct graph_value, node);
    996 			rootv = v;
    997 			do {
    998 				yval = gety(v);
    999 				ydiff = fabs(yval - y);
   1000 
   1001 				/*
   1002 				 * zero delta, or within or match critera, break
   1003 				 */
   1004 				if (ydiff < best_delta) {
   1005 					best_delta = ydiff;
   1006 					if (!best_delta ||
   1007 					    (yval >= miny && yval <= maxy)) {
   1008 						best = v;
   1009 						break;
   1010 					}
   1011 				}
   1012 				if (!flist_empty(&v->alias))
   1013 					v = flist_entry(v->alias.next, struct graph_value, alias);
   1014 			} while (v != rootv);
   1015 		} while ((n = prio_tree_next(&iter)) != NULL);
   1016 
   1017 		/*
   1018 		 * If we got matches in one label, don't check others.
   1019 		 */
   1020 		if (best)
   1021 			break;
   1022 	}
   1023 
   1024 	if (best)
   1025 		return best->tooltip;
   1026 
   1027 	return NULL;
   1028 }
   1029 
   1030 void graph_set_graph_all_zeroes(struct graph *g, unsigned int set)
   1031 {
   1032 	g->dont_graph_all_zeroes = !set;
   1033 }
   1034