MySQL  8.0.19
Source Code Documentation
intrusive_list_iterator.h
Go to the documentation of this file.
1 #ifndef SQL_INTRUSIVE_LIST_ITERATOR_H_
2 #define SQL_INTRUSIVE_LIST_ITERATOR_H_
3 /* Copyright (c) 2019, Oracle and/or its affiliates. All rights reserved.
4 
5  This program is free software; you can redistribute it and/or modify
6  it under the terms of the GNU General Public License as published by
7  the Free Software Foundation; version 2 of the License.
8 
9  This program is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  GNU General Public License for more details.
13 
14  You should have received a copy of the GNU General Public License
15  along with this program; if not, write to the Free Software Foundation,
16  51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA */
17 
18 /**
19  @file intrusive_list_iterator.h
20 
21  Iterator utilities for working with intrusive pointers.
22 */
23 
24 #include "my_dbug.h"
25 
26 /**
27  An iterator that follows a 'next' pointer with an accessor function.
28  @tparam T The type of the object holding the intrusive list.
29  @tparam GetNextPointer The accessor function, returning a pointer to the
30  next object in the list.
31 
32  @note Due to the nature of intrusive 'next' pointers it's not possible to
33  free an intrusive pointee while iterating over an intrusive list with
34  the pre-increment operator, as the enhanced for-loop does, e.g.
35 
36  ```
37  for(auto elem : elems)
38  delete *elem;
39  ```
40 
41  Will cause a core dump. However, the following is possible:
42 
43  ```
44  auto it = container.begin();
45  while(it != container.end()) delete *(it++);
46  ```
47 */
48 template <typename T, T *(*GetNextPointer)(const T *)>
50  public:
51  using value_type = T *;
52  /**
53  Constructs an iterator.
54 
55  @param start The object that the iterator will start iterating
56  from.
57  */
59 
60  /// Constructs a past-the-end iterator.
62 
64  DBUG_ASSERT(m_current != nullptr);
65  m_current = GetNextPointer(m_current);
66  return *this;
67  }
68 
70  auto pre_increment(*this);
71  ++(*this);
72  return pre_increment;
73  }
74 
75  T *operator*() const { return m_current; }
76 
77  bool operator==(const NextFunctionIterator &other) const {
78  return m_current == other.m_current;
79  }
80 
81  bool operator!=(const NextFunctionIterator &other) const {
82  return !((*this) == other);
83  }
84 
85  private:
87 };
88 
89 /**
90  Helper template for the case when the 'next' member can be used directly,
91  typically when it's public and the class definition is known.
92 */
93 template <typename T, T *T::*Member>
94 T *GetMember(const T *t) {
95  return t->*Member;
96 }
97 
98 /**
99  An iterator that follows the 'next' pointer in an intrusive list.
100  Conforms to the ForwardIterator named requirement.
101 
102  @tparam T The type of the object holding the intrusive list.
103  @tparam NextPointer The intrusive list's "next" pointer member.
104 */
105 template <typename T, T *T::*NextPointer>
107  : public NextFunctionIterator<T, GetMember<T, NextPointer>> {
108  public:
109  IntrusiveListIterator() = default;
110  explicit IntrusiveListIterator(T *t)
111  : NextFunctionIterator<T, GetMember<T, NextPointer>>(t) {}
112 };
113 
114 /**
115  Adds a collection interface on top of an iterator. The iterator must support a
116  default constructor constructing a past-the-end iterator.
117 
118  @tparam IteratorType The iterator's class.
119 */
120 template <typename IteratorType>
122  public:
123  using Type = typename IteratorType::value_type;
124  explicit IteratorContainer(Type first) : m_first(first) {}
125 
126  IteratorType begin() { return IteratorType(m_first); }
127  IteratorType end() { return IteratorType(); }
128 
129  private:
131 };
132 
133 template <typename T>
134 using GetNextPointerFunction = T *(*)(const T *);
135 
136 /**
137  Convenience alias for instantiating a container directly from the accessor
138  function.
139 */
140 template <typename T, GetNextPointerFunction<T> Fn>
142 
143 /*
144  We inline the NextFunctionContainer definition below. We want to define this
145  alias as NextFunctionContainer<T, &GetMember<T, NextPointer>>, but VS2019
146  fails with C2996. It is likely a compiler bug.
147 */
148 template <typename T, T *T::*NextPointer>
151 
152 #endif // SQL_INTRUSIVE_LIST_ITERATOR_H_
NextFunctionIterator< T, GetMember< T, NextPointer > >::value_type
T * value_type
Definition: intrusive_list_iterator.h:51
IteratorContainer::Type
typename IteratorType::value_type Type
Definition: intrusive_list_iterator.h:123
NextFunctionIterator::operator!=
bool operator!=(const NextFunctionIterator &other) const
Definition: intrusive_list_iterator.h:81
my_dbug.h
IteratorContainer::IteratorContainer
IteratorContainer(Type first)
Definition: intrusive_list_iterator.h:124
IteratorContainer::m_first
Type m_first
Definition: intrusive_list_iterator.h:130
IteratorContainer
Adds a collection interface on top of an iterator.
Definition: intrusive_list_iterator.h:121
NextFunctionIterator::m_current
T * m_current
Definition: intrusive_list_iterator.h:86
IteratorContainer::begin
IteratorType begin()
Definition: intrusive_list_iterator.h:126
IntrusiveListIterator::IntrusiveListIterator
IntrusiveListIterator(T *t)
Definition: intrusive_list_iterator.h:110
NextFunctionIterator::operator*
T * operator*() const
Definition: intrusive_list_iterator.h:75
IteratorContainer::end
IteratorType end()
Definition: intrusive_list_iterator.h:127
NextFunctionIterator::operator++
NextFunctionIterator & operator++()
Definition: intrusive_list_iterator.h:63
GetNextPointerFunction
T *(*)(const T *) GetNextPointerFunction
Definition: intrusive_list_iterator.h:134
NextFunctionIterator::NextFunctionIterator
NextFunctionIterator(T *start)
Constructs an iterator.
Definition: intrusive_list_iterator.h:58
IntrusiveListIterator
An iterator that follows the 'next' pointer in an intrusive list.
Definition: intrusive_list_iterator.h:106
Vt100::value_type
uint16_t value_type
Definition: vt100.h:182
NextFunctionIterator
An iterator that follows a 'next' pointer with an accessor function.
Definition: intrusive_list_iterator.h:49
NextFunctionIterator::operator==
bool operator==(const NextFunctionIterator &other) const
Definition: intrusive_list_iterator.h:77
DBUG_ASSERT
#define DBUG_ASSERT(A)
Definition: my_dbug.h:197
GetMember
T * GetMember(const T *t)
Helper template for the case when the 'next' member can be used directly, typically when it's public ...
Definition: intrusive_list_iterator.h:94
start
static void start(PluginFuncEnv *env)
Definition: http_server_plugin.cc:572
NextFunctionIterator::NextFunctionIterator
NextFunctionIterator()
Constructs a past-the-end iterator.
Definition: intrusive_list_iterator.h:61
IntrusiveListIterator::IntrusiveListIterator
IntrusiveListIterator()=default
NextFunctionIterator::operator++
NextFunctionIterator operator++(int)
Definition: intrusive_list_iterator.h:69