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