msgQ test: Now also reports performance of STL-based variant of msg Q
[charm.git] / tests / charm++ / queue / msgq.h
1 #ifndef MSG_Q_H
2 #define MSG_Q_H
3
4 #include <deque>
5 #include <queue>
6 #include <map>
7 #include <ostream>
8
9 typedef void msg_t;
10
11 template <typename P>
12 inline P defaultprio(P *dummy_tag) { return 0; }
13
14
15 template <typename P = int>
16 class msgQ
17 {
18     public:
19         typedef P prio_t;
20
21         ///
22         msgQ(): qSize(0) {}
23         ///
24         void enq(const msg_t *msg
25                 ,const prio_t &prio = defaultprio<prio_t>(0)
26                 ,const bool isFifo = true
27                 );
28         ///
29         const msg_t* deq();
30         ///
31         const msg_t* front() const;
32         ///
33         inline size_t size() const { return qSize; }
34         ///
35         inline bool empty() const { return (0 == qSize); }
36         ///
37         inline prio_t top_priority() const { return prios.top(); }
38
39         ///
40         friend std::ostream& operator<< (std::ostream &out, const msgQ &q)
41         {
42             out <<"\nmsgQ[" << q.qSize << "]:";
43             out<<"\n";
44             return out;
45         }
46
47     private:
48         size_t qSize;
49         std::map<prio_t, std::deque<const msg_t*> > msgmap;
50         std::priority_queue<prio_t, std::vector<prio_t>, std::greater<prio_t> > prios;
51 };
52
53
54
55 template <typename P>
56 void msgQ<P>::enq(const msg_t *msg
57                  ,const prio_t &prio
58                  ,const bool isFifo
59                  )
60 {
61     // Create or access deq holding msgs of this priority
62     std::deque<const msg_t*> &q = msgmap[prio];
63     // If this deq is empty, insert corresponding priority into prioQ
64     if (q.empty())
65         prios.push(prio);
66     // Enq msg either at front or back of deq
67     if (isFifo)
68         q.push_back(msg);
69     else
70         q.push_front(msg);
71     // Increment the total number of msgs in this container
72     qSize++;
73
74 }
75
76
77
78 template <typename P>
79 const msg_t* msgQ<P>::deq()
80 {
81     if (prios.empty())
82         return NULL;
83
84     // Get the top priority in the priority queue
85     const prio_t &prio = prios.top();
86
87     std::deque<const msg_t*> &q = msgmap[prio];
88     // Assert that there is at least one msg corresponding to this priority, in the msgmap
89     if (q.empty()) throw;
90     const msg_t *msg = q.front();
91     q.pop_front();
92     // If all msgs of the highest priority have been consumed, pop that priority from the priority Q
93     if (q.empty())
94         prios.pop();
95     // Decrement the total number of msgs in this container
96     qSize--;
97     return msg;
98 }
99
100
101
102 template <typename P>
103 const msg_t* msgQ<P>::front() const
104 {
105     if (prios.empty())
106         return NULL;
107     prio_t &prio = prios.top();
108     return msgmap[prio].front();
109 }
110
111 #endif // MSG_Q_H
112