#882

Committed 31 Aug 2023 07:44PM UTC coverage: 41.798% (-44.7%) from 86.546%

Build # #882

Build Type

push

Committed by

Commit Message

Run Details

19442 of 46514 relevant lines covered (41.8%)

126375.38 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

51.11

/libs/core/cache/include/hpx/cache/lru_cache.hpp

//  Copyright (c) 2016 Thomas Heller
//  Copyright (c) 2022-2025 Hartmut Kaiser
//
//  SPDX-License-Identifier: BSL-1.0
//  Distributed under the Boost Software License, Version 1.0. (See accompanying
//  file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#pragma once

#include <hpx/config.hpp>
#include <hpx/cache/statistics/no_statistics.hpp>

#include <cstddef>
#include <list>
#include <map>
#include <type_traits>
#include <utility>

///////////////////////////////////////////////////////////////////////////////
namespace hpx::util::cache {

    ///////////////////////////////////////////////////////////////////////////
    /// \class lru_cache lru_cache.hpp hpx/cache/lru_cache.hpp
    ///
    /// \brief The \a lru_cache implements the basic functionality needed for
    ///        a local (non-distributed) LRU cache.
    ///
    /// \tparam Key           The type of the keys to use to identify the
    ///                       entries stored in the cache
    /// \tparam Entry         The type of the items to be held in the cache.
    /// \tparam Statistics    A (optional) type allowing to collect some basic
    ///                       statistics about the operation of the cache
    ///                       instance. The type must conform to the
    ///                       CacheStatistics concept. The default value is
    ///                       the type \a statistics#no_statistics which does
    ///                       not collect any numbers, but provides empty stubs
    ///                       allowing the code to compile.
    HPX_CXX_EXPORT template <typename Key, typename Entry,
        typename Statistics = statistics::no_statistics>
    class lru_cache
    {
    public:
        using key_type = Key;
        using entry_type = Entry;
        using statistics_type = Statistics;
        using entry_pair = std::pair<key_type, entry_type>;
        using storage_type = std::list<entry_pair>;
        using map_type = std::map<Key, typename storage_type::iterator>;
        using size_type = std::size_t;

    private:
        using update_on_exit = typename statistics_type::update_on_exit;

    public:
        ///////////////////////////////////////////////////////////////////////
        /// \brief Construct an instance of a lru_cache.
        ///
        /// \param max_size   [in] The maximal size this cache is allowed to
        ///                   reach any time. The default is zero (no size
        ///                   limitation). The unit of this value is usually
        ///                   determined by the unit of the values returned by
        ///                   the entry's \a get_size function.
        ///
        explicit lru_cache(size_type max_size = 0)
          : max_size_(max_size)
        {
        }

        lru_cache(lru_cache const& other) = default;
        lru_cache(lru_cache&& other) = default;
        lru_cache& operator=(lru_cache const& other) = default;
        lru_cache& operator=(lru_cache&& other) = default;

        ~lru_cache() = default;

        ///////////////////////////////////////////////////////////////////////
        /// \brief Return current size of the cache.
        ///
        /// \returns The current size of this cache instance.
        [[nodiscard]] constexpr size_type size() const noexcept
        {
            return current_size_;
        }

        ///////////////////////////////////////////////////////////////////////
        /// \brief Access the maximum size the cache is allowed to grow to.
        ///
        /// \note       The unit of this value is usually determined by the
        ///             unit of the return values of the entry's function
        ///             \a entry#get_size.
        ///
        /// \returns    The maximum size this cache instance is currently
        ///             allowed to reach. If this number is zero the cache has
        ///             no limitation with regard to a maximum size.
        [[nodiscard]] constexpr size_type capacity() const noexcept
        {
            return max_size_;
        }

        ///////////////////////////////////////////////////////////////////////
        /// \brief Change the maximum size this cache can grow to
        ///
        /// \param max_size    [in] The new maximum size this cache will be
        ///             allowed to grow to.
        ///
        void reserve(size_type max_size)
        {
            if (max_size > max_size_)
            {
                max_size_ = max_size;
                return;
            }

            max_size_ = max_size;
            while (current_size_ > max_size_)    //-V776
            {
                evict();
            }
        }

