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