322 * to lower. Because the table uses power-of-two masking, sets of
323 * hashes that vary only in bits above the current mask will
324 * always collide. (Among known examples are sets of Float keys
325 * holding consecutive whole numbers in small tables.) So we
326 * apply a transform that spreads the impact of higher bits
327 * downward. There is a tradeoff between speed, utility, and
328 * quality of bit-spreading. Because many common sets of hashes
329 * are already reasonably distributed (so don't benefit from
330 * spreading), and because we use trees to handle large sets of
331 * collisions in bins, we just XOR some shifted bits in the
332 * cheapest possible way to reduce systematic lossage, as well as
333 * to incorporate impact of the highest bits that would otherwise
334 * never be used in index calculations because of table bounds.
335 */
336 static final int hash(Object key) {
337 int h;
338 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
339 }
340
341 /**
342 * Returns x's Class if it is of the form "class C implements
343 * Comparable<C>", else null.
344 */
345 static Class<?> comparableClassFor(Object x) {
346 if (x instanceof Comparable) {
347 Class<?> c; Type[] ts, as; ParameterizedType p;
348 if ((c = x.getClass()) == String.class) // bypass checks
349 return c;
350 if ((ts = c.getGenericInterfaces()) != null) {
351 for (Type t : ts) {
352 if ((t instanceof ParameterizedType) &&
353 ((p = (ParameterizedType) t).getRawType() ==
354 Comparable.class) &&
355 (as = p.getActualTypeArguments()) != null &&
356 as.length == 1 && as[0] == c) // type arg is c
357 return c;
358 }
359 }
360 }
361 return null;
362 }
363
364 /**
365 * Returns k.compareTo(x) if x matches kc (k's screened comparable
366 * class), else 0.
367 */
368 @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
369 static int compareComparables(Class<?> kc, Object k, Object x) {
370 return (x == null || x.getClass() != kc ? 0 :
371 ((Comparable)k).compareTo(x));
372 }
373
374 /**
375 * Returns a power of two size for the given target capacity.
376 */
377 static final int tableSizeFor(int cap) {
378 int n = cap - 1;
379 n |= n >>> 1;
380 n |= n >>> 2;
381 n |= n >>> 4;
1837 /**
1838 * Finds the node starting at root p with the given hash and key.
1839 * The kc argument caches comparableClassFor(key) upon first use
1840 * comparing keys.
1841 */
1842 final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
1843 TreeNode<K,V> p = this;
1844 do {
1845 int ph, dir; K pk;
1846 TreeNode<K,V> pl = p.left, pr = p.right, q;
1847 if ((ph = p.hash) > h)
1848 p = pl;
1849 else if (ph < h)
1850 p = pr;
1851 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
1852 return p;
1853 else if (pl == null)
1854 p = pr;
1855 else if (pr == null)
1856 p = pl;
1857 else if ((kc != null ||
1858 (kc = comparableClassFor(k)) != null) &&
1859 (dir = compareComparables(kc, k, pk)) != 0)
1860 p = (dir < 0) ? pl : pr;
1861 else if ((q = pr.find(h, k, kc)) != null)
1862 return q;
1863 else
1864 p = pl;
1865 } while (p != null);
1866 return null;
1867 }
1868
1869 /**
1870 * Calls find for root node.
1871 */
1872 final TreeNode<K,V> getTreeNode(int h, Object k) {
1873 return ((parent != null) ? root() : this).find(h, k, null);
1874 }
1875
1876 /**
1877 * Tie-breaking utility for ordering insertions when equal
1878 * hashCodes and non-comparable. We don't require a total
1898 TreeNode<K,V> root = null;
1899 for (TreeNode<K,V> x = this, next; x != null; x = next) {
1900 next = (TreeNode<K,V>)x.next;
1901 x.left = x.right = null;
1902 if (root == null) {
1903 x.parent = null;
1904 x.red = false;
1905 root = x;
1906 }
1907 else {
1908 K k = x.key;
1909 int h = x.hash;
1910 Class<?> kc = null;
1911 for (TreeNode<K,V> p = root;;) {
1912 int dir, ph;
1913 K pk = p.key;
1914 if ((ph = p.hash) > h)
1915 dir = -1;
1916 else if (ph < h)
1917 dir = 1;
1918 else if ((kc == null &&
1919 (kc = comparableClassFor(k)) == null) ||
1920 (dir = compareComparables(kc, k, pk)) == 0)
1921 dir = tieBreakOrder(k, pk);
1922
1923 TreeNode<K,V> xp = p;
1924 if ((p = (dir <= 0) ? p.left : p.right) == null) {
1925 x.parent = xp;
1926 if (dir <= 0)
1927 xp.left = x;
1928 else
1929 xp.right = x;
1930 root = balanceInsertion(root, x);
1931 break;
1932 }
1933 }
1934 }
1935 }
1936 moveRootToFront(tab, root);
1937 }
1938
1939 /**
1952 }
1953 return hd;
1954 }
1955
1956 /**
1957 * Tree version of putVal.
1958 */
1959 final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
1960 int h, K k, V v) {
1961 Class<?> kc = null;
1962 boolean searched = false;
1963 TreeNode<K,V> root = (parent != null) ? root() : this;
1964 for (TreeNode<K,V> p = root;;) {
1965 int dir, ph; K pk;
1966 if ((ph = p.hash) > h)
1967 dir = -1;
1968 else if (ph < h)
1969 dir = 1;
1970 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
1971 return p;
1972 else if ((kc == null &&
1973 (kc = comparableClassFor(k)) == null) ||
1974 (dir = compareComparables(kc, k, pk)) == 0) {
1975 if (!searched) {
1976 TreeNode<K,V> q, ch;
1977 searched = true;
1978 if (((ch = p.left) != null &&
1979 (q = ch.find(h, k, kc)) != null) ||
1980 ((ch = p.right) != null &&
1981 (q = ch.find(h, k, kc)) != null))
1982 return q;
1983 }
1984 dir = tieBreakOrder(k, pk);
1985 }
1986
1987 TreeNode<K,V> xp = p;
1988 if ((p = (dir <= 0) ? p.left : p.right) == null) {
1989 Node<K,V> xpn = xp.next;
1990 TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
1991 if (dir <= 0)
1992 xp.left = x;
1993 else
|
322 * to lower. Because the table uses power-of-two masking, sets of
323 * hashes that vary only in bits above the current mask will
324 * always collide. (Among known examples are sets of Float keys
325 * holding consecutive whole numbers in small tables.) So we
326 * apply a transform that spreads the impact of higher bits
327 * downward. There is a tradeoff between speed, utility, and
328 * quality of bit-spreading. Because many common sets of hashes
329 * are already reasonably distributed (so don't benefit from
330 * spreading), and because we use trees to handle large sets of
331 * collisions in bins, we just XOR some shifted bits in the
332 * cheapest possible way to reduce systematic lossage, as well as
333 * to incorporate impact of the highest bits that would otherwise
334 * never be used in index calculations because of table bounds.
335 */
336 static final int hash(Object key) {
337 int h;
338 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
339 }
340
341 /**
342 * Returns 'cached' if != null, else
343 * returns x's Class if it is of the form "class C implements
344 * Comparable<C>", else void.class.
345 */
346 static Class<?> comparableClassFor(Class<?> cached, Object x) {
347 if (cached != null) {
348 return cached;
349 }
350 if (x instanceof Comparable) {
351 Class<?> c; Type[] ts, as; ParameterizedType p;
352 if ((c = x.getClass()) == String.class) // bypass checks
353 return c;
354 if ((ts = c.getGenericInterfaces()) != null) {
355 for (Type t : ts) {
356 if ((t instanceof ParameterizedType) &&
357 ((p = (ParameterizedType) t).getRawType() ==
358 Comparable.class) &&
359 (as = p.getActualTypeArguments()) != null &&
360 as.length == 1 && as[0] == c) // type arg is c
361 return c;
362 }
363 }
364 }
365 return void.class;
366 }
367
368 /**
369 * Returns k.compareTo(x) if x matches kc (k's screened comparable
370 * class), else 0.
371 */
372 @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
373 static int compareComparables(Class<?> kc, Object k, Object x) {
374 return (x == null || x.getClass() != kc ? 0 :
375 ((Comparable)k).compareTo(x));
376 }
377
378 /**
379 * Returns a power of two size for the given target capacity.
380 */
381 static final int tableSizeFor(int cap) {
382 int n = cap - 1;
383 n |= n >>> 1;
384 n |= n >>> 2;
385 n |= n >>> 4;
1841 /**
1842 * Finds the node starting at root p with the given hash and key.
1843 * The kc argument caches comparableClassFor(key) upon first use
1844 * comparing keys.
1845 */
1846 final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
1847 TreeNode<K,V> p = this;
1848 do {
1849 int ph, dir; K pk;
1850 TreeNode<K,V> pl = p.left, pr = p.right, q;
1851 if ((ph = p.hash) > h)
1852 p = pl;
1853 else if (ph < h)
1854 p = pr;
1855 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
1856 return p;
1857 else if (pl == null)
1858 p = pr;
1859 else if (pr == null)
1860 p = pl;
1861 else if ((kc = comparableClassFor(kc, k)) != void.class &&
1862 (dir = compareComparables(kc, k, pk)) != 0)
1863 p = (dir < 0) ? pl : pr;
1864 else if ((q = pr.find(h, k, kc)) != null)
1865 return q;
1866 else
1867 p = pl;
1868 } while (p != null);
1869 return null;
1870 }
1871
1872 /**
1873 * Calls find for root node.
1874 */
1875 final TreeNode<K,V> getTreeNode(int h, Object k) {
1876 return ((parent != null) ? root() : this).find(h, k, null);
1877 }
1878
1879 /**
1880 * Tie-breaking utility for ordering insertions when equal
1881 * hashCodes and non-comparable. We don't require a total
1901 TreeNode<K,V> root = null;
1902 for (TreeNode<K,V> x = this, next; x != null; x = next) {
1903 next = (TreeNode<K,V>)x.next;
1904 x.left = x.right = null;
1905 if (root == null) {
1906 x.parent = null;
1907 x.red = false;
1908 root = x;
1909 }
1910 else {
1911 K k = x.key;
1912 int h = x.hash;
1913 Class<?> kc = null;
1914 for (TreeNode<K,V> p = root;;) {
1915 int dir, ph;
1916 K pk = p.key;
1917 if ((ph = p.hash) > h)
1918 dir = -1;
1919 else if (ph < h)
1920 dir = 1;
1921 else if ((kc = comparableClassFor(kc, k)) == void.class ||
1922 (dir = compareComparables(kc, k, pk)) == 0)
1923 dir = tieBreakOrder(k, pk);
1924
1925 TreeNode<K,V> xp = p;
1926 if ((p = (dir <= 0) ? p.left : p.right) == null) {
1927 x.parent = xp;
1928 if (dir <= 0)
1929 xp.left = x;
1930 else
1931 xp.right = x;
1932 root = balanceInsertion(root, x);
1933 break;
1934 }
1935 }
1936 }
1937 }
1938 moveRootToFront(tab, root);
1939 }
1940
1941 /**
1954 }
1955 return hd;
1956 }
1957
1958 /**
1959 * Tree version of putVal.
1960 */
1961 final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
1962 int h, K k, V v) {
1963 Class<?> kc = null;
1964 boolean searched = false;
1965 TreeNode<K,V> root = (parent != null) ? root() : this;
1966 for (TreeNode<K,V> p = root;;) {
1967 int dir, ph; K pk;
1968 if ((ph = p.hash) > h)
1969 dir = -1;
1970 else if (ph < h)
1971 dir = 1;
1972 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
1973 return p;
1974 else if ((kc = comparableClassFor(kc, k)) == void.class ||
1975 (dir = compareComparables(kc, k, pk)) == 0) {
1976 if (!searched) {
1977 TreeNode<K,V> q, ch;
1978 searched = true;
1979 if (((ch = p.left) != null &&
1980 (q = ch.find(h, k, kc)) != null) ||
1981 ((ch = p.right) != null &&
1982 (q = ch.find(h, k, kc)) != null))
1983 return q;
1984 }
1985 dir = tieBreakOrder(k, pk);
1986 }
1987
1988 TreeNode<K,V> xp = p;
1989 if ((p = (dir <= 0) ? p.left : p.right) == null) {
1990 Node<K,V> xpn = xp.next;
1991 TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
1992 if (dir <= 0)
1993 xp.left = x;
1994 else
|