194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/*--------------------------------------------------------------------*/ 394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/*--- A program that merges multiple cachegrind output files. ---*/ 494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/*--- cg_merge.c ---*/ 594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/*--------------------------------------------------------------------*/ 694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* 894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj This file is part of Cachegrind, a Valgrind tool for cache 994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj profiling programs. 1094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 110f157ddb404bcde7815a1c5bf2d7e41c114f3d73sewardj Copyright (C) 2002-2013 Nicholas Nethercote 1294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj njn@valgrind.org 1394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 1494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AVL tree code derived from 1594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj ANSI C Library for maintainance of AVL Balanced Trees 1694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (C) 2000 Daniel Nagy, Budapest University of Technology and Economics 1794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Released under GNU General Public License (GPL) version 2 1894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 1994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj This program is free software; you can redistribute it and/or 2094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj modify it under the terms of the GNU General Public License as 2194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj published by the Free Software Foundation; either version 2 of the 2294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj License, or (at your option) any later version. 2394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 2494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj This program is distributed in the hope that it will be useful, but 2594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj WITHOUT ANY WARRANTY; without even the implied warranty of 2694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 2794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj General Public License for more details. 2894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 2994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj You should have received a copy of the GNU General Public License 3094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj along with this program; if not, write to the Free Software 3194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 3294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 02111-1307, USA. 3394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 3494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj The GNU General Public License is contained in the file COPYING. 3594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj*/ 3694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 3794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj#include <stdio.h> 3894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj#include <stdlib.h> 3994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj#include <assert.h> 4094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj#include <string.h> 4194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj#include <ctype.h> 4294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 4394dc508cafc3c1698c31152f9b0a014c0ae56109sewardjtypedef signed long Word; 4494dc508cafc3c1698c31152f9b0a014c0ae56109sewardjtypedef unsigned long UWord; 4594dc508cafc3c1698c31152f9b0a014c0ae56109sewardjtypedef unsigned char Bool; 4694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj#define True ((Bool)1) 4794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj#define False ((Bool)0) 4894dc508cafc3c1698c31152f9b0a014c0ae56109sewardjtypedef signed int Int; 4994dc508cafc3c1698c31152f9b0a014c0ae56109sewardjtypedef unsigned int UInt; 5094dc508cafc3c1698c31152f9b0a014c0ae56109sewardjtypedef unsigned long long int ULong; 5194dc508cafc3c1698c31152f9b0a014c0ae56109sewardjtypedef signed char Char; 5294dc508cafc3c1698c31152f9b0a014c0ae56109sewardjtypedef size_t SizeT; 5394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 5494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 5594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//------------------------------------------------------------------// 5694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//--- WordFM ---// 5794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//--- Public interface ---// 5894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//------------------------------------------------------------------// 5994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 6094dc508cafc3c1698c31152f9b0a014c0ae56109sewardjtypedef struct _WordFM WordFM; /* opaque */ 6194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 6294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Initialise a WordFM */ 6394dc508cafc3c1698c31152f9b0a014c0ae56109sewardjvoid initFM ( WordFM* t, 6494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj void* (*alloc_nofail)( SizeT ), 6594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj void (*dealloc)(void*), 6694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word (*kCmp)(Word,Word) ); 6794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 6894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Allocate and initialise a WordFM */ 6994dc508cafc3c1698c31152f9b0a014c0ae56109sewardjWordFM* newFM( void* (*alloc_nofail)( SizeT ), 7094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj void (*dealloc)(void*), 7194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word (*kCmp)(Word,Word) ); 7294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 7394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Free up the FM. If kFin is non-NULL, it is applied to keys 7494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj before the FM is deleted; ditto with vFin for vals. */ 7594dc508cafc3c1698c31152f9b0a014c0ae56109sewardjvoid deleteFM ( WordFM*, void(*kFin)(Word), void(*vFin)(Word) ); 7694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 7794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Add (k,v) to fm. If a binding for k already exists, it is updated 7894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj to map to this new v. In that case we should really return the 7994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj previous v so that caller can finalise it. Oh well. */ 8094dc508cafc3c1698c31152f9b0a014c0ae56109sewardjvoid addToFM ( WordFM* fm, Word k, Word v ); 8194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 8294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// Delete key from fm, returning associated val if found 8394dc508cafc3c1698c31152f9b0a014c0ae56109sewardjBool delFromFM ( WordFM* fm, /*OUT*/Word* oldV, Word key ); 8494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 8594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// Look up in fm, assigning found val at spec'd address 8694dc508cafc3c1698c31152f9b0a014c0ae56109sewardjBool lookupFM ( WordFM* fm, /*OUT*/Word* valP, Word key ); 8794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 8894dc508cafc3c1698c31152f9b0a014c0ae56109sewardjWord sizeFM ( WordFM* fm ); 8994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 9094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// set up FM for iteration 9194dc508cafc3c1698c31152f9b0a014c0ae56109sewardjvoid initIterFM ( WordFM* fm ); 9294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 9394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// get next key/val pair. Will assert if fm has been modified 9494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// or looked up in since initIterFM was called. 9594dc508cafc3c1698c31152f9b0a014c0ae56109sewardjBool nextIterFM ( WordFM* fm, /*OUT*/Word* pKey, /*OUT*/Word* pVal ); 9694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 9794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// clear the I'm iterating flag 9894dc508cafc3c1698c31152f9b0a014c0ae56109sewardjvoid doneIterFM ( WordFM* fm ); 9994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 10094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// Deep copy a FM. If dopyK is NULL, keys are copied verbatim. 10194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// If non-null, dopyK is applied to each key to generate the 10294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// version in the new copy. In that case, if the argument to dopyK 10394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// is non-NULL but the result is NULL, it is assumed that dopyK 10494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// could not allocate memory, in which case the copy is abandoned 10594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// and NULL is returned. Ditto with dopyV for values. 10694dc508cafc3c1698c31152f9b0a014c0ae56109sewardjWordFM* dopyFM ( WordFM* fm, Word(*dopyK)(Word), Word(*dopyV)(Word) ); 10794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 10894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//------------------------------------------------------------------// 10994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//--- end WordFM ---// 11094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//--- Public interface ---// 11194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//------------------------------------------------------------------// 11294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 11394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 1146bd9dc18c043927c1196caba20a327238a179c42florianstatic const char* argv0 = "cg_merge"; 11594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 11694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Keep track of source filename/line no so as to be able to 11794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj print decent error messages. */ 11894dc508cafc3c1698c31152f9b0a014c0ae56109sewardjtypedef 11994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj struct { 12094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj FILE* fp; 12194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj UInt lno; 12294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj char* filename; 12394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 12494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj SOURCE; 12594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 12694dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic void printSrcLoc ( SOURCE* s ) 12794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 12894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(stderr, "%s: near %s line %u\n", argv0, s->filename, s->lno-1); 12994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 13094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 13194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj__attribute__((noreturn)) 1326bd9dc18c043927c1196caba20a327238a179c42florianstatic void mallocFail ( SOURCE* s, const char* who ) 13394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 13494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(stderr, "%s: out of memory in %s\n", argv0, who ); 13594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj printSrcLoc( s ); 13694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj exit(2); 13794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 13894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 13994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj__attribute__((noreturn)) 1406bd9dc18c043927c1196caba20a327238a179c42florianstatic void parseError ( SOURCE* s, const char* msg ) 14194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 14294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(stderr, "%s: parse error: %s\n", argv0, msg ); 14394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj printSrcLoc( s ); 14494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj exit(1); 14594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 14694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 14794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj__attribute__((noreturn)) 1486bd9dc18c043927c1196caba20a327238a179c42florianstatic void barf ( SOURCE* s, const char* msg ) 14994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 15094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(stderr, "%s: %s\n", argv0, msg ); 15194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj printSrcLoc( s ); 15294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj exit(1); 15394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 15494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 1552e234a678c49cb0c93dfaff313fd7a9326f2ca71florian// Read a line. Return the line read, or NULL if at EOF. 1562e234a678c49cb0c93dfaff313fd7a9326f2ca71florian// The line is allocated dynamically but will be overwritten with 1572e234a678c49cb0c93dfaff313fd7a9326f2ca71florian// every invocation. Caller must not free it. 1582e234a678c49cb0c93dfaff313fd7a9326f2ca71florianstatic const char *readline ( SOURCE* s ) 15994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 1602e234a678c49cb0c93dfaff313fd7a9326f2ca71florian static char *line = NULL; 1612e234a678c49cb0c93dfaff313fd7a9326f2ca71florian static size_t linesiz = 0; 1622e234a678c49cb0c93dfaff313fd7a9326f2ca71florian 16394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj int ch, i = 0; 1642e234a678c49cb0c93dfaff313fd7a9326f2ca71florian 16594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj while (1) { 16694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj ch = getc(s->fp); 16794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (ch != EOF) { 1682e234a678c49cb0c93dfaff313fd7a9326f2ca71florian if (i + 1 >= linesiz) { 1692e234a678c49cb0c93dfaff313fd7a9326f2ca71florian linesiz += 500; 1702e234a678c49cb0c93dfaff313fd7a9326f2ca71florian line = realloc(line, linesiz * sizeof *line); 1712e234a678c49cb0c93dfaff313fd7a9326f2ca71florian if (line == NULL) 1722e234a678c49cb0c93dfaff313fd7a9326f2ca71florian mallocFail(s, "readline:"); 1732e234a678c49cb0c93dfaff313fd7a9326f2ca71florian } 17494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj line[i++] = ch; 17594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj line[i] = 0; 17694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (ch == '\n') { 17794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj line[i-1] = 0; 17894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj s->lno++; 17994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj break; 18094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 18194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 18294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (ferror(s->fp)) { 18394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj perror(argv0); 18494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj barf(s, "I/O error while reading input file"); 18594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 18694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // hit EOF 18794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj break; 18894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 18994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 19094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 1912e234a678c49cb0c93dfaff313fd7a9326f2ca71florian return i == 0 ? NULL : line; 19294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 19394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 1946bd9dc18c043927c1196caba20a327238a179c42florianstatic Bool streqn ( const char* s1, const char* s2, size_t n ) 19594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 19694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return 0 == strncmp(s1, s2, n); 19794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 19894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 1996bd9dc18c043927c1196caba20a327238a179c42florianstatic Bool streq ( const char* s1, const char* s2 ) 20094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 20194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return 0 == strcmp(s1, s2 ); 20294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 20394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 20494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 20594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//////////////////////////////////////////////////////////////// 20694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 20794dc508cafc3c1698c31152f9b0a014c0ae56109sewardjtypedef 20894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj struct { 20994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj char* fi_name; 21094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj char* fn_name; 21194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 21294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj FileFn; 21394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 21494dc508cafc3c1698c31152f9b0a014c0ae56109sewardjtypedef 21594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj struct { 21694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Int n_counts; 21794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj ULong* counts; 21894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 21994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Counts; 22094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 22194dc508cafc3c1698c31152f9b0a014c0ae56109sewardjtypedef 22294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj struct { 22394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // null-terminated vector of desc_lines 22494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj char** desc_lines; 22594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 22694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // Cmd line 22794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj char* cmd_line; 22894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 22994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // Events line 23094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj char* events_line; 23194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Int n_events; 23294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 23394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // Summary line (copied from input) 23494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj char* summary_line; 23594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 23694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* Outermost map is 23794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj WordFM FileFn* innerMap 23894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj where innerMap is WordFM line-number=UWord Counts */ 23994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj WordFM* outerMap; 24094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 24194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // Summary counts (computed whilst parsing) 24294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // should match .summary_line 24394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Counts* summary; 24494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 24594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj CacheProfFile; 24694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 24794dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic FileFn* new_FileFn ( char* file_name, char* fn_name ) 24894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 24994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj FileFn* ffn = malloc(sizeof(FileFn)); 25094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (ffn == NULL) 25194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return NULL; 25294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj ffn->fi_name = file_name; 25394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj ffn->fn_name = fn_name; 25494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return ffn; 25594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 25694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 25794dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic void ddel_FileFn ( FileFn* ffn ) 25894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 25994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (ffn->fi_name) 26094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj free(ffn->fi_name); 26194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (ffn->fn_name) 26294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj free(ffn->fn_name); 26394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj memset(ffn, 0, sizeof(FileFn)); 26494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj free(ffn); 26594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 26694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 26794dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic FileFn* dopy_FileFn ( FileFn* ff ) 26894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 269fdae2316e234e31b87c876376f60d927da7a7ccfflorian char *fi2, *fn2; 270fdae2316e234e31b87c876376f60d927da7a7ccfflorian fi2 = strdup(ff->fi_name); 271fdae2316e234e31b87c876376f60d927da7a7ccfflorian if (fi2 == NULL) return NULL; 272fdae2316e234e31b87c876376f60d927da7a7ccfflorian fn2 = strdup(ff->fn_name); 273fdae2316e234e31b87c876376f60d927da7a7ccfflorian if (fn2 == NULL) { 274fdae2316e234e31b87c876376f60d927da7a7ccfflorian free(fi2); 27594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return NULL; 276fdae2316e234e31b87c876376f60d927da7a7ccfflorian } 27794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return new_FileFn( fi2, fn2 ); 27894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 27994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 28094dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic Counts* new_Counts ( Int n_counts, /*COPIED*/ULong* counts ) 28194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 28294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Int i; 28394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Counts* cts = malloc(sizeof(Counts)); 28494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cts == NULL) 28594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return NULL; 28694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 28794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(n_counts >= 0); 28894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cts->counts = malloc(n_counts * sizeof(ULong)); 289370a8d5587d6c19310ccc8b8512d12bba936f4abflorian if (cts->counts == NULL) { 290370a8d5587d6c19310ccc8b8512d12bba936f4abflorian free(cts); 29194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return NULL; 292370a8d5587d6c19310ccc8b8512d12bba936f4abflorian } 29394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 29494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cts->n_counts = n_counts; 29594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj for (i = 0; i < n_counts; i++) 29694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cts->counts[i] = counts[i]; 29794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 29894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return cts; 29994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 30094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 30194dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic Counts* new_Counts_Zeroed ( Int n_counts ) 30294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 30394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Int i; 30494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Counts* cts = malloc(sizeof(Counts)); 30594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cts == NULL) 30694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return NULL; 30794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 30894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(n_counts >= 0); 30994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cts->counts = malloc(n_counts * sizeof(ULong)); 310370a8d5587d6c19310ccc8b8512d12bba936f4abflorian if (cts->counts == NULL) { 311370a8d5587d6c19310ccc8b8512d12bba936f4abflorian free(cts); 31294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return NULL; 313370a8d5587d6c19310ccc8b8512d12bba936f4abflorian } 31494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 31594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cts->n_counts = n_counts; 31694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj for (i = 0; i < n_counts; i++) 31794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cts->counts[i] = 0; 31894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 31994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return cts; 32094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 32194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 32294dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic void sdel_Counts ( Counts* cts ) 32394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 32494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj memset(cts, 0, sizeof(Counts)); 32594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj free(cts); 32694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 32794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 32894dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic void ddel_Counts ( Counts* cts ) 32994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 33094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cts->counts) 33194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj free(cts->counts); 33294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj memset(cts, 0, sizeof(Counts)); 33394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj free(cts); 33494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 33594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 33694dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic Counts* dopy_Counts ( Counts* cts ) 33794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 33894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return new_Counts( cts->n_counts, cts->counts ); 33994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 34094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 34194dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic 34294dc508cafc3c1698c31152f9b0a014c0ae56109sewardjCacheProfFile* new_CacheProfFile ( char** desc_lines, 34394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj char* cmd_line, 34494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj char* events_line, 34594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Int n_events, 34694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj char* summary_line, 34794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj WordFM* outerMap, 34894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Counts* summary ) 34994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 35094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj CacheProfFile* cpf = malloc(sizeof(CacheProfFile)); 35194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cpf == NULL) 35294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return NULL; 35394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->desc_lines = desc_lines; 35494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->cmd_line = cmd_line; 35594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->events_line = events_line; 35694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->n_events = n_events; 35794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->summary_line = summary_line; 35894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->outerMap = outerMap; 35994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->summary = summary; 36094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return cpf; 36194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 36294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 36394dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic WordFM* dopy_InnerMap ( WordFM* innerMap ) 36494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 36594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return dopyFM ( innerMap, NULL, 36694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (Word(*)(Word))dopy_Counts ); 36794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 36894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 36994dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic void ddel_InnerMap ( WordFM* innerMap ) 37094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 37194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj deleteFM( innerMap, NULL, (void(*)(Word))ddel_Counts ); 37294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 37394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 37494dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic void ddel_CacheProfFile ( CacheProfFile* cpf ) 37594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 37694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj char** p; 37794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cpf->desc_lines) { 37894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj for (p = cpf->desc_lines; *p; p++) 37994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj free(*p); 38094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj free(cpf->desc_lines); 38194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 38294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cpf->cmd_line) 38394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj free(cpf->cmd_line); 38494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cpf->events_line) 38594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj free(cpf->events_line); 38694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cpf->summary_line) 38794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj free(cpf->summary_line); 38894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cpf->outerMap) 38994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj deleteFM( cpf->outerMap, (void(*)(Word))ddel_FileFn, 39094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (void(*)(Word))ddel_InnerMap ); 39194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cpf->summary) 39294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj ddel_Counts(cpf->summary); 39394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 39494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj memset(cpf, 0, sizeof(CacheProfFile)); 39594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj free(cpf); 39694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 39794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 39894dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic void showCounts ( FILE* f, Counts* c ) 39994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 40094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Int i; 40194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj for (i = 0; i < c->n_counts; i++) { 40294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(f, "%lld ", c->counts[i]); 40394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 40494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 40594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 40694dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic void show_CacheProfFile ( FILE* f, CacheProfFile* cpf ) 40794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 40894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Int i; 40994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj char** d; 41094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj FileFn* topKey; 41194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj WordFM* topVal; 41294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj UWord subKey; 41394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Counts* subVal; 41494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 41594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj for (d = cpf->desc_lines; *d; d++) 41694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(f, "%s\n", *d); 41794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(f, "%s\n", cpf->cmd_line); 41894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(f, "%s\n", cpf->events_line); 41994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 42094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj initIterFM( cpf->outerMap ); 42194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj while (nextIterFM( cpf->outerMap, (Word*)(&topKey), (Word*)(&topVal) )) { 42294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(f, "fl=%s\nfn=%s\n", 42394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj topKey->fi_name, topKey->fn_name ); 42494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj initIterFM( topVal ); 42594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj while (nextIterFM( topVal, (Word*)(&subKey), (Word*)(&subVal) )) { 42694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(f, "%ld ", subKey ); 42794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj showCounts( f, subVal ); 42894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(f, "\n"); 42994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 43094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj doneIterFM( topVal ); 43194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 43294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj doneIterFM( cpf->outerMap ); 43394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 43494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj //fprintf(f, "%s\n", cpf->summary_line); 43594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(f, "summary:"); 43694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj for (i = 0; i < cpf->summary->n_counts; i++) 43794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(f, " %lld", cpf->summary->counts[i]); 43894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(f, "\n"); 43994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 44094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 44194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//////////////////////////////////////////////////////////////// 44294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 44394dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic Word cmp_FileFn ( Word s1, Word s2 ) 44494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 44594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj FileFn* ff1 = (FileFn*)s1; 44694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj FileFn* ff2 = (FileFn*)s2; 44794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word r = strcmp(ff1->fi_name, ff2->fi_name); 44894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (r == 0) 44994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj r = strcmp(ff1->fn_name, ff2->fn_name); 45094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return r; 45194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 45294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 45394dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic Word cmp_unboxed_UWord ( Word s1, Word s2 ) 45494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 45594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj UWord u1 = (UWord)s1; 45694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj UWord u2 = (UWord)s2; 45794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (u1 < u2) return -1; 45894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (u1 > u2) return 1; 45994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return 0; 46094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 46194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 46294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//////////////////////////////////////////////////////////////// 46394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 4642e234a678c49cb0c93dfaff313fd7a9326f2ca71florianstatic Bool parse_ULong ( /*OUT*/ULong* res, /*INOUT*/const char** pptr) 46594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 46694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj ULong u64; 4672e234a678c49cb0c93dfaff313fd7a9326f2ca71florian const char* ptr = *pptr; 46894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj while (isspace(*ptr)) ptr++; 46994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (!isdigit(*ptr)) { 47094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj *pptr = ptr; 47111edf632a845e67e7fcc3ff9f9e2647d732ad4e2florian return False; /* end of string, or junk */ 47294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 47394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj u64 = 0; 47494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj while (isdigit(*ptr)) { 47594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj u64 = (u64 * 10) + (ULong)(*ptr - '0'); 47694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj ptr++; 47794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 47894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj *res = u64; 47994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj *pptr = ptr; 48094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return True; 48194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 48294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 4832e234a678c49cb0c93dfaff313fd7a9326f2ca71florian// str is a line of integers, starting with a line number. Parse it, 48494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// returning the first number in *lnno and the rest in a newly 48594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// allocated Counts struct. If lnno is non-NULL, treat the first 48694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// number as a line number and assign it to *lnno instead of 48794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// incorporating it in the counts array. 48894dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic 4892e234a678c49cb0c93dfaff313fd7a9326f2ca71florianCounts* splitUpCountsLine ( SOURCE* s, /*OUT*/UWord* lnno, const char* str ) 49094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 49194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Bool ok; 49294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Counts* counts; 4932e234a678c49cb0c93dfaff313fd7a9326f2ca71florian ULong *tmpC = NULL; 4942e234a678c49cb0c93dfaff313fd7a9326f2ca71florian UInt n_tmpC = 0, tmpCsize = 0; 49594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj while (1) { 4962e234a678c49cb0c93dfaff313fd7a9326f2ca71florian if (n_tmpC >= tmpCsize) { 4972e234a678c49cb0c93dfaff313fd7a9326f2ca71florian tmpCsize += 50; 4982e234a678c49cb0c93dfaff313fd7a9326f2ca71florian tmpC = realloc(tmpC, tmpCsize * sizeof *tmpC); 4992e234a678c49cb0c93dfaff313fd7a9326f2ca71florian if (tmpC == NULL) 5002e234a678c49cb0c93dfaff313fd7a9326f2ca71florian mallocFail(s, "splitUpCountsLine:"); 5012e234a678c49cb0c93dfaff313fd7a9326f2ca71florian } 50294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj ok = parse_ULong( &tmpC[n_tmpC], &str ); 50394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (!ok) 50494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj break; 50594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj n_tmpC++; 50694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 50794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (*str != 0) 50894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj parseError(s, "garbage in counts line"); 50994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (lnno ? (n_tmpC < 2) : (n_tmpC < 1)) 51094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj parseError(s, "too few counts in count line"); 51194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 51294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (lnno) { 51394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj *lnno = (UWord)tmpC[0]; 51494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj counts = new_Counts( n_tmpC-1, /*COPIED*/&tmpC[1] ); 51594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 51694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj counts = new_Counts( n_tmpC, /*COPIED*/&tmpC[0] ); 51794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 5182e234a678c49cb0c93dfaff313fd7a9326f2ca71florian free(tmpC); 51994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 52094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return counts; 52194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 52294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 52394dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic void addCounts ( SOURCE* s, /*OUT*/Counts* counts1, Counts* counts2 ) 52494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 52594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Int i; 52694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (counts1->n_counts != counts2->n_counts) 52794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj parseError(s, "addCounts: inconsistent number of counts"); 52894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj for (i = 0; i < counts1->n_counts; i++) 52994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj counts1->counts[i] += counts2->counts[i]; 53094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 53194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 53294dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic Bool addCountsToMap ( SOURCE* s, 53394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj WordFM* counts_map, 53494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj UWord lnno, Counts* newCounts ) 53594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 53694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Counts* oldCounts; 53794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // look up lnno in the map. If none present, add a binding 53894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // lnno->counts. If present, add counts to the existing entry. 53994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (lookupFM( counts_map, (Word*)(&oldCounts), (Word)lnno )) { 54094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // merge with existing binding 54194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj addCounts( s, oldCounts, newCounts ); 54294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return True; 54394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 54494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // create new binding 54594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj addToFM( counts_map, (Word)lnno, (Word)newCounts ); 54694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return False; 54794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 54894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 54994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 55094dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic 55194dc508cafc3c1698c31152f9b0a014c0ae56109sewardjvoid handle_counts ( SOURCE* s, 55294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj CacheProfFile* cpf, 5532e234a678c49cb0c93dfaff313fd7a9326f2ca71florian const char* fi, const char* fn, const char* newCountsStr ) 55494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 55594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj WordFM* countsMap; 55694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Bool freeNewCounts; 55794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj UWord lnno; 55894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Counts* newCounts; 55994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj FileFn* topKey; 56094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 56194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (0) printf("%s %s %s\n", fi, fn, newCountsStr ); 56294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 56394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // parse the numbers 56494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj newCounts = splitUpCountsLine( s, &lnno, newCountsStr ); 56594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 56694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // Did we get the right number? 56794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (newCounts->n_counts != cpf->n_events) 56894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj goto oom; 56994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 57094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // allocate the key 57194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj topKey = malloc(sizeof(FileFn)); 57294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (topKey) { 57394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj topKey->fi_name = strdup(fi); 57494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj topKey->fn_name = strdup(fn); 57594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 57694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (! (topKey && topKey->fi_name && topKey->fn_name)) 57794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj mallocFail(s, "handle_counts:"); 57894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 57994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // search for it 58094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (lookupFM( cpf->outerMap, (Word*)(&countsMap), (Word)topKey )) { 58194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // found it. Merge in new counts 58294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj freeNewCounts = addCountsToMap( s, countsMap, lnno, newCounts ); 58394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj ddel_FileFn(topKey); 58494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 58594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // not found in the top map. Create new entry 58694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj countsMap = newFM( malloc, free, cmp_unboxed_UWord ); 58794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (!countsMap) 58894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj goto oom; 58994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj addToFM( cpf->outerMap, (Word)topKey, (Word)countsMap ); 59094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj freeNewCounts = addCountsToMap( s, countsMap, lnno, newCounts ); 59194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 59294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 59394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // also add to running summary total 59494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj addCounts( s, cpf->summary, newCounts ); 59594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 59694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // if safe to do so, free up the count vector 59794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (freeNewCounts) 59894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj ddel_Counts(newCounts); 59994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 60094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return; 60194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 60294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj oom: 60394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj parseError(s, "# counts doesn't match # events"); 60494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 60594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 60694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 60794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Parse a complete file from the stream in 's'. If a parse error 60894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj happens, do not return; instead exit via parseError(). If an 60994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj out-of-memory condition happens, do not return; instead exit via 61094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj mallocError(). 61194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj*/ 61294dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic CacheProfFile* parse_CacheProfFile ( SOURCE* s ) 61394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 61494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Int i; 6152e234a678c49cb0c93dfaff313fd7a9326f2ca71florian char** tmp_desclines = NULL; 6162e234a678c49cb0c93dfaff313fd7a9326f2ca71florian unsigned tmp_desclines_size = 0; 61794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj char* p; 61894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj int n_tmp_desclines = 0; 61994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj CacheProfFile* cpf; 62094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Counts* summaryRead; 6216bd9dc18c043927c1196caba20a327238a179c42florian char* curr_fn = strdup("???"); 6226bd9dc18c043927c1196caba20a327238a179c42florian char* curr_fl = strdup("???"); 6232e234a678c49cb0c93dfaff313fd7a9326f2ca71florian const char* line; 62494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 62594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf = new_CacheProfFile( NULL, NULL, NULL, 0, NULL, NULL, NULL ); 62694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cpf == NULL) 62794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj mallocFail(s, "parse_CacheProfFile(1)"); 62894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 62994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // Parse "desc:" lines 63094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj while (1) { 6312e234a678c49cb0c93dfaff313fd7a9326f2ca71florian line = readline(s); 6322e234a678c49cb0c93dfaff313fd7a9326f2ca71florian if (!line) 63394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj break; 63494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (!streqn(line, "desc: ", 6)) 63594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj break; 6362e234a678c49cb0c93dfaff313fd7a9326f2ca71florian if (n_tmp_desclines >= tmp_desclines_size) { 6372e234a678c49cb0c93dfaff313fd7a9326f2ca71florian tmp_desclines_size += 100; 6382e234a678c49cb0c93dfaff313fd7a9326f2ca71florian tmp_desclines = realloc(tmp_desclines, 6392e234a678c49cb0c93dfaff313fd7a9326f2ca71florian tmp_desclines_size * sizeof *tmp_desclines); 6402e234a678c49cb0c93dfaff313fd7a9326f2ca71florian if (tmp_desclines == NULL) 6412e234a678c49cb0c93dfaff313fd7a9326f2ca71florian mallocFail(s, "parse_CacheProfFile(1)"); 6422e234a678c49cb0c93dfaff313fd7a9326f2ca71florian } 64394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj tmp_desclines[n_tmp_desclines++] = strdup(line); 64494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 64594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 64694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (n_tmp_desclines == 0) 64794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj parseError(s, "parse_CacheProfFile: no DESC lines present"); 64894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 64994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->desc_lines = malloc( (1+n_tmp_desclines) * sizeof(char*) ); 65094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cpf->desc_lines == NULL) 65194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj mallocFail(s, "parse_CacheProfFile(2)"); 65294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 65394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->desc_lines[n_tmp_desclines] = NULL; 65494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj for (i = 0; i < n_tmp_desclines; i++) 65594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->desc_lines[i] = tmp_desclines[i]; 65694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 65794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // Parse "cmd:" line 65894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (!streqn(line, "cmd: ", 5)) 65994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj parseError(s, "parse_CacheProfFile: no CMD line present"); 66094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 66194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->cmd_line = strdup(line); 66294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cpf->cmd_line == NULL) 66394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj mallocFail(s, "parse_CacheProfFile(3)"); 66494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 66594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // Parse "events:" line and figure out how many events there are 6662e234a678c49cb0c93dfaff313fd7a9326f2ca71florian line = readline(s); 6672e234a678c49cb0c93dfaff313fd7a9326f2ca71florian if (!line) 66894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj parseError(s, "parse_CacheProfFile: eof before EVENTS line"); 66994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (!streqn(line, "events: ", 8)) 67094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj parseError(s, "parse_CacheProfFile: no EVENTS line present"); 67194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 67294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // figure out how many events there are by counting the number 67394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // of space-alphanum transitions in the events_line 67494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->events_line = strdup(line); 67594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cpf->events_line == NULL) 67694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj mallocFail(s, "parse_CacheProfFile(3)"); 67794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 67894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->n_events = 0; 67994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(cpf->events_line[6] == ':'); 68094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj for (p = &cpf->events_line[6]; *p; p++) { 68194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (p[0] == ' ' && isalpha(p[1])) 68294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->n_events++; 68394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 68494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 68594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // create the running cross-check summary 68694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->summary = new_Counts_Zeroed( cpf->n_events ); 68794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cpf->summary == NULL) 68894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj mallocFail(s, "parse_CacheProfFile(4)"); 68994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 69094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // create the outer map (file+fn name --> inner map) 69194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->outerMap = newFM ( malloc, free, cmp_FileFn ); 69294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cpf->outerMap == NULL) 69394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj mallocFail(s, "parse_CacheProfFile(5)"); 69494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 69594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // process count lines 69694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj while (1) { 6972e234a678c49cb0c93dfaff313fd7a9326f2ca71florian line = readline(s); 6982e234a678c49cb0c93dfaff313fd7a9326f2ca71florian if (!line) 69994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj parseError(s, "parse_CacheProfFile: eof before SUMMARY line"); 70094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 70194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (isdigit(line[0])) { 70294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj handle_counts(s, cpf, curr_fl, curr_fn, line); 70394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj continue; 70494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 70594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj else 70694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (streqn(line, "fn=", 3)) { 7076bd9dc18c043927c1196caba20a327238a179c42florian free(curr_fn); 70894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj curr_fn = strdup(line+3); 70994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj continue; 71094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 71194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj else 71294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (streqn(line, "fl=", 3)) { 7136bd9dc18c043927c1196caba20a327238a179c42florian free(curr_fl); 71494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj curr_fl = strdup(line+3); 71594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj continue; 71694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 71794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj else 71894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (streqn(line, "summary: ", 9)) { 71994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj break; 72094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 72194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj else 72294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj parseError(s, "parse_CacheProfFile: unexpected line in main data"); 72394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 72494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 72594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // finally, the "summary:" line 72694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (!streqn(line, "summary: ", 9)) 72794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj parseError(s, "parse_CacheProfFile: missing SUMMARY line"); 72894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 72994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf->summary_line = strdup(line); 73094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cpf->summary_line == NULL) 73194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj mallocFail(s, "parse_CacheProfFile(6)"); 73294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 73394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // there should be nothing more 7342e234a678c49cb0c93dfaff313fd7a9326f2ca71florian line = readline(s); 7352e234a678c49cb0c93dfaff313fd7a9326f2ca71florian if (line) 73694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj parseError(s, "parse_CacheProfFile: " 73794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj "extraneous content after SUMMARY line"); 73894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 73994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // check the summary counts are as expected 74094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj summaryRead = splitUpCountsLine( s, NULL, &cpf->summary_line[8] ); 74194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (summaryRead == NULL) 74294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj mallocFail(s, "parse_CacheProfFile(7)"); 74394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (summaryRead->n_counts != cpf->n_events) 74494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj parseError(s, "parse_CacheProfFile: wrong # counts in SUMMARY line"); 74594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj for (i = 0; i < summaryRead->n_counts; i++) { 74694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (summaryRead->counts[i] != cpf->summary->counts[i]) { 74794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj parseError(s, "parse_CacheProfFile: " 74894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj "computed vs stated SUMMARY counts mismatch"); 74994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 75094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 75194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj free(summaryRead->counts); 75294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj sdel_Counts(summaryRead); 75394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 75494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // since the summary counts are OK, free up the summary_line text 75594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // which contains the same info. 756f5d8e65f2c61c399420cde0afd70204e0c0f7c4cflorian free(cpf->summary_line); 757f5d8e65f2c61c399420cde0afd70204e0c0f7c4cflorian cpf->summary_line = NULL; 75894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 7592e234a678c49cb0c93dfaff313fd7a9326f2ca71florian free(tmp_desclines); 7606bd9dc18c043927c1196caba20a327238a179c42florian free(curr_fn); 7616bd9dc18c043927c1196caba20a327238a179c42florian free(curr_fl); 76294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 76394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // All looks OK 76494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return cpf; 76594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 76694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 76794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 76894dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic void merge_CacheProfInfo ( SOURCE* s, 76994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /*MOD*/CacheProfFile* dst, 77094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj CacheProfFile* src ) 77194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 77294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* For each (filefn, innerMap) in src 77394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if filefn not in dst 77494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj add binding dopy(filefn)->dopy(innerMap) in src 77594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj else 77694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // merge src->innerMap with dst->innerMap 77794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj for each (lineno, counts) in src->innerMap 77894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if lineno not in dst->innerMap 77994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj add binding lineno->dopy(counts) to dst->innerMap 78094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj else 78194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj add counts into dst->innerMap[lineno] 78294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj */ 78394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* Outer iterator: FileFn* -> WordFM* (inner iterator) 78494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Inner iterator: UWord -> Counts* 78594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj */ 78694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj FileFn* soKey; 78794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj WordFM* soVal; 78894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj WordFM* doVal; 78994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj UWord siKey; 79094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Counts* siVal; 79194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Counts* diVal; 79294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 79394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* First check mundane things: that the events: lines are 79494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj identical. */ 79594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (!streq( dst->events_line, src->events_line )) 79694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj barf(s, "\"events:\" line of most recent file does " 79794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj "not match those previously processed"); 79894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 79994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj initIterFM( src->outerMap ); 80094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 80194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // for (filefn, innerMap) in src 80294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj while (nextIterFM( src->outerMap, (Word*)&soKey, (Word*)&soVal )) { 80394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 80494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // is filefn in dst? 80594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (! lookupFM( dst->outerMap, (Word*)&doVal, (Word)soKey )) { 80694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 80794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // no .. add dopy(filefn) -> dopy(innerMap) to src 80894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj FileFn* c_soKey = dopy_FileFn(soKey); 80994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj WordFM* c_soVal = dopy_InnerMap(soVal); 81094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if ((!c_soKey) || (!c_soVal)) goto oom; 81194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj addToFM( dst->outerMap, (Word)c_soKey, (Word)c_soVal ); 81294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 81394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 81494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 81594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // yes .. merge the two innermaps 81694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj initIterFM( soVal ); 81794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 81894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // for (lno, counts) in soVal (source inner map) 81994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj while (nextIterFM( soVal, (Word*)&siKey, (Word*)&siVal )) { 82094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 82194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // is lno in the corresponding dst inner map? 82294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (! lookupFM( doVal, (Word*)&diVal, siKey )) { 82394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 82494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // no .. add lineno->dopy(counts) to dst inner map 82594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Counts* c_siVal = dopy_Counts( siVal ); 82694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (!c_siVal) goto oom; 82794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj addToFM( doVal, siKey, (Word)c_siVal ); 82894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 82994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 83094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 83194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // yes .. merge counts into dst inner map val 83294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj addCounts( s, diVal, siVal ); 83394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 83494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 83594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 83694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 83794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 83894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 83994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 84094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 84194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // add the summaries too 84294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj addCounts(s, dst->summary, src->summary ); 84394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 84494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return; 84594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 84694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj oom: 84794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj mallocFail(s, "merge_CacheProfInfo"); 84894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 84994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 85094dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic void usage ( void ) 85194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 85294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(stderr, "%s: Merges multiple cachegrind output files into one\n", 85394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj argv0); 85494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(stderr, "%s: usage: %s [-o outfile] [files-to-merge]\n", 85594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj argv0, argv0); 85694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj exit(1); 85794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 85894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 85994dc508cafc3c1698c31152f9b0a014c0ae56109sewardjint main ( int argc, char** argv ) 86094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 86194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Int i; 86294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj SOURCE src; 86394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj CacheProfFile *cpf, *cpfTmp; 86494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 86594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj FILE* outfile = NULL; 86694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj char* outfilename = NULL; 86794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Int outfileix = 0; 86894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 86994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (argv[0]) 87094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj argv0 = argv[0]; 87194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 87294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (argc < 2) 87394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj usage(); 87494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 87594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj for (i = 1; i < argc; i++) { 87694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (streq(argv[i], "-h") || streq(argv[i], "--help")) 87794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj usage(); 87894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 87994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 88094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* Scan args, looking for '-o outfilename'. */ 88194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj for (i = 1; i < argc; i++) { 88294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (streq(argv[i], "-o")) { 88394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (i+1 < argc) { 88494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj outfilename = argv[i+1]; 88594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj outfileix = i; 88694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj break; 88794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 88894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj usage(); 88994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 89094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 89194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 89294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 89394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf = NULL; 89494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 89594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj for (i = 1; i < argc; i++) { 89694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 89794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (i == outfileix) { 89894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* Skip '-o' and whatever follows it */ 89994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj i += 1; 90094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj continue; 90194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 90294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 90394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(stderr, "%s: parsing %s\n", argv0, argv[i]); 90494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj src.lno = 1; 90594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj src.filename = argv[i]; 90694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj src.fp = fopen(src.filename, "r"); 90794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (!src.fp) { 90894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj perror(argv0); 90994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj barf(&src, "Cannot open input file"); 91094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 91194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(src.fp); 91294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpfTmp = parse_CacheProfFile( &src ); 91394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fclose(src.fp); 91494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 91594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* If this isn't the first file, merge */ 91694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cpf == NULL) { 91794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* this is the first file */ 91894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cpf = cpfTmp; 91994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 92094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* not the first file; merge */ 92194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(stderr, "%s: merging %s\n", argv0, argv[i]); 92294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj merge_CacheProfInfo( &src, cpf, cpfTmp ); 92394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj ddel_CacheProfFile( cpfTmp ); 92494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 92594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 92694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 92794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 92894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* Now create the output file. */ 92994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 93094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cpf) { 93194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 93294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(stderr, "%s: writing %s\n", 93394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj argv0, outfilename ? outfilename : "(stdout)" ); 93494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 93594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* Write the output. */ 93694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (outfilename) { 93794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj outfile = fopen(outfilename, "w"); 93894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (!outfile) { 93994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(stderr, "%s: can't create output file %s\n", 94094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj argv0, outfilename); 94194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj perror(argv0); 94294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj exit(1); 94394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 94494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 94594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj outfile = stdout; 94694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 94794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 94894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj show_CacheProfFile( outfile, cpf ); 94994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (ferror(outfile)) { 95094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fprintf(stderr, "%s: error writing output file %s\n", 95199b6bde003681e0c442de9f82f854cf050ccbbd0florian argv0, outfilename ? outfilename : "(stdout)" ); 95294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj perror(argv0); 95394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (outfile != stdout) 95494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fclose(outfile); 95594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj exit(1); 95694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 95794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 95894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fflush(outfile); 95994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (outfile != stdout) 96094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fclose( outfile ); 96194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 96294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj ddel_CacheProfFile( cpf ); 96394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 96494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 96594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return 0; 96694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 96794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 96894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 96994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//------------------------------------------------------------------// 97094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//--- WordFM ---// 97194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//--- Implementation ---// 97294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//------------------------------------------------------------------// 97394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 97494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* ------------ Implementation ------------ */ 97594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 97694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* One element of the AVL tree */ 97794dc508cafc3c1698c31152f9b0a014c0ae56109sewardjtypedef 97894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj struct _AvlNode { 97994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word key; 98094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word val; 98194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj struct _AvlNode* left; 98294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj struct _AvlNode* right; 98394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Char balance; 98494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 98594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode; 98694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 98794dc508cafc3c1698c31152f9b0a014c0ae56109sewardjtypedef 98894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj struct { 98994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word w; 99094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Bool b; 99194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 99294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj MaybeWord; 99394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 99494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj#define WFM_STKMAX 32 // At most 2**32 entries can be iterated over 99594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 99694dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstruct _WordFM { 99794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* root; 99894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj void* (*alloc_nofail)( SizeT ); 99994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj void (*dealloc)(void*); 100094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word (*kCmp)(Word,Word); 100194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* nodeStack[WFM_STKMAX]; // Iterator node stack 100294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Int numStack[WFM_STKMAX]; // Iterator num stack 100394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Int stackTop; // Iterator stack pointer, one past end 100494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj}; 100594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 100694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* forward */ 100794dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic Bool avl_removeroot_wrk(AvlNode** t, Word(*kCmp)(Word,Word)); 100894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 100994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Swing to the left. Warning: no balance maintainance. */ 101094dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic void avl_swl ( AvlNode** root ) 101194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 101294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* a = *root; 101394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* b = a->right; 101494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj *root = b; 101594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj a->right = b->left; 101694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj b->left = a; 101794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 101894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 101994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Swing to the right. Warning: no balance maintainance. */ 102094dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic void avl_swr ( AvlNode** root ) 102194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 102294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* a = *root; 102394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* b = a->left; 102494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj *root = b; 102594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj a->left = b->right; 102694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj b->right = a; 102794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 102894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 102994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Balance maintainance after especially nasty swings. */ 103094dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic void avl_nasty ( AvlNode* root ) 103194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 103294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj switch (root->balance) { 103394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case -1: 103494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj root->left->balance = 0; 103594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj root->right->balance = 1; 103694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj break; 103794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 1: 103894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj root->left->balance = -1; 103994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj root->right->balance = 0; 104094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj break; 104194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 0: 104294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj root->left->balance = 0; 104394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj root->right->balance = 0; 104494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj break; 104594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj default: 104694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(0); 104794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 104894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj root->balance=0; 104994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 105094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 105194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Find size of a non-NULL tree. */ 105294dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic Word size_avl_nonNull ( AvlNode* nd ) 105394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 105494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return 1 + (nd->left ? size_avl_nonNull(nd->left) : 0) 105594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj + (nd->right ? size_avl_nonNull(nd->right) : 0); 105694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 105794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 105894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Insert element a into the AVL tree t. Returns True if the depth of 105994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj the tree has grown. If element with that key is already present, 106094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj just copy a->val to existing node, first returning old ->val field 106194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj of existing node in *oldV, so that the caller can finalize it 106294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj however it wants. 106394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj*/ 106494dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic 106594dc508cafc3c1698c31152f9b0a014c0ae56109sewardjBool avl_insert_wrk ( AvlNode** rootp, 106694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /*OUT*/MaybeWord* oldV, 106794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* a, 106894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word (*kCmp)(Word,Word) ) 106994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 107094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word cmpres; 107194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 107294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* initialize */ 107394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj a->left = 0; 107494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj a->right = 0; 107594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj a->balance = 0; 107694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj oldV->b = False; 107794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 107894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* insert into an empty tree? */ 107994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (!(*rootp)) { 108094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp) = a; 108194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return True; 108294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 108394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 108494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cmpres = kCmp( (*rootp)->key, a->key ); 108594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 108694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cmpres > 0) { 108794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* insert into the left subtree */ 108894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if ((*rootp)->left) { 108994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* left_subtree = (*rootp)->left; 109094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (avl_insert_wrk(&left_subtree, oldV, a, kCmp)) { 109194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj switch ((*rootp)->balance--) { 109294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 1: return False; 109394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 0: return True; 109494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case -1: break; 109594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj default: assert(0); 109694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 109794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if ((*rootp)->left->balance < 0) { 109894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_swr( rootp ); 109994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->balance = 0; 110094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->right->balance = 0; 110194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 110294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_swl( &((*rootp)->left) ); 110394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_swr( rootp ); 110494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_nasty( *rootp ); 110594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 110694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 110794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->left = left_subtree; 110894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 110994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return False; 111094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 111194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->left = a; 111294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if ((*rootp)->balance--) 111394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return False; 111494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return True; 111594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 111694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(0);/*NOTREACHED*/ 111794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 111894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj else 111994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cmpres < 0) { 112094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* insert into the right subtree */ 112194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if ((*rootp)->right) { 112294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* right_subtree = (*rootp)->right; 112394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (avl_insert_wrk(&right_subtree, oldV, a, kCmp)) { 112494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj switch((*rootp)->balance++){ 112594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case -1: return False; 112694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 0: return True; 112794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 1: break; 112894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj default: assert(0); 112994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 113094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if ((*rootp)->right->balance > 0) { 113194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_swl( rootp ); 113294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->balance = 0; 113394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->left->balance = 0; 113494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 113594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_swr( &((*rootp)->right) ); 113694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_swl( rootp ); 113794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_nasty( *rootp ); 113894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 113994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 114094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->right = right_subtree; 114194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 114294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return False; 114394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 114494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->right = a; 114594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if ((*rootp)->balance++) 114694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return False; 114794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return True; 114894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 114994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(0);/*NOTREACHED*/ 115094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 115194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj else { 115294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* cmpres == 0, a duplicate - replace the val, but don't 115394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj incorporate the node in the tree */ 115494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj oldV->b = True; 115594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj oldV->w = (*rootp)->val; 115694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->val = a->val; 115794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return False; 115894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 115994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 116094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 116194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Remove an element a from the AVL tree t. a must be part of 116294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj the tree. Returns True if the depth of the tree has shrunk. 116394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj*/ 116494dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic 116594dc508cafc3c1698c31152f9b0a014c0ae56109sewardjBool avl_remove_wrk ( AvlNode** rootp, 116694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* a, 116794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word(*kCmp)(Word,Word) ) 116894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 116994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Bool ch; 117094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word cmpres = kCmp( (*rootp)->key, a->key ); 117194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 117294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cmpres > 0){ 117394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* remove from the left subtree */ 117494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* left_subtree = (*rootp)->left; 117594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(left_subtree); 117694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj ch = avl_remove_wrk(&left_subtree, a, kCmp); 117794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->left=left_subtree; 117894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (ch) { 117994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj switch ((*rootp)->balance++) { 118094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case -1: return True; 118194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 0: return False; 118294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 1: break; 118394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj default: assert(0); 118494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 118594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj switch ((*rootp)->right->balance) { 118694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 0: 118794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_swl( rootp ); 118894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->balance = -1; 118994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->left->balance = 1; 119094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return False; 119194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 1: 119294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_swl( rootp ); 119394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->balance = 0; 119494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->left->balance = 0; 119594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return -1; 119694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case -1: 119794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj break; 119894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj default: 119994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(0); 120094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 120194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_swr( &((*rootp)->right) ); 120294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_swl( rootp ); 120394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_nasty( *rootp ); 120494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return True; 120594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 120694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 120794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj else 120894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cmpres < 0) { 120994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* remove from the right subtree */ 121094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* right_subtree = (*rootp)->right; 121194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(right_subtree); 121294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj ch = avl_remove_wrk(&right_subtree, a, kCmp); 121394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->right = right_subtree; 121494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (ch) { 121594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj switch ((*rootp)->balance--) { 121694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 1: return True; 121794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 0: return False; 121894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case -1: break; 121994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj default: assert(0); 122094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 122194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj switch ((*rootp)->left->balance) { 122294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 0: 122394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_swr( rootp ); 122494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->balance = 1; 122594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->right->balance = -1; 122694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return False; 122794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case -1: 122894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_swr( rootp ); 122994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->balance = 0; 123094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp)->right->balance = 0; 123194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return True; 123294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 1: 123394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj break; 123494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj default: 123594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(0); 123694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 123794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_swl( &((*rootp)->left) ); 123894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_swr( rootp ); 123994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_nasty( *rootp ); 124094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return True; 124194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 124294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 124394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj else { 124494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(cmpres == 0); 124594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert((*rootp)==a); 124694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return avl_removeroot_wrk(rootp, kCmp); 124794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 124894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return 0; 124994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 125094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 125194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Remove the root of the AVL tree *rootp. 125294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj * Warning: dumps core if *rootp is empty 125394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj */ 125494dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic 125594dc508cafc3c1698c31152f9b0a014c0ae56109sewardjBool avl_removeroot_wrk ( AvlNode** rootp, 125694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word(*kCmp)(Word,Word) ) 125794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 125894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Bool ch; 125994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* a; 126094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (!(*rootp)->left) { 126194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (!(*rootp)->right) { 126294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp) = 0; 126394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return True; 126494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 126594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp) = (*rootp)->right; 126694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return True; 126794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 126894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (!(*rootp)->right) { 126994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp) = (*rootp)->left; 127094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return True; 127194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 127294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if ((*rootp)->balance < 0) { 127394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* remove from the left subtree */ 127494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj a = (*rootp)->left; 127594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj while (a->right) a = a->right; 127694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 127794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* remove from the right subtree */ 127894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj a = (*rootp)->right; 127994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj while (a->left) a = a->left; 128094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 128194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj ch = avl_remove_wrk(rootp, a, kCmp); 128294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj a->left = (*rootp)->left; 128394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj a->right = (*rootp)->right; 128494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj a->balance = (*rootp)->balance; 128594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj (*rootp) = a; 128694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if(a->balance == 0) return ch; 128794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return False; 128894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 128994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 129094dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic 129194dc508cafc3c1698c31152f9b0a014c0ae56109sewardjAvlNode* avl_find_node ( AvlNode* t, Word k, Word(*kCmp)(Word,Word) ) 129294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 129394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word cmpres; 129494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj while (True) { 129594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (t == NULL) return NULL; 129694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj cmpres = kCmp(t->key, k); 129794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cmpres > 0) t = t->left; else 129894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (cmpres < 0) t = t->right; else 129994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return t; 130094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 130194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 130294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 130394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// Clear the iterator stack. 130494dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic void stackClear(WordFM* fm) 130594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 130694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Int i; 130794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(fm); 130894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj for (i = 0; i < WFM_STKMAX; i++) { 130994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fm->nodeStack[i] = NULL; 131094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fm->numStack[i] = 0; 131194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 131294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fm->stackTop = 0; 131394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 131494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 131594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// Push onto the iterator stack. 131694dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic inline void stackPush(WordFM* fm, AvlNode* n, Int i) 131794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 131894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(fm->stackTop < WFM_STKMAX); 131994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(1 <= i && i <= 3); 132094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fm->nodeStack[fm->stackTop] = n; 132194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fm-> numStack[fm->stackTop] = i; 132294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fm->stackTop++; 132394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 132494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 132594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// Pop from the iterator stack. 132694dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic inline Bool stackPop(WordFM* fm, AvlNode** n, Int* i) 132794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 132894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(fm->stackTop <= WFM_STKMAX); 132994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 133094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (fm->stackTop > 0) { 133194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fm->stackTop--; 133294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj *n = fm->nodeStack[fm->stackTop]; 133394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj *i = fm-> numStack[fm->stackTop]; 133494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(1 <= *i && *i <= 3); 133594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fm->nodeStack[fm->stackTop] = NULL; 133694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fm-> numStack[fm->stackTop] = 0; 133794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return True; 133894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 133994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return False; 134094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 134194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 134294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 134394dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic 134494dc508cafc3c1698c31152f9b0a014c0ae56109sewardjAvlNode* avl_dopy ( AvlNode* nd, 134594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word(*dopyK)(Word), 134694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word(*dopyV)(Word), 134794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj void*(alloc_nofail)(SizeT) ) 134894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 134994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* nyu; 135094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (! nd) 135194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return NULL; 135294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj nyu = alloc_nofail(sizeof(AvlNode)); 135394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(nyu); 135494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 135594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj nyu->left = nd->left; 135694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj nyu->right = nd->right; 135794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj nyu->balance = nd->balance; 135894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 135994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* Copy key */ 136094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (dopyK) { 136194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj nyu->key = dopyK( nd->key ); 136294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (nd->key != 0 && nyu->key == 0) 136394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return NULL; /* oom in key dcopy */ 136494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 136594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* copying assumedly unboxed keys */ 136694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj nyu->key = nd->key; 136794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 136894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 136994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* Copy val */ 137094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (dopyV) { 137194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj nyu->val = dopyV( nd->val ); 137294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (nd->val != 0 && nyu->val == 0) 137394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return NULL; /* oom in val dcopy */ 137494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 137594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* copying assumedly unboxed vals */ 137694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj nyu->val = nd->val; 137794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 137894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 137994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* Copy subtrees */ 138094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (nyu->left) { 138194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj nyu->left = avl_dopy( nyu->left, dopyK, dopyV, alloc_nofail ); 138294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (! nyu->left) 138394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return NULL; 138494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 138594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (nyu->right) { 138694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj nyu->right = avl_dopy( nyu->right, dopyK, dopyV, alloc_nofail ); 138794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (! nyu->right) 138894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return NULL; 138994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 139094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 139194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return nyu; 139294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 139394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 139494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* --- Public interface functions --- */ 139594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 139694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Initialise a WordFM. */ 139794dc508cafc3c1698c31152f9b0a014c0ae56109sewardjvoid initFM ( WordFM* fm, 139894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj void* (*alloc_nofail)( SizeT ), 139994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj void (*dealloc)(void*), 140094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word (*kCmp)(Word,Word) ) 140194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 140294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fm->root = 0; 140394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fm->kCmp = kCmp; 140494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fm->alloc_nofail = alloc_nofail; 140594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fm->dealloc = dealloc; 140694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fm->stackTop = 0; 140794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 140894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 140994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Allocate and Initialise a WordFM. */ 141094dc508cafc3c1698c31152f9b0a014c0ae56109sewardjWordFM* newFM( void* (*alloc_nofail)( SizeT ), 141194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj void (*dealloc)(void*), 141294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Word (*kCmp)(Word,Word) ) 141394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 141494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj WordFM* fm = alloc_nofail(sizeof(WordFM)); 141594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(fm); 141694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj initFM(fm, alloc_nofail, dealloc, kCmp); 141794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return fm; 141894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 141994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 142094dc508cafc3c1698c31152f9b0a014c0ae56109sewardjstatic void avl_free ( AvlNode* nd, 142194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj void(*kFin)(Word), 142294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj void(*vFin)(Word), 142394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj void(*dealloc)(void*) ) 142494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 142594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (!nd) 142694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return; 142794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (nd->left) 142894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_free(nd->left, kFin, vFin, dealloc); 142994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (nd->right) 143094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_free(nd->right, kFin, vFin, dealloc); 143194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (kFin) 143294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj kFin( nd->key ); 143394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (vFin) 143494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj vFin( nd->val ); 143594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj memset(nd, 0, sizeof(AvlNode)); 143694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj dealloc(nd); 143794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 143894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 143994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Free up the FM. If kFin is non-NULL, it is applied to keys 144094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj before the FM is deleted; ditto with vFin for vals. */ 144194dc508cafc3c1698c31152f9b0a014c0ae56109sewardjvoid deleteFM ( WordFM* fm, void(*kFin)(Word), void(*vFin)(Word) ) 144294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 144394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj void(*dealloc)(void*) = fm->dealloc; 144494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_free( fm->root, kFin, vFin, dealloc ); 144594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj memset(fm, 0, sizeof(WordFM) ); 144694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj dealloc(fm); 144794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 144894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 144994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/* Add (k,v) to fm. */ 145094dc508cafc3c1698c31152f9b0a014c0ae56109sewardjvoid addToFM ( WordFM* fm, Word k, Word v ) 145194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 145294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj MaybeWord oldV; 145394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* node; 145494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj node = fm->alloc_nofail( sizeof(struct _AvlNode) ); 145594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj node->key = k; 145694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj node->val = v; 145794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj oldV.b = False; 145894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj oldV.w = 0; 145994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_insert_wrk( &fm->root, &oldV, node, fm->kCmp ); 146094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj //if (oldV.b && fm->vFin) 146194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // fm->vFin( oldV.w ); 146294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (oldV.b) 146394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj free(node); 146494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 146594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 146694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// Delete key from fm, returning associated val if found 146794dc508cafc3c1698c31152f9b0a014c0ae56109sewardjBool delFromFM ( WordFM* fm, /*OUT*/Word* oldV, Word key ) 146894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 146994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* node = avl_find_node( fm->root, key, fm->kCmp ); 147094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (node) { 147194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj avl_remove_wrk( &fm->root, node, fm->kCmp ); 147294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (oldV) 147394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj *oldV = node->val; 147494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fm->dealloc(node); 147594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return True; 147694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 147794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return False; 147894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 147994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 148094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 148194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// Look up in fm, assigning found val at spec'd address 148294dc508cafc3c1698c31152f9b0a014c0ae56109sewardjBool lookupFM ( WordFM* fm, /*OUT*/Word* valP, Word key ) 148394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 148494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* node = avl_find_node( fm->root, key, fm->kCmp ); 148594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (node) { 148694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (valP) 148794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj *valP = node->val; 148894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return True; 148994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } else { 149094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return False; 149194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 149294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 149394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 149494dc508cafc3c1698c31152f9b0a014c0ae56109sewardjWord sizeFM ( WordFM* fm ) 149594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 149694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // Hmm, this is a bad way to do this 149794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return fm->root ? size_avl_nonNull( fm->root ) : 0; 149894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 149994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 150094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// set up FM for iteration 150194dc508cafc3c1698c31152f9b0a014c0ae56109sewardjvoid initIterFM ( WordFM* fm ) 150294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 150394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(fm); 150494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj stackClear(fm); 150594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (fm->root) 150694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj stackPush(fm, fm->root, 1); 150794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 150894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 150994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// get next key/val pair. Will assert if fm has been modified 151094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// or looked up in since initIterFM was called. 151194dc508cafc3c1698c31152f9b0a014c0ae56109sewardjBool nextIterFM ( WordFM* fm, /*OUT*/Word* pKey, /*OUT*/Word* pVal ) 151294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 151394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj Int i = 0; 151494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj AvlNode* n = NULL; 151594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 151694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(fm); 151794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 151894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // This in-order traversal requires each node to be pushed and popped 151994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // three times. These could be avoided by updating nodes in-situ on the 152094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // top of the stack, but the push/pop cost is so small that it's worth 152194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // keeping this loop in this simpler form. 152294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj while (stackPop(fm, &n, &i)) { 152394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj switch (i) { 152494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 1: 152594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj stackPush(fm, n, 2); 152694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (n->left) stackPush(fm, n->left, 1); 152794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj break; 152894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 2: 152994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj stackPush(fm, n, 3); 153094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (pKey) *pKey = n->key; 153194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (pVal) *pVal = n->val; 153294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return True; 153394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj case 3: 153494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (n->right) stackPush(fm, n->right, 1); 153594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj break; 153694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj default: 153794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(0); 153894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 153994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 154094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 154194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj // Stack empty, iterator is exhausted, return NULL 154294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return False; 154394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 154494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 154594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj// clear the I'm iterating flag 154694dc508cafc3c1698c31152f9b0a014c0ae56109sewardjvoid doneIterFM ( WordFM* fm ) 154794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 154894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 154994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 155094dc508cafc3c1698c31152f9b0a014c0ae56109sewardjWordFM* dopyFM ( WordFM* fm, Word(*dopyK)(Word), Word(*dopyV)(Word) ) 155194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj{ 155294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj WordFM* nyu; 155394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 155494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj /* can't clone the fm whilst iterating on it */ 155594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(fm->stackTop == 0); 155694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 155794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj nyu = fm->alloc_nofail( sizeof(WordFM) ); 155894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj assert(nyu); 155994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 156094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj *nyu = *fm; 156194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 156294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj fm->stackTop = 0; 156394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj memset(fm->nodeStack, 0, sizeof(fm->nodeStack)); 156494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj memset(fm->numStack, 0, sizeof(fm->numStack)); 156594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 156694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (nyu->root) { 156794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj nyu->root = avl_dopy( nyu->root, dopyK, dopyV, fm->alloc_nofail ); 156894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj if (! nyu->root) 156994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return NULL; 157094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj } 157194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 157294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj return nyu; 157394dc508cafc3c1698c31152f9b0a014c0ae56109sewardj} 157494dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 157594dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//------------------------------------------------------------------// 157694dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//--- end WordFM ---// 157794dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//--- Implementation ---// 157894dc508cafc3c1698c31152f9b0a014c0ae56109sewardj//------------------------------------------------------------------// 157994dc508cafc3c1698c31152f9b0a014c0ae56109sewardj 158094dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/*--------------------------------------------------------------------*/ 158194dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/*--- end cg_merge.c ---*/ 158294dc508cafc3c1698c31152f9b0a014c0ae56109sewardj/*--------------------------------------------------------------------*/ 1583