From 8ed3e8c79b5cbccfeccee865e555b68025ee2c1f Mon Sep 17 00:00:00 2001 From: Jay Berkenbilt Date: Mon, 25 Jan 2021 08:05:43 -0500 Subject: NNTree: rework iterators to be more memory efficient Keep a std::pair internal to the iterators so that operator* can return a reference and operator-> can work, and each can work without copying pairs of objects around. --- libqpdf/NNTree.cc | 96 ++++++++++++++++++++++++++--------- libqpdf/QPDF.cc | 2 +- libqpdf/QPDFNameTreeObjectHelper.cc | 33 ++++++++++-- libqpdf/QPDFNumberTreeObjectHelper.cc | 41 ++++++++++++--- libqpdf/qpdf/NNTree.hh | 7 +-- 5 files changed, 142 insertions(+), 37 deletions(-) (limited to 'libqpdf') diff --git a/libqpdf/NNTree.cc b/libqpdf/NNTree.cc index 4f9ddcce..61710032 100644 --- a/libqpdf/NNTree.cc +++ b/libqpdf/NNTree.cc @@ -50,6 +50,57 @@ NNTreeIterator::NNTreeIterator(NNTreeImpl& impl) : { } +void +NNTreeIterator::updateIValue(bool allow_invalid) +{ + // ivalue should never be used inside the class since we return a + // pointer/reference to it. Every bit of code that ever changes + // what object the iterator points to should take care to call + // updateIValue. Failure to do this means that any old references + // to *iter will point to incorrect objects, though the next + // dereference of the iterator will fix it. This isn't necessarily + // catastrophic, but it would be confusing. The test suite + // attempts to exercise various cases to ensure we don't introduce + // that bug in the future, but sadly it's tricky to verify by + // reasoning about the code that this constraint is always + // satisfied. Whenever we update what the iterator points to, we + // should call setItemNumber, which calls this. If we change what + // the iterator in some other way, such as replacing a value or + // removing an item and making the iterator point at a different + // item in potentially the same position, we must call + // updateIValue as well. These cases are handled, and for good + // measure, we also call updateIValue in operator* and operator->. + + bool okay = false; + if ((item_number >= 0) && + this->node.isInitialized() && + this->node.isDictionary()) + { + auto items = this->node.getKey(impl.details.itemsKey()); + if (this->item_number + 1 < items.getArrayNItems()) + { + okay = true; + this->ivalue.first = items.getArrayItem(this->item_number); + this->ivalue.second = items.getArrayItem(1+this->item_number); + } + else + { + error(impl.qpdf, node, "update ivalue: items array is too short"); + } + } + if (! okay) + { + if (! allow_invalid) + { + throw std::logic_error( + "attempt made to dereference an invalid" + " name/number tree iterator"); + } + this->ivalue.first = QPDFObjectHandle(); + this->ivalue.second = QPDFObjectHandle(); + } +} + NNTreeIterator::PathElement::PathElement( QPDFObjectHandle const& node, int kid_number) : node(node), @@ -522,6 +573,7 @@ NNTreeIterator::remove() // We don't have to do anything since the removed item's // successor now occupies its former location. QTC::TC("qpdf", "NNTree erased non-last item"); + updateIValue(); } else { @@ -630,19 +682,15 @@ NNTreeIterator::operator--() NNTreeIterator::reference NNTreeIterator::operator*() { - if (this->item_number < 0) - { - throw std::logic_error( - "attempt made to dereference an invalid" - " name/number tree iterator"); - } - auto items = this->node.getKey(impl.details.itemsKey()); - if (items.getArrayNItems() < this->item_number + 2) - { - error(impl.qpdf, node, "operator*: items array is too short"); - } - return std::make_pair(items.getArrayItem(this->item_number), - items.getArrayItem(1+this->item_number)); + updateIValue(false); + return this->ivalue; +} + +NNTreeIterator::pointer +NNTreeIterator::operator->() +{ + updateIValue(false); + return &(this->ivalue); } bool @@ -660,7 +708,7 @@ NNTreeIterator::operator==(NNTreeIterator const& other) const auto opi = other.path.begin(); while (tpi != this->path.end()) { - if ((*tpi).kid_number != (*opi).kid_number) + if (tpi->kid_number != opi->kid_number) { return false; } @@ -679,6 +727,7 @@ NNTreeIterator::setItemNumber(QPDFObjectHandle const& node, int n) { this->node = node; this->item_number = n; + updateIValue(); } void @@ -961,7 +1010,7 @@ NNTreeImpl::repair() auto new_node = QPDFObjectHandle::newDictionary(); new_node.replaceKey(details.itemsKey(), QPDFObjectHandle::newArray()); NNTreeImpl repl(details, qpdf, new_node, false); - for (auto i: *this) + for (auto const& i: *this) { repl.insert(i.first, i.second); } @@ -1005,15 +1054,15 @@ NNTreeImpl::findInternal(QPDFObjectHandle key, bool return_prev_if_not_found) return end(); } else if (first_item.valid() && - details.keyValid((*first_item).first) && - details.compareKeys(key, (*first_item).first) < 0) + details.keyValid(first_item->first) && + details.compareKeys(key, first_item->first) < 0) { // Before the first key return end(); } else if (last_item.valid() && - details.keyValid((*last_item).first) && - details.compareKeys(key, (*last_item).first) > 0) + details.keyValid(last_item->first) && + details.compareKeys(key, last_item->first) > 0) { // After the last key if (return_prev_if_not_found) @@ -1097,10 +1146,10 @@ NNTreeImpl::insertFirst(QPDFObjectHandle key, QPDFObjectHandle value) } items.insertItem(0, key); items.insertItem(1, value); - iter.item_number = 0; + iter.setItemNumber(iter.node, 0); iter.resetLimits(iter.node, iter.lastPathElement()); iter.split(iter.node, iter.lastPathElement()); - return begin(); + return iter; } NNTreeImpl::iterator @@ -1112,11 +1161,12 @@ NNTreeImpl::insert(QPDFObjectHandle key, QPDFObjectHandle value) QTC::TC("qpdf", "NNTree insert inserts first"); return insertFirst(key, value); } - else if (details.compareKeys(key, (*iter).first) == 0) + else if (details.compareKeys(key, iter->first) == 0) { QTC::TC("qpdf", "NNTree insert replaces"); auto items = iter.node.getKey(details.itemsKey()); items.setArrayItem(iter.item_number + 1, value); + iter.updateIValue(); } else { @@ -1137,7 +1187,7 @@ NNTreeImpl::remove(QPDFObjectHandle key, QPDFObjectHandle* value) } if (value) { - *value = (*iter).second; + *value = iter->second; } iter.remove(); return true; diff --git a/libqpdf/QPDF.cc b/libqpdf/QPDF.cc index bb9b511d..f690d30a 100644 --- a/libqpdf/QPDF.cc +++ b/libqpdf/QPDF.cc @@ -3011,7 +3011,7 @@ QPDF::findAttachmentStreams() return; } QPDFNameTreeObjectHelper ef_tree(embedded_files, *this); - for (auto i: ef_tree) + for (auto const& i: ef_tree) { QPDFObjectHandle item = i.second; if (item.isDictionary() && diff --git a/libqpdf/QPDFNameTreeObjectHelper.cc b/libqpdf/QPDFNameTreeObjectHelper.cc index 7abc761a..1dc7f205 100644 --- a/libqpdf/QPDFNameTreeObjectHelper.cc +++ b/libqpdf/QPDFNameTreeObjectHelper.cc @@ -79,6 +79,7 @@ QPDFNameTreeObjectHelper::iterator& QPDFNameTreeObjectHelper::iterator::operator++() { ++(*impl); + updateIValue(); return *this; } @@ -86,14 +87,38 @@ QPDFNameTreeObjectHelper::iterator& QPDFNameTreeObjectHelper::iterator::operator--() { --(*impl); + updateIValue(); return *this; } +void +QPDFNameTreeObjectHelper::iterator::updateIValue() +{ + if (impl->valid()) + { + auto p = *impl; + this->ivalue.first = p->first.getUTF8Value(); + this->ivalue.second = p->second; + } + else + { + this->ivalue.first = ""; + this->ivalue.second = QPDFObjectHandle(); + } +} + QPDFNameTreeObjectHelper::iterator::reference QPDFNameTreeObjectHelper::iterator::operator*() { - auto p = **impl; - return std::make_pair(p.first.getUTF8Value(), p.second); + updateIValue(); + return this->ivalue; +} + +QPDFNameTreeObjectHelper::iterator::pointer +QPDFNameTreeObjectHelper::iterator::operator->() +{ + updateIValue(); + return &this->ivalue; } bool @@ -107,12 +132,14 @@ QPDFNameTreeObjectHelper::iterator::insertAfter( std::string const& key, QPDFObjectHandle value) { impl->insertAfter(QPDFObjectHandle::newUnicodeString(key), value); + updateIValue(); } void QPDFNameTreeObjectHelper::iterator::remove() { impl->remove(); + updateIValue(); } QPDFNameTreeObjectHelper::iterator @@ -175,7 +202,7 @@ QPDFNameTreeObjectHelper::findObject( { return false; } - oh = (*i).second; + oh = i->second; return true; } diff --git a/libqpdf/QPDFNumberTreeObjectHelper.cc b/libqpdf/QPDFNumberTreeObjectHelper.cc index 426891e2..a66a5f48 100644 --- a/libqpdf/QPDFNumberTreeObjectHelper.cc +++ b/libqpdf/QPDFNumberTreeObjectHelper.cc @@ -75,6 +75,7 @@ QPDFNumberTreeObjectHelper::iterator& QPDFNumberTreeObjectHelper::iterator::operator++() { ++(*impl); + updateIValue(); return *this; } @@ -82,14 +83,38 @@ QPDFNumberTreeObjectHelper::iterator& QPDFNumberTreeObjectHelper::iterator::operator--() { --(*impl); + updateIValue(); return *this; } +void +QPDFNumberTreeObjectHelper::iterator::updateIValue() +{ + if (impl->valid()) + { + auto p = *impl; + this->ivalue.first = p->first.getIntValue(); + this->ivalue.second = p->second; + } + else + { + this->ivalue.first = 0; + this->ivalue.second = QPDFObjectHandle(); + } +} + QPDFNumberTreeObjectHelper::iterator::reference QPDFNumberTreeObjectHelper::iterator::operator*() { - auto p = **impl; - return std::make_pair(p.first.getIntValue(), p.second); + updateIValue(); + return this->ivalue; +} + +QPDFNumberTreeObjectHelper::iterator::pointer +QPDFNumberTreeObjectHelper::iterator::operator->() +{ + updateIValue(); + return &this->ivalue; } bool @@ -103,12 +128,14 @@ QPDFNumberTreeObjectHelper::iterator::insertAfter( numtree_number key, QPDFObjectHandle value) { impl->insertAfter(QPDFObjectHandle::newInteger(key), value); + updateIValue(); } void QPDFNumberTreeObjectHelper::iterator::remove() { impl->remove(); + updateIValue(); } QPDFNumberTreeObjectHelper::iterator @@ -162,7 +189,7 @@ QPDFNumberTreeObjectHelper::getMin() { return 0; } - return (*i).first; + return i->first; } QPDFNumberTreeObjectHelper::numtree_number @@ -173,7 +200,7 @@ QPDFNumberTreeObjectHelper::getMax() { return 0; } - return (*i).first; + return i->first; } bool @@ -192,7 +219,7 @@ QPDFNumberTreeObjectHelper::findObject( { return false; } - oh = (*i).second; + oh = i->second; return true; } @@ -206,8 +233,8 @@ QPDFNumberTreeObjectHelper::findObjectAtOrBelow( { return false; } - oh = (*i).second; - offset = idx - (*i).first; + oh = i->second; + offset = idx - i->first; return true; } diff --git a/libqpdf/qpdf/NNTree.hh b/libqpdf/qpdf/NNTree.hh index e8360df1..4a843a73 100644 --- a/libqpdf/qpdf/NNTree.hh +++ b/libqpdf/qpdf/NNTree.hh @@ -6,6 +6,7 @@ #include #include +#include class NNTreeDetails { @@ -18,9 +19,6 @@ class NNTreeDetails class NNTreeImpl; class NNTreeIterator: public std::iterator< std::bidirectional_iterator_tag, - std::pair, - void, - std::pair*, std::pair> { friend class NNTreeImpl; @@ -41,6 +39,7 @@ class NNTreeIterator: public std::iterator< return t; } reference operator*(); + pointer operator->(); bool operator==(NNTreeIterator const& other) const; bool operator!=(NNTreeIterator const& other) const { @@ -63,6 +62,7 @@ class NNTreeIterator: public std::iterator< // ABI: for qpdf 11, make qpdf a reference NNTreeIterator(NNTreeImpl& impl); + void updateIValue(bool allow_invalid = true); bool deepen(QPDFObjectHandle node, bool first, bool allow_empty); void setItemNumber(QPDFObjectHandle const& node, int); void addPathElement(QPDFObjectHandle const& node, int kid_number); @@ -79,6 +79,7 @@ class NNTreeIterator: public std::iterator< std::list path; QPDFObjectHandle node; int item_number; + value_type ivalue; }; class NNTreeImpl -- cgit v1.2.3-70-g09d2