F´ Flight Software - C/C++ Documentation  NASA-v1.6.0
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.
26 namespace Os {
27 
29  // Queue handler:
31 
32  struct PriorityQueue {
34  U8* data;
38  };
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->queue = priorityQueue;
106  return true;
107  }
108 
109  void BufferQueue::finalize() {
110  PriorityQueue* pQueue = static_cast<PriorityQueue*>(this->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->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->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->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->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->depth, index);
174 
175  return true;
176  }
177 }
Os
Definition: File.cpp:7
Os::PriorityQueue::data
U8 * data
Definition: PriorityBufferQueue.cpp:34
Os::checkoutIndex
NATIVE_UINT_TYPE checkoutIndex(PriorityQueue *pQueue, NATIVE_UINT_TYPE depth)
Definition: PriorityBufferQueue.cpp:44
U8
uint8_t U8
8-bit unsigned integer
Definition: BasicTypes.hpp:73
NATIVE_UINT_TYPE
unsigned int NATIVE_UINT_TYPE
native unsigned integer type declaration
Definition: BasicTypes.hpp:28
Os::PriorityQueue::heap
MaxHeap * heap
Definition: PriorityBufferQueue.cpp:33
Os::PriorityQueue::indexes
NATIVE_UINT_TYPE * indexes
Definition: PriorityBufferQueue.cpp:35
Os::PriorityQueue
Definition: PriorityBufferQueue.cpp:32
Os::MaxHeap
A stable max heap data structure.
Definition: MaxHeap.hpp:27
NATIVE_INT_TYPE
int NATIVE_INT_TYPE
native integer type declaration
Definition: BasicTypes.hpp:27
Os::returnIndex
void returnIndex(PriorityQueue *pQueue, NATIVE_UINT_TYPE depth, NATIVE_UINT_TYPE index)
Definition: PriorityBufferQueue.cpp:55
Os::PriorityQueue::startIndex
NATIVE_UINT_TYPE startIndex
Definition: PriorityBufferQueue.cpp:36
BufferQueue.hpp
FW_ASSERT
#define FW_ASSERT(...)
Definition: Assert.hpp:9
MaxHeap.hpp
Os::PriorityQueue::stopIndex
NATIVE_UINT_TYPE stopIndex
Definition: PriorityBufferQueue.cpp:37