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