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-2012 Nicholas Nethercote 12 njn (at) 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 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)) 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)) 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)) 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 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 189 static Bool streqn ( char* s1, char* s2, size_t n ) 190 { 191 return 0 == strncmp(s1, s2, n); 192 } 193 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 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 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 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 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 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 309 static void sdel_Counts ( Counts* cts ) 310 { 311 memset(cts, 0, sizeof(Counts)); 312 free(cts); 313 } 314 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 323 static Counts* dopy_Counts ( Counts* cts ) 324 { 325 return new_Counts( cts->n_counts, cts->counts ); 326 } 327 328 static 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 350 static WordFM* dopy_InnerMap ( WordFM* innerMap ) 351 { 352 return dopyFM ( innerMap, NULL, 353 (Word(*)(Word))dopy_Counts ); 354 } 355 356 static void ddel_InnerMap ( WordFM* innerMap ) 357 { 358 deleteFM( innerMap, NULL, (void(*)(Word))ddel_Counts ); 359 } 360 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 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 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 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 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 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 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 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 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 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 */ 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 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 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 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. */ 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. */ 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. */ 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. */ 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 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 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 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 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. 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. 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. 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 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. */ 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. */ 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 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. */ 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. */ 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 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 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 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 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. 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 1535 void doneIterFM ( WordFM* fm ) 1536 { 1537 } 1538 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
