RCFProto

- Main Page
- Classes
- Files

- File List

All Classes Functions Typedefs
Heap.hpp
1
2 //******************************************************************************
3 // RCF - Remote Call Framework
4 //
5 // Copyright (c) 2005 - 2013, Delta V Software. All rights reserved.
6 // http://www.deltavsoft.com
7 //
8 // RCF is distributed under dual licenses - closed source or GPL.
9 // Consult your particular license for conditions of use.
10 //
11 // If you have not purchased a commercial license, you are using RCF
12 // under GPL terms.
13 //
14 // Version: 2.0
15 // Contact: support <at> deltavsoft.com
16 //
17 //******************************************************************************
18
19 #ifndef INCLUDE_RCF_HEAP_HPP
20 #define INCLUDE_RCF_HEAP_HPP
21
22 #include <algorithm>
23 #include <vector>
24
25 #include <boost/cstdint.hpp>
26
27 #include <RCF/ThreadLibrary.hpp>
28 #include <RCF/Tools.hpp>
29
30 namespace RCF {
31
32 template<typename Element, typename Compare = std::less<Element> >
33 class Heap
34 {
35 public:
36
37 Heap() : mCompare()
38 {
39 }
40
41 Heap(const Compare & compare) : mCompare(compare)
42 {
43 }
44
45 void add(const Element & element)
46 {
47 mStore.push_back(element);
48 std::push_heap(mStore.begin(), mStore.end(), mCompare);
49 }
50
51 void remove(const Element & element)
52 {
53 RCF::eraseRemove(mStore, element);
54 std::make_heap(mStore.begin(), mStore.end(), mCompare);
55 }
56
57 Element & top()
58 {
59 return *mStore.begin();
60 }
61
62 const Element & top() const
63 {
64 return *mStore.begin();
65 }
66
67 void pop()
68 {
69 std::pop_heap(mStore.begin(), mStore.end(), mCompare);
70 mStore.pop_back();
71 }
72
73 std::size_t size() const
74 {
75 return mStore.size();
76 }
77
78 bool empty() const
79 {
80 return mStore.empty();
81 }
82
83 void clear()
84 {
85 mStore.clear();
86 }
87
88 void setCompare(const Compare & compare, bool reorder = true)
89 {
90 mCompare = compare;
91
92 if (reorder)
93 {
94 std::make_heap(mStore.begin(), mStore.end(), mCompare);
95 }
96 }
97
98 private:
99
100 Compare mCompare;
101 std::vector<Element> mStore;
102 };
103
104 class TimerCompare
105 {
106 public:
107
108 TimerCompare() :
109 mBaseTimeMs(0)
110 {}
111
112 TimerCompare(boost::uint32_t baseTimeMs) :
113 mBaseTimeMs(baseTimeMs)
114 {}
115
116 // We want a greater-than comparison, so that the lowest
117 // elements are at the top of the heap.
118 template<typename T>
119 bool operator()(
120 const std::pair<boost::uint32_t, T> & lhs,
121 const std::pair<boost::uint32_t, T> & rhs)
122 {
123 boost::uint32_t lhsTimeMs = lhs.first - mBaseTimeMs;
124 boost::uint32_t rhsTimeMs = rhs.first - mBaseTimeMs;
125
126 return
127 std::make_pair(lhsTimeMs, lhs.second)
128 > std::make_pair(rhsTimeMs, rhs.second);
129 }
130
131 private:
132
133 boost::uint32_t mBaseTimeMs;
134 };
135
136 template<typename T>
137 class TimerHeap
138 {
139 public:
140
141 TimerHeap() :
142 mBaseTimeMs(0)
143 {
144 rebase();
145 }
146
147 void rebase()
148 {
149 Lock lock(mTimerHeapMutex);
150
151 boost::uint32_t timeNowMs = RCF::getCurrentTimeMs();
152 if (timeNowMs - mBaseTimeMs > 1000*60*60)
153 {
154 mBaseTimeMs = mTimerHeap.empty() ?
155 timeNowMs - 1000*10 :
156 mTimerHeap.top().first - 1000*10;
157
158 mTimerHeap.setCompare( TimerCompare(mBaseTimeMs), false );
159 }
160 }
161
162
163 typedef std::pair<boost::uint32_t, T> TimerEntry;
164
165 void add(const TimerEntry & timerEntry)
166 {
167 Lock lock(mTimerHeapMutex);
168 mTimerHeap.add(timerEntry);
169
170 }
171
172 void remove(const TimerEntry & timerEntry)
173 {
174 Lock lock(mTimerHeapMutex);
175 mTimerHeap.remove(timerEntry);
176 }
177
178 bool compareTop(const TimerEntry & timerEntry)
179 {
180 Lock lock(mTimerHeapMutex);
181 if (mTimerHeap.empty())
182 {
183 return false;
184 }
185 return mTimerHeap.top() == timerEntry;
186 }
187
188 std::size_t size() const
189 {
190 Lock lock(mTimerHeapMutex);
191 return mTimerHeap.size();
192 }
193
194 bool empty() const
195 {
196 Lock lock(mTimerHeapMutex);
197 return mTimerHeap.empty();
198 }
199
200 void clear()
201 {
202 Lock lock(mTimerHeapMutex);
203 mTimerHeap.clear();
204 }
205
206 bool popExpiredEntry(TimerEntry & timerEntry)
207 {
208 Lock lock(mTimerHeapMutex);
209
210 if ( !mTimerHeap.empty()
211 && getTimeoutMs( mTimerHeap.top() ) == 0)
212 {
213 timerEntry= mTimerHeap.top();
214 mTimerHeap.pop();
215 return true;
216 }
217
218 return false;
219 }
220
221 bool getExpiredEntry(TimerEntry & timerEntry)
222 {
223 Lock lock(mTimerHeapMutex);
224
225 if ( !mTimerHeap.empty()
226 && getTimeoutMs( mTimerHeap.top() ) == 0)
227 {
228 timerEntry= mTimerHeap.top();
229 return true;
230 }
231
232 return false;
233 }
234
235 boost::uint32_t getNextEntryTimeoutMs()
236 {
237 Lock lock(mTimerHeapMutex);
238
239 return mTimerHeap.empty() ?
240 boost::uint32_t(-1) :
241 getTimeoutMs(mTimerHeap.top());
242 }
243
244 private:
245
246 boost::uint32_t getTimeoutMs(const TimerEntry & timerEntry)
247 {
248 return generateTimeoutMs(timerEntry.first);
249 }
250
251 boost::uint32_t mBaseTimeMs;
252
253 mutable Mutex mTimerHeapMutex;
254 Heap<TimerEntry, TimerCompare> mTimerHeap;
255 };
256
257
258 } // namespace RCF
259
260 #endif // ! INCLUDE_RCF_HEAP_HPP