Fix unnecessary tree traversal in SearchNameNodeByNameInternal()
When SearchNameNodeByNameInternal() is searching the name tree for
`csName`, it encounters nodes with limits, designating a range of what
possible values can be found in its subtree. Logically, when one is
searching for `csName`, and encounters a node where `csName` is greater
than the node's greatest limit, that subtree should be skipped, and the
next sibling node (if it exists) should be processed instead. This was
the behavior prior to https://pdfium-review.googlesource.com/8271, but
that CL introduced a regression where the subtree still gets traversed
anyway. This behavior might make sense when trying to add to the name
tree, where there needs to be some tree balancing, but it is unnecessary
when only searching the tree, leading to slow performance for PDFs with
large name trees.
Fix this behavior by skipping the subtree when only trying to search for
`csName`.
Bug: 372523840
Change-Id: I805e0a32fbd6ffdbece6f831f1be6d3a977587fc
Reviewed-on: https://pdfium-review.googlesource.com/c/pdfium/+/128231
Reviewed-by: Lei Zhang <thestig@chromium.org>
Commit-Queue: Andy Phan <andyphan@chromium.org>
diff --git a/core/fpdfdoc/cpdf_nametree.cpp b/core/fpdfdoc/cpdf_nametree.cpp
index adfb890..48157a9 100644
--- a/core/fpdfdoc/cpdf_nametree.cpp
+++ b/core/fpdfdoc/cpdf_nametree.cpp
@@ -221,17 +221,24 @@
if (pLimits) {
auto [csLeft, csRight] = GetNodeLimitsAndSanitize(pLimits.Get());
// Skip this node if the name to look for is smaller than its lower limit.
- if (csName.Compare(csLeft) < 0)
+ if (csName.Compare(csLeft) < 0) {
return nullptr;
+ }
- // Skip this node if the name to look for is greater than its higher limit,
- // and the node itself is a leaf node.
- if (csName.Compare(csRight) > 0 && pNames) {
- if (node_to_insert) {
+ if (csName.Compare(csRight) > 0) {
+ // If only trying to find the name node, and not where the name should be
+ // added, skip this node.
+ if (!node_to_insert) {
+ return nullptr;
+ }
+
+ // If the node itself is a leaf node, set `pNames` as the array `csName`
+ // should be added to.
+ if (pNames) {
node_to_insert->names = pNames;
node_to_insert->index = fxcrt::CollectionSize<int32_t>(*pNames) / 2 - 1;
+ return nullptr;
}
- return nullptr;
}
}
