F´ Flight Software - C/C++ Documentation devel
A framework for building embedded system applications to NASA flight quality standards.
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
PriorityBufferQueue.cpp
Go to the documentation of this file.
1// ======================================================================
2// \title PriorityBufferQueue.hpp
3// \author dinkel
4// \brief An implementation of BufferQueue which uses a stable max heap
5// data structure for the queue. Items of highest priority will
6// be popped off of the queue first. Items of equal priority will
7// be popped off the queue in FIFO order.
8//
9// \copyright
10// Copyright 2009-2015, by the California Institute of Technology.
11// ALL RIGHTS RESERVED. United States Government Sponsorship
12// acknowledged.
13//
14// ======================================================================
15
18#include <Fw/Types/Assert.hpp>
19#include <cstring>
20#include <cstdio>
21#include <new>
22
23// This is a priority queue implementation implemented using a stable max heap.
24// Elements pushed onto the queue will be popped off in priority order.
25// Elements of the same priority will be popped off in FIFO order.
26namespace Os {
27
29 // Queue handler:
31
39
41 // Helper functions:
43
45 NATIVE_UINT_TYPE* indexes = pQueue->indexes;
46
47 // Get an available index from the index pool:
48 NATIVE_UINT_TYPE index = indexes[pQueue->startIndex % depth];
49 ++pQueue->startIndex;
50 NATIVE_UINT_TYPE diff = pQueue->stopIndex - pQueue->startIndex;
51 FW_ASSERT(diff <= depth, diff, depth, pQueue->stopIndex, pQueue->startIndex);
52 return index;
53 }
54
56 NATIVE_UINT_TYPE* indexes = pQueue->indexes;
57
58 // Return the index back to the index pool:
59 indexes[pQueue->stopIndex % depth] = index;
60 ++pQueue->stopIndex;
61 NATIVE_UINT_TYPE diff = pQueue->stopIndex - pQueue->startIndex;
62 FW_ASSERT(diff <= depth, diff, depth, pQueue->stopIndex, pQueue->startIndex);
63 }
64
66 // Class functions:
68
69 bool BufferQueue::initialize(NATIVE_UINT_TYPE depth, NATIVE_UINT_TYPE msgSize) {
70 // Create the priority queue data structure on the heap:
71 MaxHeap* heap = new(std::nothrow) MaxHeap;
72 if (nullptr == heap) {
73 return false;
74 }
75 if( !heap->create(depth) ) {
76 delete heap;
77 return false;
78 }
79 U8* data = new(std::nothrow) U8[depth*(sizeof(msgSize) + msgSize)];
80 if (nullptr == data) {
81 delete heap;
82 return false;
83 }
84 NATIVE_UINT_TYPE* indexes = new(std::nothrow) NATIVE_UINT_TYPE[depth];
85 if (nullptr == indexes) {
86 delete heap;
87 delete[] data;
88 return false;
89 }
90 for(NATIVE_UINT_TYPE ii = 0; ii < depth; ++ii) {
91 indexes[ii] = getBufferIndex(ii);
92 }
93 PriorityQueue* priorityQueue = new(std::nothrow) PriorityQueue;
94 if (nullptr == priorityQueue) {
95 delete heap;
96 delete[] data;
97 delete[] indexes;
98 return false;
99 }
100 priorityQueue->heap = heap;
101 priorityQueue->data = data;
102 priorityQueue->indexes = indexes;
103 priorityQueue->startIndex = 0;
104 priorityQueue->stopIndex = depth;
105 this->m_queue = priorityQueue;
106 return true;
107 }
108
109 void BufferQueue::finalize() {
110 PriorityQueue* pQueue = static_cast<PriorityQueue*>(this->m_queue);
111 if (nullptr != pQueue)
112 {
113 MaxHeap* heap = pQueue->heap;
114 if (nullptr != heap) {
115 delete heap;
116 }
117 U8* data = pQueue->data;
118 if (nullptr != data) {
119 delete [] data;
120 }
121 NATIVE_UINT_TYPE* indexes = pQueue->indexes;
122 if (nullptr != indexes)
123 {
124 delete [] indexes;
125 }
126 delete pQueue;
127 }
128 this->m_queue = nullptr;
129 }
130
131 bool BufferQueue::enqueue(const U8* buffer, NATIVE_UINT_TYPE size, NATIVE_INT_TYPE priority) {
132
133 // Extract queue handle variables:
134 PriorityQueue* pQueue = static_cast<PriorityQueue*>(this->m_queue);
135 MaxHeap* heap = pQueue->heap;
136 U8* data = pQueue->data;
137
138 // Get an available data index:
139 NATIVE_UINT_TYPE index = checkoutIndex(pQueue, this->m_depth);
140
141 // Insert the data into the heap:
142 bool ret = heap->push(priority, index);
143 FW_ASSERT(ret, ret);
144
145 // Store the buffer to the queue:
146 this->enqueueBuffer(buffer, size, data, index);
147
148 return true;
149 }
150
151 bool BufferQueue::dequeue(U8* buffer, NATIVE_UINT_TYPE& size, NATIVE_INT_TYPE &priority) {
152
153 // Extract queue handle variables:
154 PriorityQueue* pQueue = static_cast<PriorityQueue*>(this->m_queue);
155 MaxHeap* heap = pQueue->heap;
156 U8* data = pQueue->data;
157
158 // Get the highest priority data from the heap:
159 NATIVE_UINT_TYPE index = 0;
160 bool ret = heap->pop(priority, index);
161 FW_ASSERT(ret, ret);
162
163 ret = this->dequeueBuffer(buffer, size, data, index);
164 if(!ret) {
165 // The dequeue failed, so push the popped
166 // value back on the heap.
167 ret = heap->push(priority, index);
168 FW_ASSERT(ret, ret);
169 return false;
170 }
171
172 // Return the index to the available indexes:
173 returnIndex(pQueue, this->m_depth, index);
174
175 return true;
176 }
177}
#define FW_ASSERT(...)
Definition Assert.hpp:14
PlatformIntType NATIVE_INT_TYPE
Definition BasicTypes.h:51
uint8_t U8
8-bit unsigned integer
Definition BasicTypes.h:26
PlatformUIntType NATIVE_UINT_TYPE
Definition BasicTypes.h:52
A stable max heap data structure.
Definition MaxHeap.hpp:27
Definition File.cpp:6
void returnIndex(PriorityQueue *pQueue, NATIVE_UINT_TYPE depth, NATIVE_UINT_TYPE index)
NATIVE_UINT_TYPE checkoutIndex(PriorityQueue *pQueue, NATIVE_UINT_TYPE depth)
NATIVE_UINT_TYPE startIndex
NATIVE_UINT_TYPE * indexes
NATIVE_UINT_TYPE stopIndex