        ///////////////////////////////////////////////////////////////////////
        /// \brief Check whether the cache currently holds an entry identified
        ///        by the given key
        ///
        /// \param key    [in] The key for the entry which should be looked up
        ///               in the cache.
        ///
        /// \note         This function does not call the entry's function
        ///               \a entry#touch. It just checks if the cache contains
        ///               an entry corresponding to the given key.
        ///
        /// \returns      This function returns \a true if the cache holds the
        ///               referenced entry, otherwise it returns \a false.
        [[nodiscard]] bool holds_key(key_type const& key) const
        {
            return map_.find(key) != map_.end();
        }

        ///////////////////////////////////////////////////////////////////////
        /// \brief Get a specific entry identified by the given key.
        ///
        /// \param key     [in] The key for the entry which should be retrieved
        ///               from the cache.
        /// \param realkey[out] Return the full real key found in the cache
        /// \param entry  [out] If the entry indexed by the key is found in the
        ///               cache this value on successful return will be a copy
        ///               of the corresponding entry.
        ///
        /// \note         The function will "touch" the entry and mark it as recently
        ///               used if the key was found in the cache.
        ///
        /// \returns      This function returns \a true if the cache holds the
        ///               referenced entry, otherwise it returns \a false.
        bool get_entry(
            key_type const& key, key_type& realkey, entry_type& entry)
        {
            update_on_exit update(statistics_, statistics::method::get_entry);

            auto it = map_.find(key);

            if (it == map_.end())
            {
                // Got miss
                statistics_.got_miss();    // update statistics
                return false;
            }

            touch(it->second);

            // update statistics
            statistics_.got_hit();

            // got hit
            realkey = it->first;
            entry = it->second->second;

            return true;
        }

        ///////////////////////////////////////////////////////////////////////
        /// \brief Get a specific entry identified by the given key.
        ///
        /// \param key    [in] The key for the entry which should be retrieved
        ///               from the cache.
        /// \param entry  [out] If the entry indexed by the key is found in the
        ///               cache this value on successful return will be a copy
        ///               of the corresponding entry.
        ///
        /// \note         The function will "touch" the entry and mark it as recently
        ///               used if the key was found in the cache.
        ///
        /// \returns      This function returns \a true if the cache holds the
        ///               referenced entry, otherwise it returns \a false.
        bool get_entry(key_type const& key, entry_type const& entry)
        {
            key_type tmp;
            return get_entry(key, tmp, entry);
        }

        /// \brief Insert a new entry into this cache
        ///
        /// \param key    [in] The key for the entry which should be added to
        ///               the cache.
        /// \param entry  [in] The entry which should be added to the cache.
        ///
        /// \note         This function assumes that the entry is not in the
        ///               cache already. Inserting an already existing entry
        ///               is considered undefined behavior
        template <typename Entry_,
            typename = std::enable_if_t<
                std::is_convertible_v<std::decay_t<Entry_>, entry_type>>>
        bool insert(key_type const& key, Entry_&& entry)
        {
            update_on_exit update(
                statistics_, statistics::method::insert_entry);
            if (map_.find(key) != map_.end())
            {
                return false;
            }

            insert_nonexist(key, HPX_FORWARD(Entry_, entry));
            return true;
        }

    private:
        template <typename Entry_,
            typename = std::enable_if_t<
                std::is_convertible_v<std::decay_t<Entry_>, entry_type>>>
        void insert_nonexist(key_type const& key, Entry_&& entry)
        {
            // insert ...
            storage_.emplace_front(key, HPX_FORWARD(Entry_, entry));
            map_[key] = storage_.begin();
            ++current_size_;

            // update statistics
            statistics_.got_insertion();

            // Do we need to evict a cache entry?
            if (current_size_ > max_size_)
            {
                // evict an entry
                evict();
            }
        }

