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