From e7e20772ed29f3eb9756b31fe0bd9bc29a445891 Mon Sep 17 00:00:00 2001 From: Jay Berkenbilt Date: Sun, 24 Jan 2021 11:48:46 -0500 Subject: name/number trees: remove --- libqpdf/NNTree.cc | 166 +++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 164 insertions(+), 2 deletions(-) (limited to 'libqpdf/NNTree.cc') diff --git a/libqpdf/NNTree.cc b/libqpdf/NNTree.cc index 02237939..4f9ddcce 100644 --- a/libqpdf/NNTree.cc +++ b/libqpdf/NNTree.cc @@ -163,6 +163,13 @@ NNTreeIterator::resetLimits(QPDFObjectHandle node, bool done = false; while (! done) { + if (parent == this->path.end()) + { + QTC::TC("qpdf", "NNTree remove limits from root"); + node.removeKey("/Limits"); + done = true; + break; + } auto kids = node.getKey("/Kids"); int nkids = kids.isArray() ? kids.getArrayNItems() : 0; auto items = node.getKey(impl.details.itemsKey()); @@ -459,7 +466,7 @@ NNTreeIterator::insertAfter(QPDFObjectHandle key, QPDFObjectHandle value) } if (items.getArrayNItems() < this->item_number + 2) { - error(impl.qpdf, node, "items array is too short"); + error(impl.qpdf, node, "insert: items array is too short"); } items.insertItem(this->item_number + 2, key); items.insertItem(this->item_number + 3, value); @@ -468,6 +475,144 @@ NNTreeIterator::insertAfter(QPDFObjectHandle key, QPDFObjectHandle value) increment(false); } +void +NNTreeIterator::remove() +{ + // Remove this item, leaving the tree valid and this iterator + // pointing to the next item. + + if (! valid()) + { + throw std::logic_error("attempt made to remove an invalid iterator"); + } + auto items = this->node.getKey(impl.details.itemsKey()); + int nitems = items.getArrayNItems(); + if (this->item_number + 2 > nitems) + { + error(impl.qpdf, this->node, + "found short items array while removing an item"); + } + + items.eraseItem(this->item_number); + items.eraseItem(this->item_number); + nitems -= 2; + + if (nitems > 0) + { + // There are still items left + + if ((this->item_number == 0) || (this->item_number == nitems)) + { + // We removed either the first or last item of an items array + // that remains non-empty, so we have to adjust limits. + QTC::TC("qpdf", "NNTree remove reset limits"); + resetLimits(this->node, lastPathElement()); + } + + if (this->item_number == nitems) + { + // We removed the last item of a non-empty items array, so + // advance to the successor of the previous item. + QTC::TC("qpdf", "NNTree erased last item"); + this->item_number -= 2; + increment(false); + } + else if (this->item_number < nitems) + { + // 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"); + } + else + { + // We already checked to ensure this condition would not + // happen. + throw std::logic_error( + "NNTreeIterator::remove: item_number > nitems after erase"); + } + return; + } + + if (this->path.empty()) + { + // Special case: if this is the root node, we can leave it + // empty. + QTC::TC("qpdf", "NNTree erased all items on leaf/root"); + setItemNumber(impl.oh, -1); + return; + } + + QTC::TC("qpdf", "NNTree items is empty after remove"); + + // We removed the last item from this items array, so we need to + // remove this node from the parent on up the tree. Then we need + // to position ourselves at the removed item's successor. + bool done = false; + while (! done) + { + auto element = lastPathElement(); + auto parent = element; + --parent; + auto kids = element->node.getKey("/Kids"); + kids.eraseItem(element->kid_number); + auto nkids = kids.getArrayNItems(); + if (nkids > 0) + { + // The logic here is similar to the items case. + if ((element->kid_number == 0) || (element->kid_number == nkids)) + { + QTC::TC("qpdf", "NNTree erased first or last kid"); + resetLimits(element->node, parent); + } + if (element->kid_number == nkids) + { + // Move to the successor of the last child of the + // previous kid. + setItemNumber(QPDFObjectHandle(), -1); + --element->kid_number; + deepen(kids.getArrayItem(element->kid_number), false, true); + if (valid()) + { + increment(false); + if (! valid()) + { + QTC::TC("qpdf", "NNTree erased last item in tree"); + } + else + { + QTC::TC("qpdf", "NNTree erased last kid"); + } + } + } + else + { + // Next kid is in deleted kid's position + QTC::TC("qpdf", "NNTree erased non-last kid"); + deepen(kids.getArrayItem(element->kid_number), true, true); + } + done = true; + } + else if (parent == this->path.end()) + { + // We erased the very last item. Convert the root to an + // empty items array. + QTC::TC("qpdf", "NNTree non-flat tree is empty after remove"); + element->node.removeKey("/Kids"); + element->node.replaceKey(impl.details.itemsKey(), + QPDFObjectHandle::newArray()); + this->path.clear(); + setItemNumber(impl.oh, -1); + done = true; + } + else + { + // Walk up the tree and continue + QTC::TC("qpdf", "NNTree remove walking up tree"); + this->path.pop_back(); + } + } +} + NNTreeIterator& NNTreeIterator::operator++() { @@ -494,7 +639,7 @@ NNTreeIterator::operator*() auto items = this->node.getKey(impl.details.itemsKey()); if (items.getArrayNItems() < this->item_number + 2) { - error(impl.qpdf, node, "items array is too short"); + 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)); @@ -980,3 +1125,20 @@ NNTreeImpl::insert(QPDFObjectHandle key, QPDFObjectHandle value) } return iter; } + +bool +NNTreeImpl::remove(QPDFObjectHandle key, QPDFObjectHandle* value) +{ + auto iter = find(key, false); + if (! iter.valid()) + { + QTC::TC("qpdf", "NNTree remove not found"); + return false; + } + if (value) + { + *value = (*iter).second; + } + iter.remove(); + return true; +} -- cgit v1.2.3-54-g00ecf