From 18c1ffe0df335a46cddbeb96e2cb939d850df9fa Mon Sep 17 00:00:00 2001 From: m-holger Date: Sat, 25 Mar 2023 12:07:04 +0000 Subject: Change underlying data structure of QPDF_Array in non-sparse mode to std::vector --- libqpdf/OHArray.cc | 109 +++++++++++++----------------------------------- libqpdf/QPDF_Array.cc | 6 +-- libqpdf/qpdf/OHArray.hh | 13 ++---- 3 files changed, 35 insertions(+), 93 deletions(-) diff --git a/libqpdf/OHArray.cc b/libqpdf/OHArray.cc index 436fa4f2..e25e1239 100644 --- a/libqpdf/OHArray.cc +++ b/libqpdf/OHArray.cc @@ -5,120 +5,82 @@ #include -OHArray::OHArray() : - n_elements(0) +static const QPDFObjectHandle null_oh = QPDFObjectHandle::newNull(); + +OHArray::OHArray() { } size_t OHArray::size() const { - return this->n_elements; + return elements.size(); } void OHArray::append(QPDFObjectHandle oh) { - if (!oh.isDirectNull()) { - this->elements[this->n_elements] = oh; - } - ++this->n_elements; + elements.push_back(oh.getObj()); } void OHArray::append(std::shared_ptr&& obj) { - if (obj->getTypeCode() != ::ot_null || !obj->getObjGen().isIndirect()) { - this->elements[this->n_elements] = std::move(obj); - } - ++this->n_elements; + elements.push_back(std::move(obj)); } QPDFObjectHandle OHArray::at(size_t idx) const { - if (idx >= this->n_elements) { + if (idx >= elements.size()) { throw std::logic_error( "INTERNAL ERROR: bounds error accessing OHArray element"); } - auto const& iter = this->elements.find(idx); - if (iter == this->elements.end()) { - return QPDFObjectHandle::newNull(); - } else { - return (*iter).second; - } -} - -void -OHArray::remove_last() -{ - if (this->n_elements == 0) { - throw std::logic_error("INTERNAL ERROR: attempt to remove" - " last item from empty OHArray"); - } - --this->n_elements; - this->elements.erase(this->n_elements); + auto const& obj = elements.at(idx); + return obj ? obj : null_oh; } void OHArray::disconnect() { - for (auto& iter: this->elements) { - QPDFObjectHandle::DisconnectAccess::disconnect(iter.second); + for (auto const& iter: elements) { + if (iter) { + QPDFObjectHandle oh = iter; + QPDFObjectHandle::DisconnectAccess::disconnect(oh); + } } } void OHArray::setAt(size_t idx, QPDFObjectHandle oh) { - if (idx >= this->n_elements) { + if (idx >= elements.size()) { throw std::logic_error("bounds error setting item in OHArray"); } - if (oh.isDirectNull()) { - this->elements.erase(idx); - } else { - this->elements[idx] = oh; - } + elements[idx] = oh.getObj(); } void OHArray::erase(size_t idx) { - if (idx >= this->n_elements) { + if (idx >= elements.size()) { throw std::logic_error("bounds error erasing item from OHArray"); } - decltype(this->elements) dest; - for (auto const& iter: this->elements) { - if (iter.first < idx) { - dest.insert(iter); - } else if (iter.first > idx) { - dest[iter.first - 1] = iter.second; - } - } - this->elements = dest; - --this->n_elements; + int n = int(idx); + elements.erase(elements.cbegin() + n); } void OHArray::insert(size_t idx, QPDFObjectHandle oh) { - if (idx > this->n_elements) { + if (idx > elements.size()) { throw std::logic_error("bounds error inserting item to OHArray"); - } else if (idx == this->n_elements) { + } else if (idx == elements.size()) { // Allow inserting to the last position - append(oh); + append(oh.getObj()); } else { - decltype(this->elements) dest; - for (auto const& iter: this->elements) { - if (iter.first < idx) { - dest.insert(iter); - } else { - dest[iter.first + 1] = iter.second; - } - } - this->elements = dest; - this->elements[idx] = oh; - ++this->n_elements; + int n = int(idx); + elements.insert(elements.cbegin() + n, oh.getObj()); } } @@ -126,23 +88,12 @@ OHArray OHArray::copy() { OHArray result; - result.n_elements = this->n_elements; - for (auto const& element: this->elements) { - auto value = element.second; - result.elements[element.first] = - value.isIndirect() ? value : value.shallowCopy(); + result.elements.reserve(elements.size()); + for (auto const& element: elements) { + result.elements.push_back( + element ? (element->getObjGen().isIndirect() ? element + : element->copy()) + : element); } return result; } - -OHArray::const_iterator -OHArray::begin() const -{ - return this->elements.begin(); -} - -OHArray::const_iterator -OHArray::end() const -{ - return this->elements.end(); -} diff --git a/libqpdf/QPDF_Array.cc b/libqpdf/QPDF_Array.cc index ed43245f..7a3a29ca 100644 --- a/libqpdf/QPDF_Array.cc +++ b/libqpdf/QPDF_Array.cc @@ -205,11 +205,7 @@ QPDF_Array::setFromVector(std::vector>&& v) } else { elements = OHArray(); for (auto&& item: v) { - if (item) { - elements.append(item); - } else { - ++elements.n_elements; - } + elements.append(std::move(item)); } } } diff --git a/libqpdf/qpdf/OHArray.hh b/libqpdf/qpdf/OHArray.hh index 66223c4f..e6dc9524 100644 --- a/libqpdf/qpdf/OHArray.hh +++ b/libqpdf/qpdf/OHArray.hh @@ -2,7 +2,9 @@ #define QPDF_OHARRAY_HH #include -#include +#include + +#include class QPDF_Array; @@ -14,22 +16,15 @@ class OHArray void append(QPDFObjectHandle oh); void append(std::shared_ptr&& obj); QPDFObjectHandle at(size_t idx) const; - void remove_last(); void setAt(size_t idx, QPDFObjectHandle oh); void erase(size_t idx); void insert(size_t idx, QPDFObjectHandle oh); OHArray copy(); void disconnect(); - typedef std::unordered_map::const_iterator - const_iterator; - const_iterator begin() const; - const_iterator end() const; - private: friend class QPDF_Array; - std::unordered_map elements; - size_t n_elements; + std::vector> elements; }; #endif // QPDF_OHARRAY_HH -- cgit v1.2.3-54-g00ecf