X-Git-Url: https://git.kernel.dk/?p=fio.git;a=blobdiff_plain;f=graph.c;h=7a174170c7562fe7b13b27506ba0b68709d3df00;hp=837211dacebdb4f47defcc6e5b02ce9149c0b25c;hb=01bf5128d0581e267383f280c6a1dcd26517240f;hpb=5aec66804d2a6d60aee8d973680c69b13c1d34a3

diff --git a/graph.c b/graph.c
index 837211da..7a174170 100644
--- a/graph.c
+++ b/graph.c
@@ -1,7 +1,7 @@
 /*
  * gfio - gui front end for fio - the flexible io tester
  *
- * Copyright (C) 2012 Stephen M. Cameron <stephenmcameron@gmail.com> 
+ * Copyright (C) 2012 Stephen M. Cameron <stephenmcameron@gmail.com>
  *
  * The license below covers all files distributed with fio unless otherwise
  * noted in the file itself.
@@ -17,11 +17,11 @@
  *
  *  You should have received a copy of the GNU General Public License
  *  along with this program; if not, write to the Free Software
- *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  *
  */
 #include <string.h>
-#include <malloc.h>
+#include <stdlib.h>
 #include <math.h>
 #include <assert.h>
 #include <stdlib.h>
@@ -31,46 +31,75 @@
 
 #include "tickmarks.h"
 #include "graph.h"
+#include "flist.h"
+#include "lib/prio_tree.h"
+#include "cairo_text_helpers.h"
+
+/*
+ * Allowable difference to show tooltip
+ */
+#define TOOLTIP_DELTA	0.08
 
 struct xyvalue {
 	double x, y;
-	int gx, gy;
+};
+
+enum {
+	GV_F_ON_PRIO	= 1,
+	GV_F_PRIO_SKIP	= 2,
 };
 
 struct graph_value {
-	struct graph_value *next;
+	struct flist_head list;
+	struct prio_tree_node node;
+	struct flist_head alias;
+	unsigned int flags;
 	char *tooltip;
 	void *value;
 };
 
 struct graph_label {
+	struct flist_head list;
 	char *label;
-	struct graph_value *tail;
-	struct graph_value *values;
-	struct graph_label *next;
+	struct flist_head value_list;
+	struct prio_tree_root prio_tree;
 	double r, g, b;
+	int hide;
 	int value_count;
-	unsigned int tooltip_count;
 	struct graph *parent;
 };
 
+struct tick_value {
+	unsigned int offset;
+	double value;
+};
+
 struct graph {
 	char *title;
 	char *xtitle;
 	char *ytitle;
 	unsigned int xdim, ydim;
 	double xoffset, yoffset;
-	struct graph_label *labels;
-	struct graph_label *tail;
+	struct flist_head label_list;
 	int per_label_limit;
 	const char *font;
 	graph_axis_unit_change_callback x_axis_unit_change_callback;
 	graph_axis_unit_change_callback y_axis_unit_change_callback;
 	unsigned int base_offset;
-	double left_extra;	
-	double right_extra;	
-	double top_extra;	
-	double bottom_extra;	
+	unsigned int dont_graph_all_zeroes;
+	double left_extra;
+	double right_extra;
+	double top_extra;
+	double bottom_extra;
+
+	double xtick_zero;
+	double xtick_delta;
+	double xtick_zero_val;
+	double xtick_one_val;
+	double ytick_zero;
+	double ytick_delta;
+	double ytick_zero_val;
+	double ytick_one_val;
 };
 
 void graph_set_size(struct graph *g, unsigned int xdim, unsigned int ydim)
@@ -90,14 +119,20 @@ struct graph *graph_new(unsigned int xdim, unsigned int ydim, const char *font)
 	struct graph *g;
 
 	g = calloc(1, sizeof(*g));
+	INIT_FLIST_HEAD(&g->label_list);
 	graph_set_size(g, xdim, ydim);
 	g->per_label_limit = -1;
 	g->font = font;
 	if (!g->font)
-		g->font = "Sans";
+		g->font = GRAPH_DEFAULT_FONT;
 	return g;
 }
 
+void graph_set_font(struct graph *g, const char *font)
+{
+	g->font = font;
+}
+
 void graph_x_axis_unit_change_notify(struct graph *g, graph_axis_unit_change_callback f)
 {
 	g->x_axis_unit_change_callback = f;
@@ -108,23 +143,25 @@ void graph_y_axis_unit_change_notify(struct graph *g, graph_axis_unit_change_cal
 	g->y_axis_unit_change_callback = f;
 }
 
-static int count_labels(struct graph_label *labels)
+static int count_labels(struct graph *g)
 {
+	struct flist_head *entry;
 	int count = 0;
-	struct graph_label *i;
 
-	for (i = labels; i; i = i->next)
+	flist_for_each(entry, &g->label_list)
 		count++;
+
 	return count;
 }
 
-static int count_values(struct graph_value *values)
+static int count_values(struct graph_label *l)
 {
+	struct flist_head *entry;
 	int count = 0;
-	struct graph_value *i;
 
-	for (i = values; i; i = i->next)
+	flist_for_each(entry, &l->value_list)
 		count++;
+
 	return count;
 }
 
@@ -140,16 +177,20 @@ static double maxdouble(double a, double b)
 	return a < b ? b : a;
 }
 
