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