From 12f1eb15ca3fed6310402847559a7c99d3c77847 Mon Sep 17 00:00:00 2001 From: Jay Berkenbilt Date: Sat, 2 Apr 2022 17:14:10 -0400 Subject: Programmatically apply new formatting to code Run this: for i in **/*.cc **/*.c **/*.h **/*.hh; do clang-format < $i >| $i.new && mv $i.new $i done --- libqpdf/NNTree.cc | 637 +++++++++++++++++++++--------------------------------- 1 file changed, 247 insertions(+), 390 deletions(-) (limited to 'libqpdf/NNTree.cc') diff --git a/libqpdf/NNTree.cc b/libqpdf/NNTree.cc index ceb69c8d..c85ac4cf 100644 --- a/libqpdf/NNTree.cc +++ b/libqpdf/NNTree.cc @@ -9,8 +9,7 @@ static std::string get_description(QPDFObjectHandle& node) { std::string result("Name/Number tree node"); - if (node.isIndirect()) - { + if (node.isIndirect()) { result += " (object " + QUtil::int_to_string(node.getObjectID()) + ")"; } return result; @@ -21,11 +20,13 @@ warn(QPDF* qpdf, QPDFObjectHandle& node, std::string const& msg) { // ABI: in qpdf 11, change to a reference. - if (qpdf) - { + if (qpdf) { qpdf->warn(QPDFExc( - qpdf_e_damaged_pdf, - qpdf->getFilename(), get_description(node), 0, msg)); + qpdf_e_damaged_pdf, + qpdf->getFilename(), + get_description(node), + 0, + msg)); } } @@ -34,13 +35,14 @@ error(QPDF* qpdf, QPDFObjectHandle& node, std::string const& msg) { // ABI: in qpdf 11, change to a reference. - if (qpdf) - { - throw QPDFExc(qpdf_e_damaged_pdf, - qpdf->getFilename(), get_description(node), 0, msg); - } - else - { + if (qpdf) { + throw QPDFExc( + qpdf_e_damaged_pdf, + qpdf->getFilename(), + get_description(node), + 0, + msg); + } else { throw std::runtime_error(get_description(node) + ": " + msg); } } @@ -73,29 +75,21 @@ NNTreeIterator::updateIValue(bool allow_invalid) // measure, we also call updateIValue in operator* and operator->. bool okay = false; - if ((item_number >= 0) && - this->node.isInitialized() && - this->node.isDictionary()) - { + 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()) - { + 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 - { + 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"); + 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(); @@ -114,29 +108,24 @@ NNTreeIterator::getNextKid(PathElement& pe, bool backward) { QPDFObjectHandle result; bool found = false; - while (! found) - { + while (!found) { pe.kid_number += backward ? -1 : 1; auto kids = pe.node.getKey("/Kids"); - if ((pe.kid_number >= 0) && (pe.kid_number < kids.getArrayNItems())) - { + if ((pe.kid_number >= 0) && (pe.kid_number < kids.getArrayNItems())) { result = kids.getArrayItem(pe.kid_number); if (result.isDictionary() && (result.hasKey("/Kids") || - result.hasKey(impl.details.itemsKey()))) - { + result.hasKey(impl.details.itemsKey()))) { found = true; - } - else - { + } else { QTC::TC("qpdf", "NNTree skip invalid kid"); - warn(impl.qpdf, pe.node, - "skipping over invalid kid at index " + - QUtil::int_to_string(pe.kid_number)); + warn( + impl.qpdf, + pe.node, + "skipping over invalid kid at index " + + QUtil::int_to_string(pe.kid_number)); } - } - else - { + } else { result = QPDFObjectHandle::newNull(); found = true; } @@ -153,55 +142,46 @@ NNTreeIterator::valid() const void NNTreeIterator::increment(bool backward) { - if (this->item_number < 0) - { + if (this->item_number < 0) { QTC::TC("qpdf", "NNTree increment end()"); - deepen(impl.oh, ! backward, true); + deepen(impl.oh, !backward, true); return; } bool found_valid_key = false; - while (valid() && (! found_valid_key)) - { + while (valid() && (!found_valid_key)) { this->item_number += backward ? -2 : 2; auto items = this->node.getKey(impl.details.itemsKey()); if ((this->item_number < 0) || - (this->item_number >= items.getArrayNItems())) - { + (this->item_number >= items.getArrayNItems())) { bool found = false; setItemNumber(QPDFObjectHandle(), -1); - while (! (found || this->path.empty())) - { + while (!(found || this->path.empty())) { auto& element = this->path.back(); auto pe_node = getNextKid(element, backward); - if (pe_node.isNull()) - { + if (pe_node.isNull()) { this->path.pop_back(); - } - else - { - found = deepen(pe_node, ! backward, false); + } else { + found = deepen(pe_node, !backward, false); } } } - if (this->item_number >= 0) - { + if (this->item_number >= 0) { items = this->node.getKey(impl.details.itemsKey()); - if (this->item_number + 1 >= items.getArrayNItems()) - { + if (this->item_number + 1 >= items.getArrayNItems()) { QTC::TC("qpdf", "NNTree skip item at end of short items"); - warn(impl.qpdf, this->node, - "items array doesn't have enough elements"); - } - else if (! impl.details.keyValid( - items.getArrayItem(this->item_number))) - { + warn( + impl.qpdf, + this->node, + "items array doesn't have enough elements"); + } else if (!impl.details.keyValid( + items.getArrayItem(this->item_number))) { QTC::TC("qpdf", "NNTree skip invalid key"); - warn(impl.qpdf, this->node, - "item " + QUtil::int_to_string(this->item_number) + - " has the wrong type"); - } - else - { + warn( + impl.qpdf, + this->node, + "item " + QUtil::int_to_string(this->item_number) + + " has the wrong type"); + } else { found_valid_key = true; } } @@ -209,14 +189,12 @@ NNTreeIterator::increment(bool backward) } void -NNTreeIterator::resetLimits(QPDFObjectHandle node, - std::list::iterator parent) +NNTreeIterator::resetLimits( + QPDFObjectHandle node, std::list::iterator parent) { bool done = false; - while (! done) - { - if (parent == this->path.end()) - { + while (!done) { + if (parent == this->path.end()) { QTC::TC("qpdf", "NNTree remove limits from root"); node.removeKey("/Limits"); done = true; @@ -230,65 +208,51 @@ NNTreeIterator::resetLimits(QPDFObjectHandle node, bool changed = true; QPDFObjectHandle first; QPDFObjectHandle last; - if (nitems >= 2) - { + if (nitems >= 2) { first = items.getArrayItem(0); last = items.getArrayItem((nitems - 1) & ~1); - } - else if (nkids > 0) - { + } else if (nkids > 0) { auto first_kid = kids.getArrayItem(0); auto last_kid = kids.getArrayItem(nkids - 1); - if (first_kid.isDictionary() && last_kid.isDictionary()) - { + if (first_kid.isDictionary() && last_kid.isDictionary()) { auto first_limits = first_kid.getKey("/Limits"); auto last_limits = last_kid.getKey("/Limits"); if (first_limits.isArray() && (first_limits.getArrayNItems() >= 2) && last_limits.isArray() && - (last_limits.getArrayNItems() >= 2)) - { + (last_limits.getArrayNItems() >= 2)) { first = first_limits.getArrayItem(0); last = last_limits.getArrayItem(1); } } } - if (first.isInitialized() && last.isInitialized()) - { + if (first.isInitialized() && last.isInitialized()) { auto limits = QPDFObjectHandle::newArray(); limits.appendItem(first); limits.appendItem(last); auto olimits = node.getKey("/Limits"); - if (olimits.isArray() && (olimits.getArrayNItems() == 2)) - { + if (olimits.isArray() && (olimits.getArrayNItems() == 2)) { auto ofirst = olimits.getArrayItem(0); auto olast = olimits.getArrayItem(1); if (impl.details.keyValid(ofirst) && impl.details.keyValid(olast) && (impl.details.compareKeys(first, ofirst) == 0) && - (impl.details.compareKeys(last, olast) == 0)) - { + (impl.details.compareKeys(last, olast) == 0)) { QTC::TC("qpdf", "NNTree limits didn't change"); changed = false; } } - if (changed) - { + if (changed) { node.replaceKey("/Limits", limits); } - } - else - { + } else { QTC::TC("qpdf", "NNTree unable to determine limits"); warn(impl.qpdf, node, "unable to determine limits"); } - if ((! changed) || (parent == this->path.begin())) - { + if ((!changed) || (parent == this->path.begin())) { done = true; - } - else - { + } else { node = parent->node; --parent; } @@ -296,8 +260,8 @@ NNTreeIterator::resetLimits(QPDFObjectHandle node, } void -NNTreeIterator::split(QPDFObjectHandle to_split, - std::list::iterator parent) +NNTreeIterator::split( + QPDFObjectHandle to_split, std::list::iterator parent) { // Split some node along the path to the item pointed to by this // iterator, and adjust the iterator so it points to the same @@ -327,13 +291,10 @@ NNTreeIterator::split(QPDFObjectHandle to_split, // node: A // item_number: 0 - if (! this->impl.qpdf) - { - throw std::logic_error( - "NNTreeIterator::split called with null qpdf"); + if (!this->impl.qpdf) { + throw std::logic_error("NNTreeIterator::split called with null qpdf"); } - if (! valid()) - { + if (!valid()) { throw std::logic_error( "NNTreeIterator::split called an invalid iterator"); } @@ -349,29 +310,23 @@ NNTreeIterator::split(QPDFObjectHandle to_split, int n = 0; std::string key; int threshold = 0; - if (nkids > 0) - { + if (nkids > 0) { QTC::TC("qpdf", "NNTree split kids"); first_half = kids; n = nkids; threshold = impl.split_threshold; key = "/Kids"; - } - else if (nitems > 0) - { + } else if (nitems > 0) { QTC::TC("qpdf", "NNTree split items"); first_half = items; n = nitems; threshold = 2 * impl.split_threshold; key = impl.details.itemsKey(); - } - else - { + } else { throw std::logic_error("NNTreeIterator::split called on invalid node"); } - if (n <= threshold) - { + if (n <= threshold) { return; } @@ -381,8 +336,7 @@ NNTreeIterator::split(QPDFObjectHandle to_split, // CURRENT STATE: tree is in original state; iterator is valid and // unchanged. - if (is_root) - { + if (is_root) { // What we want to do is to create a new node for the second // half of the items and put it in the parent's /Kids array // right after the element that points to the current to_split @@ -404,21 +358,18 @@ NNTreeIterator::split(QPDFObjectHandle to_split, // non-root case so remaining logic can handle them in the // same way. - auto first_node = impl.qpdf->makeIndirectObject( - QPDFObjectHandle::newDictionary()); + auto first_node = + impl.qpdf->makeIndirectObject(QPDFObjectHandle::newDictionary()); first_node.replaceKey(key, first_half); QPDFObjectHandle new_kids = QPDFObjectHandle::newArray(); new_kids.appendItem(first_node); to_split.removeKey("/Limits"); // already shouldn't be there for root to_split.removeKey(impl.details.itemsKey()); to_split.replaceKey("/Kids", new_kids); - if (is_leaf) - { + if (is_leaf) { QTC::TC("qpdf", "NNTree split root + leaf"); this->node = first_node; - } - else - { + } else { QTC::TC("qpdf", "NNTree split root + !leaf"); auto next = this->path.begin(); next->node = first_node; @@ -436,16 +387,15 @@ NNTreeIterator::split(QPDFObjectHandle to_split, // items into the second half array. QPDFObjectHandle second_half = QPDFObjectHandle::newArray(); int start_idx = ((n / 2) & ~1); - while (first_half.getArrayNItems() > start_idx) - { + while (first_half.getArrayNItems() > start_idx) { second_half.appendItem(first_half.getArrayItem(start_idx)); first_half.eraseItem(start_idx); } resetLimits(to_split, parent); // Create a new node to contain the second half - QPDFObjectHandle second_node = impl.qpdf->makeIndirectObject( - QPDFObjectHandle::newDictionary()); + QPDFObjectHandle second_node = + impl.qpdf->makeIndirectObject(QPDFObjectHandle::newDictionary()); second_node.replaceKey(key, second_half); resetLimits(second_node, parent); @@ -464,23 +414,18 @@ NNTreeIterator::split(QPDFObjectHandle to_split, auto cur_elem = parent; ++cur_elem; // points to end() for leaf nodes int old_idx = (is_leaf ? this->item_number : cur_elem->kid_number); - if (old_idx >= start_idx) - { + if (old_idx >= start_idx) { ++parent->kid_number; - if (is_leaf) - { + if (is_leaf) { QTC::TC("qpdf", "NNTree split second half item"); setItemNumber(second_node, this->item_number - start_idx); - } - else - { + } else { QTC::TC("qpdf", "NNTree split second half kid"); cur_elem->node = second_node; cur_elem->kid_number -= start_idx; } } - if (! is_root) - { + if (!is_root) { QTC::TC("qpdf", "NNTree split parent"); auto next = parent->node; resetLimits(next, parent); @@ -493,8 +438,7 @@ std::list::iterator NNTreeIterator::lastPathElement() { auto result = this->path.end(); - if (! this->path.empty()) - { + if (!this->path.empty()) { --result; } return result; @@ -503,8 +447,7 @@ NNTreeIterator::lastPathElement() void NNTreeIterator::insertAfter(QPDFObjectHandle key, QPDFObjectHandle value) { - if (! valid()) - { + if (!valid()) { QTC::TC("qpdf", "NNTree insertAfter inserts first"); impl.insertFirst(key, value); deepen(impl.oh, true, false); @@ -512,12 +455,10 @@ NNTreeIterator::insertAfter(QPDFObjectHandle key, QPDFObjectHandle value) } auto items = this->node.getKey(impl.details.itemsKey()); - if (! items.isArray()) - { + if (!items.isArray()) { error(impl.qpdf, node, "node contains no items array"); } - if (items.getArrayNItems() < this->item_number + 2) - { + if (items.getArrayNItems() < this->item_number + 2) { error(impl.qpdf, node, "insert: items array is too short"); } items.insertItem(this->item_number + 2, key); @@ -533,51 +474,44 @@ NNTreeIterator::remove() // Remove this item, leaving the tree valid and this iterator // pointing to the next item. - if (! valid()) - { + 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"); + 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) - { + if (nitems > 0) { // There are still items left - if ((this->item_number == 0) || (this->item_number == nitems)) - { + 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) - { + 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) - { + } 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"); updateIValue(); - } - else - { + } else { // We already checked to ensure this condition would not // happen. throw std::logic_error( @@ -586,8 +520,7 @@ NNTreeIterator::remove() return; } - if (this->path.empty()) - { + 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"); @@ -601,64 +534,50 @@ NNTreeIterator::remove() // 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) - { + 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) - { + if (nkids > 0) { // The logic here is similar to the items case. - if ((element->kid_number == 0) || (element->kid_number == nkids)) - { + 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) - { + 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()) - { + if (valid()) { increment(false); - if (! valid()) - { + if (!valid()) { QTC::TC("qpdf", "NNTree erased last item in tree"); - } - else - { + } else { QTC::TC("qpdf", "NNTree erased last kid"); } } - } - else - { + } 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()) - { + } 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()); + element->node.replaceKey( + impl.details.itemsKey(), QPDFObjectHandle::newArray()); this->path.clear(); setItemNumber(impl.oh, -1); done = true; - } - else - { + } else { // Walk up the tree and continue QTC::TC("qpdf", "NNTree remove walking up tree"); this->path.pop_back(); @@ -697,27 +616,22 @@ NNTreeIterator::operator->() bool NNTreeIterator::operator==(NNTreeIterator const& other) const { - if ((this->item_number == -1) && (other.item_number == -1)) - { + if ((this->item_number == -1) && (other.item_number == -1)) { return true; } - if (this->path.size() != other.path.size()) - { + if (this->path.size() != other.path.size()) { return false; } auto tpi = this->path.begin(); auto opi = other.path.begin(); - while (tpi != this->path.end()) - { - if (tpi->kid_number != opi->kid_number) - { + while (tpi != this->path.end()) { + if (tpi->kid_number != opi->kid_number) { return false; } ++tpi; ++opi; } - if (this->item_number != other.item_number) - { + if (this->item_number != other.item_number) { return false; } return true; @@ -732,8 +646,7 @@ NNTreeIterator::setItemNumber(QPDFObjectHandle const& node, int n) } void -NNTreeIterator::addPathElement(QPDFObjectHandle const& node, - int kid_number) +NNTreeIterator::addPathElement(QPDFObjectHandle const& node, int kid_number) { this->path.push_back(PathElement(node, kid_number)); } @@ -749,33 +662,31 @@ NNTreeIterator::deepen(QPDFObjectHandle node, bool first, bool allow_empty) bool failed = false; std::set seen; - for (auto i: this->path) - { - if (i.node.isIndirect()) - { + for (auto i : this->path) { + if (i.node.isIndirect()) { seen.insert(i.node.getObjGen()); } } - while (! failed) - { - if (node.isIndirect()) - { + while (!failed) { + if (node.isIndirect()) { auto og = node.getObjGen(); - if (seen.count(og)) - { + if (seen.count(og)) { QTC::TC("qpdf", "NNTree deepen: loop"); - warn(impl.qpdf, node, - "loop detected while traversing name/number tree"); + warn( + impl.qpdf, + node, + "loop detected while traversing name/number tree"); failed = true; break; } seen.insert(og); } - if (! node.isDictionary()) - { + if (!node.isDictionary()) { QTC::TC("qpdf", "NNTree node is not a dictionary"); - warn(impl.qpdf, node, - "non-dictionary node while traversing name/number tree"); + warn( + impl.qpdf, + node, + "non-dictionary node while traversing name/number tree"); failed = true; break; } @@ -784,66 +695,61 @@ NNTreeIterator::deepen(QPDFObjectHandle node, bool first, bool allow_empty) int nkids = kids.isArray() ? kids.getArrayNItems() : 0; auto items = node.getKey(impl.details.itemsKey()); int nitems = items.isArray() ? items.getArrayNItems() : 0; - if (nitems > 0) - { + if (nitems > 0) { setItemNumber(node, first ? 0 : nitems - 2); break; - } - else if (nkids > 0) - { + } else if (nkids > 0) { int kid_number = first ? 0 : nkids - 1; addPathElement(node, kid_number); auto next = kids.getArrayItem(kid_number); - if (! next.isIndirect()) - { - if (impl.qpdf && impl.auto_repair) - { + if (!next.isIndirect()) { + if (impl.qpdf && impl.auto_repair) { QTC::TC("qpdf", "NNTree fix indirect kid"); - warn(impl.qpdf, node, - "converting kid number " + - QUtil::int_to_string(kid_number) + - " to an indirect object"); + warn( + impl.qpdf, + node, + "converting kid number " + + QUtil::int_to_string(kid_number) + + " to an indirect object"); next = impl.qpdf->makeIndirectObject(next); kids.setArrayItem(kid_number, next); - } - else - { + } else { QTC::TC("qpdf", "NNTree warn indirect kid"); - warn(impl.qpdf, node, - "kid number " + QUtil::int_to_string(kid_number) + - " is not an indirect object"); + warn( + impl.qpdf, + node, + "kid number " + QUtil::int_to_string(kid_number) + + " is not an indirect object"); } } node = next; - } - else if (allow_empty && items.isArray()) - { + } else if (allow_empty && items.isArray()) { QTC::TC("qpdf", "NNTree deepen found empty"); setItemNumber(node, -1); break; - } - else - { + } else { QTC::TC("qpdf", "NNTree deepen: invalid node"); - warn(impl.qpdf, node, - "name/number tree node has neither non-empty " + - impl.details.itemsKey() + " nor /Kids"); + warn( + impl.qpdf, + node, + "name/number tree node has neither non-empty " + + impl.details.itemsKey() + " nor /Kids"); failed = true; break; } } - if (failed) - { + if (failed) { this->path = opath; return false; } return true; } -NNTreeImpl::NNTreeImpl(NNTreeDetails const& details, - QPDF* qpdf, - QPDFObjectHandle& oh, - bool auto_repair) : +NNTreeImpl::NNTreeImpl( + NNTreeDetails const& details, + QPDF* qpdf, + QPDFObjectHandle& oh, + bool auto_repair) : details(details), qpdf(qpdf), split_threshold(32), @@ -887,19 +793,13 @@ NNTreeImpl::withinLimits(QPDFObjectHandle key, QPDFObjectHandle node) auto limits = node.getKey("/Limits"); if (limits.isArray() && (limits.getArrayNItems() >= 2) && details.keyValid(limits.getArrayItem(0)) && - details.keyValid(limits.getArrayItem(1))) - { - if (details.compareKeys(key, limits.getArrayItem(0)) < 0) - { + details.keyValid(limits.getArrayItem(1))) { + if (details.compareKeys(key, limits.getArrayItem(0)) < 0) { result = -1; - } - else if (details.compareKeys(key, limits.getArrayItem(1)) > 0) - { + } else if (details.compareKeys(key, limits.getArrayItem(1)) > 0) { result = 1; } - } - else - { + } else { QTC::TC("qpdf", "NNTree missing limits"); error(qpdf, node, "node is missing /Limits"); } @@ -908,15 +808,15 @@ NNTreeImpl::withinLimits(QPDFObjectHandle key, QPDFObjectHandle node) int NNTreeImpl::binarySearch( - QPDFObjectHandle key, QPDFObjectHandle items, - int num_items, bool return_prev_if_not_found, - int (NNTreeImpl::*compare)(QPDFObjectHandle& key, - QPDFObjectHandle& arr, - int item)) + QPDFObjectHandle key, + QPDFObjectHandle items, + int num_items, + bool return_prev_if_not_found, + int (NNTreeImpl::*compare)( + QPDFObjectHandle& key, QPDFObjectHandle& arr, int item)) { int max_idx = 1; - while (max_idx < num_items) - { + while (max_idx < num_items) { max_idx <<= 1; } @@ -928,56 +828,40 @@ NNTreeImpl::binarySearch( bool found_leq = false; int status = 0; - while ((! found) && (checks > 0)) - { - if (idx < num_items) - { + while ((!found) && (checks > 0)) { + if (idx < num_items) { status = (this->*compare)(key, items, idx); - if (status >= 0) - { + if (status >= 0) { found_leq = true; found_idx = idx; } - } - else - { + } else { // consider item to be below anything after the top status = -1; } - if (status == 0) - { + if (status == 0) { found = true; - } - else - { + } else { checks >>= 1; - if (checks > 0) - { + if (checks > 0) { step >>= 1; - if (step == 0) - { + if (step == 0) { step = 1; } - if (status < 0) - { + if (status < 0) { idx -= step; - } - else - { + } else { idx += step; } } } } - if (found || (found_leq && return_prev_if_not_found)) - { + if (found || (found_leq && return_prev_if_not_found)) { return found_idx; - } - else - { + } else { return -1; } } @@ -986,13 +870,14 @@ int NNTreeImpl::compareKeyItem( QPDFObjectHandle& key, QPDFObjectHandle& items, int idx) { - if (! ((items.isArray() && (items.getArrayNItems() > (2 * idx)) && - details.keyValid(items.getArrayItem(2 * idx))))) - { + if (!((items.isArray() && (items.getArrayNItems() > (2 * idx)) && + details.keyValid(items.getArrayItem(2 * idx))))) { QTC::TC("qpdf", "NNTree item is wrong type"); - error(qpdf, this->oh, - "item at index " + QUtil::int_to_string(2 * idx) + - " is not the right type"); + error( + qpdf, + this->oh, + "item at index " + QUtil::int_to_string(2 * idx) + + " is not the right type"); } return details.compareKeys(key, items.getArrayItem(2 * idx)); } @@ -1001,25 +886,24 @@ int NNTreeImpl::compareKeyKid( QPDFObjectHandle& key, QPDFObjectHandle& kids, int idx) { - if (! (kids.isArray() && (idx < kids.getArrayNItems()) && - kids.getArrayItem(idx).isDictionary())) - { + if (!(kids.isArray() && (idx < kids.getArrayNItems()) && + kids.getArrayItem(idx).isDictionary())) { QTC::TC("qpdf", "NNTree kid is invalid"); - error(qpdf, this->oh, - "invalid kid at index " + QUtil::int_to_string(idx)); + error( + qpdf, + this->oh, + "invalid kid at index " + QUtil::int_to_string(idx)); } return withinLimits(key, kids.getArrayItem(idx)); } - void NNTreeImpl::repair() { auto new_node = QPDFObjectHandle::newDictionary(); new_node.replaceKey(details.itemsKey(), QPDFObjectHandle::newArray()); NNTreeImpl repl(details, qpdf, new_node, false); - for (auto const& i: *this) - { + for (auto const& i : *this) { repl.insert(i.first, i.second); } this->oh.replaceKey("/Kids", new_node.getKey("/Kids")); @@ -1030,22 +914,18 @@ NNTreeImpl::repair() NNTreeImpl::iterator NNTreeImpl::find(QPDFObjectHandle key, bool return_prev_if_not_found) { - try - { + try { return findInternal(key, return_prev_if_not_found); - } - catch (QPDFExc& e) - { - if (this->auto_repair) - { + } catch (QPDFExc& e) { + if (this->auto_repair) { QTC::TC("qpdf", "NNTree repair"); - warn(qpdf, this->oh, - std::string("attempting to repair after error: ") + e.what()); + warn( + qpdf, + this->oh, + std::string("attempting to repair after error: ") + e.what()); repair(); return findInternal(key, return_prev_if_not_found); - } - else - { + } else { throw e; } } @@ -1056,29 +936,21 @@ NNTreeImpl::findInternal(QPDFObjectHandle key, bool return_prev_if_not_found) { auto first_item = begin(); auto last_item = end(); - if (first_item == end()) - { + if (first_item == end()) { // Empty return end(); - } - else if (first_item.valid() && - details.keyValid(first_item->first) && - details.compareKeys(key, first_item->first) < 0) - { + } else if ( + first_item.valid() && 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) - { + } else if ( + last_item.valid() && details.keyValid(last_item->first) && + details.compareKeys(key, last_item->first) > 0) { // After the last key - if (return_prev_if_not_found) - { + if (return_prev_if_not_found) { return last_item; - } - else - { + } else { return end(); } } @@ -1087,11 +959,9 @@ NNTreeImpl::findInternal(QPDFObjectHandle key, bool return_prev_if_not_found) auto node = this->oh; iterator result(*this); - while (true) - { + while (true) { auto og = node.getObjGen(); - if (seen.count(og)) - { + if (seen.count(og)) { QTC::TC("qpdf", "NNTree loop in find"); error(qpdf, node, "loop detected in find"); } @@ -1101,34 +971,31 @@ NNTreeImpl::findInternal(QPDFObjectHandle key, bool return_prev_if_not_found) int nkids = kids.isArray() ? kids.getArrayNItems() : 0; auto items = node.getKey(details.itemsKey()); int nitems = items.isArray() ? items.getArrayNItems() : 0; - if (nitems > 0) - { + if (nitems > 0) { int idx = binarySearch( - key, items, nitems / 2, return_prev_if_not_found, + key, + items, + nitems / 2, + return_prev_if_not_found, &NNTreeImpl::compareKeyItem); - if (idx >= 0) - { + if (idx >= 0) { result.setItemNumber(node, 2 * idx); } break; - } - else if (nkids > 0) - { + } else if (nkids > 0) { int idx = binarySearch( - key, kids, nkids, true, - &NNTreeImpl::compareKeyKid); - if (idx == -1) - { + key, kids, nkids, true, &NNTreeImpl::compareKeyKid); + if (idx == -1) { QTC::TC("qpdf", "NNTree -1 in binary search"); - error(qpdf, node, - "unexpected -1 from binary search of kids;" - " limits may by wrong"); + error( + qpdf, + node, + "unexpected -1 from binary search of kids;" + " limits may by wrong"); } result.addPathElement(node, idx); node = kids.getArrayItem(idx); - } - else - { + } else { QTC::TC("qpdf", "NNTree bad node during find"); error(qpdf, node, "bad node during find"); } @@ -1142,13 +1009,10 @@ NNTreeImpl::insertFirst(QPDFObjectHandle key, QPDFObjectHandle value) { auto iter = begin(); QPDFObjectHandle items; - if (iter.node.isInitialized() && - iter.node.isDictionary()) - { + if (iter.node.isInitialized() && iter.node.isDictionary()) { items = iter.node.getKey(details.itemsKey()); } - if (! (items.isInitialized() && items.isArray())) - { + if (!(items.isInitialized() && items.isArray())) { QTC::TC("qpdf", "NNTree no valid items node in insertFirst"); error(qpdf, this->oh, "unable to find a valid items node"); } @@ -1164,20 +1028,15 @@ NNTreeImpl::iterator NNTreeImpl::insert(QPDFObjectHandle key, QPDFObjectHandle value) { auto iter = find(key, true); - if (! iter.valid()) - { + if (!iter.valid()) { 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 - { + } else { QTC::TC("qpdf", "NNTree insert inserts after"); iter.insertAfter(key, value); } @@ -1188,13 +1047,11 @@ bool NNTreeImpl::remove(QPDFObjectHandle key, QPDFObjectHandle* value) { auto iter = find(key, false); - if (! iter.valid()) - { + if (!iter.valid()) { QTC::TC("qpdf", "NNTree remove not found"); return false; } - if (value) - { + if (value) { *value = iter->second; } iter.remove(); -- cgit v1.2.3-54-g00ecf