From 0ee4bafff637eef15e5bd39e8f5c4ae77ab05dcc Mon Sep 17 00:00:00 2001
From: Sage Weil <sage@redhat.com>
Date: Mon, 5 Jun 2017 15:31:05 -0400
Subject: [PATCH] common/LogEntry: make LogSummary::contains() efficient

A linear search here is dumb.  Use an unordered_set.

Signed-off-by: Sage Weil <sage@redhat.com>
---
 src/common/LogEntry.cc |  4 ++++
 src/common/LogEntry.h  | 18 ++++++++++++------
 2 files changed, 16 insertions(+), 6 deletions(-)

diff --git a/src/common/LogEntry.cc b/src/common/LogEntry.cc
index d97b0480d707..52af1eb878d7 100644
--- a/src/common/LogEntry.cc
+++ b/src/common/LogEntry.cc
@@ -250,6 +250,10 @@ void LogSummary::decode(bufferlist::iterator& bl)
   ::decode(version, bl);
   ::decode(tail, bl);
   DECODE_FINISH(bl);
+  keys.clear();
+  for (auto& p : tail) {
+    keys.insert(p.key());
+  }
 }
 
 void LogSummary::dump(Formatter *f) const
diff --git a/src/common/LogEntry.h b/src/common/LogEntry.h
index 790b8662b131..5d00119d7805 100644
--- a/src/common/LogEntry.h
+++ b/src/common/LogEntry.h
@@ -71,6 +71,14 @@ WRITE_CLASS_ENCODER_FEATURES(LogEntryKey)
 static inline bool operator==(const LogEntryKey& l, const LogEntryKey& r) {
   return l.who == r.who && l.stamp == r.stamp && l.seq == r.seq;
 }
+namespace std {
+  template<> struct hash<LogEntryKey> {
+    size_t operator()(const LogEntryKey& r) const {
+      hash<entity_inst_t> h;
+      return r.seq + h(r.who);
+    }
+  };
+} // namespace std
 
 struct LogEntry {
   entity_inst_t who;
@@ -97,24 +105,22 @@ WRITE_CLASS_ENCODER_FEATURES(LogEntry)
 struct LogSummary {
   version_t version;
   list<LogEntry> tail;
+  ceph::unordered_set<LogEntryKey> keys;
 
   LogSummary() : version(0) {}
 
   void add(const LogEntry& e) {
     tail.push_back(e);
+    keys.insert(tail.back().key());
   }
   void prune(size_t max) {
     while (tail.size() > max) {
+      keys.erase(tail.front().key());
       tail.pop_front();
     }
   }
   bool contains(const LogEntryKey& k) const {
-    for (list<LogEntry>::const_iterator p = tail.begin();
-	 p != tail.end();
-	 ++p)
-      if (p->key() == k)
-	return true;
-    return false;
+    return keys.count(k);
   }
 
   void encode(bufferlist& bl, uint64_t features) const;
-- 
2.47.3