GCC Code Coverage Report

Line	Branch	Exec	Source
1			// ======================================================================
2			// \title MaxHeap.cpp
3			// \author dinkel
4			// \brief An implementation of a stable max heap data structure. Items
5			// popped off the heap are guaranteed to be in order of decreasing
6			// "value" (max removed first). Items of equal "value" will be
7			// popped off in FIFO order. The performance of both push and pop
8			// is O(log(n)).
9			//
10			// \copyright
11			// Copyright 2009-2015, by the California Institute of Technology.
12			// ALL RIGHTS RESERVED. United States Government Sponsorship
13			// acknowledged.
14			//
15			// ======================================================================
16
17			#include "Os/Generic/Types/MaxHeap.hpp"
18			#include <Fw/FPrimeBasicTypes.hpp>
19			#include <Fw/Logger/Logger.hpp>
20			#include <cstdio>
21			#include "Fw/LanguageHelpers.hpp"
22			#include "Fw/Types/Assert.hpp"
23
24			// Macros for traversing the heap:
25			#define LCHILD(x) (2 * x + 1)
26			#define RCHILD(x) (2 * x + 2)
27			#define PARENT(x) ((x - 1) / 2)
28
29			namespace Types {
30
31		✗	MaxHeap::MaxHeap() {
32		✗	this->m_capacity = 0;
33		✗	this->m_heap = nullptr;
34		✗	this->m_size = 0;
35		✗	this->m_order = 0;
36		✗	}
37
38		✗	MaxHeap::~MaxHeap() {
39		✗	this->m_heap = nullptr;
40		✗	}
41
42		✗	void MaxHeap::create(FwSizeType capacity, Fw::ByteArray heap_allocation) {
43		✗	FW_ASSERT(this->m_heap == nullptr);
44		✗	FW_ASSERT((heap_allocation.size / sizeof(Node)) >= capacity, static_cast<FwAssertArgType>(capacity),
45			static_cast<FwAssertArgType>(heap_allocation.size));
46		✗	FW_ASSERT(heap_allocation.bytes != nullptr);
47			// Loop bounds will overflow if capacity set to the max allowable value
48		✗	FW_ASSERT(capacity < std::numeric_limits<FwSizeType>::max());
49		✗	this->m_heap = Fw::arrayPlacementNew<Node>(heap_allocation, capacity);
50		✗	this->m_capacity = capacity;
51		✗	}
52
53		✗	void MaxHeap::teardown() {
54			// Only destroy the heap if it is still allocated
55		✗	if (this->m_heap != nullptr) {
56		✗	Fw::arrayPlacementDestruct<Node>(this->m_heap, this->m_capacity);
57			}
58			// Reset the capacity and heap so that the provider of memory
59		✗	this->m_capacity = 0;
60		✗	this->m_heap = nullptr;
61		✗	this->m_size = 0;
62		✗	this->m_order = 0;
63		✗	}
64
65		✗	bool MaxHeap::push(FwQueuePriorityType value, FwSizeType id) {
66			// If the queue is full, return false:
67		✗	if (this->isFull()) {
68		✗	return false;
69			}
70
71			// Heap indexes:
72			FwSizeType parent;
73		✗	FwSizeType index = this->m_size;
74
75			// Max loop bounds for bit flip protection:
76		✗	const FwSizeType maxIter = this->m_size + 1;
77		✗	FW_ASSERT(maxIter != 0);
78			// Start at the bottom of the heap and work our ways
79			// upwards until we find a parent that has a value
80			// greater than ours.
81		✗	FwSizeType i = 0;
82		✗	for (i = 0; (i < maxIter) && (index != 0); i++) {
83			// Get the parent index:
84		✗	parent = PARENT(index);
85			// The parent index should ALWAYS be less than the
86			// current index. Let's verify that.
87		✗	FW_ASSERT(parent < index, static_cast<FwAssertArgType>(parent), static_cast<FwAssertArgType>(index));
88			// If the current value is less than the parent,
89			// then the current index is in the correct place,
90			// so break out of the loop:
91		✗	if (value <= this->m_heap[parent].value) {
92		✗	break;
93			}
94			// Swap the parent and child:
95		✗	this->m_heap[index] = this->m_heap[parent];
96		✗	index = parent;
97			}
98
99			// Check for programming errors or bit flips:
100		✗	FW_ASSERT(i < maxIter, static_cast<FwAssertArgType>(i), static_cast<FwAssertArgType>(maxIter));
101		✗	FW_ASSERT(index <= this->m_size, static_cast<FwAssertArgType>(index));
102
103			// Set the values of the new element:
104		✗	this->m_heap[index].value = value;
105		✗	this->m_heap[index].order = m_order;
106		✗	this->m_heap[index].id = id;
107
108		✗	++this->m_size;
109		✗	++this->m_order;
110		✗	return true;
111			}
112
113		✗	bool MaxHeap::pop(FwQueuePriorityType& value, FwSizeType& id) {
114			// If there is nothing in the heap then
115			// return false:
116		✗	if (this->isEmpty()) {
117		✗	return false;
118			}
119		✗	FW_ASSERT(this->m_heap != nullptr);
120
121			// Set the return values to the top (max) of
122			// the heap:
123		✗	value = this->m_heap[0].value;
124		✗	id = this->m_heap[0].id;
125
126			// Now place the last element on the heap in
127			// the root position, and resize the heap.
128			// This will put the smallest value in the
129			// heap on the top, violating the heap property.
130		✗	FwSizeType index = this->m_size - 1;
131		✗	this->m_heap[0] = this->m_heap[index];
132		✗	--this->m_size;
133
134			// Now that the heap property is violated, we
135			// need to reorganize the heap to restore it's
136			// heapy-ness.
137		✗	this->heapify();
138		✗	return true;
139			}
140
141			// Is the heap full:
142		✗	bool MaxHeap::isFull() {
143		✗	return (this->m_size == this->m_capacity);
144			}
145
146			// Is the heap empty:
147		✗	bool MaxHeap::isEmpty() {
148		✗	return (this->m_size == 0);
149			}
150
151			// Get the current size of the heap:
152		✗	FwSizeType MaxHeap::getSize() const {
153		✗	return this->m_size;
154			}
155
156			// A non-recursive heapify method.
157			// Note: This method had an additional property, such that
158			// items pushed of the same priority will be popped in FIFO
159			// order.
160		✗	void MaxHeap::heapify() {
161		✗	FwSizeType index = 0;
162			FwSizeType left;
163			FwSizeType right;
164			FwSizeType largest;
165
166			// Max loop bounds for bit flip protection:
167		✗	const FwSizeType maxIter = this->m_size + 1;
168		✗	FwSizeType i = 0;
169
170		✗	for (i = 0; (i < maxIter) && (index <= this->m_size); i++) {
171			// Get the children indexes for this node:
172		✗	left = LCHILD(index);
173		✗	right = RCHILD(index);
174		✗	FW_ASSERT(left > index, static_cast<FwAssertArgType>(left), static_cast<FwAssertArgType>(index));
175		✗	FW_ASSERT(right > left, static_cast<FwAssertArgType>(right), static_cast<FwAssertArgType>(left));
176
177			// If the left node is bigger than the heap
178			// size, we have reached the end of the heap
179			// so we can stop:
180		✗	if (left >= this->m_size) {
181		✗	break;
182			}
183
184			// Initialize the largest node to the current
185			// node:
186		✗	largest = index;
187
188			// Which one is larger, the current node or
189			// the left node?:
190		✗	largest = this->max(left, largest);
191
192			// Make sure the right node exists before checking it:
193		✗	if (right < this->m_size) {
194			// Which one is larger, the current largest
195			// node or the right node?
196		✗	largest = this->max(right, largest);
197			}
198
199			// If the largest node is the current node
200			// then we are done heapifying:
201		✗	if (largest == index) {
202		✗	break;
203			}
204
205			// Swap the largest node with the current node:
206		✗	this->swap(index, largest);
207
208			// Set the new index to whichever child was larger:
209		✗	index = largest;
210			}
211
212			// Check for programming errors or bit flips:
213		✗	FW_ASSERT(i < maxIter, static_cast<FwAssertArgType>(i), static_cast<FwAssertArgType>(maxIter));
214		✗	FW_ASSERT(index <= this->m_size, static_cast<FwAssertArgType>(index));
215		✗	}
216
217			// Return the maximum priority index between two nodes. If their
218			// priorities are equal, return the oldest to keep the heap stable
219		✗	FwSizeType MaxHeap::max(FwSizeType a, FwSizeType b) {
220			static_assert(not std::numeric_limits<FwSizeType>::is_signed, "FwSizeType must be unsigned");
221		✗	FW_ASSERT(a < this->m_size, static_cast<FwAssertArgType>(a), static_cast<FwAssertArgType>(this->m_size));
222		✗	FW_ASSERT(b < this->m_size, static_cast<FwAssertArgType>(b), static_cast<FwAssertArgType>(this->m_size));
223
224			// Extract the priorities:
225		✗	FwQueuePriorityType aValue = this->m_heap[a].value;
226		✗	FwQueuePriorityType bValue = this->m_heap[b].value;
227
228			// If the priorities are equal, the "larger" one will be
229			// the "older" one as determined by order pushed on to the
230			// heap. Using this secondary ordering technique makes the
231			// heap stable (ie. FIFO for equal priority elements).
232			// Note: We check this first, because it is the most common
233			// case. Let's save as many ticks as we can...
234		✗	if (aValue == bValue) {
235		✗	FwSizeType aAge = this->m_order - this->m_heap[a].order;
236		✗	FwSizeType bAge = this->m_order - this->m_heap[b].order;
237		✗	if (aAge > bAge) {
238		✗	return a;
239			}
240		✗	return b;
241			}
242
243			// Which priority is larger?:
244		✗	if (aValue > bValue) {
245		✗	return a;
246			}
247			// B is larger:
248		✗	return b;
249			}
250
251			// Swap two nodes in the heap:
252		✗	void MaxHeap::swap(FwSizeType a, FwSizeType b) {
253		✗	FW_ASSERT(a < this->m_size, static_cast<FwAssertArgType>(a), static_cast<FwAssertArgType>(this->m_size));
254		✗	FW_ASSERT(b < this->m_size, static_cast<FwAssertArgType>(b), static_cast<FwAssertArgType>(this->m_size));
255		✗	Node temp = this->m_heap[a];
256		✗	this->m_heap[a] = this->m_heap[b];
257		✗	this->m_heap[b] = temp;
258		✗	}
259
260			} // namespace Types
261