Issue 984 - port referrer mapping from Android

This port is pretty close to what we have on Android:
https://hg.adblockplus.org/adblockplusandroid/file/4fd8c169eb6a/src/org/adblockplus/android/ReferrerMapping.java

The main difference is that Java has the perfect data structure for our needs; LinkedHashMap, while C++'s standard library doesn't have anything comparable.

[René Jeschke, 2014-07-16 08:57:06]

Just a single'n'small issue.

http://codereview.adblockplus.org/6307944991817728/diff/5161210659995648/src/...
File src/ReferrerMapping.cpp (right):

http://codereview.adblockplus.org/6307944991817728/diff/5161210659995648/src/...
src/ReferrerMapping.cpp:53: const std::string url = currentEntry->second;
Shouldn't this 
1) be a reference here?
2) be renamed as it's shadowing the method argument 'url'?

[Felix Dahlke, 2014-07-16 09:05:21]

New patch set with the issue addressed.

http://codereview.adblockplus.org/6307944991817728/diff/5161210659995648/src/...
File src/ReferrerMapping.cpp (right):

http://codereview.adblockplus.org/6307944991817728/diff/5161210659995648/src/...
src/ReferrerMapping.cpp:53: const std::string url = currentEntry->second;
On 2014/07/16 08:57:07, René Jeschke wrote:
> Shouldn't this 
> 1) be a reference here?
> 2) be renamed as it's shadowing the method argument 'url'?

Done.

[René Jeschke, 2014-07-16 09:11:33]

LGTM

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

LGTM given that the issue below should only affect Linux once we switch to
libc++. Still, feel free to address it.

http://codereview.adblockplus.org/6307944991817728/diff/5750085036015616/src/...
File src/ReferrerMapping.cpp (right):

http://codereview.adblockplus.org/6307944991817728/diff/5750085036015616/src/...
src/ReferrerMapping.cpp:33: while (cachedUrls.size() > maxCachedUrls)
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:14:33]

On 2014/07/16 09:51:11, Wladimir Palant wrote:
> LGTM given that the issue below should only affect Linux once we switch to
> libc++. Still, feel free to address it.
> 
>
http://codereview.adblockplus.org/6307944991817728/diff/5750085036015616/src/...
> File src/ReferrerMapping.cpp (right):
> 
>
http://codereview.adblockplus.org/6307944991817728/diff/5750085036015616/src/...
> src/ReferrerMapping.cpp:33: while (cachedUrls.size() > maxCachedUrls)
> 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.

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:15:48]

http://codereview.adblockplus.org/6307944991817728/diff/5750085036015616/src/...
File src/ReferrerMapping.cpp (right):

http://codereview.adblockplus.org/6307944991817728/diff/5750085036015616/src/...
src/ReferrerMapping.cpp:33: while (cachedUrls.size() > maxCachedUrls)
On 2014/07/16 09:51:11, Wladimir Palant wrote:
> 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.


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:38]

http://codereview.adblockplus.org/6307944991817728/diff/5750085036015616/src/...
File src/ReferrerMapping.cpp (right):

http://codereview.adblockplus.org/6307944991817728/diff/5750085036015616/src/...
src/ReferrerMapping.cpp:33: while (cachedUrls.size() > maxCachedUrls)
On 2014/07/16 10:15:48, Felix H. Dahlke wrote:
> On 2014/07/16 09:51:11, Wladimir Palant wrote:
> > 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.
> 
> 
> 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.

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:23:24]

LGTM

http://codereview.adblockplus.org/6307944991817728/diff/5634387206995968/src/...
File src/ReferrerMapping.cpp (right):

http://codereview.adblockplus.org/6307944991817728/diff/5634387206995968/src/...
src/ReferrerMapping.cpp:33: const int urlsToPop = cachedUrls.size() -
maxCachedUrls;
Nit: add an empty line before this one to indicate a new logical block?

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

http://codereview.adblockplus.org/6307944991817728/diff/5750085036015616/src/...
File src/ReferrerMapping.cpp (right):

http://codereview.adblockplus.org/6307944991817728/diff/5750085036015616/src/...
src/ReferrerMapping.cpp:33: while (cachedUrls.size() > maxCachedUrls)
On 2014/07/16 10:18:39, Felix H. Dahlke wrote:
> 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?

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:23]

New patch set is up. So once we've switched to C++11 (and compliant
implementations), we won't have a single linear time access remaining in Add!

http://codereview.adblockplus.org/6307944991817728/diff/5750085036015616/src/...
File src/ReferrerMapping.cpp (right):

http://codereview.adblockplus.org/6307944991817728/diff/5750085036015616/src/...
src/ReferrerMapping.cpp:33: while (cachedUrls.size() > maxCachedUrls)
On 2014/07/16 10:26:01, Wladimir Palant wrote:
> On 2014/07/16 10:18:39, Felix H. Dahlke wrote:
> > 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?
> 
> 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.

Done.

http://codereview.adblockplus.org/6307944991817728/diff/5634387206995968/src/...
File src/ReferrerMapping.cpp (right):

http://codereview.adblockplus.org/6307944991817728/diff/5634387206995968/src/...
src/ReferrerMapping.cpp:33: const int urlsToPop = cachedUrls.size() -
maxCachedUrls;
On 2014/07/16 10:23:24, Wladimir Palant wrote:
> Nit: add an empty line before this one to indicate a new logical block?

Done.

[Wladimir Palant, 2014-07-16 10:39:35]

LGTM, nice

[René Jeschke, 2014-07-16 10:49:51]

LGTM