gwnavruntime/containers/sharedpoollist.h Source File

sharedpoollist.h
Go to the documentation of this file.
1 /*
2 * Copyright 2016 Autodesk, Inc. All rights reserved.
3 * Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
4 * or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
5 */
6 
7 #pragma once
8 
12 
13 namespace Kaim
14 {
15 
17 template <typename T>
19 {
20  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
22 
23 private:
24  typedef Pool<SPListNode<T> > NodePool;
25  typedef typename NodePool::Key NodeKey;
26 
27 public:
28  SPListNode() : m_prev(nullptr), m_next(nullptr) {}
29  explicit SPListNode(const T& data) : m_prev(nullptr), m_next(nullptr), m_data(data) {}
30 
31 public: // internal
32  SPListNode* m_prev;
33  SPListNode* m_next;
34  NodeKey m_nodeKey;
35  T m_data;
36 };
37 
38 
40 template <typename T>
42 {
43  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
44 
45 public:
46  // ---------------------------------- Public typedef ----------------------------------
47 
48  typedef SPListNode<T> Node;
49 
50 
51  // ------------------------------ Functions -----------------------------
52 
53  SPL_Iterator() : m_node(nullptr) {}
54  explicit SPL_Iterator(Node* listNode) : m_node(listNode) {}
55  SPL_Iterator(const SPL_Iterator& rhs) : m_node(rhs.m_node) {}
56 
57  KY_INLINE const SPL_Iterator& operator=(const SPL_Iterator& rhs) { m_node = rhs.m_node; return *this; }
58 
59  KY_INLINE bool operator==(const SPL_Iterator& rhs) const { return m_node == rhs.m_node; }
60  KY_INLINE bool operator!=(const SPL_Iterator& rhs) const { return m_node != rhs.m_node; }
61 
62  KY_INLINE SPL_Iterator& operator++() { m_node = m_node->m_next; return *this; }
63  KY_INLINE SPL_Iterator& operator--() { m_node = m_node->m_prev; return *this; }
64 
65  KY_INLINE SPL_Iterator operator++(int) { SPL_Iterator old = *this; m_node = m_node->m_next; return old; }
66  KY_INLINE SPL_Iterator operator--(int) { SPL_Iterator old = *this; m_node = m_node->m_prev; return old; }
67 
68  KY_INLINE T& operator*() const { return m_node->m_data; }
69  KY_INLINE T* operator->() const { return &m_node->m_data; }
70 
71  KY_INLINE SPL_Iterator GetNext() const { return SPL_Iterator(m_node->m_next); }
72  KY_INLINE SPL_Iterator GetPrev() const { return SPL_Iterator(m_node->m_prev); }
73 
74  KY_INLINE bool IsNull() const { return m_node == nullptr; }
75  KY_INLINE bool IsNotNull() const { return m_node != nullptr; }
76 
77 public: // internal
78  Node* m_node;
79 };
80 
82 template <typename T>
84 {
85  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
86 
87 public:
88  // ---------------------------------- Public typedef ----------------------------------
89  typedef SPListNode<T> Node;
90 
91  // ------------------------------ Functions -----------------------------
92 
93  SPL_ConstIterator() : m_node(nullptr) {}
94  SPL_ConstIterator(const SPL_Iterator<T>& it) : m_node(it.m_node) {}
95  SPL_ConstIterator(const SPL_ConstIterator& it) : m_node(it.m_node) {}
96  explicit SPL_ConstIterator(const Node* listNode) : m_node(listNode) {}
97 
98  KY_INLINE const SPL_ConstIterator& operator=(const SPL_ConstIterator& rhs) { m_node = rhs.m_node; return *this; }
99 
100  KY_INLINE bool operator==(const SPL_ConstIterator& rhs) const { return m_node == rhs.m_node; }
101  KY_INLINE bool operator!=(const SPL_ConstIterator& rhs) const { return m_node != rhs.m_node; }
102 
103  KY_INLINE SPL_ConstIterator& operator++() { m_node = m_node->m_next; return *this; }
104  KY_INLINE SPL_ConstIterator& operator--() { m_node = m_node->m_prev; return *this; }
105 
106  KY_INLINE SPL_ConstIterator operator++(int) { SPL_ConstIterator old = *this; m_node = m_node->m_next; return old; }
107  KY_INLINE SPL_ConstIterator operator--(int) { SPL_ConstIterator old = *this; m_node = m_node->m_prev; return old; }
108 
109  KY_INLINE const T& operator*() const { return m_node->m_data; }
110  KY_INLINE const T* operator->() const { return &m_node->m_data; }
111 
112  KY_INLINE SPL_ConstIterator GetNext() const { return SPL_ConstIterator(m_node->m_next); }
113  KY_INLINE SPL_ConstIterator GetPrev() const { return SPL_ConstIterator(m_node->m_prev); }
114 
115  KY_INLINE bool IsNull() const { return m_node == nullptr; }
116  KY_INLINE bool IsNotNull() const { return m_node != nullptr; }
117 
118 public: // internal
119  const Node* m_node;
120 };
121 
143 
146 template <typename T>
148 {
149  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
151 
152 public:
153  // ---------------------------------- Public typedefs ----------------------------------
154 
155  typedef SPListNode<T> Node;
156  typedef SPL_Iterator<T> Iterator;
158  typedef Pool<SPListNode<T> > NodePool;
159  typedef typename NodePool::Key NodeKey;
160 
161 public:
162  // ---------------------------------- Main API Functions ----------------------------------
163 
164  explicit SharedPoolList(NodePool* nodePool = nullptr) : m_nodePool(nodePool), m_count(0)
165  { m_root.m_next = m_root.m_prev = RootAsNode(); }
166 
167  void SetNodePool(NodePool* nodePool) { m_nodePool = nodePool; }
168 
169  ~SharedPoolList() { Clear(); }
170 
171  void Clear();
172 
173  KyUInt32 GetCount() const { return m_count; }
174 
175 
176  // ---------------------------------- Bounds ----------------------------------
177 
178  ConstIterator GetFirst() const { return ConstIterator(m_root.m_next); }
179  ConstIterator GetLast() const { return ConstIterator(m_root.m_prev); }
180  Iterator GetFirst() { return Iterator(m_root.m_next); }
181  Iterator GetLast () { return Iterator(m_root.m_prev); }
182 
183  ConstIterator Begin() const { return ConstIterator(m_root.m_next); }
184  ConstIterator End() const { return ConstIterator(RootAsNode()); }
185  Iterator Begin() { return Iterator(m_root.m_next); }
186  Iterator End() { return Iterator(RootAsNode()); }
187 
188 
189 
190  // ---------------------------------- Utility Functions ----------------------------------
191 
192  // Determine if list is empty (i.e.) points to itself.
193  // Go through void* access to avoid issues with strict-aliasing optimizing out the
194  // access after RemoveNode(), etc.
195  bool IsEmpty() const { return m_root.m_next == RootAsNode(); }
196 
197  bool IsFirst(ConstIterator it) const { return it.m_node == m_root.m_next; }
198  bool IsFirst(Iterator it) const { return it.m_node == m_root.m_next; }
199 
200  bool IsLast (ConstIterator it) const { return it.m_node == m_root.m_prev; }
201  bool IsLast (Iterator it) const { return it.m_node == m_root.m_prev; }
202 
203  bool IsNull (ConstIterator it) const { return it.m_node == RootAsNode(); }
204  bool IsNull (Iterator it) const { return it.m_node == RootAsNode(); }
205 
206  bool IsValid(ConstIterator it) const { return it.m_node != RootAsNode(); }
207  bool IsValid(Iterator it) const { return it.m_node != RootAsNode(); }
208 
209  ConstIterator Find(const T& data) const;
210  Iterator Find(const T& data);
211 
212 
213  // ---------------------------------- Node Insertion ----------------------------------
214 
215  Iterator InsertBefore(const T& data, Iterator nextNodeIt) { Node* newNode = NewNode(data); InsertNodeBefore(newNode, nextNodeIt.m_node); return Iterator(newNode); }
216  Iterator InsertAfter(Iterator prevNodeIt, const T& data) { Node* newNode = NewNode(data); InsertNodeAfter(prevNodeIt.m_node, newNode); return Iterator(newNode); }
217 
218  Iterator InsertBefore(Iterator nextNodeIt) { Node* newNode = NewNode(); InsertNodeBefore(newNode, nextNodeIt.m_node); return Iterator(newNode); }
219  Iterator InsertAfter(Iterator prevNodeIt) { Node* newNode = NewNode(); InsertNodeAfter(prevNodeIt.m_node, newNode); return Iterator(newNode); }
220 
221  Iterator PushFront(const T& data) { Node* newNode = NewNode(data); InsertNodeBefore(newNode, m_root.m_next); return Iterator(newNode); }
222  Iterator PushBack(const T& data) { Node* newNode = NewNode(data); InsertNodeAfter(m_root.m_prev, newNode); return Iterator(newNode); }
223 
224  Iterator PushFront() { Node* newNode = NewNode(); InsertNodeBefore(newNode, m_root.m_next); return Iterator(newNode); }
225  Iterator PushBack() { Node* newNode = NewNode(); InsertNodeAfter(m_root.m_prev, newNode); return Iterator(newNode); }
226 
227 
228  // ---------------------------------- Node Removal ----------------------------------
229 
230  Iterator Erase(Iterator it);
231 
232  Iterator RemoveFirstOccurrence(Iterator begin, const T& data);
233 
234  KyUInt32 RemoveAllOccurrences(const T& data);
235 
236  template<class Predicate>
237  KyUInt32 Remove_If(Predicate predicate)
238  {
239  KyUInt32 count = 0;
240  for (Iterator it = Begin(); it != End(); )
241  {
242  if (!predicate(*it))
243  ++it;
244  else
245  {
246  it = Erase(it);
247  ++count;
248  }
249  }
250  return count;
251  }
252 
253 private:
254  void InsertNodeBefore(Node* newNode, Node* nextNode) { InsertNodeBetween(nextNode->m_prev, newNode, nextNode); }
255  void InsertNodeAfter(Node* prevNode, Node* newNode) { InsertNodeBetween(prevNode, newNode, prevNode->m_next); }
256  void InsertNodeBetween(Node* prevNode, Node* newNode, Node* nextNode);
257  Node* NewNode(const T& data); // return NewNode with m_data=data, m_nodeKey=newone, m_prev=m_next=0
258  Node* NewNode(); // return NewNode with m_data=T() , m_nodeKey=newone, m_prev=m_next=0
259  void RemoveNode(Node* node) { node->m_prev->m_next = node->m_next; node->m_next->m_prev = node->m_prev; }
260  Node* RootAsNode() { return &m_root; }
261  const Node* RootAsNode() const { return &m_root; }
262 
263 private:
264  NodePool* m_nodePool;
265  Node m_root;
266  KyUInt32 m_count;
267 };
268 
269 
270 template <typename T>
272 {
273  NodeKey key;
274  Node* node = nullptr;
275  m_nodePool->New_CompactKeyAndPtr(key, node);
276 
277  node->m_data = data;
278  node->m_nodeKey = key;
279 
280  ++m_count;
281  return node;
282 }
283 
284 
285 template <typename T>
286 typename SharedPoolList<T>::Node* SharedPoolList<T>::NewNode()
287 {
288  NodeKey nodeKey = m_nodePool->New_CompactKey();
289  Node* node = &m_nodePool->Get(nodeKey);
290  // TODO one call to m_nodePool that returns {nodeKey, node}
291  node->m_nodeKey = nodeKey;
292  ++m_count;
293  return node;
294 }
295 
296 template <typename T>
297 void SharedPoolList<T>::InsertNodeBetween(Node* prevNode, Node* newNode, Node* nextNode)
298 {
299  prevNode->m_next = newNode;
300  newNode->m_prev = prevNode;
301 
302  newNode->m_next = nextNode;
303  nextNode->m_prev = newNode;
304 }
305 
306 
307 template <typename T>
308 typename SharedPoolList<T>::Iterator SharedPoolList<T>::Erase(Iterator it)
309 {
310  Node* node = it.m_node;
311  Node* nextNode = node->m_next;
312  RemoveNode(node);
313  m_nodePool->Delete(node->m_nodeKey);
314  --m_count;
315  return Iterator(nextNode);
316 }
317 
318 
319 template <typename T>
320 void SharedPoolList<T>::Clear()
321 {
322  for (Iterator it = Begin(); it != End(); ++it)
323  m_nodePool->Delete(it.m_node->m_nodeKey);
324 
325  m_count = 0;
326  m_root.m_next = m_root.m_prev = RootAsNode();
327 }
328 
329 
330 template <typename T>
331 typename SharedPoolList<T>::ConstIterator SharedPoolList<T>::Find(const T& data) const
332 {
333  for (ConstIterator it = Begin(); it != End(); ++it)
334  {
335  if (*it == data)
336  return it;
337  }
338  return End();
339 }
340 
341 template <typename T>
342 typename SharedPoolList<T>::Iterator SharedPoolList<T>::Find(const T& data)
343 {
344  for (Iterator it = Begin(); it != End(); ++it)
345  {
346  if (*it == data)
347  return it;
348  }
349  return End();
350 }
351 
352 
353 template <typename T>
354 typename SharedPoolList<T>::Iterator SharedPoolList<T>::RemoveFirstOccurrence(Iterator begin, const T& data)
355 {
356  Iterator it = begin;
357  for (; it != End(); ++it)
358  {
359  if (*it == data)
360  return Erase(it);
361  }
362  return it;
363 }
364 
365 
366 template <typename T>
367 KyUInt32 SharedPoolList<T>::RemoveAllOccurrences(const T& data)
368 {
369  KyUInt32 count = 0;
370  for (Iterator it = Begin(); it != End(); )
371  {
372  if (*it != data)
373  ++it;
374  else
375  {
376  it = Erase(it);
377  ++count;
378  }
379  }
380  return count;
381 }
382 
383 } // namespace Kaim
384 
385 
std::uint32_t KyUInt32
uint32_t
Definition: types.h:29
Const iterator on SharedPoolList nodes (SPL stands for SharedPoolList).
Definition: sharedpoollist.h:83
SharedPoolList represents an ordered list of elements of a single type, drawn as needed from a pre-al...
Definition: sharedpoollist.h:147
#define KY_CLASS_WITHOUT_COPY(ClassName)
Define to forbid copy constructor and copy assignment.
Definition: types.h:196
#define KY_DEFINE_NEW_DELETE_OPERATORS(MemStat)
This macro defines new and delete operators.
Definition: memory.h:132
This is the list node used in SharedPoolList implementation (SP stands for SharedPool).
Definition: sharedpoollist.h:18
The Autodesk Navigation namespace.
Definition: gamekitcrowddispersion.cpp:17
Iterator on SharedPoolList nodes (SPL stands for SharedPoolList).
Definition: sharedpoollist.h:41