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