8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.io.IOException;
29 import java.io.InvalidObjectException;
30 import java.io.Serializable;
31 import java.lang.reflect.ParameterizedType;
32 import java.lang.reflect.Type;
33 import java.util.function.BiConsumer;
34 import java.util.function.BiFunction;
35 import java.util.function.Consumer;
36 import java.util.function.Function;
37
38 /**
39 * Hash table based implementation of the <tt>Map</tt> interface. This
40 * implementation provides all of the optional map operations, and permits
41 * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
42 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
43 * unsynchronized and permits nulls.) This class makes no guarantees as to
44 * the order of the map; in particular, it does not guarantee that the order
45 * will remain constant over time.
46 *
47 * <p>This implementation provides constant-time performance for the basic
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;
|
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import sun.misc.JavaLangAccess;
29 import sun.misc.SharedSecrets;
30
31 import java.io.IOException;
32 import java.io.InvalidObjectException;
33 import java.io.Serializable;
34 import java.lang.reflect.ParameterizedType;
35 import java.lang.reflect.Type;
36 import java.util.function.BiConsumer;
37 import java.util.function.BiFunction;
38 import java.util.function.Consumer;
39 import java.util.function.Function;
40
41 /**
42 * Hash table based implementation of the <tt>Map</tt> interface. This
43 * implementation provides all of the optional map operations, and permits
44 * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
45 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
46 * unsynchronized and permits nulls.) This class makes no guarantees as to
47 * the order of the map; in particular, it does not guarantee that the order
48 * will remain constant over time.
49 *
50 * <p>This implementation provides constant-time performance for the basic
325 * to lower. Because the table uses power-of-two masking, sets of
326 * hashes that vary only in bits above the current mask will
327 * always collide. (Among known examples are sets of Float keys
328 * holding consecutive whole numbers in small tables.) So we
329 * apply a transform that spreads the impact of higher bits
330 * downward. There is a tradeoff between speed, utility, and
331 * quality of bit-spreading. Because many common sets of hashes
332 * are already reasonably distributed (so don't benefit from
333 * spreading), and because we use trees to handle large sets of
334 * collisions in bins, we just XOR some shifted bits in the
335 * cheapest possible way to reduce systematic lossage, as well as
336 * to incorporate impact of the highest bits that would otherwise
337 * never be used in index calculations because of table bounds.
338 */
339 static final int hash(Object key) {
340 int h;
341 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
342 }
343
344 /**
345 * Function returning TRUE for given Class when it is safe to compare
346 * instances of it among themselves.
347 */
348 private static final Function<Class<?>, Boolean> isSelfComparableClass =
349 new Function<Class<?>, Boolean>() {
350 @Override
351 public Boolean apply(Class<?> c) {
352 Type[] ts, as; ParameterizedType p;
353 if ((ts = c.getGenericInterfaces()) != null) {
354 for (Type t : ts) {
355 if ((t instanceof ParameterizedType) &&
356 ((p = (ParameterizedType) t).getRawType() ==
357 Comparable.class) &&
358 (as = p.getActualTypeArguments()) != null &&
359 as.length == 1 && as[0] == c) // type arg is c
360 return Boolean.TRUE;
361 }
362 }
363 return Boolean.FALSE;
364 }
365 };
366
367 /**
368 * Returns x's Class if it is of the form "class C implements
369 * Comparable<C>", else null.
370 */
371 static Class<?> comparableClassFor(Object x) {
372 if (x instanceof Comparable) {
373 Class<?> c;
374 if ((c = x.getClass()) == String.class) { // bypass checks
375 return c;
376 }
377 JavaLangAccess jla = SharedSecrets.getJavaLangAccess();
378 Boolean scc = (jla != null)
379 ? jla.getGenericDerivative(c, isSelfComparableClass, isSelfComparableClass)
380 : isSelfComparableClass.apply(c); // in case very early in boot-up sequence
381 if (scc != null && scc) {
382 return c;
383 }
384 }
385 return null;
386 }
387
388 /**
389 * Returns k.compareTo(x) if x matches kc (k's screened comparable
390 * class), else 0.
391 */
392 @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
393 static int compareComparables(Class<?> kc, Object k, Object x) {
394 return (x == null || x.getClass() != kc ? 0 :
395 ((Comparable)k).compareTo(x));
396 }
397
398 /**
399 * Returns a power of two size for the given target capacity.
400 */
401 static final int tableSizeFor(int cap) {
402 int n = cap - 1;
|