epan/stats_tree.c

   1 /* stats_tree.c
   2  * API for a counter tree for Wireshark
   3  * 2004, Luis E. G. Ontanon
   4  *
   5  * Wireshark - Network traffic analyzer
   6  * By Gerald Combs <gerald@wireshark.org>
   7  * Copyright 1998 Gerald Combs
   8  *
   9  * SPDX-License-Identifier: GPL-2.0-or-later
  10  */
  11
  12  /* stats_tree modifications by Deon van der Westhuysen, November 2013
  13   * support for
  14   *  - sorting by column,
  15   *  - calculation of average values
  16   *  - calculation of burst rate
  17   *  - export to text, CSV or XML file
  18   */
  19
  20 #include "config.h"
  21
  22 #include <glib.h>
  23
  24 #include <stdlib.h>
  25
  26 #include <epan/stats_tree_priv.h>
  27 #include <epan/prefs.h>
  28 #include <math.h>
  29 #include <string.h>
  30
  31 #include "strutil.h"
  32 #include "stats_tree.h"
  33
  34 enum _stat_tree_columns {
  35     COL_NAME,
  36     COL_COUNT,
  37     COL_AVERAGE,
  38     COL_MIN,
  39     COL_MAX,
  40     COL_RATE,
  41     COL_PERCENT,
  42     COL_BURSTRATE,
  43     COL_BURSTTIME,
  44     N_COLUMNS
  45 };
  46
  47 /* used to contain the registered stat trees */
  48 static GHashTable *registry = NULL;
  49
  50 /* a text representation of a node
  51 if buffer is NULL returns a newly allocated string */
  52 extern gchar*
  53 stats_tree_node_to_str(const stat_node *node, gchar *buffer, guint len)
  54 {
  55     if (buffer) {
  56         g_snprintf(buffer,len,"%s: %i",node->name, node->counter);
  57         return buffer;
  58     } else {
  59         return g_strdup_printf("%s: %i",node->name, node->counter);
  60     }
  61 }
  62
  63 extern guint
  64 stats_tree_branch_max_namelen(const stat_node *node, guint indent)
  65 {
  66     stat_node *child;
  67     guint maxlen = 0;
  68     guint len;
  69
  70     indent = indent > INDENT_MAX ? INDENT_MAX : indent;
  71
  72     if (node->children) {
  73         for (child = node->children; child; child = child->next ) {
  74             len = stats_tree_branch_max_namelen(child,indent+1);
  75             maxlen = len > maxlen ? len : maxlen;
  76         }
  77     }
  78
  79     if (node->st_flags&ST_FLG_ROOTCHILD) {
  80         gchar *display_name = stats_tree_get_displayname(node->name);
  81         len = (guint) strlen(display_name) + indent;
  82         g_free(display_name);
  83     }
  84     else {
  85     len = (guint) strlen(node->name) + indent;
  86     }
  87     maxlen = len > maxlen ? len : maxlen;
  88
  89     return maxlen;
  90 }
  91
  92 /* frees the resources allocated by a stat_tree node */
  93 static void
  94 free_stat_node(stat_node *node)
  95 {
  96     stat_node *child;
  97     stat_node *next;
  98     burst_bucket *bucket;
  99
 100     if (node->children) {
 101     for (child = node->children; child; child = next ) {
 102         /* child->next will be gone after free_stat_node, so cache it here */
 103         next = child->next;
 104         free_stat_node(child);
 105     }
 106     }
 107
 108     if (node->hash) g_hash_table_destroy(node->hash);
 109
 110     while (node->bh) {
 111         bucket = node->bh;
 112         node->bh = bucket->next;
 113         g_free(bucket);
 114     }
 115
 116     g_free(node->rng);
 117     g_free(node->name);
 118     g_free(node);
 119 }
 120
 121 /* destroys the whole tree instance */
 122 extern void
 123 stats_tree_free(stats_tree *st)
 124 {
 125     stat_node *child;
 126     stat_node *next;
 127
 128     if (!st) return;
 129
 130     g_free(st->filter);
 131     g_hash_table_destroy(st->names);
 132     g_ptr_array_free(st->parents,TRUE);
 133     g_free(st->display_name);
 134
 135     for (child = st->root.children; child; child = next ) {
 136         /* child->next will be gone after free_stat_node, so cache it here */
 137         next = child->next;
 138         free_stat_node(child);
 139     }
 140
 141     if (st->cfg->free_tree_pr)
 142         st->cfg->free_tree_pr(st);
 143
 144     if (st->cfg->cleanup)
 145         st->cfg->cleanup(st);
 146
 147     g_free(st);
 148 }
 149
 150
 151 /* reset a node to its original state */
 152 static void
 153 reset_stat_node(stat_node *node)
 154 {
 155     stat_node *child;
 156     burst_bucket *bucket;
 157
 158     node->counter = 0;
 159     node->total = 0;
 160     node->minvalue = G_MAXINT;
 161     node->maxvalue = G_MININT;
 162     node->st_flags = 0;
 163
 164     while (node->bh) {
 165         bucket = node->bh;
 166         node->bh = bucket->next;
 167         g_free(bucket);
 168     }
 169     node->bh = (burst_bucket*)g_malloc0(sizeof(burst_bucket));
 170     node->bt = node->bh;
 171     node->bcount = 0;
 172     node->max_burst = 0;
 173     node->burst_time = -1.0;
 174
 175     if (node->children) {
 176         for (child = node->children; child; child = child->next )
 177             reset_stat_node(child);
 178     }
 179 }
 180
 181 /* reset the whole stats_tree */
 182 extern void
 183 stats_tree_reset(void *p)
 184 {
 185     stats_tree *st = (stats_tree *)p;
 186
 187     st->start = -1.0;
 188     st->elapsed = 0.0;
 189     st->now = - 1.0;
 190
 191     reset_stat_node(&st->root);
 192 }
 193
 194 extern void
 195 stats_tree_reinit(void *p)
 196 {
 197     stats_tree *st = (stats_tree *)p;
 198     stat_node *child;
 199     stat_node *next;
 200
 201     for (child = st->root.children; child; child = next) {
 202         /* child->next will be gone after free_stat_node, so cache it here */
 203         next = child->next;
 204         free_stat_node(child);
 205     }
 206
 207     st->root.children = NULL;
 208     st->root.counter = 0;
 209     st->root.total = 0;
 210     st->root.minvalue = G_MAXINT;
 211     st->root.maxvalue = G_MININT;
 212     st->root.st_flags = 0;
 213
 214     st->root.bh = (burst_bucket*)g_malloc0(sizeof(burst_bucket));
 215     st->root.bt = st->root.bh;
 216     st->root.bcount = 0;
 217     st->root.max_burst = 0;
 218     st->root.burst_time = -1.0;
 219
 220     /* No more stat_nodes left in tree - clean out hash, array */
 221     g_hash_table_remove_all(st->names);
 222     if (st->parents->len>1) {
 223         g_ptr_array_remove_range(st->parents, 1, st->parents->len-1);
 224     }
 225
 226     /* Do not update st_flags for the tree (sorting) - leave as was */
 227     st->num_columns = N_COLUMNS;
 228     g_free(st->display_name);
 229     st->display_name = stats_tree_get_displayname(st->cfg->name);
 230
 231     if (st->cfg->init) {
 232         st->cfg->init(st);
 233     }
 234 }
 235
 236 static void
 237 stats_tree_cfg_free(gpointer p)
 238 {
 239     stats_tree_cfg* cfg = (stats_tree_cfg*)p;
 240     g_free(cfg->tapname);
 241     g_free(cfg->abbr);
 242     g_free(cfg->name);
 243     g_free(cfg);
 244 }
 245
 246 /* register a new stats_tree */
 247 extern void
 248 stats_tree_register_with_group(const char *tapname, const char *abbr, const char *name,
 249             guint flags,
 250             stat_tree_packet_cb packet, stat_tree_init_cb init,
 251             stat_tree_cleanup_cb cleanup, register_stat_group_t stat_group)
 252 {
 253     stats_tree_cfg *cfg = (stats_tree_cfg *)g_malloc0( sizeof(stats_tree_cfg) );
 254
 255     /* at the very least the abbrev and the packet function should be given */
 256     g_assert( tapname && abbr && packet );
 257
 258     cfg->tapname = g_strdup(tapname);
 259     cfg->abbr = g_strdup(abbr);
 260     cfg->name = name ? g_strdup(name) : g_strdup(abbr);
 261     cfg->stat_group = stat_group;
 262
 263     cfg->packet = packet;
 264     cfg->init = init;
 265     cfg->cleanup = cleanup;
 266
 267     cfg->flags = flags&~ST_FLG_MASK;
 268     cfg->st_flags = flags&ST_FLG_MASK;
 269
 270     if (!registry) registry = g_hash_table_new_full(g_str_hash,g_str_equal,NULL,stats_tree_cfg_free);
 271
 272     g_hash_table_insert(registry,cfg->abbr,cfg);
 273 }
 274
 275 /* register a new stats_tree with default group REGISTER_STAT_GROUP_UNSORTED */
 276 extern void
 277 stats_tree_register(const char *tapname, const char *abbr, const char *name,
 278             guint flags,
 279             stat_tree_packet_cb packet, stat_tree_init_cb init,
 280             stat_tree_cleanup_cb cleanup)
 281 {
 282     stats_tree_register_with_group(tapname, abbr, name,
 283             flags,
 284             packet, init,
 285             cleanup, REGISTER_STAT_GROUP_UNSORTED);
 286 }
 287
 288 /* register a new stat_tree with default group REGISTER_STAT_GROUP_UNSORTED from a plugin */
 289 extern void
 290 stats_tree_register_plugin(const char *tapname, const char *abbr, const char *name,
 291             guint flags,
 292             stat_tree_packet_cb packet, stat_tree_init_cb init,
 293             stat_tree_cleanup_cb cleanup)
 294 {
 295     stats_tree_cfg *cfg;
 296
 297     stats_tree_register(tapname, abbr, name,
 298             flags,
 299             packet, init,
 300             cleanup);
 301     cfg = stats_tree_get_cfg_by_abbr(abbr);
 302     cfg->plugin = TRUE;
 303 }
 304
 305 extern stats_tree*
 306 stats_tree_new(stats_tree_cfg *cfg, tree_pres *pr, const char *filter)
 307 {
 308     stats_tree *st = (stats_tree *)g_malloc0(sizeof(stats_tree));
 309
 310     st->cfg = cfg;
 311     st->pr = pr;
 312
 313     st->names = g_hash_table_new(g_str_hash,g_str_equal);
 314     st->parents = g_ptr_array_new();
 315     st->filter = g_strdup(filter);
 316
 317     st->start = -1.0;
 318     st->elapsed = 0.0;
 319
 320     st->root.minvalue = G_MAXINT;
 321     st->root.maxvalue = G_MININT;
 322
 323     st->root.bh = (burst_bucket*)g_malloc0(sizeof(burst_bucket));
 324     st->root.bt = st->root.bh;
 325     st->root.burst_time = -1.0;
 326
 327     st->root.name = stats_tree_get_displayname(cfg->name);
 328     st->root.st = st;
 329
 330     st->st_flags = st->cfg->st_flags;
 331
 332     if (!(st->st_flags&ST_FLG_SRTCOL_MASK)) {
 333         /* No default sort specified - use preferences */
 334         st->st_flags |= prefs.st_sort_defcolflag<<ST_FLG_SRTCOL_SHIFT;
 335         if (prefs.st_sort_defdescending) {
 336             st->st_flags |= ST_FLG_SORT_DESC;
 337         }
 338     }
 339     st->num_columns = N_COLUMNS;
 340     st->display_name = stats_tree_get_displayname(st->cfg->name);
 341
 342     g_ptr_array_add(st->parents,&st->root);
 343
 344     return st;
 345 }
 346
 347 /* will be the tap packet cb */
 348 extern int
 349 stats_tree_packet(void *p, packet_info *pinfo, epan_dissect_t *edt, const void *pri)
 350 {
 351     stats_tree *st = (stats_tree *)p;
 352
 353     st->now = nstime_to_msec(&pinfo->rel_ts);
 354     if (st->start < 0.0) st->start = st->now;
 355
 356     st->elapsed = st->now - st->start;
 357
 358     if (st->cfg->packet)
 359         return st->cfg->packet(st,pinfo,edt,pri);
 360     else
 361         return 0;
 362 }
 363
 364 extern stats_tree_cfg*
 365 stats_tree_get_cfg_by_abbr(const char *abbr)
 366 {
 367     if (!abbr) return NULL;
 368     return (stats_tree_cfg *)g_hash_table_lookup(registry,abbr);
 369 }
 370
 371 static gint
 372 compare_stat_menu_item(gconstpointer stat_a, gconstpointer stat_b)
 373 {
 374     const stats_tree_cfg* stat_cfg_a = (const stats_tree_cfg*)stat_a;
 375     const stats_tree_cfg* stat_cfg_b = (const stats_tree_cfg*)stat_b;
 376
 377     return strcmp(stat_cfg_a->name, stat_cfg_b->name);
 378 }
 379
 380 extern GList*
 381 stats_tree_get_cfg_list(void)
 382 {
 383     GList* registry_list = g_hash_table_get_values(registry);
 384     /* Now sort the list so they can show up in the
 385        menu alphabetically */
 386     return g_list_sort(registry_list, compare_stat_menu_item);
 387
 388 }
 389
 390 struct _stats_tree_pres_cbs {
 391     void (*setup_node_pr)(stat_node*);
 392     void (*free_tree_pr)(stats_tree*);
 393 };
 394
 395 static void
 396 setup_tree_presentation(gpointer k _U_, gpointer v, gpointer p)
 397 {
 398     stats_tree_cfg *cfg = (stats_tree_cfg *)v;
 399     struct _stats_tree_pres_cbs *d = (struct _stats_tree_pres_cbs *)p;
 400
 401     cfg->setup_node_pr = d->setup_node_pr;
 402     cfg->free_tree_pr = d->free_tree_pr;
 403
 404 }
 405
 406 extern void
 407 stats_tree_presentation(void (*registry_iterator)(gpointer,gpointer,gpointer),
 408             void (*setup_node_pr)(stat_node*),
 409             void (*free_tree_pr)(stats_tree*),
 410             void *data)
 411 {
 412     static struct _stats_tree_pres_cbs d;
 413
 414     d.setup_node_pr = setup_node_pr;
 415     d.free_tree_pr = free_tree_pr;
 416
 417     if (registry) g_hash_table_foreach(registry,setup_tree_presentation,&d);
 418
 419     if (registry_iterator && registry)
 420         g_hash_table_foreach(registry,registry_iterator,data);
 421
 422 }
 423
 424
 425 /* creates a stat_tree node
 426 *    name: the name of the stats_tree node
 427 *    parent_name: the name of the ALREADY REGISTERED parent
 428 *    with_hash: whether or not it should keep a hash with its children names
 429 *    as_named_node: whether or not it has to be registered in the root namespace
 430 */
 431 static stat_node*
 432 new_stat_node(stats_tree *st, const gchar *name, int parent_id,
 433           gboolean with_hash, gboolean as_parent_node)
 434 {
 435
 436     stat_node *node = (stat_node *)g_malloc0(sizeof(stat_node));
 437     stat_node *last_chld = NULL;
 438
 439     node->minvalue = G_MAXINT;
 440     node->maxvalue = G_MININT;
 441     node->st_flags = parent_id?0:ST_FLG_ROOTCHILD;
 442
 443     node->bh = (burst_bucket*)g_malloc0(sizeof(burst_bucket));
 444     node->bt = node->bh;
 445     node->burst_time = -1.0;
 446
 447     node->name = g_strdup(name);
 448     node->st = (stats_tree*) st;
 449     node->hash = with_hash ? g_hash_table_new(g_str_hash,g_str_equal) : NULL;
 450
 451     if (as_parent_node) {
 452         g_hash_table_insert(st->names,
 453                             node->name,
 454                             node);
 455
 456         g_ptr_array_add(st->parents,node);
 457
 458         node->id = st->parents->len - 1;
 459     } else {
 460         node->id = -1;
 461     }
 462
 463     if (parent_id >= 0 && parent_id < (int) st->parents->len ) {
 464         node->parent = (stat_node *)g_ptr_array_index(st->parents,parent_id);
 465     } else {
 466         /* ??? should we set the parent to be root ??? */
 467         g_assert_not_reached();
 468     }
 469
 470     if (node->parent->children) {
 471         /* insert as last child */
 472
 473         for (last_chld = node->parent->children;
 474              last_chld->next;
 475              last_chld = last_chld->next ) ;
 476
 477         last_chld->next = node;
 478
 479     } else {
 480         /* insert as first child */
 481         node->parent->children = node;
 482     }
 483
 484     if(node->parent->hash) {
 485         g_hash_table_insert(node->parent->hash,node->name,node);
 486     }
 487
 488     if (st->cfg->setup_node_pr) {
 489         st->cfg->setup_node_pr(node);
 490     } else {
 491         node->pr = NULL;
 492     }
 493
 494     return node;
 495 }
 496 /***/
 497
 498 extern int
 499 stats_tree_create_node(stats_tree *st, const gchar *name, int parent_id, gboolean with_hash)
 500 {
 501     stat_node *node = new_stat_node(st,name,parent_id,with_hash,TRUE);
 502
 503     if (node)
 504         return node->id;
 505     else
 506         return 0;
 507 }
 508
 509 /* XXX: should this be a macro? */
 510 extern int
 511 stats_tree_create_node_by_pname(stats_tree *st, const gchar *name,
 512                 const gchar *parent_name, gboolean with_children)
 513 {
 514     return stats_tree_create_node(st,name,stats_tree_parent_id_by_name(st,parent_name),with_children);
 515 }
 516
 517 /* Internal function to update the burst calculation data - add entry to bucket */
 518 static void
 519 update_burst_calc(stat_node *node, gint value)
 520 {
 521     double current_bucket;
 522     double burstwin;
 523
 524     burst_bucket *bn;
 525
 526     if (!prefs.st_enable_burstinfo) {
 527         return;
 528     }
 529
 530     /* NB thebucket list should always contain at least one node - even if it is */
 531     /* the dummy created at init time. Head and tail should never be NULL!       */
 532     current_bucket = floor(node->st->now/prefs.st_burst_resolution);
 533     burstwin = prefs.st_burst_windowlen/prefs.st_burst_resolution;
 534     if (current_bucket>node->bt->bucket_no) {
 535         /* Must add a new bucket at the burst list tail */
 536         bn = (burst_bucket*)g_malloc0(sizeof(burst_bucket));
 537         bn->count = value;
 538         bn->bucket_no = current_bucket;
 539         bn->start_time = node->st->now;
 540         bn->prev = node->bt;
 541         node->bt->next = bn;
 542         node->bt = bn;
 543         /* And add value to the current burst count for node */
 544         node->bcount += value;
 545         /* Check if bucket list head is now too old and must be removed */
 546         while (current_bucket>=(node->bh->bucket_no+burstwin)) {
 547             /* off with its head! */
 548             bn = node->bh;
 549             node->bh = bn->next;
 550             node->bh->prev = NULL;
 551             node->bcount -= bn->count;
 552             g_free(bn);
 553         }
 554     }
 555     else if (current_bucket<node->bh->bucket_no) {
 556         /* Packet must be added at head of burst list - check if not too old */
 557         if ((current_bucket+burstwin)>node->bt->bucket_no) {
 558             /* packet still within the window */
 559             bn = (burst_bucket*)g_malloc0(sizeof(burst_bucket));
 560             bn->count = value;
 561             bn->bucket_no = current_bucket;
 562             bn->start_time = node->st->now;
 563             bn->next = node->bh;
 564             node->bh->prev = bn;
 565             node->bh = bn;
 566             /* And add value to the current burst count for node */
 567             node->bcount += value;
 568         }
 569     }
 570     else
 571     {
 572         /* Somewhere in the middle... */
 573         burst_bucket *search = node->bt;
 574         while (current_bucket<search->bucket_no) {
 575             search = search->prev;
 576         }
 577         if (current_bucket==search->bucket_no) {
 578             /* found existing bucket, increase value */
 579             search->count += value;
 580             if (search->start_time>node->st->now) {
 581                 search->start_time = node->st->now;
 582             }
 583         }
 584         else {
 585             /* must add a new bucket after bn. */
 586             bn = (burst_bucket*)g_malloc0(sizeof(burst_bucket));
 587             bn->count = value;
 588             bn->bucket_no = current_bucket;
 589             bn->start_time = node->st->now;
 590             bn->prev = search;
 591             bn->next = search->next;
 592             search->next = bn;
 593             bn->next->prev = bn;
 594         }
 595         node->bcount += value;
 596     }
 597     if (node->bcount>node->max_burst) {
 598         /* new record burst */
 599         node->max_burst = node->bcount;
 600         node->burst_time = node->bh->start_time;
 601     }
 602 }
 603
 604 /*
 605  * Increases by delta the counter of the node whose name is given
 606  * if the node does not exist yet it's created (with counter=1)
 607  * using parent_name as parent node.
 608  * with_hash=TRUE to indicate that the created node will have a parent
 609  */
 610 extern int
 611 stats_tree_manip_node(manip_node_mode mode, stats_tree *st, const char *name,
 612               int parent_id, gboolean with_hash, gint value)
 613 {
 614     stat_node *node = NULL;
 615     stat_node *parent = NULL;
 616
 617     g_assert( parent_id >= 0 && parent_id < (int) st->parents->len );
 618
 619     parent = (stat_node *)g_ptr_array_index(st->parents,parent_id);
 620
 621     if( parent->hash ) {
 622         node = (stat_node *)g_hash_table_lookup(parent->hash,name);
 623     } else {
 624         node = (stat_node *)g_hash_table_lookup(st->names,name);
 625     }
 626
 627     if ( node == NULL )
 628         node = new_stat_node(st,name,parent_id,with_hash,with_hash);
 629
 630     switch (mode) {
 631         case MN_INCREASE:
 632             node->counter += value;
 633             update_burst_calc(node, value);
 634             break;
 635         case MN_SET: node->counter = value; break;
 636         case MN_AVERAGE:
 637             node->counter++;
 638             update_burst_calc(node, 1);
 639             /* fall through */ /*to average code */
 640         case MN_AVERAGE_NOTICK:
 641             node->total += value;
 642             if (node->minvalue > value) {
 643                 node->minvalue = value;
 644             }
 645             if (node->maxvalue < value) {
 646                 node->maxvalue = value;
 647             }
 648             node->st_flags |= ST_FLG_AVERAGE;
 649             break;
 650         case MN_SET_FLAGS:
 651             node->st_flags |= value;
 652             break;
 653         case MN_CLEAR_FLAGS:
 654             node->st_flags &= ~value;
 655             break;
 656     }
 657
 658     if (node)
 659         return node->id;
 660     else
 661         return -1;
 662 }
 663
 664
 665 extern char*
 666 stats_tree_get_abbr(const char *opt_arg)
 667 {
 668     guint i;
 669
 670     /* XXX: this fails when tshark is given any options
 671        after the -z */
 672     g_assert(opt_arg != NULL);
 673
 674     for (i=0; opt_arg[i] && opt_arg[i] != ','; i++);
 675
 676     if (opt_arg[i] == ',') {
 677         return g_strndup(opt_arg,i);
 678     } else {
 679         return NULL;
 680     }
 681 }
 682
 683
 684 /*
 685  * This function accepts an input string which should define a long integer range.
 686  * The normal result is a struct containing the floor and ceil value of this
 687  * range.
 688  *
 689  * It is allowed to define a range string in the following ways :
 690  *
 691  * "0-10" -> { 0, 10 }
 692  * "-0" -> { G_MININT, 0 }
 693  * "0-" -> { 0, G_MAXINT }
 694  * "-" -> { G_MININT, G_MAXINT }
 695  *
 696  * Note that this function is robust to buggy input string. If in some cases it
 697  * returns NULL, it but may also return a pair with undefined values.
 698  *
 699  */
 700 static range_pair_t*
 701 get_range(char *rngstr)
 702 {
 703     gchar **split;
 704     range_pair_t *rng;
 705
 706     split = g_strsplit((gchar*)rngstr,"-",2);
 707
 708     /* empty string */
 709     if (split[0] == NULL) {
 710         g_strfreev(split);
 711         return NULL;
 712     }
 713
 714     rng = (range_pair_t *)g_malloc(sizeof(range_pair_t));
 715
 716     if (split[1] == NULL) {
 717         /* means we have a non empty string with no delimiter
 718          * so it must be a single number */
 719         rng->floor = (gint)strtol(split[0],NULL,10);
 720         rng->ceil = rng->floor;
 721     } else {
 722       /* string == "X-?" */
 723         if (*(split[0]) != '\0') {
 724             rng->floor = (gint)strtol(split[0],NULL,10);
 725         } else {
 726             /* string == "-?" */
 727             rng->floor = G_MININT;
 728         }
 729
 730         /* string != "?-" */
 731         if (*(split[1]) != '\0') {
 732             rng->ceil  = (gint)strtol(split[1],NULL,10);
 733         } else {
 734             /* string == "?-" */
 735             rng->ceil = G_MAXINT;
 736         }
 737     }
 738     g_strfreev(split);
 739
 740     return rng;
 741 }
 742
 743
 744 extern int
 745 stats_tree_create_range_node(stats_tree *st, const gchar *name, int parent_id, ...)
 746 {
 747     va_list list;
 748     gchar *curr_range;
 749     stat_node *rng_root = new_stat_node(st, name, parent_id, FALSE, TRUE);
 750     stat_node *range_node = NULL;
 751
 752     va_start( list, parent_id );
 753     while (( curr_range = va_arg(list, gchar*) )) {
 754         range_node = new_stat_node(st, curr_range, rng_root->id, FALSE, FALSE);
 755         range_node->rng = get_range(curr_range);
 756     }
 757     va_end( list );
 758
 759     return rng_root->id;
 760 }
 761
 762 extern int
 763 stats_tree_create_range_node_string(stats_tree *st, const gchar *name,
 764                     int parent_id, int num_str_ranges,
 765                     gchar** str_ranges)
 766 {
 767     int i;
 768     stat_node *rng_root = new_stat_node(st, name, parent_id, FALSE, TRUE);
 769     stat_node *range_node = NULL;
 770
 771     for (i = 0; i < num_str_ranges - 1; i++) {
 772         range_node = new_stat_node(st, str_ranges[i], rng_root->id, FALSE, FALSE);
 773         range_node->rng = get_range(str_ranges[i]);
 774     }
 775     range_node = new_stat_node(st, str_ranges[i], rng_root->id, FALSE, FALSE);
 776     range_node->rng = get_range(str_ranges[i]);
 777     if (range_node->rng->floor == range_node->rng->ceil) {
 778         range_node->rng->ceil = G_MAXINT;
 779     }
 780
 781     return rng_root->id;
 782 }
 783
 784 /****/
 785 extern int
 786 stats_tree_parent_id_by_name(stats_tree *st, const gchar *parent_name)
 787 {
 788     stat_node *node = (stat_node *)g_hash_table_lookup(st->names,parent_name);
 789
 790     if (node)
 791         return node->id;
 792     else
 793         return 0; /* XXX: this is the root shoud we return -1 instead?*/
 794 }
 795
 796
 797 extern int
 798 stats_tree_range_node_with_pname(stats_tree *st, const gchar *name,
 799                  const gchar *parent_name, ...)
 800 {
 801     va_list list;
 802     gchar *curr_range;
 803     stat_node *range_node = NULL;
 804     int parent_id = stats_tree_parent_id_by_name(st,parent_name);
 805     stat_node *rng_root = new_stat_node(st, name, parent_id, FALSE, TRUE);
 806
 807     va_start( list, parent_name );
 808     while (( curr_range = va_arg(list, gchar*) )) {
 809         range_node = new_stat_node(st, curr_range, rng_root->id, FALSE, FALSE);
 810         range_node->rng = get_range(curr_range);
 811     }
 812     va_end( list );
 813
 814     return rng_root->id;
 815 }
 816
 817
 818 extern int
 819 stats_tree_tick_range(stats_tree *st, const gchar *name, int parent_id,
 820               int value_in_range)
 821 {
 822
 823     stat_node *node = NULL;
 824     stat_node *parent = NULL;
 825     stat_node *child = NULL;
 826     gint stat_floor, stat_ceil;
 827
 828     if (parent_id >= 0 && parent_id < (int) st->parents->len) {
 829         parent = (stat_node *)g_ptr_array_index(st->parents,parent_id);
 830     } else {
 831         g_assert_not_reached();
 832     }
 833
 834     if( parent->hash ) {
 835         node = (stat_node *)g_hash_table_lookup(parent->hash,name);
 836     } else {
 837         node = (stat_node *)g_hash_table_lookup(st->names,name);
 838     }
 839
 840     if ( node == NULL )
 841         g_assert_not_reached();
 842
 843     /* update stats for container node. counter should already be ticked so we only update total and min/max */
 844     node->total += value_in_range;
 845     if (node->minvalue > value_in_range) {
 846         node->minvalue = value_in_range;
 847     }
 848     if (node->maxvalue < value_in_range) {
 849         node->maxvalue = value_in_range;
 850     }
 851     node->st_flags |= ST_FLG_AVERAGE;
 852
 853     for ( child = node->children; child; child = child->next) {
 854         stat_floor =  child->rng->floor;
 855         stat_ceil = child->rng->ceil;
 856
 857         if ( value_in_range >= stat_floor && value_in_range <= stat_ceil ) {
 858             child->counter++;
 859             child->total += value_in_range;
 860             if (child->minvalue > value_in_range) {
 861                 child->minvalue = value_in_range;
 862             }
 863             if (child->maxvalue < value_in_range) {
 864                 child->maxvalue = value_in_range;
 865             }
 866             child->st_flags |= ST_FLG_AVERAGE;
 867             update_burst_calc(child, 1);
 868             return node->id;
 869         }
 870     }
 871
 872     return node->id;
 873 }
 874
 875 extern int
 876 stats_tree_create_pivot(stats_tree *st, const gchar *name, int parent_id)
 877 {
 878     stat_node *node = new_stat_node(st,name,parent_id,TRUE,TRUE);
 879
 880     if (node)
 881         return node->id;
 882     else
 883         return 0;
 884 }
 885
 886 extern int
 887 stats_tree_create_pivot_by_pname(stats_tree *st, const gchar *name,
 888                  const gchar *parent_name)
 889 {
 890     int parent_id = stats_tree_parent_id_by_name(st,parent_name);
 891     stat_node *node;
 892
 893     node = new_stat_node(st,name,parent_id,TRUE,TRUE);
 894
 895     if (node)
 896         return node->id;
 897     else
 898         return 0;
 899 }
 900
 901 extern int
 902 stats_tree_tick_pivot(stats_tree *st, int pivot_id, const gchar *pivot_value)
 903 {
 904     stat_node *parent = (stat_node *)g_ptr_array_index(st->parents,pivot_id);
 905
 906     parent->counter++;
 907     update_burst_calc(parent, 1);
 908     stats_tree_manip_node( MN_INCREASE, st, pivot_value, pivot_id, FALSE, 1);
 909
 910     return pivot_id;
 911 }
 912
 913 extern gchar*
 914 stats_tree_get_displayname (gchar* fullname)
 915 {
 916     gchar *buf = g_strdup(fullname);
 917     gchar *sep;
 918
 919     if (prefs.st_sort_showfullname) {
 920         return buf; /* unmodifed */
 921     }
 922
 923     sep = buf;
 924     while ((sep = strchr(sep,'/')) != NULL) {
 925         if (*(++sep)=='/') {  /* escapeded slash - two slash characters after each other */
 926             memmove(sep,sep+1,strlen(sep));
 927         }
 928         else {
 929             /* we got a new path separator */
 930             memmove(buf,sep,strlen(sep)+1);
 931             sep = buf;
 932         }
 933     }
 934
 935     return buf;
 936 }
 937
 938 extern gint
 939 stats_tree_get_default_sort_col (stats_tree *st)
 940 {
 941     switch ((st->st_flags&ST_FLG_SRTCOL_MASK)>>ST_FLG_SRTCOL_SHIFT) {
 942         case ST_SORT_COL_NAME:
 943             return COL_NAME;
 944         case ST_SORT_COL_COUNT:
 945             return COL_COUNT;
 946         case ST_SORT_COL_AVG:
 947             return COL_AVERAGE;
 948         case ST_SORT_COL_MIN:
 949             return COL_MIN;
 950         case ST_SORT_COL_MAX:
 951             return COL_MAX;
 952         case ST_SORT_COL_BURSTRATE:
 953             return COL_BURSTRATE;
 954     }
 955     return COL_COUNT;   /* nothing specific set */
 956 }
 957
 958 extern gboolean
 959 stats_tree_is_default_sort_DESC (stats_tree *st)
 960 {
 961     return st->st_flags&ST_FLG_SORT_DESC;
 962 }
 963
 964 extern const gchar*
 965 stats_tree_get_column_name (gint col_index)
 966 {
 967     switch (col_index) {
 968         case COL_NAME:
 969             return "Topic / Item";
 970         case COL_COUNT:
 971             return "Count";
 972         case COL_AVERAGE:
 973             return "Average";
 974         case COL_MIN:
 975             return "Min val";
 976         case COL_MAX:
 977             return "Max val";
 978         case COL_RATE:
 979             return "Rate (ms)";
 980         case COL_PERCENT:
 981             return "Percent";
 982         case COL_BURSTRATE:
 983             return prefs.st_burst_showcount?"Burst count":"Burst rate";
 984         case COL_BURSTTIME:
 985             return "Burst start";
 986         default:
 987             return "(Unknown)";
 988     }
 989 }
 990
 991 extern gint
 992 stats_tree_get_column_size (gint col_index)
 993 {
 994     if (col_index==COL_NAME) {
 995         return 36;      /* but caller should really call stats_tree_branch_max_namelen() */
 996     }
 997     if (col_index<N_COLUMNS) {
 998         return 12;      /* all numerical values are this size */
 999     }
1000     return 0;           /* invalid column */
1001 }
1002
1003 extern gchar**
1004 stats_tree_get_values_from_node (const stat_node* node)
1005 {
1006     gchar **values = (gchar**) g_malloc0(sizeof(gchar*)*(node->st->num_columns));
1007
1008     values[COL_NAME] = (node->st_flags&ST_FLG_ROOTCHILD)?stats_tree_get_displayname(node->name):g_strdup(node->name);
1009     values[COL_COUNT] = g_strdup_printf("%u",node->counter);
1010     values[COL_AVERAGE] = ((node->st_flags&ST_FLG_AVERAGE)||node->rng)?
1011                 (node->counter?g_strdup_printf("%.2f",((float)node->total)/node->counter):g_strdup("-")):
1012                 g_strdup("");
1013     values[COL_MIN] = ((node->st_flags&ST_FLG_AVERAGE)||node->rng)?
1014                 (node->counter?g_strdup_printf("%u",node->minvalue):g_strdup("-")):
1015                 g_strdup("");
1016     values[COL_MAX] = ((node->st_flags&ST_FLG_AVERAGE)||node->rng)?
1017                 (node->counter?g_strdup_printf("%u",node->maxvalue):g_strdup("-")):
1018                 g_strdup("");
1019     values[COL_RATE] = (node->st->elapsed)?g_strdup_printf("%.4f",((float)node->counter)/node->st->elapsed):g_strdup("");
1020     values[COL_PERCENT] = ((node->parent)&&(node->parent->counter))?
1021                 g_strdup_printf("%.2f%%",(node->counter*100.0)/node->parent->counter):
1022                 (node->parent==&(node->st->root)?g_strdup("100%"):g_strdup(""));
1023     if (node->st->num_columns>COL_BURSTTIME) {
1024         values[COL_BURSTRATE] = (!prefs.st_enable_burstinfo)?g_strdup(""):
1025                 (node->max_burst?(prefs.st_burst_showcount?
1026                                 g_strdup_printf("%d",node->max_burst):
1027                                 g_strdup_printf("%.4f",((double)node->max_burst)/prefs.st_burst_windowlen)):
1028                 g_strdup("-"));
1029         values[COL_BURSTTIME] = (!prefs.st_enable_burstinfo)?g_strdup(""):
1030                 (node->max_burst?g_strdup_printf("%.3f",((double)node->burst_time/1000.0)):g_strdup("-"));
1031     }
1032     return values;
1033 }
1034
1035 extern gint
1036 stats_tree_sort_compare (const stat_node *a, const stat_node *b, gint sort_column,
1037                     gboolean sort_descending)
1038 {
1039     int result = 0;
1040     float avg_a, avg_b;
1041
1042     if  (prefs.st_sort_rng_nameonly&&(a->rng&&b->rng)) {
1043         /* always sort ranges by range name */
1044         result = a->rng->floor - b->rng->floor;
1045         if (sort_descending&&(!prefs.st_sort_rng_fixorder)) {
1046             result = -result;
1047         }
1048         return result;
1049     }
1050
1051     switch (sort_column) {
1052         case COL_NAME:
1053             if  (a->rng&&b->rng) {
1054                 result = a->rng->floor - b->rng->floor;
1055             }
1056             else if (prefs.st_sort_casesensitve) {
1057                 result = strcmp(a->name,b->name);
1058             }
1059             else {
1060                 result = g_ascii_strcasecmp(a->name,b->name);
1061             }
1062             break;
1063
1064         case COL_RATE:
1065         case COL_PERCENT:
1066         case COL_COUNT:
1067             result = a->counter - b->counter;
1068             break;
1069
1070         case COL_AVERAGE:
1071             avg_a = a->counter ? ((float)a->total)/a->counter : 0;
1072             avg_b = b->counter ? ((float)b->total)/b->counter : 0;
1073             result = (avg_a>avg_b) ? 1 : ( (avg_a<avg_b) ? -1 : 0);
1074             break;
1075
1076         case COL_MIN:
1077             result = a->minvalue - b->minvalue;
1078             break;
1079
1080         case COL_MAX:
1081             result = a->maxvalue - b->maxvalue;
1082             break;
1083
1084         case COL_BURSTRATE:
1085             result = a->max_burst - b->max_burst;
1086             break;
1087
1088         case COL_BURSTTIME:
1089             result = (a->burst_time>b->burst_time)?1:((a->burst_time<b->burst_time)?-1:0);
1090             break;
1091
1092         default:
1093             /* no sort comparison found for column - must update this switch statement */
1094             g_assert_not_reached();
1095     }
1096
1097     /* break tie between items with same primary search result */
1098     if (!result) {
1099         if (sort_column==COL_NAME) {
1100             result = a->counter - b->counter;
1101         }
1102         else {
1103             if  (a->rng&&b->rng) {
1104                 result = a->rng->floor - b->rng->floor;
1105             }
1106             else if (prefs.st_sort_casesensitve) {
1107                 result = strcmp(a->name,b->name);
1108             }
1109             else {
1110                 result = g_ascii_strcasecmp(a->name,b->name);
1111             }
1112         }
1113     }
1114
1115     /* take into account sort order */
1116     if (sort_descending) {
1117         result = -result;
1118     }
1119
1120     if ((a->st_flags&ST_FLG_SORT_TOP)!=(b->st_flags&ST_FLG_SORT_TOP)) {
1121         /* different sort groups top vs non-top */
1122         result = (a->st_flags&ST_FLG_SORT_TOP)?-1:1;
1123     }
1124     return result;
1125 }
1126
1127 extern GString*
1128 stats_tree_format_as_str(const stats_tree* st, st_format_type format_type,
1129                     gint sort_column, gboolean sort_descending)
1130 {
1131     int maxnamelen = stats_tree_branch_max_namelen(&st->root,0);
1132     stat_node *child;
1133     GString *s;
1134     int count;
1135     gchar *separator = NULL;
1136
1137     switch(format_type) {
1138         case ST_FORMAT_YAML:
1139             s = g_string_new("---\n");
1140             break;
1141         case ST_FORMAT_XML:
1142             s = g_string_new("<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
1143             break;
1144         case ST_FORMAT_CSV:
1145             s = g_string_new("\"level\",\"parent\",");
1146             for (count = 0; count<st->num_columns; count++) {
1147                 g_string_append_printf(s,"\"%s\",",stats_tree_get_column_name(count));
1148             }
1149             g_string_append (s,"\n");
1150             break;
1151         case ST_FORMAT_PLAIN:
1152         {
1153             char fmt[16];
1154             int sep_length;
1155
1156             sep_length = maxnamelen;
1157             for (count = 1; count<st->num_columns; count++) {
1158                 sep_length += stats_tree_get_column_size(count)+2;
1159             }
1160             separator = (gchar *)g_malloc(sep_length+1);
1161             memset (separator, '=', sep_length);
1162             separator[sep_length] = 0;
1163
1164             s = g_string_new("\n");
1165             g_string_append(s,separator);
1166             g_string_append_printf(s,"\n%s:\n",st->cfg->name);
1167             g_snprintf (fmt,(gulong)sizeof(fmt),"%%-%us",maxnamelen);
1168             g_string_append_printf(s,fmt,stats_tree_get_column_name(0));
1169             for (count = 1; count<st->num_columns; count++) {
1170                 g_snprintf (fmt,(gulong)sizeof(fmt)," %%-%us",stats_tree_get_column_size(count)+1);
1171                 g_string_append_printf(s,fmt,stats_tree_get_column_name(count));
1172             }
1173             memset (separator, '-', sep_length);
1174             g_string_append_printf(s,"\n%s\n",separator);
1175             break;
1176         }
1177         default:
1178             return g_string_new("unknown format for stats_tree\n");
1179     }
1180
1181     for (child = st->root.children; child; child = child->next ) {
1182         stats_tree_format_node_as_str(child,s,format_type,0,"",maxnamelen,sort_column,sort_descending);
1183
1184     }
1185
1186     if (format_type==ST_FORMAT_PLAIN) {
1187         g_string_append_printf(s,"\n%s\n",separator);
1188         g_free(separator);
1189     }
1190
1191     return s;
1192 }
1193
1194 typedef struct {
1195     gint sort_column;
1196     gboolean sort_descending;
1197 }   sortinfo;
1198
1199 /* Function to compare elements for child array sort. a and b are children, user_data
1200 points to a st_flags value */
1201 extern gint
1202 stat_node_array_sortcmp (gconstpointer a, gconstpointer b, gpointer user_data)
1203 {
1204     /* user_data is *guint value to st_flags */
1205     return stats_tree_sort_compare (*(const stat_node*const*)a,*(const stat_node*const*)b,
1206                     ((sortinfo*)user_data)->sort_column,((sortinfo*)user_data)->sort_descending);
1207 }
1208
1209 static gchar*
1210 clean_for_xml_tag (gchar *str)
1211 {
1212     gchar *s = str;
1213     while ((s=strpbrk(s,"!\"#$%%&'()*+,/;<=>?@[\\]^`{|}~ ")) != NULL) {
1214         *(s++) = '-';
1215     }
1216     return str;
1217 }
1218
1219 /** helper funcation to add note to formatted stats_tree */
1220 WS_DLL_PUBLIC void stats_tree_format_node_as_str(const stat_node *node,
1221                          GString *s,
1222                          st_format_type format_type,
1223                          guint indent,
1224                          const gchar *path,
1225                          gint maxnamelen,
1226                          gint sort_column,
1227                          gboolean sort_descending)
1228 {
1229     int count;
1230     int num_columns = node->st->num_columns;
1231     gchar **values = stats_tree_get_values_from_node(node);
1232     stat_node *child;
1233     sortinfo si;
1234     gchar *full_path;
1235     char fmt[16] = "%s%s%s";
1236
1237     switch(format_type) {
1238         case ST_FORMAT_YAML:
1239             if (indent) {
1240                 g_snprintf(fmt, (gulong)sizeof(fmt), "%%%ds%%s%%s", indent*4-2);
1241             }
1242             g_string_append_printf(s, fmt, "", indent?"- ":"", "Description");
1243             g_string_append_printf(s, ": \"%s\"\n", values[0]);
1244
1245             for (count = 1; count<num_columns; count++) {
1246                 if (*values[count]) {
1247                     g_string_append_printf(s, fmt, "", indent?"  ":"",
1248                                             stats_tree_get_column_name(count));
1249                     g_string_append_printf(s, ": %s\n", values[count]);
1250                 }
1251             }
1252             if (node->children) {
1253                 g_string_append_printf(s, fmt, "", indent?"  ":"", "Items:\n");
1254             }
1255             break;
1256         case ST_FORMAT_XML:
1257         {
1258             char *itemname = xml_escape(values[0]);
1259             g_string_append_printf(s,"<stat-node name=\"%s\"%s>\n",itemname,
1260                     node->rng?" isrange=\"true\"":"");
1261             g_free(itemname);
1262             for (count = 1; count<num_columns; count++) {
1263                 gchar *colname = g_strdup(stats_tree_get_column_name(count));
1264                 g_string_append_printf(s,"<%s>",clean_for_xml_tag(colname));
1265                 g_string_append_printf(s,"%s</%s>\n",values[count],colname);
1266                 g_free(colname);
1267             }
1268             break;
1269         }
1270         case ST_FORMAT_CSV:
1271             g_string_append_printf(s,"%d,\"%s\",\"%s\"",indent,path,values[0]);
1272             for (count = 1; count<num_columns; count++) {
1273                 g_string_append_printf(s,",%s",values[count]);
1274             }
1275             g_string_append (s,"\n");
1276             break;
1277         case ST_FORMAT_PLAIN:
1278             g_snprintf (fmt,(gulong)sizeof(fmt),"%%%ds%%-%us",indent,maxnamelen-indent);
1279             g_string_append_printf(s,fmt,"",values[0]);
1280             for (count = 1; count<num_columns; count++) {
1281                 g_snprintf (fmt,(gulong)sizeof(fmt)," %%-%us",stats_tree_get_column_size(count)+1);
1282                 g_string_append_printf(s,fmt,values[count]);
1283             }
1284             g_string_append (s,"\n");
1285             break;
1286     }
1287
1288     indent++;
1289     indent = indent > INDENT_MAX ? INDENT_MAX : indent;
1290     full_path = g_strdup_printf ("%s/%s",path,values[0]);
1291
1292     for (count = 0; count<num_columns; count++) {
1293         g_free(values[count]);
1294     }
1295     g_free(values);
1296
1297     if (node->children) {
1298         GArray *Children = g_array_new(FALSE,FALSE,sizeof(child));
1299         for (child = node->children; child; child = child->next ) {
1300             g_array_append_val(Children,child);
1301         }
1302         si.sort_column = sort_column;
1303         si.sort_descending = sort_descending;
1304         g_array_sort_with_data(Children,stat_node_array_sortcmp,&si);
1305         for (count = 0; count<((int)Children->len); count++) {
1306             stats_tree_format_node_as_str(g_array_index(Children,stat_node*,count), s, format_type,
1307                     indent, full_path, maxnamelen, sort_column, sort_descending);
1308         }
1309         g_array_free(Children, TRUE);
1310     }
1311     g_free(full_path);
1312
1313     if (format_type==ST_FORMAT_XML) {
1314         g_string_append(s,"</stat-node>\n");
1315     }
1316 }
1317
1318 void stats_tree_cleanup(void)
1319 {
1320     g_hash_table_destroy(registry);
1321 }
1322
1323 /*
1324  * Editor modelines  -  http://www.wireshark.org/tools/modelines.html
1325  *
1326  * Local variables:
1327  * c-basic-offset: 4
1328  * tab-width: 8
1329  * indent-tabs-mode: nil
1330  * End:
1331  *
1332  * vi: set shiftwidth=4 tabstop=8 expandtab:
1333  * :indentSize=4:tabSize=8:noTabs=true:
1334  */