1 /*
   2  * Copyright (c) 2017, 2017, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.


















  22  */
  23 
  24 
  25 package jdk.internal.vm.compiler.collections;
  26 
  27 import java.util.Iterator;
  28 import java.util.Objects;
  29 import java.util.function.BiFunction;
  30 
  31 /**
  32  * Implementation of a map with a memory-efficient structure that always preserves insertion order
  33  * when iterating over keys. Particularly efficient when number of entries is 0 or smaller equal
  34  * {@link #INITIAL_CAPACITY} or smaller 256.
  35  *
  36  * The key/value pairs are kept in an expanding flat object array with keys at even indices and
  37  * values at odd indices. If the map has smaller or equal to {@link #HASH_THRESHOLD} entries, there
  38  * is no additional hash data structure and comparisons are done via linear checking of the
  39  * key/value pairs. For the case where the equality check is particularly cheap (e.g., just an
  40  * object identity comparison), this limit below which the map is without an actual hash table is
  41  * higher and configured at {@link #HASH_THRESHOLD_IDENTITY_COMPARE}.
  42  *
  43  * When the hash table needs to be constructed, the field {@link #hashArray} becomes a new hash
  44  * array where an entry of 0 means no hit and otherwise denotes the entry number in the

   1 /*
   2  * Copyright (c) 2017, 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * The Universal Permissive License (UPL), Version 1.0
   6  *
   7  * Subject to the condition set forth below, permission is hereby granted to any
   8  * person obtaining a copy of this software, associated documentation and/or
   9  * data (collectively the "Software"), free of charge and under any and all
  10  * copyright rights in the Software, and any and all patent rights owned or
  11  * freely licensable by each licensor hereunder covering either (i) the
  12  * unmodified Software as contributed to or provided by such licensor, or (ii)
  13  * the Larger Works (as defined below), to deal in both
  14  *
  15  * (a) the Software, and
  16  *
  17  * (b) any piece of software and/or hardware listed in the lrgrwrks.txt file if
  18  * one is included with the Software each a "Larger Work" to which the Software
  19  * is contributed by such licensors),
  20  *
  21  * without restriction, including without limitation the rights to copy, create
  22  * derivative works of, display, perform, and distribute the Software and make,
  23  * use, sell, offer for sale, import, export, have made, and have sold the
  24  * Software and the Larger Work(s), and to sublicense the foregoing rights on
  25  * either these or other terms.
  26  *
  27  * This license is subject to the following condition:
  28  *
  29  * The above copyright notice and either this complete permission notice or at a
  30  * minimum a reference to the UPL must be included in all copies or substantial
  31  * portions of the Software.
  32  *
  33  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  34  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  35  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  36  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  37  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  38  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  39  * SOFTWARE.
  40  */


  41 package jdk.internal.vm.compiler.collections;
  42 
  43 import java.util.Iterator;
  44 import java.util.Objects;
  45 import java.util.function.BiFunction;
  46 
  47 /**
  48  * Implementation of a map with a memory-efficient structure that always preserves insertion order
  49  * when iterating over keys. Particularly efficient when number of entries is 0 or smaller equal
  50  * {@link #INITIAL_CAPACITY} or smaller 256.
  51  *
  52  * The key/value pairs are kept in an expanding flat object array with keys at even indices and
  53  * values at odd indices. If the map has smaller or equal to {@link #HASH_THRESHOLD} entries, there
  54  * is no additional hash data structure and comparisons are done via linear checking of the
  55  * key/value pairs. For the case where the equality check is particularly cheap (e.g., just an
  56  * object identity comparison), this limit below which the map is without an actual hash table is
  57  * higher and configured at {@link #HASH_THRESHOLD_IDENTITY_COMPARE}.
  58  *
  59  * When the hash table needs to be constructed, the field {@link #hashArray} becomes a new hash
  60  * array where an entry of 0 means no hit and otherwise denotes the entry number in the