00001 /***************************************************************************** 00002 00003 The following code is derived, directly or indirectly, from the SystemC 00004 source code Copyright (c) 1996-2006 by all Contributors. 00005 All Rights reserved. 00006 00007 The contents of this file are subject to the restrictions and limitations 00008 set forth in the SystemC Open Source License Version 2.4 (the "License"); 00009 You may not use this file except in compliance with such restrictions and 00010 limitations. You may obtain instructions on how to receive a copy of the 00011 License at http://www.systemc.org/. Software distributed by Contributors 00012 under the License is distributed on an "AS IS" basis, WITHOUT WARRANTY OF 00013 ANY KIND, either express or implied. See the License for the specific 00014 language governing rights and limitations under the License. 00015 00016 *****************************************************************************/ 00017 00018 /***************************************************************************** 00019 00020 sc_pq.cpp - Simple heap implementation of priority queue. 00021 00022 Original Author: Stan Y. Liao, Synopsys, Inc. 00023 00024 *****************************************************************************/ 00025 00026 /***************************************************************************** 00027 00028 MODIFICATION LOG - modifiers, enter your name, affiliation, date and 00029 changes you are making here. 00030 00031 Name, Affiliation, Date: 00032 Description of Modification: 00033 00034 *****************************************************************************/ 00035 00036 00037 // $Log: sc_pq.cpp,v $ 00038 // Revision 1.1.1.1 2006/12/15 20:31:39 acg 00039 // SystemC 2.2 00040 // 00041 // Revision 1.3 2006/01/13 18:53:11 acg 00042 // Andy Goodrich: Added $Log command so that CVS comments are reproduced in 00043 // the source. 00044 // 00045 00046 #include "sysc/utils/sc_pq.h" 00047 00048 namespace sc_core { 00049 00050 sc_ppq_base::sc_ppq_base( int sz, int (*cmp)( const void*, const void* ) ) 00051 : m_size_alloc( sz ), m_heap_size( 0 ), m_compar( cmp ) 00052 { 00053 // m_size_alloc must be at least 2, otherwise resizing doesn't work 00054 if( m_size_alloc < 2 ) { 00055 m_size_alloc = 2; 00056 } 00057 // allocate 00058 m_heap = new void*[m_size_alloc + 1]; 00059 // initialize 00060 for( int i = 0; i < m_size_alloc; ++ i ) { 00061 m_heap[i] = 0; 00062 } 00063 } 00064 00065 sc_ppq_base::~sc_ppq_base() 00066 { 00067 delete[] m_heap; 00068 } 00069 00070 void* 00071 sc_ppq_base::extract_top() 00072 { 00073 assert( m_heap_size > 0 ); 00074 void* topelem = m_heap[1]; 00075 m_heap[1] = m_heap[m_heap_size]; 00076 m_heap_size --; 00077 heapify( 1 ); 00078 return topelem; 00079 } 00080 00081 void 00082 sc_ppq_base::insert( void* elem ) 00083 { 00084 m_heap_size ++; 00085 int i = m_heap_size; 00086 00087 // resize the heap in case there's not enough memory 00088 if( m_heap_size > m_size_alloc ) { 00089 m_size_alloc += m_size_alloc / 2; 00090 void** new_heap = new void*[m_size_alloc + 1]; 00091 for( int j = 1; j < m_heap_size; ++ j ) { 00092 new_heap[j] = m_heap[j]; 00093 } 00094 delete[] m_heap; 00095 m_heap = new_heap; 00096 } 00097 00098 while( (i > 1) && (m_compar( m_heap[parent( i )], elem ) < 0) ) { 00099 m_heap[i] = m_heap[parent( i )]; 00100 i = parent( i ); 00101 } 00102 m_heap[i] = elem; 00103 } 00104 00105 void 00106 sc_ppq_base::heapify( int i ) 00107 { 00108 int l; 00109 while( l = left( i ), l <= m_heap_size ) { 00110 int largest = (m_compar( m_heap[l], m_heap[i] ) > 0) ? l : i; 00111 00112 int r = right( i ); 00113 if( (r <= m_heap_size) && 00114 (m_compar( m_heap[r], m_heap[largest] ) > 0) ) { 00115 largest = r; 00116 } 00117 00118 if( largest != i ) { 00119 void* tmp = m_heap[i]; 00120 m_heap[i] = m_heap[largest]; 00121 m_heap[largest] = tmp; 00122 i = largest; 00123 } else { 00124 break; 00125 } 00126 } 00127 } 00128 00129 } // namespace sc_core
1.5.6