    public:
        ///////////////////////////////////////////////////////////////////////
        /// \brief Update an existing element in this cache
        ///
        /// \param key    [in] The key for the value which should be updated in
        ///               the cache.
        /// \param entry  [in] The entry which should be used as a replacement
        ///               for the existing value in the cache. Any existing
        ///               cache entry is not changed except for its value.
        ///
        /// \note         The function will "touch" the entry and mark it as recently
        ///               used if the key was found in the cache.
        /// \note         The difference to the other overload of the \a insert
        ///               function is that this overload replaces the cached
        ///               value only, while the other overload replaces the
        ///               whole cache entry, updating the cache entry
        ///               properties.
        template <typename Entry_,
            typename = std::enable_if_t<
                std::is_convertible_v<std::decay_t<Entry_>, entry_type>>>
        void update(key_type const& key, Entry_&& entry)
        {
            update_on_exit update(
                statistics_, statistics::method::update_entry);

            // Is it already in the cache?
            auto it = map_.find(key);
            if (it == map_.end())
            {
                // got miss
                statistics_.got_miss();    // update statistics
                insert_nonexist(key, HPX_FORWARD(Entry_, entry));
                return;
            }

            // got hit!
            it->second->second = HPX_FORWARD(Entry_, entry);
            touch(it->second);

            // update statistics
            statistics_.got_hit();
        }

        ///////////////////////////////////////////////////////////////////////
        /// \brief Update an existing element in this cache
        ///
        /// \param key    [in] The key for the value which should be updated in
        ///               the cache.
        /// \param entry  [in] The value which should be used as a replacement
        ///               for the existing value in the cache. Any existing
        ///               cache entry is not changed except for its value.
        /// \param f      [in] A callable taking two arguments, \a k and the
        ///               key found in the cache (in that order). If \a f
        ///               returns true, then the update will continue. If \a f
        ///               returns false, then the update will not succeed.
        ///
        /// \note         The function will "touch" the entry and mark it as recently
        ///               used if the key was found in the cache.
        /// \note         The difference to the other overload of the \a insert
        ///               function is that this overload replaces the cached
        ///               value only, while the other overload replaces the
        ///               whole cache entry, updating the cache entry
        ///               properties.
        ///
        /// \returns      This function returns \a true if the entry has been
        ///               successfully updated, otherwise it returns \a false.
        ///               If the entry currently is not held by the cache it is
        ///               added and the return value reflects the outcome of
        ///               the corresponding insert operation.
        template <typename F, typename Entry_,
            std::enable_if_t<
                std::is_convertible_v<std::decay_t<Entry_>, entry_type>, int> =
                0>
        bool update_if(key_type const& key, Entry_&& entry, F&& f)
        {
            update_on_exit update(
                statistics_, statistics::method::update_entry);

            // Is it already in the cache?
            auto it = map_.find(key);
            if (it == map_.end())
            {
                // got miss
                statistics_.got_miss();    // update statistics
                insert_nonexist(key, HPX_FORWARD(Entry_, entry));
                return true;
            }

            if (f(key, it->first))
                return false;

            // got hit!
            touch(it->second);
            it->second->second = HPX_FORWARD(Entry_, entry);

            // update statistics
            statistics_.got_hit();

            return true;
        }

        ///////////////////////////////////////////////////////////////////////
        /// \brief Remove stored entries from the cache for which the supplied
        ///        function object returns true.
        ///
        /// \param ep     [in] This parameter has to be a (unary) function
        ///               object. It is invoked for each of the entries
        ///               currently held in the cache. An entry is considered
        ///               for removal from the cache whenever the value
        ///               returned from this invocation is \a true.
        ///
        /// \returns      This function returns the overall size of the removed
        ///               entries (which is the sum of the values returned by
        ///               the \a entry#get_size functions of the removed
        ///               entries).
        template <typename Func>
        size_type erase(Func const& ep)
        {
            update_on_exit update(statistics_, statistics::method::erase_entry);

            size_type erased = 0;
            for (auto it = map_.begin(); it != map_.end();)
            {
                auto jt = it->second;
                if (ep(*jt))
                {
                    ++erased;

                    storage_.erase(jt);
                    it = map_.erase(it);

                    // update statistics
                    statistics_.got_eviction();
                }
                else
                {
                    ++it;
                }
            }

            return erased;
        }

