/*

 * Copyright (c) 2017, 2017, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package org.graalvm.util.impl;

import java.util.Iterator;

import java.util.Objects;

import java.util.function.BiFunction;

import org.graalvm.util.Equivalence;

import org.graalvm.util.EconomicMap;

import org.graalvm.util.EconomicSet;

import org.graalvm.util.UnmodifiableEconomicMap;

import org.graalvm.util.UnmodifiableEconomicSet;

import org.graalvm.util.MapCursor;

/**

 * Implementation of a map with a memory-efficient structure that always preserves insertion order

 * when iterating over keys. Particularly efficient when number of entries is 0 or smaller equal

 * {@link #INITIAL_CAPACITY} or smaller 256.

 *

 * The key/value pairs are kept in an expanding flat object array with keys at even indices and

 * values at odd indices. If the map has smaller or equal to {@link #HASH_THRESHOLD} entries, there

 * is no additional hash data structure and comparisons are done via linear checking of the

 * key/value pairs. For the case where the equality check is particularly cheap (e.g., just an

 * object identity comparison), this limit below which the map is without an actual hash table is

 * higher and configured at {@link #HASH_THRESHOLD_IDENTITY_COMPARE}.

 *

 * When the hash table needs to be constructed, the field {@link #hashArray} becomes a new hash

 * array where an entry of 0 means no hit and otherwise denotes the entry number in the

 * {@link #entries} array. The hash array is interpreted as an actual byte array if the indices fit

 * within 8 bit, or as an array of short values if the indices fit within 16 bit, or as an array of

 * integer values in other cases.

 *

 * Hash collisions are handled by chaining a linked list of {@link CollisionLink} objects that take

 * the place of the values in the {@link #entries} array.

 *

 * Removing entries will put {@code null} into the {@link #entries} array. If the occupation of the

 * map falls below a specific threshold, the map will be compressed via the

 * {@link #maybeCompress(int)} method.

 */

public final class EconomicMapImpl<K, V> implements EconomicMap<K, V>, EconomicSet<K> {

    /**

     * Initial number of key/value pair entries that is allocated in the first entries array.

     */

    private static final int INITIAL_CAPACITY = 4;

    /**

     * Maximum number of entries that are moved linearly forward if a key is removed.

     */

    private static final int COMPRESS_IMMEDIATE_CAPACITY = 8;

    /**

     * Minimum number of key/value pair entries added when the entries array is increased in size.

     */

    private static final int MIN_CAPACITY_INCREASE = 8;

    /**

     * Number of entries above which a hash table is created.

     */

    private static final int HASH_THRESHOLD = 4;

    /**

     * Number of entries above which a hash table is created when equality can be checked with

     * object identity.

     */

    private static final int HASH_THRESHOLD_IDENTITY_COMPARE = 8;

    /**

     * Maximum number of entries allowed in the map.

     */

    private static final int MAX_ELEMENT_COUNT = Integer.MAX_VALUE >> 1;

    /**

     * Number of entries above which more than 1 byte is necessary for the hash index.

     */

    private static final int LARGE_HASH_THRESHOLD = ((1 << Byte.SIZE) << 1);

    /**

     * Number of entries above which more than 2 bytes are are necessary for the hash index.

     */

    private static final int VERY_LARGE_HASH_THRESHOLD = (LARGE_HASH_THRESHOLD << Byte.SIZE);

    /**

     * Total number of entries (actual entries plus deleted entries).

     */

    private int totalEntries;

    /**

     * Number of deleted entries.

     */

    private int deletedEntries;

    /**

     * Entries array with even indices storing keys and odd indices storing values.

     */

    private Object[] entries;

    /**

     * Hash array that is interpreted either as byte or short or int array depending on number of

     * map entries.

     */

    private byte[] hashArray;

    /**

     * The strategy used for comparing keys or {@code null} for denoting special strategy

     * {@link Equivalence#IDENTITY}.

     */

    private final Equivalence strategy;

    /**

     * Intercept method for debugging purposes.

     */

    private static <K, V> EconomicMapImpl<K, V> intercept(EconomicMapImpl<K, V> map) {

        return map;

    }

