Using circular_buffer instead of list.

3 files changed, 28 insertions, 19 deletions

diff --git a/base/base_tests/fifo_cache_test.cpp b/base/base_tests/fifo_cache_test.cpp
index f9fa25e8a6..d4e1a773df 100644
--- a/base/base_tests/fifo_cache_test.cpp
+++ b/base/base_tests/fifo_cache_test.cpp
@@ -6,6 +6,8 @@
 #include <set>
 #include <unordered_map>
 
+#include <boost/circular_buffer.hpp>
+
 using namespace std;
 
 template <typename Key, typename Value>
@@ -19,11 +21,11 @@ public:
 
   Value const & GetValue(Key const & key) { return m_cache.GetValue(key); }
   unordered_map<Key, Value> const & GetMap() const { return m_cache.m_map; }
-  list<Key> const & GetList() const { return m_cache.m_list; }
+  boost::circular_buffer<Key> const & GetList() const { return m_cache.m_list; }
 
   bool IsValid() const
   {
-    set<Key> listKeys(m_cache.m_list.cbegin(), m_cache.m_list.cend());
+    set<Key> listKeys(m_cache.m_list.begin(), m_cache.m_list.end());
     set<Key> mapKeys;
 
     for (auto const & kv : m_cache.m_map)
@@ -63,8 +65,9 @@ UNIT_TEST(FifoCache)
   {
     unordered_map<Key, Value> expectedMap({{1 /* key */, 1 /* value */}, {2, 2}, {3, 3}});
     TEST_EQUAL(cache.GetMap(), expectedMap, ());
-    list<Key> expectedList({2, 3, 1});
-    TEST_EQUAL(cache.GetList(), expectedList, ());
+    std::list<Key> expectedList({2, 3, 1});
+    boost::circular_buffer<Key> expectedCB(expectedList.cbegin(), expectedList.cend());
+    TEST_EQUAL(cache.GetList(), expectedCB, ());
   }
 
   TEST_EQUAL(cache.GetValue(7), 7, ());
@@ -72,8 +75,9 @@ UNIT_TEST(FifoCache)
   {
     unordered_map<Key, Value> expectedMap({{7 /* key */, 7 /* value */}, {2, 2}, {3, 3}});
     TEST_EQUAL(cache.GetMap(), expectedMap, ());
-    list<Key> expectedList({7, 2, 3});
-    TEST_EQUAL(cache.GetList(), expectedList, ());
+    std::list<Key> expectedList({7, 2, 3});
+    boost::circular_buffer<Key> expectedCB(expectedList.cbegin(), expectedList.cend());
+    TEST_EQUAL(cache.GetList(), expectedCB, ());
   }
 }
 
diff --git a/base/fifo_cache.hpp b/base/fifo_cache.hpp
index 0eeb8dc4c4..d08739fe76 100644
--- a/base/fifo_cache.hpp
+++ b/base/fifo_cache.hpp
@@ -4,9 +4,10 @@
 
 #include <cstddef>
 #include <functional>
-#include <list>
 #include <unordered_map>
 
+#include <boost/circular_buffer.hpp>
+
 template<class Key, class Value>
 class FifoCache
 {
@@ -17,7 +18,10 @@ public:
 
   /// \param capacity maximum size of the cache in number of items.
   /// \param loader Function which is called if it's necessary to load a new item for the cache.
-  FifoCache(size_t capacity, Loader const & loader) : m_capacity(capacity), m_loader(loader) {}
+  FifoCache(size_t capacity, Loader const & loader)
+    : m_list(capacity), m_capacity(capacity), m_loader(loader)
+  {
+  }
 
   /// \brief Loads value, if it's necessary, by |key| with |m_loader|, puts it to cache and
   /// returns the reference to the value to |m_map|.
@@ -28,7 +32,10 @@ public:
       return it->second;
 
     if (Size() >= m_capacity)
-      Evict();
+    {
+      CHECK(!m_list.empty(), ());
+      m_map.erase(m_list.back());
+    }
 
     m_list.push_front(key);
 
@@ -38,19 +45,10 @@ public:
   }
 
 private:
-  void Evict()
-  {
-    auto const i = --m_list.end();
-    m_map.erase(*i);
-    m_list.erase(i);
-  }
-
   size_t Size() const { return m_map.size(); }
 
   std::unordered_map<Key, Value> m_map;
-  // @TODO(bykoianko) Consider using a structure like boost/circular_buffer instead of list
-  // but with handling overwriting shift. We need it to know to remove overwritten key from |m_map|.
-  std::list<Key> m_list;
+  boost::circular_buffer<Key> m_list;
   size_t m_capacity;
   Loader m_loader;
 };
diff --git a/base/internal/message.hpp b/base/internal/message.hpp
index 2b549d8409..aac209d580 100644
--- a/base/internal/message.hpp
+++ b/base/internal/message.hpp
@@ -18,6 +18,7 @@
 #include <utility>
 #include <vector>
 
+#include <boost/circular_buffer.hpp>
 
 /// @name Declarations.
 //@{
@@ -29,6 +30,7 @@ inline std::string DebugPrint(char t);
 
 template <typename U, typename V> inline std::string DebugPrint(std::pair<U, V> const & p);
 template <typename T> inline std::string DebugPrint(std::list<T> const & v);
+template <typename T> inline std::string DebugPrint(boost::circular_buffer<T> const & v);
 template <typename T> inline std::string DebugPrint(std::vector<T> const & v);
 template <typename T, typename C = std::less<T>> inline std::string DebugPrint(std::set<T, C> const & v);
 template <typename T, typename C = std::less<T>> inline std::string DebugPrint(std::multiset<T, C> const & v);
@@ -120,6 +122,11 @@ template <typename T> inline std::string DebugPrint(std::list<T> const & v)
   return ::my::impl::DebugPrintSequence(v.begin(), v.end());
 }
 
+template <typename T> inline std::string DebugPrint(boost::circular_buffer<T> const & v)
+{
+  return ::my::impl::DebugPrintSequence(v.begin(), v.end());
+}
+
 template <typename T, typename C> inline std::string DebugPrint(std::set<T, C> const & v)
 {
   return ::my::impl::DebugPrintSequence(v.begin(), v.end());