00001 /* 00002 Copyright (C) 2000-2003, Institute of Computing Technology, Chinese Academy of Sciences 00003 All rights reserved. 00004 00005 Redistribution and use in source and binary forms, with or without modification, 00006 are permitted provided that the following conditions are met: 00007 00008 Redistributions of source code must retain the above copyright notice, this list 00009 of conditions and the following disclaimer. 00010 00011 Redistributions in binary form must reproduce the above copyright notice, this list 00012 of conditions and the following disclaimer in the documentation and/or other materials 00013 provided with the distribution. 00014 00015 Neither the name of the owner nor the names of its contributors may be used to endorse or 00016 promote products derived from this software without specific prior written permission. 00017 00018 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR 00019 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 00020 FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR 00021 ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 00022 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 00023 BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00024 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 00025 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00026 */ 00027 00028 //-*-c++-*- 00029 00030 #ifndef scc_finder_INCLUDED 00031 #define scc_finder_INCLUDED 00032 00033 #include "region.h" 00034 00035 class SCC_FINDER_MEM { 00036 00037 protected: 00038 MEM_POOL _m; 00039 00040 SCC_FINDER_MEM() { 00041 MEM_POOL_Initialize( &_m, "SCC_FINDER_MEM", true ); 00042 MEM_POOL_Push( &_m ); 00043 } 00044 00045 ~SCC_FINDER_MEM() { 00046 MEM_POOL_Pop( &_m ); 00047 MEM_POOL_Delete(&_m ); 00048 } 00049 }; 00050 00051 //============================================================================ 00052 // 00053 // Class Name: SCC_FINDER 00054 // 00055 // Base Class: SCC_FINDER_MEM 00056 // 00057 // Derived Class: <none> 00058 // 00059 // Class Description: Find out all Stronly connected components in a cfg. 00060 // 00061 // Note: 00062 // 00063 //============================================================================ 00064 class SCC_FINDER : public SCC_FINDER_MEM { 00065 typedef mempool_allocator<NODE_VECTOR> NODE_VECTOR_ALLOC; 00066 typedef std::vector<NODE_VECTOR,NODE_VECTOR_ALLOC> SCC_VECTOR; 00067 00068 private: 00069 NODE_VECTOR _in_stack; 00070 NODE_VECTOR _scc; 00071 NODE_STACK _stack; 00072 SCC_VECTOR _scc_set; 00073 REGIONAL_CFG *_cfg; 00074 00075 void Strong_Components(REGIONAL_CFG_NODE *node,INT_VECTOR& dfn, 00076 INT_VECTOR& low_link,BS *bs,INT32& next_dfn); 00077 00078 public: 00079 SCC_FINDER() : 00080 _in_stack(NODE_ALLOC(&(_m))), 00081 _scc(NODE_ALLOC(&(_m))), 00082 _scc_set(NODE_VECTOR_ALLOC(&(_m))), 00083 _stack(NODE_VECTOR(NODE_ALLOC(&(_m)))) { 00084 00085 } 00086 00087 ~SCC_FINDER() {} 00088 00089 void Find_Scc(REGIONAL_CFG *cfg); 00090 SCC_VECTOR Scc_Set() { return _scc_set; } 00091 00092 void Print(FILE *f = stderr); 00093 }; 00094 00095 #endif 00096
1.5.6