epan/stats_tree.c

   1 /* stats_tree.c
   2  * API for a counter tree for Wireshark
   3  * 2004, Luis E. G. Ontanon
   4  *
   5  * $Id$
   6  *
   7  * Wireshark - Network traffic analyzer
   8  * By Gerald Combs <gerald@wireshark.org>
   9  * Copyright 1998 Gerald Combs
  10  *
  11  * This program is free software; you can redistribute it and/or
  12  * modify it under the terms of the GNU General Public License
  13  * as published by the Free Software Foundation; either version 2
  14  * of the License, or (at your option) any later version.
  15  *
  16  * This program is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  * GNU General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU General Public License
  22  * along with this program; if not, write to the Free Software
  23  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  24  */
  25
  26 #ifdef HAVE_CONFIG_H
  27 #include "config.h"
  28 #endif
  29
  30 #include <glib.h>
  31 #include <epan/stats_tree_priv.h>
  32 #include <string.h>
  33
  34 #include "stats_tree.h"
  35
  36 /*
  37 TODO:
  38    - sort out the sorting issue
  39
  40  */
  41
  42 /* used to contain the registered stat trees */
  43 static GHashTable *registry = NULL;
  44
  45 /* writes into the buffers pointed by value, rate and percent
  46    the string representations of a node*/
  47 extern void
  48 stats_tree_get_strs_from_node(const stat_node *node, gchar *value, gchar *rate, gchar *percent)
  49 {
  50         float f;
  51
  52         if (value) g_snprintf(value,NUM_BUF_SIZE,"%u",node->counter);
  53
  54         if (rate) {
  55                 *rate = '\0';
  56                 if (node->st->elapsed > 0.0) {
  57                         f = ((float)node->counter) / (float)node->st->elapsed;
  58                         g_snprintf(rate,NUM_BUF_SIZE,"%f",f);
  59                 }
  60         }
  61
  62         if (percent) {
  63                 *percent = '\0';
  64                 if (node->parent->counter > 0) {
  65                         f = (float)(((float)node->counter * 100.0) / node->parent->counter);
  66                         g_snprintf(percent,NUM_BUF_SIZE,"%.2f%%",f);
  67                 }
  68         }
  69 }
  70
  71
  72 /* a text representation of a node
  73 if buffer is NULL returns a newly allocated string */
  74 extern gchar*
  75 stats_tree_node_to_str(const stat_node *node, gchar *buffer, guint len)
  76 {
  77         if (buffer) {
  78                 g_snprintf(buffer,len,"%s: %i",node->name, node->counter);
  79                 return buffer;
  80         } else {
  81                 return g_strdup_printf("%s: %i",node->name, node->counter);
  82         }
  83 }
  84
  85 extern guint
  86 stats_tree_branch_max_namelen(const stat_node *node, guint indent)
  87 {
  88         stat_node *child;
  89         guint maxlen = 0;
  90         guint len;
  91
  92         indent = indent > INDENT_MAX ? INDENT_MAX : indent;
  93
  94         if (node->children) {
  95                 for (child = node->children; child; child = child->next ) {
  96                         len = stats_tree_branch_max_namelen(child,indent+1);
  97                         maxlen = len > maxlen ? len : maxlen;
  98                 }
  99         }
 100
 101         len = (guint) strlen(node->name) + indent;
 102         maxlen = len > maxlen ? len : maxlen;
 103
 104         return maxlen;
 105 }
 106
 107 static gchar *format;
 108
 109 /* populates the given GString with a tree representation of a branch given by node,
 110 using indent spaces as initial indentation */
 111 extern void
 112 stats_tree_branch_to_str(const stat_node *node, GString *s, guint indent)
 113 {
 114         stat_node *child;
 115         static gchar indentation[INDENT_MAX+1];
 116         static gchar value[NUM_BUF_SIZE];
 117         static gchar rate[NUM_BUF_SIZE];
 118         static gchar percent[NUM_BUF_SIZE];
 119
 120         guint i = 0;
 121
 122         if (indent == 0) {
 123                 format = g_strdup_printf(" %%s%%-%us%%12s   %%12s    %%12s\n",stats_tree_branch_max_namelen(node,0));
 124         }
 125
 126         stats_tree_get_strs_from_node(node, value, rate, percent);
 127
 128         indent = indent > INDENT_MAX ? INDENT_MAX : indent;
 129
 130         /* fill indentation with indent spaces */
 131         if (indent > 0) {
 132                 while(i<indent)
 133                         indentation[i++] = ' ';
 134         }
 135
 136         indentation[i] = '\0';
 137
 138         g_string_append_printf(s,format,
 139                                           indentation,node->name,value,rate,percent);
 140
 141         if (node->children) {
 142                 for (child = node->children; child; child = child->next ) {
 143                         stats_tree_branch_to_str(child,s,indent+1);
 144                 }
 145         }
 146
 147         if (indent == 0) {
 148                 g_free(format);
 149         }
 150 }
 151
 152
 153 /* frees the resources allocated by a stat_tree node */
 154 static void
 155 free_stat_node(stat_node *node)
 156 {
 157         stat_node *child;
 158         stat_node *next;
 159
 160         if (node->children) {
 161         for (child = node->children; child; child = next ) {
 162             /* child->next will be gone after free_stat_node, so cache it here */
 163             next = child->next;
 164                         free_stat_node(child);
 165         }
 166         }
 167
 168         if(node->st->cfg->free_node_pr) node->st->cfg->free_node_pr(node);
 169
 170         if (node->hash) g_hash_table_destroy(node->hash);
 171
 172         g_free(node->rng);
 173         g_free(node->name);
 174         g_free(node);
 175 }
 176
 177 /* destroys the whole tree instance */
 178 extern void
 179 stats_tree_free(stats_tree *st)
 180 {
 181         stat_node *child;
 182         stat_node *next;
 183
 184         g_free(st->filter);
 185         g_hash_table_destroy(st->names);
 186         g_ptr_array_free(st->parents,TRUE);
 187
 188         for (child = st->root.children; child; child = next ) {
 189                 /* child->next will be gone after free_stat_node, so cache it here */
 190                 next = child->next;
 191                 free_stat_node(child);
 192         }
 193
 194         if (st->cfg->free_tree_pr)
 195                 st->cfg->free_tree_pr(st);
 196
 197         if (st->cfg->cleanup)
 198                 st->cfg->cleanup(st);
 199
 200         g_free(st);
 201 }
 202
 203
 204 /* reset a node to its original state */
 205 static void
 206 reset_stat_node(stat_node *node)
 207 {
 208         stat_node *child;
 209
 210         if (node->children) {
 211                 for (child = node->children; child; child = child->next )
 212                         reset_stat_node(child);
 213         }
 214
 215         node->counter = 0;
 216
 217         if(node->st->cfg->reset_node) {
 218                 node->st->cfg->reset_node(node);
 219         }
 220
 221 }
 222
 223 /* reset the whole stats_tree */
 224 extern void
 225 stats_tree_reset(void *p)
 226 {
 227         stats_tree *st = p;
 228
 229         st->start = -1.0;
 230         st->elapsed = 0.0;
 231
 232         reset_stat_node(&st->root);
 233
 234         if (st->cfg->reset_tree) {
 235                 st->cfg->reset_tree(st);
 236         }
 237 }
 238
 239 extern void
 240 stats_tree_reinit(void *p)
 241 {
 242         stats_tree *st = p;
 243         stat_node *child;
 244         stat_node *next;
 245
 246         for (child = st->root.children; child; child = next) {
 247         /* child->next will be gone after free_stat_node, so cache it here */
 248         next = child->next;
 249                 free_stat_node(child);
 250         }
 251
 252         st->root.children = NULL;
 253         st->root.counter = 0;
 254
 255         if (st->cfg->init) {
 256                 st->cfg->init(st);
 257         }
 258 }
 259
 260 /* register a new stats_tree */
 261 extern void
 262 stats_tree_register_with_group(const char *tapname, const char *abbr, const char *name,
 263                     guint flags,
 264                     stat_tree_packet_cb packet, stat_tree_init_cb init,
 265                     stat_tree_cleanup_cb cleanup, register_stat_group_t stat_group)
 266 {
 267
 268         stats_tree_cfg *cfg = g_malloc( sizeof(stats_tree_cfg) );
 269
 270         /* at the very least the abbrev and the packet function should be given */
 271         g_assert( tapname && abbr && packet );
 272
 273         cfg->tapname = g_strdup(tapname);
 274         cfg->abbr = g_strdup(abbr);
 275         cfg->name = name ? g_strdup(name) : g_strdup(abbr);
 276         cfg->stat_group = stat_group;
 277
 278         cfg->packet = packet;
 279         cfg->init = init;
 280         cfg->cleanup = cleanup;
 281
 282         cfg->flags = flags;
 283
 284         /* these have to be filled in by implementations */
 285         cfg->setup_node_pr = NULL;
 286         cfg->new_tree_pr = NULL;
 287         cfg->free_node_pr = NULL;
 288         cfg->free_tree_pr = NULL;
 289         cfg->draw_node = NULL;
 290         cfg->draw_tree = NULL;
 291         cfg->reset_node = NULL;
 292         cfg->reset_tree = NULL;
 293
 294         if (!registry) registry = g_hash_table_new(g_str_hash,g_str_equal);
 295
 296         g_hash_table_insert(registry,cfg->abbr,cfg);
 297
 298 }
 299
 300 /* register a new stats_tree with default group REGISTER_STAT_GROUP_UNSORTED */
 301 extern void
 302 stats_tree_register(const char *tapname, const char *abbr, const char *name,
 303                     guint flags,
 304                     stat_tree_packet_cb packet, stat_tree_init_cb init,
 305                     stat_tree_cleanup_cb cleanup)
 306 {
 307         stats_tree_register_with_group(tapname, abbr, name,
 308                     flags,
 309                     packet, init,
 310                     cleanup, REGISTER_STAT_GROUP_UNSORTED);
 311 }
 312
 313 extern stats_tree*
 314 stats_tree_new(stats_tree_cfg *cfg, tree_pres *pr, const char *filter)
 315 {
 316         stats_tree *st = g_malloc(sizeof(stats_tree));
 317
 318         st->cfg = cfg;
 319         st->pr = pr;
 320
 321         st->names = g_hash_table_new(g_str_hash,g_str_equal);
 322         st->parents = g_ptr_array_new();
 323         st->filter = g_strdup(filter);
 324
 325         st->start = -1.0;
 326         st->elapsed = 0.0;
 327
 328         st->root.counter = 0;
 329         st->root.name = g_strdup(cfg->name);
 330         st->root.st = st;
 331         st->root.parent = NULL;
 332         st->root.children = NULL;
 333         st->root.next = NULL;
 334         st->root.hash = NULL;
 335         st->root.pr = NULL;
 336
 337         g_ptr_array_add(st->parents,&st->root);
 338
 339         return st;
 340 }
 341
 342 /* will be the tap packet cb */
 343 extern int
 344 stats_tree_packet(void *p, packet_info *pinfo, epan_dissect_t *edt, const void *pri)
 345 {
 346         stats_tree *st = p;
 347         double now = nstime_to_msec(&pinfo->fd->rel_ts);
 348
 349         if (st->start < 0.0) st->start = now;
 350
 351         st->elapsed = now - st->start;
 352
 353         if (st->cfg->packet)
 354                 return st->cfg->packet(st,pinfo,edt,pri);
 355         else
 356                 return 0;
 357 }
 358
 359 extern stats_tree_cfg*
 360 stats_tree_get_cfg_by_abbr(char *abbr)
 361 {
 362         return g_hash_table_lookup(registry,abbr);
 363 }
 364
 365
 366 struct _stats_tree_pres_cbs {
 367         void (*setup_node_pr)(stat_node*);
 368         void (*free_node_pr)(stat_node*);
 369         void (*draw_node)(stat_node*);
 370         void (*reset_node)(stat_node*);
 371         tree_pres *(*new_tree_pr)(stats_tree*);
 372         void (*free_tree_pr)(stats_tree*);
 373         void (*draw_tree)(stats_tree*);
 374         void (*reset_tree)(stats_tree*);
 375 };
 376
 377 static void
 378 setup_tree_presentation(gpointer k _U_, gpointer v, gpointer p)
 379 {
 380         stats_tree_cfg *cfg = v;
 381         struct _stats_tree_pres_cbs *d = p;
 382
 383         cfg->in_use = FALSE;
 384         cfg->setup_node_pr = d->setup_node_pr;
 385         cfg->new_tree_pr = d->new_tree_pr;
 386         cfg->free_node_pr = d->free_node_pr;
 387         cfg->free_tree_pr = d->free_tree_pr;
 388         cfg->draw_node = d->draw_node;
 389         cfg->draw_tree = d->draw_tree;
 390         cfg->reset_node = d->reset_node;
 391         cfg->reset_tree = d->reset_tree;
 392
 393 }
 394
 395 extern void
 396 stats_tree_presentation(void (*registry_iterator)(gpointer,gpointer,gpointer),
 397                         void (*setup_node_pr)(stat_node*),
 398                         void (*free_node_pr)(stat_node*),
 399                         void (*draw_node)(stat_node*),
 400                         void (*reset_node)(stat_node*),
 401                         tree_pres *(*new_tree_pr)(stats_tree*),
 402                         void (*free_tree_pr)(stats_tree*),
 403                         void (*draw_tree)(stats_tree*),
 404                         void (*reset_tree)(stats_tree*),
 405                         void *data)
 406 {
 407         static struct _stats_tree_pres_cbs d;
 408
 409         d.setup_node_pr = setup_node_pr;
 410         d.new_tree_pr = new_tree_pr;
 411         d.free_node_pr = free_node_pr;
 412         d.free_tree_pr = free_tree_pr;
 413         d.draw_node = draw_node;
 414         d.draw_tree = draw_tree;
 415         d.reset_node = reset_node;
 416         d.reset_tree = reset_tree;
 417
 418         if (registry) g_hash_table_foreach(registry,setup_tree_presentation,&d);
 419
 420         if (registry_iterator && registry)
 421                 g_hash_table_foreach(registry,registry_iterator,data);
 422
 423 }
 424
 425
 426 /* creates a stat_tree node
 427 *    name: the name of the stats_tree node
 428 *    parent_name: the name of the ALREADY REGISTERED parent
 429 *    with_hash: whether or not it should keep a hash with it's children names
 430 *    as_named_node: whether or not it has to be registered in the root namespace
 431 */
 432 static stat_node*
 433 new_stat_node(stats_tree *st, const gchar *name, int parent_id,
 434               gboolean with_hash, gboolean as_parent_node)
 435 {
 436
 437         stat_node *node = g_malloc (sizeof(stat_node));
 438         stat_node *last_chld = NULL;
 439
 440         node->counter = 0;
 441         node->name = g_strdup(name);
 442         node->children = NULL;
 443         node->next = NULL;
 444         node->st = (stats_tree*) st;
 445         node->hash = with_hash ? g_hash_table_new(g_str_hash,g_str_equal) : NULL;
 446         node->parent = NULL;
 447         node->rng  =  NULL;
 448
 449         if (as_parent_node) {
 450                 g_hash_table_insert(st->names,
 451                                                         node->name,
 452                                                         node);
 453
 454                 g_ptr_array_add(st->parents,node);
 455
 456                 node->id = st->parents->len - 1;
 457         } else {
 458                 node->id = -1;
 459         }
 460
 461         if (parent_id >= 0 && parent_id < (int) st->parents->len ) {
 462                 node->parent = g_ptr_array_index(st->parents,parent_id);
 463         } else {
 464                 /* ??? should we set the parent to be root ??? */
 465                 g_assert_not_reached();
 466         }
 467
 468         if (node->parent->children) {
 469                 /* insert as last child */
 470
 471                 for (last_chld = node->parent->children;
 472                          last_chld->next;
 473                          last_chld = last_chld->next ) ;
 474
 475                 last_chld->next = node;
 476
 477         } else {
 478                 /* insert as first child */
 479                 node->parent->children = node;
 480         }
 481
 482         if(node->parent->hash) {
 483                 g_hash_table_insert(node->parent->hash,node->name,node);
 484         }
 485
 486         if (st->cfg->setup_node_pr) {
 487                 st->cfg->setup_node_pr(node);
 488         } else {
 489                 node->pr = NULL;
 490         }
 491
 492         return node;
 493 }
 494 /***/
 495
 496 extern int
 497 stats_tree_create_node(stats_tree *st, const gchar *name, int parent_id, gboolean with_hash)
 498 {
 499         stat_node *node = new_stat_node(st,name,parent_id,with_hash,TRUE);
 500
 501         if (node)
 502                 return node->id;
 503         else
 504                 return 0;
 505 }
 506
 507 /* XXX: should this be a macro? */
 508 extern int
 509 stats_tree_create_node_by_pname(stats_tree *st, const gchar *name,
 510                                 const gchar *parent_name, gboolean with_children)
 511 {
 512         return stats_tree_create_node(st,name,stats_tree_parent_id_by_name(st,parent_name),with_children);
 513 }
 514
 515
 516
 517 /*
 518  * Increases by delta the counter of the node whose name is given
 519  * if the node does not exist yet it's created (with counter=1)
 520  * using parent_name as parent node.
 521  * with_hash=TRUE to indicate that the created node will have a parent
 522  */
 523 extern int
 524 stats_tree_manip_node(manip_node_mode mode, stats_tree *st, const char *name,
 525                       int parent_id, gboolean with_hash, gint value)
 526 {
 527         stat_node *node = NULL;
 528         stat_node *parent = NULL;
 529
 530         g_assert( parent_id >= 0 && parent_id < (int) st->parents->len );
 531
 532         parent = g_ptr_array_index(st->parents,parent_id);
 533
 534         if( parent->hash ) {
 535                 node = g_hash_table_lookup(parent->hash,name);
 536         } else {
 537                 node = g_hash_table_lookup(st->names,name);
 538         }
 539
 540         if ( node == NULL )
 541                 node = new_stat_node(st,name,parent_id,with_hash,with_hash);
 542
 543         switch (mode) {
 544                 case MN_INCREASE: node->counter += value; break;
 545                 case MN_SET: node->counter = value; break;
 546         }
 547
 548         if (node)
 549                 return node->id;
 550         else
 551                 return -1;
 552 }
 553
 554
 555 extern char*
 556 stats_tree_get_abbr(const char *optarg)
 557 {
 558         guint i;
 559
 560         /* XXX: this fails when tshark is given any options
 561            after the -z */
 562         g_assert(optarg != NULL);
 563
 564         for (i=0; optarg[i] && optarg[i] != ','; i++);
 565
 566         if (optarg[i] == ',') {
 567                 return g_strndup(optarg,i);
 568         } else {
 569                 return NULL;
 570         }
 571 }
 572
 573
 574 /*
 575  * This function accepts an input string which should define a long integer range.
 576  * The normal result is a struct containing the floor and ceil value of this
 577  * range.
 578  *
 579  * It is allowed to define a range string in the following ways :
 580  *
 581  * "0-10" -> { 0, 10 }
 582  * "-0" -> { G_MININT, 0 }
 583  * "0-" -> { 0, G_MAXINT }
 584  * "-" -> { G_MININT, G_MAXINT }
 585  *
 586  * Note that this function is robust to buggy input string. If in some cases it
 587  * returns NULL, it but may also return a pair with undefined values.
 588  *
 589  */
 590 static range_pair_t*
 591 get_range(char *rngstr)
 592 {
 593         gchar **split;
 594         range_pair_t *rng;
 595
 596         split = g_strsplit((gchar*)rngstr,"-",2);
 597
 598         /* empty string */
 599         if (split[0] == NULL) {
 600           g_strfreev(split);
 601           return NULL;
 602         }
 603
 604         /* means we have a non empty string
 605          * which does not contain a delimiter */
 606         if (split[1] == NULL) {
 607           g_strfreev(split);
 608           return NULL;
 609         }
 610
 611         rng = g_malloc(sizeof(range_pair_t));
 612
 613         /* string == "X-?" */
 614         if (*(split[0]) != '\0') {
 615             rng->floor = strtol(split[0],NULL,10);
 616         } else
 617           /* string == "-?" */
 618           rng->floor = G_MININT;
 619
 620         /* string != "?-" */
 621         if (*(split[1]) != '\0') {
 622           rng->ceil  = strtol(split[1],NULL,10);
 623         } else
 624           /* string == "?-" */
 625           rng->ceil = G_MAXINT;
 626
 627         g_strfreev(split);
 628
 629         return rng;
 630 }
 631
 632
 633 extern int
 634 stats_tree_create_range_node(stats_tree *st, const gchar *name, int parent_id, ...)
 635 {
 636         va_list list;
 637         gchar *curr_range;
 638         stat_node *rng_root = new_stat_node(st, name, parent_id, FALSE, TRUE);
 639         stat_node *range_node = NULL;
 640
 641         va_start( list, parent_id );
 642         while (( curr_range = va_arg(list, gchar*) )) {
 643                 range_node = new_stat_node(st, curr_range, rng_root->id, FALSE, FALSE);
 644                 range_node->rng = get_range(curr_range);
 645         }
 646         va_end( list );
 647
 648         return rng_root->id;
 649 }
 650
 651 /****/
 652 extern int
 653 stats_tree_parent_id_by_name(stats_tree *st, const gchar *parent_name)
 654 {
 655         stat_node *node = g_hash_table_lookup(st->names,parent_name);
 656
 657         if (node)
 658                 return node->id;
 659         else
 660                 return 0; /* XXX: this is the root shoud we return -1 instead?*/
 661 }
 662
 663
 664 extern int
 665 stats_tree_range_node_with_pname(stats_tree *st, const gchar *name,
 666                                  const gchar *parent_name, ...)
 667 {
 668         va_list list;
 669         gchar *curr_range;
 670         stat_node *range_node = NULL;
 671         int parent_id = stats_tree_parent_id_by_name(st,parent_name);
 672         stat_node *rng_root = new_stat_node(st, name, parent_id, FALSE, TRUE);
 673
 674         va_start( list, parent_name );
 675         while (( curr_range = va_arg(list, gchar*) )) {
 676                 range_node = new_stat_node(st, curr_range, rng_root->id, FALSE, FALSE);
 677                 range_node->rng = get_range(curr_range);
 678         }
 679         va_end( list );
 680
 681         return rng_root->id;
 682 }
 683
 684
 685 extern int
 686 stats_tree_tick_range(stats_tree *st, const gchar *name, int parent_id,
 687                       int value_in_range)
 688 {
 689
 690         stat_node *node = NULL;
 691         stat_node *parent = NULL;
 692         stat_node *child = NULL;
 693         gint floor, ceil;
 694
 695         if (parent_id >= 0 && parent_id < (int) st->parents->len) {
 696                 parent = g_ptr_array_index(st->parents,parent_id);
 697         } else {
 698                 g_assert_not_reached();
 699         }
 700
 701         if( parent->hash ) {
 702                 node = g_hash_table_lookup(parent->hash,name);
 703         } else {
 704                 node = g_hash_table_lookup(st->names,name);
 705         }
 706
 707         if ( node == NULL )
 708                 g_assert_not_reached();
 709
 710         for ( child = node->children; child; child = child->next) {
 711                 floor =  child->rng->floor;
 712                 ceil = child->rng->ceil;
 713
 714                 if ( value_in_range >= floor && value_in_range <= ceil ) {
 715                         child->counter++;
 716                         return node->id;
 717                 }
 718         }
 719
 720         return node->id;
 721 }
 722
 723 extern int
 724 stats_tree_create_pivot(stats_tree *st, const gchar *name, int parent_id)
 725 {
 726         stat_node *node = new_stat_node(st,name,parent_id,TRUE,TRUE);
 727
 728         if (node)
 729                 return node->id;
 730         else
 731                 return 0;
 732 }
 733
 734 extern int
 735 stats_tree_create_pivot_by_pname(stats_tree *st, const gchar *name,
 736                                  const gchar *parent_name)
 737 {
 738         int parent_id = stats_tree_parent_id_by_name(st,parent_name);
 739         stat_node *node;
 740
 741         node = new_stat_node(st,name,parent_id,TRUE,TRUE);
 742
 743         if (node)
 744                 return node->id;
 745         else
 746                 return 0;
 747 }
 748
 749 extern int
 750 stats_tree_tick_pivot(stats_tree *st, int pivot_id, const gchar *pivot_value)
 751 {
 752
 753         stat_node *parent = g_ptr_array_index(st->parents,pivot_id);
 754
 755         parent->counter++;
 756         stats_tree_manip_node( MN_INCREASE, st, pivot_value, pivot_id, FALSE, 1);
 757
 758         return pivot_id;
 759 }
 760