-static double find_double_values(struct graph_value *values, double_comparator cmp)
+static double find_double_values(struct graph_label *l, double_comparator cmp)
 {
-	struct graph_value *i;
+	struct flist_head *entry;
+	double answer = 0.0, tmp;
 	int first = 1;
-	double answer, tmp;
 
-	assert(values != NULL);
-	answer = 0.0; /* shut the compiler up, might need to think harder though. */
-	for (i = values; i; i = i->next) {
-		tmp = *(double *) i->value; 
+	if (flist_empty(&l->value_list))
+		return 0.0;
+
+	flist_for_each(entry, &l->value_list) {
+		struct graph_value *i;
+
+		i = flist_entry(entry, struct graph_value, list);
+		tmp = *(double *) i->value;
 		if (first) {
 			answer = tmp;
 			first = 0;
@@ -160,16 +201,19 @@ static double find_double_values(struct graph_value *values, double_comparator c
 	return answer;
 }
 
-static double find_double_data(struct graph_label *labels, double_comparator cmp)
+static double find_double_data(struct graph *g, double_comparator cmp)
 {
+	struct flist_head *entry;
 	struct graph_label *i;
 	int first = 1;
 	double answer, tmp;
 
-	assert(labels != NULL);
-	answer = 0.0; /* shut the compiler up, might need to think harder though. */
-	for (i = labels; i; i = i->next) {
-		tmp = find_double_values(i->values, cmp);
+	if (flist_empty(&g->label_list))
+		return 0.0;
+
+	flist_for_each(entry, &g->label_list) {
+		i = flist_entry(entry, struct graph_label, list);
+		tmp = find_double_values(i, cmp);
 		if (first) {
 			answer = tmp;
 			first = 0;
@@ -180,21 +224,21 @@ static double find_double_data(struct graph_label *labels, double_comparator cmp
 	return answer;
 }
 
-static double find_min_data(struct graph_label *labels)
+static double find_min_data(struct graph *g)
 {
-	return find_double_data(labels, mindouble);
+	return find_double_data(g, mindouble);
 }
 
-static double find_max_data(struct graph_label *labels)
+static double find_max_data(struct graph *g)
 {
-	return find_double_data(labels, maxdouble);
+	return find_double_data(g, maxdouble);
 }
 
 static void draw_bars(struct graph *bg, cairo_t *cr, struct graph_label *lb,
 			double label_offset, double bar_width,
 			double mindata, double maxdata)
 {
-	struct graph_value *i;
+	struct flist_head *entry;
 	double x1, y1, x2, y2;
 	int bar_num = 0;
 	double domain, range, v;
@@ -202,7 +246,10 @@ static void draw_bars(struct graph *bg, cairo_t *cr, struct graph_label *lb,
 	domain = (maxdata - mindata);
 	range = (double) bg->ydim * 0.80; /* FIXME */
 	cairo_stroke(cr);
-	for (i = lb->values; i; i = i->next) {
+	flist_for_each(entry, &lb->value_list) {
+		struct graph_value *i;
+
+		i = flist_entry(entry, struct graph_value, list);
 
 		x1 = label_offset + (double) bar_num * bar_width + (bar_width * 0.05);
 		x2 = x1 + bar_width * 0.90;
@@ -216,101 +263,39 @@ static void draw_bars(struct graph *bg, cairo_t *cr, struct graph_label *lb,
 		cairo_close_path(cr);
 		cairo_fill(cr);
 		cairo_stroke(cr);
-		bar_num++;	
+		bar_num++;
 	}
 }
 
-static void draw_aligned_text(struct graph *g, cairo_t *cr, double x, double y,
-			       double fontsize, const char *text, int alignment)
+static void graph_draw_common(struct graph *g, cairo_t *cr, double *x1,
+			      double *y1, double *x2, double *y2)
 {
-#define CENTERED 0
-#define LEFT_JUSTIFIED 1
-#define RIGHT_JUSTIFIED 2
+	const double shade_col[3][3] = { { 0.55, 0.54, 0.54 },
+					 { 0.80, 0.78, 0.78 },
+					 { 0.93, 0.91, 0.91 } };
+	int i;
 
-	double factor, direction;
-	cairo_text_extents_t extents;
+	*x1 = 0.10 * g->xdim;
+	*x2 = 0.95 * g->xdim;
+	*y1 = 0.10 * g->ydim;
+	*y2 = 0.90 * g->ydim;
 
-	switch(alignment) {
-		case CENTERED:
-			direction = -1.0;
-			factor = 0.5;
-			break;
-		case RIGHT_JUSTIFIED:
-			direction = -1.0;
-			factor = 1.0;
-			break;
-		case LEFT_JUSTIFIED:
-		default:
-			direction = 1.0;
-			factor = 1.0;
-			break;
+	/*
+	 * Add shade
+	 */
+	cairo_set_line_width(cr, 1.0);
+	for (i = 0; i < 3; i++) {
+		float offset = i + 1.0;
+
+		cairo_set_source_rgb(cr, shade_col[i][0], shade_col[i][1], shade_col[i][2]);
+		cairo_move_to(cr, offset + *x1, *y1 - offset);
+		cairo_line_to(cr, *x2 + offset, *y1 - offset);
+		cairo_line_to(cr, *x2 + offset, *y2 - offset);
+		cairo_stroke(cr);
 	}
-	cairo_select_font_face (cr, g->font, CAIRO_FONT_SLANT_NORMAL, CAIRO_FONT_WEIGHT_NORMAL);
 
-	cairo_set_font_size(cr, fontsize);
-	cairo_text_extents(cr, text, &extents);
-	x = x + direction * (factor * extents.width  + extents.x_bearing);
-	y = y - (extents.height / 2 + extents.y_bearing);
-
-	cairo_move_to(cr, x, y);
-	cairo_show_text(cr, text);
-}
-
-static inline void draw_centered_text(struct graph *g, cairo_t *cr, double x, double y,
-			       double fontsize, const char *text)
-{
-	draw_aligned_text(g, cr, x, y, fontsize, text, CENTERED);
-}
-
-static inline void draw_right_justified_text(struct graph *g, cairo_t *cr,
-				double x, double y,
-				double fontsize, const char *text)
-{
-	draw_aligned_text(g, cr, x, y, fontsize, text, RIGHT_JUSTIFIED);
-}
-
-static inline void draw_left_justified_text(struct graph *g, cairo_t *cr,
-				double x, double y,
-				double fontsize, const char *text)
-{
-	draw_aligned_text(g, cr, x, y, fontsize, text, LEFT_JUSTIFIED);
-}
-
-static void draw_vertical_centered_text(struct graph *g, cairo_t *cr, double x,
-					double y, double fontsize,
-					const char *text)
-{
-	double sx, sy;
-	cairo_text_extents_t extents;
-
-	cairo_select_font_face(cr, g->font, CAIRO_FONT_SLANT_NORMAL, CAIRO_FONT_WEIGHT_NORMAL);
-
-	cairo_set_font_size(cr, fontsize);
-	cairo_text_extents(cr, text, &extents);
-	sx = x;
-	sy = y;
-	y = y + (extents.width / 2.0 + extents.x_bearing);
-	x = x - (extents.height / 2.0 + extents.y_bearing);
-
-	cairo_move_to(cr, x, y);
-	cairo_save(cr);
-	cairo_translate(cr, -sx, -sy);
-	cairo_rotate(cr, -90.0 * M_PI / 180.0);
-	cairo_translate(cr, sx, sy);
-	cairo_show_text(cr, text);
-	cairo_restore(cr);
-}
-
-static void graph_draw_common(struct graph *g, cairo_t *cr,
-	double *x1, double *y1, double *x2, double *y2)
-{
-        cairo_set_source_rgb(cr, 0, 0, 0);
-        cairo_set_line_width (cr, 0.8);
-
-	*x1 = 0.10 * g->xdim;	
-	*x2 = 0.95 * g->xdim;
-	*y1 = 0.10 * g->ydim;	
-	*y2 = 0.90 * g->ydim;
+	cairo_set_source_rgb(cr, 0, 0, 0);
+	cairo_set_line_width(cr, 1.2);
 
 	cairo_move_to(cr, *x1, *y1);
 	cairo_line_to(cr, *x1, *y2);
@@ -319,9 +304,9 @@ static void graph_draw_common(struct graph *g, cairo_t *cr,
 	cairo_line_to(cr, *x1, *y1);
 	cairo_stroke(cr);
 
-	draw_centered_text(g, cr, g->xdim / 2, g->ydim / 20, 20.0, g->title);
-	draw_centered_text(g, cr, g->xdim / 2, g->ydim * 0.97, 14.0, g->xtitle);
-	draw_vertical_centered_text(g, cr, g->xdim * 0.02, g->ydim / 2, 14.0, g->ytitle);
+	draw_centered_text(cr, g->font, g->xdim / 2, g->ydim / 20, 20.0, g->title);
+	draw_centered_text(cr, g->font, g->xdim / 2, g->ydim * 0.97, 14.0, g->xtitle);
+	draw_vertical_centered_text(cr, g->font, g->xdim * 0.02, g->ydim / 2, 14.0, g->ytitle);
 	cairo_stroke(cr);
 }
 
@@ -342,20 +327,31 @@ static void graph_draw_x_ticks(struct graph *g, cairo_t *cr,
 	for (i = 0; i < nticks; i++) {
 		tx = (((tm[i].value) - minx) / (maxx - minx)) * (x2 - x1) + x1;
 
+		/*
+		 * Update tick delta
+		 */
+		if (!i) {
+			g->xtick_zero = tx;
+			g->xtick_zero_val = tm[0].value;
+		} else if (i == 1) {
+			g->xtick_delta = (tm[1].value - tm[0].value) / (tx - g->xtick_zero);
+			g->xtick_one_val = tm[1].value;
+		}
+
 		/* really tx < yx || tx > x2, but protect against rounding */
 		if (x1 - tx > 0.01 || tx - x2 > 0.01)
 			continue;
 
 		/* Draw tick mark */
-		cairo_set_line_width(cr, 0.8);
+		cairo_set_line_width(cr, 1.0);
 		cairo_move_to(cr, tx, y2);
 		cairo_line_to(cr, tx, y2 + (y2 - y1) * 0.03);
 		cairo_stroke(cr);
 
 		/* draw grid lines */
 		cairo_save(cr);
-		cairo_set_dash(cr, dash, 2, 2.0);
-		cairo_set_line_width(cr, 0.5);
+		cairo_set_dash(cr, dash, 2, 0.66);
+		cairo_set_line_width(cr, 0.33);
 		cairo_move_to(cr, tx, y1);
 		cairo_line_to(cr, tx, y2);
 		cairo_stroke(cr);
@@ -365,9 +361,8 @@ static void graph_draw_x_ticks(struct graph *g, cairo_t *cr,
 			continue;
 
 		/* draw tickmark label */
-		draw_centered_text(g, cr, tx, y2 * 1.04, 12.0, tm[i].string);
+		draw_centered_text(cr, g->font, tx, y2 * 1.04, 12.0, tm[i].string);
 		cairo_stroke(cr);
-		
 	}
 }
 
@@ -378,7 +373,7 @@ static double graph_draw_y_ticks(struct graph *g, cairo_t *cr,
 	struct tickmark *tm;
 	double ty;
 	int i, power_of_ten;
-	static double dash[] = { 2.0, 2.0 };
+	static double dash[] = { 1.0, 2.0 };
 
 	nticks = calc_tickmarks(miny, maxy, nticks, &tm, &power_of_ten,
 		g->y_axis_unit_change_callback == NULL, g->base_offset);
@@ -395,6 +390,17 @@ static double graph_draw_y_ticks(struct graph *g, cairo_t *cr,
 	for (i = 0; i < nticks; i++) {
 		ty = y2 - (((tm[i].value) - miny) / (maxy - miny)) * (y2 - y1);
 
+		/*
+		 * Update tick delta
+		 */
+		if (!i) {
+			g->ytick_zero = ty;
+			g->ytick_zero_val = tm[0].value;
+		} else if (i == 1) {
+			g->ytick_delta = (tm[1].value - tm[0].value) / (ty - g->ytick_zero);
+			g->ytick_one_val = tm[1].value;
+		}
+
 		/* really ty < y1 || ty > y2, but protect against rounding */
 		if (y1 - ty > 0.01 || ty - y2 > 0.01)
 			continue;
@@ -406,8 +412,8 @@ static double graph_draw_y_ticks(struct graph *g, cairo_t *cr,
 
 		/* draw grid lines */
 		cairo_save(cr);
-		cairo_set_dash(cr, dash, 2, 2.0);
-		cairo_set_line_width(cr, 0.5);
+		cairo_set_dash(cr, dash, 2, 0.66);
+		cairo_set_line_width(cr, 0.33);
 		cairo_move_to(cr, x1, ty);
 		cairo_line_to(cr, x2, ty);
 		cairo_stroke(cr);
@@ -417,7 +423,7 @@ static double graph_draw_y_ticks(struct graph *g, cairo_t *cr,
 			continue;
 
 		/* draw tickmark label */
-		draw_right_justified_text(g, cr, x1 - (x2 - x1) * 0.025, ty, 12.0, tm[i].string);
+		draw_right_justified_text(cr, g->font, x1 - (x2 - x1) * 0.025, ty, 12.0, tm[i].string);
 		cairo_stroke(cr);
 	}
 
@@ -434,26 +440,27 @@ void bar_graph_draw(struct graph *bg, cairo_t *cr)
 	double label_offset, mindata, maxdata;
 	int i, nlabels;
 	struct graph_label *lb;
+	struct flist_head *entry;
 
 	cairo_save(cr);
 	cairo_translate(cr, bg->xoffset, bg->yoffset);
 	graph_draw_common(bg, cr, &x1, &y1, &x2, &y2);
 
-	nlabels = count_labels(bg->labels);
+	nlabels = count_labels(bg);
 	space_per_label = (x2 - x1) / (double) nlabels;
 
 	/*
 	 * Start bars at 0 unless we have negative values, otherwise we
 	 * present a skewed picture comparing label X and X+1.
 	 */
-	mindata = find_min_data(bg->labels);
+	mindata = find_min_data(bg);
 	if (mindata > 0)
 		mindata = 0;
 
-	maxdata = find_max_data(bg->labels);
+	maxdata = find_max_data(bg);
 
 	if (fabs(maxdata - mindata) < 1e-20) {
-		draw_centered_text(bg, cr,
+		draw_centered_text(cr, bg->font,
 			x1 + (x2 - x1) / 2.0,
 			y1 + (y2 - y1) / 2.0, 20.0, "No good data");
 		return;
@@ -461,15 +468,17 @@ void bar_graph_draw(struct graph *bg, cairo_t *cr)
 
 	maxdata = graph_draw_y_ticks(bg, cr, x1, y1, x2, y2, mindata, maxdata, 10, 1);
 	i = 0;
-	for (lb = bg->labels; lb; lb = lb->next) {
+	flist_for_each(entry, &bg->label_list) {
 		int nvalues;
-		nvalues = count_values(lb->values);
+
+		lb = flist_entry(entry, struct graph_label, list);
+		nvalues = count_values(lb);
 		bar_width = (space_per_label - space_per_label * 0.2) / (double) nvalues;
 		label_offset = bg->xdim * 0.1 + space_per_label * (double) i + space_per_label * 0.1;
 		draw_bars(bg, cr, lb, label_offset, bar_width, mindata, maxdata);
 		// draw_centered_text(cr, label_offset + (bar_width / 2.0 + bar_width * 0.1), bg->ydim * 0.93,
-		draw_centered_text(bg, cr, x1 + space_per_label * (i + 0.5), bg->ydim * 0.93,
-			12.0, lb->label); 
+		draw_centered_text(cr, bg->font, x1 + space_per_label * (i + 0.5), bg->ydim * 0.93,
+			12.0, lb->label);
 		i++;
 	}
 	cairo_stroke(cr);
@@ -495,19 +504,25 @@ static double find_xy_value(struct graph *g, xy_value_extractor getvalue, double
 	double tmp, answer = 0.0;
 	struct graph_label *i;
 	struct graph_value *j;
+	struct flist_head *jentry, *entry;
 	int first = 1;
 
-	for (i = g->labels; i; i = i->next)
-		for (j = i->values; j; j = j->next) {
+	flist_for_each(entry, &g->label_list) {
+		i = flist_entry(entry, struct graph_label, list);
+
+		flist_for_each(jentry, &i->value_list) {
+			j = flist_entry(jentry, struct graph_value, list);
 			tmp = getvalue(j);
 			if (first) {
 				first = 0;
 				answer = tmp;
 			}
-			answer = cmp(tmp, answer);	
+			answer = cmp(tmp, answer);
 		}
+	}
+
 	return answer;
-} 
+}
 
 void line_graph_draw(struct graph *g, cairo_t *cr)
 {
@@ -517,6 +532,7 @@ void line_graph_draw(struct graph *g, cairo_t *cr)
 	struct graph_label *i;
 	struct graph_value *j;
 	int good_data = 1, first = 1;
+	struct flist_head *entry, *lentry;
 
 	cairo_save(cr);
 	cairo_translate(cr, g->xoffset, g->yoffset);
@@ -570,42 +586,35 @@ void line_graph_draw(struct graph *g, cairo_t *cr)
 		goto skip_data;
 
 	cairo_set_line_width(cr, 1.5);
-	for (i = g->labels; i; i = i->next) {
+	cairo_set_line_join(cr, CAIRO_LINE_JOIN_ROUND);
+
+	flist_for_each(lentry, &g->label_list) {
+		i = flist_entry(lentry, struct graph_label, list);
 		first = 1;
-		if (i->r < 0) /* invisible data */
+		if (i->hide || i->r < 0) /* invisible data */
 			continue;
-		cairo_set_source_rgb(cr, i->r, i->g, i->b);
-		for (j = i->values; j; j = j->next) {
-			struct xyvalue *xy = j->value;
 
+		cairo_set_source_rgb(cr, i->r, i->g, i->b);
+		flist_for_each(entry, &i->value_list) {
+			j = flist_entry(entry, struct graph_value, list);
 			tx = ((getx(j) - gminx) / (gmaxx - gminx)) * (x2 - x1) + x1;
 			ty = y2 - ((gety(j) - gminy) / (gmaxy - gminy)) * (y2 - y1);
 			if (first) {
 				cairo_move_to(cr, tx, ty);
 				first = 0;
-			} else {
+			} else
 				cairo_line_to(cr, tx, ty);
-			}
-			xy->gx = tx;
-			xy->gy = ty;
 		}
 		cairo_stroke(cr);
 	}
 
 skip_data:
 	cairo_restore(cr);
-
-}
-
-static void gfree(void *f)
-{
-	if (f)
-		free(f);
 }
 
 static void setstring(char **str, const char *value)
 {
-	gfree(*str);
+	free(*str);
 	*str = strdup(value);
 }
 
@@ -627,56 +636,131 @@ void graph_y_title(struct graph *bg, const char *title)
 static struct graph_label *graph_find_label(struct graph *bg,
 				const char *label)
 {
+	struct flist_head *entry;
 	struct graph_label *i;
-	
-	for (i = bg->labels; i; i = i->next)
+
+	flist_for_each(entry, &bg->label_list) {
+		i = flist_entry(entry, struct graph_label, list);
+
 		if (strcmp(label, i->label) == 0)
 			return i;
+	}
+
 	return NULL;
 }
 
-void graph_add_label(struct graph *bg, const char *label)
+graph_label_t graph_add_label(struct graph *bg, const char *label)
 {
 	struct graph_label *i;
-	
+
 	i = graph_find_label(bg, label);
 	if (i)
-		return; /* already present. */
+		return i; /* already present. */
 	i = calloc(1, sizeof(*i));
+	INIT_FLIST_HEAD(&i->value_list);
 	i->parent = bg;
 	setstring(&i->label, label);
-	i->next = NULL;
-	if (!bg->tail)
-		bg->labels = i;
-	else
-		bg->tail->next = i;
-	bg->tail = i;
+	flist_add_tail(&i->list, &bg->label_list);
+	INIT_PRIO_TREE_ROOT(&i->prio_tree);
+	return i;
+}
+
+static void __graph_value_drop(struct graph_label *l, struct graph_value *v)
+{
+	flist_del_init(&v->list);
+	if (v->tooltip)
+		free(v->tooltip);
+	free(v->value);
+	free(v);
+	l->value_count--;
+}
+
+static void graph_value_drop(struct graph_label *l, struct graph_value *v)
+{
+	if (v->flags & GV_F_PRIO_SKIP) {
+		__graph_value_drop(l, v);
+		return;
+	}
+
+	/*
+	 * Find head, the guy that's on the prio tree
+	 */
+	while (!(v->flags & GV_F_ON_PRIO)) {
+		assert(!flist_empty(&v->alias));
+		v = flist_first_entry(&v->alias, struct graph_value, alias);
+	}
+
+	prio_tree_remove(&l->prio_tree, &v->node);
+
+	/*
+	 * Free aliases
+	 */
+	while (!flist_empty(&v->alias)) {
+		struct graph_value *a;
+
+		a = flist_first_entry(&v->alias, struct graph_value, alias);
+		flist_del_init(&a->alias);
+
+		__graph_value_drop(l, a);
+	}
+
+	__graph_value_drop(l, v);
 }
 
 static void graph_label_add_value(struct graph_label *i, void *value,
 				  const char *tooltip)
 {
+	struct graph *g = i->parent;
 	struct graph_value *x;
 
 	x = malloc(sizeof(*x));
+	memset(x, 0, sizeof(*x));
+	INIT_FLIST_HEAD(&x->alias);
+	INIT_FLIST_HEAD(&x->list);
+	flist_add_tail(&x->list, &i->value_list);
+	i->value_count++;
 	x->value = value;
-	if (tooltip)
+
+	if (tooltip) {
+		double xval = getx(x);
+		double minx = xval - (g->xtick_one_val * TOOLTIP_DELTA);
+		double maxx = xval + (g->xtick_one_val * TOOLTIP_DELTA);
+		struct prio_tree_node *ret;
+
+		/*
+		 * use msec to avoid dropping too much precision when
+		 * storing as an integer.
+		 */
+		minx = minx * 1000.0;
+		maxx = maxx * 1000.0;
+
+		INIT_PRIO_TREE_NODE(&x->node);
+		x->node.start = minx;
+		x->node.last = maxx;
 		x->tooltip = strdup(tooltip);
-	else
-		x->tooltip = NULL;
-	x->next = NULL;
-	if (!i->tail) {
-		i->values = x;
-	} else {
-		i->tail->next = x;
-	}
-	i->tail = x;
-	i->value_count++;
-	if (x->tooltip)
-		i->tooltip_count++;
+		if (x->node.last == x->node.start) {
+			x->node.last += fabs(g->xtick_delta);
+			if (x->node.last == x->node.start)
+				x->node.last++;
+		}
 
-	if (i->parent->per_label_limit != -1 &&
-		i->value_count > i->parent->per_label_limit) {
+		/*
+		 * If ret != &x->node, we have an alias. Since the values
+		 * should be identical, we can drop it
+		 */
+		ret = prio_tree_insert(&i->prio_tree, &x->node);
+		if (ret != &x->node) {
+			struct graph_value *alias;
+
+			alias = container_of(ret, struct graph_value, node);
+			flist_add_tail(&x->alias, &alias->alias);
+		} else
+			x->flags = GV_F_ON_PRIO;
+	} else
+		x->flags = GV_F_PRIO_SKIP;
+
+	if (g->per_label_limit != -1 &&
+		i->value_count > g->per_label_limit) {
 		int to_drop = 1;
 
 		/*
@@ -685,82 +769,105 @@ static void graph_label_add_value(struct graph_label *i, void *value,
 		 * entries. This will make us (eventually) reach the
 		 * specified limit.
 		 */
-		if (i->value_count - i->parent->per_label_limit >= 2)
+		if (i->value_count - g->per_label_limit >= 2)
 			to_drop = 2;
 
-		while (to_drop--) {
-			x = i->values;
-			i->values = i->values->next;
-			if (x->tooltip) {
-				free(x->tooltip);
-				i->tooltip_count--;
-			}
-			free(x->value);
-			free(x);
-			i->value_count--;
+		while (to_drop-- && !flist_empty(&i->value_list)) {
+			x = flist_first_entry(&i->value_list, struct graph_value, list);
+			graph_value_drop(i, x);
+
+			/*
+			 * If we have aliases, we could drop > 1 above.
+			 */
+			if (i->value_count <= g->per_label_limit)
+				break;
 		}
 	}
 }
 
-int graph_add_data(struct graph *bg, const char *label, const double value)
+int graph_add_data(struct graph *bg, graph_label_t label, const double value)
 {
-	struct graph_label *i;
+	struct graph_label *i = label;
 	double *d;
 
 	d = malloc(sizeof(*d));
 	*d = value;
 
-	i = graph_find_label(bg, label);
-	if (!i)
-		return -1;
 	graph_label_add_value(i, d, NULL);
 	return 0;
 }
 
-int graph_add_xy_data(struct graph *bg, const char *label,
+static int graph_nonzero_y(struct graph_label *l)
+{
+	struct flist_head *entry;
+
+	flist_for_each(entry, &l->value_list) {
+		struct graph_value *v;
+
+		v = flist_entry(entry, struct graph_value, list);
+		if (gety(v) != 0.0)
+			return 1;
+	}
+
+	return 0;
+}
+
+int graph_add_xy_data(struct graph *bg, graph_label_t label,
 		      const double x, const double y, const char *tooltip)
 {
-	struct graph_label *i;
+	struct graph_label *i = label;
 	struct xyvalue *xy;
 
+	if (bg->dont_graph_all_zeroes && y == 0.0 && !graph_nonzero_y(i))
+		i->hide = 1;
+	else
+		i->hide = 0;
+
 	xy = malloc(sizeof(*xy));
 	xy->x = x;
 	xy->y = y;
 
-	i = graph_find_label(bg, label);
-	if (!i)
-		return -1;
-
 	graph_label_add_value(i, xy, tooltip);
 	return 0;
 }
 
-static void graph_free_values(struct graph_value *values)
+static void graph_free_values(struct graph_label *l)
 {
-	struct graph_value *i, *next;
+	struct graph_value *i;
 
-	for (i = values; i; i = next) {
-		next = i->next;
-		gfree(i->value);
-		gfree(i);
-	}	
+	while (!flist_empty(&l->value_list)) {
+		i = flist_first_entry(&l->value_list, struct graph_value, list);
+		graph_value_drop(l, i);
+	}
 }
 
-static void graph_free_labels(struct graph_label *labels)
+static void graph_free_labels(struct graph *g)
 {
-	struct graph_label *i, *next;
+	struct graph_label *i;
 
-	for (i = labels; i; i = next) {
-		next = i->next;
-		graph_free_values(i->values);
-		gfree(i);
-	}	
+	while (!flist_empty(&g->label_list)) {
+		i = flist_first_entry(&g->label_list, struct graph_label, list);
+		flist_del(&i->list);
+		graph_free_values(i);
+		free(i);
+	}
 }
 
-void graph_set_color(struct graph *gr, const char *label,
-	double red, double green, double blue)
+void graph_clear_values(struct graph *g)
 {
+	struct flist_head *node;
 	struct graph_label *i;
+
+	flist_for_each(node, &g->label_list) {
+		i = flist_entry(node, struct graph_label, list);
+		graph_free_values(i);
+	}
+}
+
+void graph_set_color(struct graph *gr, graph_label_t label, double red,
+		     double green, double blue)
+{
+	struct graph_label *i = label;
 	double r, g, b;
 
 	if (red < 0.0) { /* invisible color */
@@ -777,24 +884,20 @@ void graph_set_color(struct graph *gr, const char *label,
 		if (g > 1.0)
 			g = 1.0;
 		if (b > 1.0)
-			b =1.0;
+			b = 1.0;
 	}
 
-	for (i = gr->labels; i; i = i->next)
-		if (strcmp(i->label, label) == 0) {
-			i->r = r;	
-			i->g = g;	
-			i->b = b;	
-			break;
-		}
+	i->r = r;
+	i->g = g;
+	i->b = b;
 }
 
 void graph_free(struct graph *bg)
 {
-	gfree(bg->title);
-	gfree(bg->xtitle);
-	gfree(bg->ytitle);
-	graph_free_labels(bg->labels);
+	free(bg->title);
+	free(bg->xtitle);
+	free(bg->ytitle);
+	graph_free_labels(bg);
 }
 
 /* For each line in the line graph, up to per_label_limit segments may
@@ -806,13 +909,14 @@ void line_graph_set_data_count_limit(struct graph *g, int per_label_limit)
 	g->per_label_limit = per_label_limit;
 }
 
-void graph_add_extra_space(struct graph *g, double left_percent, double right_percent,
-                                double top_percent, double bottom_percent)
+void graph_add_extra_space(struct graph *g, double left_percent,
+			   double right_percent, double top_percent,
+			   double bottom_percent)
 {
-	g->left_extra = left_percent;	
-	g->right_extra = right_percent;	
-	g->top_extra = top_percent;	
-	g->bottom_extra = bottom_percent;	
+	g->left_extra = left_percent;
+	g->right_extra = right_percent;
+	g->top_extra = top_percent;
+	g->bottom_extra = bottom_percent;
 }
 
 /*
@@ -827,11 +931,15 @@ void graph_set_base_offset(struct graph *g, unsigned int base_offset)
 
 int graph_has_tooltips(struct graph *g)
 {
+	struct flist_head *entry;
 	struct graph_label *i;
 
-	for (i = g->labels; i; i = i->next)
-		if (i->tooltip_count)
+	flist_for_each(entry, &g->label_list) {
+		i = flist_entry(entry, struct graph_label, list);
+
+		if (!prio_tree_empty(&i->prio_tree))
 			return 1;
+	}
 
 	return 0;
 }
@@ -846,27 +954,80 @@ int graph_contains_xy(struct graph *g, int x, int y)
 	return (x >= first_x && x <= last_x) && (y >= first_y && y <= last_y);
 }
 
-static int xy_match(struct xyvalue *xy, int x, int y)
+const char *graph_find_tooltip(struct graph *g, int ix, int iy)
 {
-	int xdiff = abs(xy->gx - x);
-	int ydiff = abs(xy->gy - y);
+	double x = ix, y = iy;
+	struct prio_tree_iter iter;
+	struct prio_tree_node *n;
+	struct graph_value *best = NULL;
+	struct flist_head *entry;
+	double best_delta;
+	double maxy, miny;
+
+	x -= g->xoffset;
+	y -= g->yoffset;
+
+	x = g->xtick_zero_val + ((x - g->xtick_zero) * g->xtick_delta);
+	y = g->ytick_zero_val + ((y - g->ytick_zero) * g->ytick_delta);
+
+	x = x * 1000.0;
+	maxy = y + (g->ytick_one_val * TOOLTIP_DELTA);
+	miny = y - (g->ytick_one_val * TOOLTIP_DELTA);
+	best_delta = UINT_MAX;
+	flist_for_each(entry, &g->label_list) {
+		struct graph_label *i;
+
+		i = flist_entry(entry, struct graph_label, list);
+		if (i->hide)
+			continue;
 
-	return xdiff <= 10 && ydiff <= 10;
-}
+		INIT_PRIO_TREE_ITER(&iter);
+		prio_tree_iter_init(&iter, &i->prio_tree, x, x);
 
-const char *graph_find_tooltip(struct graph *g, int x, int y)
-{
-	struct graph_label *i;
-	struct graph_value *j;
+		n = prio_tree_next(&iter);
+		if (!n)
+			continue;
 
-	for (i = g->labels; i; i = i->next) {
-		for (j = i->values; j; j = j->next) {
-			struct xyvalue *xy = j->value;
+		do {
+			struct graph_value *v, *rootv;
+			double yval, ydiff;
+
+			v = container_of(n, struct graph_value, node);
+			rootv = v;
+			do {
+				yval = gety(v);
+				ydiff = fabs(yval - y);
+
+				/*
+				 * zero delta, or within or match critera, break
+				 */
+				if (ydiff < best_delta) {
+					best_delta = ydiff;
+					if (!best_delta ||
+					    (yval >= miny && yval <= maxy)) {
+						best = v;
+						break;
+					}
+				}
+				if (!flist_empty(&v->alias))
+					v = flist_first_entry(&v->alias, struct graph_value, alias);
+			} while (v != rootv);
+		} while ((n = prio_tree_next(&iter)) != NULL);
 
-			if (xy_match(xy, x - g->xoffset, y))
-				return j->tooltip;
-		}
+		/*
+		 * If we got matches in one label, don't check others.
+		 */
+		if (best)
+			break;
 	}
 
+	if (best)
+		return best->tooltip;
+
 	return NULL;
 }
+
+void graph_set_graph_all_zeroes(struct graph *g, unsigned int set)
+{
+	g->dont_graph_all_zeroes = !set;
+}