00001 /************************************************************************ 00002 ************************************************************************ 00003 FAUST compiler 00004 Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale 00005 --------------------------------------------------------------------- 00006 This program is free software; you can redistribute it and/or modify 00007 it under the terms of the GNU General Public License as published by 00008 the Free Software Foundation; either version 2 of the License, or 00009 (at your option) any later version. 00010 00011 This program is distributed in the hope that it will be useful, 00012 but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 GNU General Public License for more details. 00015 00016 You should have received a copy of the GNU General Public License 00017 along with this program; if not, write to the Free Software 00018 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00019 ************************************************************************ 00020 ************************************************************************/ 00021 00022 00023 00024 #ifndef __SHLYSIS__ 00025 #define __SHLYSIS__ 00026 /***************************************************************************** 00027 ****************************************************************************** 00028 Tree Sharing Analysis 00029 Y. Orlarey, (c) Grame 2002 00030 ------------------------------------------------------------------------------ 00031 The sharing analysis of tree t is the annotation of all its subtrees t' 00032 with their number of occurences in t. As this annotation of t' depends of 00033 a context (the tree t for which t' is a subtree) a specific property key 00034 unique to each sharing analysis must be generated. 00035 00036 API: 00037 ---- 00038 00039 shprkey(t) -> k = unique sharing property key of t 00040 shcount(k,t') -> n = returns the number of occurences of t' in t (where k = shprkey(t)) 00041 shlysis(t) -> k = annotated the subtrees of t with prop (key sharing-count) 00042 (0 if t' is not a subtree of t) 00043 00044 History : 00045 --------- 00046 2002-04-08 : First version 00047 00048 ****************************************************************************** 00049 *****************************************************************************/ 00050 00051 #include <string.h> 00052 #include <stdlib.h> 00053 #include <stdio.h> 00054 00055 #include "list.hh" 00056 00057 00058 typedef bool (*barrier)(const Tree& t); 00059 00060 //------------------------------------------------------------------------------ 00061 // shprkey : Create a specific property key for the sharing count of subtrees of t 00062 00063 Tree shprkey(Tree t); 00064 00065 00066 //------------------------------------------------------------------------------ 00067 // shcount : returns the sharing count of t within the tree T of key k 00068 00069 int shcount(Tree key, Tree t); 00070 00071 #if 0 00072 00073 //------------------------------------------------------------------------------ 00074 // shlysis : create a specific property key for the sharing count of subtrees of t 00075 00076 Tree shlysis(Tree t); 00077 00078 Tree shlysis(Tree t, barrier foo); 00079 #endif 00080 #endif