interpretor/faust-0.9.47mr3/compiler/tlib/shlysis.hh

   1 /************************************************************************
   2  ************************************************************************
   3     FAUST compiler
   4         Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale
   5     ---------------------------------------------------------------------
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19  ************************************************************************
  20  ************************************************************************/
  21
  22
  23
  24 #ifndef __SHLYSIS__
  25 #define __SHLYSIS__
  26 /*****************************************************************************
  27 ******************************************************************************
  28                                                                 Tree Sharing Analysis
  29                                                 Y. Orlarey, (c) Grame 2002
  30 ------------------------------------------------------------------------------
  31 The sharing analysis of tree t is the annotation of all its subtrees t'
  32 with their number of occurences in t. As this annotation of t' depends of
  33 a context (the tree t for which t' is a subtree) a specific property key
  34 unique to each sharing analysis must be generated.
  35
  36  API:
  37  ----
  38
  39         shprkey(t) -> k         = unique sharing property key of t
  40         shcount(k,t') -> n      = returns the number of occurences of t' in t (where k = shprkey(t))
  41         shlysis(t)      -> k    = annotated the subtrees of t with prop (key sharing-count)
  42                                                   (0 if t' is not a subtree of t)
  43
  44  History :
  45  ---------
  46         2002-04-08 : First version
  47
  48 ******************************************************************************
  49 *****************************************************************************/
  50
  51 #include    <string.h>
  52 #include    <stdlib.h>
  53 #include    <stdio.h>
  54
  55 #include        "list.hh"
  56
  57
  58 typedef bool (*barrier)(const Tree& t);
  59
  60 //------------------------------------------------------------------------------
  61 // shprkey : Create a specific property key for the sharing count of subtrees of t
  62
  63 Tree shprkey(Tree t);
  64
  65
  66 //------------------------------------------------------------------------------
  67 // shcount : returns the sharing count of t within the tree T of key k
  68
  69 int shcount(Tree key, Tree t);
  70
  71 #if 0
  72
  73 //------------------------------------------------------------------------------
  74 // shlysis : create a specific property key for the sharing count of subtrees of t
  75
  76 Tree shlysis(Tree t);
  77
  78 Tree shlysis(Tree t, barrier foo);
  79 #endif
  80 #endif