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