QP/C++  5.9.8
qpset.h
Go to the documentation of this file.
1 
39 #ifndef qpset_h
40 #define qpset_h
41 
42 #if (QF_MAX_ACTIVE < 1) || (64 < QF_MAX_ACTIVE)
43  #error "QF_MAX_ACTIVE not defined or out of range. Valid range is 1..64"
44 #endif
45 
46 namespace QP {
47 
48 /****************************************************************************/
49 /* Log-base-2 calculations ...*/
50 #ifndef QF_LOG2
51 
57  extern uint8_t const QF_log2Lkup[256];
58 
67  inline uint_fast8_t QF_LOG2(uint32_t const x) {
68  uint_fast8_t n;
69  uint_fast8_t i;
70 
71  if ((x >> 16) != static_cast<uint32_t>(0)) {
72  if ((x >> 24) != static_cast<uint32_t>(0)) {
73  i = static_cast<uint_fast8_t>(x >> 24);
74  n = static_cast<uint_fast8_t>(24);
75  }
76  else {
77  i = static_cast<uint_fast8_t>(x >> 16);
78  n = static_cast<uint_fast8_t>(16);
79  }
80  }
81  else {
82  if ((x >> 8) != static_cast<uint32_t>(0)) {
83  i = static_cast<uint_fast8_t>(x >> 8);
84  n = static_cast<uint_fast8_t>(8);
85  }
86  else {
87  i = static_cast<uint_fast8_t>(x);
88  n = static_cast<uint_fast8_t>(0);
89  }
90  }
91  return static_cast<uint_fast8_t>(QF_log2Lkup[i]) + n;
92  }
93 
94 #endif // QF_LOG2
95 
96 //****************************************************************************
97 #if (QF_MAX_ACTIVE <= 32)
98 class QPSet {
105 
106  uint32_t volatile m_bits;
107 
108 public:
109 
111  void setEmpty(void) {
112  m_bits = static_cast<uint32_t>(0);
113  }
114 
116  bool isEmpty(void) const {
117  return (m_bits == static_cast<uint32_t>(0));
118  }
119 
121  bool notEmpty(void) const {
122  return (m_bits != static_cast<uint32_t>(0));
123  }
124 
126  bool hasElement(uint_fast8_t const n) const {
127  return (m_bits & (static_cast<uint32_t>(1)
128  << (n - static_cast<uint_fast8_t>(1))))
129  != static_cast<uint32_t>(0);
130  }
131 
133  void insert(uint_fast8_t const n) {
134  m_bits |= static_cast<uint32_t>(
135  static_cast<uint32_t>(1) << (n - static_cast<uint_fast8_t>(1)));
136  }
137 
139  void remove(uint_fast8_t const n) {
140  m_bits &= static_cast<uint32_t>(
141  ~(static_cast<uint32_t>(1) << (n - static_cast<uint_fast8_t>(1))));
142  }
143 
145  uint_fast8_t findMax(void) const {
146  return QF_LOG2(m_bits);
147  }
148 };
149 
150 #else // QF_MAX_ACTIVE > 32
151 
158 class QPSet {
159 
160  uint32_t volatile m_bits[2];
161 
162 public:
163 
165  void setEmpty(void) {
166  m_bits[0] = static_cast<uint32_t>(0);
167  m_bits[1] = static_cast<uint32_t>(0);
168  }
169 
171  // the following logic avoids UB in volatile access for MISRA compliantce
172  bool isEmpty(void) const {
173  return (m_bits[0] == static_cast<uint32_t>(0))
174  ? (m_bits[1] == static_cast<uint32_t>(0))
175  : false;
176  }
177 
179  // the following logic avoids UB in volatile access for MISRA compliantce
180  bool notEmpty(void) const {
181  return (m_bits[0] != static_cast<uint32_t>(0))
182  ? true
183  : (m_bits[1] != static_cast<uint32_t>(0));
184  }
185 
187  bool hasElement(uint_fast8_t const n) const {
188  return (n <= static_cast<uint_fast8_t>(32))
189  ? ((m_bits[0] & (static_cast<uint32_t>(1)
190  << (n - static_cast<uint_fast8_t>(1))))
191  != static_cast<uint32_t>(0))
192  : ((m_bits[1] & (static_cast<uint32_t>(1)
193  << (n - static_cast<uint_fast8_t>(33))))
194  != static_cast<uint32_t>(0));
195  }
196 
198  void insert(uint_fast8_t const n) {
199  if (n <= static_cast<uint_fast8_t>(32)) {
200  m_bits[0] |= (static_cast<uint32_t>(1)
201  << (n - static_cast<uint_fast8_t>(1)));
202  }
203  else {
204  m_bits[1] |= (static_cast<uint32_t>(1)
205  << (n - static_cast<uint_fast8_t>(33)));
206  }
207  }
208 
210  void remove(uint_fast8_t const n) {
211  if (n <= static_cast<uint_fast8_t>(32)) {
212  (m_bits[0] &= ~(static_cast<uint32_t>(1)
213  << (n - static_cast<uint_fast8_t>(1))));
214  }
215  else {
216  (m_bits[1] &= ~(static_cast<uint32_t>(1)
217  << (n - static_cast<uint_fast8_t>(33))));
218  }
219  }
220 
222  uint_fast8_t findMax(void) const {
223  return (m_bits[1] != static_cast<uint32_t>(0))
224  ? (QF_LOG2(m_bits[1]) + static_cast<uint_fast8_t>(32)) \
225  : (QF_LOG2(m_bits[0]));
226  }
227 };
228 
229 #endif // QF_MAX_ACTIVE
230 
231 } // namespace QP
232 
233 #endif // qpset_h
234 
Priority Set of up to 32 elements */.
Definition: qpset.h:104
uint8_t const QF_log2Lkup[256]
Lookup table for (log2(n) + 1), where n = 0..255 */.
Definition: qf_act.cpp:159
unsigned char uint8_t
exact-width 8-bit unsigned int
Definition: stdint.h:29
void insert(uint_fast8_t const n)
insert element n into the set, n = 1..8
Definition: qpset.h:133
bool notEmpty(void) const
Evaluates to true if the priority set is not empty.
Definition: qpset.h:121
bool isEmpty(void) const
Evaluates to true if the priority set is empty.
Definition: qpset.h:116
unsigned int uint_fast8_t
fast at-least 8-bit unsigned int
Definition: stdint.h:36
unsigned long uint32_t
exact-width 32-bit unsigned int
Definition: stdint.h:31
bool hasElement(uint_fast8_t const n) const
the function evaluates to TRUE if the priority set has the element n.
Definition: qpset.h:126
namespace associated with the QP/C++ framework
Definition: api.dox:1
uint_fast8_t QF_LOG2(uint32_t const x)
function that returns (log2(x) + 1), where x is uint32_t */
Definition: qpset.h:67
void setEmpty(void)
Makes the priority set me_ empty.
Definition: qpset.h:111
uint_fast8_t findMax(void) const
find the maximum element in the set, returns zero if the set is empty
Definition: qpset.h:145