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.h -- A simple priority queue (which can be used to model multiple 00021 clocks). From Cormen-Leiserson-Rivest, Ch.7. 00022 00023 Original Author: Stan Y. Liao, Synopsys, Inc. 00024 00025 *****************************************************************************/ 00026 00027 /***************************************************************************** 00028 00029 MODIFICATION LOG - modifiers, enter your name, affiliation, date and 00030 changes you are making here. 00031 00032 Name, Affiliation, Date: 00033 Description of Modification: 00034 00035 *****************************************************************************/ 00036 00037 // $Log: sc_pq.h,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 #ifndef SC_PQ_H 00047 #define SC_PQ_H 00048 00049 00050 #include <cassert> 00051 00052 namespace sc_core { 00053 00054 // ---------------------------------------------------------------------------- 00055 // CLASS : sc_ppq_base 00056 // 00057 // Priority queue base class. 00058 // ---------------------------------------------------------------------------- 00059 00060 class sc_ppq_base 00061 { 00062 public: 00063 00064 typedef int (*compare_fn_t)( const void*, const void* ); 00065 00066 sc_ppq_base( int sz, compare_fn_t cmp ); 00067 00068 ~sc_ppq_base(); 00069 00070 void* top() const 00071 { return m_heap[1]; } 00072 00073 void* extract_top(); 00074 00075 void insert( void* elem ); 00076 00077 int size() const 00078 { return m_heap_size; } 00079 00080 bool empty() const 00081 { return (m_heap_size == 0); } 00082 00083 protected: 00084 00085 int parent( int i ) const 00086 { return i >> 1; } 00087 00088 int left( int i ) const 00089 { return i << 1; } 00090 00091 int right( int i ) const 00092 { return (i << 1) + 1; } 00093 00094 void heapify( int i ); 00095 00096 private: 00097 00098 void** m_heap; 00099 int m_size_alloc; 00100 int m_heap_size; 00101 compare_fn_t m_compar; 00102 }; 00103 00104 00105 // ---------------------------------------------------------------------------- 00106 // CLASS TEMPLATE : sc_ppq<T> 00107 // 00108 // This class is a simple implementation of a priority queue based on 00109 // binary heaps. The class is templatized on its data type. A comparison 00110 // function needs to be supplied. 00111 // ---------------------------------------------------------------------------- 00112 00113 template <class T> 00114 class sc_ppq 00115 : public sc_ppq_base 00116 { 00117 public: 00118 00119 // constructor - specify the maximum size of the queue and 00120 // give a comparison function. 00121 00122 sc_ppq( int sz, compare_fn_t cmp ) 00123 : sc_ppq_base( sz, cmp ) 00124 {} 00125 00126 ~sc_ppq() 00127 {} 00128 00129 // returns the value of the top element in the priority queue. 00130 T top() const 00131 { return (T) sc_ppq_base::top(); } 00132 00133 // pops the first element of the priority queue. 00134 00135 T extract_top() 00136 { return (T) sc_ppq_base::extract_top(); } 00137 00138 // insert a new element to the priority queue. 00139 00140 void insert( T elem ) 00141 { sc_ppq_base::insert( (void*) elem ); } 00142 00143 // size() and empty() are inherited. 00144 }; 00145 00146 } // namespace sc_core 00147 00148 #endif
1.5.6