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