Main Page Class List Class Members

NvBlastDLink.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 NVBLASTDLINK_H
30 #define NVBLASTDLINK_H
31
32
33 #include "NvBlastAssert.h"
34 #include "NvBlastIndexFns.h"
35
36
37 namespace Nv
38 {
39 namespace Blast
40 {
41
42 template<typename IndexType>
43 struct IndexDLink
44 {
45 IndexType m_adj[2];
46 };
47
48
49 template<typename IndexType>
50 class IndexDList
51 {
52 public:
53 void initLinksSolitary(IndexDLink<IndexType>* links, IndexType linkCount)
54 {
55 for (IndexType i = 0; i < linkCount; ++i)
56 {
57 links[i].m_adj[0] = invalidIndex<IndexType>();
58 links[i].m_adj[1] = invalidIndex<IndexType>();
59 }
60 }
61
62 void initLinksChain(IndexDLink<IndexType>* links, IndexType linkCount)
63 {
64 if (linkCount > 0)
65 {
66 links[0].m_adj[0] = invalidIndex<IndexType>();
67 for (IndexType i = 1; i < linkCount; ++i)
68 {
69 links[i - 1].m_adj[1] = i;
70 links[i].m_adj[0] = i - 1;
71 }
72 links[linkCount - 1].m_adj[1] = invalidIndex<IndexType>();
73 }
74 }
75
76 IndexType getAdj(IndexDLink<IndexType>* links, IndexType linkIndex, int which)
77 {
78 return links[linkIndex].m_adj[which & 1];
79 }
80
81 void remove(IndexDLink<IndexType>* links, IndexType linkIndex)
82 {
83 IndexDLink<IndexType>& link = links[linkIndex];
84 const IndexType adj0 = link.m_adj[0];
85 const IndexType adj1 = link.m_adj[1];
86 if (!isInvalidIndex(adj1))
87 {
88 links[adj1].m_adj[0] = adj0;
89 link.m_adj[1] = invalidIndex<IndexType>();
90 }
91 if (!isInvalidIndex(adj0))
92 {
93 links[adj0].m_adj[1] = adj1;
94 link.m_adj[0] = invalidIndex<IndexType>();
95 }
96 }
97
98 bool isSolitary(IndexDLink<IndexType>* links, IndexType linkIndex)
99 {
100 const IndexDLink<IndexType>& link = links[linkIndex];
101 return isInvalidIndex(link.m_adj[0]) && isInvalidIndex(link.m_adj[1]);
102 }
103
104 void insertListHead(IndexType& listHead, IndexDLink<IndexType>* links, IndexType linkIndex)
105 {
106 NVBLAST_ASSERT(!isInvalidIndex(linkIndex));
107 if (!isInvalidIndex(listHead))
108 {
109 links[listHead].m_adj[0] = linkIndex;
110 }
111 links[linkIndex].m_adj[1] = listHead;
112 listHead = linkIndex;
113 }
114
115 IndexType removeListHead(IndexType& listHead, IndexDLink<IndexType>* links)
116 {
117 const IndexType linkIndex = listHead;
118 if (!isInvalidIndex(linkIndex))
119 {
120 listHead = links[linkIndex].m_adj[1];
121 if (!isInvalidIndex(listHead))
122 {
123 links[listHead].m_adj[0] = invalidIndex<IndexType>();
124 }
125 links[linkIndex].m_adj[1] = invalidIndex<IndexType>();
126 }
127 return linkIndex;
128 }
129
130 void removeFromList(IndexType& listHead, IndexDLink<IndexType>* links, IndexType linkIndex)
131 {
132 NVBLAST_ASSERT(!isInvalidIndex(linkIndex));
133 if (listHead == linkIndex)
134 {
135 listHead = links[linkIndex].m_adj[1];
136 }
137 remove(links, linkIndex);
138 }
139 };
140
141
142 struct DLink
143 {
144 DLink() : m_prev(nullptr), m_next(nullptr) {}
145
146 DLink* getPrev() const
147 {
148 return m_prev;
149 }
150
151 DLink* getNext() const
152 {
153 return m_next;
154 }
155
156 private:
157 DLink* m_prev;
158 DLink* m_next;
159
160 friend class DList;
161 };
162
163
164 class DList
165 {
166 public:
167 DList() : m_head(nullptr), m_tail(nullptr) {}
168
169 bool isEmpty() const
170 {
171 NVBLAST_ASSERT((m_head == nullptr) == (m_tail == nullptr));
172 return m_head == nullptr;
173 }
174
175 bool isSolitary(const DLink& link) const
176 {
177 return link.m_prev == nullptr && link.m_next == nullptr && m_head != &link;
178 }
179
180 DLink* getHead() const
181 {
182 return m_head;
183 }
184
185 DLink* getTail() const
186 {
187 return m_tail;
188 }
189
190 bool insertHead(DLink& link)
191 {
192 NVBLAST_ASSERT(isSolitary(link));
193 if (!isSolitary(link))
194 {
195 return false;
196 }
197
198 link.m_next = m_head;
199 if (m_head != nullptr)
200 {
201 m_head->m_prev = &link;
202 }
203 m_head = &link;
204 if (m_tail == nullptr)
205 {
206 m_tail = &link;
207 }
208
209 return true;
210 }
211
212 bool insertTail(DLink& link)
213 {
214 NVBLAST_ASSERT(isSolitary(link));
215 if (!isSolitary(link))
216 {
217 return false;
218 }
219
220 link.m_prev = m_tail;
221 if (m_tail != nullptr)
222 {
223 m_tail->m_next = &link;
224 }
225 m_tail = &link;
226 if (m_head == nullptr)
227 {
228 m_head = &link;
229 }
230
231 return true;
232 }
233
234 void remove(DLink& link)
235 {
236 if (link.m_prev != nullptr)
237 {
238 link.m_prev->m_next = link.m_next;
239 }
240 else
241 if (m_head == &link)
242 {
243 m_head = link.m_next;
244 }
245
246 if (link.m_next != nullptr)
247 {
248 link.m_next->m_prev = link.m_prev;
249 }
250 else
251 if (m_tail == &link)
252 {
253 m_tail = link.m_prev;
254 }
255
256 link.m_next = link.m_prev = nullptr;
257 }
258
259 class It
260 {
261 public:
262 enum Direction { Reverse, Forward };
263
264 It(const DList& list, Direction dir = Forward) : m_curr(dir == Forward ? list.getHead() : list.getTail()) {}
265
267 operator bool() const
268 {
269 return m_curr != nullptr;
270 }
271
273 operator const DLink*() const
274 {
275 return m_curr;
276 }
277
279 const DLink* operator ++ ()
280 {
281 return m_curr = m_curr->getNext();
282 }
283
285 const DLink* operator -- ()
286 {
287 return m_curr = m_curr->getPrev();
288 }
289
290 private:
291 const DLink* m_curr;
292 };
293
294 private:
295 DLink* m_head;
296 DLink* m_tail;
297 };
298
299 } // end namespace Blast
300 } // end namespace Nv
301
302
303 #endif // #ifndef NVBLASTDLINK_H
Nv::Blast::DList::DList
DList()
Definition: NvBlastDLink.h:167
Nv::Blast::DList::insertTail
bool insertTail(DLink &link)
Definition: NvBlastDLink.h:212
Nv::Blast::IndexDLink::m_adj
IndexType m_adj[2]
Definition: NvBlastDLink.h:45
Nv::Blast::DLink::getNext
DLink * getNext() const
Definition: NvBlastDLink.h:151
Nv::Blast::DList::It::Reverse
Definition: NvBlastDLink.h:262
Nv::Blast::isInvalidIndex
NV_INLINE bool isInvalidIndex(T index)
Definition: NvBlastIndexFns.h:57
Nv::Blast::DLink
Definition: NvBlastDLink.h:142
Nv::Blast::DLink::getPrev
DLink * getPrev() const
Definition: NvBlastDLink.h:146
NVBLAST_ASSERT
#define NVBLAST_ASSERT(exp)
Definition: NvBlastAssert.h:37
NvBlastIndexFns.h
Nv::Blast::IndexDList::initLinksSolitary
void initLinksSolitary(IndexDLink< IndexType > *links, IndexType linkCount)
Definition: NvBlastDLink.h:53
Nv::Blast::IndexDList::initLinksChain
void initLinksChain(IndexDLink< IndexType > *links, IndexType linkCount)
Definition: NvBlastDLink.h:62
Nv::Blast::DList::isSolitary
bool isSolitary(const DLink &link) const
Definition: NvBlastDLink.h:175
Nv::Blast::IndexDList::isSolitary
bool isSolitary(IndexDLink< IndexType > *links, IndexType linkIndex)
Definition: NvBlastDLink.h:98
Nv::Blast::IndexDList::removeListHead
IndexType removeListHead(IndexType &listHead, IndexDLink< IndexType > *links)
Definition: NvBlastDLink.h:115
Nv::Blast::DList::insertHead
bool insertHead(DLink &link)
Definition: NvBlastDLink.h:190
Nv::Blast::DList::isEmpty
bool isEmpty() const
Definition: NvBlastDLink.h:169
Nv::Blast::IndexDList::getAdj
IndexType getAdj(IndexDLink< IndexType > *links, IndexType linkIndex, int which)
Definition: NvBlastDLink.h:76
Nv::Blast::IndexDList
Definition: NvBlastDLink.h:50
Nv::Blast::DList::It::Direction
Direction
Definition: NvBlastDLink.h:262
Nv::Blast::IndexDList::insertListHead
void insertListHead(IndexType &listHead, IndexDLink< IndexType > *links, IndexType linkIndex)
Definition: NvBlastDLink.h:104
Nv::Blast::DList
Definition: NvBlastDLink.h:164
Nv::Blast::DList::It::It
It(const DList &list, Direction dir=Forward)
Definition: NvBlastDLink.h:264
Nv::Blast::DList::It
Definition: NvBlastDLink.h:259
Nv::Blast::DLink::DLink
DLink()
Definition: NvBlastDLink.h:144
Nv::Blast::IndexDLink
Definition: NvBlastDLink.h:43
Nv::Blast::DList::getHead
DLink * getHead() const
Definition: NvBlastDLink.h:180
Nv
Definition: NvBlastArray.h:37
NvBlastAssert.h
Nv::Blast::IndexDList::removeFromList
void removeFromList(IndexType &listHead, IndexDLink< IndexType > *links, IndexType linkIndex)
Definition: NvBlastDLink.h:130
Nv::Blast::DList::getTail
DLink * getTail() const
Definition: NvBlastDLink.h:185