        /// \brief Remove all stored entries from the cache
        ///
        /// \returns      This function returns the overall size of the removed
        ///               entries (which is the sum of the values returned by
        ///               the \a entry#get_size functions of the removed
        ///               entries).
        size_type erase()
        {
            std::size_t const current_size = current_size_;
            clear();
            return current_size;
        }

        /// \brief Clear the cache
        ///
        /// Unconditionally removes all stored entries from the cache.
        size_type clear()
        {
            size_type const erased = current_size_;
            current_size_ = 0;
            map_.clear();
            storage_.clear();
            return erased;
        }

        ///////////////////////////////////////////////////////////////////////
        /// \brief Allow to access the embedded statistics instance
        ///
        /// \returns      This function returns a reference to the statistics
        ///               instance embedded inside this cache
        [[nodiscard]] constexpr statistics_type const& get_statistics()
            const noexcept
        {
            return statistics_;
        }

        [[nodiscard]] statistics_type& get_statistics() noexcept
        {
            return statistics_;
        }

    private:
        void touch(typename storage_type::iterator it)
        {
            storage_.splice(storage_.begin(), storage_, it);
        }

        void evict()
        {
            statistics_.got_eviction();
            map_.erase(storage_.back().first);
            storage_.pop_back();
            --current_size_;
        }

    private:
        size_type max_size_;
        size_type current_size_ = 0;

        storage_type storage_;
        map_type map_;

        statistics_type statistics_;
    };
}    // namespace hpx::util::cache

