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  * [[http://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                         _removed = false;
 265                         _index = -1;
 266                         _prev = null;
 267                         _curr = head;
 268                 }
 269
 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);
 274                         if (success) {
 275                                 if (_removed)
 276                                         _prev = (owned)_old_prev;
 277                                 _removed = false;
 278                                 _index++;
 279                         }
 280                         return success;
 281                 }
 282
 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);
 288                 }
 289
 290                 public new G get () {
 291                         HazardPointer.Context ctx = new HazardPointer.Context ();
 292                         assert (valid);
 293                         return HazardPointer.get_pointer<G> (&_curr._data);
 294                 }
 295
 296                 public new void set (G item) {
 297                         HazardPointer.Context ctx = new HazardPointer.Context ();
 298                         assert (valid);
 299 #if DEBUG
 300                         G item_copy = item;
 301                         stderr.printf ("  Setting data %p to %p\n", _curr, item_copy);
 302                         HazardPointer.set_pointer<G> (&_curr._data, (owned)item_copy);
 303 #else
 304                         HazardPointer.set_pointer<G> (&_curr._data, item);
 305 #endif
 306                 }
 307
 308                 public void remove () {
 309                         HazardPointer.Context ctx = new HazardPointer.Context ();
 310                         assert (valid);
 311                         _curr.remove (_prev);
 312                         _removed = true;
 313                         _index--;
 314                 }
 315
 316                 public bool valid {
 317                         get {
 318                                 assert (_curr != null);
 319                                 return _prev != null && !_removed;
 320                         }
 321                 }
 322
 323                 public bool read_only { get { return false; } }
 324
 325                 public int index() {
 326                         assert (valid);
 327                         return _index;
 328                 }
 329
 330                 public void add (G item) {
 331                         HazardPointer.Context ctx = new HazardPointer.Context ();
 332                         assert (valid);
 333                         if (!Node.proceed<G> (ref _prev, ref _curr)) {
 334                                 _prev = (owned)_curr;
 335                                 _curr = null;
 336                         }
 337                         Node<G> new_node = new Node<G> (item);
 338                         new_node.insert (_prev, _curr);
 339                         _curr = (owned)new_node;
 340                         _index++;
 341                 }
 342
 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))) {
 347                                         return false;
 348                                 }
 349                         }
 350                         Node<G>? _old_prev = _removed ? _prev : null;
 351                         while (Node.proceed<G> (ref _prev, ref _curr)) {
 352                                 if (_removed)
 353                                         _prev = (owned)_old_prev;
 354                                 _removed = false;
 355                                 _index++;
 356                                 if (!f (HazardPointer.get_pointer<G> (&_curr._data))) {
 357                                         return false;
 358                                 }
 359                         }
 360                         return true;
 361                 }
 362
 363                 private bool _removed;
 364                 private int _index;
 365                 private Node<G>? _prev;
 366                 private Node<G> _curr;
 367         }
 368
 369         private class Node<G> {
 370                 public inline Node (G data) {
 371                         AtomicPointer.set (&_succ, null);
 372                         AtomicPointer.set (&_backlink, null);
 373                         G data_copy = data;
 374                         G *data_ptr = (owned)data_copy;
 375 #if DEBUG
 376                         stderr.printf ("  Creating node %p with data %p\n", this, data_ptr);
 377 #endif
 378                         AtomicPointer.set (&_data, (owned)data_ptr);
 379                 }
 380
 381                 public inline Node.head () {
 382                         AtomicPointer.set (&_succ, null);
 383                         AtomicPointer.set (&_backlink, null);
 384                         AtomicPointer.set (&_data, null);
 385 #if DEBUG
 386                         stderr.printf ("  Creating head node %p\n", this);
 387 #endif
 388                 }
 389
 390                 inline ~Node () {
 391                         HazardPointer.set_pointer<Node<G>?> (&_succ, null, 3);
 392                         HazardPointer.set_pointer<Node<G>?> (&_backlink, null);
 393 #if DEBUG
 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?> ());
 398                         }
 399 #else
 400                         HazardPointer.set_pointer<G> (&_data, null);
 401 #endif
 402                 }
 403
 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 ();
 408                                 State curr_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))
 411                                         break;
 412                                 if (curr_next == next)
 413                                         next.help_marked (curr);
 414                                 next = curr_next;
 415                         }
 416                         bool success = next != null;
 417                         if (success || force) {
 418                                 prev = (owned)curr;
 419                                 curr = (owned)next;
 420 #if DEBUG
 421                                 stderr.printf ("  Procceed to %p (previous %p)\n", curr, prev);
 422 #endif
 423                         }
 424                         return success;
 425                 }
 426
 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));
 430                         return curr == goal;
 431                 }
 432
 433                 public inline bool remove (Node<G> prev_node) {
 434 #if DEBUG
 435                         stderr.printf ("  Removing %p (previous %p)\n", this, prev_node);
 436 #endif
 437                         Node<G>? prev = prev_node;
 438                         bool result = try_flag (ref prev);
 439                         if (prev != null)
 440                                 help_flagged (prev);
 441                         return result;
 442                 }
 443
 444                 public inline void insert (owned Node<G> prev, Node<G>? next) {
 445 #if DEBUG
 446                         stderr.printf ("  Inserting %p between %p and %p\n", this, prev, next);
 447 #endif
 448                         while (true) {
 449                                 State prev_state;
 450                                 Node<G>? prev_next = get_succ (out prev_state);
 451                                 if (prev_state == State.FLAGGED) {
 452                                         prev_next.help_flagged (prev);
 453                                 } else {
 454                                         set_succ (next, State.NONE);
 455                                         bool result = prev.compare_and_exchange (next, State.NONE, this, State.NONE);
 456                                         if (result)
 457                                                 return;
 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);
 462                                 }
 463                                 search_for<G> (next, ref prev);
 464                         }
 465
 466                 }
 467
 468                 public inline void help_flagged (Node<G> prev) {
 469 #if DEBUG
 470                         stderr.printf ("    Help flagging %p (previous %p)\n", this, prev);
 471 #endif
 472                         set_backlink (prev);
 473                         if (get_state () != State.MARKED)
 474                                 try_mark ();
 475                         help_marked (prev);
 476                 }
 477
 478                 public inline void try_mark () {
 479 #if DEBUG
 480                         stderr.printf ("    Try flagging %p\n", this);
 481 #endif
 482                         do {
 483                                 Node<G>? next_node = get_next ();
 484                                 bool result = compare_and_exchange (next_node, State.NONE, next_node, State.MARKED);
 485                                 if (!result) {
 486                                         State state;
 487                                         next_node = get_succ (out state);
 488                                         if (state == State.FLAGGED)
 489                                                 help_flagged (next_node);
 490                                 }
 491                         } while (get_state () != State.MARKED);
 492                 }
 493
 494                 public inline void help_marked (Node<G> prev_node) {
 495 #if DEBUG
 496                         stderr.printf ("    Help marking %p (previous %p)\n", this, prev_node);
 497 #endif
 498                         prev_node.compare_and_exchange (this, State.FLAGGED, get_next (), State.NONE);
 499                 }
 500
 501                 public inline bool try_flag (ref Node<G>? prev_node) {
 502 #if DEBUG
 503                         stderr.printf ("    Try flagging %p (previous %p)\n", this, prev_node);
 504 #endif
 505                         while (true) {
 506                                 if (prev_node.compare_succ (this, State.FLAGGED))
 507                                         return false;
 508                                 bool result = prev_node.compare_and_exchange (this, State.NONE, this, State.FLAGGED);
 509                                 if (result)
 510                                         return true;
 511                                 State result_state;
 512                                 Node<G>? result_node = prev_node.get_succ (out result_state);
 513                                 if (result_node == this && result_state == State.FLAGGED)
 514                                         return false;
 515                                 backtrace<G> (ref prev_node);
 516                                 if (!search_for<G> (this, ref prev_node)) {
 517                                         prev_node = null;
 518                                         return false;
 519                                 }
 520                         }
 521                 }
 522
 523                 public static inline void backtrace<G> (ref Node<G>? curr) {
 524                         while (curr.get_state () == State.MARKED)
 525                                 curr = curr.get_backlink ();
 526                 }
 527
 528                 public inline bool compare_and_exchange (Node<G>? old_node, State old_state, Node<G>? new_node, State new_state) {
 529 #if DEBUG
 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");
 532                         return b;
 533 #else
 534                         return HazardPointer.compare_and_exchange_pointer<Node<G>> (&_succ, old_node, new_node, 3, (size_t)old_state, (size_t)new_state);
 535 #endif
 536                 }
 537
 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);
 541                 }
 542
 543                 public inline Node<G>? get_next () {
 544                         return get_succ (null);
 545                 }
 546
 547                 public inline State get_state () {
 548                         return (State)((size_t)AtomicPointer.get (&_succ) & 3);
 549                 }
 550
 551                 public inline Node<G>? get_succ (out State state) {
 552                         size_t rstate;
 553                         Node<G>? succ = HazardPointer.get_pointer<Node<G>> (&_succ, 3, out rstate);
 554                         state = (State)rstate;
 555                         return (owned)succ;
 556                 }
 557
 558                 public inline void set_succ (Node<G>? next, State state) {
 559 #if DEBUG
 560                         stderr.printf ("      Setting %p.succ to (%p, %s)\n", this, next, state.to_string ());
 561 #endif
 562                         HazardPointer.set_pointer<Node<G>> (&_succ, next, 3, (size_t)state);
 563                 }
 564
 565                 public inline Node<G>? get_backlink () {
 566                         return HazardPointer.get_pointer<Node<G>> (&_backlink);
 567                 }
 568
 569                 public inline void set_backlink (Node<G>? backlink) {
 570 #if DEBUG
 571                         stderr.printf ("      Setting backlink from %p to %p\n", this, backlink);
 572 #endif
 573                         HazardPointer.compare_and_exchange_pointer<Node<G>?> (&_backlink, null, backlink);
 574                 }
 575
 576                 public Node<G> *_succ;
 577                 public Node<G> *_backlink;
 578                 public G *_data;
 579         }
 580
 581         private enum State {
 582                 NONE = 0,
 583                 MARKED = 1,
 584                 FLAGGED = 2
 585         }
 586 }