1 #ifndef WF_SAFE_LIST_HPP
2 #define WF_SAFE_LIST_HPP
3 
4 #include <list>
5 #include <memory>
6 #include <algorithm>
7 #include <functional>
8 
9 #include <wayland-server.h>
10 
11 #include "reverse.hpp"
12 
13 /* This is a trimmed-down wrapper of std::list<T>.
14  *
15  * It supports safe iteration over all elements in the collection, where any
16  * element can be deleted from the list at any given time (i.e even in a
17  * for-each-like loop) */
18 namespace wf
19 {
20 /* The object type depends on the safe list type, and the safe list type
21  * needs access to the event loop. However, the event loop is typically
22  * available from core.hpp. Because we can't resolve this circular dependency,
23  * we provide a link to the event loop specially for the safe list */
24 namespace _safe_list_detail
25 {
26 /* In main.cpp, and initialized there */
27 extern wl_event_loop *event_loop;
28 void idle_cleanup_func(void *data);
29 }
30 
31 template<class T>
32 class safe_list_t
33 {
34     std::list<std::unique_ptr<T>> list;
35     wl_event_source *idle_cleanup_source = NULL;
36 
37     /* Remove all invalidated elements in the list */
38     std::function<void()> do_cleanup = [&] ()
__anon609bbfd90102() 39     {
40         auto it = list.begin();
41         while (it != list.end())
42         {
43             if (*it)
44             {
45                 ++it;
46             } else
47             {
48                 it = list.erase(it);
49             }
50         }
51 
52         idle_cleanup_source = NULL;
53     };
54 
55     /* Return whether the list has invalidated elements */
is_dirty() const56     bool is_dirty() const
57     {
58         return idle_cleanup_source;
59     }
60 
61   public:
safe_list_t()62     safe_list_t()
63     {}
64 
65     /* Copy the not-erased elements from other, but do not copy the idle source */
safe_list_t(const safe_list_t & other)66     safe_list_t(const safe_list_t& other)
67     {
68         *this = other;
69     }
70 
operator =(const safe_list_t & other)71     safe_list_t& operator =(const safe_list_t& other)
72     {
73         this->idle_cleanup_source = NULL;
74         other.for_each([&] (auto& el)
75         {
76             this->push_back(el);
77         });
78     }
79 
80     safe_list_t(safe_list_t&& other) = default;
81     safe_list_t& operator =(safe_list_t&& other) = default;
82 
~safe_list_t()83     ~safe_list_t()
84     {
85         if (idle_cleanup_source)
86         {
87             wl_event_source_remove(idle_cleanup_source);
88         }
89     }
90 
back()91     T& back()
92     {
93         /* No invalidated elements */
94         if (!is_dirty())
95         {
96             return *list.back();
97         }
98 
99         auto it = list.rbegin();
100         while (it != list.rend() && (*it) == nullptr)
101         {
102             ++it;
103         }
104 
105         if (it == list.rend())
106         {
107             throw std::out_of_range("back() called on an empty list!");
108         }
109 
110         return **it;
111     }
112 
size() const113     size_t size() const
114     {
115         if (!is_dirty())
116         {
117             return list.size();
118         }
119 
120         /* Count non-null elements, because that's the real size */
121         size_t sz = 0;
122         for (auto& it : list)
123         {
124             sz += (it != nullptr);
125         }
126 
127         return sz;
128     }
129 
130     /* Push back by copying */
push_back(T value)131     void push_back(T value)
132     {
133         list.push_back(std::make_unique<T>(std::move(value)));
134     }
135 
136     /* Push back by moving */
emplace_back(T && value)137     void emplace_back(T&& value)
138     {
139         list.push_back(std::make_unique<T>(value));
140     }
141 
142     enum insert_place_t
143     {
144         INSERT_BEFORE,
145         INSERT_AFTER,
146         INSERT_NONE,
147     };
148 
149     /* Insert the given value at a position in the list, determined by the
150      * check function. The value is inserted at the first position that
151      * check indicates, or at the end of the list otherwise */
emplace_at(T && value,std::function<insert_place_t (T &)> check)152     void emplace_at(T&& value, std::function<insert_place_t(T&)> check)
153     {
154         auto it = list.begin();
155         while (it != list.end())
156         {
157             /* Skip empty elements */
158             if (*it == nullptr)
159             {
160                 ++it;
161                 continue;
162             }
163 
164             auto place = check(**it);
165             switch (place)
166             {
167               case INSERT_AFTER:
168                 /* We can safely increment it, because it points to an
169                  * element in the list */
170                 ++it;
171 
172               // fall through
173               case INSERT_BEFORE:
174                 list.emplace(it, std::make_unique<T>(value));
175 
176                 return;
177 
178               default:
179                 break;
180             }
181 
182             ++it;
183         }
184 
185         /* If no place found, insert at the end */
186         emplace_back(std::move(value));
187     }
188 
insert_at(T value,std::function<insert_place_t (T &)> check)189     void insert_at(T value, std::function<insert_place_t(T&)> check)
190     {
191         emplace_at(std::move(value), check);
192     }
193 
194     /* Call func for each non-erased element of the list */
for_each(std::function<void (T &)> func) const195     void for_each(std::function<void(T&)> func) const
196     {
197         /* Go through all elements currently in the list */
198         auto it = list.begin();
199         for (int size = list.size(); size > 0; size--, it++)
200         {
201             if (*it)
202             {
203                 func(**it);
204             }
205         }
206     }
207 
208     /* Call func for each non-erased element of the list in reversed order */
for_each_reverse(std::function<void (T &)> func) const209     void for_each_reverse(std::function<void(T&)> func) const
210     {
211         auto it = list.rbegin();
212         for (int size = list.size(); size > 0; size--, it++)
213         {
214             if (*it)
215             {
216                 func(**it);
217             }
218         }
219     }
220 
221     /* Safely remove all elements equal to value */
remove_all(const T & value)222     void remove_all(const T& value)
223     {
224         remove_if([=] (const T& el) { return el == value; });
225     }
226 
227     /* Remove all elements from the list */
clear()228     void clear()
229     {
230         remove_if([] (const T& el) { return true; });
231     }
232 
233     /* Remove all elements satisfying a given condition.
234      * This function resets their pointers and scheduling a cleanup operation */
remove_if(std::function<bool (const T &)> predicate)235     void remove_if(std::function<bool(const T&)> predicate)
236     {
237         bool actually_removed = false;
238         for (auto& it : list)
239         {
240             if (it && predicate(*it))
241             {
242                 actually_removed = true;
243                 /* First reset the element in the list, and then free resources */
244                 auto copy = std::move(it);
245                 it = nullptr;
246                 /* Now copy goes out of scope */
247             }
248         }
249 
250         /* Schedule a clean-up, but be careful to not schedule it twice */
251         if (!idle_cleanup_source && actually_removed)
252         {
253             idle_cleanup_source = wl_event_loop_add_idle(
254                 _safe_list_detail::event_loop,
255                 _safe_list_detail::idle_cleanup_func, &do_cleanup);
256         }
257     }
258 };
259 }
260 
261 #endif /* end of include guard: WF_SAFE_LIST_HPP */
262