    public static <K, V> EconomicMapImpl<K, V> create(Equivalence strategy) {

        return intercept(new EconomicMapImpl<>(strategy));

    }

    public static <K, V> EconomicMapImpl<K, V> create(Equivalence strategy, int initialCapacity) {

        return intercept(new EconomicMapImpl<>(strategy, initialCapacity));

    }

    public static <K, V> EconomicMapImpl<K, V> create(Equivalence strategy, UnmodifiableEconomicMap<K, V> other) {

        return intercept(new EconomicMapImpl<>(strategy, other));

    }

    public static <K, V> EconomicMapImpl<K, V> create(Equivalence strategy, UnmodifiableEconomicSet<K> other) {

        return intercept(new EconomicMapImpl<>(strategy, other));

    }

    private EconomicMapImpl(Equivalence strategy) {

        if (strategy == Equivalence.IDENTITY) {

            this.strategy = null;

        } else {

            this.strategy = strategy;

        }

    }

    private EconomicMapImpl(Equivalence strategy, int initialCapacity) {

        this(strategy);

        init(initialCapacity);

    }

    private EconomicMapImpl(Equivalence strategy, UnmodifiableEconomicMap<K, V> other) {

        this(strategy);

        if (!initFrom(other)) {

            init(other.size());

            putAll(other);

        }

    }

    private EconomicMapImpl(Equivalence strategy, UnmodifiableEconomicSet<K> other) {

        this(strategy);

        if (!initFrom(other)) {

            init(other.size());

            addAll(other);

        }

    }

    @SuppressWarnings("unchecked")

    private boolean initFrom(Object o) {

        if (o instanceof EconomicMapImpl) {

            EconomicMapImpl<K, V> otherMap = (EconomicMapImpl<K, V>) o;

            // We are only allowed to directly copy if the strategies of the two maps are the same.

            if (strategy == otherMap.strategy) {

                totalEntries = otherMap.totalEntries;

                deletedEntries = otherMap.deletedEntries;

                if (otherMap.entries != null) {

                    entries = otherMap.entries.clone();

                }

                if (otherMap.hashArray != null) {

                    hashArray = otherMap.hashArray.clone();

                }

                return true;

            }

        }

        return false;

    }

    private void init(int size) {

        if (size > INITIAL_CAPACITY) {

            entries = new Object[size << 1];

        }

    }

    /**

     * Links the collisions. Needs to be immutable class for allowing efficient shallow copy from

     * other map on construction.

     */

    private static final class CollisionLink {

        CollisionLink(Object value, int next) {

            this.value = value;

            this.next = next;

        }

        final Object value;

        /**

         * Index plus one of the next entry in the collision link chain.

         */

        final int next;

    }

    @SuppressWarnings("unchecked")

    @Override

    public V get(K key) {

        Objects.requireNonNull(key);

        int index = find(key);

        if (index != -1) {

            return (V) getValue(index);

        }

        return null;

    }

    private int find(K key) {

        if (hasHashArray()) {

            return findHash(key);

        } else {

            return findLinear(key);

        }

    }

    private int findLinear(K key) {

        for (int i = 0; i < totalEntries; i++) {

            Object entryKey = entries[i << 1];

            if (entryKey != null && compareKeys(key, entryKey)) {

                return i;

            }

        }

        return -1;

    }

    private boolean compareKeys(Object key, Object entryKey) {

        if (key == entryKey) {

            return true;

        }

        if (strategy != null && strategy != Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE) {

            if (strategy == Equivalence.DEFAULT) {

                return key.equals(entryKey);

            } else {

                return strategy.equals(key, entryKey);

            }

        }

        return false;

    }

    private int findHash(K key) {

        int index = getHashArray(getHashIndex(key)) - 1;

        if (index != -1) {

            Object entryKey = getKey(index);

            if (compareKeys(key, entryKey)) {

                return index;

            } else {

                Object entryValue = getRawValue(index);

                if (entryValue instanceof CollisionLink) {

                    return findWithCollision(key, (CollisionLink) entryValue);

                }

            }

        }

        return -1;

    }

