cg_merge.c revision 2d3c75979dd0bbf2606bf1a8e11b72ae6220e5db 
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@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 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, 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, 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, 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 ( char* s1, char* s2, size_t n )
190{
191   return 0 == strncmp(s1, s2, n);
192}
193
194static Bool streq ( char* s1, 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 = 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
271static 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
290static 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
309static void sdel_Counts ( Counts* cts )
310{
311   memset(cts, 0, sizeof(Counts));
312   free(cts);
313}
314
315static 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
323static Counts* dopy_Counts ( Counts* cts )
324{
325   return new_Counts( cts->n_counts, cts->counts );
326}
327
328static
329CacheProfFile* 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
350static WordFM* dopy_InnerMap ( WordFM* innerMap )
351{
352   return dopyFM ( innerMap, NULL,
353                             (Word(*)(Word))dopy_Counts );
354}
355
356static void ddel_InnerMap ( WordFM* innerMap )
357{
358   deleteFM( innerMap, NULL, (void(*)(Word))ddel_Counts );
359}
360
361static 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
385static 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
393static 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
430static 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
440static 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
451static 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.
475static
476Counts* 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
507static 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
516static 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
534static
535void 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*/
596static 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
757static 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
839static 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
848int 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 */
966typedef
967   struct _AvlNode {
968      Word key;
969      Word val;
970      struct _AvlNode* left;
971      struct _AvlNode* right;
972      Char balance;
973   }
974   AvlNode;
975
976typedef
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
985struct _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 */
996static Bool avl_removeroot_wrk(AvlNode** t, Word(*kCmp)(Word,Word));
997
998/* Swing to the left.  Warning: no balance maintainance. */
999static 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. */
1009static 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. */
1019static 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. */
1041static 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*/
1053static
1054Bool 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*/
1153static
1154Bool 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 */
1243static
1244Bool 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
1279static
1280AvlNode* 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.
1293static 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.
1305static 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.
1315static 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
1332static
1333AvlNode* 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. */
1386void 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. */
1399WordFM* 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
1409static 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. */
1430void 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. */
1439void 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
1456Bool 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
1471Bool 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
1483Word 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
1490void 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.
1500Bool 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
1535void doneIterFM ( WordFM* fm )
1536{
1537}
1538
1539WordFM* 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