SuperTinyKernel™ RTOS 1.08.x
Lightweight, high-performance, deterministic, bare-metal C++ RTOS for resource-constrained embedded systems. MIT Open Source License.
Loading...
Searching...
No Matches
stk::sched::PriorityBitmap< BITS > Class Template Reference

Two-level bitmap for more priority levels than a native integer can hold (BITS is a multiple of 32 above 64, e.g. 96, 128, ..., 1024). More...

#include <stk_priority_bitmap.h>

Inheritance diagram for stk::sched::PriorityBitmap< BITS >:
Collaboration diagram for stk::sched::PriorityBitmap< BITS >:

Public Types

enum  {
  CAPACITY = BITS ,
  WORDS = (BITS / 32U)
}

Public Member Functions

 STK_STATIC_ASSERT_DESC_N (Multiple32,(BITS % 32U)==0U, "PriorityBitmap: BITS must be a multiple of 32")
 STK_STATIC_ASSERT_DESC_N (Min32, BITS >=32U, "PriorityBitmap: BITS must be at least 32")
 STK_STATIC_ASSERT_DESC_N (Max1024, BITS<=1024U, "PriorityBitmap: BITS must not exceed 1024 (32-bit summary)")
 PriorityBitmap ()
 Construct an empty bitmap.
__stk_forceinline void Set (uint32_t bit)
 Set bit bit, [0, BITS).
__stk_forceinline void Clear (uint32_t bit)
 Clear bit bit, [0, BITS).
__stk_forceinline bool IsSet (uint32_t bit) const
 Check that bit bit is set, [0, BITS).
__stk_forceinline bool IsEmpty () const
 Check that no bit is set.
__stk_forceinline uint32_t HighestSet () const
 Index of the most significant set bit.

Private Attributes

uint32_t m_summary
 Bit w set when m_words[w] != 0.
uint32_t m_words [WORDS]
 Level 0: the bits.

Detailed Description

template<uint32_t BITS>
class stk::sched::PriorityBitmap< BITS >

Two-level bitmap for more priority levels than a native integer can hold (BITS is a multiple of 32 above 64, e.g. 96, 128, ..., 1024).

Level 0 is an array of BITS / 32 words (bit i lives in word i / 32, position i % 32). Level 1 is a single 32-bit summary word where bit w is set if and only if word w is non-zero. The summary keeps every operation O(1) regardless of BITS:

Template Parameters
BITSNumber of bits. Must be a multiple of 32 and at most 1024 (32 words, the summary width). Any such value works (32 and 64 too), but plain uint32_t / uint64_t are cheaper for up to 64 priorities.
Note
Memory: BITS / 8 + 4 bytes, e.g. 36 bytes for 256 priorities, 132 bytes for 1024.
The default constructor creates an empty bitmap (value-initialization is therefore valid).
See also
PriorityBitmapTraits

Definition at line 140 of file stk_priority_bitmap.h.

Member Enumeration Documentation

◆ anonymous enum

template<uint32_t BITS>
anonymous enum
Enumerator
CAPACITY 

Number of bits.

WORDS 

Number of 32-bit words.

Definition at line 147 of file stk_priority_bitmap.h.

