sc_pq.cpp revision 12027
112027Sjungma@eit.uni-kl.de/***************************************************************************** 212027Sjungma@eit.uni-kl.de 312027Sjungma@eit.uni-kl.de Licensed to Accellera Systems Initiative Inc. (Accellera) under one or 412027Sjungma@eit.uni-kl.de more contributor license agreements. See the NOTICE file distributed 512027Sjungma@eit.uni-kl.de with this work for additional information regarding copyright ownership. 612027Sjungma@eit.uni-kl.de Accellera licenses this file to you under the Apache License, Version 2.0 712027Sjungma@eit.uni-kl.de (the "License"); you may not use this file except in compliance with the 812027Sjungma@eit.uni-kl.de License. You may obtain a copy of the License at 912027Sjungma@eit.uni-kl.de 1012027Sjungma@eit.uni-kl.de http://www.apache.org/licenses/LICENSE-2.0 1112027Sjungma@eit.uni-kl.de 1212027Sjungma@eit.uni-kl.de Unless required by applicable law or agreed to in writing, software 1312027Sjungma@eit.uni-kl.de distributed under the License is distributed on an "AS IS" BASIS, 1412027Sjungma@eit.uni-kl.de WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or 1512027Sjungma@eit.uni-kl.de implied. See the License for the specific language governing 1612027Sjungma@eit.uni-kl.de permissions and limitations under the License. 1712027Sjungma@eit.uni-kl.de 1812027Sjungma@eit.uni-kl.de *****************************************************************************/ 1912027Sjungma@eit.uni-kl.de 2012027Sjungma@eit.uni-kl.de/***************************************************************************** 2112027Sjungma@eit.uni-kl.de 2212027Sjungma@eit.uni-kl.de sc_pq.cpp - Simple heap implementation of priority queue. 2312027Sjungma@eit.uni-kl.de 2412027Sjungma@eit.uni-kl.de Original Author: Stan Y. Liao, Synopsys, Inc. 2512027Sjungma@eit.uni-kl.de 2612027Sjungma@eit.uni-kl.de CHANGE LOG AT END OF FILE 2712027Sjungma@eit.uni-kl.de *****************************************************************************/ 2812027Sjungma@eit.uni-kl.de 2912027Sjungma@eit.uni-kl.de// $Log: sc_pq.cpp,v $ 3012027Sjungma@eit.uni-kl.de// Revision 1.4 2011/08/26 20:46:18 acg 3112027Sjungma@eit.uni-kl.de// Andy Goodrich: moved the modification log to the end of the file to 3212027Sjungma@eit.uni-kl.de// eliminate source line number skew when check-ins are done. 3312027Sjungma@eit.uni-kl.de// 3412027Sjungma@eit.uni-kl.de 3512027Sjungma@eit.uni-kl.de#include "sysc/utils/sc_pq.h" 3612027Sjungma@eit.uni-kl.de 3712027Sjungma@eit.uni-kl.denamespace sc_core { 3812027Sjungma@eit.uni-kl.de 3912027Sjungma@eit.uni-kl.desc_ppq_base::sc_ppq_base( int sz, int (*cmp)( const void*, const void* ) ) 4012027Sjungma@eit.uni-kl.de : m_heap(0), m_size_alloc( sz ), m_heap_size( 0 ), m_compar( cmp ) 4112027Sjungma@eit.uni-kl.de{ 4212027Sjungma@eit.uni-kl.de // m_size_alloc must be at least 2, otherwise resizing doesn't work 4312027Sjungma@eit.uni-kl.de if( m_size_alloc < 2 ) { 4412027Sjungma@eit.uni-kl.de m_size_alloc = 2; 4512027Sjungma@eit.uni-kl.de } 4612027Sjungma@eit.uni-kl.de // allocate 4712027Sjungma@eit.uni-kl.de m_heap = new void*[m_size_alloc + 1]; 4812027Sjungma@eit.uni-kl.de // initialize 4912027Sjungma@eit.uni-kl.de for( int i = 0; i < m_size_alloc; ++ i ) { 5012027Sjungma@eit.uni-kl.de m_heap[i] = 0; 5112027Sjungma@eit.uni-kl.de } 5212027Sjungma@eit.uni-kl.de} 5312027Sjungma@eit.uni-kl.de 5412027Sjungma@eit.uni-kl.desc_ppq_base::~sc_ppq_base() 5512027Sjungma@eit.uni-kl.de{ 5612027Sjungma@eit.uni-kl.de delete[] m_heap; 5712027Sjungma@eit.uni-kl.de} 5812027Sjungma@eit.uni-kl.de 5912027Sjungma@eit.uni-kl.devoid* 6012027Sjungma@eit.uni-kl.desc_ppq_base::extract_top() 6112027Sjungma@eit.uni-kl.de{ 6212027Sjungma@eit.uni-kl.de assert( m_heap_size > 0 ); 6312027Sjungma@eit.uni-kl.de void* topelem = m_heap[1]; 6412027Sjungma@eit.uni-kl.de m_heap[1] = m_heap[m_heap_size]; 6512027Sjungma@eit.uni-kl.de m_heap_size --; 6612027Sjungma@eit.uni-kl.de heapify( 1 ); 6712027Sjungma@eit.uni-kl.de return topelem; 6812027Sjungma@eit.uni-kl.de} 6912027Sjungma@eit.uni-kl.de 7012027Sjungma@eit.uni-kl.devoid 7112027Sjungma@eit.uni-kl.desc_ppq_base::insert( void* elem ) 7212027Sjungma@eit.uni-kl.de{ 7312027Sjungma@eit.uni-kl.de m_heap_size ++; 7412027Sjungma@eit.uni-kl.de int i = m_heap_size; 7512027Sjungma@eit.uni-kl.de 7612027Sjungma@eit.uni-kl.de // resize the heap in case there's not enough memory 7712027Sjungma@eit.uni-kl.de if( m_heap_size > m_size_alloc ) { 7812027Sjungma@eit.uni-kl.de m_size_alloc += m_size_alloc / 2; 7912027Sjungma@eit.uni-kl.de void** new_heap = new void*[m_size_alloc + 1]; 8012027Sjungma@eit.uni-kl.de for( int j = 1; j < m_heap_size; ++ j ) { 8112027Sjungma@eit.uni-kl.de new_heap[j] = m_heap[j]; 8212027Sjungma@eit.uni-kl.de } 8312027Sjungma@eit.uni-kl.de delete[] m_heap; 8412027Sjungma@eit.uni-kl.de m_heap = new_heap; 8512027Sjungma@eit.uni-kl.de } 8612027Sjungma@eit.uni-kl.de 8712027Sjungma@eit.uni-kl.de while( (i > 1) && (m_compar( m_heap[parent( i )], elem ) < 0) ) { 8812027Sjungma@eit.uni-kl.de m_heap[i] = m_heap[parent( i )]; 8912027Sjungma@eit.uni-kl.de i = parent( i ); 9012027Sjungma@eit.uni-kl.de } 9112027Sjungma@eit.uni-kl.de m_heap[i] = elem; 9212027Sjungma@eit.uni-kl.de} 9312027Sjungma@eit.uni-kl.de 9412027Sjungma@eit.uni-kl.devoid 9512027Sjungma@eit.uni-kl.desc_ppq_base::heapify( int i ) 9612027Sjungma@eit.uni-kl.de{ 9712027Sjungma@eit.uni-kl.de int l; 9812027Sjungma@eit.uni-kl.de while( l = left( i ), l <= m_heap_size ) { 9912027Sjungma@eit.uni-kl.de int largest = (m_compar( m_heap[l], m_heap[i] ) > 0) ? l : i; 10012027Sjungma@eit.uni-kl.de 10112027Sjungma@eit.uni-kl.de int r = right( i ); 10212027Sjungma@eit.uni-kl.de if( (r <= m_heap_size) && 10312027Sjungma@eit.uni-kl.de (m_compar( m_heap[r], m_heap[largest] ) > 0) ) { 10412027Sjungma@eit.uni-kl.de largest = r; 10512027Sjungma@eit.uni-kl.de } 10612027Sjungma@eit.uni-kl.de 10712027Sjungma@eit.uni-kl.de if( largest != i ) { 10812027Sjungma@eit.uni-kl.de void* tmp = m_heap[i]; 10912027Sjungma@eit.uni-kl.de m_heap[i] = m_heap[largest]; 11012027Sjungma@eit.uni-kl.de m_heap[largest] = tmp; 11112027Sjungma@eit.uni-kl.de i = largest; 11212027Sjungma@eit.uni-kl.de } else { 11312027Sjungma@eit.uni-kl.de break; 11412027Sjungma@eit.uni-kl.de } 11512027Sjungma@eit.uni-kl.de } 11612027Sjungma@eit.uni-kl.de} 11712027Sjungma@eit.uni-kl.de 11812027Sjungma@eit.uni-kl.de} // namespace sc_core 11912027Sjungma@eit.uni-kl.de 12012027Sjungma@eit.uni-kl.de// Revision 1.3 2011/08/24 22:05:56 acg 12112027Sjungma@eit.uni-kl.de// Torsten Maehne: initialization changes to remove warnings. 12212027Sjungma@eit.uni-kl.de// 12312027Sjungma@eit.uni-kl.de// Revision 1.2 2011/02/18 20:38:44 acg 12412027Sjungma@eit.uni-kl.de// Andy Goodrich: Updated Copyright notice. 12512027Sjungma@eit.uni-kl.de// 12612027Sjungma@eit.uni-kl.de// Revision 1.1.1.1 2006/12/15 20:20:06 acg 12712027Sjungma@eit.uni-kl.de// SystemC 2.3 12812027Sjungma@eit.uni-kl.de// 12912027Sjungma@eit.uni-kl.de// Revision 1.3 2006/01/13 18:53:11 acg 13012027Sjungma@eit.uni-kl.de// Andy Goodrich: Added $Log command so that CVS comments are reproduced in 13112027Sjungma@eit.uni-kl.de// the source. 13212027Sjungma@eit.uni-kl.de 13312027Sjungma@eit.uni-kl.de// taf 134