GCC Code Coverage Report

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