148 {
149 CAPACITY = BITS,
150 WORDS = (BITS / 32U)
151 };
Two-level bitmap for more priority levels than a native integer can hold (BITS is a multiple of 32 ab...
@ WORDS
Number of 32-bit words.

Constructor & Destructor Documentation

◆ PriorityBitmap()

template<uint32_t BITS>
stk::sched::PriorityBitmap< BITS >::PriorityBitmap ( )
inline

Construct an empty bitmap.

Definition at line 154 of file stk_priority_bitmap.h.

154 : m_summary(0U), m_words()
155 {}
uint32_t m_words[WORDS]
Level 0: the bits.
uint32_t m_summary
Bit w set when m_words[w] != 0.

Member Function Documentation

◆ Clear()

template<uint32_t BITS>
__stk_forceinline void stk::sched::PriorityBitmap< BITS >::Clear ( uint32_t bit)
inline

Clear bit bit, [0, BITS).

Definition at line 169 of file stk_priority_bitmap.h.

170 {
172
173 const uint32_t word = (bit >> 5U);
174
175 m_words[word] &= ~(1U << (bit & 31U));
176
177 if (m_words[word] == 0U)
178 {
179 m_summary &= ~(1U << word);
180 }
181 }
#define STK_ASSERT(e)
Runtime assertion. Halts execution if the expression e evaluates to false.
Definition stk_defs.h:532

◆ HighestSet()

template<uint32_t BITS>
__stk_forceinline uint32_t stk::sched::PriorityBitmap< BITS >::HighestSet ( ) const
inline

Index of the most significant set bit.

Warning
Bitmap must not be empty.

Definition at line 198 of file stk_priority_bitmap.h.

199 {
201
202 const uint32_t word = (31U - CountLeadingZeros(m_summary));
203
204 STK_ASSERT(m_words[word] != 0U);
205
206 return ((word << 5U) + (31U - CountLeadingZeros(m_words[word])));
207 }
uint32_t CountLeadingZeros(const uint32_t value) noexcept
Count leading zeros.
Definition stk_defs.h:791

◆ IsEmpty()

template<uint32_t BITS>
__stk_forceinline bool stk::sched::PriorityBitmap< BITS >::IsEmpty ( ) const
inline

Check that no bit is set.

Definition at line 192 of file stk_priority_bitmap.h.

193 {
194 return (m_summary == 0U);
195 }

◆ IsSet()

template<uint32_t BITS>
__stk_forceinline bool stk::sched::PriorityBitmap< BITS >::IsSet ( uint32_t bit) const
inline

Check that bit bit is set, [0, BITS).

Definition at line 184 of file stk_priority_bitmap.h.

185 {
187
188 return ((m_words[bit >> 5U] & (1U << (bit & 31U))) != 0U);
189 }

◆ Set()

template<uint32_t BITS>
__stk_forceinline void stk::sched::PriorityBitmap< BITS >::Set ( uint32_t bit)
inline

Set bit bit, [0, BITS).

Definition at line 158 of file stk_priority_bitmap.h.

159 {
161
162 const uint32_t word = (bit >> 5U);
163
164 m_words[word] |= (1U << (bit & 31U));
165 m_summary |= (1U << word);
166 }

◆ STK_STATIC_ASSERT_DESC_N() [1/3]

template<uint32_t BITS>
stk::sched::PriorityBitmap< BITS >::STK_STATIC_ASSERT_DESC_N ( Max1024 ,
BITS<= 1024U,
"PriorityBitmap< BITS >: BITS must not exceed 1024 (32-bit summary)"  )

◆ STK_STATIC_ASSERT_DESC_N() [2/3]

template<uint32_t BITS>
stk::sched::PriorityBitmap< BITS >::STK_STATIC_ASSERT_DESC_N ( Min32 ,
BITS >= 32U,
"PriorityBitmap< BITS >: BITS must be at least 32"  )

◆ STK_STATIC_ASSERT_DESC_N() [3/3]

template<uint32_t BITS>
stk::sched::PriorityBitmap< BITS >::STK_STATIC_ASSERT_DESC_N ( Multiple32 ,
(BITS % 32U) = =0U,
"PriorityBitmap< BITS >: BITS must be a multiple of 32"  )

Member Data Documentation

◆ m_summary

template<uint32_t BITS>
uint32_t stk::sched::PriorityBitmap< BITS >::m_summary
private

Bit w set when m_words[w] != 0.

Definition at line 210 of file stk_priority_bitmap.h.

◆ m_words

template<uint32_t BITS>
uint32_t stk::sched::PriorityBitmap< BITS >::m_words[WORDS]
private

Level 0: the bits.

Definition at line 211 of file stk_priority_bitmap.h.


The documentation for this class was generated from the following file: