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