From 769210ed7f48bade03d6fb4783afa54473013f61 Mon Sep 17 00:00:00 2001
From: Francesco Chemolli <5175948+kinkie@users.noreply.github.com>
Date: Thu, 6 Jul 2023 14:55:30 +0000
Subject: [PATCH] Support read-only ClpMap iteration by ClpMap users (#1409)

This change makes it possible for anticipated future ClpMap users (e.g.,
stat_ipcache_get()) to report their cache contents. No changes to
ClpMap::Entry and related old types except making them public.

The alternative solution -- a visitor design pattern -- was rejected
because `for` loops are a bit easier to read than for_each() loops.

No Squid functionality changes expected.
---
 src/base/ClpMap.h       | 50 ++++++++++++++++++++++++-----------------
 src/tests/testClpMap.cc | 35 +++++++++++++++++++++++++++++
 2 files changed, 65 insertions(+), 20 deletions(-)

diff --git a/src/base/ClpMap.h b/src/base/ClpMap.h
index 7d6e8894f5..af3e30713a 100644
--- a/src/base/ClpMap.h
+++ b/src/base/ClpMap.h
@@ -46,6 +46,27 @@ public:
     /// maximum desired entry caching duration (a.k.a. TTL), in seconds
     using Ttl = int;
 
+    /// the keeper of cache entry Key, Value, and caching-related entry metadata
+    class Entry
+    {
+    public:
+        Entry(const Key &, const Value &, const Ttl);
+
+        /// whether the entry is stale
+        bool expired() const { return expires < squid_curtime; }
+
+    public:
+        Key key; ///< the entry search key; see ClpMap::get()
+        Value value; ///< cached value provided by the map user
+        time_t expires = 0; ///< get() stops returning the entry after this time
+        uint64_t memCounted = 0; ///< memory accounted for this entry in our ClpMap
+    };
+
+    /// Entries in LRU order
+    using Entries = std::list<Entry, PoolingAllocator<Entry> >;
+    using EntriesIterator = typename Entries::iterator;
+    using ConstEntriesIterator = typename Entries::const_iterator;
+
     explicit ClpMap(const uint64_t capacity) { setMemLimit(capacity); }
     ClpMap(uint64_t capacity, Ttl defaultTtl);
     ~ClpMap() = default;
@@ -87,27 +108,16 @@ public:
     /// The number of currently stored entries, including expired ones
     size_t entries() const { return entries_.size(); }
 
-private:
-    /// the keeper of cache entry Key, Value, and caching-related entry metadata
-    class Entry
-    {
-    public:
-        Entry(const Key &, const Value &, const Ttl);
-
-        /// whether the entry is stale
-        bool expired() const { return expires < squid_curtime; }
-
-    public:
-        Key key; ///< the entry search key; see ClpMap::get()
-        Value value; ///< cached value provided by the map user
-        time_t expires = 0; ///< get() stops returning the entry after this time
-        uint64_t memCounted = 0; ///< memory accounted for this entry in our ClpMap
-    };
-
-    /// Entries in LRU order
-    using Entries = std::list<Entry, PoolingAllocator<Entry> >;
-    using EntriesIterator = typename Entries::iterator;
+    /// Read-only traversal of all cached entries in LRU order, least recently
+    /// used entry first. Stored expired entries (if any) are included. Any map
+    /// modification may invalidate these iterators and their derivatives.
+    ConstEntriesIterator cbegin() const { return entries_.cbegin(); }
+    ConstEntriesIterator cend() const { return entries_.cend(); }
+    /// range-based `for` loop support; \sa cbegin()
+    ConstEntriesIterator begin() const { return cbegin(); }
+    ConstEntriesIterator end() const { return cend(); }
 
+private:
     using IndexItem = std::pair<const Key, EntriesIterator>;
     /// key:entry_position mapping for fast entry lookups by key
     using Index = std::unordered_map<Key, EntriesIterator, std::hash<Key>, std::equal_to<Key>, PoolingAllocator<IndexItem> >;
diff --git a/src/tests/testClpMap.cc b/src/tests/testClpMap.cc
index 8c6eb3c420..7e6e9361f8 100644
--- a/src/tests/testClpMap.cc
+++ b/src/tests/testClpMap.cc
@@ -28,6 +28,8 @@ class TestClpMap: public CPPUNIT_NS::TestFixture
     CPPUNIT_TEST( testZeroTtl );
     CPPUNIT_TEST( testNegativeTtl );
     CPPUNIT_TEST( testPurgeIsLru );
+    CPPUNIT_TEST( testClassicLoopTraversal );
+    CPPUNIT_TEST( testRangeLoopTraversal );
     CPPUNIT_TEST_SUITE_END();
 
 public:
@@ -47,6 +49,8 @@ protected:
     void testZeroTtl();
     void testNegativeTtl();
     void testPurgeIsLru();
+    void testClassicLoopTraversal();
+    void testRangeLoopTraversal();
 
     /// Generate and insert the given number of entries into the given map. Each
     /// entry is guaranteed to be inserted, but that insertion may purge other
@@ -352,3 +356,34 @@ TestClpMap::testPurgeIsLru()
     fillMapWithEntries(m);
     CPPUNIT_ASSERT(!m.get("0")); // removable when not recently used
 }
+
+void
+TestClpMap::testClassicLoopTraversal()
+{
+    Map m(2048);
+    const size_t expectedEntryCount = 10;
+    addSequenceOfEntriesToMap(m, expectedEntryCount, 0, 50);
+    size_t iterations = 0;
+    for (auto i = m.cbegin(); i != m.cend(); ++i) {
+        ++iterations;
+        const auto expectedValue = static_cast<Map::mapped_type>(expectedEntryCount - iterations);
+        CPPUNIT_ASSERT_EQUAL(expectedValue, i->value);
+    }
+    CPPUNIT_ASSERT_EQUAL(expectedEntryCount, iterations);
+}
+
+void
+TestClpMap::testRangeLoopTraversal()
+{
+    Map m(2048);
+    const size_t expectedEntryCount = 10;
+    addSequenceOfEntriesToMap(m, expectedEntryCount, 0, 50);
+    size_t iterations = 0;
+    for (const auto &entry: m) {
+        ++iterations;
+        const auto expectedValue = static_cast<Map::mapped_type>(expectedEntryCount - iterations);
+        CPPUNIT_ASSERT_EQUAL(expectedValue, entry.value);
+    }
+    CPPUNIT_ASSERT_EQUAL(expectedEntryCount, iterations);
+}
+
-- 
2.39.5