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-2015 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
43 typedef signed long Word;
44 typedef unsigned long UWord;
45 typedef unsigned char Bool;
46 #define True ((Bool)1)
47 #define False ((Bool)0)
48 typedef signed int Int;
49 typedef unsigned int UInt;
50 typedef unsigned long long int ULong;
51 typedef signed char Char;
52 typedef size_t SizeT;
53
54
55 //------------------------------------------------------------------//
56 //--- WordFM ---//
57 //--- Public interface ---//
58 //------------------------------------------------------------------//
59
60 typedef struct _WordFM WordFM; /* opaque */
61
62 /* Initialise a WordFM */
63 void initFM ( WordFM* t,
64 void* (*alloc_nofail)( SizeT ),
65 void (*dealloc)(void*),
66 Word (*kCmp)(Word,Word) );
67
68 /* Allocate and initialise a WordFM */
69 WordFM* newFM( void* (*alloc_nofail)( SizeT ),
70 void (*dealloc)(void*),
71 Word (*kCmp)(Word,Word) );
72
73 /* Free up the FM. If kFin is non-NULL, it is applied to keys
74 before the FM is deleted; ditto with vFin for vals. */
75 void deleteFM ( WordFM*, void(*kFin)(Word), void(*vFin)(Word) );
76
77 /* Add (k,v) to fm. If a binding for k already exists, it is updated
78 to map to this new v. In that case we should really return the
79 previous v so that caller can finalise it. Oh well. */
80 void addToFM ( WordFM* fm, Word k, Word v );
81
82 // Delete key from fm, returning associated val if found
83 Bool delFromFM ( WordFM* fm, /*OUT*/Word* oldV, Word key );
84
85 // Look up in fm, assigning found val at spec'd address
86 Bool lookupFM ( WordFM* fm, /*OUT*/Word* valP, Word key );
87
88 Word sizeFM ( WordFM* fm );
89
90 // set up FM for iteration
91 void initIterFM ( WordFM* fm );
92
93 // get next key/val pair. Will assert if fm has been modified
94 // or looked up in since initIterFM was called.
95 Bool nextIterFM ( WordFM* fm, /*OUT*/Word* pKey, /*OUT*/Word* pVal );
96
97 // clear the I'm iterating flag
98 void doneIterFM ( WordFM* fm );
99
100 // Deep copy a FM. If dopyK is NULL, keys are copied verbatim.
101 // If non-null, dopyK is applied to each key to generate the
102 // version in the new copy. In that case, if the argument to dopyK
103 // is non-NULL but the result is NULL, it is assumed that dopyK
104 // could not allocate memory, in which case the copy is abandoned
105 // and NULL is returned. Ditto with dopyV for values.
106 WordFM* dopyFM ( WordFM* fm, Word(*dopyK)(Word), Word(*dopyV)(Word) );
107
108 //------------------------------------------------------------------//
109 //--- end WordFM ---//
110 //--- Public interface ---//
111 //------------------------------------------------------------------//
112
113
114 static 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. */
118 typedef
119 struct {
120 FILE* fp;
121 UInt lno;
122 char* filename;
123 }
124 SOURCE;
125
printSrcLoc(SOURCE * s)126 static void printSrcLoc ( SOURCE* s )
127 {
128 fprintf(stderr, "%s: near %s line %u\n", argv0, s->filename, s->lno-1);
129 }
130
131 __attribute__((noreturn))
mallocFail(SOURCE * s,const char * who)132 static 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))
parseError(SOURCE * s,const char * msg)140 static 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))
barf(SOURCE * s,const char * msg)148 static 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.
readline(SOURCE * s)158 static 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
streqn(const char * s1,const char * s2,size_t n)194 static Bool streqn ( const char* s1, const char* s2, size_t n )
195 {
196 return 0 == strncmp(s1, s2, n);
197 }
198
streq(const char * s1,const char * s2)199 static Bool streq ( const char* s1, const char* s2 )
200 {
201 return 0 == strcmp(s1, s2 );
202 }
203
204
205 ////////////////////////////////////////////////////////////////
206
207 typedef
208 struct {
209 char* fi_name;
210 char* fn_name;
211 }
212 FileFn;
213
214 typedef
215 struct {
216 Int n_counts;
217 ULong* counts;
218 }
219 Counts;
220
221 typedef
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
new_FileFn(char * file_name,char * fn_name)247 static 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
ddel_FileFn(FileFn * ffn)257 static 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
dopy_FileFn(FileFn * ff)267 static 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
new_Counts(Int n_counts,ULong * counts)280 static 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
new_Counts_Zeroed(Int n_counts)301 static 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
sdel_Counts(Counts * cts)322 static void sdel_Counts ( Counts* cts )
323 {
324 memset(cts, 0, sizeof(Counts));
325 free(cts);
326 }
327
ddel_Counts(Counts * cts)328 static 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
dopy_Counts(Counts * cts)336 static Counts* dopy_Counts ( Counts* cts )
337 {
338 return new_Counts( cts->n_counts, cts->counts );
339 }
340
341 static
new_CacheProfFile(char ** desc_lines,char * cmd_line,char * events_line,Int n_events,char * summary_line,WordFM * outerMap,Counts * summary)342 CacheProfFile* 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
dopy_InnerMap(WordFM * innerMap)363 static WordFM* dopy_InnerMap ( WordFM* innerMap )
364 {
365 return dopyFM ( innerMap, NULL,
366 (Word(*)(Word))dopy_Counts );
367 }
368
ddel_InnerMap(WordFM * innerMap)369 static void ddel_InnerMap ( WordFM* innerMap )
370 {
371 deleteFM( innerMap, NULL, (void(*)(Word))ddel_Counts );
372 }
373
ddel_CacheProfFile(CacheProfFile * cpf)374 static 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
showCounts(FILE * f,Counts * c)398 static 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
show_CacheProfFile(FILE * f,CacheProfFile * cpf)406 static 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
cmp_FileFn(Word s1,Word s2)443 static 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
cmp_unboxed_UWord(Word s1,Word s2)453 static 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
parse_ULong(ULong * res,const char ** pptr)464 static 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.
488 static
splitUpCountsLine(SOURCE * s,UWord * lnno,const char * str)489 Counts* 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
addCounts(SOURCE * s,Counts * counts1,Counts * counts2)523 static 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
addCountsToMap(SOURCE * s,WordFM * counts_map,UWord lnno,Counts * newCounts)532 static 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
550 static
handle_counts(SOURCE * s,CacheProfFile * cpf,const char * fi,const char * fn,const char * newCountsStr)551 void 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 */
parse_CacheProfFile(SOURCE * s)612 static 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
merge_CacheProfInfo(SOURCE * s,CacheProfFile * dst,CacheProfFile * src)768 static 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
usage(void)850 static 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
main(int argc,char ** argv)859 int 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 */
977 typedef
978 struct _AvlNode {
979 Word key;
980 Word val;
981 struct _AvlNode* left;
982 struct _AvlNode* right;
983 Char balance;
984 }
985 AvlNode;
986
987 typedef
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
996 struct _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 */
1007 static Bool avl_removeroot_wrk(AvlNode** t, Word(*kCmp)(Word,Word));
1008
1009 /* Swing to the left. Warning: no balance maintainance. */
avl_swl(AvlNode ** root)1010 static 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. */
avl_swr(AvlNode ** root)1020 static 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. */
avl_nasty(AvlNode * root)1030 static 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. */
size_avl_nonNull(AvlNode * nd)1052 static 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 */
1064 static
avl_insert_wrk(AvlNode ** rootp,MaybeWord * oldV,AvlNode * a,Word (* kCmp)(Word,Word))1065 Bool 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 */
1164 static
avl_remove_wrk(AvlNode ** rootp,AvlNode * a,Word (* kCmp)(Word,Word))1165 Bool 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 */
1254 static
avl_removeroot_wrk(AvlNode ** rootp,Word (* kCmp)(Word,Word))1255 Bool 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
1290 static
avl_find_node(AvlNode * t,Word k,Word (* kCmp)(Word,Word))1291 AvlNode* 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.
stackClear(WordFM * fm)1304 static 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.
stackPush(WordFM * fm,AvlNode * n,Int i)1316 static 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.
stackPop(WordFM * fm,AvlNode ** n,Int * i)1326 static 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
1343 static
avl_dopy(AvlNode * nd,Word (* dopyK)(Word),Word (* dopyV)(Word),void * (alloc_nofail)(SizeT))1344 AvlNode* 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. */
initFM(WordFM * fm,void * (* alloc_nofail)(SizeT),void (* dealloc)(void *),Word (* kCmp)(Word,Word))1397 void 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. */
newFM(void * (* alloc_nofail)(SizeT),void (* dealloc)(void *),Word (* kCmp)(Word,Word))1410 WordFM* 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
avl_free(AvlNode * nd,void (* kFin)(Word),void (* vFin)(Word),void (* dealloc)(void *))1420 static 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. */
deleteFM(WordFM * fm,void (* kFin)(Word),void (* vFin)(Word))1441 void 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. */
addToFM(WordFM * fm,Word k,Word v)1450 void 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
delFromFM(WordFM * fm,Word * oldV,Word key)1467 Bool 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
lookupFM(WordFM * fm,Word * valP,Word key)1482 Bool 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
sizeFM(WordFM * fm)1494 Word 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
initIterFM(WordFM * fm)1501 void 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.
nextIterFM(WordFM * fm,Word * pKey,Word * pVal)1511 Bool 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
doneIterFM(WordFM * fm)1546 void doneIterFM ( WordFM* fm )
1547 {
1548 }
1549
dopyFM(WordFM * fm,Word (* dopyK)(Word),Word (* dopyV)(Word))1550 WordFM* 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