Issue 984 - port referrer mapping from Android

src/ReferrerMapping.cpp

 /*
  * This file is part of Adblock Plus <http://adblockplus.org/>,
  * Copyright (C) 2006-2014 Eyeo GmbH
  *
  * Adblock Plus is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 3 as
  * published by the Free Software Foundation.
  *
  * Adblock Plus is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 #include <AdblockPlus/ReferrerMapping.h>
 
 using namespace AdblockPlus;
 
 ReferrerMapping::ReferrerMapping(const int maxCachedUrls)
   : maxCachedUrls(maxCachedUrls)
 {
 }
 
 void ReferrerMapping::Add(const std::string& url, const std::string& referrer)
 {
-  mapping[url] = referrer;
-  if (std::find(cachedUrls.begin(), cachedUrls.end(), url) != cachedUrls.end())
+  if (mapping.find(url) != mapping.end())
     cachedUrls.remove(url);
   cachedUrls.push_back(url);
-  while (cachedUrls.size() > maxCachedUrls)

[Wladimir Palant, 2014/07/16 09:51:11]

I'm already unhappy with std::find() having to go through the entire list above.
Unfortunately, std::list::size() currently does the same in libstdc++ (see
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561) even though libc++ and MSVC
don't. Please consider adding a member variable to store the number of URLs.

[Felix Dahlke, 2014/07/16 10:15:48]

Done. We shouldn't really rely on implementation details like that, and calling
size repeatedly until the cache size is appropriate is pointless.

I'd rather not keep the size in a separate member variable though. The gain
doesn't seem worth the extra complexity. It only makes sense to call Add for an
actual request, so we're not exactly the bottleneck in reality.

[Felix Dahlke, 2014/07/16 10:18:39]

Note that we can optimise the std::find above away in pretty much all cases by
checking if url is in mapping. std::list::remove can handle it if url is
missing, but the two data structures should be in sync anyway. I'd rather go for
that if we want to optimise, agreed?

[Wladimir Palant, 2014/07/16 10:26:01]

Overlooked this comment - sure, sounds like a good idea to improve the
performance here. We really shouldn't go through that list more often than
necessary.

[Felix Dahlke, 2014/07/16 10:34:24]

Done.

+  mapping[url] = referrer;
+
+  const int urlsToPop = cachedUrls.size() - maxCachedUrls;
+  for (int i = 0; i < urlsToPop; i++)
   {
     const std::string poppedUrl = cachedUrls.front();
     cachedUrls.pop_front();
     mapping.erase(poppedUrl);
   }
 }
 
 std::vector<std::string> ReferrerMapping::BuildReferrerChain(
   const std::string& url) const
 {
   std::vector<std::string> referrerChain;
   referrerChain.push_back(url);
   // We need to limit the chain length to ensure we don't block indefinitely
   // if there's a referrer loop.
   const int maxChainLength = 10;
   std::map<std::string, std::string>::const_iterator currentEntry =
     mapping.find(url);
   for (int i = 0; i < maxChainLength && currentEntry != mapping.end(); i++)
   {
     const std::string& currentUrl = currentEntry->second;
     referrerChain.insert(referrerChain.begin(), currentUrl);
     currentEntry = mapping.find(currentUrl);
   }
   return referrerChain;
 }