Line data Source code
1 : /*
2 : *
3 : * Copyright (c) 2024 Project CHIP Authors
4 : *
5 : * Licensed under the Apache License, Version 2.0 (the "License");
6 : * you may not use this file except in compliance with the License.
7 : * You may obtain a copy of the License at
8 : *
9 : * http://www.apache.org/licenses/LICENSE-2.0
10 : *
11 : * Unless required by applicable law or agreed to in writing, software
12 : * distributed under the License is distributed on an "AS IS" BASIS,
13 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 : * See the License for the specific language governing permissions and
15 : * limitations under the License.
16 : */
17 :
18 : #pragma once
19 :
20 : #include <lib/core/CHIPCallback.h>
21 : #include <lib/support/CodeUtils.h>
22 :
23 : #include <utility>
24 :
25 : namespace chip {
26 : namespace Callback {
27 :
28 : namespace detail {
29 : // Internal helper functions
30 : template <size_t Index>
31 : void TaggedDequeueGroup(Cancelable * cancelable);
32 : void EnqueueWithGroup(Cancelable * cancelable, Cancelable *& group, Cancelable * anchor, void (*cancelFn)(Cancelable *));
33 : void LinkGroup(Cancelable * prev, Cancelable * next);
34 : inline Cancelable * ClearCancelable(Cancelable * cancelable);
35 : } // namespace detail
36 :
37 : /**
38 : * A GroupedCallbackList manages a list of Callback objects (see CHIPCallback.h).
39 : * The state of the list is maintained using the prev/next pointers of each Callback.
40 : * Unlike a normal linked list where entries are managed individually, this class
41 : * manages a number of related callbacks as a group, with the callback function types
42 : * given as template parameters.
43 : *
44 : * For example, a `GroupedCallbackList<SuccessFn, FailureFn>` manages groups of a
45 : * `Callback<SuccessFn>` and a `Callback<FailureFn>`.
46 : *
47 : * Groups of callbacks are enqueued and dequeued (or cancelled) as a unit.
48 : * Within a group each callback is optional (i.e. can be null), however attempting
49 : * to enqueue a group where all callbacks are null has no effect.
50 : */
51 : template <typename... T>
52 : class GroupedCallbackList : protected Cancelable
53 : {
54 : public:
55 0 : GroupedCallbackList() = default;
56 0 : ~GroupedCallbackList() { Clear(); }
57 :
58 : GroupedCallbackList(GroupedCallbackList const &) = delete;
59 : GroupedCallbackList & operator=(GroupedCallbackList const &) = delete;
60 :
61 0 : bool IsEmpty() { return mNext == this; }
62 :
63 : /**
64 : * Enqueues the specified group of callbacks, any of which may be null.
65 : */
66 0 : void Enqueue(Callback<T> *... callback) { Enqueue(std::index_sequence_for<T...>{}, callback...); }
67 :
68 : /**
69 : * If the list is non-empty, populates the reference arguments with the first
70 : * group of callbacks and returns true. Returns false if the list is empty.
71 : */
72 0 : bool Peek(Callback<T> *&... callback) const { return Peek(std::index_sequence_for<T...>{}, callback...); }
73 :
74 : /**
75 : * Like Peek(), but additionally removes the first group of callbacks from the list.
76 : */
77 0 : bool Take(Callback<T> *&... callback)
78 : {
79 0 : VerifyOrReturnValue(Peek(callback...), false);
80 0 : mNext->Cancel();
81 0 : return true;
82 : }
83 :
84 : /**
85 : * Moves all elements of the source list into this list, leaving the source list empty.
86 : */
87 0 : void EnqueueTakeAll(GroupedCallbackList & source)
88 : {
89 0 : VerifyOrReturn(!source.IsEmpty() && this != &source);
90 0 : detail::LinkGroup(mPrev, source.mNext);
91 0 : source.mPrev->mNext = this;
92 0 : mPrev = source.mPrev;
93 :
94 0 : source.mPrev = source.mNext = &source;
95 : }
96 :
97 0 : void Clear()
98 : {
99 0 : Cancelable * next = mNext;
100 0 : while (next != this)
101 : {
102 0 : next = detail::ClearCancelable(next);
103 : }
104 0 : mPrev = mNext = this;
105 0 : }
106 :
107 : private:
108 : /*
109 : * The grouped list structure is similar to a normal doubly linked list,
110 : * with the list object itself (via inheriting from Cancelable) acting as
111 : * an external "anchor" node that is both the head and tail of the list.
112 : *
113 : * However we have the additional requirement of representing node grouping.
114 : * Due to the requirement so support sparse groups (one or more callbacks may
115 : * not be present in a particular group) we cannot rely on a fixed group size.
116 : * This problem is solved by having the "prev" pointer for all nodes in a group
117 : * point to the node before the group, as illustrated below:
118 : *
119 : * |Anchor| |Grp 1| |====== Group 2 ======|
120 : * _______________________________________________
121 : * / \
122 : * \ +---+ +---+ +---+ +---+ +---+ /
123 : * ->|###|----->| |----->| |-->| |-->| |--
124 : * |###| | | | | | | | |
125 : * --|###|<-----| |<-----| | -| | -| |<-
126 : * / +---+ +---+ \ +---+ / +---+ / +---+ \
127 : * | \_______/ / |
128 : * | \_____________/ |
129 : * \_______________________________________________/
130 : *
131 : * This allows the start of a group to be reached from any group member via
132 : * ->prev->next. Nodes in a group can be enumerated by via the "next" chain,
133 : * inspecting the "prev" pointers to detect the end of the group. The price
134 : * for encoding grouping in this way is that upon removal of a group we have
135 : * to update not just the "prev" pointer of the following node, but of all
136 : * nodes in the following group.
137 : *
138 : * When retrieving a (sparse) group from the list, we also need to be able
139 : * to tell which callbacks are present: In a grouped list with types (A, B)
140 : * both (a, nullptr) and (nullptr, b) are by necessity represented by only
141 : * a single node in the list. To be able to recover this information, we use
142 : * distinct trampolines that tag the "cancel" function pointer stored in each
143 : * node with the index of the callback type within the argument type tuple.
144 : */
145 :
146 : template <std::size_t... Index>
147 0 : void Enqueue(std::index_sequence<Index...>, Callback<T> *... callback)
148 : {
149 0 : Cancelable * group = nullptr;
150 : (
151 0 : [&] {
152 0 : VerifyOrReturn(callback != nullptr);
153 0 : detail::EnqueueWithGroup(callback->Cancel(), group, this, &detail::TaggedDequeueGroup<Index>);
154 0 : }(),
155 : ...);
156 0 : }
157 :
158 : template <std::size_t... Index>
159 0 : bool Peek(std::index_sequence<Index...>, Callback<T> *&... callback) const
160 : {
161 0 : Cancelable * cancelable = mNext;
162 0 : VerifyOrReturnValue(cancelable != this, false);
163 0 : Cancelable * groupPrev = cancelable->mPrev;
164 : (
165 0 : [&] {
166 0 : if (cancelable->mPrev == groupPrev && cancelable->mCancel == &detail::TaggedDequeueGroup<Index>)
167 : {
168 0 : callback = Callback<decltype(callback->mCall)>::FromCancelable(cancelable);
169 0 : cancelable = cancelable->mNext;
170 : }
171 : else
172 : {
173 0 : callback = nullptr;
174 : }
175 0 : }(),
176 : ...);
177 0 : return true;
178 : }
179 : };
180 :
181 : namespace detail {
182 :
183 : // Inserts `cancelable` before `anchor`, either starting a new `group`
184 : // (populating the passed pointer if it is null) or adding to it.
185 0 : inline void EnqueueWithGroup(Cancelable * cancelable, Cancelable *& group, Cancelable * anchor, void (*cancelFn)(Cancelable *))
186 : {
187 0 : cancelable->mCancel = cancelFn;
188 0 : cancelable->mNext = anchor;
189 0 : if (!group)
190 : {
191 0 : group = cancelable;
192 0 : cancelable->mPrev = anchor->mPrev;
193 : }
194 : else
195 : {
196 0 : cancelable->mPrev = group->mPrev;
197 : }
198 0 : anchor->mPrev->mNext = cancelable;
199 0 : anchor->mPrev = cancelable;
200 0 : }
201 :
202 : // Establish prev/next links between `prev` and the group starting at `cancelable`.
203 0 : inline void LinkGroup(Cancelable * prev, Cancelable * cancelable)
204 : {
205 0 : prev->mNext = cancelable;
206 :
207 0 : Cancelable * groupPrev = cancelable->mPrev;
208 : do
209 : {
210 0 : cancelable->mPrev = prev;
211 0 : cancelable = cancelable->mNext;
212 0 : } while (cancelable->mPrev == groupPrev);
213 0 : }
214 :
215 : // Clears the state of a cancelable and returns the following one.
216 : // Does NOT touch the state of adjacent nodes.
217 0 : inline Cancelable * ClearCancelable(Cancelable * cancelable)
218 : {
219 0 : auto * next = cancelable->mNext;
220 0 : cancelable->mPrev = cancelable->mNext = cancelable;
221 0 : cancelable->mCancel = nullptr;
222 0 : return next;
223 : }
224 :
225 : // Dequeues `cancelable` and all otehr nodes in the same group.
226 0 : inline void DequeueGroup(Cancelable * cancelable)
227 : {
228 0 : Cancelable * prev = cancelable->mPrev;
229 0 : Cancelable * next = prev->mNext;
230 : do
231 : {
232 0 : next = ClearCancelable(next);
233 0 : } while (next->mPrev == prev);
234 0 : LinkGroup(prev, next);
235 0 : }
236 :
237 : template <size_t Index>
238 0 : void TaggedDequeueGroup(Cancelable * cancelable)
239 : {
240 : (void) Index; // not used, we only care that instantiations have unique addresses
241 0 : DequeueGroup(cancelable);
242 0 : }
243 :
244 : } // namespace detail
245 : } // namespace Callback
246 : } // namespace chip
|
