F´ Flight Software - C/C++ Documentation  NASA-v2.1.0
A framework for building embedded system applications to NASA flight quality standards.
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 <string.h>
20 #include <stdio.h>
21 
22 // This is a priority queue implementation implemented using a stable max heap.
23 // Elements pushed onto the queue will be popped off in priority order.
24 // Elements of the same priority will be popped off in FIFO order.
25 namespace Os {
26 
28  // Queue handler:
30 
31  struct PriorityQueue {
33  U8* data;
37  };
38 
40  // Helper functions:
42 
44  NATIVE_UINT_TYPE* indexes = pQueue->indexes;
45 
46  // Get an available index from the index pool:
47  NATIVE_UINT_TYPE index = indexes[pQueue->startIndex % depth];
48  ++pQueue->startIndex;
49  NATIVE_UINT_TYPE diff = pQueue->stopIndex - pQueue->startIndex;
50  FW_ASSERT(diff <= depth, diff, depth, pQueue->stopIndex, pQueue->startIndex);
51  return index;
52  }
53 
55  NATIVE_UINT_TYPE* indexes = pQueue->indexes;
56 
57  // Return the index back to the index pool:
58  indexes[pQueue->stopIndex % depth] = index;
59  ++pQueue->stopIndex;
60  NATIVE_UINT_TYPE diff = pQueue->stopIndex - pQueue->startIndex;
61  FW_ASSERT(diff <= depth, diff, depth, pQueue->stopIndex, pQueue->startIndex);
62  }
63 
65  // Class functions:
67 
68  bool BufferQueue::initialize(NATIVE_UINT_TYPE depth, NATIVE_UINT_TYPE msgSize) {
69  // Create the priority queue data structure on the heap:
70  MaxHeap* heap = new MaxHeap;
71  if (NULL == heap) {
72  return false;
73  }
74  if( !heap->create(depth) ) {
75  return false;
76  }
77  U8* data = new U8[depth*(sizeof(msgSize) + msgSize)];
78  if (NULL == data) {
79  return false;
80  }
81  NATIVE_UINT_TYPE* indexes = new NATIVE_UINT_TYPE[depth];
82  if (NULL == indexes) {
83  return false;
84  }
85  for(NATIVE_UINT_TYPE ii = 0; ii < depth; ++ii) {
86  indexes[ii] = getBufferIndex(ii);
87  }
88  PriorityQueue* priorityQueue = new PriorityQueue;
89  if (NULL == priorityQueue) {
90  return false;
91  }
92  priorityQueue->heap = heap;
93  priorityQueue->data = data;
94  priorityQueue->indexes = indexes;
95  priorityQueue->startIndex = 0;
96  priorityQueue->stopIndex = depth;
97  this->queue = priorityQueue;
98  return true;
99  }
100 
101  void BufferQueue::finalize() {
102  PriorityQueue* pQueue = static_cast<PriorityQueue*>(this->queue);
103  if (NULL != pQueue)
104  {
105  MaxHeap* heap = pQueue->heap;
106  if (NULL != heap) {
107  delete heap;
108  }
109  U8* data = pQueue->data;
110  if (NULL != data) {
111  delete [] data;
112  }
113  NATIVE_UINT_TYPE* indexes = pQueue->indexes;
114  if (NULL != indexes)
115  {
116  delete [] indexes;
117  }
118  delete pQueue;
119  }
120  this->queue = NULL;
121  }
122 
123  bool BufferQueue::enqueue(const U8* buffer, NATIVE_UINT_TYPE size, NATIVE_INT_TYPE priority) {
124 
125  // Extract queue handle variables:
126  PriorityQueue* pQueue = static_cast<PriorityQueue*>(this->queue);
127  MaxHeap* heap = pQueue->heap;
128  U8* data = pQueue->data;
129 
130  // Get an available data index:
131  NATIVE_UINT_TYPE index = checkoutIndex(pQueue, this->depth);
132 
133  // Insert the data into the heap:
134  bool ret = heap->push(priority, index);
135  FW_ASSERT(ret, ret);
136 
137  // Store the buffer to the queue:
138  this->enqueueBuffer(buffer, size, data, index);
139 
140  return true;
141  }
142 
143  bool BufferQueue::dequeue(U8* buffer, NATIVE_UINT_TYPE& size, NATIVE_INT_TYPE &priority) {
144 
145  // Extract queue handle variables:
146  PriorityQueue* pQueue = static_cast<PriorityQueue*>(this->queue);
147  MaxHeap* heap = pQueue->heap;
148  U8* data = pQueue->data;
149 
150  // Get the highest priority data from the heap:
151  NATIVE_UINT_TYPE index = 0;
152  bool ret = heap->pop(priority, index);
153  FW_ASSERT(ret, ret);
154 
155  ret = this->dequeueBuffer(buffer, size, data, index);
156  if(!ret) {
157  // The dequeue failed, so push the popped
158  // value back on the heap.
159  ret = heap->push(priority, index);
160  FW_ASSERT(ret, ret);
161  return false;
162  }
163 
164  // Return the index to the available indexes:
165  returnIndex(pQueue, this->depth, index);
166 
167  return true;
168  }
169 }
Os
Definition: File.cpp:7
Os::PriorityQueue::data
U8 * data
Definition: PriorityBufferQueue.cpp:33
Os::checkoutIndex
NATIVE_UINT_TYPE checkoutIndex(PriorityQueue *pQueue, NATIVE_UINT_TYPE depth)
Definition: PriorityBufferQueue.cpp:43
U8
uint8_t U8
8-bit unsigned integer
Definition: BasicTypes.hpp:76
Os::PriorityQueue::heap
MaxHeap * heap
Definition: PriorityBufferQueue.cpp:32
Os::PriorityQueue::indexes
NATIVE_UINT_TYPE * indexes
Definition: PriorityBufferQueue.cpp:34
Os::PriorityQueue
Definition: PriorityBufferQueue.cpp:31
Assert.hpp
Os::MaxHeap
A stable max heap data structure.
Definition: MaxHeap.hpp:27
Os::returnIndex
void returnIndex(PriorityQueue *pQueue, NATIVE_UINT_TYPE depth, NATIVE_UINT_TYPE index)
Definition: PriorityBufferQueue.cpp:54
Os::PriorityQueue::startIndex
NATIVE_UINT_TYPE startIndex
Definition: PriorityBufferQueue.cpp:35
BufferQueue.hpp
NATIVE_UINT_TYPE
unsigned int NATIVE_UINT_TYPE
native unsigned integer type declaration
Definition: BasicTypes.hpp:30
FW_ASSERT
#define FW_ASSERT(...)
Definition: Assert.hpp:9
MaxHeap.hpp
NATIVE_INT_TYPE
int NATIVE_INT_TYPE
native integer type declaration
Definition: BasicTypes.hpp:29
NULL
#define NULL
NULL.
Definition: BasicTypes.hpp:100
Os::PriorityQueue::stopIndex
NATIVE_UINT_TYPE stopIndex
Definition: PriorityBufferQueue.cpp:36