| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // ====================================================================== | ||
| 2 | // \title Os/Generic/PriorityQueue.hpp | ||
| 3 | // \brief priority queue implementation definitions for Os::Queue | ||
| 4 | // ====================================================================== | ||
| 5 | #include "Os/Condition.hpp" | ||
| 6 | #include "Os/Generic/Types/MaxHeap.hpp" | ||
| 7 | #include "Os/Mutex.hpp" | ||
| 8 | #include "Os/Queue.hpp" | ||
| 9 | #ifndef OS_GENERIC_PRIORITYQUEUE_HPP | ||
| 10 | #define OS_GENERIC_PRIORITYQUEUE_HPP | ||
| 11 | |||
| 12 | namespace Os { | ||
| 13 | namespace Generic { | ||
| 14 | |||
| 15 | //! \brief critical data stored for priority queue | ||
| 16 | //! | ||
| 17 | //! The priority queue has two essential data structures: a block of unordered memory storing message data and size. The | ||
| 18 | //! queue also stores a circular list of indices into that memory tracking which slots are free and which are taken. | ||
| 19 | //! These indices are ordered by a max heap data structure projecting priority on to the otherwise unordered data. Both | ||
| 20 | //! the data region and index list have queue depth number of entries. | ||
| 21 | struct PriorityQueueHandle : public QueueHandle { | ||
| 22 | Types::MaxHeap m_heap; //!< MaxHeap data store for tracking priority | ||
| 23 | U8* m_heap_pointer; //!< Pointer to the MaxHeap data store | ||
| 24 | U8* m_data = nullptr; //!< Pointer to data allocation | ||
| 25 | FwSizeType* m_indices = nullptr; //!< List of indices into data | ||
| 26 | FwSizeType* m_sizes = nullptr; //!< Size store for each method | ||
| 27 | FwSizeType m_depth = 0; //!< Depth of the queue | ||
| 28 | FwSizeType m_startIndex = 0; //!< Start index of the circular data structure | ||
| 29 | FwSizeType m_stopIndex = 0; //!< End index of the circular data structure | ||
| 30 | FwSizeType m_maxSize = 0; //!< Maximum size allowed of a message | ||
| 31 | FwSizeType m_highMark = 0; //!< Message count high water mark | ||
| 32 | Os::Mutex m_data_lock; //!< Lock against data manipulation | ||
| 33 | Os::ConditionVariable m_full; //!< Queue full condition variable to support blocking | ||
| 34 | Os::ConditionVariable m_empty; //!< Queue empty condition variable to support blocking | ||
| 35 | FwEnumStoreType m_id; //!< Identifier for the queue, used for memory allocation | ||
| 36 | |||
| 37 | //!\brief find an available index to store data from the list | ||
| 38 | FwSizeType find_index(); | ||
| 39 | |||
| 40 | //!\brief return index to the circular data structure | ||
| 41 | //!\param index: index to return to the list | ||
| 42 | void return_index(FwSizeType index); | ||
| 43 | |||
| 44 | //!\brief store data into a set index in the data store | ||
| 45 | void store_data(FwSizeType index, const U8* source, FwSizeType size); | ||
| 46 | |||
| 47 | //!\brief load data from a set index in the data store | ||
| 48 | void load_data(FwSizeType index, U8* destination, FwSizeType capacity); | ||
| 49 | }; | ||
| 50 | //! \brief generic priority queue implementation | ||
| 51 | //! | ||
| 52 | //! \warning This Priority Queue is not ISR safe | ||
| 53 | //! | ||
| 54 | //! A generic implementation of a priority queue to support the Os::QueueInterface. This queue uses OSAL mutexes, | ||
| 55 | //! and condition variables to provide for a task-safe blocking queue implementation. Data is stored in heap memory. | ||
| 56 | //! | ||
| 57 | //! \warning allocates memory on the heap | ||
| 58 | class PriorityQueue : public Os::QueueInterface { | ||
| 59 | public: | ||
| 60 | //! \brief default queue interface constructor | ||
| 61 |
1/1✓ Branch 2 taken 28 times.
|
28 | PriorityQueue() = default; |
| 62 | |||
| 63 | //! \brief default queue destructor | ||
| 64 | virtual ~PriorityQueue(); | ||
| 65 | |||
| 66 | //! \brief copy constructor is forbidden | ||
| 67 | PriorityQueue(const QueueInterface& other) = delete; | ||
| 68 | |||
| 69 | //! \brief copy constructor is forbidden | ||
| 70 | PriorityQueue(const QueueInterface* other) = delete; | ||
| 71 | |||
| 72 | //! \brief assignment operator is forbidden | ||
| 73 | PriorityQueue& operator=(const QueueInterface& other) override = delete; | ||
| 74 | |||
| 75 | //! \brief create queue storage | ||
| 76 | //! | ||
| 77 | //! Creates a queue ensuring sufficient storage to hold `depth` messages of `messageSize` size each. | ||
| 78 | //! | ||
| 79 | //! \warning allocates memory through the memory allocator registry | ||
| 80 | //! | ||
| 81 | //! \param id: identifier for the queue, used for memory allocation | ||
| 82 | //! \param name: name of queue | ||
| 83 | //! \param depth: depth of queue in number of messages | ||
| 84 | //! \param messageSize: size of an individual message | ||
| 85 | //! \return: status of the creation | ||
| 86 | Status create(FwEnumStoreType id, | ||
| 87 | const Fw::ConstStringBase& name, | ||
| 88 | FwSizeType depth, | ||
| 89 | FwSizeType messageSize) override; | ||
| 90 | |||
| 91 | //! \brief teardown the queue | ||
| 92 | //! | ||
| 93 | //! Allow for queues to deallocate resources as part of system shutdown. This delegates to the underlying queue | ||
| 94 | //! implementation. | ||
| 95 | void teardown() override; | ||
| 96 | |||
| 97 | //! \brief teardown the queue | ||
| 98 | //! | ||
| 99 | //! Allow for queues to deallocate resources as part of system shutdown. This delegates to the underlying queue | ||
| 100 | //! implementation. | ||
| 101 | //! | ||
| 102 | //! Note: this is a helper to allow this to be called from the destructor. | ||
| 103 | void teardownInternal(); | ||
| 104 | |||
| 105 | //! \brief send a message into the queue | ||
| 106 | //! | ||
| 107 | //! Send a message into the queue, providing the message data, size, priority, and blocking type. When | ||
| 108 | //! `blockType` is set to BLOCKING, this call will block on queue full. Otherwise, this will return an error | ||
| 109 | //! status on queue full. | ||
| 110 | //! | ||
| 111 | //! \warning It is invalid to send a null buffer | ||
| 112 | //! \warning This method will block if the queue is full and blockType is set to BLOCKING | ||
| 113 | //! \warning This method is not ISR safe | ||
| 114 | //! | ||
| 115 | //! \param buffer: message data | ||
| 116 | //! \param size: size of message data | ||
| 117 | //! \param priority: priority of the message | ||
| 118 | //! \param blockType: BLOCKING to block for space or NONBLOCKING to return error when queue is full | ||
| 119 | //! \return: status of the send | ||
| 120 | Status send(const U8* buffer, FwSizeType size, FwQueuePriorityType priority, BlockingType blockType) override; | ||
| 121 | |||
| 122 | //! \brief receive a message from the queue | ||
| 123 | //! | ||
| 124 | //! Receive a message from the queue, providing the message destination, capacity, priority, and blocking type. | ||
| 125 | //! When `blockType` is set to BLOCKING, this call will block on queue empty. Otherwise, this will return an | ||
| 126 | //! error status on queue empty. Actual size received and priority of message is set on success status. | ||
| 127 | //! | ||
| 128 | //! \warning It is invalid to send a null buffer | ||
| 129 | //! \warning This method will block if the queue is full and blockType is set to BLOCKING | ||
| 130 | //! | ||
| 131 | //! \param destination: destination for message data | ||
| 132 | //! \param capacity: maximum size of message data | ||
| 133 | //! \param blockType: BLOCKING to wait for message or NONBLOCKING to return error when queue is empty | ||
| 134 | //! \param actualSize: (output) actual size of message read | ||
| 135 | //! \param priority: (output) priority of message read | ||
| 136 | //! \return: status of the send | ||
| 137 | Status receive(U8* destination, | ||
| 138 | FwSizeType capacity, | ||
| 139 | BlockingType blockType, | ||
| 140 | FwSizeType& actualSize, | ||
| 141 | FwQueuePriorityType& priority) override; | ||
| 142 | |||
| 143 | //! \brief get number of messages available | ||
| 144 | //! | ||
| 145 | //! \return number of messages available | ||
| 146 | FwSizeType getMessagesAvailable() const override; | ||
| 147 | |||
| 148 | //! \brief get maximum messages stored at any given time | ||
| 149 | //! | ||
| 150 | //! \warning This method is not ISR safe | ||
| 151 | //! | ||
| 152 | //! Returns the maximum number of messages in this queue at any given time. This is the high-water mark for this | ||
| 153 | //! queue. | ||
| 154 | //! \return queue message high-water mark | ||
| 155 | FwSizeType getMessageHighWaterMark() const override; | ||
| 156 | |||
| 157 | QueueHandle* getHandle() override; | ||
| 158 | |||
| 159 | PriorityQueueHandle m_handle; | ||
| 160 | }; | ||
| 161 | } // namespace Generic | ||
| 162 | } // namespace Os | ||
| 163 | |||
| 164 | #endif // OS_GENERIC_PRIORITYQUEUE_HPP | ||
| 165 |