00001 /***************************************************************************** 00002 00003 The following code is derived, directly or indirectly, from the SystemC 00004 source code Copyright (c) 1996-2014 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 (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.accellera.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 CHANGE LOG AT END OF FILE 00026 *****************************************************************************/ 00027 00028 #ifndef SC_PQ_H 00029 #define SC_PQ_H 00030 00031 00032 #include <cassert> 00033 00034 namespace sc_core { 00035 00036 // ---------------------------------------------------------------------------- 00037 // CLASS : sc_ppq_base 00038 // 00039 // Priority queue base class. 00040 // ---------------------------------------------------------------------------- 00041 00042 class sc_ppq_base 00043 { 00044 public: 00045 00046 typedef int (*compare_fn_t)( const void*, const void* ); 00047 00048 sc_ppq_base( int sz, compare_fn_t cmp ); 00049 00050 ~sc_ppq_base(); 00051 00052 void* top() const 00053 { return m_heap[1]; } 00054 00055 void* extract_top(); 00056 00057 void insert( void* elem ); 00058 00059 int size() const 00060 { return m_heap_size; } 00061 00062 bool empty() const 00063 { return (m_heap_size == 0); } 00064 00065 protected: 00066 00067 int parent( int i ) const 00068 { return i >> 1; } 00069 00070 int left( int i ) const 00071 { return i << 1; } 00072 00073 int right( int i ) const 00074 { return (i << 1) + 1; } 00075 00076 void heapify( int i ); 00077 00078 private: 00079 00080 void** m_heap; 00081 int m_size_alloc; 00082 int m_heap_size; 00083 compare_fn_t m_compar; 00084 }; 00085 00086 00087 // ---------------------------------------------------------------------------- 00088 // CLASS TEMPLATE : sc_ppq<T> 00089 // 00090 // This class is a simple implementation of a priority queue based on 00091 // binary heaps. The class is templatized on its data type. A comparison 00092 // function needs to be supplied. 00093 // ---------------------------------------------------------------------------- 00094 00095 template <class T> 00096 class sc_ppq 00097 : public sc_ppq_base 00098 { 00099 public: 00100 00101 // constructor - specify the maximum size of the queue and 00102 // give a comparison function. 00103 00104 sc_ppq( int sz, compare_fn_t cmp ) 00105 : sc_ppq_base( sz, cmp ) 00106 {} 00107 00108 ~sc_ppq() 00109 {} 00110 00111 // returns the value of the top element in the priority queue. 00112 T top() const 00113 { return (T) sc_ppq_base::top(); } 00114 00115 // pops the first element of the priority queue. 00116 00117 T extract_top() 00118 { return (T) sc_ppq_base::extract_top(); } 00119 00120 // insert a new element to the priority queue. 00121 00122 void insert( T elem ) 00123 { sc_ppq_base::insert( (void*) elem ); } 00124 00125 // size() and empty() are inherited. 00126 }; 00127 00128 } // namespace sc_core 00129 00130 // $Log: sc_pq.h,v $ 00131 // Revision 1.5 2011/08/29 18:04:32 acg 00132 // Philipp A. Hartmann: miscellaneous clean ups. 00133 // 00134 // Revision 1.4 2011/08/26 20:46:18 acg 00135 // Andy Goodrich: moved the modification log to the end of the file to 00136 // eliminate source line number skew when check-ins are done. 00137 // 00138 // Revision 1.3 2011/08/24 22:05:56 acg 00139 // Torsten Maehne: initialization changes to remove warnings. 00140 // 00141 // Revision 1.2 2011/02/18 20:38:44 acg 00142 // Andy Goodrich: Updated Copyright notice. 00143 // 00144 // Revision 1.1.1.1 2006/12/15 20:20:06 acg 00145 // SystemC 2.3 00146 // 00147 // Revision 1.3 2006/01/13 18:53:11 acg 00148 // Andy Goodrich: Added $Log command so that CVS comments are reproduced in 00149 // the source. 00150 // 00151 00152 #endif
1.6.1