l4/pkg/valgrind/src/valgrind-3.6.0-svn/cachegrind/cg_merge.c

   1
   2 /*--------------------------------------------------------------------*/
   3 /*--- A program that merges multiple cachegrind output files.      ---*/
   4 /*---                                                   cg_merge.c ---*/
   5 /*--------------------------------------------------------------------*/
   6
   7 /*
   8   This file is part of Cachegrind, a Valgrind tool for cache
   9   profiling programs.
  10
  11   Copyright (C) 2002-2010 Nicholas Nethercote
  12      njn@valgrind.org
  13
  14   AVL tree code derived from
  15   ANSI C Library for maintainance of AVL Balanced Trees
  16   (C) 2000 Daniel Nagy, Budapest University of Technology and Economics
  17   Released under GNU General Public License (GPL) version 2
  18
  19   This program is free software; you can redistribute it and/or
  20   modify it under the terms of the GNU General Public License as
  21   published by the Free Software Foundation; either version 2 of the
  22   License, or (at your option) any later version.
  23
  24   This program is distributed in the hope that it will be useful, but
  25   WITHOUT ANY WARRANTY; without even the implied warranty of
  26   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  27   General Public License for more details.
  28
  29   You should have received a copy of the GNU General Public License
  30   along with this program; if not, write to the Free Software
  31   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  32   02111-1307, USA.
  33
  34   The GNU General Public License is contained in the file COPYING.
  35 */
  36
  37 #include <stdio.h>
  38 #include <stdlib.h>
  39 #include <assert.h>
  40 #include <string.h>
  41 #include <ctype.h>
  42
  43 typedef  signed long   Word;
  44 typedef  unsigned long UWord;
  45 typedef  unsigned char Bool;
  46 #define True ((Bool)1)
  47 #define False ((Bool)0)
  48 typedef  signed int    Int;
  49 typedef  unsigned int  UInt;
  50 typedef  unsigned long long int ULong;
  51 typedef  signed char   Char;
  52 typedef  size_t        SizeT;
  53
  54
  55 //------------------------------------------------------------------//
  56 //---                           WordFM                           ---//
  57 //---                      Public interface                      ---//
  58 //------------------------------------------------------------------//
  59
  60 typedef  struct _WordFM  WordFM; /* opaque */
  61
  62 /* Initialise a WordFM */
  63 void initFM ( WordFM* t,
  64               void*   (*alloc_nofail)( SizeT ),
  65               void    (*dealloc)(void*),
  66               Word    (*kCmp)(Word,Word) );
  67
  68 /* Allocate and initialise a WordFM */
  69 WordFM* newFM( void* (*alloc_nofail)( SizeT ),
  70                void  (*dealloc)(void*),
  71                Word  (*kCmp)(Word,Word) );
  72
  73 /* Free up the FM.  If kFin is non-NULL, it is applied to keys
  74    before the FM is deleted; ditto with vFin for vals. */
  75 void deleteFM ( WordFM*, void(*kFin)(Word), void(*vFin)(Word) );
  76
  77 /* Add (k,v) to fm.  If a binding for k already exists, it is updated
  78    to map to this new v.  In that case we should really return the
  79    previous v so that caller can finalise it.  Oh well. */
  80 void addToFM ( WordFM* fm, Word k, Word v );
  81
  82 // Delete key from fm, returning associated val if found
  83 Bool delFromFM ( WordFM* fm, /*OUT*/Word* oldV, Word key );
  84
  85 // Look up in fm, assigning found val at spec'd address
  86 Bool lookupFM ( WordFM* fm, /*OUT*/Word* valP, Word key );
  87
  88 Word sizeFM ( WordFM* fm );
  89
  90 // set up FM for iteration
  91 void initIterFM ( WordFM* fm );
  92
  93 // get next key/val pair.  Will assert if fm has been modified
  94 // or looked up in since initIterFM was called.
  95 Bool nextIterFM ( WordFM* fm, /*OUT*/Word* pKey, /*OUT*/Word* pVal );
  96
  97 // clear the I'm iterating flag
  98 void doneIterFM ( WordFM* fm );
  99
 100 // Deep copy a FM.  If dopyK is NULL, keys are copied verbatim.
 101 // If non-null, dopyK is applied to each key to generate the
 102 // version in the new copy.  In that case, if the argument to dopyK
 103 // is non-NULL but the result is NULL, it is assumed that dopyK
 104 // could not allocate memory, in which case the copy is abandoned
 105 // and NULL is returned.  Ditto with dopyV for values.
 106 WordFM* dopyFM ( WordFM* fm, Word(*dopyK)(Word), Word(*dopyV)(Word) );
 107
 108 //------------------------------------------------------------------//
 109 //---                         end WordFM                         ---//
 110 //---                      Public interface                      ---//
 111 //------------------------------------------------------------------//
 112
 113
 114 static char* argv0 = "cg_merge";
 115
 116 /* Keep track of source filename/line no so as to be able to
 117    print decent error messages. */
 118 typedef
 119    struct {
 120       FILE* fp;
 121       UInt  lno;
 122       char* filename;
 123    }
 124    SOURCE;
 125
 126 static void printSrcLoc ( SOURCE* s )
 127 {
 128    fprintf(stderr, "%s: near %s line %u\n", argv0, s->filename, s->lno-1);
 129 }
 130
 131 __attribute__((noreturn))
 132 static void mallocFail ( SOURCE* s, char* who )
 133 {
 134    fprintf(stderr, "%s: out of memory in %s\n", argv0, who );
 135    printSrcLoc( s );
 136    exit(2);
 137 }
 138
 139 __attribute__((noreturn))
 140 static void parseError ( SOURCE* s, char* msg )
 141 {
 142    fprintf(stderr, "%s: parse error: %s\n", argv0, msg );
 143    printSrcLoc( s );
 144    exit(1);
 145 }
 146
 147 __attribute__((noreturn))
 148 static void barf ( SOURCE* s, char* msg )
 149 {
 150    fprintf(stderr, "%s: %s\n", argv0, msg );
 151    printSrcLoc( s );
 152    exit(1);
 153 }
 154
 155 // Read a line
 156 #define M_LINEBUF 40960
 157 static char line[M_LINEBUF];
 158
 159 // True if anything read, False if at EOF
 160 static Bool readline ( SOURCE* s )
 161 {
 162    int ch, i = 0;
 163    line[0] = 0;
 164    while (1) {
 165       if (i >= M_LINEBUF-10)
 166          parseError(s, "Unexpected long line in input file");
 167       ch = getc(s->fp);
 168       if (ch != EOF) {
 169           line[i++] = ch;
 170           line[i] = 0;
 171           if (ch == '\n') {
 172              line[i-1] = 0;
 173              s->lno++;
 174              break;
 175           }
 176       } else {
 177          if (ferror(s->fp)) {
 178             perror(argv0);
 179             barf(s, "I/O error while reading input file");
 180          } else {
 181             // hit EOF
 182             break;
 183          }
 184       }
 185    }
 186    return line[0] != 0;
 187 }
 188
 189 static Bool streqn ( char* s1, char* s2, size_t n )
 190 {
 191    return 0 == strncmp(s1, s2, n);
 192 }
 193
 194 static Bool streq ( char* s1, char* s2 )
 195 {
 196    return 0 == strcmp(s1, s2 );
 197 }
 198
 199
 200 ////////////////////////////////////////////////////////////////
 201
 202 typedef
 203    struct {
 204       char* fi_name;
 205       char* fn_name;
 206    }
 207    FileFn;
 208
 209 typedef
 210    struct {
 211       Int n_counts;
 212       ULong* counts;
 213    }
 214    Counts;
 215
 216 typedef
 217    struct {
 218       // null-terminated vector of desc_lines
 219       char** desc_lines;
 220
 221       // Cmd line
 222       char* cmd_line;
 223
 224       // Events line
 225       char* events_line;
 226       Int   n_events;
 227
 228       // Summary line (copied from input)
 229       char* summary_line;
 230
 231       /* Outermost map is
 232             WordFM FileFn* innerMap
 233          where innerMap is   WordFM line-number=UWord Counts */
 234       WordFM* outerMap;
 235
 236       // Summary counts (computed whilst parsing)
 237       // should match .summary_line
 238       Counts* summary;
 239    }
 240    CacheProfFile;
 241
 242 static FileFn* new_FileFn ( char* file_name, char* fn_name )
 243 {
 244    FileFn* ffn = malloc(sizeof(FileFn));
 245    if (ffn == NULL)
 246       return NULL;
 247    ffn->fi_name = file_name;
 248    ffn->fn_name = fn_name;
 249    return ffn;
 250 }
 251
 252 static void ddel_FileFn ( FileFn* ffn )
 253 {
 254    if (ffn->fi_name)
 255       free(ffn->fi_name);
 256    if (ffn->fn_name)
 257       free(ffn->fn_name);
 258    memset(ffn, 0, sizeof(FileFn));
 259    free(ffn);
 260 }
 261
 262 static FileFn* dopy_FileFn ( FileFn* ff )
 263 {
 264    char* fi2 = strdup(ff->fi_name);
 265    char* fn2 = strdup(ff->fn_name);
 266    if ((!fi2) || (!fn2))
 267       return NULL;
 268    return new_FileFn( fi2, fn2 );
 269 }
 270
 271 static Counts* new_Counts ( Int n_counts, /*COPIED*/ULong* counts )
 272 {
 273    Int i;
 274    Counts* cts = malloc(sizeof(Counts));
 275    if (cts == NULL)
 276       return NULL;
 277
 278    assert(n_counts >= 0);
 279    cts->counts = malloc(n_counts * sizeof(ULong));
 280    if (cts->counts == NULL)
 281       return NULL;
 282
 283    cts->n_counts = n_counts;
 284    for (i = 0; i < n_counts; i++)
 285       cts->counts[i] = counts[i];
 286
 287    return cts;
 288 }
 289
 290 static Counts* new_Counts_Zeroed ( Int n_counts )
 291 {
 292    Int i;
 293    Counts* cts = malloc(sizeof(Counts));
 294    if (cts == NULL)
 295       return NULL;
 296
 297    assert(n_counts >= 0);
 298    cts->counts = malloc(n_counts * sizeof(ULong));
 299    if (cts->counts == NULL)
 300       return NULL;
 301
 302    cts->n_counts = n_counts;
 303    for (i = 0; i < n_counts; i++)
 304       cts->counts[i] = 0;
 305
 306    return cts;
 307 }
 308
 309 static void sdel_Counts ( Counts* cts )
 310 {
 311    memset(cts, 0, sizeof(Counts));
 312    free(cts);
 313 }
 314
 315 static void ddel_Counts ( Counts* cts )
 316 {
 317    if (cts->counts)
 318       free(cts->counts);
 319    memset(cts, 0, sizeof(Counts));
 320    free(cts);
 321 }
 322
 323 static Counts* dopy_Counts ( Counts* cts )
 324 {
 325    return new_Counts( cts->n_counts, cts->counts );
 326 }
 327
 328 static
 329 CacheProfFile* new_CacheProfFile ( char**  desc_lines,
 330                                    char*   cmd_line,
 331                                    char*   events_line,
 332                                    Int     n_events,
 333                                    char*   summary_line,
 334                                    WordFM* outerMap,
 335                                    Counts* summary )
 336 {
 337    CacheProfFile* cpf = malloc(sizeof(CacheProfFile));
 338    if (cpf == NULL)
 339       return NULL;
 340    cpf->desc_lines   = desc_lines;
 341    cpf->cmd_line     = cmd_line;
 342    cpf->events_line  = events_line;
 343    cpf->n_events     = n_events;
 344    cpf->summary_line = summary_line;
 345    cpf->outerMap     = outerMap;
 346    cpf->summary      = summary;
 347    return cpf;
 348 }
 349
 350 static WordFM* dopy_InnerMap ( WordFM* innerMap )
 351 {
 352    return dopyFM ( innerMap, NULL,
 353                              (Word(*)(Word))dopy_Counts );
 354 }
 355
 356 static void ddel_InnerMap ( WordFM* innerMap )
 357 {
 358    deleteFM( innerMap, NULL, (void(*)(Word))ddel_Counts );
 359 }
 360
 361 static void ddel_CacheProfFile ( CacheProfFile* cpf )
 362 {
 363    char** p;
 364    if (cpf->desc_lines) {
 365       for (p = cpf->desc_lines; *p; p++)
 366          free(*p);
 367       free(cpf->desc_lines);
 368    }
 369    if (cpf->cmd_line)
 370       free(cpf->cmd_line);
 371    if (cpf->events_line)
 372       free(cpf->events_line);
 373    if (cpf->summary_line)
 374       free(cpf->summary_line);
 375    if (cpf->outerMap)
 376       deleteFM( cpf->outerMap, (void(*)(Word))ddel_FileFn,
 377                                (void(*)(Word))ddel_InnerMap );
 378    if (cpf->summary)
 379       ddel_Counts(cpf->summary);
 380
 381    memset(cpf, 0, sizeof(CacheProfFile));
 382    free(cpf);
 383 }
 384
 385 static void showCounts ( FILE* f, Counts* c )
 386 {
 387    Int i;
 388    for (i = 0; i < c->n_counts; i++) {
 389       fprintf(f, "%lld ", c->counts[i]);
 390    }
 391 }
 392
 393 static void show_CacheProfFile ( FILE* f, CacheProfFile* cpf )
 394 {
 395    Int     i;
 396    char**  d;
 397    FileFn* topKey;
 398    WordFM* topVal;
 399    UWord   subKey;
 400    Counts* subVal;
 401
 402    for (d = cpf->desc_lines; *d; d++)
 403       fprintf(f, "%s\n", *d);
 404    fprintf(f, "%s\n", cpf->cmd_line);
 405    fprintf(f, "%s\n", cpf->events_line);
 406
 407    initIterFM( cpf->outerMap );
 408    while (nextIterFM( cpf->outerMap, (Word*)(&topKey), (Word*)(&topVal) )) {
 409       fprintf(f, "fl=%s\nfn=%s\n",
 410                  topKey->fi_name, topKey->fn_name );
 411       initIterFM( topVal );
 412       while (nextIterFM( topVal, (Word*)(&subKey), (Word*)(&subVal) )) {
 413          fprintf(f, "%ld   ", subKey );
 414          showCounts( f, subVal );
 415          fprintf(f, "\n");
 416       }
 417       doneIterFM( topVal );
 418    }
 419    doneIterFM( cpf->outerMap );
 420
 421    //fprintf(f, "%s\n", cpf->summary_line);
 422    fprintf(f, "summary:");
 423    for (i = 0; i < cpf->summary->n_counts; i++)
 424       fprintf(f, " %lld", cpf->summary->counts[i]);
 425    fprintf(f, "\n");
 426 }
 427
 428 ////////////////////////////////////////////////////////////////
 429
 430 static Word cmp_FileFn ( Word s1, Word s2 )
 431 {
 432    FileFn* ff1 = (FileFn*)s1;
 433    FileFn* ff2 = (FileFn*)s2;
 434    Word r = strcmp(ff1->fi_name, ff2->fi_name);
 435    if (r == 0)
 436       r = strcmp(ff1->fn_name, ff2->fn_name);
 437    return r;
 438 }
 439
 440 static Word cmp_unboxed_UWord ( Word s1, Word s2 )
 441 {
 442    UWord u1 = (UWord)s1;
 443    UWord u2 = (UWord)s2;
 444    if (u1 < u2) return -1;
 445    if (u1 > u2) return 1;
 446    return 0;
 447 }
 448
 449 ////////////////////////////////////////////////////////////////
 450
 451 static Bool parse_ULong ( /*OUT*/ULong* res, /*INOUT*/char** pptr)
 452 {
 453    ULong u64;
 454    char* ptr = *pptr;
 455    while (isspace(*ptr)) ptr++;
 456    if (!isdigit(*ptr)) {
 457       return False; /* end of string, or junk */
 458       *pptr = ptr;
 459    }
 460    u64 = 0;
 461    while (isdigit(*ptr)) {
 462       u64 = (u64 * 10) + (ULong)(*ptr - '0');
 463       ptr++;
 464    }
 465    *res = u64;
 466    *pptr = ptr;
 467    return True;
 468 }
 469
 470 // str is a line of digits, starting with a line number.  Parse it,
 471 // returning the first number in *lnno and the rest in a newly
 472 // allocated Counts struct.  If lnno is non-NULL, treat the first
 473 // number as a line number and assign it to *lnno instead of
 474 // incorporating it in the counts array.
 475 static
 476 Counts* splitUpCountsLine ( SOURCE* s, /*OUT*/UWord* lnno, char* str )
 477 {
 478 #define N_TMPC 50
 479    Bool    ok;
 480    Counts* counts;
 481    ULong   tmpC[N_TMPC];
 482    Int     n_tmpC = 0;
 483    while (1) {
 484       ok = parse_ULong( &tmpC[n_tmpC], &str );
 485       if (!ok)
 486          break;
 487       n_tmpC++;
 488       if (n_tmpC >= N_TMPC)
 489          barf(s, "N_TMPC too low.  Increase and recompile.");
 490    }
 491    if (*str != 0)
 492       parseError(s, "garbage in counts line");
 493    if (lnno ? (n_tmpC < 2) : (n_tmpC < 1))
 494       parseError(s, "too few counts in count line");
 495
 496    if (lnno) {
 497       *lnno = (UWord)tmpC[0];
 498       counts = new_Counts( n_tmpC-1, /*COPIED*/&tmpC[1] );
 499    } else {
 500       counts = new_Counts( n_tmpC, /*COPIED*/&tmpC[0] );
 501    }
 502
 503    return counts;
 504 #undef N_TMPC
 505 }
 506
 507 static void addCounts ( SOURCE* s, /*OUT*/Counts* counts1, Counts* counts2 )
 508 {
 509    Int i;
 510    if (counts1->n_counts != counts2->n_counts)
 511       parseError(s, "addCounts: inconsistent number of counts");
 512    for (i = 0; i < counts1->n_counts; i++)
 513       counts1->counts[i] += counts2->counts[i];
 514 }
 515
 516 static Bool addCountsToMap ( SOURCE* s,
 517                              WordFM* counts_map,
 518                              UWord lnno, Counts* newCounts )
 519 {
 520    Counts* oldCounts;
 521    // look up lnno in the map.  If none present, add a binding
 522    // lnno->counts.  If present, add counts to the existing entry.
 523    if (lookupFM( counts_map, (Word*)(&oldCounts), (Word)lnno )) {
 524       // merge with existing binding
 525       addCounts( s, oldCounts, newCounts );
 526       return True;
 527    } else {
 528       // create new binding
 529       addToFM( counts_map, (Word)lnno, (Word)newCounts );
 530       return False;
 531    }
 532 }
 533
 534 static
 535 void handle_counts ( SOURCE* s,
 536                      CacheProfFile* cpf,
 537                      char* fi, char* fn, char* newCountsStr )
 538 {
 539    WordFM* countsMap;
 540    Bool    freeNewCounts;
 541    UWord   lnno;
 542    Counts* newCounts;
 543    FileFn* topKey;
 544
 545    if (0)  printf("%s %s %s\n", fi, fn, newCountsStr );
 546
 547    // parse the numbers
 548    newCounts = splitUpCountsLine( s, &lnno, newCountsStr );
 549
 550    // Did we get the right number?
 551    if (newCounts->n_counts != cpf->n_events)
 552       goto oom;
 553
 554    // allocate the key
 555    topKey = malloc(sizeof(FileFn));
 556    if (topKey) {
 557       topKey->fi_name = strdup(fi);
 558       topKey->fn_name = strdup(fn);
 559    }
 560    if (! (topKey && topKey->fi_name && topKey->fn_name))
 561       mallocFail(s, "handle_counts:");
 562
 563    // search for it
 564    if (lookupFM( cpf->outerMap, (Word*)(&countsMap), (Word)topKey )) {
 565       // found it.  Merge in new counts
 566       freeNewCounts = addCountsToMap( s, countsMap, lnno, newCounts );
 567       ddel_FileFn(topKey);
 568    } else {
 569       // not found in the top map.  Create new entry
 570       countsMap = newFM( malloc, free, cmp_unboxed_UWord );
 571       if (!countsMap)
 572          goto oom;
 573       addToFM( cpf->outerMap, (Word)topKey, (Word)countsMap );
 574       freeNewCounts = addCountsToMap( s, countsMap, lnno, newCounts );
 575    }
 576
 577    // also add to running summary total
 578    addCounts( s, cpf->summary, newCounts );
 579
 580    // if safe to do so, free up the count vector
 581    if (freeNewCounts)
 582       ddel_Counts(newCounts);
 583
 584    return;
 585
 586   oom:
 587    parseError(s, "# counts doesn't match # events");
 588 }
 589
 590
 591 /* Parse a complete file from the stream in 's'.  If a parse error
 592    happens, do not return; instead exit via parseError().  If an
 593    out-of-memory condition happens, do not return; instead exit via
 594    mallocError().
 595 */
 596 static CacheProfFile* parse_CacheProfFile ( SOURCE* s )
 597 {
 598 #define M_TMP_DESCLINES 10
 599
 600    Int            i;
 601    Bool           b;
 602    char*          tmp_desclines[M_TMP_DESCLINES];
 603    char*          p;
 604    int            n_tmp_desclines = 0;
 605    CacheProfFile* cpf;
 606    Counts*        summaryRead;
 607    char*          curr_fn_init = "???";
 608    char*          curr_fl_init = "???";
 609    char*          curr_fn      = curr_fn_init;
 610    char*          curr_fl      = curr_fl_init;
 611
 612    cpf = new_CacheProfFile( NULL, NULL, NULL, 0, NULL, NULL, NULL );
 613    if (cpf == NULL)
 614       mallocFail(s, "parse_CacheProfFile(1)");
 615
 616    // Parse "desc:" lines
 617    while (1) {
 618       b = readline(s);
 619       if (!b)
 620          break;
 621       if (!streqn(line, "desc: ", 6))
 622          break;
 623       if (n_tmp_desclines >= M_TMP_DESCLINES)
 624          barf(s, "M_TMP_DESCLINES too low; increase and recompile");
 625       tmp_desclines[n_tmp_desclines++] = strdup(line);
 626    }
 627
 628    if (n_tmp_desclines == 0)
 629       parseError(s, "parse_CacheProfFile: no DESC lines present");
 630
 631    cpf->desc_lines = malloc( (1+n_tmp_desclines) * sizeof(char*) );
 632    if (cpf->desc_lines == NULL)
 633       mallocFail(s, "parse_CacheProfFile(2)");
 634
 635    cpf->desc_lines[n_tmp_desclines] = NULL;
 636    for (i = 0; i < n_tmp_desclines; i++)
 637       cpf->desc_lines[i] = tmp_desclines[i];
 638
 639    // Parse "cmd:" line
 640    if (!streqn(line, "cmd: ", 5))
 641       parseError(s, "parse_CacheProfFile: no CMD line present");
 642
 643    cpf->cmd_line = strdup(line);
 644    if (cpf->cmd_line == NULL)
 645       mallocFail(s, "parse_CacheProfFile(3)");
 646
 647    // Parse "events:" line and figure out how many events there are
 648    b = readline(s);
 649    if (!b)
 650       parseError(s, "parse_CacheProfFile: eof before EVENTS line");
 651    if (!streqn(line, "events: ", 8))
 652       parseError(s, "parse_CacheProfFile: no EVENTS line present");
 653
 654    // figure out how many events there are by counting the number
 655    // of space-alphanum transitions in the events_line
 656    cpf->events_line = strdup(line);
 657    if (cpf->events_line == NULL)
 658       mallocFail(s, "parse_CacheProfFile(3)");
 659
 660    cpf->n_events = 0;
 661    assert(cpf->events_line[6] == ':');
 662    for (p = &cpf->events_line[6]; *p; p++) {
 663       if (p[0] == ' ' && isalpha(p[1]))
 664          cpf->n_events++;
 665    }
 666
 667    // create the running cross-check summary
 668    cpf->summary = new_Counts_Zeroed( cpf->n_events );
 669    if (cpf->summary == NULL)
 670       mallocFail(s, "parse_CacheProfFile(4)");
 671
 672    // create the outer map (file+fn name --> inner map)
 673    cpf->outerMap = newFM ( malloc, free, cmp_FileFn );
 674    if (cpf->outerMap == NULL)
 675       mallocFail(s, "parse_CacheProfFile(5)");
 676
 677    // process count lines
 678    while (1) {
 679       b = readline(s);
 680       if (!b)
 681          parseError(s, "parse_CacheProfFile: eof before SUMMARY line");
 682
 683       if (isdigit(line[0])) {
 684          handle_counts(s, cpf, curr_fl, curr_fn, line);
 685          continue;
 686       }
 687       else
 688       if (streqn(line, "fn=", 3)) {
 689          if (curr_fn != curr_fn_init)
 690             free(curr_fn);
 691          curr_fn = strdup(line+3);
 692          continue;
 693       }
 694       else
 695       if (streqn(line, "fl=", 3)) {
 696          if (curr_fl != curr_fl_init)
 697             free(curr_fl);
 698          curr_fl = strdup(line+3);
 699          continue;
 700       }
 701       else
 702       if (streqn(line, "summary: ", 9)) {
 703          break;
 704       }
 705       else
 706          parseError(s, "parse_CacheProfFile: unexpected line in main data");
 707    }
 708
 709    // finally, the "summary:" line
 710    if (!streqn(line, "summary: ", 9))
 711       parseError(s, "parse_CacheProfFile: missing SUMMARY line");
 712
 713    cpf->summary_line = strdup(line);
 714    if (cpf->summary_line == NULL)
 715       mallocFail(s, "parse_CacheProfFile(6)");
 716
 717    // there should be nothing more
 718    b = readline(s);
 719    if (b)
 720       parseError(s, "parse_CacheProfFile: "
 721                     "extraneous content after SUMMARY line");
 722
 723    // check the summary counts are as expected
 724    summaryRead = splitUpCountsLine( s, NULL, &cpf->summary_line[8] );
 725    if (summaryRead == NULL)
 726       mallocFail(s, "parse_CacheProfFile(7)");
 727    if (summaryRead->n_counts != cpf->n_events)
 728       parseError(s, "parse_CacheProfFile: wrong # counts in SUMMARY line");
 729    for (i = 0; i < summaryRead->n_counts; i++) {
 730       if (summaryRead->counts[i] != cpf->summary->counts[i]) {
 731          parseError(s, "parse_CacheProfFile: "
 732                        "computed vs stated SUMMARY counts mismatch");
 733       }
 734    }
 735    free(summaryRead->counts);
 736    sdel_Counts(summaryRead);
 737
 738    // since the summary counts are OK, free up the summary_line text
 739    // which contains the same info.
 740    if (cpf->summary_line) {
 741       free(cpf->summary_line);
 742       cpf->summary_line = NULL;
 743    }
 744
 745    if (curr_fn != curr_fn_init)
 746       free(curr_fn);
 747    if (curr_fl != curr_fl_init)
 748       free(curr_fl);
 749
 750    // All looks OK
 751    return cpf;
 752
 753 #undef N_TMP_DESCLINES
 754 }
 755
 756
 757 static void merge_CacheProfInfo ( SOURCE* s,
 758                                   /*MOD*/CacheProfFile* dst,
 759                                   CacheProfFile* src )
 760 {
 761    /* For each (filefn, innerMap) in src
 762       if filefn not in dst
 763          add binding dopy(filefn)->dopy(innerMap) in src
 764       else
 765          // merge src->innerMap with dst->innerMap
 766          for each (lineno, counts) in src->innerMap
 767          if lineno not in dst->innerMap
 768             add binding lineno->dopy(counts) to dst->innerMap
 769          else
 770             add counts into dst->innerMap[lineno]
 771    */
 772    /* Outer iterator:  FileFn* -> WordFM* (inner iterator)
 773       Inner iterator:  UWord   -> Counts*
 774    */
 775    FileFn* soKey;
 776    WordFM* soVal;
 777    WordFM* doVal;
 778    UWord   siKey;
 779    Counts* siVal;
 780    Counts* diVal;
 781
 782    /* First check mundane things: that the events: lines are
 783       identical. */
 784    if (!streq( dst->events_line, src->events_line ))
 785      barf(s, "\"events:\" line of most recent file does "
 786              "not match those previously processed");
 787
 788    initIterFM( src->outerMap );
 789
 790    // for (filefn, innerMap) in src
 791    while (nextIterFM( src->outerMap, (Word*)&soKey, (Word*)&soVal )) {
 792
 793       // is filefn in dst?
 794       if (! lookupFM( dst->outerMap, (Word*)&doVal, (Word)soKey )) {
 795
 796          // no .. add dopy(filefn) -> dopy(innerMap) to src
 797          FileFn* c_soKey = dopy_FileFn(soKey);
 798          WordFM* c_soVal = dopy_InnerMap(soVal);
 799          if ((!c_soKey) || (!c_soVal)) goto oom;
 800          addToFM( dst->outerMap, (Word)c_soKey, (Word)c_soVal );
 801
 802       } else {
 803
 804          // yes .. merge the two innermaps
 805          initIterFM( soVal );
 806
 807          // for (lno, counts) in soVal (source inner map)
 808          while (nextIterFM( soVal, (Word*)&siKey, (Word*)&siVal )) {
 809
 810             // is lno in the corresponding dst inner map?
 811             if (! lookupFM( doVal, (Word*)&diVal, siKey )) {
 812
 813                // no .. add lineno->dopy(counts) to dst inner map
 814                Counts* c_siVal = dopy_Counts( siVal );
 815                if (!c_siVal) goto oom;
 816                addToFM( doVal, siKey, (Word)c_siVal );
 817
 818             } else {
 819
 820                // yes .. merge counts into dst inner map val
 821                addCounts( s, diVal, siVal );
 822
 823             }
 824          }
 825
 826       }
 827
 828    }
 829
 830    // add the summaries too
 831    addCounts(s, dst->summary, src->summary );
 832
 833    return;
 834
 835   oom:
 836    mallocFail(s, "merge_CacheProfInfo");
 837 }
 838
 839 static void usage ( void )
 840 {
 841    fprintf(stderr, "%s: Merges multiple cachegrind output files into one\n",
 842                    argv0);
 843    fprintf(stderr, "%s: usage: %s [-o outfile] [files-to-merge]\n",
 844                    argv0, argv0);
 845    exit(1);
 846 }
 847
 848 int main ( int argc, char** argv )
 849 {
 850    Int            i;
 851    SOURCE         src;
 852    CacheProfFile  *cpf, *cpfTmp;
 853
 854    FILE*          outfile = NULL;
 855    char*          outfilename = NULL;
 856    Int            outfileix = 0;
 857
 858    if (argv[0])
 859       argv0 = argv[0];
 860
 861    if (argc < 2)
 862       usage();
 863
 864    for (i = 1; i < argc; i++) {
 865       if (streq(argv[i], "-h") || streq(argv[i], "--help"))
 866          usage();
 867    }
 868
 869    /* Scan args, looking for '-o outfilename'. */
 870    for (i = 1; i < argc; i++) {
 871       if (streq(argv[i], "-o")) {
 872          if (i+1 < argc) {
 873             outfilename = argv[i+1];
 874             outfileix   = i;
 875             break;
 876          } else {
 877             usage();
 878          }
 879       }
 880    }
 881
 882    cpf = NULL;
 883
 884    for (i = 1; i < argc; i++) {
 885
 886       if (i == outfileix) {
 887          /* Skip '-o' and whatever follows it */
 888          i += 1;
 889          continue;
 890       }
 891
 892       fprintf(stderr, "%s: parsing %s\n", argv0, argv[i]);
 893       src.lno      = 1;
 894       src.filename = argv[i];
 895       src.fp       = fopen(src.filename, "r");
 896       if (!src.fp) {
 897          perror(argv0);
 898          barf(&src, "Cannot open input file");
 899       }
 900       assert(src.fp);
 901       cpfTmp = parse_CacheProfFile( &src );
 902       fclose(src.fp);
 903
 904       /* If this isn't the first file, merge */
 905       if (cpf == NULL) {
 906          /* this is the first file */
 907          cpf = cpfTmp;
 908       } else {
 909          /* not the first file; merge */
 910          fprintf(stderr, "%s: merging %s\n", argv0, argv[i]);
 911          merge_CacheProfInfo( &src, cpf, cpfTmp );
 912          ddel_CacheProfFile( cpfTmp );
 913       }
 914
 915    }
 916
 917    /* Now create the output file. */
 918
 919    if (cpf) {
 920
 921       fprintf(stderr, "%s: writing %s\n",
 922                        argv0, outfilename ? outfilename : "(stdout)" );
 923
 924       /* Write the output. */
 925       if (outfilename) {
 926          outfile = fopen(outfilename, "w");
 927          if (!outfile) {
 928             fprintf(stderr, "%s: can't create output file %s\n",
 929                             argv0, outfilename);
 930             perror(argv0);
 931             exit(1);
 932          }
 933       } else {
 934          outfile = stdout;
 935       }
 936
 937       show_CacheProfFile( outfile, cpf );
 938       if (ferror(outfile)) {
 939          fprintf(stderr, "%s: error writing output file %s\n",
 940                          argv0, outfilename);
 941          perror(argv0);
 942          if (outfile != stdout)
 943             fclose(outfile);
 944          exit(1);
 945       }
 946
 947       fflush(outfile);
 948       if (outfile != stdout)
 949          fclose( outfile );
 950
 951       ddel_CacheProfFile( cpf );
 952    }
 953
 954    return 0;
 955 }
 956
 957
 958 //------------------------------------------------------------------//
 959 //---                           WordFM                           ---//
 960 //---                       Implementation                       ---//
 961 //------------------------------------------------------------------//
 962
 963 /* ------------ Implementation ------------ */
 964
 965 /* One element of the AVL tree */
 966 typedef
 967    struct _AvlNode {
 968       Word key;
 969       Word val;
 970       struct _AvlNode* left;
 971       struct _AvlNode* right;
 972       Char balance;
 973    }
 974    AvlNode;
 975
 976 typedef
 977    struct {
 978       Word w;
 979       Bool b;
 980    }
 981    MaybeWord;
 982
 983 #define WFM_STKMAX    32    // At most 2**32 entries can be iterated over
 984
 985 struct _WordFM {
 986    AvlNode* root;
 987    void*    (*alloc_nofail)( SizeT );
 988    void     (*dealloc)(void*);
 989    Word     (*kCmp)(Word,Word);
 990    AvlNode* nodeStack[WFM_STKMAX]; // Iterator node stack
 991    Int      numStack[WFM_STKMAX];  // Iterator num stack
 992    Int      stackTop;              // Iterator stack pointer, one past end
 993 };
 994
 995 /* forward */
 996 static Bool avl_removeroot_wrk(AvlNode** t, Word(*kCmp)(Word,Word));
 997
 998 /* Swing to the left.  Warning: no balance maintainance. */
 999 static void avl_swl ( AvlNode** root )
