current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 0 down vote favorite

I need concurrent HashMap of List as value with following behavior:

  • count of read/write ops approximately equals
  • support add/remove values in lists
  • thread safe iterations over lists

After some research I implemented ConcurrentMapOfList, but I'm not sure in his correctness.

public class ConcurrentMapOfList<Key, ListValue> {
    private final ConcurrentMap<Key, ConcurrentList<ListValue>> values
            = new ConcurrentHashMap<Key, ConcurrentList<ListValue>>();

    public void add(Key key, Value value) {
        List<Value> list = values.get(key);

        if (list == null) {
            final ConcurrentList<Value> newList = new ConcurrentList<Value>();
            final ConcurrentList<Value> oldList = values.putIfAbsent(key, newList);

            if (oldList == null) {
                list = newList;
            } else {
                list = oldList;
            }
        }

        list.add(value);
    }

    public List<ListValue> remove(Key key) {
        return values.remove(key);
    }

    public boolean remove(Key key, ListValue value) {
        final List<ListValue> list = values.get(key);

        if (list == null) {
            return false;
        }

        return list.remove(value);
    }

    public List<ListValue> obtainListCopy(Key key) {
        final ConcurrentList<ListValue> list = values.get(key);

        if (list == null) {
            return Collections.emptyList();
        }

        return list.clone();
    }

    public void removeAll() {
        values.clear();
    }

    private class ConcurrentList<V> extends ArrayList<V> {
        final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
        final Lock readLock = lock.readLock();
        final Lock writeLock = lock.writeLock();

        @Override
        public boolean add(V v) {
            writeLock.lock();
            try {
                return super.add(v);
            }finally {
                writeLock.unlock();
            }
        }

        @Override
        public V remove(int index) {
            writeLock.lock();
            try {
                return super.remove(index);
            }finally {
                writeLock.unlock();
            }
        }

        @Override
        public ConcurrentList<V> clone() {
            readLock.lock();
            try {
                return (ConcurrentList<V>)super.clone();
            }finally {
                readLock.unlock();
            }
        }
    }
}
share|improve this question
    
Is there a reason you do not use the wrapper interface synchronizedMap from Collections? It seems to me that this would be the easier and safer solution. From a quick look, your implementation will e.g. fail if you add element and copy it in parallel. –  tb- Apr 9 '13 at 17:41
    
ConcurrentMap better than syncronizedMap and I need additional synchronization on values of map(some Lists). Copy and changes list isn't be failed, because they synchronized with one ReadWriteLock –  komelgman Apr 10 '13 at 6:21
    
Map of List it is MultiMap, for example in guava collections –  komelgman Apr 10 '13 at 13:49
    
For unknown reasons, I did not see this other part. Thanks for the hint. Then just one minor additional comment: I think you mixed up Value and ListValue at some places. At least, this will not compile in the current state (but is trivial to change) –  tb- Apr 10 '13 at 17:37
    
About Value and ListValue you are right. It happened at editing this question. –  komelgman Apr 11 '13 at 6:24

1 Answer 1

up vote 1 down vote accepted

Ok, after the hint from the comment it makes more sense for me. I felt a bit bad because of the wrong comment, so I have investigated this deeper.

As far as I see it, there is only one problem which I will explain in the next paragraph. But I have to admit, the implementation is rather complex because we have several layers of parallelization and locking with multiple data structures. It would need very carefully analysis to prove the correctness.

The problem I found is the remove method. You have implemented remove(int):

@Override
public V remove(int index) {
    writeLock.lock();
    try {
        return super.remove(index);
    }finally {
        writeLock.unlock();
    }
}

But you are using remove(Object):

public boolean remove(Key key, ListValue value) {
    final List<ListValue> list = values.get(key);

    if (list == null) {
        return false;
    }

    return list.remove(value);
}

Test case to show it:

    final int max = 500;
    final int maxThreads = 200;
    for (int i = 0; i < max; i++) {
        final int currentI = i;
        final List<Thread> threadList = new ArrayList<>();
        for (int j = 0; j < maxThreads; j++) {
            final int currentJ = j;
            threadList.add(new Thread(new Runnable() {
                @Override
                public void run() {
                    map.add(currentI, currentJ);
                    map.remove(currentI, currentJ);
                }
            }));
        }
        for (final Thread thread : threadList)
            thread.start();
        for (final Thread thread : threadList)
            thread.join();
    }

    if (map.getEntrySet().size() != max)
        System.err.println("entryset size should be: " + maxThreads + " is:" + map.getEntrySet().size());

    for (final Entry<Integer, ConcurrentList<Integer>> entry : map.getEntrySet()) {
        final ConcurrentList<Integer> value = entry.getValue();
        if (value.size() != 0)
            System.err.println("value size should be: " + 0 + " is:" + value.size() + ", value: " + value);
    }

This can easily be solved, if you just implement the remove(Object) method:

@Override
public boolean remove(final Object o) {
    writeLock.lock();
    try {
        return super.remove(o);
    } finally {
        writeLock.unlock();
    }
}

This errors could be avoided if you use one of the following patterns:

  • Use a synchronized list here, Vector (not recommended), CopyOnWriteArrayList or Collections.synchronizedList

  • Use encapsulation, rather then extension. Do not extend ArrayList, use implements List and use a member field with the backed up data structure. This will be in the end, nearly the same as using Collections.synchronizedList, but you could avoid the mutex and use the ReantrantLocks if you really need it

As already partly mentioned in my comment. To get the code running, I had to change the generic identifier Value to ListValue at some places, it looked like they were mixed up.

share|improve this answer
    
My bad, I really wanted implement remove(Object). I found some info on stackoverflow. –  komelgman Apr 11 '13 at 6:51
    
My current implementation uses ConcurrentLinkedQueue –  komelgman Apr 11 '13 at 6:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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