Enable comparing KFileItems by url
ClosedPublic

Authored by jtamate on May 30 2018, 10:38 AM.

Details

Summary

Based on QUrl comparisons (available since Qt 5.4).
Those comparisons can be used to speedup the lookup of the requested KFileItem, for example using std::lower_bound.

Test Plan

Included a new test in kfileitemtest

Diff Detail

Repository
R241 KIO
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
jtamate created this revision.May 30 2018, 10:38 AM
Restricted Application added a project: Frameworks. · View Herald TranscriptMay 30 2018, 10:38 AM
Restricted Application added a subscriber: kde-frameworks-devel. · View Herald Transcript
dfaure requested changes to this revision.May 30 2018, 11:59 AM
dfaure added inline comments.
src/core/kfileitem.cpp
1241

This isn't symmetric. operator< must have the property that a<b and b<a aren't both true, and that they are both false only if the items are equal.

If this is a valid item and other is null, then this code says that *this<other is false and other<*this is false.
Which would let some algorithms deduce that *this == other, which is completely wrong.

If we decide that a null item is inferior to anything else, then we need

if (!d) return true; if (!other.d) return false;

(with newlines and braces of course).

This also calls for a corresponding unittest.

src/core/kfileitem.h
493

This one looks good.

499

This operator seems strange to me, it's comparing a KFileItem and a QUrl, which are two different kinds of objects... What's the use case?

This revision now requires changes to proceed.May 30 2018, 11:59 AM
jtamate updated this revision to Diff 35188.May 30 2018, 2:02 PM
jtamate marked 3 inline comments as done.
jtamate edited the test plan for this revision. (Show Details)

A KFileItem without url will be the lowest, even lower than itself.
Created a new test.

The comparison with the QUrl is for this use case:

auto it = std::lower_bound(dirItem->lstItems.begin(), dirItem->lstItems.end(), oldUrl);
dfaure requested changes to this revision.May 30 2018, 2:11 PM

A good example of how a unittest helps catching a bug :-)
(and a good example of how code that I suggest isn't necessarily bugfree, haha)

Missing: unittests for the < QUrl overload.
The case of the invalid item vs an invalid URL will be interesting too ;)

autotests/kfileitemtest.cpp
305

I wonder if that should be true, though ;-)

I guess it should rather be false, so that a binary search (based on < only) can deduce that a null item is *equal* to another null item, rather than both being lower than the other, which would be nonsense.

314

... exactly. I think the same reasoning applies to a null item.

src/core/kfileitem.h
490

"this item's URL"

496

"than this item's URL", then

This revision now requires changes to proceed.May 30 2018, 2:11 PM
bruns added a subscriber: bruns.May 30 2018, 2:16 PM
bruns added inline comments.
src/core/kfileitem.cpp
1241

If we decide that a null item is inferior to anything else, then we need
if (!d) return true; if (!other.d) return false;

this has to be
if (!other.d) return false; if (!d) return true; (mind the order)

otherwise (nullptr) < (nullptr).

jtamate updated this revision to Diff 35190.May 30 2018, 3:00 PM
jtamate marked 4 inline comments as done.

Invalid items are not less than invalid items or invalid urls, they are not like -infinite.
Added the tests comparing items with urls.
Changed the descriptions.

jtamate updated this revision to Diff 35192.May 30 2018, 3:15 PM

Taken into account invalid Items created from invalid QUrls.

jtamate updated this revision to Diff 35303.Jun 1 2018, 7:22 AM

Now passes the tests and its performance for non invalid items is not degraded too much (same +3ms inserting).

jtamate updated this revision to Diff 36037.Jun 12 2018, 9:21 AM
jtamate marked an inline comment as done.
jtamate edited the summary of this revision. (Show Details)

Change @since to 5.48

dfaure accepted this revision.Jun 13 2018, 7:54 AM
This revision is now accepted and ready to land.Jun 13 2018, 7:54 AM
This revision was automatically updated to reflect the committed changes.
markg added a subscriber: markg.Jun 13 2018, 8:42 PM

While this works, there is a newer en better way for it.
It's new in C++14 and called "transparent compare".
In "this" case it won't change the resulting code of how you compare, but it might be worth checking that out.

Read this: https://www.fluentcpp.com/2017/06/09/search-set-another-type-key/
And watch this: https://www.youtube.com/watch?v=BBUacofxOP8

those will explain how to use it.