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.h -- A simple priority queue (which can be used to model multiple 2312027Sjungma@eit.uni-kl.de clocks). From Cormen-Leiserson-Rivest, Ch.7. 2412027Sjungma@eit.uni-kl.de 2512027Sjungma@eit.uni-kl.de Original Author: Stan Y. Liao, Synopsys, Inc. 2612027Sjungma@eit.uni-kl.de 2712027Sjungma@eit.uni-kl.de CHANGE LOG AT END OF FILE 2812027Sjungma@eit.uni-kl.de *****************************************************************************/ 2912027Sjungma@eit.uni-kl.de 3012027Sjungma@eit.uni-kl.de#ifndef SC_PQ_H 3112027Sjungma@eit.uni-kl.de#define SC_PQ_H 3212027Sjungma@eit.uni-kl.de 3312027Sjungma@eit.uni-kl.de 3412027Sjungma@eit.uni-kl.de#include <cassert> 3512027Sjungma@eit.uni-kl.de 3612027Sjungma@eit.uni-kl.denamespace sc_core { 3712027Sjungma@eit.uni-kl.de 3812027Sjungma@eit.uni-kl.de// ---------------------------------------------------------------------------- 3912027Sjungma@eit.uni-kl.de// CLASS : sc_ppq_base 4012027Sjungma@eit.uni-kl.de// 4112027Sjungma@eit.uni-kl.de// Priority queue base class. 4212027Sjungma@eit.uni-kl.de// ---------------------------------------------------------------------------- 4312027Sjungma@eit.uni-kl.de 4412027Sjungma@eit.uni-kl.declass sc_ppq_base 4512027Sjungma@eit.uni-kl.de{ 4612027Sjungma@eit.uni-kl.depublic: 4712027Sjungma@eit.uni-kl.de 4812027Sjungma@eit.uni-kl.de typedef int (*compare_fn_t)( const void*, const void* ); 4912027Sjungma@eit.uni-kl.de 5012027Sjungma@eit.uni-kl.de sc_ppq_base( int sz, compare_fn_t cmp ); 5112027Sjungma@eit.uni-kl.de 5212027Sjungma@eit.uni-kl.de ~sc_ppq_base(); 5312027Sjungma@eit.uni-kl.de 5412027Sjungma@eit.uni-kl.de void* top() const 5512027Sjungma@eit.uni-kl.de { return m_heap[1]; } 5612027Sjungma@eit.uni-kl.de 5712027Sjungma@eit.uni-kl.de void* extract_top(); 5812027Sjungma@eit.uni-kl.de 5912027Sjungma@eit.uni-kl.de void insert( void* elem ); 6012027Sjungma@eit.uni-kl.de 6112027Sjungma@eit.uni-kl.de int size() const 6212027Sjungma@eit.uni-kl.de { return m_heap_size; } 6312027Sjungma@eit.uni-kl.de 6412027Sjungma@eit.uni-kl.de bool empty() const 6512027Sjungma@eit.uni-kl.de { return (m_heap_size == 0); } 6612027Sjungma@eit.uni-kl.de 6712027Sjungma@eit.uni-kl.deprotected: 6812027Sjungma@eit.uni-kl.de 6912027Sjungma@eit.uni-kl.de int parent( int i ) const 7012027Sjungma@eit.uni-kl.de { return i >> 1; } 7112027Sjungma@eit.uni-kl.de 7212027Sjungma@eit.uni-kl.de int left( int i ) const 7312027Sjungma@eit.uni-kl.de { return i << 1; } 7412027Sjungma@eit.uni-kl.de 7512027Sjungma@eit.uni-kl.de int right( int i ) const 7612027Sjungma@eit.uni-kl.de { return (i << 1) + 1; } 7712027Sjungma@eit.uni-kl.de 7812027Sjungma@eit.uni-kl.de void heapify( int i ); 7912027Sjungma@eit.uni-kl.de 8012027Sjungma@eit.uni-kl.deprivate: 8112027Sjungma@eit.uni-kl.de 8212027Sjungma@eit.uni-kl.de void** m_heap; 8312027Sjungma@eit.uni-kl.de int m_size_alloc; 8412027Sjungma@eit.uni-kl.de int m_heap_size; 8512027Sjungma@eit.uni-kl.de compare_fn_t m_compar; 8612027Sjungma@eit.uni-kl.de}; 8712027Sjungma@eit.uni-kl.de 8812027Sjungma@eit.uni-kl.de 8912027Sjungma@eit.uni-kl.de// ---------------------------------------------------------------------------- 9012027Sjungma@eit.uni-kl.de// CLASS TEMPLATE : sc_ppq<T> 9112027Sjungma@eit.uni-kl.de// 9212027Sjungma@eit.uni-kl.de// This class is a simple implementation of a priority queue based on 9312027Sjungma@eit.uni-kl.de// binary heaps. The class is templatized on its data type. A comparison 9412027Sjungma@eit.uni-kl.de// function needs to be supplied. 9512027Sjungma@eit.uni-kl.de// ---------------------------------------------------------------------------- 9612027Sjungma@eit.uni-kl.de 9712027Sjungma@eit.uni-kl.detemplate <class T> 9812027Sjungma@eit.uni-kl.declass sc_ppq 9912027Sjungma@eit.uni-kl.de : public sc_ppq_base 10012027Sjungma@eit.uni-kl.de{ 10112027Sjungma@eit.uni-kl.depublic: 10212027Sjungma@eit.uni-kl.de 10312027Sjungma@eit.uni-kl.de // constructor - specify the maximum size of the queue and 10412027Sjungma@eit.uni-kl.de // give a comparison function. 10512027Sjungma@eit.uni-kl.de 10612027Sjungma@eit.uni-kl.de sc_ppq( int sz, compare_fn_t cmp ) 10712027Sjungma@eit.uni-kl.de : sc_ppq_base( sz, cmp ) 10812027Sjungma@eit.uni-kl.de {} 10912027Sjungma@eit.uni-kl.de 11012027Sjungma@eit.uni-kl.de ~sc_ppq() 11112027Sjungma@eit.uni-kl.de {} 11212027Sjungma@eit.uni-kl.de 11312027Sjungma@eit.uni-kl.de // returns the value of the top element in the priority queue. 11412027Sjungma@eit.uni-kl.de T top() const 11512027Sjungma@eit.uni-kl.de { return (T) sc_ppq_base::top(); } 11612027Sjungma@eit.uni-kl.de 11712027Sjungma@eit.uni-kl.de // pops the first element of the priority queue. 11812027Sjungma@eit.uni-kl.de 11912027Sjungma@eit.uni-kl.de T extract_top() 12012027Sjungma@eit.uni-kl.de { return (T) sc_ppq_base::extract_top(); } 12112027Sjungma@eit.uni-kl.de 12212027Sjungma@eit.uni-kl.de // insert a new element to the priority queue. 12312027Sjungma@eit.uni-kl.de 12412027Sjungma@eit.uni-kl.de void insert( T elem ) 12512027Sjungma@eit.uni-kl.de { sc_ppq_base::insert( (void*) elem ); } 12612027Sjungma@eit.uni-kl.de 12712027Sjungma@eit.uni-kl.de // size() and empty() are inherited. 12812027Sjungma@eit.uni-kl.de}; 12912027Sjungma@eit.uni-kl.de 13012027Sjungma@eit.uni-kl.de} // namespace sc_core 13112027Sjungma@eit.uni-kl.de 13212027Sjungma@eit.uni-kl.de// $Log: sc_pq.h,v $ 13312027Sjungma@eit.uni-kl.de// Revision 1.5 2011/08/29 18:04:32 acg 13412027Sjungma@eit.uni-kl.de// Philipp A. Hartmann: miscellaneous clean ups. 13512027Sjungma@eit.uni-kl.de// 13612027Sjungma@eit.uni-kl.de// Revision 1.4 2011/08/26 20:46:18 acg 13712027Sjungma@eit.uni-kl.de// Andy Goodrich: moved the modification log to the end of the file to 13812027Sjungma@eit.uni-kl.de// eliminate source line number skew when check-ins are done. 13912027Sjungma@eit.uni-kl.de// 14012027Sjungma@eit.uni-kl.de// Revision 1.3 2011/08/24 22:05:56 acg 14112027Sjungma@eit.uni-kl.de// Torsten Maehne: initialization changes to remove warnings. 14212027Sjungma@eit.uni-kl.de// 14312027Sjungma@eit.uni-kl.de// Revision 1.2 2011/02/18 20:38:44 acg 14412027Sjungma@eit.uni-kl.de// Andy Goodrich: Updated Copyright notice. 14512027Sjungma@eit.uni-kl.de// 14612027Sjungma@eit.uni-kl.de// Revision 1.1.1.1 2006/12/15 20:20:06 acg 14712027Sjungma@eit.uni-kl.de// SystemC 2.3 14812027Sjungma@eit.uni-kl.de// 14912027Sjungma@eit.uni-kl.de// Revision 1.3 2006/01/13 18:53:11 acg 15012027Sjungma@eit.uni-kl.de// Andy Goodrich: Added $Log command so that CVS comments are reproduced in 15112027Sjungma@eit.uni-kl.de// the source. 15212027Sjungma@eit.uni-kl.de// 15312027Sjungma@eit.uni-kl.de 15412027Sjungma@eit.uni-kl.de#endif 155