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