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