GCC Code Coverage Report

Directory: Os/Generic/Types/
File: MaxHeap.cpp
Date: 2026-09-03 21:15:49
Exec Total Coverage
Lines: 99 107 92.5%
Functions: 11 12 91.7%
Branches: 23 28 82.1%
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 7 MaxHeap::MaxHeap() {
32 7 this->m_capacity = 0;
33 7 this->m_heap = nullptr;
34 7 this->m_size = 0;
35 7 this->m_order = 0;
36 7 }
37
38 7 MaxHeap::~MaxHeap() {
39 7 this->m_heap = nullptr;
40 7 }
41
42 7 void MaxHeap::create(FwSizeType capacity, Fw::ByteArray heap_allocation) {
43 7 FW_ASSERT(this->m_heap == nullptr);
44 7 FW_ASSERT((heap_allocation.size / sizeof(Node)) >= capacity, static_cast<FwAssertArgType>(capacity),
45 static_cast<FwAssertArgType>(heap_allocation.size));
46 7 FW_ASSERT(heap_allocation.bytes != nullptr);
47 // Loop bounds will overflow if capacity set to the max allowable value
48 7 FW_ASSERT(capacity < std::numeric_limits<FwSizeType>::max());
49 7 this->m_heap = Fw::arrayPlacementNew<Node>(heap_allocation, capacity);
50 7 this->m_capacity = capacity;
51 7 }
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 34 bool MaxHeap::push(FwQueuePriorityType value, FwSizeType id) {
66 // If the queue is full, return false:
67
2/2
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 30 times.
 34 if (this->isFull()) {
68 4 return false;
69 }
70
71 // Heap indexes:
72 FwSizeType parent;
73 30 FwSizeType index = this->m_size;
74
75 // Max loop bounds for bit flip protection:
76 30 const FwSizeType maxIter = this->m_size + 1;
77 30 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 30 FwSizeType i = 0;
82
3/4
✓ Branch 0 taken 53 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 32 times.
✓ Branch 3 taken 21 times.
 53 for (i = 0; (i < maxIter) && (index != 0); i++) {
83 // Get the parent index:
84 32 parent = PARENT(index);
85 // The parent index should ALWAYS be less than the
86 // current index. Let's verify that.
87 32 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
2/2
✓ Branch 3 taken 9 times.
✓ Branch 4 taken 23 times.
 32 if (value <= this->m_heap[parent].value) {
92 9 break;
93 }
94 // Swap the parent and child:
95 23 this->m_heap[index] = this->m_heap[parent];
96 23 index = parent;
97 }
98
99 // Check for programming errors or bit flips:
100 30 FW_ASSERT(i < maxIter, static_cast<FwAssertArgType>(i), static_cast<FwAssertArgType>(maxIter));
101 30 FW_ASSERT(index <= this->m_size, static_cast<FwAssertArgType>(index));
102
103 // Set the values of the new element:
104 30 this->m_heap[index].value = value;
105 30 this->m_heap[index].order = m_order;
106 30 this->m_heap[index].id = id;
107
108 30 ++this->m_size;
109 30 ++this->m_order;
110 30 return true;
111 }
112
113 35 bool MaxHeap::pop(FwQueuePriorityType& value, FwSizeType& id) {
114 // If there is nothing in the heap then
115 // return false:
116
2/2
✓ Branch 2 taken 5 times.
✓ Branch 3 taken 30 times.
 35 if (this->isEmpty()) {
117 5 return false;
118 }
119 30 FW_ASSERT(this->m_heap != nullptr);
120
121 // Set the return values to the top (max) of
122 // the heap:
123 30 value = this->m_heap[0].value;
124 30 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 30 FwSizeType index = this->m_size - 1;
131 30 this->m_heap[0] = this->m_heap[index];
132 30 --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 30 this->heapify();
138 30 return true;
139 }
140
141 // Is the heap full:
142 34 bool MaxHeap::isFull() {
143 34 return (this->m_size == this->m_capacity);
144 }
145
146 // Is the heap empty:
147 35 bool MaxHeap::isEmpty() {
148 35 return (this->m_size == 0);
149 }
150
151 // Get the current size of the heap:
152 60 FwSizeType MaxHeap::getSize() const {
153 60 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 30 void MaxHeap::heapify() {
161 30 FwSizeType index = 0;
162 FwSizeType left;
163 FwSizeType right;
164 FwSizeType largest;
165
166 // Max loop bounds for bit flip protection:
167 30 const FwSizeType maxIter = this->m_size + 1;
168 30 FwSizeType i = 0;
169
170
2/4
✓ Branch 0 taken 45 times.
✗ Branch 1 not taken.
✓ Branch 4 taken 45 times.
✗ Branch 5 not taken.
 45 for (i = 0; (i < maxIter) && (index <= this->m_size); i++) {
171 // Get the children indexes for this node:
172 45 left = LCHILD(index);
173 45 right = RCHILD(index);
174 45 FW_ASSERT(left > index, static_cast<FwAssertArgType>(left), static_cast<FwAssertArgType>(index));
175 45 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
2/2
✓ Branch 2 taken 22 times.
✓ Branch 3 taken 23 times.
 45 if (left >= this->m_size) {
181 22 break;
182 }
183
184 // Initialize the largest node to the current
185 // node:
186 23 largest = index;
187
188 // Which one is larger, the current node or
189 // the left node?:
190 23 largest = this->max(left, largest);
191
192 // Make sure the right node exists before checking it:
193
2/2
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 11 times.
 23 if (right < this->m_size) {
194 // Which one is larger, the current largest
195 // node or the right node?
196 12 largest = this->max(right, largest);
197 }
198
199 // If the largest node is the current node
200 // then we are done heapifying:
201
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 15 times.
 23 if (largest == index) {
202 8 break;
203 }
204
205 // Swap the largest node with the current node:
206 15 this->swap(index, largest);
207
208 // Set the new index to whichever child was larger:
209 15 index = largest;
210 }
211
212 // Check for programming errors or bit flips:
213 30 FW_ASSERT(i < maxIter, static_cast<FwAssertArgType>(i), static_cast<FwAssertArgType>(maxIter));
214 30 FW_ASSERT(index <= this->m_size, static_cast<FwAssertArgType>(index));
215 30 }
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 35 FwSizeType MaxHeap::max(FwSizeType a, FwSizeType b) {
220 static_assert(not std::numeric_limits<FwSizeType>::is_signed, "FwSizeType must be unsigned");
221 35 FW_ASSERT(a < this->m_size, static_cast<FwAssertArgType>(a), static_cast<FwAssertArgType>(this->m_size));
222 35 FW_ASSERT(b < this->m_size, static_cast<FwAssertArgType>(b), static_cast<FwAssertArgType>(this->m_size));
223
224 // Extract the priorities:
225 35 FwQueuePriorityType aValue = this->m_heap[a].value;
226 35 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
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 27 times.
 35 if (aValue == bValue) {
235 8 FwSizeType aAge = this->m_order - this->m_heap[a].order;
236 8 FwSizeType bAge = this->m_order - this->m_heap[b].order;
237
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 2 times.
 8 if (aAge > bAge) {
238 6 return a;
239 }
240 2 return b;
241 }
242
243 // Which priority is larger?:
244
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 15 times.
 27 if (aValue > bValue) {
245 12 return a;
246 }
247 // B is larger:
248 15 return b;
249 }
250
251 // Swap two nodes in the heap:
252 15 void MaxHeap::swap(FwSizeType a, FwSizeType b) {
253 15 FW_ASSERT(a < this->m_size, static_cast<FwAssertArgType>(a), static_cast<FwAssertArgType>(this->m_size));
254 15 FW_ASSERT(b < this->m_size, static_cast<FwAssertArgType>(b), static_cast<FwAssertArgType>(this->m_size));
255 15 Node temp = this->m_heap[a];
256 15 this->m_heap[a] = this->m_heap[b];
257 15 this->m_heap[b] = temp;
258 15 }
259
260 } // namespace Types
261