/**
 * Expunge a stale entry by rehashing any possibly colliding entries
 * lying between staleSlot and the next null slot.  This also expunges
 * any other stale entries encountered before the trailing null.  See
 * Knuth, Section 6.4
 *
 * @param staleSlot index of slot known to have null key
 * @return the index of the next null slot after staleSlot
 * (all between staleSlot and this slot will have been checked
 * for expunging).
 */
private int expungeStaleEntry(int staleSlot) {
    // 入參 staleSlot: 待清理位置下標
    
    // 獲取 ThreadLocalMap 中的 Entry 數組。
    ThreadLocal.ThreadLocalMap.Entry[] tab = table;
    // len 為當前 Entry 數組容量。
    int len = tab.length;

    // expunge entry at staleSlot
    // 清除當前 staleSlot 位置的過時 Entry。
    tab[staleSlot].value = null;
    tab[staleSlot] = null;
    // 元素數量減一。
    size--;

    // Rehash until we encounter null
    // 因為 ThreadLocalMap 解決哈希沖突采用的是線性探測法，如將當前下標位置賦值為 null ，但不對后續 Entry
    // 元素進行 rehash 操作，就可能導致存在哈希沖突的后置元素無法被探測到。所以將當前元素清理后需要
    // 對后續元素進行 rehash 操作，直到遇到下一個為 null 的元素。
    ThreadLocal.ThreadLocalMap.Entry e;
    int i;
    // nextIndex 用于向后遞增索引 ((i + 1 < len) ? i + 1 : 0)
    for (i = nextIndex(staleSlot, len);
         (e = tab[i]) != null;
         i = nextIndex(i, len)) {
        ThreadLocal<?> k = e.get();
        if (k == null) {
            // 此時 Entry 不為 null，key 為 null，Entry 為過時 Entry 需清理掉。
            e.value = null;
            tab[i] = null;
            size--;
        } else {
            // 此時為有效 Entry，需要進行 rehash 操作重新定位。
            int h = k.threadLocalHashCode & (len - 1);
            if (h != i) {
                // 進入到這個分支說明 rehash 后，新的下標與原來下標不等。
                // 將當前下標位置清空。
                tab[i] = null;

                // Unlike Knuth 6.4 Algorithm R, we must scan until
                // null because multiple entries could have been stale.
                // 從 h 位置開始遍歷，直到遇到為 null 的元素，并將 rehash 后的元素插入到該位置。
                while (tab[h] != null)
                    h = nextIndex(h, len);
                tab[h] = e;
            }
        }
    }
    
    // i 為 staleSlot 后的第一個 null 元素的位置下標。
    return i;
}

/**
 * Heuristically scan some cells looking for stale entries.
 * This is invoked when either a new element is added, or
 * another stale one has been expunged. It performs a
 * logarithmic number of scans, as a balance between no
 * scanning (fast but retains garbage) and a number of scans
 * proportional to number of elements, that would find all
 * garbage but would cause some insertions to take O(n) time.
 *
 * @param i a position known NOT to hold a stale entry. The
 * scan starts at the element after i.
 *
 * @param n scan control: {@code log2(n)} cells are scanned,
 * unless a stale entry is found, in which case
 * {@code log2(table.length)-1} additional cells are scanned.
 * When called from insertions, this parameter is the number
 * of elements, but when from replaceStaleEntry, it is the
 * table length. (Note: all this could be changed to be either
 * more or less aggressive by weighting n instead of just
 * using straight log n. But this version is simple, fast, and
 * seems to work well.)
 *
 * @return true if any stale entries have been removed.
 */
private boolean cleanSomeSlots(int i, int n) {
    // 入參 i: 一個已知不為過時 Entry 的下標。掃描從 i 之后的位置開始。
    // 入參 n: 掃描次數控制值
    
    // 是否清理了任意過時 Entry 標志，
    // 為 false 代表本次方法調用未能清理任何過時 Entry，為 true 代表本次方法調用至少清理了一個過時 Entry。
    boolean removed = false;
    ThreadLocal.ThreadLocalMap.Entry[] tab = table;
    int len = tab.length;
    // doWhile 循環，至少執行一次。
    do {
        i = nextIndex(i, len);
        ThreadLocal.ThreadLocalMap.Entry e = tab[i];
        if (e != null && e.get() == null) {
            // 進入到當前分支說明當前 Entry 為過時 Entry。
            // 將 n 置為數組容量，將當前循環遍歷次數進行追增（n 變大了）。
            n = len;
            // 將標志置為 true，證明本次方法調用并不是無功而返。
            removed = true;
            // 調用清理過時 Entry 方法，并將 expungeStaleEntry 方法返回的 null 元素的下標賦值給 i，
            // 在這之間的下標都在 expungeStaleEntry 方法中進行了清理，所以這里直接跳過避免重復操作。
            i = expungeStaleEntry(i);
        }
        // >>>= 無符號右移并賦值，相當于除以 2 操作。
    } while ( (n >>>= 1) != 0);
    // 返回本次是否至少清理了一個過時 Entry。
    return removed;
}

/**
 * Replace a stale entry encountered during a set operation
 * with an entry for the specified key.  The value passed in
 * the value parameter is stored in the entry, whether or not
 * an entry already exists for the specified key.
 *
 * As a side effect, this method expunges all stale entries in the
 * "run" containing the stale entry.  (A run is a sequence of entries
 * between two null slots.)
 *
 * @param  key the key
 * @param  value the value to be associated with key
 * @param  staleSlot index of the first stale entry encountered while
 *         searching for key.
 */
