graph.c

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