[concurrency-interest] A question aboutConcurrentLinkedQueue.remove()

[Martin Buchholz]

I agree with David's evaluation.

Martin

On Thu, Feb 26, 2009 at 00:42, David Holmes <dcholmes at optusnet.com.au> wrote:
> Hi James,
>
> Yes it is possible for a concurrent remove(o) and poll() to both succeed and
> have poll() return o.
> This looks like a bug to me - l
> ooking at the code I think poll() should use casItem rather than
> setItem(null) so that it can detect a concurrent remove().
>
> David Holmes
>
> -----Original Message-----
> From: concurrency-interest-bounces at cs.oswego.edu
> [mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of James Gan
> Sent: Thursday, 26 February 2009 5:49 PM
> To: Concurrency-interest at cs.oswego.edu
> Subject: [concurrency-interest] A question
> aboutConcurrentLinkedQueue.remove()
>
> I'm a little confused by code of ConcurrentLinkedQueue.
>
> Let's consider following scenario. Assume thread A is removing the element
> inside first node and thread B is popping, it seems to me that both of them
> can succeed.
>
>     // THREAD A
>     public boolean remove(Object o) {
>         if (o == null) return false;
>         for (Node<E> p = first(); p != null; p = p.getNext()) {
>             E item = p.getItem();
>             if (item != null &&
>                 o.equals(item) &&
>                                                  // <--- thread A here
>                 p.casItem(item, null))
>                 return true;
>         }
>         return false;
>     }
>
>     // THREAD B
>     public E poll() {
>         for (;;) {
>             Node<E> h = head;
>             Node<E> t = tail;
>             Node<E> first = h.getNext();
>             if (h == head) {
>                 if (h == t) {
>                     if (first == null)
>                         return null;
>                     else
>                         casTail(t, first);
>                 } else if (casHead(h, first)) {
>                     E item = first.getItem();
>                     if (item != null) {
>                                                    //<--- thread B is here.
>                         first.setItem(null);
>                         return item;
>                     }
>                 }
>             }
>         }
>     }
>
> Is it as-design or is it actually impossible to observe above situation?
> Thanks a lot!
>
> --
> Best Regards
> James Gan
> Current Project: Concurrent Building Block at
> http://amino-cbbs.sourceforge.net/
> Blog: http://ganzhi.blogspot.com
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>