    private int findWithCollision(K key, CollisionLink initialEntryValue) {

        int index;

        Object entryKey;

        CollisionLink entryValue = initialEntryValue;

        while (true) {

            CollisionLink collisionLink = entryValue;

            index = collisionLink.next;

            entryKey = getKey(index);

            if (compareKeys(key, entryKey)) {

                return index;

            } else {

                Object value = getRawValue(index);

                if (value instanceof CollisionLink) {

                    entryValue = (CollisionLink) getRawValue(index);

                } else {

                    return -1;

                }

            }

        }

    }

    private int getHashArray(int index) {

        if (entries.length < LARGE_HASH_THRESHOLD) {

            return (hashArray[index] & 0xFF);

        } else if (entries.length < VERY_LARGE_HASH_THRESHOLD) {

            int adjustedIndex = index << 1;

            return (hashArray[adjustedIndex] & 0xFF) | ((hashArray[adjustedIndex + 1] & 0xFF) << 8);

        } else {

            int adjustedIndex = index << 2;

            return (hashArray[adjustedIndex] & 0xFF) | ((hashArray[adjustedIndex + 1] & 0xFF) << 8) | ((hashArray[adjustedIndex + 2] & 0xFF) << 16) | ((hashArray[adjustedIndex + 3] & 0xFF) << 24);

        }

    }

    private void setHashArray(int index, int value) {

        if (entries.length < LARGE_HASH_THRESHOLD) {

            hashArray[index] = (byte) value;

        } else if (entries.length < VERY_LARGE_HASH_THRESHOLD) {

            int adjustedIndex = index << 1;

            hashArray[adjustedIndex] = (byte) value;

            hashArray[adjustedIndex + 1] = (byte) (value >> 8);

        } else {

            int adjustedIndex = index << 2;

            hashArray[adjustedIndex] = (byte) value;

            hashArray[adjustedIndex + 1] = (byte) (value >> 8);

            hashArray[adjustedIndex + 2] = (byte) (value >> 16);

            hashArray[adjustedIndex + 3] = (byte) (value >> 24);

        }

    }

    private int findAndRemoveHash(Object key) {

        int hashIndex = getHashIndex(key);

        int index = getHashArray(hashIndex) - 1;

        if (index != -1) {

            Object entryKey = getKey(index);

            if (compareKeys(key, entryKey)) {

                Object value = getRawValue(index);

                int nextIndex = -1;

                if (value instanceof CollisionLink) {

                    CollisionLink collisionLink = (CollisionLink) value;

                    nextIndex = collisionLink.next;

                }

                setHashArray(hashIndex, nextIndex + 1);

                return index;

            } else {

                Object entryValue = getRawValue(index);

                if (entryValue instanceof CollisionLink) {

                    return findAndRemoveWithCollision(key, (CollisionLink) entryValue, index);

                }

            }

        }

        return -1;

    }

    private int findAndRemoveWithCollision(Object key, CollisionLink initialEntryValue, int initialIndexValue) {

        int index;

        Object entryKey;

        CollisionLink entryValue = initialEntryValue;

        int lastIndex = initialIndexValue;

        while (true) {

            CollisionLink collisionLink = entryValue;

            index = collisionLink.next;

            entryKey = getKey(index);

            if (compareKeys(key, entryKey)) {

                Object value = getRawValue(index);

                if (value instanceof CollisionLink) {

                    CollisionLink thisCollisionLink = (CollisionLink) value;

                    setRawValue(lastIndex, new CollisionLink(collisionLink.value, thisCollisionLink.next));

                } else {

                    setRawValue(lastIndex, collisionLink.value);

                }

                return index;

            } else {

                Object value = getRawValue(index);

                if (value instanceof CollisionLink) {

                    entryValue = (CollisionLink) getRawValue(index);

                    lastIndex = index;

                } else {

                    return -1;

                }

            }

        }

    }

    private int getHashIndex(Object key) {

        int hash;

        if (strategy != null && strategy != Equivalence.DEFAULT) {

            if (strategy == Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE) {

                hash = System.identityHashCode(key);

            } else {

                hash = strategy.hashCode(key);

            }

        } else {

            hash = key.hashCode();

        }

        hash = hash ^ (hash >>> 16);

        return hash & (getHashTableSize() - 1);

    }

