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