ConcurrentWeakKeyHashMap isEmpty method

Question

The following is isEmpty() method from ConcurrentWeakKeyHashMap.java, https://github.com/netty/netty/blob/master/src/main/java/org/jboss/netty/util/internal/ConcurrentWeakKeyHashMap.java

Why does it need mcsum, and what does the if(mcsum!= 0) {..} block doing ?

And more importantly, how do I get

 if (segments[i].count != 0 || mc[i] != segments[i].modCount) 

to evaluate to true?

public boolean isEmpty() {
    final Segment<K, V>[] segments = this.segments;
    /*
     * We keep track of per-segment modCounts to avoid ABA problems in which
     * an element in one segment was added and in another removed during
     * traversal, in which case the table was never actually empty at any
     * point. Note the similar use of modCounts in the size() and
     * containsValue() methods, which are the only other methods also
     * susceptible to ABA problems.
     */
    int[] mc = new int[segments.length];
    int mcsum = 0;
    for (int i = 0; i < segments.length; ++ i) {
        if (segments[i].count != 0) {
            return false;
        } else {
            mcsum += mc[i] = segments[i].modCount;
        }
    }


    // If mcsum happens to be zero, then we know we got a snapshot before
    // any modifications at all were made.  This is probably common enough
    // to bother tracking.
    if (mcsum != 0) {
        for (int i = 0; i < segments.length; ++ i) {
            if (segments[i].count != 0 || mc[i] != segments[i].modCount) {
                return false;
            }
        }
    }


    return true;
}

EDIT: Code to evaluate the above if block is now in ConcurrentWeakKeyHashMapTest

Essentially 1 thread continously monitors the concurrentMap, while another thread continuously add/remove same keypair value

Answer 1

This method is a copy of the same in Javas ConcurrentHashMap.

This kind of Map is using a modCount per segment to track during operations if it remained unchanged by different treads. During our traversal of the Map there could actually be other operations modifying the Map. This is called an ABA problem. We are asking the Map if it is empty and in fact it is not, but by accident it appears to be. A simple example:

Map with three segements
Segment 1: size=0
Segment 2: size=0
Segment 3: size=1

1. In this moment we decide to ask the Map and look into segment 1, which appears to be empty.

2. Now another algorithm comes and inserts an element to segment 1, but removes the other from segment 3. The Map was never empty.

3. Our Thread is running now again and we look into segment 2 and 3, both are empty. For us the Map is empty - as a result.

But for any empty slot we tracked whether it was modified, too. And for slot 3 we realize there have been modifications: mc[2]>=1 which means mcsum>=1. This means: since construction the Map was modified at least once. So to answer what mcsum is for: It is a shortcut for the default empty ConcurrentHashMap. If there never have been modifications, we do not need to check for concurrent modifications.

So we know something happened and check again each segment. If now a segment is empty we know what its modCount has been. For segment 3, lets say it was 1, for segment 1 it has been 0. Checking the modCount of segment 1 now it is 1 and the count is > 0 so we know that the Map is not empty.

Still there could be an ABA problem in the second loop as well. But because we know the modCounts we can catch any other concurrent algorithm changing something. So we say if the segment is empty and something changed with the modCount it has not been empty in the first place. That is, what the second loop is doing.

Hope this helps.

EDIT

And more importantly, how do I get

if (segments[i].count != 0 || mc[i] != segments[i].modCount)

to evaluate to true?

This evaluates to true if a segment contains something or if something was modified since the first loop. And it evaluates to false (which means: segment empty) if the segment contains nothing AND nothing was changed since the first loop. Or, to say it differently: We can be sure it has been empty all the time since looked on the checked segment first.

Answer 2

The mcsum checks if the map has ever been structurally modified. There appears to be no way to reset the modification counts to zero, so if the map has ever contained anything at all mcsum will be non-zero.

The weak keys are only cleaned up when the map is changed through a put, remove, et c, and they are only cleaned up within the modified segment. Retrieving values from the map does not clear up the weak keys. This means the map as implemented will hold many weak keys that have been garbage collected as they are only cleaned up if the same segment is modified.

This means results from the size() and isEmpty() methods will frequently return the wrong result.

With the API as provided your best recourse is to call purgeStaleEntries() prior to checking if the map is empty.