Home | History | Annotate | Download | only in cachegrind
      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-2012 Nicholas Nethercote
     12      njn (at) 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 ? outfilename : "(stdout)" );
    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 /*--------------------------------------------------------------------*/
   1572