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