CTR Pia  4.11.3
Game Communication Engine
common_OffsetTreeMap.h
1 /*---------------------------------------------------------------------------*
2  Project: Pia
3  File: common_OffsetTreeMap.h
4 
5  Copyright Nintendo. All rights reserved.
6 
7  These coded instructions, statements, and computer programs contain
8  proprietary information of Nintendo of America Inc. and/or Nintendo
9  Company Ltd., and are protected by Federal copyright law. They may
10  not be disclosed to third parties or copied or duplicated in any form,
11  in whole or in part, without the prior written consent of Nintendo.
12  *---------------------------------------------------------------------------*/
13 
14 
15 #pragma once
16 
17 #include <pia/common/common_definitions.h>
18 #include <pia/common/common_TreeMap.h>
19 
20 namespace nn
21 {
22 namespace pia
23 {
24 namespace common
25 {
26 
27 
28 /*!
29 @cond PRIVATE
30 @brief Represents a tree map that maintains a <tt>TreeMapNode</tt> instance for each element member.
31 */
32 template <typename Key_, typename Value_>
33 class OffsetTreeMap : public TreeMap<Key_>
34 {
35 public:
36  typedef Key_ Key;
37  typedef Value_ Value;
38  typedef TreeMapNode<Key> Node;
39 
40 
41 /*!
42 @brief Instantiates the object with default parameters (default constructor).
43 */
44  OffsetTreeMap()
45  : TreeMap<Key>(), m_Offset(-1)
46  {
47  }
48 
49 
50 /*!
51 @brief Sets the offset from the start address of <tt>Value</tt> to the <tt>TreeMapNode</tt> member.
52 @details You must call this function before use.
53 @param[in] offset Specifies the offset.
54 */
55  void InitOffset(s32 offset)
56  {
57  m_Offset = offset;
58  }
59 
60 
61 /*!
62 @brief Deletes all elements.
63 */
64  void Clear()
65  {
66  TreeMap<Key>::ClearNode();
67  }
68 
69 
70 /*!
71 @brief Finds the element that corresponds to the specified key.
72 @param[in] key Specifies the key to find.
73 @return Returns the element that corresponds to the key. Returns <tt>NULL</tt> if it does not exist.
74 */
75  Value* Find(const Key& key) const
76  {
77  return NodeToValueWithNullCheck(TreeMap<Key>::FindNode(key));
78  }
79 
80 
81 /*!
82 @brief Adds an element that corresponds to the specified key.
83 @details If an element with the same key already exists, it is replaced.
84 @param[in] key Specifies the key to add.
85 @param[in] pValue Specifies the element to add.
86 @return Returns the old element if an element was replaced. Otherwise, returns <tt>NULL</tt>.
87 */
88  Value* Insert(const Key& key, Value* pValue)
89  {
90  return NodeToValueWithNullCheck(TreeMap<Key>::InsertNode(key, ValueToNode(pValue)));
91  }
92 
93 
94 /*!
95 @brief Removes the element with the specified key.
96 @details If an element with the specified key does not exist, nothing is erased.
97 @param[in] key Specifies the key to erase.
98 @return Returns the erased element if one was erased. Returns <tt>NULL</tt> if nothing was erased.
99 */
100  Value* Erase(const Key& key)
101  {
102  return NodeToValueWithNullCheck(TreeMap<Key>::EraseNode(key));
103  }
104 
105 
106 /*!
107 @brief Removes the specified element.
108 @details Operations are undefined if anything other than an element of this <tt>TreeMap</tt> is specified.
109 @param[in] pValue Specifies the element to erase.
110 */
111  void Erase(Value* pValue)
112  {
113  EraseNode(ValueToNode(pValue));
114  }
115 
116 
117 /*!
118 @brief Gets the element at the start of the list.
119 @return Returns the element at the start of the list. Returns <tt>NULL</tt> if the list is empty.
120 */
121  Value* Front() const
122  {
123  return NodeToValueWithNullCheck(TreeMap<Key>::FrontNode());
124  }
125 
126 
127 /*!
128 @brief Gets the last element in the list.
129 @return Returns the element at the end of the list.
130 */
131  Value* Back() const
132  {
133  return NodeToValueWithNullCheck(TreeMap<Key>::BackNode());
134  }
135 
136 
137 /*!
138 @brief Gets the element before the specified element.
139 @details Operations are undefined if anything other than an element of this <tt>TreeMap</tt> is specified.
140 @param[in] pValue Specifies the base element.
141 @return Returns the previous element. Returns <tt>NULL</tt> if the first element in the list is specified as the base.
142 */
143  Value* Prev(const Value* pValue) const
144  {
145  return NodeToValueWithNullCheck(ValueToNode(pValue)->Prev());
146  }
147 
148 
149 /*!
150 @brief Gets the element after the specified element.
151 @details Operations are undefined if anything other than an element of this <tt>TreeMap</tt> is specified.
152 @param[in] pValue Specifies the base element.
153 @return Returns the next element. Returns <tt>NULL</tt> if the last element in the list is specified as the base.
154 */
155  Value* Next(const Value* pValue) const
156  {
157  return NodeToValueWithNullCheck(ValueToNode(pValue)->Next());
158  }
159 
160 
161 /*!
162 @brief Determines whether the specified element is included in this <tt>TreeMap</tt>.
163 @param[in] pValue Specifies the element to check for.
164 @return Returns <tt>true</tt> if the element is in this <tt>TreeMap</tt>.
165 */
166  bool IsInclude(const Value* pValue) const
167  {
168  return IsIncludeNode(ValueToNode(pValue));
169  }
170 
171 
172 /*!
173 @brief Represents an iterator.
174 */
175  class Iterator
176  {
177  friend class OffsetTreeMap;
178 
179  private:
180  Iterator(const OffsetTreeMap* pTreeMap, Node* pNode)
181  : m_pTreeMap(pTreeMap), m_pNode(pNode)
182  {
183  m_pValue = m_pTreeMap->NodeToValueWithNullCheck(pNode);
184  }
185 
186  public:
187  Iterator& operator++()
188  {
189  m_pNode = m_pNode->Next();
190  m_pValue = m_pTreeMap->NodeToValueWithNullCheck(m_pNode);
191  return *this;
192  }
193 
194  bool operator==(const Iterator& x) const
195  {
196  return m_pValue == x.m_pValue;
197  }
198  bool operator!=(const Iterator& x) const
199  {
200  return m_pValue != x.m_pValue;
201  }
202 
203  Value& operator*()
204  {
205  return *m_pValue;
206  }
207  Value* operator->()
208  {
209  return m_pValue;
210  }
211 
212  private:
213  const OffsetTreeMap* m_pTreeMap;
214  Value* m_pValue;
215  Node* m_pNode;
216  };
217 
218 
219 /*!
220 @brief Represents a <tt>const</tt> iterator.
221 */
222  class ConstIterator
223  {
224  friend class OffsetTreeMap;
225 
226  private:
227  ConstIterator(const OffsetTreeMap* pTreeMap, const Node* pNode)
228  : m_pTreeMap(pTreeMap), m_pNode(pNode)
229  {
230  m_pValue = m_pTreeMap->NodeToValueWithNullCheck(pNode);
231  }
232 
233  public:
234  ConstIterator& operator++()
235  {
236  m_pNode = m_pNode->Next();
237  m_pValue = m_pTreeMap->NodeToValueWithNullCheck(m_pNode);
238  return *this;
239  }
240 
241  bool operator==(const ConstIterator& x) const
242  {
243  return m_pValue == x.m_pValue;
244  }
245  bool operator!=(const ConstIterator& x) const
246  {
247  return m_pValue != x.m_pValue;
248  }
249 
250  const Value& operator*()
251  {
252  return *m_pValue;
253  }
254  const Value* operator->()
255  {
256  return m_pValue;
257  }
258 
259  private:
260  const OffsetTreeMap* m_pTreeMap;
261  const Value* m_pValue;
262  const Node* m_pNode;
263  };
264 
265 
266 /*!
267 @brief Represents a <tt>robust</tt> iterator
268 @details The iterator remains valid even if the element it points to is removed.
269 The iterator is no longer valid if an element is added or an element it does not point to is removed.
270 */
271  class RobustIterator
272  {
273  friend class OffsetTreeMap;
274 
275  private:
276  RobustIterator(const OffsetTreeMap* pTreeMap, Node* pNode)
277  : m_pTreeMap(pTreeMap)
278  {
279  m_pValue = m_pTreeMap->NodeToValueWithNullCheck(pNode);
280  m_pNextNode = (pNode != NULL) ? pNode->Next() : NULL;
281  }
282 
283  public:
284  RobustIterator& operator++()
285  {
286  if (m_pNextNode != NULL)
287  {
288  m_pValue = m_pTreeMap->NodeToValue(m_pNextNode);
289  m_pNextNode = m_pNextNode->Next();
290  }
291  else
292  {
293  m_pValue = NULL;
294  }
295  return *this;
296  }
297 
298  bool operator==(const RobustIterator& x) const
299  {
300  return m_pValue == x.m_pValue;
301  }
302  bool operator!=(const RobustIterator& x) const
303  {
304  return m_pValue != x.m_pValue;
305  }
306 
307  Value& operator*()
308  {
309  return *m_pValue;
310  }
311  Value* operator->()
312  {
313  return m_pValue;
314  }
315 
316  private:
317  const OffsetTreeMap* m_pTreeMap;
318  Value* m_pValue;
319  Node* m_pNextNode;
320  };
321 
322 
323 /*!
324 @brief Gets an <tt>Iterator</tt> object pointing to the element at the start of the list.
325 
326 @return Returns an <tt>Iterator</tt> object pointing to the element at the start of the list.
327 */
328  Iterator Begin() const
329  {
330  return Iterator(this, TreeMap<Key>::FrontNode());
331  }
332 
333 
334 /*!
335 @brief Gets an <tt>Iterator</tt> object pointing to the element after the last element in the list.
336 
337 @return Returns an <tt>Iterator</tt> object pointing to the element after the last element in the list.
338 */
339  Iterator End() const
340  {
341  return Iterator(this, NULL);
342  }
343 
344 
345 /*!
346 @brief Gets an <tt>Iterator</tt> object pointing to the element with the smallest key that is equal to or greater than the specified key.
347 
348 @return Returns an <tt>Iterator</tt> object pointing to the element with the smallest key that is equal to or greater than the specified key.
349 */
350  Iterator LowerBound(const Key& key) const
351  {
352  return Iterator(this, TreeMap<Key>::LowerBoundNode(key));
353  }
354 
355 
356 /*!
357 @brief Gets a <tt>ConstIterator</tt> object pointing to the element at the start of the list.
358 
359 @return Returns a <tt>ConstIterator</tt> object pointing to the element at the start of the list.
360 */
361  ConstIterator ConstBegin() const
362  {
363  return ConstIterator(this, TreeMap<Key>::FrontNode());
364  }
365 
366 
367 /*!
368 @brief Gets a <tt>ConstIterator</tt> object pointing to the element after the last element in the list.
369 
370 @return Returns a <tt>ConstIterator</tt> object pointing to the element after the last element in the list.
371 */
372  ConstIterator ConstEnd() const
373  {
374  return ConstIterator(this, NULL);
375  }
376 
377 
378 /*!
379 @brief Gets a <tt>ConstIterator</tt> object pointing to the element with the smallest key that is equal to or greater than the specified key.
380 
381 @return Returns a <tt>ConstIterator</tt> object pointing to the element with the smallest key that is equal to or greater than the specified key.
382 */
383  ConstIterator ConstLowerBound(const Key& key) const
384  {
385  return ConstIterator(this, TreeMap<Key>::LowerBoundNode(key));
386  }
387 
388 
389 /*!
390 @brief Gets a <tt>RobustIterator</tt> object pointing to the element at the start of the list.
391 
392 @return Returns a <tt>RobustIterator</tt> object pointing to the element at the start of the list.
393 */
394  RobustIterator RobustBegin() const
395  {
396  return RobustIterator(this, TreeMap<Key>::FrontNode());
397  }
398 
399 
400 /*!
401 @brief Gets a <tt>RobustIterator</tt> object pointing to the element after the last element in the list.
402 
403 @return Returns a <tt>RobustIterator</tt> object pointing to the element after the last element in the list.
404 */
405  RobustIterator RobustEnd() const
406  {
407  return RobustIterator(this, NULL);
408  }
409 
410 
411 /*!
412 @brief Gets a <tt>RobustIterator</tt> object pointing to the element with the smallest key that is equal to or greater than the specified key.
413 
414 @return Returns a <tt>RobustIterator</tt> object pointing to the element with the smallest key that is equal to or greater than the specified key.
415 */
416  RobustIterator RobustLowerBound(const Key& key) const
417  {
418  return RobustIterator(this, TreeMap<Key>::LowerBoundNode(key));
419  }
420 
421 private:
422  s32 m_Offset;
423 
424  Node* ValueToNode(const Value* pObj) const
425  {
426  return reinterpret_cast<Node*>((reinterpret_cast<u32>(pObj)) + m_Offset);
427  }
428 
429  Value* NodeToValue(const Node* pNode) const
430  {
431  return reinterpret_cast<Value*>((reinterpret_cast<u32>(pNode)) - m_Offset);
432  }
433 
434  Value* NodeToValueWithNullCheck(const Node* pNode) const
435  {
436  if (pNode)
437  return reinterpret_cast<Value*>((reinterpret_cast<u32>(pNode)) - m_Offset);
438  else
439  return NULL;
440  }
441 };
442 //! @endcond
443 }
444 }
445 } // end of namespace nn::pia::common
Definition: assert.h:115