gee/concurrentlist.vala

   1 /* concurrentlist.vala
   2  *
   3  * Copyright (C) 2011  Maciej Piechotka
   4  *
   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.
   9
  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.
  14
  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
  18  *
  19  * Author:
  20  *      Maciej Piechotka <uzytkownik2@gmail.com>
  21  */
  22
  23 /**
  24  * A single-linked list. This implementation is based on
  25  * [[www.cse.yorku.ca/~ruppert/papers/lfll.pdf|Mikhail Fomitchev and  Eric Ruppert paper ]].
  26  *
  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.
  30  */
  31 public class Gee.ConcurrentList<G> : AbstractList<G> {
  32         /**
  33          * The elements' equality testing function.
  34          */
  35         [CCode (notify = false)]
  36         public Gee.EqualDataFunc<G> equal_func { private set; get; }
  37
  38         /**
  39          * Construct new, empty single linked list
  40          *
  41          * If not provided, the function parameter is requested to the
  42          * {@link Functions} function factory methods.
  43          *
  44          * @param equal_func an optional element equality testing function
  45          */
  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);
  52         }
  53
  54         ~ConcurrentList () {
  55                 HazardPointer.Context ctx = new HazardPointer.Context ();
  56                 _head = null;
  57                 HazardPointer.set_pointer<Node<G>?> (&_tail, null);
  58         }
  59
  60         /**
  61          * {@inheritDoc}
  62          */
  63         public override bool read_only {
  64                 get {
  65                         return false;
  66                 }
  67         }
  68
  69         /**
  70          * {@inheritDoc}
  71          */
  72         public override int size {
  73                 get {
  74                         HazardPointer.Context ctx = new HazardPointer.Context ();
  75                         int result = 0;
  76                         for (var iter = iterator (); iter.next ();)
  77                                 result++;
  78                         return result;
  79                 }
  80         }
  81
  82         /**
  83          * {@inheritDoc}
  84          */
  85         public bool is_empty {
  86                 get {
  87                         return !iterator ().next ();
  88                 }
  89         }
  90
  91         /**
  92          * {@inheritDoc}
  93          */
  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 ()))
  98                                 return true;
  99                 return false;
 100         }
 101
 102         /**
 103          * {@inheritDoc}
 104          */
 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);
 109                 return true;
 110         }
 111
 112         /**
 113          * {@inheritDoc}
 114          */
 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 ())) {
 120                                 iter.remove ();
 121                                 return true;
 122                         }
 123                 }
 124                 return false;
 125         }
 126
 127         /**
 128          * {@inheritDoc}
 129          */
 130         public override void clear () {
 131                 HazardPointer.Context ctx = new HazardPointer.Context ();
 132                 var iter = iterator ();
 133                 while (iter.next ())
 134                         iter.remove ();
 135                 HazardPointer.set_pointer (&_tail, _head);
 136         }
 137
 138         /**
 139          * {@inheritDoc}
 140          */
 141         public override Gee.Iterator<G> iterator () {
 142                 return new Iterator<G> (_head);
 143         }
 144
 145         /**
 146          * {@inheritDoc}
 147          */
 148         public override ListIterator<G> list_iterator () {
 149                 return new Iterator<G> (_head);
 150         }
 151
 152         /**
 153          * {@inheritDoc}
 154          */
 155         public override G? get (int index) {
 156                 HazardPointer.Context ctx = new HazardPointer.Context ();
 157                 assert (index >= 0);
 158                 for (var iterator = iterator (); iterator.next ();)
 159                         if (index-- == 0)
 160                                 return iterator.get ();
 161                 assert_not_reached ();
 162         }
 163
 164         /**
 165          * {@inheritDoc}
 166          */
 167         public override void set (int index, G item) {
 168                 HazardPointer.Context ctx = new HazardPointer.Context ();
 169                 assert (index >= 0);
 170                 for (var iterator = list_iterator (); iterator.next ();) {
 171                         if (index-- == 0) {
 172                                 iterator.set (item);
 173                                 return;
 174                         }
 175                 }
 176                 assert_not_reached ();
 177         }
 178
 179         /**
 180          * {@inheritDoc}
 181          */
 182         public override int index_of (G item) {
 183                 HazardPointer.Context ctx = new HazardPointer.Context ();
 184                 int index = 0;
 185                 for (var iterator = list_iterator (); iterator.next (); index++)
 186                         if (equal_func (item, iterator.get ()))
 187                                 return index;
 188                 return -1;
 189         }
 190
 191         /**
 192          * {@inheritDoc}
 193          */
 194         public override void insert (int index, G item) {
 195                 HazardPointer.Context ctx = new HazardPointer.Context ();
 196                 assert (index >= 0);
 197                 if (index == 0) {
 198                         var prev = _head;
 199                         var next = _head.get_next ();
 200                         Node<G> new_node = new Node<G> (item);
 201                         new_node.insert (prev, next);
 202                 } else {
 203                         for (var iterator = list_iterator (); iterator.next ();) {
 204                                 if (--index == 0) {
 205                                         iterator.add (item);
 206                                         return;
 207                                 }
 208                         }
 209                         assert_not_reached ();
 210                 }
 211         }
 212
 213         /**
 214          * {@inheritDoc}
 215          */
 216         public override G remove_at (int index) {
 217                 HazardPointer.Context ctx = new HazardPointer.Context ();
 218                 for (var iterator = list_iterator (); iterator.next ();) {
 219                         if (index-- == 0) {
 220                                 G data = iterator.get ();
 221                                 iterator.remove ();
 222                                 return data;
 223                         }
 224                 }
 225                 assert_not_reached ();
 226         }
 227
 228         /**
 229          * {@inheritDoc}
 230          */
 231         public override List<G>? slice (int start, int end) {
 232                 HazardPointer.Context ctx = new HazardPointer.Context ();
 233                 assert (0 <= start);
 234                 assert (start <= end);
 235                 var list = new ConcurrentList<G> (equal_func);
 236                 var iterator = iterator ();
 237                 int idx = 0;
 238                 for (; iterator.next (); idx++)
 239                         if (idx >= start && idx < end)
 240                                 list.add (iterator.get ());
 241                         else if (idx >= end)
 242                                 break;
 243                 assert (idx >= end);
 244                 return list;
 245         }
 246
 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);
 252                 return tail;
 253         }
 254
 255         private inline Node<G> get_tail () {
 256                 return update_tail ();
 257         }
 258
 259         private Node<G> _head;
 260         private Node<G> *_tail;
 261
 262         private class Iterator<G> : Object, Gee.Traversable<G>, Gee.Iterator<G>, ListIterator<G> {
 263                 public Iterator (Node<G> head) {
 264                         _started = false;
 265                         _removed = false;
 266                         _index = -1;
 267                         _prev = null;
 268                         _curr = head;
 269                 }
 270
 271                 public bool next () {
 272                         HazardPointer.Context ctx = new HazardPointer.Context ();
 273                         Node<G>? _old_prev = _removed ? _prev : null;
 274                         bool success = Node.proceed<G> (ref _prev, ref _curr);
 275                         if (success) {
 276                                 if (_removed)
 277                                         _prev = _old_prev;
 278                                 _removed = false;
 279                                 _started = true;
 280                                 _index++;
 281                         }
 282                         return success;
 283                 }
 284
 285                 public bool has_next () {
 286                         HazardPointer.Context ctx = new HazardPointer.Context ();
 287                         Node<G>? prev = _prev;
 288                         Node<G>? curr = _curr;
 289                         return Node.proceed<G> (ref prev, ref curr);
 290                 }
 291
 292                 public new G get () {
 293                         HazardPointer.Context ctx = new HazardPointer.Context ();
 294                         assert (valid);
 295                         return HazardPointer.get_pointer<G> (&_curr._data);
 296                 }
 297
 298                 public new void set (G item) {
 299                         HazardPointer.Context ctx = new HazardPointer.Context ();
 300                         assert (valid);
 301 #if DEBUG
 302                         G item_copy = item;
 303                         stderr.printf ("  Setting data %p to %p\n", _curr, item_copy);
 304                         HazardPointer.set_pointer<G> (&_curr._data, (owned)item_copy);
 305 #else
 306                         HazardPointer.set_pointer<G> (&_curr._data, item);
 307 #endif
 308                 }
 309
 310                 public void remove () {
 311                         HazardPointer.Context ctx = new HazardPointer.Context ();
 312                         assert (valid);
 313                         _curr.remove (_prev);
 314                         _removed = true;
 315                         _index--;
 316                 }
 317
 318                 public bool valid {
 319                         get { return _started && !_removed && _curr != null; }
 320                 }
 321
 322                 public bool read_only { get { return false; } }
 323
 324                 public int index() {
 325                         assert (valid);
 326                         return _index;
 327                 }
 328
 329                 public void add (G item) {
 330                         HazardPointer.Context ctx = new HazardPointer.Context ();
 331                         assert (valid);
 332                         if (!Node.proceed<G> (ref _prev, ref _curr)) {
 333                                 _prev = (owned)_curr;
 334                                 _curr = null;
 335                         }
 336                         Node<G> new_node = new Node<G> (item);
 337                         new_node.insert (_prev, _curr);
 338                         _curr = (owned)new_node;
 339                         _index++;
 340                 }
 341
 342                 public new bool foreach (ForallFunc<G> f) {
 343                         HazardPointer.Context ctx = new HazardPointer.Context ();
 344                         if (_started && !_removed) {
 345                                 if (!f (HazardPointer.get_pointer<G> (&_curr._data))) {
 346                                         return false;
 347                                 }
 348                         }
 349                         Node<G>? _old_prev = _removed ? _prev : null;
 350                         while (Node.proceed<G> (ref _prev, ref _curr)) {
 351                                 if (_removed)
 352                                         _prev = _old_prev;
 353                                 _removed = false;
 354                                 _started = true;
 355                                 _index++;
 356                                 if (!f (HazardPointer.get_pointer<G> (&_curr._data))) {
 357                                         return false;
 358                                 }
 359                         }
 360                         return true;
 361                 }
 362
 363                 private bool _started;
 364                 private bool _removed;
 365                 private int _index;
 366                 private Node<G> _prev;
 367                 private Node<G>? _curr;
 368         }
 369
 370         private class Node<G> {
 371                 public inline Node (G data) {
 372                         AtomicPointer.set (&_succ, null);
 373                         AtomicPointer.set (&_backlink, null);
 374                         G data_copy = data;
 375                         G *data_ptr = (owned)data_copy;
 376 #if DEBUG
 377                         stderr.printf ("  Creating node %p with data %p\n", this, data_ptr);
 378 #endif
 379                         AtomicPointer.set (&_data, (owned)data_ptr);
 380                 }
 381
 382                 public inline Node.head () {
 383                         AtomicPointer.set (&_succ, null);
 384                         AtomicPointer.set (&_backlink, null);
 385                         AtomicPointer.set (&_data, null);
 386 #if DEBUG
 387                         stderr.printf ("  Creating head node %p\n", this);
 388 #endif
 389                 }
 390
 391                 inline ~Node () {
 392                         HazardPointer.set_pointer<Node<G>?> (&_succ, null, 3);
 393                         HazardPointer.set_pointer<Node<G>?> (&_backlink, null);
 394 #if DEBUG
 395                         HazardPointer<G?>? old_data = HazardPointer.exchange_hazard_pointer (&_data, null);
 396                         stderr.printf ("  Freeing node %p (with data %p)\n", this, old_data != null ? old_data.get() : null);
 397                         if (old_data != null) {
 398                                 old_data.release (HazardPointer.get_destroy_notify<G?> ());
 399                         }
 400 #else
 401                         HazardPointer.set_pointer<G> (&_data, null);
 402 #endif
 403                 }
 404
 405                 public static inline bool proceed<G> (ref Node<G>? prev, ref Node<G> curr, bool force = false) {
 406                         Node<G> next = curr.get_next ();
 407                         while (next != null) {
 408                                 State next_state = next.get_state ();
 409                                 State curr_state;
 410                                 Node<G> curr_next = curr.get_succ (out curr_state);
 411                                 if (next_state != State.MARKED || (curr_state == State.MARKED && curr_next == next))
 412                                         break;
 413                                 if (curr_next == next)
 414                                         next.help_marked (curr);
 415                                 next = curr_next;
 416                         }
 417                         bool success = next != null;
 418                         if (success || force) {
 419                                 prev = (owned)curr;
 420                                 curr = (owned)next;
 421 #if DEBUG
 422                                 stderr.printf ("  Procceed to %p (previous %p)\n", curr, prev);
 423 #endif
 424                         }
 425                         return success;
 426                 }
 427
 428                 public static inline bool search_for<G> (Node<G>? goal, ref Node<G>? prev) {
 429                         Node<G>? curr = prev.get_next ();
 430                         while ((curr != goal || curr != null) && proceed<G> (ref prev, ref curr, true));
 431                         return curr == goal;
 432                 }
 433
 434                 public inline bool remove (Node<G> prev_node) {
 435 #if DEBUG
 436                         stderr.printf ("  Removing %p (previous %p)\n", this, prev_node);
 437 #endif
 438                         Node<G>? prev = prev_node;
 439                         bool result = try_flag (ref prev);
 440                         if (prev != null)
 441                                 help_flagged (prev);
 442                         return result;
 443                 }
 444
 445                 public inline void insert (owned Node<G> prev, Node<G>? next) {
 446 #if DEBUG
 447                         stderr.printf ("  Inserting %p between %p and %p\n", this, prev, next);
 448 #endif
 449                         while (true) {
 450                                 State prev_state;
 451                                 Node<G>? prev_next = get_succ (out prev_state);
 452                                 if (prev_state == State.FLAGGED) {
 453                                         prev_next.help_flagged (prev);
 454                                 } else {
 455                                         set_succ (next, State.NONE);
 456                                         bool result = prev.compare_and_exchange (next, State.NONE, this, State.NONE);
 457                                         if (result)
 458                                                 return;
 459                                         prev_next = get_succ (out prev_state);
 460                                         if (prev_state == State.FLAGGED)
 461                                                 prev_next.help_flagged (prev);
 462                                         backtrace<G> (ref prev);
 463                                 }
 464                                 search_for<G> (next, ref prev);
 465                         }
 466
 467                 }
 468
 469                 public inline void help_flagged (Node<G> prev) {
 470 #if DEBUG
 471                         stderr.printf ("    Help flagging %p (previous %p)\n", this, prev);
 472 #endif
 473                         set_backlink (prev);
 474                         if (get_state () == State.MARKED)
 475                                 try_mark ();
 476                         help_marked (prev);
 477                 }
 478
 479                 public inline void try_mark () {
 480 #if DEBUG
 481                         stderr.printf ("    Try flagging %p\n", this);
 482 #endif
 483                         do {
 484                                 Node<G>? next_node = get_next ();
 485                                 bool result = compare_and_exchange (next_node, State.NONE, next_node, State.MARKED);
 486                                 if (!result && get_state () == State.FLAGGED)
 487                                         help_flagged (next_node);
 488                         } while (get_state () != State.MARKED);
 489                 }
 490
 491                 public inline void help_marked (Node<G> prev_node) {
 492 #if DEBUG
 493                         stderr.printf ("    Help marking %p (previous %p)\n", this, prev_node);
 494 #endif
 495                         prev_node.compare_and_exchange (this, State.FLAGGED, get_next (), State.NONE);
 496                 }
 497
 498                 public inline bool try_flag (ref Node<G>? prev_node) {
 499 #if DEBUG
 500                         stderr.printf ("    Try flagging %p (previous %p)\n", this, prev_node);
 501 #endif
 502                         while (true) {
 503                                 if (prev_node.compare_succ (this, State.FLAGGED))
 504                                         return false;
 505                                 bool result = prev_node.compare_and_exchange (this, State.NONE, this, State.FLAGGED);
 506                                 if (result)
 507                                         return true;
 508                                 State result_state;
 509                                 Node<G>? result_node = prev_node.get_succ (out result_state);
 510                                 if (result_node == this && result_state == State.FLAGGED)
 511                                         return false;
 512                                 backtrace<G> (ref prev_node);
 513                                 if (!search_for<G> (this, ref prev_node)) {
 514                                         prev_node = null;
 515                                         return false;
 516                                 }
 517                         }
 518                 }
 519
 520                 public static inline void backtrace<G> (ref Node<G>? curr) {
 521                         while (curr.get_state () == State.MARKED)
 522                                 curr = curr.get_backlink ();
 523                 }
 524
 525                 public inline bool compare_and_exchange (Node<G>? old_node, State old_state, Node<G>? new_node, State new_state) {
 526 #if DEBUG
 527                         bool b = HazardPointer.compare_and_exchange_pointer (&_succ, old_node, new_node, 3, (size_t)old_state, (size_t)new_state);
 528                         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");
 529                         return b;
 530 #else
 531                         return HazardPointer.compare_and_exchange_pointer (&_succ, old_node, new_node, 3, (size_t)old_state, (size_t)new_state);
 532 #endif
 533                 }
 534
 535                 public inline bool compare_succ (Node<G>? next, State state) {
 536                         size_t cur = (size_t)AtomicPointer.get (&_succ);
 537                         return cur == ((size_t)next | (size_t)state);
 538                 }
 539
 540                 public inline Node<G>? get_next () {
 541                         return get_succ (null);
 542                 }
 543
 544                 public inline State get_state () {
 545                         return (State)((size_t)AtomicPointer.get (&_succ) & 3);
 546                 }
 547
 548                 public inline Node<G>? get_succ (out State state) {
 549                         size_t rstate;
 550                         Node<G>? succ = HazardPointer.get_pointer<Node<G>> (&_succ, 3, out rstate);
 551                         state = (State)rstate;
 552                         return (owned)succ;
 553                 }
 554
 555                 public inline void set_succ (Node<G>? next, State state) {
 556 #if DEBUG
 557                         stderr.printf ("      Setting %p.succ to (%p, %s)\n", this, next, state.to_string ());
 558 #endif
 559                         HazardPointer.set_pointer<Node<G>> (&_succ, next, 3, (size_t)state);
 560                 }
 561
 562                 public inline Node<G>? get_backlink () {
 563                         return HazardPointer.get_pointer<Node<G>> (&_backlink);
 564                 }
 565
 566                 public inline void set_backlink (Node<G>? backlink) {
 567 #if DEBUG
 568                         stderr.printf ("      Setting backlink from %p to %p\n", this, backlink);
 569 #endif
 570                         HazardPointer.compare_and_exchange_pointer<Node<G>?> (&_backlink, null, backlink);
 571                 }
 572
 573                 public Node<G> *_succ;
 574                 public Node<G> *_backlink;
 575                 public G *_data;
 576         }
 577
 578         private enum State {
 579                 NONE = 0,
 580                 MARKED = 1,
 581                 FLAGGED = 2
 582         }
 583 }