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