Function DeleteEntriesFromSpriteCache

src/spritecache.cpp:704–760

* Delete entries from the sprite cache to remove the requested number of bytes. * Sprite data is removed in order of LRU values. * The total number of bytes removed may be larger than the number requested. * @param to_remove Requested number of bytes to remove. */

 * @param to_remove Requested number of bytes to remove.
 */
static void DeleteEntriesFromSpriteCache(size_t to_remove)
{
	const size_t initial_in_use = _spritecache_bytes_used;

	struct SpriteInfo {
		uint32_t lru;
		SpriteID id;
		size_t size;

		bool operator<(const SpriteInfo &other) const
		{
			return this->lru < other.lru;
		}
	};

	std::vector<SpriteInfo> candidates; // max heap, ordered by LRU
	size_t candidate_bytes = 0;         // total bytes that would be released when clearing all sprites in candidates

	auto push = [&](SpriteInfo info) {
		candidates.push_back(info);
		std::push_heap(candidates.begin(), candidates.end());
		candidate_bytes += info.size;
	};

	auto pop = [&]() {
		candidate_bytes -= candidates.front().size;
		std::pop_heap(candidates.begin(), candidates.end());
		candidates.pop_back();
	};

	SpriteID i = 0;
	for (; i != static_cast<SpriteID>(_spritecache.size()) && candidate_bytes < to_remove; i++) {
		const SpriteCache *sc = GetSpriteCache(i);
		if (sc->ptr != nullptr) {
			push({ sc->lru, i, sc->length });
			if (candidate_bytes >= to_remove) break;
		}
	}
	/* candidates now contains enough bytes to meet to_remove.
	 * only sprites with LRU values <= the maximum (i.e. the top of the heap) need to be considered */
	for (; i != static_cast<SpriteID>(_spritecache.size()); i++) {
		const SpriteCache *sc = GetSpriteCache(i);
		if (sc->ptr != nullptr && sc->lru <= candidates.front().lru) {
			push({ sc->lru, i, sc->length });
			while (!candidates.empty() && candidate_bytes - candidates.front().size >= to_remove) {
				pop();
			}
		}
	}

	for (const auto &it : candidates) {
		GetSpriteCache(it.id)->ClearSpriteData();
	}

	Debug(sprite, 3, "DeleteEntriesFromSpriteCache, deleted: {}, freed: {}, in use: {} --> {}, requested: {}",
			candidates.size(), candidate_bytes, initial_in_use, _spritecache_bytes_used, to_remove);
}