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 *g, struct graph_label *i,
 686                                   void *value, 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         x->next = NULL;
 694         if (!i->tail)
 695                 i->values = x;
 696         else
 697                 i->tail->next = x;
 698         i->tail = x;
 699         i->value_count++;
 700
 701         if (tooltip) {
 702                 double yval = gety(x);
 703                 double miny = yval / TOOLTIP_DELTA;
 704                 double maxy = yval * TOOLTIP_DELTA;
 705                 struct prio_tree_node *ret;
 706
 707                 INIT_PRIO_TREE_NODE(&x->node);
 708                 x->node.start = miny;
 709                 x->node.last = maxy;
 710                 if (x->node.last == x->node.start) {
 711                         x->node.last += fabs(g->ytick_delta);
 712                         printf("last bumped to %lu\n", x->node.last);
 713                 }
 714
 715                 /*
 716                  * If ret != &x->node, we have an alias. Since the values
 717                  * should be identical, we can drop it
 718                  */
 719                 ret = prio_tree_insert(&i->prio_tree, &x->node);
 720                 if (ret == &x->node) {
 721                         x->tooltip = strdup(tooltip);
 722                         i->tooltip_count++;
 723                 }
 724         }
 725
 726         if (i->parent->per_label_limit != -1 &&
 727                 i->value_count > i->parent->per_label_limit) {
 728                 int to_drop = 1;
 729
 730                 /*
 731                  * If the limit was dynamically reduced, making us more
 732                  * than 1 entry ahead after adding this one, drop two
 733                  * entries. This will make us (eventually) reach the
 734                  * specified limit.
 735                  */
 736                 if (i->value_count - i->parent->per_label_limit >= 2)
 737                         to_drop = 2;
 738
 739                 while (to_drop--) {
 740                         x = i->values;
 741                         i->values = i->values->next;
 742                         if (x->tooltip) {
 743                                 free(x->tooltip);
 744                                 prio_tree_remove(&i->prio_tree, &x->node);
 745                                 i->tooltip_count--;
 746                         }
 747                         free(x->value);
 748                         free(x);
 749                         i->value_count--;
 750                 }
 751         }
 752 }
 753
 754 int graph_add_data(struct graph *bg, const char *label, const double value)
 755 {
 756         struct graph_label *i;
 757         double *d;
 758
 759         d = malloc(sizeof(*d));
 760         *d = value;
 761
 762         i = graph_find_label(bg, label);
 763         if (!i)
 764                 return -1;
 765         graph_label_add_value(bg, i, d, NULL);
 766         return 0;
 767 }
 768
 769 int graph_add_xy_data(struct graph *bg, const char *label,
 770                       const double x, const double y, const char *tooltip)
 771 {
 772         struct graph_label *i;
 773         struct xyvalue *xy;
 774
 775         xy = malloc(sizeof(*xy));
 776         xy->x = x;
 777         xy->y = y;
 778
 779         i = graph_find_label(bg, label);
 780         if (!i)
 781                 return -1;
 782
 783         graph_label_add_value(bg, i, xy, tooltip);
 784         return 0;
 785 }
 786
 787 static void graph_free_values(struct graph_label *l, struct graph_value *values)
 788 {
 789         struct graph_value *i, *next;
 790
 791         for (i = values; i; i = next) {
 792                 next = i->next;
 793                 free(i->value);
 794                 if (i->tooltip) {
 795                         free(i->tooltip);
 796                         prio_tree_remove(&l->prio_tree, &i->node);
 797                         l->tooltip_count--;
 798                 }
 799                 free(i);
 800         }
 801 }
 802
 803 static void graph_free_labels(struct graph_label *labels)
 804 {
 805         struct graph_label *i, *next;
 806
 807         for (i = labels; i; i = next) {
 808                 next = i->next;
 809                 graph_free_values(i, i->values);
 810                 free(i);
 811         }
 812 }
 813
 814 void graph_set_color(struct graph *gr, const char *label,
 815         double red, double green, double blue)
 816 {
 817         struct graph_label *i;
 818         double r, g, b;
 819
 820         if (red < 0.0) { /* invisible color */
 821                 r = -1.0;
 822                 g = -1.0;
 823                 b = -1.0;
 824         } else {
 825                 r = fabs(red);
 826                 g = fabs(green);
 827                 b = fabs(blue);
 828
 829                 if (r > 1.0)
 830                         r = 1.0;
 831                 if (g > 1.0)
 832                         g = 1.0;
 833                 if (b > 1.0)
 834                         b = 1.0;
 835         }
 836
 837         for (i = gr->labels; i; i = i->next)
 838                 if (strcmp(i->label, label) == 0) {
 839                         i->r = r;
 840                         i->g = g;
 841                         i->b = b;
 842                         break;
 843                 }
 844 }
 845
 846 void graph_free(struct graph *bg)
 847 {
 848         free(bg->title);
 849         free(bg->xtitle);
 850         free(bg->ytitle);
 851         graph_free_labels(bg->labels);
 852 }
 853
 854 /* For each line in the line graph, up to per_label_limit segments may
 855  * be added.  After that, adding more data to the end of the line
 856  * causes data to drop off of the front of the line.
 857  */
 858 void line_graph_set_data_count_limit(struct graph *g, int per_label_limit)
 859 {
 860         g->per_label_limit = per_label_limit;
 861 }
 862
 863 void graph_add_extra_space(struct graph *g, double left_percent, double right_percent,
 864                                 double top_percent, double bottom_percent)
 865 {
 866         g->left_extra = left_percent;
 867         g->right_extra = right_percent;
 868         g->top_extra = top_percent;
 869         g->bottom_extra = bottom_percent;
 870 }
 871
 872 /*
 873  * Normally values are logged in a base unit of 0, but for other purposes
 874  * it makes more sense to log in higher unit. For instance for bandwidth
 875  * purposes, you may want to log in KB/sec (or MB/sec) rather than bytes/sec.
 876  */
 877 void graph_set_base_offset(struct graph *g, unsigned int base_offset)
 878 {
 879         g->base_offset = base_offset;
 880 }
 881
 882 int graph_has_tooltips(struct graph *g)
 883 {
 884         struct graph_label *i;
 885
 886         for (i = g->labels; i; i = i->next)
 887                 if (i->tooltip_count)
 888                         return 1;
 889
 890         return 0;
 891 }
 892
 893 int graph_contains_xy(struct graph *g, int x, int y)
 894 {
 895         int first_x = g->xoffset;
 896         int last_x = g->xoffset + g->xdim;
 897         int first_y = g->yoffset;
 898         int last_y = g->yoffset + g->ydim;
 899
 900         return (x >= first_x && x <= last_x) && (y >= first_y && y <= last_y);
 901 }
 902
 903 const char *graph_find_tooltip(struct graph *g, int ix, int iy)
 904 {
 905         double x = ix, y = iy;
 906         struct prio_tree_iter iter;
 907         struct prio_tree_node *n;
 908         struct graph_label *i;
 909         struct graph_value *best = NULL;
 910         double best_delta;
 911         double maxx, minx;
 912
 913         x -= g->xoffset;
 914         y -= g->yoffset;
 915
 916         x = g->xtick_zero_val + ((x - g->xtick_zero) * g->xtick_delta);
 917         y = g->ytick_zero_val + ((y - g->ytick_zero) * g->ytick_delta);
 918
 919         maxx = x * TOOLTIP_DELTA;
 920         minx = x / TOOLTIP_DELTA;
 921         best_delta = UINT_MAX;
 922         i = g->labels;
 923         do {
 924                 INIT_PRIO_TREE_ITER(&iter);
 925                 prio_tree_iter_init(&iter, &i->prio_tree, y, y);
 926
 927                 n = prio_tree_next(&iter);
 928                 if (!n)
 929                         continue;
 930
 931                 do {
 932                         struct graph_value *v;
 933                         double xval, xdiff;
 934
 935                         v = container_of(n, struct graph_value, node);
 936                         xval = getx(v);
 937
 938                         if (xval > x)
 939                                 xdiff = xval - x;
 940                         else
 941                                 xdiff = x - xval;
 942
 943                         /*
 944                          * zero delta, or within or match critera, break
 945                          */
 946                         if (xdiff < best_delta) {
 947                                 best_delta = xdiff;
 948                                 if (!best_delta ||
 949                                     (xval >= minx && xval <= maxx)) {
 950                                         best = v;
 951                                         break;
 952                                 }
 953                         }
 954                 } while ((n = prio_tree_next(&iter)) != NULL);
 955
 956                 /*
 957                  * If we got matches in one label, don't check others.
 958                  */
 959                 break;
 960         } while ((i = i->next) != NULL);
 961
 962         if (best)
 963                 return best->tooltip;
 964
 965         return NULL;
 966 }