GCC Code Coverage Report

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