sc_pq.h revision 12027:1eb7dc7aa10b
1/***************************************************************************** 2 3 Licensed to Accellera Systems Initiative Inc. (Accellera) under one or 4 more contributor license agreements. See the NOTICE file distributed 5 with this work for additional information regarding copyright ownership. 6 Accellera licenses this file to you under the Apache License, Version 2.0 7 (the "License"); you may not use this file except in compliance with the 8 License. You may obtain a copy of the License at 9 10 http://www.apache.org/licenses/LICENSE-2.0 11 12 Unless required by applicable law or agreed to in writing, software 13 distributed under the License is distributed on an "AS IS" BASIS, 14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or 15 implied. See the License for the specific language governing 16 permissions and limitations under the License. 17 18 *****************************************************************************/ 19 20/***************************************************************************** 21 22 sc_pq.h -- A simple priority queue (which can be used to model multiple 23 clocks). From Cormen-Leiserson-Rivest, Ch.7. 24 25 Original Author: Stan Y. Liao, Synopsys, Inc. 26 27 CHANGE LOG AT END OF FILE 28 *****************************************************************************/ 29 30#ifndef SC_PQ_H 31#define SC_PQ_H 32 33 34#include <cassert> 35 36namespace sc_core { 37 38// ---------------------------------------------------------------------------- 39// CLASS : sc_ppq_base 40// 41// Priority queue base class. 42// ---------------------------------------------------------------------------- 43 44class sc_ppq_base 45{ 46public: 47 48 typedef int (*compare_fn_t)( const void*, const void* ); 49 50 sc_ppq_base( int sz, compare_fn_t cmp ); 51 52 ~sc_ppq_base(); 53 54 void* top() const 55 { return m_heap[1]; } 56 57 void* extract_top(); 58 59 void insert( void* elem ); 60 61 int size() const 62 { return m_heap_size; } 63 64 bool empty() const 65 { return (m_heap_size == 0); } 66 67protected: 68 69 int parent( int i ) const 70 { return i >> 1; } 71 72 int left( int i ) const 73 { return i << 1; } 74 75 int right( int i ) const 76 { return (i << 1) + 1; } 77 78 void heapify( int i ); 79 80private: 81 82 void** m_heap; 83 int m_size_alloc; 84 int m_heap_size; 85 compare_fn_t m_compar; 86}; 87 88 89// ---------------------------------------------------------------------------- 90// CLASS TEMPLATE : sc_ppq<T> 91// 92// This class is a simple implementation of a priority queue based on 93// binary heaps. The class is templatized on its data type. A comparison 94// function needs to be supplied. 95// ---------------------------------------------------------------------------- 96 97template <class T> 98class sc_ppq 99 : public sc_ppq_base 100{ 101public: 102 103 // constructor - specify the maximum size of the queue and 104 // give a comparison function. 105 106 sc_ppq( int sz, compare_fn_t cmp ) 107 : sc_ppq_base( sz, cmp ) 108 {} 109 110 ~sc_ppq() 111 {} 112 113 // returns the value of the top element in the priority queue. 114 T top() const 115 { return (T) sc_ppq_base::top(); } 116 117 // pops the first element of the priority queue. 118 119 T extract_top() 120 { return (T) sc_ppq_base::extract_top(); } 121 122 // insert a new element to the priority queue. 123 124 void insert( T elem ) 125 { sc_ppq_base::insert( (void*) elem ); } 126 127 // size() and empty() are inherited. 128}; 129 130} // namespace sc_core 131 132// $Log: sc_pq.h,v $ 133// Revision 1.5 2011/08/29 18:04:32 acg 134// Philipp A. Hartmann: miscellaneous clean ups. 135// 136// Revision 1.4 2011/08/26 20:46:18 acg 137// Andy Goodrich: moved the modification log to the end of the file to 138// eliminate source line number skew when check-ins are done. 139// 140// Revision 1.3 2011/08/24 22:05:56 acg 141// Torsten Maehne: initialization changes to remove warnings. 142// 143// Revision 1.2 2011/02/18 20:38:44 acg 144// Andy Goodrich: Updated Copyright notice. 145// 146// Revision 1.1.1.1 2006/12/15 20:20:06 acg 147// SystemC 2.3 148// 149// Revision 1.3 2006/01/13 18:53:11 acg 150// Andy Goodrich: Added $Log command so that CVS comments are reproduced in 151// the source. 152// 153 154#endif 155