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 = 0.0, 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, double *x1,
 271                               double *y1, double *x2, double *y2)
 272 {
 273         const double shade_col[3][3] = { { 0.55, 0.54, 0.54 },
 274                                          { 0.80, 0.78, 0.78 },
 275                                          { 0.93, 0.91, 0.91 } };
 276         int i;
 277
 278         *x1 = 0.10 * g->xdim;
 279         *x2 = 0.95 * g->xdim;
 280         *y1 = 0.10 * g->ydim;
 281         *y2 = 0.90 * g->ydim;
 282
 283         /*
 284          * Add shade
 285          */
 286         cairo_set_line_width(cr, 1.0);
 287         for (i = 0; i < 3; i++) {
 288                 float offset = i + 1.0;
 289
 290                 cairo_set_source_rgb(cr, shade_col[i][0], shade_col[i][1], shade_col[i][2]);
 291                 cairo_move_to(cr, offset + *x1, *y1 - offset);
 292                 cairo_line_to(cr, *x2 + offset, *y1 - offset);
 293                 cairo_line_to(cr, *x2 + offset, *y2 - offset);
 294                 cairo_stroke(cr);
 295         }
 296
 297         cairo_set_source_rgb(cr, 0, 0, 0);
 298         cairo_set_line_width(cr, 1.2);
 299
 300         cairo_move_to(cr, *x1, *y1);
 301         cairo_line_to(cr, *x1, *y2);
 302         cairo_line_to(cr, *x2, *y2);
 303         cairo_line_to(cr, *x2, *y1);
 304         cairo_line_to(cr, *x1, *y1);
 305         cairo_stroke(cr);
 306
 307         draw_centered_text(cr, g->font, g->xdim / 2, g->ydim / 20, 20.0, g->title);
 308         draw_centered_text(cr, g->font, g->xdim / 2, g->ydim * 0.97, 14.0, g->xtitle);
 309         draw_vertical_centered_text(cr, g->font, g->xdim * 0.02, g->ydim / 2, 14.0, g->ytitle);
 310         cairo_stroke(cr);
 311 }
 312
 313 static void graph_draw_x_ticks(struct graph *g, cairo_t *cr,
 314         double x1, double y1, double x2, double y2,
 315         double minx, double maxx, int nticks, int add_tm_text)
 316 {
 317         struct tickmark *tm;
 318         double tx;
 319         int i, power_of_ten;
 320         static double dash[] = { 1.0, 2.0 };
 321
 322         nticks = calc_tickmarks(minx, maxx, nticks, &tm, &power_of_ten,
 323                 g->x_axis_unit_change_callback == NULL, g->base_offset);
 324         if (g->x_axis_unit_change_callback)
 325                 g->x_axis_unit_change_callback(g, power_of_ten);
 326
 327         for (i = 0; i < nticks; i++) {
 328                 tx = (((tm[i].value) - minx) / (maxx - minx)) * (x2 - x1) + x1;
 329
 330                 /*
 331                  * Update tick delta
 332                  */
 333                 if (!i) {
 334                         g->xtick_zero = tx;
 335                         g->xtick_zero_val = tm[0].value;
 336                 } else if (i == 1) {
 337                         g->xtick_delta = (tm[1].value - tm[0].value) / (tx - g->xtick_zero);
 338                         g->xtick_one_val = tm[1].value;
 339                 }
 340
 341                 /* really tx < yx || tx > x2, but protect against rounding */
 342                 if (x1 - tx > 0.01 || tx - x2 > 0.01)
 343                         continue;
 344
 345                 /* Draw tick mark */
 346                 cairo_set_line_width(cr, 1.0);
 347                 cairo_move_to(cr, tx, y2);
 348                 cairo_line_to(cr, tx, y2 + (y2 - y1) * 0.03);
 349                 cairo_stroke(cr);
 350
 351                 /* draw grid lines */
 352                 cairo_save(cr);
 353                 cairo_set_dash(cr, dash, 2, 0.66);
 354                 cairo_set_line_width(cr, 0.33);
 355                 cairo_move_to(cr, tx, y1);
 356                 cairo_line_to(cr, tx, y2);
 357                 cairo_stroke(cr);
 358                 cairo_restore(cr);
 359
 360                 if (!add_tm_text)
 361                         continue;
 362
 363                 /* draw tickmark label */
 364                 draw_centered_text(cr, g->font, tx, y2 * 1.04, 12.0, tm[i].string);
 365                 cairo_stroke(cr);
 366         }
 367 }
 368
 369 static double graph_draw_y_ticks(struct graph *g, cairo_t *cr,
 370         double x1, double y1, double x2, double y2,
 371         double miny, double maxy, int nticks, int add_tm_text)
 372 {
 373         struct tickmark *tm;
 374         double ty;
 375         int i, power_of_ten;
 376         static double dash[] = { 1.0, 2.0 };
 377
 378         nticks = calc_tickmarks(miny, maxy, nticks, &tm, &power_of_ten,
 379                 g->y_axis_unit_change_callback == NULL, g->base_offset);
 380         if (g->y_axis_unit_change_callback)
 381                 g->y_axis_unit_change_callback(g, power_of_ten);
 382
 383         /*
 384          * Use highest tickmark as top of graph, not highest value. Otherwise
 385          * it's impossible to see what the max value is, if the graph is
 386          * fairly flat.
 387          */
 388         maxy = tm[nticks - 1].value;
 389
 390         for (i = 0; i < nticks; i++) {
 391                 ty = y2 - (((tm[i].value) - miny) / (maxy - miny)) * (y2 - y1);
 392
 393                 /*
 394                  * Update tick delta
 395                  */
 396                 if (!i) {
 397                         g->ytick_zero = ty;
 398                         g->ytick_zero_val = tm[0].value;
 399                 } else if (i == 1) {
 400                         g->ytick_delta = (tm[1].value - tm[0].value) / (ty - g->ytick_zero);
 401                         g->ytick_one_val = tm[1].value;
 402                 }
 403
 404                 /* really ty < y1 || ty > y2, but protect against rounding */
 405                 if (y1 - ty > 0.01 || ty - y2 > 0.01)
 406                         continue;
 407
 408                 /* draw tick mark */
 409                 cairo_move_to(cr, x1, ty);
 410                 cairo_line_to(cr, x1 - (x2 - x1) * 0.02, ty);
 411                 cairo_stroke(cr);
 412
 413                 /* draw grid lines */
 414                 cairo_save(cr);
 415                 cairo_set_dash(cr, dash, 2, 0.66);
 416                 cairo_set_line_width(cr, 0.33);
 417                 cairo_move_to(cr, x1, ty);
 418                 cairo_line_to(cr, x2, ty);
 419                 cairo_stroke(cr);
 420                 cairo_restore(cr);
 421
 422                 if (!add_tm_text)
 423                         continue;
 424
 425                 /* draw tickmark label */
 426                 draw_right_justified_text(cr, g->font, x1 - (x2 - x1) * 0.025, ty, 12.0, tm[i].string);
 427                 cairo_stroke(cr);
 428         }
 429
 430         /*
 431          * Return new max to use
 432          */
 433         return maxy;
 434 }
 435
 436 void bar_graph_draw(struct graph *bg, cairo_t *cr)
 437 {
 438         double x1, y1, x2, y2;
 439         double space_per_label, bar_width;
 440         double label_offset, mindata, maxdata;
 441         int i, nlabels;
 442         struct graph_label *lb;
 443         struct flist_head *entry;
 444
 445         cairo_save(cr);
 446         cairo_translate(cr, bg->xoffset, bg->yoffset);
 447         graph_draw_common(bg, cr, &x1, &y1, &x2, &y2);
 448
 449         nlabels = count_labels(bg);
 450         space_per_label = (x2 - x1) / (double) nlabels;
 451
 452         /*
 453          * Start bars at 0 unless we have negative values, otherwise we
 454          * present a skewed picture comparing label X and X+1.
 455          */
 456         mindata = find_min_data(bg);
 457         if (mindata > 0)
 458                 mindata = 0;
 459
 460         maxdata = find_max_data(bg);
 461
 462         if (fabs(maxdata - mindata) < 1e-20) {
 463                 draw_centered_text(cr, bg->font,
 464                         x1 + (x2 - x1) / 2.0,
 465                         y1 + (y2 - y1) / 2.0, 20.0, "No good data");
 466                 return;
 467         }
 468
 469         maxdata = graph_draw_y_ticks(bg, cr, x1, y1, x2, y2, mindata, maxdata, 10, 1);
 470         i = 0;
 471         flist_for_each(entry, &bg->label_list) {
 472                 int nvalues;
 473
 474                 lb = flist_entry(entry, struct graph_label, list);
 475                 nvalues = count_values(lb);
 476                 bar_width = (space_per_label - space_per_label * 0.2) / (double) nvalues;
 477                 label_offset = bg->xdim * 0.1 + space_per_label * (double) i + space_per_label * 0.1;
 478                 draw_bars(bg, cr, lb, label_offset, bar_width, mindata, maxdata);
 479                 // draw_centered_text(cr, label_offset + (bar_width / 2.0 + bar_width * 0.1), bg->ydim * 0.93,
 480                 draw_centered_text(cr, bg->font, x1 + space_per_label * (i + 0.5), bg->ydim * 0.93,
 481                         12.0, lb->label);
 482                 i++;
 483         }
 484         cairo_stroke(cr);
 485         cairo_restore(cr);
 486 }
 487
 488 typedef double (*xy_value_extractor)(struct graph_value *v);
 489
 490 static double getx(struct graph_value *v)
 491 {
 492         struct xyvalue *xy = v->value;
 493         return xy->x;
 494 }
 495
 496 static double gety(struct graph_value *v)
 497 {
 498         struct xyvalue *xy = v->value;
 499         return xy->y;
 500 }
 501
 502 static double find_xy_value(struct graph *g, xy_value_extractor getvalue, double_comparator cmp)
 503 {
 504         double tmp, answer = 0.0;
 505         struct graph_label *i;
 506         struct graph_value *j;
 507         struct flist_head *jentry, *entry;
 508         int first = 1;
 509
 510         flist_for_each(entry, &g->label_list) {
 511                 i = flist_entry(entry, struct graph_label, list);
 512
 513                 flist_for_each(jentry, &i->value_list) {
 514                         j = flist_entry(jentry, struct graph_value, list);
 515                         tmp = getvalue(j);
 516                         if (first) {
 517                                 first = 0;
 518                                 answer = tmp;
 519                         }
 520                         answer = cmp(tmp, answer);
 521                 }
 522         }
 523
 524         return answer;
 525 }
 526
 527 void line_graph_draw(struct graph *g, cairo_t *cr)
 528 {
 529         double x1, y1, x2, y2;
 530         double minx, miny, maxx, maxy, gminx, gminy, gmaxx, gmaxy;
 531         double tx, ty, top_extra, bottom_extra, left_extra, right_extra;
 532         struct graph_label *i;
 533         struct graph_value *j;
 534         int good_data = 1, first = 1;
 535         struct flist_head *entry, *lentry;
 536
 537         cairo_save(cr);
 538         cairo_translate(cr, g->xoffset, g->yoffset);
 539         graph_draw_common(g, cr, &x1, &y1, &x2, &y2);
 540
 541         minx = find_xy_value(g, getx, mindouble);
 542         maxx = find_xy_value(g, getx, maxdouble);
 543         miny = find_xy_value(g, gety, mindouble);
 544
 545         /*
 546          * Start graphs at zero, unless we have a value below. Otherwise
 547          * it's hard to visually compare the read and write graph, since
 548          * the lowest valued one will be the floor of the graph view.
 549          */
 550         if (miny > 0)
 551                 miny = 0;
 552
 553         maxy = find_xy_value(g, gety, maxdouble);
 554
 555         if (fabs(maxx - minx) < 1e-20 || fabs(maxy - miny) < 1e-20) {
 556                 good_data = 0;
 557                 minx = 0.0;
 558                 miny = 0.0;
 559                 maxx = 10.0;
 560                 maxy = 100.0;
 561         }
 562
 563         top_extra = 0.0;
 564         bottom_extra = 0.0;
 565         left_extra = 0.0;
 566         right_extra = 0.0;
 567
 568         if (g->top_extra > 0.001)
 569                 top_extra = fabs(maxy - miny) * g->top_extra;
 570         if (g->bottom_extra > 0.001)
 571                 bottom_extra = fabs(maxy - miny) * g->bottom_extra;
 572         if (g->left_extra > 0.001)
 573                 left_extra = fabs(maxx - minx) * g->left_extra;
 574         if (g->right_extra > 0.001)
 575                 right_extra = fabs(maxx - minx) * g->right_extra;
 576
 577         gminx = minx - left_extra;
 578         gmaxx = maxx + right_extra;
 579         gminy = miny - bottom_extra;
 580         gmaxy = maxy + top_extra;
 581
 582         graph_draw_x_ticks(g, cr, x1, y1, x2, y2, gminx, gmaxx, 10, good_data);
 583         gmaxy = graph_draw_y_ticks(g, cr, x1, y1, x2, y2, gminy, gmaxy, 10, good_data);
 584
 585         if (!good_data)
 586                 goto skip_data;
 587
 588         cairo_set_line_width(cr, 1.5);
 589         cairo_set_line_join(cr, CAIRO_LINE_JOIN_ROUND);
 590
 591         flist_for_each(lentry, &g->label_list) {
 592                 i = flist_entry(lentry, struct graph_label, list);
 593                 first = 1;
 594                 if (i->hide || i->r < 0) /* invisible data */
 595                         continue;
 596
 597                 cairo_set_source_rgb(cr, i->r, i->g, i->b);
 598                 flist_for_each(entry, &i->value_list) {
 599                         j = flist_entry(entry, struct graph_value, list);
 600                         tx = ((getx(j) - gminx) / (gmaxx - gminx)) * (x2 - x1) + x1;
 601                         ty = y2 - ((gety(j) - gminy) / (gmaxy - gminy)) * (y2 - y1);
 602                         if (first) {
 603                                 cairo_move_to(cr, tx, ty);
 604                                 first = 0;
 605                         } else
 606                                 cairo_line_to(cr, tx, ty);
 607                 }
 608                 cairo_stroke(cr);
 609         }
 610
 611 skip_data:
 612         cairo_restore(cr);
 613 }
 614
 615 static void setstring(char **str, const char *value)
 616 {
 617         free(*str);
 618         *str = strdup(value);
 619 }
 620
 621 void graph_title(struct graph *bg, const char *title)
 622 {
 623         setstring(&bg->title, title);
 624 }
 625
 626 void graph_x_title(struct graph *bg, const char *title)
 627 {
 628         setstring(&bg->xtitle, title);
 629 }
 630
 631 void graph_y_title(struct graph *bg, const char *title)
 632 {
 633         setstring(&bg->ytitle, title);
 634 }
 635
 636 static struct graph_label *graph_find_label(struct graph *bg,
 637                                 const char *label)
 638 {
 639         struct flist_head *entry;
 640         struct graph_label *i;
 641
 642         flist_for_each(entry, &bg->label_list) {
 643                 i = flist_entry(entry, struct graph_label, list);
 644
 645                 if (strcmp(label, i->label) == 0)
 646                         return i;
 647         }
 648
 649         return NULL;
 650 }
 651
 652 graph_label_t graph_add_label(struct graph *bg, const char *label)
 653 {
 654         struct graph_label *i;
 655
 656         i = graph_find_label(bg, label);
 657         if (i)
 658                 return i; /* already present. */
 659         i = calloc(1, sizeof(*i));
 660         INIT_FLIST_HEAD(&i->value_list);
 661         i->parent = bg;
 662         setstring(&i->label, label);
 663         flist_add_tail(&i->list, &bg->label_list);
 664         INIT_PRIO_TREE_ROOT(&i->prio_tree);
 665         return i;
 666 }
 667
 668 static void __graph_value_drop(struct graph_label *l, struct graph_value *v)
 669 {
 670         flist_del_init(&v->list);
 671         if (v->tooltip)
 672                 free(v->tooltip);
 673         free(v->value);
 674         free(v);
 675         l->value_count--;
 676 }
 677
 678 static void graph_value_drop(struct graph_label *l, struct graph_value *v)
 679 {
 680         if (v->flags & GV_F_PRIO_SKIP) {
 681                 __graph_value_drop(l, v);
 682                 return;
 683         }
 684
 685         /*
 686          * Find head, the guy that's on the prio tree
 687          */
 688         while (!(v->flags & GV_F_ON_PRIO)) {
 689                 assert(!flist_empty(&v->alias));
 690                 v = flist_first_entry(&v->alias, struct graph_value, alias);
 691         }
 692
 693         prio_tree_remove(&l->prio_tree, &v->node);
 694
 695         /*
 696          * Free aliases
 697          */
 698         while (!flist_empty(&v->alias)) {
 699                 struct graph_value *a;
 700
 701                 a = flist_first_entry(&v->alias, struct graph_value, alias);
 702                 flist_del_init(&a->alias);
 703
 704                 __graph_value_drop(l, a);
 705         }
 706
 707         __graph_value_drop(l, v);
 708 }
 709
 710 static void graph_label_add_value(struct graph_label *i, void *value,
 711                                   const char *tooltip)
 712 {
 713         struct graph *g = i->parent;
 714         struct graph_value *x;
 715
 716         x = malloc(sizeof(*x));
 717         memset(x, 0, sizeof(*x));
 718         INIT_FLIST_HEAD(&x->alias);
 719         INIT_FLIST_HEAD(&x->list);
 720         flist_add_tail(&x->list, &i->value_list);
 721         i->value_count++;
 722         x->value = value;
 723
 724         if (tooltip) {
 725                 double xval = getx(x);
 726                 double minx = xval - (g->xtick_one_val * TOOLTIP_DELTA);
 727                 double maxx = xval + (g->xtick_one_val * TOOLTIP_DELTA);
 728                 struct prio_tree_node *ret;
 729
 730                 /*
 731                  * use msec to avoid dropping too much precision when
 732                  * storing as an integer.
 733                  */
 734                 minx = minx * 1000.0;
 735                 maxx = maxx * 1000.0;
 736
 737                 INIT_PRIO_TREE_NODE(&x->node);
 738                 x->node.start = minx;
 739                 x->node.last = maxx;
 740                 x->tooltip = strdup(tooltip);
 741                 if (x->node.last == x->node.start) {
 742                         x->node.last += fabs(g->xtick_delta);
 743                         if (x->node.last == x->node.start)
 744                                 x->node.last++;
 745                 }
 746
 747                 /*
 748                  * If ret != &x->node, we have an alias. Since the values
 749                  * should be identical, we can drop it
 750                  */
 751                 ret = prio_tree_insert(&i->prio_tree, &x->node);
 752                 if (ret != &x->node) {
 753                         struct graph_value *alias;
 754
 755                         alias = container_of(ret, struct graph_value, node);
 756                         flist_add_tail(&x->alias, &alias->alias);
 757                 } else
 758                         x->flags = GV_F_ON_PRIO;
 759         } else
 760                 x->flags = GV_F_PRIO_SKIP;
 761
 762         if (g->per_label_limit != -1 &&
 763                 i->value_count > g->per_label_limit) {
 764                 int to_drop = 1;
 765
 766                 /*
 767                  * If the limit was dynamically reduced, making us more
 768                  * than 1 entry ahead after adding this one, drop two
 769                  * entries. This will make us (eventually) reach the
 770                  * specified limit.
 771                  */
 772                 if (i->value_count - g->per_label_limit >= 2)
 773                         to_drop = 2;
 774
 775                 while (to_drop-- && !flist_empty(&i->value_list)) {
 776                         x = flist_first_entry(&i->value_list, struct graph_value, list);
 777                         graph_value_drop(i, x);
 778
 779                         /*
 780                          * If we have aliases, we could drop > 1 above.
 781                          */
 782                         if (i->value_count <= g->per_label_limit)
 783                                 break;
 784                 }
 785         }
 786 }
 787
 788 int graph_add_data(struct graph *bg, graph_label_t label, const double value)
 789 {
 790         struct graph_label *i = label;
 791         double *d;
 792
 793         d = malloc(sizeof(*d));
 794         *d = value;
 795
 796         graph_label_add_value(i, d, NULL);
 797         return 0;
 798 }
 799
 800 static int graph_nonzero_y(struct graph_label *l)
 801 {
 802         struct flist_head *entry;
 803
 804         flist_for_each(entry, &l->value_list) {
 805                 struct graph_value *v;
 806
 807                 v = flist_entry(entry, struct graph_value, list);
 808                 if (gety(v) != 0.0)
 809                         return 1;
 810         }
 811
 812         return 0;
 813 }
 814
 815 int graph_add_xy_data(struct graph *bg, graph_label_t label,
 816                       const double x, const double y, const char *tooltip)
 817 {
 818         struct graph_label *i = label;
 819         struct xyvalue *xy;
 820
 821         if (bg->dont_graph_all_zeroes && y == 0.0 && !graph_nonzero_y(i))
 822                 i->hide = 1;
 823         else
 824                 i->hide = 0;
 825
 826         xy = malloc(sizeof(*xy));
 827         xy->x = x;
 828         xy->y = y;
 829
 830         graph_label_add_value(i, xy, tooltip);
 831         return 0;
 832 }
 833
 834 static void graph_free_values(struct graph_label *l)
 835 {
 836         struct graph_value *i;
 837
 838         while (!flist_empty(&l->value_list)) {
 839                 i = flist_first_entry(&l->value_list, struct graph_value, list);
 840                 graph_value_drop(l, i);
 841         }
 842 }
 843
 844 static void graph_free_labels(struct graph *g)
 845 {
 846         struct graph_label *i;
 847
 848         while (!flist_empty(&g->label_list)) {
 849                 i = flist_first_entry(&g->label_list, struct graph_label, list);
 850                 flist_del(&i->list);
 851                 graph_free_values(i);
 852                 free(i);
 853         }
 854 }
 855
 856 void graph_clear_values(struct graph *g)
 857 {
 858         struct flist_head *node;
 859         struct graph_label *i;
 860
 861         flist_for_each(node, &g->label_list) {
 862                 i = flist_entry(node, struct graph_label, list);
 863                 graph_free_values(i);
 864         }
 865 }
 866
 867 void graph_set_color(struct graph *gr, graph_label_t label, double red,
 868                      double green, double blue)
 869 {
 870         struct graph_label *i = label;
 871         double r, g, b;
 872
 873         if (red < 0.0) { /* invisible color */
 874                 r = -1.0;
 875                 g = -1.0;
 876                 b = -1.0;
 877         } else {
 878                 r = fabs(red);
 879                 g = fabs(green);
 880                 b = fabs(blue);
 881
 882                 if (r > 1.0)
 883                         r = 1.0;
 884                 if (g > 1.0)
 885                         g = 1.0;
 886                 if (b > 1.0)
 887                         b = 1.0;
 888         }
 889
 890         i->r = r;
 891         i->g = g;
 892         i->b = b;
 893 }
 894
 895 void graph_free(struct graph *bg)
 896 {
 897         free(bg->title);
 898         free(bg->xtitle);
 899         free(bg->ytitle);
 900         graph_free_labels(bg);
 901 }
 902
 903 /* For each line in the line graph, up to per_label_limit segments may
 904  * be added.  After that, adding more data to the end of the line
 905  * causes data to drop off of the front of the line.
 906  */
 907 void line_graph_set_data_count_limit(struct graph *g, int per_label_limit)
 908 {
 909         g->per_label_limit = per_label_limit;
 910 }
 911
 912 void graph_add_extra_space(struct graph *g, double left_percent,
 913                            double right_percent, double top_percent,
 914                            double bottom_percent)
 915 {
 916         g->left_extra = left_percent;
 917         g->right_extra = right_percent;
 918         g->top_extra = top_percent;
 919         g->bottom_extra = bottom_percent;
 920 }
 921
 922 /*
 923  * Normally values are logged in a base unit of 0, but for other purposes
 924  * it makes more sense to log in higher unit. For instance for bandwidth
 925  * purposes, you may want to log in KB/sec (or MB/sec) rather than bytes/sec.
 926  */
 927 void graph_set_base_offset(struct graph *g, unsigned int base_offset)
 928 {
 929         g->base_offset = base_offset;
 930 }
 931
 932 int graph_has_tooltips(struct graph *g)
 933 {
 934         struct flist_head *entry;
 935         struct graph_label *i;
 936
 937         flist_for_each(entry, &g->label_list) {
 938                 i = flist_entry(entry, struct graph_label, list);
 939
 940                 if (!prio_tree_empty(&i->prio_tree))
 941                         return 1;
 942         }
 943
 944         return 0;
 945 }
 946
 947 int graph_contains_xy(struct graph *g, int x, int y)
 948 {
 949         int first_x = g->xoffset;
 950         int last_x = g->xoffset + g->xdim;
 951         int first_y = g->yoffset;
 952         int last_y = g->yoffset + g->ydim;
 953
 954         return (x >= first_x && x <= last_x) && (y >= first_y && y <= last_y);
 955 }
 956
 957 const char *graph_find_tooltip(struct graph *g, int ix, int iy)
 958 {
 959         double x = ix, y = iy;
 960         struct prio_tree_iter iter;
 961         struct prio_tree_node *n;
 962         struct graph_value *best = NULL;
 963         struct flist_head *entry;
 964         double best_delta;
 965         double maxy, miny;
 966
 967         x -= g->xoffset;
 968         y -= g->yoffset;
 969
 970         x = g->xtick_zero_val + ((x - g->xtick_zero) * g->xtick_delta);
 971         y = g->ytick_zero_val + ((y - g->ytick_zero) * g->ytick_delta);
 972
 973         x = x * 1000.0;
 974         maxy = y + (g->ytick_one_val * TOOLTIP_DELTA);
 975         miny = y - (g->ytick_one_val * TOOLTIP_DELTA);
 976         best_delta = UINT_MAX;
 977         flist_for_each(entry, &g->label_list) {
 978                 struct graph_label *i;
 979
 980                 i = flist_entry(entry, struct graph_label, list);
 981                 if (i->hide)
 982                         continue;
 983
 984                 INIT_PRIO_TREE_ITER(&iter);
 985                 prio_tree_iter_init(&iter, &i->prio_tree, x, x);
 986
 987                 n = prio_tree_next(&iter);
 988                 if (!n)
 989                         continue;
 990
 991                 do {
 992                         struct graph_value *v, *rootv;
 993                         double yval, ydiff;
 994
 995                         v = container_of(n, struct graph_value, node);
 996                         rootv = v;
 997                         do {
 998                                 yval = gety(v);
 999                                 ydiff = fabs(yval - y);
1000
1001                                 /*
1002                                  * zero delta, or within or match critera, break
1003                                  */
1004                                 if (ydiff < best_delta) {
1005                                         best_delta = ydiff;
1006                                         if (!best_delta ||
1007                                             (yval >= miny && yval <= maxy)) {
1008                                                 best = v;
1009                                                 break;
1010                                         }
1011                                 }
1012                                 if (!flist_empty(&v->alias))
1013                                         v = flist_first_entry(&v->alias, struct graph_value, alias);
1014                         } while (v != rootv);
1015                 } while ((n = prio_tree_next(&iter)) != NULL);
1016
1017                 /*
1018                  * If we got matches in one label, don't check others.
1019                  */
1020                 if (best)
1021                         break;
1022         }
1023
1024         if (best)
1025                 return best->tooltip;
1026
1027         return NULL;
1028 }
1029
1030 void graph_set_graph_all_zeroes(struct graph *g, unsigned int set)
1031 {
1032         g->dont_graph_all_zeroes = !set;
1033 }