3 * Copyright (C) 2011 Maciej Piechotka
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 * Maciej Piechotka <uzytkownik2@gmail.com>
24 * A single-linked list. This implementation is based on
25 * [[http://www.cse.yorku.ca/~ruppert/papers/lfll.pdf|Mikhail Fomitchev and Eric Ruppert paper ]].
27 * Many threads are allowed to operate on the same structure as well as modification
28 * of structure during iteration is allowed. However the change may not be immidiatly
29 * visible to other threads.
31 public class Gee.ConcurrentList<G> : AbstractList<G> {
33 * The elements' equality testing function.
35 [CCode (notify = false)]
36 public Gee.EqualDataFunc<G> equal_func { private set; get; }
39 * Construct new, empty single linked list
41 * If not provided, the function parameter is requested to the
42 * {@link Functions} function factory methods.
44 * @param equal_func an optional element equality testing function
46 public ConcurrentList (owned Gee.EqualDataFunc<G>? equal_func = null) {
47 if (equal_func == null)
48 equal_func = Gee.Functions.get_equal_func_for (typeof (G));
49 this.equal_func = (owned)equal_func;
50 _head = new Node<G>.head ();
51 HazardPointer.set_pointer<Node<G>> (&_tail, _head);
55 HazardPointer.Context ctx = new HazardPointer.Context ();
57 HazardPointer.set_pointer<Node<G>?> (&_tail, null);
63 public override bool read_only {
72 public override int size {
74 HazardPointer.Context ctx = new HazardPointer.Context ();
76 for (var iter = iterator (); iter.next ();)
85 public bool is_empty {
87 return !iterator ().next ();
94 public override bool contains (G item) {
95 HazardPointer.Context ctx = new HazardPointer.Context ();
96 for (var iter = iterator (); iter.next ();)
97 if (equal_func (item, iter.get ()))
105 public override bool add (G item) {
106 HazardPointer.Context ctx = new HazardPointer.Context ();
107 Node<G> node = new Node<G> (item);
108 node.insert (get_tail (), null);
115 public override bool remove (G item) {
116 HazardPointer.Context ctx = new HazardPointer.Context ();
117 Gee.Iterator<G> iter = iterator ();
118 while (iter.next ()) {
119 if (equal_func (item, iter.get ())) {
130 public override void clear () {
131 HazardPointer.Context ctx = new HazardPointer.Context ();
132 var iter = iterator ();
135 HazardPointer.set_pointer (&_tail, _head);
141 public override Gee.Iterator<G> iterator () {
142 return new Iterator<G> (_head);
148 public override ListIterator<G> list_iterator () {
149 return new Iterator<G> (_head);
155 public override G? get (int index) {
156 HazardPointer.Context ctx = new HazardPointer.Context ();
158 for (var iterator = iterator (); iterator.next ();)
160 return iterator.get ();
161 assert_not_reached ();
167 public override void set (int index, G item) {
168 HazardPointer.Context ctx = new HazardPointer.Context ();
170 for (var iterator = list_iterator (); iterator.next ();) {
176 assert_not_reached ();
182 public override int index_of (G item) {
183 HazardPointer.Context ctx = new HazardPointer.Context ();
185 for (var iterator = list_iterator (); iterator.next (); index++)
186 if (equal_func (item, iterator.get ()))
194 public override void insert (int index, G item) {
195 HazardPointer.Context ctx = new HazardPointer.Context ();
199 var next = _head.get_next ();
200 Node<G> new_node = new Node<G> (item);
201 new_node.insert (prev, next);
203 for (var iterator = list_iterator (); iterator.next ();) {
209 assert_not_reached ();
216 public override G remove_at (int index) {
217 HazardPointer.Context ctx = new HazardPointer.Context ();
218 for (var iterator = list_iterator (); iterator.next ();) {
220 G data = iterator.get ();
225 assert_not_reached ();
231 public override List<G>? slice (int start, int end) {
232 HazardPointer.Context ctx = new HazardPointer.Context ();
234 assert (start <= end);
235 var list = new ConcurrentList<G> (equal_func);
236 var iterator = iterator ();
238 for (; iterator.next (); idx++)
239 if (idx >= start && idx < end)
240 list.add (iterator.get ());
247 private inline Node<G> update_tail () {
248 Node<G> tail = HazardPointer.get_pointer (&_tail);
249 Node.backtrace<G> (ref tail);
250 Node.search_for<G> (null, ref tail);
251 HazardPointer.set_pointer<Node<G>> (&_tail, tail);
255 private inline Node<G> get_tail () {
256 return update_tail ();
259 private Node<G> _head;
260 private Node<G> *_tail;
262 private class Iterator<G> : Object, Gee.Traversable<G>, Gee.Iterator<G>, ListIterator<G> {
263 public Iterator (Node<G> head) {
270 public bool next () {
271 HazardPointer.Context ctx = new HazardPointer.Context ();
272 Node<G>? _old_prev = _removed ? _prev : null;
273 bool success = Node.proceed<G> (ref _prev, ref _curr);
276 _prev = (owned)_old_prev;
283 public bool has_next () {
284 HazardPointer.Context ctx = new HazardPointer.Context ();
285 Node<G>? prev = _prev;
286 Node<G> curr = _curr;
287 return Node.proceed<G> (ref prev, ref curr);
290 public new G get () {
291 HazardPointer.Context ctx = new HazardPointer.Context ();
293 return HazardPointer.get_pointer<G> (&_curr._data);
296 public new void set (G item) {
297 HazardPointer.Context ctx = new HazardPointer.Context ();
301 stderr.printf (" Setting data %p to %p\n", _curr, item_copy);
302 HazardPointer.set_pointer<G> (&_curr._data, (owned)item_copy);
304 HazardPointer.set_pointer<G> (&_curr._data, item);
308 public void remove () {
309 HazardPointer.Context ctx = new HazardPointer.Context ();
311 _curr.remove (_prev);
318 assert (_curr != null);
319 return _prev != null && !_removed;
323 public bool read_only { get { return false; } }
330 public void add (G item) {
331 HazardPointer.Context ctx = new HazardPointer.Context ();
333 if (!Node.proceed<G> (ref _prev, ref _curr)) {
334 _prev = (owned)_curr;
337 Node<G> new_node = new Node<G> (item);
338 new_node.insert (_prev, _curr);
339 _curr = (owned)new_node;
343 public new bool foreach (ForallFunc<G> f) {
344 HazardPointer.Context ctx = new HazardPointer.Context ();
345 if (_prev != null && !_removed) {
346 if (!f (HazardPointer.get_pointer<G> (&_curr._data))) {
350 Node<G>? _old_prev = _removed ? _prev : null;
351 while (Node.proceed<G> (ref _prev, ref _curr)) {
353 _prev = (owned)_old_prev;
356 if (!f (HazardPointer.get_pointer<G> (&_curr._data))) {
363 private bool _removed;
365 private Node<G>? _prev;
366 private Node<G> _curr;
369 private class Node<G> {
370 public inline Node (G data) {
371 AtomicPointer.set (&_succ, null);
372 AtomicPointer.set (&_backlink, null);
374 G *data_ptr = (owned)data_copy;
376 stderr.printf (" Creating node %p with data %p\n", this, data_ptr);
378 AtomicPointer.set (&_data, (owned)data_ptr);
381 public inline Node.head () {
382 AtomicPointer.set (&_succ, null);
383 AtomicPointer.set (&_backlink, null);
384 AtomicPointer.set (&_data, null);
386 stderr.printf (" Creating head node %p\n", this);
391 HazardPointer.set_pointer<Node<G>?> (&_succ, null, 3);
392 HazardPointer.set_pointer<Node<G>?> (&_backlink, null);
394 HazardPointer<G?>? old_data = HazardPointer.exchange_hazard_pointer (&_data, null);
395 stderr.printf (" Freeing node %p (with data %p)\n", this, old_data != null ? old_data.get() : null);
396 if (old_data != null) {
397 old_data.release (HazardPointer.get_destroy_notify<G?> ());
400 HazardPointer.set_pointer<G> (&_data, null);
404 public static inline bool proceed<G> (ref Node<G>? prev, ref Node<G> curr, bool force = false) {
405 Node<G>? next = curr.get_next ();
406 while (next != null) {
407 State next_state = next.get_state ();
409 Node<G> curr_next = curr.get_succ (out curr_state);
410 if (next_state != State.MARKED || (curr_state == State.MARKED && curr_next == next))
412 if (curr_next == next)
413 next.help_marked (curr);
416 bool success = next != null;
417 if (success || force) {
421 stderr.printf (" Procceed to %p (previous %p)\n", curr, prev);
427 public static inline bool search_for<G> (Node<G>? goal, ref Node<G>? prev) {
428 Node<G>? curr = prev.get_next ();
429 while ((curr != goal || curr != null) && proceed<G> (ref prev, ref curr, true));
433 public inline bool remove (Node<G> prev_node) {
435 stderr.printf (" Removing %p (previous %p)\n", this, prev_node);
437 Node<G>? prev = prev_node;
438 bool result = try_flag (ref prev);
444 public inline void insert (owned Node<G> prev, Node<G>? next) {
446 stderr.printf (" Inserting %p between %p and %p\n", this, prev, next);
450 Node<G>? prev_next = get_succ (out prev_state);
451 if (prev_state == State.FLAGGED) {
452 prev_next.help_flagged (prev);
454 set_succ (next, State.NONE);
455 bool result = prev.compare_and_exchange (next, State.NONE, this, State.NONE);
458 prev_next = get_succ (out prev_state);
459 if (prev_state == State.FLAGGED)
460 prev_next.help_flagged (prev);
461 backtrace<G> (ref prev);
463 search_for<G> (next, ref prev);
468 public inline void help_flagged (Node<G> prev) {
470 stderr.printf (" Help flagging %p (previous %p)\n", this, prev);
473 if (get_state () != State.MARKED)
478 public inline void try_mark () {
480 stderr.printf (" Try flagging %p\n", this);
483 Node<G>? next_node = get_next ();
484 bool result = compare_and_exchange (next_node, State.NONE, next_node, State.MARKED);
487 next_node = get_succ (out state);
488 if (state == State.FLAGGED)
489 help_flagged (next_node);
491 } while (get_state () != State.MARKED);
494 public inline void help_marked (Node<G> prev_node) {
496 stderr.printf (" Help marking %p (previous %p)\n", this, prev_node);
498 prev_node.compare_and_exchange (this, State.FLAGGED, get_next (), State.NONE);
501 public inline bool try_flag (ref Node<G>? prev_node) {
503 stderr.printf (" Try flagging %p (previous %p)\n", this, prev_node);
506 if (prev_node.compare_succ (this, State.FLAGGED))
508 bool result = prev_node.compare_and_exchange (this, State.NONE, this, State.FLAGGED);
512 Node<G>? result_node = prev_node.get_succ (out result_state);
513 if (result_node == this && result_state == State.FLAGGED)
515 backtrace<G> (ref prev_node);
516 if (!search_for<G> (this, ref prev_node)) {
523 public static inline void backtrace<G> (ref Node<G>? curr) {
524 while (curr.get_state () == State.MARKED)
525 curr = curr.get_backlink ();
528 public inline bool compare_and_exchange (Node<G>? old_node, State old_state, Node<G>? new_node, State new_state) {
530 bool b = HazardPointer.compare_and_exchange_pointer (&_succ, old_node, new_node, 3, (size_t)old_state, (size_t)new_state);
531 stderr.printf (" Setting %p.succ to (%p, %s) if %p.succ is (%p, %s): %s\n", this, new_node, new_state.to_string (), this, old_node, old_state.to_string (), b ? "success" : "failure");
534 return HazardPointer.compare_and_exchange_pointer<Node<G>> (&_succ, old_node, new_node, 3, (size_t)old_state, (size_t)new_state);
538 public inline bool compare_succ (Node<G>? next, State state) {
539 size_t cur = (size_t)AtomicPointer.get (&_succ);
540 return cur == ((size_t)next | (size_t)state);
543 public inline Node<G>? get_next () {
544 return get_succ (null);
547 public inline State get_state () {
548 return (State)((size_t)AtomicPointer.get (&_succ) & 3);
551 public inline Node<G>? get_succ (out State state) {
553 Node<G>? succ = HazardPointer.get_pointer<Node<G>> (&_succ, 3, out rstate);
554 state = (State)rstate;
558 public inline void set_succ (Node<G>? next, State state) {
560 stderr.printf (" Setting %p.succ to (%p, %s)\n", this, next, state.to_string ());
562 HazardPointer.set_pointer<Node<G>> (&_succ, next, 3, (size_t)state);
565 public inline Node<G>? get_backlink () {
566 return HazardPointer.get_pointer<Node<G>> (&_backlink);
569 public inline void set_backlink (Node<G>? backlink) {
571 stderr.printf (" Setting backlink from %p to %p\n", this, backlink);
573 HazardPointer.compare_and_exchange_pointer<Node<G>?> (&_backlink, null, backlink);
576 public Node<G> *_succ;
577 public Node<G> *_backlink;