source: frontend/node_modules/webpack/lib/util/StackedCacheMap.js

/*
        MIT License http://www.opensource.org/licenses/mit-license.php
        Author Tobias Koppers @sokra
*/

"use strict";

/**
 * The StackedCacheMap is a data structure designed as an alternative to a Map
 * in situations where you need to handle multiple item additions and
 * frequently access the largest map.
 *
 * It is particularly optimized for efficiently adding multiple items
 * at once, which can be achieved using the `addAll` method.
 *
 * It has a fallback Map that is used when the map to be added is mutable.
 *
 * Note: `delete` and `has` are not supported for performance reasons.
 * @example
 * ```js
 * const map = new StackedCacheMap();
 * map.addAll(new Map([["a", 1], ["b", 2]]), true);
 * map.addAll(new Map([["c", 3], ["d", 4]]), true);
 * map.get("a"); // 1
 * map.get("d"); // 4
 * for (const [key, value] of map) {
 *              console.log(key, value);
 * }
 * ```
 * @template K
 * @template V
 */
class StackedCacheMap {
        /**
         * Initializes the mutable fallback map and the stack of immutable cache
         * layers.
         */
        constructor() {
                /** @type {Map<K, V>} */
                this.map = new Map();
                /** @type {ReadonlyMap<K, V>[]} */
                this.stack = [];
        }

        /**
         * Adds another cache layer. Immutable maps are retained by reference and
         * reordered so larger layers are checked first, while mutable maps are
         * copied into the fallback map.
         * @param {ReadonlyMap<K, V>} map map to add
         * @param {boolean=} immutable if 'map' is immutable and StackedCacheMap can keep referencing it
         */
        addAll(map, immutable) {
                if (immutable) {
                        this.stack.push(map);

                        // largest map should go first
                        for (let i = this.stack.length - 1; i > 0; i--) {
                                const beforeLast = this.stack[i - 1];
                                if (beforeLast.size >= map.size) break;
                                this.stack[i] = beforeLast;
                                this.stack[i - 1] = map;
                        }
                } else {
                        for (const [key, value] of map) {
                                this.map.set(key, value);
                        }
                }
        }

        /**
         * Stores or overrides a value in the mutable fallback map.
         * @param {K} item the key of the element to add
         * @param {V} value the value of the element to add
         * @returns {void}
         */
        set(item, value) {
                this.map.set(item, value);
        }

        /**
         * Rejects deletions because this data structure is optimized for append-only
         * cache layers.
         * @param {K} item the item to delete
         * @returns {void}
         */
        delete(item) {
                throw new Error("Items can't be deleted from a StackedCacheMap");
        }

        /**
         * Rejects `has` checks because they would force the same layered lookup work
         * as `get` without returning the cached value.
         * @param {K} item the item to test
         * @returns {boolean} true if the item exists in this set
         */
        has(item) {
                throw new Error(
                        "Checking StackedCacheMap.has before reading is inefficient, use StackedCacheMap.get and check for undefined"
                );
        }

        /**
         * Looks up a key by scanning immutable cache layers first and then the
         * mutable fallback map.
         * @param {K} item the key of the element to return
         * @returns {V | undefined} the value of the element
         */
        get(item) {
                for (const map of this.stack) {
                        const value = map.get(item);
                        if (value !== undefined) return value;
                }
                return this.map.get(item);
        }

        /**
         * Removes every cache layer and clears the mutable fallback map.
         */
        clear() {
                this.stack.length = 0;
                this.map.clear();
        }

        /**
         * Returns the total number of entries across the fallback map and all stacked
         * cache layers.
         * @returns {number} size of the map
         */
        get size() {
                let size = this.map.size;
                for (const map of this.stack) {
                        size += map.size;
                }
                return size;
        }

        /**
         * Iterates over the fallback map first and then each stacked cache layer.
         * @returns {Iterator<[K, V]>} iterator
         */
        [Symbol.iterator]() {
                const iterators = this.stack.map((map) => map[Symbol.iterator]());
                let current = this.map[Symbol.iterator]();
                return {
                        next() {
                                let result = current.next();
                                while (result.done && iterators.length > 0) {
                                        current = /** @type {MapIterator<[K, V]>} */ (iterators.pop());
                                        result = current.next();
                                }
                                return result;
                        }
                };
        }
}

module.exports = StackedCacheMap;