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