private void replaceStaleEntry(ThreadLocal<?> key, Object value,
                               int staleSlot) {
    // 入參 key: set 操作傳過來的 key
    // 入參 value: set 操作傳過來的 value，與參數 key 相關聯
    // 入參 staleSlot: 待替換的過時 Entry 的下標
    
    ThreadLocal.ThreadLocalMap.Entry[] tab = table;
    int len = tab.length;
    ThreadLocal.ThreadLocalMap.Entry e;

    // Back up to check for prior stale entry in current run.
    // We clean out whole runs at a time to avoid continual
    // incremental rehashing due to garbage collector freeing
    // up refs in bunches (i.e., whenever the collector runs).
    // slotToExpunge 變量目標是存儲當前區間段（兩個 null 元素之間），第一個過時 Entry 的下標。
    // 將入參的過時 Entry 下標賦值給 slotToExpunge。
    int slotToExpunge = staleSlot;
    // 這里需要格外注意一下，這里并不是遞增下標，而是對下標進行遞減。
    // prevIndex ((i - 1 >= 0) ? i - 1 : len - 1)。
    // 向前進行遍歷直到遇到為 null 的元素。
    for (int i = prevIndex(staleSlot, len);
         (e = tab[i]) != null;
         i = prevIndex(i, len))
        if (e.get() == null)
            // 將遍歷過程中過時 Entry 的下標賦值給 slotToExpunge 變量。
            // 經過當前遍歷邏輯，slotToExpunge 將存儲兩個 null 元素之間第一個過時 key 的下標。
            slotToExpunge = i;

    // Find either the key or trailing null slot of run, whichever
    // occurs first
    // 這里是由入參的過時 Entry 下標開始向后遍歷，直到遇到 null 元素。
    for (int i = nextIndex(staleSlot, len);
         (e = tab[i]) != null;
         i = nextIndex(i, len)) {
        ThreadLocal<?> k = e.get();

        // If we find key, then we need to swap it
        // with the stale entry to maintain hash table order.
        // The newly stale slot, or any other stale slot
        // encountered above it, can then be sent to expungeStaleEntry
        // to remove or rehash all of the other entries in run.
        if (k == key) {
            // 進入當前分支表示在遍歷的過程中找到了被 set 的 Entry 對象的本體。
            // 將和 key 關聯的新 value 值賦值給本體。
            e.value = value;
            // 操作一
            // 將 Entry 對象本體和入參 staleSlot 位置的過時 Entry 進行交換，
            // 結果是set操作的 key 與 value，無論之前本體存儲在哪里，
            // 最終都會存儲在入參的 staleSlot 下標，符合方法名中的 replace 含義。
            tab[i] = tab[staleSlot];
            tab[staleSlot] = e;

            // Start expunge at preceding stale entry if it exists
            if (slotToExpunge == staleSlot)
                // 如果當前區間段第一個過時 Entry 下標仍是 staleSlot 下標，
                // 那么需要將當前 i 下標賦值給 slotToExpunge ，因為 staleSlot 下標已經存儲了 set 操作的 Entry 對象，
                // 導致當前 i 下標變成了第一個過時 Entry 的下標。
                slotToExpunge = i;
            // 先調用 expungeStaleEntry 方法清除 slotToExpunge 下標的過時 Entry，
            // 再從 expungeStaleEntry 方法返回的 null 元素的下標開始執行 cleanSomeSlots 方法。
            cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
            // 已經完成替換過時條目操作，退出當前方法。
            return;
        }

        // If we didn't find stale entry on backward scan, the
        // first stale entry seen while scanning for key is the
        // first still present in the run.
        if (k == null && slotToExpunge == staleSlot)
            // 進入當前分支說明當前 Entry 是過時 Entry。
            // 如果當前區間段第一個過時 Entry 下標仍是入參的 staleSlot 下標，
            // 則需要將當前位置下標賦值給 slotToExpunge，因為最終當前位置的過時 Entry 將是
            // 當前區間段的第一個過時 Entry。因為 staleSlot 下標位置的過時 Entry 在之后的邏輯
            // 里要么被交換到當前下標之后（上文操作一），要么被新的 set 傳入的 Entry 覆蓋掉（下文操作二）。
            slotToExpunge = i;
    }

    // If key not found, put new entry in stale slot
    // 操作二
    // 代碼執行到當前位置說明 set 的 key 與 value 是一個新的 Entry，在之前并不存在。
    // 以 set 方法傳入的 key 和 value 值 new 一個新的 Entry 對象，并覆蓋在入參的 staleSlot 下標處。
    tab[staleSlot].value = null;
    tab[staleSlot] = new ThreadLocal.ThreadLocalMap.Entry(key, value);

    // If there are any other stale entries in run, expunge them
    if (slotToExpunge != staleSlot)
        // slotToExpunge 與 staleSlot 相等則說明當前區間段只有入參 staleSlot 位置有過時 Entry，
        // 并且該過時 Entry 已被覆蓋，所以無需清理，無需進入當前分支。
        
        // 進入當前分支說明當前區間段，除了被覆蓋的過時 Entry，至少還存在一個過時 Entry，
        // slotToExpunge 下標為第一個過時 Entry 的下標。
        // 先調用 expungeStaleEntry 方法清除 slotToExpunge 下標的過時 Entry，
        // 再從 expungeStaleEntry 方法返回的 null 元素的下標開始執行 cleanSomeSlots 方法。
        cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
}