Mir
thread_safe_list.h
Go to the documentation of this file.
1 /*
2  * Copyright © 2014 Canonical Ltd.
3  *
4  * This program is free software: you can redistribute it and/or modify it
5  * under the terms of the GNU Lesser General Public License version 3,
6  * as published by the Free Software Foundation.
7  *
8  * This program is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11  * GNU Lesser General Public License for more details.
12  *
13  * You should have received a copy of the GNU Lesser General Public License
14  * along with this program. If not, see <http://www.gnu.org/licenses/>.
15  *
16  * Authored By: Alan Griffiths <alan@octopull.co.uk>
17  Alexandros Frantzis <alexandros.frantzis@canonical.com>
18  */
19 
20 #ifndef MIR_THREAD_SAFE_LIST_H_
21 #define MIR_THREAD_SAFE_LIST_H_
22 
24 
25 #include <atomic>
26 
27 namespace mir
28 {
29 
30 /*
31  * Requirements for type 'Element'
32  * - for_each():
33  * - copy-assignable
34  * - add():
35  * - copy-assignable
36  * - operator bool: returns whether this is a valid element
37  * - remove(), remove_all():
38  * - copy-assignable
39  * - Element{}: default construction should create an invalid element
40  * - bool operator==: equality of elements
41  * - bool operator!=: inequality of elements
42  * - clear():
43  * - copy-assignable
44  * - Element{}: default construction should create an invalid element
45  */
46 
47 template<class Element>
49 {
50 public:
51  void add(Element const& element);
52  void remove(Element const& element);
53  unsigned int remove_all(Element const& element);
54  void clear();
55  void for_each(std::function<void(Element const& element)> const& f);
56 
57 private:
58  struct ListItem
59  {
60  ListItem() {}
62  Element element;
63  std::atomic<ListItem*> next{nullptr};
64 
65  ~ListItem() { delete next.load(); }
66  } head;
67 };
68 
69 template<class Element>
71  std::function<void(Element const& element)> const& f)
72 {
73  ListItem* current_item = &head;
74 
75  while (current_item)
76  {
77  RecursiveReadLock lock{current_item->mutex};
78 
79  // We need to take a copy in case we recursively remove during call
80  if (auto const copy_of_element = current_item->element) f(copy_of_element);
81 
82  current_item = current_item->next;
83  }
84 }
85 
86 template<class Element>
87 void ThreadSafeList<Element>::add(Element const& element)
88 {
89  ListItem* current_item = &head;
90 
91  do
92  {
93  // Note: we release the read lock to avoid two threads calling add at
94  // the same time mutually blocking the other's upgrade to write lock.
95  {
96  RecursiveReadLock lock{current_item->mutex};
97  if (current_item->element) continue;
98  }
99 
100  RecursiveWriteLock lock{current_item->mutex};
101 
102  if (!current_item->element)
103  {
104  current_item->element = element;
105  return;
106  }
107  }
108  while (current_item->next && (current_item = current_item->next));
109 
110  // No empty Items so append a new one
111  auto new_item = new ListItem;
112  new_item->element = element;
113 
114  for (ListItem* expected{nullptr};
115  !current_item->next.compare_exchange_weak(expected, new_item);
116  expected = nullptr)
117  {
118  if (expected) current_item = expected;
119  }
120 }
121 
122 template<class Element>
123 void ThreadSafeList<Element>::remove(Element const& element)
124 {
125  ListItem* current_item = &head;
126 
127  do
128  {
129  {
130  RecursiveReadLock lock{current_item->mutex};
131  if (current_item->element != element) continue;
132  }
133 
134  RecursiveWriteLock lock{current_item->mutex};
135 
136  if (current_item->element == element)
137  {
138  current_item->element = Element{};
139  return;
140  }
141  }
142  while ((current_item = current_item->next));
143 }
144 
145 template<class Element>
146 unsigned int ThreadSafeList<Element>::remove_all(Element const& element)
147 {
148  ListItem* current_item = &head;
149  auto removed = 0u;
150 
151  do
152  {
153  {
154  RecursiveReadLock lock{current_item->mutex};
155  if (current_item->element != element) continue;
156  }
157 
158  RecursiveWriteLock lock{current_item->mutex};
159 
160  if (current_item->element == element)
161  {
162  current_item->element = Element{};
163  ++removed;
164  }
165  }
166  while ((current_item = current_item->next));
167 
168  return removed;
169 }
170 
171 template<class Element>
173 {
174  ListItem* current_item = &head;
175 
176  do
177  {
178  RecursiveWriteLock lock{current_item->mutex};
179  current_item->element = Element{};
180  }
181  while ((current_item = current_item->next));
182 }
183 
184 }
185 
186 #endif /* MIR_THREAD_SAFE_LIST_H_ */
All things Mir.
Definition: buffer_stream.h:37
Definition: recursive_read_write_mutex.h:56
unsigned int remove_all(Element const &element)
Definition: thread_safe_list.h:146
void remove(Element const &element)
Definition: thread_safe_list.h:123
void for_each(std::function< void(Element const &element)> const &f)
Definition: thread_safe_list.h:70
void add(Element const &element)
Definition: thread_safe_list.h:87
a recursive read-write mutex.
Definition: recursive_read_write_mutex.h:31
void clear()
Definition: thread_safe_list.h:172
Definition: thread_safe_list.h:48
Definition: recursive_read_write_mutex.h:66

Copyright © 2012,2013 Canonical Ltd.
Generated on Tue Mar 24 16:15:19 UTC 2015