Main Page Class List Class Members

NvBlastFixedPriorityQueue.h
Go to the documentation of this file.
1 // This code contains NVIDIA Confidential Information and is disclosed to you
2 // under a form of NVIDIA software license agreement provided separately to you.
3 //
4 // Notice
5 // NVIDIA Corporation and its licensors retain all intellectual property and
6 // proprietary rights in and to this software and related documentation and
7 // any modifications thereto. Any use, reproduction, disclosure, or
8 // distribution of this software and related documentation without an express
9 // license agreement from NVIDIA Corporation is strictly prohibited.
10 //
11 // ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
12 // NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
13 // THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
14 // MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
15 //
16 // Information and code furnished is believed to be accurate and reliable.
17 // However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
18 // information or for any infringement of patents or other rights of third parties that may
19 // result from its use. No license is granted by implication or otherwise under any patent
20 // or patent rights of NVIDIA Corporation. Details are subject to change without notice.
21 // This code supersedes and replaces all information previously supplied.
22 // NVIDIA Corporation products are not authorized for use as critical
23 // components in life support devices or systems without express written approval of
24 // NVIDIA Corporation.
25 //
26 // Copyright (c) 2016-2020 NVIDIA Corporation. All rights reserved.
27
28
29 #ifndef NVBLASTFIXEDPRIORITYQUEUE_H
30 #define NVBLASTFIXEDPRIORITYQUEUE_H
31
32 #include "NvBlastAssert.h"
33 #include "NvBlastMemory.h"
34
35 namespace Nv
36 {
37
38 namespace Blast
39 {
40
62 template <typename A>
63 struct Less
64 {
65 bool operator()(const A& a, const A& b) const
66 {
67 return a < b;
68 }
69 };
70
71
72 template<class Element, class Comparator = Less<Element> >
73 class FixedPriorityQueue : protected Comparator // inherit so that stateless comparators take no space
74 {
75 public:
76 FixedPriorityQueue(const Comparator& less = Comparator()) : Comparator(less), mHeapSize(0)
77 {
78 }
79
80 ~FixedPriorityQueue()
81 {
82 }
83
84 static size_t requiredMemorySize(uint32_t capacity)
85 {
86 return align16(sizeof(FixedPriorityQueue<Element, Comparator>)) + align16(capacity * sizeof(Element));
87 }
88
90 const Element top() const
91 {
92 return data()[0];
93 }
94
96 Element top()
97 {
98 return data()[0];
99 }
100
102 bool empty() const
103 {
104 return (mHeapSize == 0);
105 }
106
108 void clear()
109 {
110 mHeapSize = 0;
111 }
112
114 void push(const Element& value)
115 {
116 uint32_t newIndex;
117 uint32_t parentIndex = parent(mHeapSize);
118
119 for (newIndex = mHeapSize; newIndex > 0 && compare(value, data()[parentIndex]); newIndex = parentIndex, parentIndex= parent(newIndex))
120 {
121 data()[ newIndex ] = data()[parentIndex];
122 }
123 data()[newIndex] = value;
124 mHeapSize++;
125 NVBLAST_ASSERT(valid());
126 }
127
129 Element pop()
130 {
131 NVBLAST_ASSERT(mHeapSize > 0);
132 uint32_t i, child;
133 //try to avoid LHS
134 uint32_t tempHs = mHeapSize-1;
135 mHeapSize = tempHs;
136 Element min = data()[0];
137 Element last = data()[tempHs];
138
139 for (i = 0; (child = left(i)) < tempHs; i = child)
140 {
141 /* Find highest priority child */
142 const uint32_t rightChild = child + 1;
143
144 child += ((rightChild < tempHs) & compare((data()[rightChild]), (data()[child]))) ? 1 : 0;
145
146 if(compare(last, data()[child]))
147 break;
148
149 data()[i] = data()[child];
150 }
151 data()[ i ] = last;
152
153 NVBLAST_ASSERT(valid());
154 return min;
155 }
156
158 bool valid() const
159 {
160 const Element& min = data()[0];
161 for(uint32_t i=1; i<mHeapSize; ++i)
162 {
163 if(compare(data()[i], min))
164 return false;
165 }
166
167 return true;
168 }
169
171 uint32_t size() const
172 {
173 return mHeapSize;
174 }
175
176 private:
177 uint32_t mHeapSize;
178
179 NV_FORCE_INLINE Element* data()
180 {
181 return (Element*)((char*)this + sizeof(FixedPriorityQueue<Element, Comparator>));
182 }
183
184 NV_FORCE_INLINE Element* data() const
185 {
186 return (Element*)((char*)this + sizeof(FixedPriorityQueue<Element, Comparator>));
187 }
188
189 bool compare(const Element& a, const Element& b) const
190 {
191 return Comparator::operator()(a,b);
192 }
193
194 static uint32_t left(uint32_t nodeIndex)
195 {
196 return (nodeIndex << 1) + 1;
197 }
198
199 static uint32_t parent(uint32_t nodeIndex)
200 {
201 return (nodeIndex - 1) >> 1;
202 }
203
204 FixedPriorityQueue<Element, Comparator>& operator = (const FixedPriorityQueue<Element, Comparator>);
205 };
206
207 } // namespace Blast
208 } // namespace Nv
209
210 #endif // ifndef NVBLASTFIXEDPRIORITYQUEUE_H
Nv::Blast::FixedPriorityQueue::top
Element top()
Get the element with the highest priority.
Definition: NvBlastFixedPriorityQueue.h:96
Nv::Blast::FixedPriorityQueue::push
void push(const Element &value)
Insert a new element into the priority queue. Only valid when size() is less than Capacity...
Definition: NvBlastFixedPriorityQueue.h:114
Nv::Blast::FixedPriorityQueue
Definition: NvBlastFixedPriorityQueue.h:73
Nv::Blast::FixedPriorityQueue::clear
void clear()
Empty the priority queue.
Definition: NvBlastFixedPriorityQueue.h:108
Nv::Blast::FixedPriorityQueue::pop
Element pop()
Delete the highest priority element. Only valid when non-empty.
Definition: NvBlastFixedPriorityQueue.h:129
Nv::Blast::FixedPriorityQueue::valid
bool valid() const
Make sure the priority queue sort all elements correctly.
Definition: NvBlastFixedPriorityQueue.h:158
NVBLAST_ASSERT
#define NVBLAST_ASSERT(exp)
Definition: NvBlastAssert.h:37
Nv::Blast::FixedPriorityQueue::requiredMemorySize
static size_t requiredMemorySize(uint32_t capacity)
Definition: NvBlastFixedPriorityQueue.h:84
Nv::Blast::FixedPriorityQueue::top
const Element top() const
Get the element with the highest priority.
Definition: NvBlastFixedPriorityQueue.h:90
NvBlastMemory.h
Nv::Blast::Less::operator()
bool operator()(const A &a, const A &b) const
Definition: NvBlastFixedPriorityQueue.h:65
Nv::Blast::FixedPriorityQueue::~FixedPriorityQueue
~FixedPriorityQueue()
Definition: NvBlastFixedPriorityQueue.h:80
Nv::Blast::FixedPriorityQueue::empty
bool empty() const
Check to whether the priority queue is empty.
Definition: NvBlastFixedPriorityQueue.h:102
Nv::Blast::FixedPriorityQueue::size
uint32_t size() const
Return number of elements in the priority queue.
Definition: NvBlastFixedPriorityQueue.h:171
Nv::Blast::align16
NV_INLINE T align16(T value)
Definition: NvBlastMemory.h:46
Nv::Blast::FixedPriorityQueue::FixedPriorityQueue
FixedPriorityQueue(const Comparator &less=Comparator())
Definition: NvBlastFixedPriorityQueue.h:76
Nv
Definition: NvBlastArray.h:37
Nv::Blast::Less
Definition: NvBlastFixedPriorityQueue.h:63
NvBlastAssert.h
NV_FORCE_INLINE
#define NV_FORCE_INLINE
Definition: NvPreprocessor.h:365