Repository: microsoft/terminal
File: src/renderer/atlas/AtlasEngine.h (C/C++)

Code before:
            std::unordered_set<std::list<std::pair<AtlasKey, AtlasValue>>::iterator, AtlasKeyHasher, AtlasKeyEq> _map;
        };

        struct TileAllocator
        {
            TileAllocator() = default;

            explicit TileAllocator(u16x2 tileSize, u16x2 windowSize) noexcept :
                _tileSize{ tileSize }
            {
                const auto initialSize = std::max(u16{ _absoluteMinSize }, std::bit_ceil(std::max(tileSize.x, tileSize.y)));
                _size = { initialSize, initialSize };
                _limit = { gsl::narrow_cast<u16>(initialSize - _tileSize.x), gsl::narrow_cast<u16>(initialSize - _tileSize.y) };
                setMaxArea(windowSize);
            }

            u16x2 size() const noexcept
            {
                return _size;
            }

            void setMaxArea(u16x2 windowSize) noexcept
            {
                // _generate() uses a quadratic growth factor for _size's area.
                // Once it exceeds the _maxArea, it'll start snatching tiles back from the
                // TileHashMap using it's LRU queue. Since _size will at least reach half
                // of _maxSize (because otherwise it could still grow by a factor of 2)
                // and by ensuring that _maxArea is at least twice the window size
                // we make it impossible* for _generate() to return false before
                // TileHashMap contains at least as many tiles as the window contains.
                // If that wasn't the case we'd snatch and reuse tiles that are still in use.
                // * lhecker's legal department:
                //   No responsibility is taken for the correctness of this information.
                setMaxArea(static_cast<size_t>(windowSize.x) * static_cast<size_t>(windowSize.y) * 2);
            }

            void setMaxArea(size_t max) noexcept
            {
                _maxArea = clamp(max, _absoluteMinArea, _absoluteMaxArea);
                _updateCanGenerate();
            }

            u16x2 allocate(TileHashMap& map) noexcept
            {
                if (_generate())
                {
                    return _pos;
                }

                if (_cache.empty())
                {

Review comment (suggestion):
```suggestion
                // TileHashMap using its LRU queue. Since _size will at least reach half
```

Code after:
            // If you need a LRU hash-map, write a custom one with an intrusive
            // prev/next linked list (it's easier than you might think!).
            std::list<std::pair<AtlasKey, AtlasValue>> _lru;
            std::unordered_set<std::list<std::pair<AtlasKey, AtlasValue>>::iterator, AtlasKeyHasher, AtlasKeyEq> _map;
        };

        // TileAllocator yields `tileSize`-sized tiles for our texture atlas.
        // While doing so it'll grow the atlas size() by a factor of 2 if needed.
        // Once the setMaxArea() is exceeded it'll stop growing and instead
        // snatch tiles back from the oldest TileHashMap entries.
        //
        // The quadratic growth works by alternating the size()
        // between an 1:1 and 2:1 aspect ratio, like so:
        //   (64,64) -> (128,64) -> (128,128) -> (256,128) -> (256,256)
        // These initial tile positions allocate() returns are in a Z
        // pattern over the available space in the atlas texture.
        // You can log the `return _pos;` in allocate() using "Tracepoint"s
        // in Visual Studio if you'd like to understand the Z pattern better.
        struct TileAllocator
        {
            TileAllocator() = default;

            explicit TileAllocator(u16x2 tileSize, u16x2 windowSize) noexcept :
                _tileSize{ tileSize }
            {
                const auto initialSize = std::max(u16{ _absoluteMinSize }, std::bit_ceil(std::max(tileSize.x, tileSize.y)));
                _size = { initialSize, initialSize };
                _limit = { gsl::narrow_cast<u16>(initialSize - _tileSize.x), gsl::narrow_cast<u16>(initialSize - _tileSize.y) };
                setMaxArea(windowSize);
            }

            u16x2 size() const noexcept
            {
                return _size;
            }

            void setMaxArea(u16x2 windowSize) noexcept
            {
                // _generate() uses a quadratic growth factor for _size's area.
                // Once it exceeds the _maxArea, it'll start snatching tiles back from the
                // TileHashMap using its LRU queue. Since _size will at least reach half
                // of _maxSize (because otherwise it could still grow by a factor of 2)
                // and by ensuring that _maxArea is at least twice the window size
                // we make it impossible* for _generate() to return false before
                // TileHashMap contains at least as many tiles as the window contains.
                // If that wasn't the case we'd snatch and reuse tiles that are still in use.
                // * lhecker's legal department:
                //   No responsibility is taken for the correctness of this information.
                setMaxArea(static_cast<size_t>(windowSize.x) * static_cast<size_t>(windowSize.y) * 2);
            }