1	// Copyright (c) 2016 Thomas Heller
2	// Copyright (c) 2022-2025 Hartmut Kaiser
3	//
4	// SPDX-License-Identifier: BSL-1.0
5	// Distributed under the Boost Software License, Version 1.0. (See accompanying
6	// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7
8	#pragma once
9
10	#include <hpx/config.hpp>
11	#include <hpx/cache/statistics/no_statistics.hpp>
12
13	#include <cstddef>
14	#include <list>
15	#include <map>
16	#include <type_traits>
17	#include <utility>
18
19	///////////////////////////////////////////////////////////////////////////////
20	namespace hpx::util::cache {
21
22	///////////////////////////////////////////////////////////////////////////
23	/// \class lru_cache lru_cache.hpp hpx/cache/lru_cache.hpp
24	///
25	/// \brief The \a lru_cache implements the basic functionality needed for
26	/// a local (non-distributed) LRU cache.
27	///
28	/// \tparam Key The type of the keys to use to identify the
29	/// entries stored in the cache
30	/// \tparam Entry The type of the items to be held in the cache.
31	/// \tparam Statistics A (optional) type allowing to collect some basic
32	/// statistics about the operation of the cache
33	/// instance. The type must conform to the
34	/// CacheStatistics concept. The default value is
35	/// the type \a statistics#no_statistics which does
36	/// not collect any numbers, but provides empty stubs
37	/// allowing the code to compile.
38	HPX_CXX_EXPORT template <typename Key, typename Entry,
39	typename Statistics = statistics::no_statistics>
40	class lru_cache
41	{
42	public:
43	using key_type = Key;
44	using entry_type = Entry;
45	using statistics_type = Statistics;
46	using entry_pair = std::pair<key_type, entry_type>;
47	using storage_type = std::list<entry_pair>;
48	using map_type = std::map<Key, typename storage_type::iterator>;
49	using size_type = std::size_t;
50
51	private:
52	using update_on_exit = typename statistics_type::update_on_exit;
53
54	public:
55	///////////////////////////////////////////////////////////////////////
56	/// \brief Construct an instance of a lru_cache.
57	///
58	/// \param max_size [in] The maximal size this cache is allowed to
59	/// reach any time. The default is zero (no size
60	/// limitation). The unit of this value is usually
61	/// determined by the unit of the values returned by
62	/// the entry's \a get_size function.
63	///	32✔
64	explicit lru_cache(size_type max_size = 0)	32✔
65	: max_size_(max_size)
66	{
67	}
68
69	lru_cache(lru_cache const& other) = default;
70	lru_cache(lru_cache&& other) = default;
71	lru_cache& operator=(lru_cache const& other) = default;
72	lru_cache& operator=(lru_cache&& other) = default;
73		32✔
74	~lru_cache() = default;
75
76	///////////////////////////////////////////////////////////////////////
77	/// \brief Return current size of the cache.
78	///
79	/// \returns The current size of this cache instance.
80	[[nodiscard]] constexpr size_type size() const noexcept
81	{	×
82	return current_size_;
83	}
84
85	///////////////////////////////////////////////////////////////////////
86	/// \brief Access the maximum size the cache is allowed to grow to.
87	///
88	/// \note The unit of this value is usually determined by the
89	/// unit of the return values of the entry's function
90	/// \a entry#get_size.
91	///
92	/// \returns The maximum size this cache instance is currently
93	/// allowed to reach. If this number is zero the cache has
94	/// no limitation with regard to a maximum size.
95	[[nodiscard]] constexpr size_type capacity() const noexcept
96	{
97	return max_size_;
98	}
99
100	///////////////////////////////////////////////////////////////////////
101	/// \brief Change the maximum size this cache can grow to
102	///
103	/// \param max_size [in] The new maximum size this cache will be
104	/// allowed to grow to.
105	///
106	void reserve(size_type max_size)
107	{	32✔
108	if (max_size > max_size_)
109	{	32✔
110	max_size_ = max_size;	32✔
111	return;
112	}
113		×
114	max_size_ = max_size;	×
115	while (current_size_ > max_size_) //-V776
116	{	×
117	evict();
118	}
119	}
120
121	///////////////////////////////////////////////////////////////////////
122	/// \brief Check whether the cache currently holds an entry identified
123	/// by the given key
124	///
125	/// \param key [in] The key for the entry which should be looked up
126	/// in the cache.
127	///
128	/// \note This function does not call the entry's function
129	/// \a entry#touch. It just checks if the cache contains
130	/// an entry corresponding to the given key.
131	///
132	/// \returns This function returns \a true if the cache holds the
133	/// referenced entry, otherwise it returns \a false.
134	[[nodiscard]] bool holds_key(key_type const& key) const
135	{
136	return map_.find(key) != map_.end();
137	}
138
139	///////////////////////////////////////////////////////////////////////
140	/// \brief Get a specific entry identified by the given key.
141	///
142	/// \param key [in] The key for the entry which should be retrieved
143	/// from the cache.
144	/// \param realkey[out] Return the full real key found in the cache
145	/// \param entry [out] If the entry indexed by the key is found in the
146	/// cache this value on successful return will be a copy
147	/// of the corresponding entry.
148	///
149	/// \note The function will "touch" the entry and mark it as recently
150	/// used if the key was found in the cache.
151	///
152	/// \returns This function returns \a true if the cache holds the
153	/// referenced entry, otherwise it returns \a false.	15✔
154	bool get_entry(
155	key_type const& key, key_type& realkey, entry_type& entry)
156	{
157	update_on_exit update(statistics_, statistics::method::get_entry);
158
159	auto it = map_.find(key);
160		15✔
161	if (it == map_.end())
162	{
163	// Got miss
164	statistics_.got_miss(); // update statistics	15✔
165	return false;
166	}
167
168	touch(it->second);
169
170	// update statistics
171	statistics_.got_hit();
172
173	// got hit
174	realkey = it->first;
175	entry = it->second->second;
176		×
177	return true;	15✔
178	}
179
180	///////////////////////////////////////////////////////////////////////
181	/// \brief Get a specific entry identified by the given key.
182	///
183	/// \param key [in] The key for the entry which should be retrieved
184	/// from the cache.
185	/// \param entry [out] If the entry indexed by the key is found in the
186	/// cache this value on successful return will be a copy
187	/// of the corresponding entry.
188	///
189	/// \note The function will "touch" the entry and mark it as recently
190	/// used if the key was found in the cache.
191	///
192	/// \returns This function returns \a true if the cache holds the
193	/// referenced entry, otherwise it returns \a false.
194	bool get_entry(key_type const& key, entry_type const& entry)
195	{
196	key_type tmp;
197	return get_entry(key, tmp, entry);
198	}
199
200	/// \brief Insert a new entry into this cache
201	///
202	/// \param key [in] The key for the entry which should be added to
203	/// the cache.
204	/// \param entry [in] The entry which should be added to the cache.
205	///
206	/// \note This function assumes that the entry is not in the
207	/// cache already. Inserting an already existing entry
208	/// is considered undefined behavior
209	template <typename Entry_,
210	typename = std::enable_if_t<
211	std::is_convertible_v<std::decay_t<Entry_>, entry_type>>>
212	bool insert(key_type const& key, Entry_&& entry)
213	{
214	update_on_exit update(
215	statistics_, statistics::method::insert_entry);
216	if (map_.find(key) != map_.end())
217	{
218	return false;
219	}
220
221	insert_nonexist(key, HPX_FORWARD(Entry_, entry));
222	return true;
223	}
224
225	private:
226	template <typename Entry_,
227	typename = std::enable_if_t<
228	std::is_convertible_v<std::decay_t<Entry_>, entry_type>>>	15✔
229	void insert_nonexist(key_type const& key, Entry_&& entry)
230	{
231	// insert ...	15✔
232	storage_.emplace_front(key, HPX_FORWARD(Entry_, entry));	15✔
233	map_[key] = storage_.begin();	15✔
234	++current_size_;
235
236	// update statistics
237	statistics_.got_insertion();
238
239	// Do we need to evict a cache entry?	15✔
240	if (current_size_ > max_size_)
241	{
242	// evict an entry	×
243	evict();
244	}	15✔
245	}
246
247	public:
248	///////////////////////////////////////////////////////////////////////
249	/// \brief Update an existing element in this cache
250	///
251	/// \param key [in] The key for the value which should be updated in
252	/// the cache.
253	/// \param entry [in] The entry which should be used as a replacement
254	/// for the existing value in the cache. Any existing
255	/// cache entry is not changed except for its value.
256	///
257	/// \note The function will "touch" the entry and mark it as recently
258	/// used if the key was found in the cache.
259	/// \note The difference to the other overload of the \a insert
260	/// function is that this overload replaces the cached
261	/// value only, while the other overload replaces the
262	/// whole cache entry, updating the cache entry
263	/// properties.
264	template <typename Entry_,
265	typename = std::enable_if_t<
266	std::is_convertible_v<std::decay_t<Entry_>, entry_type>>>
267	void update(key_type const& key, Entry_&& entry)
268	{
269	update_on_exit update(
270	statistics_, statistics::method::update_entry);
271
272	// Is it already in the cache?
273	auto it = map_.find(key);
274	if (it == map_.end())
275	{
276	// got miss
277	statistics_.got_miss(); // update statistics
278	insert_nonexist(key, HPX_FORWARD(Entry_, entry));
279	return;
280	}
281
282	// got hit!
283	it->second->second = HPX_FORWARD(Entry_, entry);
284	touch(it->second);
285
286	// update statistics
287	statistics_.got_hit();
288	}
289
290	///////////////////////////////////////////////////////////////////////
291	/// \brief Update an existing element in this cache
292	///
293	/// \param key [in] The key for the value which should be updated in
294	/// the cache.
295	/// \param entry [in] The value which should be used as a replacement
296	/// for the existing value in the cache. Any existing
297	/// cache entry is not changed except for its value.
298	/// \param f [in] A callable taking two arguments, \a k and the
299	/// key found in the cache (in that order). If \a f
300	/// returns true, then the update will continue. If \a f
301	/// returns false, then the update will not succeed.
302	///
303	/// \note The function will "touch" the entry and mark it as recently
304	/// used if the key was found in the cache.
305	/// \note The difference to the other overload of the \a insert
306	/// function is that this overload replaces the cached
307	/// value only, while the other overload replaces the
308	/// whole cache entry, updating the cache entry
309	/// properties.
310	///
311	/// \returns This function returns \a true if the entry has been
312	/// successfully updated, otherwise it returns \a false.
313	/// If the entry currently is not held by the cache it is
314	/// added and the return value reflects the outcome of
315	/// the corresponding insert operation.
316	template <typename F, typename Entry_,
317	std::enable_if_t<
318	std::is_convertible_v<std::decay_t<Entry_>, entry_type>, int> =
319	0>	21✔
320	bool update_if(key_type const& key, Entry_&& entry, F&& f)
321	{
322	update_on_exit update(
323	statistics_, statistics::method::update_entry);
324
325	// Is it already in the cache?
326	auto it = map_.find(key);	21✔
327	if (it == map_.end())
328	{
329	// got miss
330	statistics_.got_miss(); // update statistics	15✔
331	insert_nonexist(key, HPX_FORWARD(Entry_, entry));
332	return true;
333	}
334		6✔
335	if (f(key, it->first))
336	return false;
337
338	// got hit!
339	touch(it->second);
340	it->second->second = HPX_FORWARD(Entry_, entry);
341
342	// update statistics
343	statistics_.got_hit();
344		6✔
345	return true;	21✔
346	}
347
348	///////////////////////////////////////////////////////////////////////
349	/// \brief Remove stored entries from the cache for which the supplied
350	/// function object returns true.
351	///
352	/// \param ep [in] This parameter has to be a (unary) function
353	/// object. It is invoked for each of the entries
354	/// currently held in the cache. An entry is considered
355	/// for removal from the cache whenever the value
356	/// returned from this invocation is \a true.
357	///
358	/// \returns This function returns the overall size of the removed
359	/// entries (which is the sum of the values returned by
360	/// the \a entry#get_size functions of the removed
361	/// entries).
362	template <typename Func>	×
363	size_type erase(Func const& ep)
364	{
365	update_on_exit update(statistics_, statistics::method::erase_entry);
366
367	size_type erased = 0;	×
368	for (auto it = map_.begin(); it != map_.end();)
369	{	×
370	auto jt = it->second;
371	if (ep(*jt))
372	{	×
373	++erased;
374		×
375	storage_.erase(jt);
376	it = map_.erase(it);
377
378	// update statistics
379	statistics_.got_eviction();
380	}
381	else
382	{
383	++it;
384	}
385	}
386		×
387	return erased;	×
388	}
389
390	/// \brief Remove all stored entries from the cache
391	///
392	/// \returns This function returns the overall size of the removed
393	/// entries (which is the sum of the values returned by
394	/// the \a entry#get_size functions of the removed
395	/// entries).
396	size_type erase()
397	{
398	std::size_t const current_size = current_size_;
399	clear();
400	return current_size;
401	}
402
403	/// \brief Clear the cache
404	///
405	/// Unconditionally removes all stored entries from the cache.	×
406	size_type clear()
407	{	×
408	size_type const erased = current_size_;	×
409	current_size_ = 0;
410	map_.clear();
411	storage_.clear();	×
412	return erased;
413	}
414
415	///////////////////////////////////////////////////////////////////////
416	/// \brief Allow to access the embedded statistics instance
417	///
418	/// \returns This function returns a reference to the statistics
419	/// instance embedded inside this cache
420	[[nodiscard]] constexpr statistics_type const& get_statistics()
421	const noexcept
422	{
423	return statistics_;
424	}
425
426	[[nodiscard]] statistics_type& get_statistics() noexcept
427	{
428	return statistics_;
429	}
430
431	private:
432	void touch(typename storage_type::iterator it)
433	{	6✔
434	storage_.splice(storage_.begin(), storage_, it);
435	}
436		×
437	void evict()
438	{
439	statistics_.got_eviction();	×
440	map_.erase(storage_.back().first);	×
441	storage_.pop_back();	×
442	--current_size_;	×
443	}
444
445	private:
446	size_type max_size_;
447	size_type current_size_ = 0;
448
449	storage_type storage_;
450	map_type map_;
451
452	statistics_type statistics_;
453	};
454	} // namespace hpx::util::cache

STEllAR-GROUP / hpx / #882

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous