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