公平队列的实现
（金庆的专栏）
公平队列（Fair Queuing）是一种调度算法，与先进先出队列不同，
公平队列分成几个子队列，每个子队列公平地得到处理。
例如上海地铁站充值窗口有两个，一个站外，一个站内，由同一位服务人员受理，
服务人员会轮流处理两个窗口的请求，两个窗口的队列将公平地得到处理。
公平队列应用于路由器，保证不同的数据流得到公平处理。
Zeromq的消息处理也应用了公平队列，不会因为高数据量的连接阻塞其他连接的处理。
在网游服务器中，公平队列应用于消息的处理，解决场景局部拥挤造成整服都卡的问题。
例如消息处理按地图排队，这样某个地图的消息拥塞不会影响其他地图的消息处理。
fair_queue 仿 std::priority_queue 实现
1
2 /* Fair queue gives each sub queue a fair share.
3 Author: Jin Qing ( http://blog.csdn.net/jq0123 )
4
5 Example:
6 fair_queue<int, int> fq;
7 fq.push(1, 11);
8 fq.push(1, 12);
9 fq.push(1, 13);
10 fq.push(2, 21);
11 VERIFY(11 == fq.top()); fq.pop();
12 VERIFY(21 == fq.top()); fq.pop();
13 VERIFY(12 == fq.top()); fq.pop();
14 VERIFY(13 == fq.top()); fq.pop();
15 */
16
17 #ifndef _FAIR_QUEUE_H_
18 #define _FAIR_QUEUE_H_
19
20 #include <queue>
21 #include <boost/assert.hpp>
22 #include <boost/unordered_map.hpp>
23
24 // TEMPLATE CLASS fair_queue
25 template<class _Kty, class _Ty>
26 class fair_queue
27 {
28 public:
29 typedef _Kty key_type;
30 typedef _Ty value_type;
31
32 protected:
33 typedef std::queue<velue_type> sub_queue_type;
34 typedef boost::unordered_map<key_type, sub_queue_type> map_type;
35 typedef std::queue<sub_queue_type *> ordered_queue_type;
36 typedef boost::unordered_map<sub_queue_type *, key_type> reversed_map_type;
37
38 public:
39 fair_queue() {};
40
41 bool empty() const
42 { // test if queue is empty
43 return m.empty();
44 }
45
46 const value_type & top() const
47 { // return top element
48 BOOST_ASSERT(!empty());
49 BOOST_ASSERT(q.front());
50 return q.front()->front();
51 }
52
53 value_type top()
54 { // return mutable top element
55 BOOST_ASSERT(!empty());
56 BOOST_ASSERT(q.front());
57 return q.front()->front();
58 }
59
60 void push(const key_type & k, const value_type & v)
61 { // insert value in k sub queue
62 map_type::iterator itr = m.find(k);
63 if (itr != m.end())
64 {
65 BOOST_ASSERT(!(*itr).second.empty());
66 (*itr).second.push(v);
67 return;
68 }
69 // new sub queue
70 sub_queue_type * sub_queue = &m[k];
71 sub_queue->push(v);
72 BOOST_ASSERT(1 == sub_queue->size());
73 q.push(sub_queue);
74 rm[sub_queue] = k;
75 BOOST_ASSERT(q.size() == rm.size());
76 BOOST_ASSERT(m.size() == q.size());
77 }
78
79 void pop()
80 { // erase top element
81 BOOST_ASSERT(!empty());
82 BOOST_ASSERT(!q.empty());
83 sub_queue_type * sub_queue = q.front();
84 q.pop();
85 BOOST_ASSERT(sub_queue);
86 sub_queue->pop();
87 if (!sub_queue->empty())
88 {
89 // move to the end
90 q.push(sub_queue);
91 return;
92 }
93
94 // erase empty sub queue
95 const key_type & k = rm[sub_queue];
96 m.erase(k);
97 rm.erase(sub_queue);
98 BOOST_ASSERT(q.size() == rm.size());
99 BOOST_ASSERT(m.size() == q.size())
100 }
101
102 protected:
103 map_type m; //container
104 ordered_queue_type q; // to order the queues
105 reversed_map_type rm; // to delete key in m
106
107 };
108
109 #endif // _FAIR_QUEUE_H_
110
111