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
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
156 #define M_LINEBUF 40960
157 static char line[M_LINEBUF];
158
159 // True if anything read, False if at EOF
readline(SOURCE * s)160 static 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
streqn(const char * s1,const char * s2,size_t n)189 static Bool streqn ( const char* s1, const char* s2, size_t n )
190 {
191 return 0 == strncmp(s1, s2, n);
192 }
193
streq(const char * s1,const char * s2)194 static Bool streq ( const char* s1, const char* s2 )
195 {
196 return 0 == strcmp(s1, s2 );
197 }
198
199
200 ////////////////////////////////////////////////////////////////
201
202 typedef
203 struct {
204 char* fi_name;
205 char* fn_name;
206 }
207 FileFn;
208
209 typedef
210 struct {
211 Int n_counts;
212 ULong* counts;
213 }
214 Counts;
215
216 typedef
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
new_FileFn(char * file_name,char * fn_name)242 static 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
ddel_FileFn(FileFn * ffn)252 static 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
dopy_FileFn(FileFn * ff)262 static 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
new_Counts(Int n_counts,ULong * counts)271 static 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
new_Counts_Zeroed(Int n_counts)292 static 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
sdel_Counts(Counts * cts)313 static void sdel_Counts ( Counts* cts )
314 {
315 memset(cts, 0, sizeof(Counts));
316 free(cts);
317 }
318
ddel_Counts(Counts * cts)319 static 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
dopy_Counts(Counts * cts)327 static Counts* dopy_Counts ( Counts* cts )
328 {
329 return new_Counts( cts->n_counts, cts->counts );
330 }
331
332 static
new_CacheProfFile(char ** desc_lines,char * cmd_line,char * events_line,Int n_events,char * summary_line,WordFM * outerMap,Counts * summary)333 CacheProfFile* 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
dopy_InnerMap(WordFM * innerMap)354 static WordFM* dopy_InnerMap ( WordFM* innerMap )
355 {
356 return dopyFM ( innerMap, NULL,
357 (Word(*)(Word))dopy_Counts );
358 }
359
ddel_InnerMap(WordFM * innerMap)360 static void ddel_InnerMap ( WordFM* innerMap )
361 {
362 deleteFM( innerMap, NULL, (void(*)(Word))ddel_Counts );
363 }
364
ddel_CacheProfFile(CacheProfFile * cpf)365 static 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
showCounts(FILE * f,Counts * c)389 static 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
show_CacheProfFile(FILE * f,CacheProfFile * cpf)397 static 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
cmp_FileFn(Word s1,Word s2)434 static 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
cmp_unboxed_UWord(Word s1,Word s2)444 static 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
parse_ULong(ULong * res,char ** pptr)455 static 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.
479 static
splitUpCountsLine(SOURCE * s,UWord * lnno,char * str)480 Counts* 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
addCounts(SOURCE * s,Counts * counts1,Counts * counts2)511 static 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
addCountsToMap(SOURCE * s,WordFM * counts_map,UWord lnno,Counts * newCounts)520 static 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
538 static
handle_counts(SOURCE * s,CacheProfFile * cpf,const char * fi,const char * fn,char * newCountsStr)539 void 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 */
parse_CacheProfFile(SOURCE * s)600 static 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
merge_CacheProfInfo(SOURCE * s,CacheProfFile * dst,CacheProfFile * src)755 static 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
usage(void)837 static 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
main(int argc,char ** argv)846 int 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 */
964 typedef
965 struct _AvlNode {
966 Word key;
967 Word val;
968 struct _AvlNode* left;
969 struct _AvlNode* right;
970 Char balance;
971 }
972 AvlNode;
973
974 typedef
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
983 struct _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 */
994 static Bool avl_removeroot_wrk(AvlNode** t, Word(*kCmp)(Word,Word));
995
996 /* Swing to the left. Warning: no balance maintainance. */
avl_swl(AvlNode ** root)997 static 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. */
avl_swr(AvlNode ** root)1007 static 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. */
avl_nasty(AvlNode * root)1017 static 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. */
size_avl_nonNull(AvlNode * nd)1039 static 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 */
1051 static
avl_insert_wrk(AvlNode ** rootp,MaybeWord * oldV,AvlNode * a,Word (* kCmp)(Word,Word))1052 Bool 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 */
1151 static
avl_remove_wrk(AvlNode ** rootp,AvlNode * a,Word (* kCmp)(Word,Word))1152 Bool 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 */
1241 static
avl_removeroot_wrk(AvlNode ** rootp,Word (* kCmp)(Word,Word))1242 Bool 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
1277 static
avl_find_node(AvlNode * t,Word k,Word (* kCmp)(Word,Word))1278 AvlNode* 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.
stackClear(WordFM * fm)1291 static 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.
stackPush(WordFM * fm,AvlNode * n,Int i)1303 static 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.
stackPop(WordFM * fm,AvlNode ** n,Int * i)1313 static 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
1330 static
avl_dopy(AvlNode * nd,Word (* dopyK)(Word),Word (* dopyV)(Word),void * (alloc_nofail)(SizeT))1331 AvlNode* 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. */
initFM(WordFM * fm,void * (* alloc_nofail)(SizeT),void (* dealloc)(void *),Word (* kCmp)(Word,Word))1384 void 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. */
newFM(void * (* alloc_nofail)(SizeT),void (* dealloc)(void *),Word (* kCmp)(Word,Word))1397 WordFM* 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
avl_free(AvlNode * nd,void (* kFin)(Word),void (* vFin)(Word),void (* dealloc)(void *))1407 static 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. */
deleteFM(WordFM * fm,void (* kFin)(Word),void (* vFin)(Word))1428 void 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. */
addToFM(WordFM * fm,Word k,Word v)1437 void 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
delFromFM(WordFM * fm,Word * oldV,Word key)1454 Bool 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
lookupFM(WordFM * fm,Word * valP,Word key)1469 Bool 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
sizeFM(WordFM * fm)1481 Word 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
initIterFM(WordFM * fm)1488 void 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.
nextIterFM(WordFM * fm,Word * pKey,Word * pVal)1498 Bool 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
doneIterFM(WordFM * fm)1533 void doneIterFM ( WordFM* fm )
1534 {
1535 }
1536
dopyFM(WordFM * fm,Word (* dopyK)(Word),Word (* dopyV)(Word))1537 WordFM* 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