In ConcurrentHashMap's transfer method, I don't understand the meaning of these two conditions "i >= n" and "i + n >= nextn"

user_14158012 0
Viewed 282

In the transfer method,the condition for judging the termination of the expansion (or the helping transfer threads finish) is if (i < 0 || i >= n || i + n >= nextn) {. I know i < 0 this condition means that all bins have been allocated, but I don't understand the meaning of other two conditions: i >= n and i + n >= nextn

Is i >= n considering a data overflow?(-2147483648 - 1 = 2147483647);

Is i + n >= nextn the same as i >= n?(I don't think so)

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        int n = tab.length, stride;
        //...
        int nextn = nextTab.length;
        ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
        boolean advance = true;
        boolean finishing = false; // to ensure sweep before committing nextTab
        for (int i = 0, bound = 0;;) {
            Node<K,V> f; int fh;
            while (advance) {
                int nextIndex, nextBound;
                if (--i >= bound || finishing)
                    advance = false;
                else if ((nextIndex = transferIndex) <= 0) {
                    i = -1;
                    advance = false;
                }
                else if (U.compareAndSwapInt
                         (this, TRANSFERINDEX, nextIndex,
                          nextBound = (nextIndex > stride ?
                                       nextIndex - stride : 0))) {
                    bound = nextBound;
                    i = nextIndex - 1;
                    advance = false;
                }
            }
            if (i < 0 || i >= n || i + n >= nextn) {
                int sc;
                if (finishing) {
                    nextTable = null;
                    table = nextTab;
                    sizeCtl = (n << 1) - (n >>> 1);
                    return;
                }
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                        return;
                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
            //...
}
java.util.concurrent java
1 Answers

logically, it's a piece of dead code, i think it might be boundary dection during coding/deubging.

From the view of math, if i >= n, then

  1. int overflow: impossible. because max resizing threshold is 1<<29，the maximum value of n is 1<<29
  2. i become larger than n: impossible. beacuse i = nextIndex-1, while nextIndex = transferIndex, and transferIndex=nextIndex-stride
    if i>=n, then transferIndex need to be updated to larger value(doubled) by another thread. which means a new resizing happens while current resizing has not completed!
    it's definitely impossible
while (advance) {
  int nextIndex, nextBound;
  if (--i >= bound || finishing)
      advance = false;
  else if ((nextIndex = transferIndex) <= 0) { //here is the only chance to update nextIndex
      i = -1;
      advance = false;
  }
  else if (U.compareAndSwapInt
           (this, TRANSFERINDEX, nextIndex,
            nextBound = (nextIndex > stride ?
                         nextIndex - stride : 0))) {
      bound = nextBound;
      i = nextIndex - 1;
      advance = false;
  }
}

one might doubt the updated sequence of volatile variables, such as nextTable/table/sizeCtl, also impossible.
because at the end of resizing, they got updated as belows:

//see the method transfer
if (finishing) {
   nextTable = null;
   table = nextTab;
   sizeCtl = (n << 1) - (n >>> 1);
   return;
}

And all the entering of transfer strictly check table/nextTable/sizeCtl and transferIndex.
again, no way to leak partially updates to transfer.

and so i+n >= nextn

user_49576260
Related