1000 {
1001    AvlNode* a = *root;
1002    AvlNode* b = a->right;
1003    *root    = b;
1004    a->right = b->left;
1005    b->left  = a;
1006 }
1007
1008 /* Swing to the right.  Warning: no balance maintainance. */
1009 static void avl_swr ( AvlNode** root )
1010 {
1011    AvlNode* a = *root;
1012    AvlNode* b = a->left;
1013    *root    = b;
1014    a->left  = b->right;
1015    b->right = a;
1016 }
1017
1018 /* Balance maintainance after especially nasty swings. */
1019 static void avl_nasty ( AvlNode* root )
1020 {
1021    switch (root->balance) {
1022       case -1:
1023          root->left->balance  = 0;
1024          root->right->balance = 1;
1025          break;
1026       case 1:
1027          root->left->balance  = -1;
1028          root->right->balance = 0;
1029          break;
1030       case 0:
1031          root->left->balance  = 0;
1032          root->right->balance = 0;
1033          break;
1034       default:
1035          assert(0);
1036    }
1037    root->balance=0;
1038 }
1039
1040 /* Find size of a non-NULL tree. */
1041 static Word size_avl_nonNull ( AvlNode* nd )
1042 {
1043    return 1 + (nd->left  ? size_avl_nonNull(nd->left)  : 0)
1044             + (nd->right ? size_avl_nonNull(nd->right) : 0);
1045 }
1046
1047 /* Insert element a into the AVL tree t.  Returns True if the depth of
1048    the tree has grown.  If element with that key is already present,
1049    just copy a->val to existing node, first returning old ->val field
1050    of existing node in *oldV, so that the caller can finalize it
1051    however it wants.
1052 */
1053 static
1054 Bool avl_insert_wrk ( AvlNode**         rootp,
1055                       /*OUT*/MaybeWord* oldV,
1056                       AvlNode*          a,
1057                       Word              (*kCmp)(Word,Word) )
1058 {
1059    Word cmpres;
1060
1061    /* initialize */
1062    a->left    = 0;
1063    a->right   = 0;
1064    a->balance = 0;
1065    oldV->b    = False;
1066
1067    /* insert into an empty tree? */
1068    if (!(*rootp)) {
1069       (*rootp) = a;
1070       return True;
1071    }
1072
1073    cmpres = kCmp( (*rootp)->key, a->key );
1074
1075    if (cmpres > 0) {
1076       /* insert into the left subtree */
1077       if ((*rootp)->left) {
1078          AvlNode* left_subtree = (*rootp)->left;
1079          if (avl_insert_wrk(&left_subtree, oldV, a, kCmp)) {
1080             switch ((*rootp)->balance--) {
1081                case  1: return False;
1082                case  0: return True;
1083                case -1: break;
1084                default: assert(0);
1085             }
1086             if ((*rootp)->left->balance < 0) {
1087                avl_swr( rootp );
1088                (*rootp)->balance = 0;
1089                (*rootp)->right->balance = 0;
1090             } else {
1091                avl_swl( &((*rootp)->left) );
1092                avl_swr( rootp );
1093                avl_nasty( *rootp );
1094             }
1095          } else {
1096             (*rootp)->left = left_subtree;
1097          }
1098          return False;
1099       } else {
1100          (*rootp)->left = a;
1101          if ((*rootp)->balance--)
1102             return False;
1103          return True;
1104       }
1105       assert(0);/*NOTREACHED*/
1106    }
1107    else
1108    if (cmpres < 0) {
1109       /* insert into the right subtree */
1110       if ((*rootp)->right) {
1111          AvlNode* right_subtree = (*rootp)->right;
1112          if (avl_insert_wrk(&right_subtree, oldV, a, kCmp)) {
1113             switch((*rootp)->balance++){
1114                case -1: return False;
1115                case  0: return True;
1116                case  1: break;
1117                default: assert(0);
1118             }
1119             if ((*rootp)->right->balance > 0) {
1120                avl_swl( rootp );
1121                (*rootp)->balance = 0;
1122                (*rootp)->left->balance = 0;
1123             } else {
1124                avl_swr( &((*rootp)->right) );
1125                avl_swl( rootp );
1126                avl_nasty( *rootp );
1127             }
1128          } else {
1129             (*rootp)->right = right_subtree;
1130          }
1131          return False;
1132       } else {
1133          (*rootp)->right = a;
1134          if ((*rootp)->balance++)
1135             return False;
1136          return True;
1137       }
1138       assert(0);/*NOTREACHED*/
1139    }
1140    else {
1141       /* cmpres == 0, a duplicate - replace the val, but don't
1142          incorporate the node in the tree */
1143       oldV->b = True;
1144       oldV->w = (*rootp)->val;
1145       (*rootp)->val = a->val;
1146       return False;
1147    }
1148 }
1149
1150 /* Remove an element a from the AVL tree t.  a must be part of
1151    the tree.  Returns True if the depth of the tree has shrunk.
1152 */
1153 static
1154 Bool avl_remove_wrk ( AvlNode** rootp,
1155                       AvlNode*  a,
1156                       Word(*kCmp)(Word,Word) )
1157 {
1158    Bool ch;
1159    Word cmpres = kCmp( (*rootp)->key, a->key );
1160
1161    if (cmpres > 0){
1162       /* remove from the left subtree */
1163       AvlNode* left_subtree = (*rootp)->left;
1164       assert(left_subtree);
1165       ch = avl_remove_wrk(&left_subtree, a, kCmp);
1166       (*rootp)->left=left_subtree;
1167       if (ch) {
1168          switch ((*rootp)->balance++) {
1169             case -1: return True;
1170             case  0: return False;
1171             case  1: break;
1172             default: assert(0);
1173          }
1174          switch ((*rootp)->right->balance) {
1175             case 0:
1176                avl_swl( rootp );
1177                (*rootp)->balance = -1;
1178                (*rootp)->left->balance = 1;
1179                return False;
1180             case 1:
1181                avl_swl( rootp );
1182                (*rootp)->balance = 0;
1183                (*rootp)->left->balance = 0;
1184                return -1;
1185             case -1:
1186                break;
1187             default:
1188                assert(0);
1189          }
1190          avl_swr( &((*rootp)->right) );
1191          avl_swl( rootp );
1192          avl_nasty( *rootp );
1193          return True;
1194       }
1195    }
1196    else
1197    if (cmpres < 0) {
1198       /* remove from the right subtree */
1199       AvlNode* right_subtree = (*rootp)->right;
1200       assert(right_subtree);
1201       ch = avl_remove_wrk(&right_subtree, a, kCmp);
1202       (*rootp)->right = right_subtree;
1203       if (ch) {
1204          switch ((*rootp)->balance--) {
1205             case  1: return True;
1206             case  0: return False;
1207             case -1: break;
1208             default: assert(0);
1209          }
1210          switch ((*rootp)->left->balance) {
1211             case 0:
1212                avl_swr( rootp );
1213                (*rootp)->balance = 1;
1214                (*rootp)->right->balance = -1;
1215                return False;
1216             case -1:
1217                avl_swr( rootp );
1218                (*rootp)->balance = 0;
1219                (*rootp)->right->balance = 0;
1220                return True;
1221             case 1:
1222                break;
1223             default:
1224                assert(0);
1225          }
1226          avl_swl( &((*rootp)->left) );
1227          avl_swr( rootp );
1228          avl_nasty( *rootp );
1229          return True;
1230       }
1231    }
1232    else {
1233       assert(cmpres == 0);
1234       assert((*rootp)==a);
1235       return avl_removeroot_wrk(rootp, kCmp);
1236    }
1237    return 0;
1238 }
1239
1240 /* Remove the root of the AVL tree *rootp.
1241  * Warning: dumps core if *rootp is empty
1242  */
1243 static
1244 Bool avl_removeroot_wrk ( AvlNode** rootp,
1245                           Word(*kCmp)(Word,Word) )
1246 {
1247    Bool     ch;
1248    AvlNode* a;
1249    if (!(*rootp)->left) {
1250       if (!(*rootp)->right) {
1251          (*rootp) = 0;
1252          return True;
1253       }
1254       (*rootp) = (*rootp)->right;
1255       return True;
1256    }
1257    if (!(*rootp)->right) {
1258       (*rootp) = (*rootp)->left;
1259       return True;
1260    }
1261    if ((*rootp)->balance < 0) {
1262       /* remove from the left subtree */
1263       a = (*rootp)->left;
1264       while (a->right) a = a->right;
1265    } else {
1266       /* remove from the right subtree */
1267       a = (*rootp)->right;
1268       while (a->left) a = a->left;
1269    }
1270    ch = avl_remove_wrk(rootp, a, kCmp);
1271    a->left    = (*rootp)->left;
1272    a->right   = (*rootp)->right;
1273    a->balance = (*rootp)->balance;
1274    (*rootp)   = a;
1275    if(a->balance == 0) return ch;
1276    return False;
1277 }
1278
1279 static
1280 AvlNode* avl_find_node ( AvlNode* t, Word k, Word(*kCmp)(Word,Word) )
1281 {
1282    Word cmpres;
1283    while (True) {
1284       if (t == NULL) return NULL;
1285       cmpres = kCmp(t->key, k);
1286       if (cmpres > 0) t = t->left;  else
1287       if (cmpres < 0) t = t->right; else
1288       return t;
1289    }
1290 }
1291
1292 // Clear the iterator stack.
1293 static void stackClear(WordFM* fm)
1294 {
1295    Int i;
1296    assert(fm);
1297    for (i = 0; i < WFM_STKMAX; i++) {
1298       fm->nodeStack[i] = NULL;
1299       fm->numStack[i]  = 0;
1300    }
1301    fm->stackTop = 0;
1302 }
1303
1304 // Push onto the iterator stack.
1305 static inline void stackPush(WordFM* fm, AvlNode* n, Int i)
1306 {
1307    assert(fm->stackTop < WFM_STKMAX);
1308    assert(1 <= i && i <= 3);
1309    fm->nodeStack[fm->stackTop] = n;
1310    fm-> numStack[fm->stackTop] = i;
1311    fm->stackTop++;
1312 }
1313
1314 // Pop from the iterator stack.
1315 static inline Bool stackPop(WordFM* fm, AvlNode** n, Int* i)
1316 {
1317    assert(fm->stackTop <= WFM_STKMAX);
1318
1319    if (fm->stackTop > 0) {
1320       fm->stackTop--;
1321       *n = fm->nodeStack[fm->stackTop];
1322       *i = fm-> numStack[fm->stackTop];
1323       assert(1 <= *i && *i <= 3);
1324       fm->nodeStack[fm->stackTop] = NULL;
1325       fm-> numStack[fm->stackTop] = 0;
1326       return True;
1327    } else {
1328       return False;
1329    }
1330 }
1331
1332 static
1333 AvlNode* avl_dopy ( AvlNode* nd,
1334                     Word(*dopyK)(Word),
1335                     Word(*dopyV)(Word),
1336                     void*(alloc_nofail)(SizeT) )
1337 {
1338    AvlNode* nyu;
1339    if (! nd)
1340       return NULL;
1341    nyu = alloc_nofail(sizeof(AvlNode));
1342    assert(nyu);
1343
1344    nyu->left = nd->left;
1345    nyu->right = nd->right;
1346    nyu->balance = nd->balance;
1347
1348    /* Copy key */
1349    if (dopyK) {
1350       nyu->key = dopyK( nd->key );
1351       if (nd->key != 0 && nyu->key == 0)
1352          return NULL; /* oom in key dcopy */
1353    } else {
1354       /* copying assumedly unboxed keys */
1355       nyu->key = nd->key;
1356    }
1357
1358    /* Copy val */
1359    if (dopyV) {
1360       nyu->val = dopyV( nd->val );
1361       if (nd->val != 0 && nyu->val == 0)
1362          return NULL; /* oom in val dcopy */
1363    } else {
1364       /* copying assumedly unboxed vals */
1365       nyu->val = nd->val;
1366    }
1367
1368    /* Copy subtrees */
1369    if (nyu->left) {
1370       nyu->left = avl_dopy( nyu->left, dopyK, dopyV, alloc_nofail );
1371       if (! nyu->left)
1372          return NULL;
1373    }
1374    if (nyu->right) {
1375       nyu->right = avl_dopy( nyu->right, dopyK, dopyV, alloc_nofail );
1376       if (! nyu->right)
1377          return NULL;
1378    }
1379
1380    return nyu;
1381 }
1382
1383 /* --- Public interface functions --- */
1384
1385 /* Initialise a WordFM. */
1386 void initFM ( WordFM* fm,
1387               void*   (*alloc_nofail)( SizeT ),
1388               void    (*dealloc)(void*),
1389               Word    (*kCmp)(Word,Word) )
1390 {
1391    fm->root         = 0;
1392    fm->kCmp         = kCmp;
1393    fm->alloc_nofail = alloc_nofail;
1394    fm->dealloc      = dealloc;
1395    fm->stackTop     = 0;
1396 }
1397
1398 /* Allocate and Initialise a WordFM. */
1399 WordFM* newFM( void* (*alloc_nofail)( SizeT ),
1400                void  (*dealloc)(void*),
1401                Word  (*kCmp)(Word,Word) )
1402 {
1403    WordFM* fm = alloc_nofail(sizeof(WordFM));
1404    assert(fm);
1405    initFM(fm, alloc_nofail, dealloc, kCmp);
1406    return fm;
1407 }
1408
1409 static void avl_free ( AvlNode* nd,
1410                        void(*kFin)(Word),
1411                        void(*vFin)(Word),
1412                        void(*dealloc)(void*) )
1413 {
1414    if (!nd)
1415       return;
1416    if (nd->left)
1417       avl_free(nd->left, kFin, vFin, dealloc);
1418    if (nd->right)
1419       avl_free(nd->right, kFin, vFin, dealloc);
1420    if (kFin)
1421       kFin( nd->key );
1422    if (vFin)
1423       vFin( nd->val );
1424    memset(nd, 0, sizeof(AvlNode));
1425    dealloc(nd);
1426 }
1427
1428 /* Free up the FM.  If kFin is non-NULL, it is applied to keys
1429    before the FM is deleted; ditto with vFin for vals. */
1430 void deleteFM ( WordFM* fm, void(*kFin)(Word), void(*vFin)(Word) )
1431 {
1432    void(*dealloc)(void*) = fm->dealloc;
1433    avl_free( fm->root, kFin, vFin, dealloc );
1434    memset(fm, 0, sizeof(WordFM) );
1435    dealloc(fm);
1436 }
1437
1438 /* Add (k,v) to fm. */
1439 void addToFM ( WordFM* fm, Word k, Word v )
1440 {
1441    MaybeWord oldV;
1442    AvlNode* node;
1443    node = fm->alloc_nofail( sizeof(struct _AvlNode) );
1444    node->key = k;
1445    node->val = v;
1446    oldV.b = False;
1447    oldV.w = 0;
1448    avl_insert_wrk( &fm->root, &oldV, node, fm->kCmp );
1449    //if (oldV.b && fm->vFin)
1450    //   fm->vFin( oldV.w );
1451    if (oldV.b)
1452       free(node);
1453 }
1454
1455 // Delete key from fm, returning associated val if found
1456 Bool delFromFM ( WordFM* fm, /*OUT*/Word* oldV, Word key )
1457 {
1458    AvlNode* node = avl_find_node( fm->root, key, fm->kCmp );
1459    if (node) {
1460       avl_remove_wrk( &fm->root, node, fm->kCmp );
1461       if (oldV)
1462          *oldV = node->val;
1463       fm->dealloc(node);
1464       return True;
1465    } else {
1466       return False;
1467    }
1468 }
1469
1470 // Look up in fm, assigning found val at spec'd address
1471 Bool lookupFM ( WordFM* fm, /*OUT*/Word* valP, Word key )
1472 {
1473    AvlNode* node = avl_find_node( fm->root, key, fm->kCmp );
1474    if (node) {
1475       if (valP)
1476          *valP = node->val;
1477       return True;
1478    } else {
1479       return False;
1480    }
1481 }
1482
1483 Word sizeFM ( WordFM* fm )
1484 {
1485    // Hmm, this is a bad way to do this
1486    return fm->root ? size_avl_nonNull( fm->root ) : 0;
1487 }
1488
1489 // set up FM for iteration
1490 void initIterFM ( WordFM* fm )
1491 {
1492    assert(fm);
1493    stackClear(fm);
1494    if (fm->root)
1495       stackPush(fm, fm->root, 1);
1496 }
1497
1498 // get next key/val pair.  Will assert if fm has been modified
1499 // or looked up in since initIterFM was called.
1500 Bool nextIterFM ( WordFM* fm, /*OUT*/Word* pKey, /*OUT*/Word* pVal )
1501 {
1502    Int i = 0;
1503    AvlNode* n = NULL;
1504
1505    assert(fm);
1506
1507    // This in-order traversal requires each node to be pushed and popped
1508    // three times.  These could be avoided by updating nodes in-situ on the
1509    // top of the stack, but the push/pop cost is so small that it's worth
1510    // keeping this loop in this simpler form.
1511    while (stackPop(fm, &n, &i)) {
1512       switch (i) {
1513       case 1:
1514          stackPush(fm, n, 2);
1515          if (n->left)  stackPush(fm, n->left, 1);
1516          break;
1517       case 2:
1518          stackPush(fm, n, 3);
1519          if (pKey) *pKey = n->key;
1520          if (pVal) *pVal = n->val;
1521          return True;
1522       case 3:
1523          if (n->right) stackPush(fm, n->right, 1);
1524          break;
1525       default:
1526          assert(0);
1527       }
1528    }
1529
1530    // Stack empty, iterator is exhausted, return NULL
1531    return False;
1532 }
1533
1534 // clear the I'm iterating flag
1535 void doneIterFM ( WordFM* fm )
1536 {
1537 }
1538
1539 WordFM* dopyFM ( WordFM* fm, Word(*dopyK)(Word), Word(*dopyV)(Word) )
1540 {
1541    WordFM* nyu;
1542
1543    /* can't clone the fm whilst iterating on it */
1544    assert(fm->stackTop == 0);
1545
1546    nyu = fm->alloc_nofail( sizeof(WordFM) );
1547    assert(nyu);
1548
1549    *nyu = *fm;
1550
1551    fm->stackTop = 0;
1552    memset(fm->nodeStack, 0, sizeof(fm->nodeStack));
1553    memset(fm->numStack, 0,  sizeof(fm->numStack));
1554
1555    if (nyu->root) {
1556       nyu->root = avl_dopy( nyu->root, dopyK, dopyV, fm->alloc_nofail );
1557       if (! nyu->root)
1558          return NULL;
1559    }
1560
1561    return nyu;
1562 }
1563
1564 //------------------------------------------------------------------//
1565 //---                         end WordFM                         ---//
1566 //---                       Implementation                       ---//
1567 //------------------------------------------------------------------//
1568
1569 /*--------------------------------------------------------------------*/
1570 /*--- end                                               cg_merge.c ---*/
1571 /*--------------------------------------------------------------------*/