Speed up lookups
Main idea behind this change is to avoid linear search by storing list
of child nodes in a set<node*>. Using std:is_transparent custom
comparator we can compare node* to other types (in this case
std::pair<std::string, uintptr_t>), which allows us to speed up
LookupChildByName function.
Note that this slightly changes the behaviour. Before this change, if
there were multiple children nodes with the same case-insensitive name,
the one that was added to the parent earliest will be returned (among
the non-deleted ones). With this change, the one with lowest inode will
be returned (again, among the non-deleted ones). Given that both of the
orderings seem quite random to me, I don't see a problem here, but I
might be wrong. :)
Test: atest fuse_node_test
Test: atest com.android.providers.media.client.PerformanceTest
Test: atest CtsScopedStorageHostTest
Bug: 158809855
Change-Id: Idec356253bcd1abfa0dc6d47090bcdbee845f8b1
(cherry picked from commit 890e6f2b2500af11c6399fa4abd740d15558feb7)
2 files changed