msgQ: privatize a coupla typedefs
[charm.git] / src / conv-core / msgq.h
1 #ifndef MSG_Q_H
2 #define MSG_Q_H
3
4 #include <deque>
5 #include <queue>
6 #include <ostream>
7
8 #if CMK_HAS_STD_UNORDERED_MAP
9 #include <unordered_map>
10 #else
11 #include <map>
12 #endif
13
14 namespace conv {
15
16 typedef void msg_t;
17
18 template <typename P>
19 inline P defaultprio(P *dummy_tag) { return 0; }
20
21
22 template <typename P = int>
23 class msgQ
24 {
25     public:
26         /// The datatype for msg priorities
27         typedef P prio_t;
28
29         ///
30         msgQ(): qSize(0) {}
31         ///
32         void enq(const msg_t *msg
33                 ,const prio_t &prio = defaultprio<prio_t>(0)
34                 ,const bool isFifo = true
35                 );
36         ///
37         const msg_t* deq();
38         ///
39         const msg_t* front() const;
40         ///
41         inline size_t size() const { return qSize; }
42         ///
43         inline bool empty() const { return (0 == qSize); }
44         ///
45         inline prio_t top_priority() const { return prios.top().first; }
46
47         ///
48         void enumerate(msg_t **first, msg_t **last) const;
49         ///
50         friend std::ostream& operator<< (std::ostream &out, const msgQ &q)
51         {
52             out <<"\nmsgQ[" << q.qSize << "]:";
53             out<<"\n";
54             return out;
55         }
56
57     private:
58         /// The datatype of the index of the container storing msgs of a given priority
59         typedef short bktidx_t;
60         /// Yet another typedef. Just for terseness
61         typedef typename std::pair<prio_t, bktidx_t> prioidx_t;
62
63         ///
64         size_t qSize;
65         /// Vector of msg buckets (each of them a deq)
66         std::vector< std::deque<const msg_t*> > msgbuckets;
67         /// A heap of distinct msg priorities
68         std::priority_queue<prioidx_t, std::vector<prioidx_t>, std::greater<prioidx_t> > prios;
69         /// A mapping between priority values and the bucket indices
70         #if CMK_HAS_STD_UNORDERED_MAP
71         std::unordered_map<prio_t, int> prio2bktidx;
72         #else
73         std::map<prio_t, int> prio2bktidx;
74         #endif
75 };
76
77
78
79 template <typename P>
80 void msgQ<P>::enq(const msg_t *msg
81                  ,const prio_t &prio
82                  ,const bool isFifo
83                  )
84 {
85     // Find index of / create the bucket holding msgs of this priority
86     typename std::map<prio_t, int>::iterator itr = prio2bktidx.find(prio);
87     bktidx_t bktidx;
88     if (prio2bktidx.end() != itr)
89         bktidx = itr->second;
90     else
91     {
92         msgbuckets.push_back( std::deque<const msg_t*>() );
93         bktidx = msgbuckets.size() - 1;
94         prio2bktidx[prio] = bktidx;
95     }
96
97     // Access deq holding msgs of this priority
98     std::deque<const msg_t*> &q = msgbuckets[bktidx];
99     // If this deq is empty, insert corresponding priority into prioQ
100     if (q.empty())
101         prios.push( std::make_pair(prio, bktidx) );
102
103     // Enq msg either at front or back of deq
104     if (isFifo)
105         q.push_back(msg);
106     else
107         q.push_front(msg);
108     // Increment the total number of msgs in this container
109     qSize++;
110 }
111
112
113
114 template <typename P>
115 const msg_t* msgQ<P>::deq()
116 {
117     if (prios.empty())
118         return NULL;
119
120     // Get the index of the bucket holding the highest priority msgs
121     const bktidx_t &bktidx = prios.top().second;
122     std::deque<const msg_t*> &q = msgbuckets[bktidx];
123
124     // Assert that there is at least one msg corresponding to this priority
125     if (q.empty()) throw;
126     const msg_t *msg = q.front();
127     q.pop_front();
128     // If all msgs of the highest priority have been consumed, pop that priority from the priority Q
129     if (q.empty())
130         prios.pop();
131     // Decrement the total number of msgs in this container
132     qSize--;
133     return msg;
134 }
135
136
137
138 template <typename P>
139 const msg_t* msgQ<P>::front() const
140 {
141     if (prios.empty())
142         return NULL;
143     return msgbuckets[prios.top().second].front();
144 }
145
146
147
148 template <typename P>
149 void msgQ<P>::enumerate(msg_t **first, msg_t **last) const
150 {
151     if (first >= last)
152         return;
153
154     msg_t **ptr = first;
155     for (int i=0; ptr != last && i <= msgbuckets.size(); i++)
156     {
157         std::deque<const msg_t*>::const_iterator itr = msgbuckets[i].begin();
158         while (ptr != last && itr != msgbuckets[i].end())
159             *ptr++ = (msg_t*) *itr++;
160     }
161 }
162
163 } // end namespace conv
164
165 #endif // MSG_Q_H
166