    @SuppressWarnings("unchecked")

    @Override

    public V put(K key, V value) {

        if (key == null) {

            throw new UnsupportedOperationException("null not supported as key!");

        }

        int index = find(key);

        if (index != -1) {

            Object oldValue = getValue(index);

            setValue(index, value);

            return (V) oldValue;

        }

        int nextEntryIndex = totalEntries;

        if (entries == null) {

            entries = new Object[INITIAL_CAPACITY << 1];

        } else if (entries.length == nextEntryIndex << 1) {

            grow();

            assert entries.length > totalEntries << 1;

            // Can change if grow is actually compressing.

            nextEntryIndex = totalEntries;

        }

        setKey(nextEntryIndex, key);

        setValue(nextEntryIndex, value);

        totalEntries++;

        if (hasHashArray()) {

            // Rehash on collision if hash table is more than three quarters full.

            boolean rehashOnCollision = (getHashTableSize() < (size() + (size() >> 1)));

            putHashEntry(key, nextEntryIndex, rehashOnCollision);

        } else if (totalEntries > getHashThreshold()) {

            createHash();

        }

        return null;

    }

    /**

     * Number of entries above which a hash table should be constructed.

     */

    private int getHashThreshold() {

        if (strategy == null || strategy == Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE) {

            return HASH_THRESHOLD_IDENTITY_COMPARE;

        } else {

            return HASH_THRESHOLD;

        }

    }

    private void grow() {

        int entriesLength = entries.length;

        int newSize = (entriesLength >> 1) + Math.max(MIN_CAPACITY_INCREASE, entriesLength >> 2);

        if (newSize > MAX_ELEMENT_COUNT) {

            throw new UnsupportedOperationException("map grown too large!");

        }

        Object[] newEntries = new Object[newSize << 1];

        System.arraycopy(entries, 0, newEntries, 0, entriesLength);

        entries = newEntries;

        if ((entriesLength < LARGE_HASH_THRESHOLD && newEntries.length >= LARGE_HASH_THRESHOLD) ||

                        (entriesLength < VERY_LARGE_HASH_THRESHOLD && newEntries.length > VERY_LARGE_HASH_THRESHOLD)) {

            // Rehash in order to change number of bits reserved for hash indices.

            createHash();

        }

    }

    /**

     * Compresses the graph if there is a large number of deleted entries and returns the translated

     * new next index.

     */

    private int maybeCompress(int nextIndex) {

        if (entries.length != INITIAL_CAPACITY << 1 && deletedEntries >= (totalEntries >> 1) + (totalEntries >> 2)) {

            return compressLarge(nextIndex);

        }

        return nextIndex;

    }

    /**

     * Compresses the graph and returns the translated new next index.

     */

    private int compressLarge(int nextIndex) {

        int size = INITIAL_CAPACITY;

        int remaining = totalEntries - deletedEntries;

        while (size <= remaining) {

            size += Math.max(MIN_CAPACITY_INCREASE, size >> 1);

        }

        Object[] newEntries = new Object[size << 1];

        int z = 0;

        int newNextIndex = remaining;

        for (int i = 0; i < totalEntries; ++i) {

            Object key = getKey(i);

            if (i == nextIndex) {

                newNextIndex = z;

            }

            if (key != null) {

                newEntries[z << 1] = key;

                newEntries[(z << 1) + 1] = getValue(i);

                z++;

            }

        }

        this.entries = newEntries;

        totalEntries = z;

        deletedEntries = 0;

        if (z <= getHashThreshold()) {

            this.hashArray = null;

        } else {

            createHash();

        }

        return newNextIndex;

    }

    private int getHashTableSize() {

        if (entries.length < LARGE_HASH_THRESHOLD) {

            return hashArray.length;

        } else if (entries.length < VERY_LARGE_HASH_THRESHOLD) {

            return hashArray.length >> 1;

        } else {

            return hashArray.length >> 2;

        }