Remote Call Framework 3.2
Heap.hpp
1 
2 //******************************************************************************
3 // RCF - Remote Call Framework
4 //
5 // Copyright (c) 2005 - 2020, 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: 3.2
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 <cstdint>
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(std::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<std::uint32_t, T> & lhs,
121  const std::pair<std::uint32_t, T> & rhs)
122  {
123  std::uint32_t lhsTimeMs = lhs.first - mBaseTimeMs;
124  std::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  std::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  std::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<std::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  std::uint32_t getNextEntryTimeoutMs()
236  {
237  Lock lock(mTimerHeapMutex);
238 
239  return mTimerHeap.empty() ?
240  std::uint32_t(-1) :
241  getTimeoutMs(mTimerHeap.top());
242  }
243 
244  private:
245 
246  std::uint32_t getTimeoutMs(const TimerEntry & timerEntry)
247  {
248  return generateTimeoutMs(timerEntry.first);
249  }
250 
251  std::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
Definition: AmiIoHandler.hpp:24