7
\$\begingroup\$

Basically I want to create a concurrent LinkedHashSet which returns proper size too.

I am mainly concerned about adding and removing iterations. Suggestions relating to implementation of set modification during iteration are also welcomed.

import java.util.Collection;
import java.util.LinkedHashSet;

//TODO still not sure
public class ConcurrentLinkedHashSet<E> extends LinkedHashSet<E>
{
    private static final long serialVersionUID = 1L;
    private boolean isUpdating = false;

    @Override
    public int size()
    {
        while (isUpdating)
        {
            try
            {
                wait();
            } catch (InterruptedException e)
            {
                e.printStackTrace();
                return (Integer) null;
            }
        }
        return super.size();
    }

    @Override
    public synchronized boolean addAll(Collection<? extends E> arg0)
    {
        while (isUpdating)
        {
            try
            {
                wait();
            } catch (InterruptedException e)
            {
                e.printStackTrace();
                return false;
            }
        }
        isUpdating = true;
        boolean result = false;
        result = super.addAll(arg0);
        isUpdating = false;
        notify();
        return result;
    }

    @Override
    public synchronized boolean add(E arg0)
    {
        while (isUpdating)
        {
            try
            {
                wait();
            } catch (InterruptedException e)
            {
                e.printStackTrace();
                return false;
            }
        }
        isUpdating = true;
        boolean result = super.add(arg0);
        isUpdating = false;
        notify();
        return result;
    }

    @Override
    public boolean remove(Object arg0)
    {
        while (isUpdating)
        {
            try
            {
                wait();
            } catch (InterruptedException e)
            {
                e.printStackTrace();
                return false;
            }
        }
        isUpdating = true;
        boolean result = super.remove(arg0);
        isUpdating = false;
        notify();
        return result;
    }

    @Override
    public boolean removeAll(Collection<?> arg0)
    {
        while (isUpdating)
        {
            try
            {
                wait();
            } catch (InterruptedException e)
            {
                e.printStackTrace();
                return false;
            }
        }
        isUpdating = true;
        boolean result = super.removeAll(arg0);
        isUpdating = false;
        notify();
        return result;

    }
}

EDIT : Updated the code based on reviews and is available on github

\$\endgroup\$
10
\$\begingroup\$

There are several thread safety issues :

  1. if size(), remove() and removeAll() need to wait(), they will throw an IllegalMonitorStateException since they do not hold the lock on this at the time they call wait();
  2. for that same reason, they may see stale values for isUpdating
  3. if size() would be interrupted while waiting (supposing that gets fixed) its return statement would result in a NullPointerException.
  4. while many threads may be waiting, only one will be notified when isUpdating is set to false again, since you call notify() instead of notifyAll()
  5. operations such as contains() and isEmpty() may see stale values since they are not properly synchronized.
  6. when interrupted all overridden methods violate the Set contract.
  7. the interrupted flag is cleared upon interruption since the InterruptedException is caught and the state is not set to interrupted again.
  8. not strictly a problem, but you synchronize on this. This means third party code locking on your Set will influence its behavior. It is preferrable to lock on a private Object.

I'm not sure what you mean exactly by 'proper size'.

Also, I think that if you properly implement this, you'll basically end up with the same behavior as what you'd get from Collections.synchronizedSet(new LinkedHashSet())

\$\endgroup\$
  • \$\begingroup\$ point 1 : will add under synchronized blocks. p3 : can return 0/-1.p4: no point in notifying all since ultimately only one would be active.p5: I understand it and intend to use only size() for now.p6: I believe they implement the Set interface since they properly override the methods in LinkedHashSet class.p7: can you elaborate.p8: that is the cost. \$\endgroup\$ – Abhishek Bhatia Sep 2 '14 at 19:52
  • 1
    \$\begingroup\$ @AbhishekBhatia p4 sure, only one would be active, but this is no reason to make all the others wait forever! p7 you're simply swallowing the interrupt, instead of calling Thread.currentThread().interrupt so that some other piece of code in the same thread could handle it later \$\endgroup\$ – maaartinus Sep 3 '14 at 0:27
  • \$\begingroup\$ @maaartinus : p4 since all the threads changing isUpdating will call notify, won't notify and notifyAll exhibit same behaviour? \$\endgroup\$ – Abhishek Bhatia Sep 3 '14 at 6:10
  • \$\begingroup\$ Not all threads waiting are threads that will change isUpdating. \$\endgroup\$ – bowmore Sep 3 '14 at 11:04
  • 1
    \$\begingroup\$ @AbhishekBhatia Imagine single thread starting add() and N threads calling size() and going to wait(). When the first one finishes, one waiter will be notified. \$\endgroup\$ – maaartinus Sep 4 '14 at 5:40
2
\$\begingroup\$

Naming: I think concurrent means thread safe without locks, what you are doing is SynchronizedLinkedHashSet.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.