GCC Code Coverage Report

Directory: ./
File: Types/MaxHeap.cpp
Date: 2026-09-03 22:13:11
Exec Total Coverage
Lines: 100 107 93.5%
Functions: 12 12 100.0%
Branches: 18 28 64.3%
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 28 MaxHeap::MaxHeap() {
32 28 this->m_capacity = 0;
33 28 this->m_heap = nullptr;
34 28 this->m_size = 0;
35 28 this->m_order = 0;
36 28 }
37
38 28 MaxHeap::~MaxHeap() {
39 28 this->m_heap = nullptr;
40 28 }
41
42 28 void MaxHeap::create(FwSizeType capacity, Fw::ByteArray heap_allocation) {
43 28 FW_ASSERT(this->m_heap == nullptr);
44 28 FW_ASSERT((heap_allocation.size / sizeof(Node)) >= capacity, static_cast<FwAssertArgType>(capacity),
45 static_cast<FwAssertArgType>(heap_allocation.size));
46 28 FW_ASSERT(heap_allocation.bytes != nullptr);
47 // Loop bounds will overflow if capacity set to the max allowable value
48 28 FW_ASSERT(capacity < std::numeric_limits<FwSizeType>::max());
49 28 this->m_heap = Fw::arrayPlacementNew<Node>(heap_allocation, capacity);
50 28 this->m_capacity = capacity;
51 28 }
52
53 28 void MaxHeap::teardown() {
54 // Only destroy the heap if it is still allocated
55
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 if (this->m_heap != nullptr) {
56 28 Fw::arrayPlacementDestruct<Node>(this->m_heap, this->m_capacity);
57 }
58 // Reset the capacity and heap so that the provider of memory
59 28 this->m_capacity = 0;
60 28 this->m_heap = nullptr;
61 28 this->m_size = 0;
62 28 this->m_order = 0;
63 28 }
64
65 6945 bool MaxHeap::push(FwQueuePriorityType value, FwSizeType id) {
66 // If the queue is full, return false:
67
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 6944 times.
 6945 if (this->isFull()) {
68 ✗ return false;
69 }
70
71 // Heap indexes:
72 FwSizeType parent;
73 6944 FwSizeType index = this->m_size;
74
75 // Max loop bounds for bit flip protection:
76 6944 const FwSizeType maxIter = this->m_size + 1;
77 6944 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 6944 FwSizeType i = 0;
82
3/4
✓ Branch 0 taken 6944 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1348 times.
✓ Branch 3 taken 5596 times.
 6944 for (i = 0; (i < maxIter) && (index != 0); i++) {
83 // Get the parent index:
84 1348 parent = PARENT(index);
85 // The parent index should ALWAYS be less than the
86 // current index. Let's verify that.
87 1348 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
1/2
✓ Branch 0 taken 1348 times.
✗ Branch 1 not taken.
 1348 if (value <= this->m_heap[parent].value) {
92 1348 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 6944 FW_ASSERT(i < maxIter, static_cast<FwAssertArgType>(i), static_cast<FwAssertArgType>(maxIter));
101 6944 FW_ASSERT(index <= this->m_size, static_cast<FwAssertArgType>(index));
102
103 // Set the values of the new element:
104 6937 this->m_heap[index].value = value;
105 6937 this->m_heap[index].order = m_order;
106 6937 this->m_heap[index].id = id;
107
108 6937 ++this->m_size;
109 6937 ++this->m_order;
110 6937 return true;
111 }
112
113 6920 bool MaxHeap::pop(FwQueuePriorityType& value, FwSizeType& id) {
114 // If there is nothing in the heap then
115 // return false:
116
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 6922 times.
 6920 if (this->isEmpty()) {
117 ✗ return false;
118 }
119 6922 FW_ASSERT(this->m_heap != nullptr);
120
121 // Set the return values to the top (max) of
122 // the heap:
123 6922 value = this->m_heap[0].value;
124 6922 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 6922 FwSizeType index = this->m_size - 1;
131 6922 this->m_heap[0] = this->m_heap[index];
132 6922 --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 6922 this->heapify();
138 6908 return true;
139 }
140
141 // Is the heap full:
142 20795 bool MaxHeap::isFull() {
143 20795 return (this->m_size == this->m_capacity);
144 }
145
146 // Is the heap empty:
147 26621 bool MaxHeap::isEmpty() {
148 26621 return (this->m_size == 0);
149 }
150
151 // Get the current size of the heap:
152 6923 FwSizeType MaxHeap::getSize() const {
153 6923 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 6906 void MaxHeap::heapify() {
161 6906 FwSizeType index = 0;
162 FwSizeType left;
163 FwSizeType right;
164 FwSizeType largest;
165
166 // Max loop bounds for bit flip protection:
167 6906 const FwSizeType maxIter = this->m_size + 1;
168 6906 FwSizeType i = 0;
169
170
2/4
✓ Branch 0 taken 8488 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 8488 times.
✗ Branch 3 not taken.
 8488 for (i = 0; (i < maxIter) && (index <= this->m_size); i++) {
171 // Get the children indexes for this node:
172 8488 left = LCHILD(index);
173 8488 right = RCHILD(index);
174 8488 FW_ASSERT(left > index, static_cast<FwAssertArgType>(left), static_cast<FwAssertArgType>(index));
175 8488 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 0 taken 6782 times.
✓ Branch 1 taken 1708 times.
 8490 if (left >= this->m_size) {
181 6782 break;
182 }
183
184 // Initialize the largest node to the current
185 // node:
186 1708 largest = index;
187
188 // Which one is larger, the current node or
189 // the left node?:
190 1708 largest = this->max(left, largest);
191
192 // Make sure the right node exists before checking it:
193
2/2
✓ Branch 0 taken 1489 times.
✓ Branch 1 taken 219 times.
 1708 if (right < this->m_size) {
194 // Which one is larger, the current largest
195 // node or the right node?
196 1489 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 126 times.
✓ Branch 1 taken 1582 times.
 1708 if (largest == index) {
202 126 break;
203 }
204
205 // Swap the largest node with the current node:
206 1582 this->swap(index, largest);
207
208 // Set the new index to whichever child was larger:
209 1582 index = largest;
210 }
211
212 // Check for programming errors or bit flips:
213 6908 FW_ASSERT(i < maxIter, static_cast<FwAssertArgType>(i), static_cast<FwAssertArgType>(maxIter));
214 6908 FW_ASSERT(index <= this->m_size, static_cast<FwAssertArgType>(index));
215 6908 }
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 3197 FwSizeType MaxHeap::max(FwSizeType a, FwSizeType b) {
220 static_assert(not std::numeric_limits<FwSizeType>::is_signed, "FwSizeType must be unsigned");
221 3197 FW_ASSERT(a < this->m_size, static_cast<FwAssertArgType>(a), static_cast<FwAssertArgType>(this->m_size));
222 3197 FW_ASSERT(b < this->m_size, static_cast<FwAssertArgType>(b), static_cast<FwAssertArgType>(this->m_size));
223
224 // Extract the priorities:
225 3197 FwQueuePriorityType aValue = this->m_heap[a].value;
226 3197 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
1/2
✓ Branch 0 taken 3197 times.
✗ Branch 1 not taken.
 3197 if (aValue == bValue) {
235 3197 FwSizeType aAge = this->m_order - this->m_heap[a].order;
236 3197 FwSizeType bAge = this->m_order - this->m_heap[b].order;
237
2/2
✓ Branch 0 taken 1999 times.
✓ Branch 1 taken 1198 times.
 3197 if (aAge > bAge) {
238 1999 return a;
239 }
240 1198 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 1582 void MaxHeap::swap(FwSizeType a, FwSizeType b) {
253 1582 FW_ASSERT(a < this->m_size, static_cast<FwAssertArgType>(a), static_cast<FwAssertArgType>(this->m_size));
254 1582 FW_ASSERT(b < this->m_size, static_cast<FwAssertArgType>(b), static_cast<FwAssertArgType>(this->m_size));
255 1582 Node temp = this->m_heap[a];
256 1582 this->m_heap[a] = this->m_heap[b];
257 1582 this->m_heap[b] = temp;
258 1582 }
259
260 } // namespace Types
261