From 5e9de5cd509310bb5f954bb6c767cfec2b2bbeb7 Mon Sep 17 00:00:00 2001 From: m-holger Date: Tue, 9 Jan 2024 15:19:48 +0000 Subject: Tune handling of sparse arrays in QPDF_Array Sparse arrays are rare. Dynamically create the variables needed to manage them only when needed. --- libqpdf/QPDF_Array.cc | 83 ++++++++++++++++++++++------------------------ libqpdf/qpdf/QPDF_Array.hh | 13 +++++--- 2 files changed, 49 insertions(+), 47 deletions(-) (limited to 'libqpdf') diff --git a/libqpdf/QPDF_Array.cc b/libqpdf/QPDF_Array.cc index b5b182af..c8cfe110 100644 --- a/libqpdf/QPDF_Array.cc +++ b/libqpdf/QPDF_Array.cc @@ -30,10 +30,7 @@ QPDF_Array::QPDF_Array() : QPDF_Array::QPDF_Array(QPDF_Array const& other) : QPDFValue(::ot_array, "array"), - sparse(other.sparse), - sp_size(other.sp_size), - sp_elements(other.sp_elements), - elements(other.elements) + sp(other.sp ? std::make_unique(*other.sp) : nullptr) { } @@ -44,15 +41,15 @@ QPDF_Array::QPDF_Array(std::vector const& v) : } QPDF_Array::QPDF_Array(std::vector>&& v, bool sparse) : - QPDFValue(::ot_array, "array"), - sparse(sparse) + QPDFValue(::ot_array, "array") { if (sparse) { + sp = std::make_unique(); for (auto&& item: v) { if (item->getTypeCode() != ::ot_null || item->getObjGen().isIndirect()) { - sp_elements[sp_size] = std::move(item); + sp->elements[sp->size] = std::move(item); } - ++sp_size; + ++sp->size; } } else { elements = std::move(v); @@ -77,12 +74,12 @@ QPDF_Array::copy(bool shallow) if (shallow) { return do_create(new QPDF_Array(*this)); } else { - if (sparse) { + if (sp) { auto* result = new QPDF_Array(); - result->sp_size = sp_size; - for (auto const& element: sp_elements) { + result->sp->size = sp->size; + for (auto const& element: sp->elements) { auto const& obj = element.second; - result->sp_elements[element.first] = + result->sp->elements[element.first] = obj->getObjGen().isIndirect() ? obj : obj->copy(); } return do_create(result); @@ -102,8 +99,8 @@ QPDF_Array::copy(bool shallow) void QPDF_Array::disconnect() { - if (sparse) { - for (auto& item: sp_elements) { + if (sp) { + for (auto& item: sp->elements) { auto& obj = item.second; if (!obj->getObjGen().isIndirect()) { obj->disconnect(); @@ -122,9 +119,9 @@ std::string QPDF_Array::unparse() { std::string result = "[ "; - if (sparse) { + if (sp) { int next = 0; - for (auto& item: sp_elements) { + for (auto& item: sp->elements) { int key = item.first; for (int j = next; j < key; ++j) { result += "null "; @@ -134,7 +131,7 @@ QPDF_Array::unparse() result += og.isIndirect() ? og.unparse(' ') + " R " : item.second->unparse() + " "; next = ++key; } - for (int j = next; j < sp_size; ++j) { + for (int j = next; j < sp->size; ++j) { result += "null "; } } else { @@ -153,9 +150,9 @@ QPDF_Array::getJSON(int json_version) { static const JSON j_null = JSON::makeNull(); JSON j_array = JSON::makeArray(); - if (sparse) { + if (sp) { int next = 0; - for (auto& item: sp_elements) { + for (auto& item: sp->elements) { int key = item.first; for (int j = next; j < key; ++j) { j_array.addArrayElement(j_null); @@ -166,7 +163,7 @@ QPDF_Array::getJSON(int json_version) : item.second->getJSON(json_version)); next = ++key; } - for (int j = next; j < sp_size; ++j) { + for (int j = next; j < sp->size; ++j) { j_array.addArrayElement(j_null); } } else { @@ -185,9 +182,9 @@ QPDF_Array::at(int n) const noexcept { if (n < 0 || n >= size()) { return {}; - } else if (sparse) { - auto const& iter = sp_elements.find(n); - return iter == sp_elements.end() ? null_oh : (*iter).second; + } else if (sp) { + auto const& iter = sp->elements.find(n); + return iter == sp->elements.end() ? null_oh : (*iter).second; } else { return elements[size_t(n)]; } @@ -196,10 +193,10 @@ QPDF_Array::at(int n) const noexcept std::vector QPDF_Array::getAsVector() const { - if (sparse) { + if (sp) { std::vector v; v.reserve(size_t(size())); - for (auto const& item: sp_elements) { + for (auto const& item: sp->elements) { v.resize(size_t(item.first), null_oh); v.emplace_back(item.second); } @@ -217,8 +214,8 @@ QPDF_Array::setAt(int at, QPDFObjectHandle const& oh) return false; } checkOwnership(oh); - if (sparse) { - sp_elements[at] = oh.getObj(); + if (sp) { + sp->elements[at] = oh.getObj(); } else { elements[size_t(at)] = oh.getObj(); } @@ -247,20 +244,20 @@ QPDF_Array::insert(int at, QPDFObjectHandle const& item) push_back(item); } else { checkOwnership(item); - if (sparse) { - auto iter = sp_elements.crbegin(); - while (iter != sp_elements.crend()) { + if (sp) { + auto iter = sp->elements.crbegin(); + while (iter != sp->elements.crend()) { auto key = (iter++)->first; if (key >= at) { - auto nh = sp_elements.extract(key); + auto nh = sp->elements.extract(key); ++nh.key(); - sp_elements.insert(std::move(nh)); + sp->elements.insert(std::move(nh)); } else { break; } } - sp_elements[at] = item.getObj(); - ++sp_size; + sp->elements[at] = item.getObj(); + ++sp->size; } else { elements.insert(elements.cbegin() + at, item.getObj()); } @@ -272,8 +269,8 @@ void QPDF_Array::push_back(QPDFObjectHandle const& item) { checkOwnership(item); - if (sparse) { - sp_elements[sp_size++] = item.getObj(); + if (sp) { + sp->elements[(sp->size)++] = item.getObj(); } else { elements.push_back(item.getObj()); } @@ -285,21 +282,21 @@ QPDF_Array::erase(int at) if (at < 0 || at >= size()) { return false; } - if (sparse) { - auto end = sp_elements.end(); - if (auto iter = sp_elements.lower_bound(at); iter != end) { + if (sp) { + auto end = sp->elements.end(); + if (auto iter = sp->elements.lower_bound(at); iter != end) { if (iter->first == at) { iter++; - sp_elements.erase(at); + sp->elements.erase(at); } while (iter != end) { - auto nh = sp_elements.extract(iter++); + auto nh = sp->elements.extract(iter++); --nh.key(); - sp_elements.insert(std::move(nh)); + sp->elements.insert(std::move(nh)); } } - --sp_size; + --(sp->size); } else { elements.erase(elements.cbegin() + at); } diff --git a/libqpdf/qpdf/QPDF_Array.hh b/libqpdf/qpdf/QPDF_Array.hh index 10ac9f8c..281e1d48 100644 --- a/libqpdf/qpdf/QPDF_Array.hh +++ b/libqpdf/qpdf/QPDF_Array.hh @@ -8,6 +8,13 @@ class QPDF_Array: public QPDFValue { + private: + struct Sparse + { + int size{0}; + std::map> elements; + }; + public: ~QPDF_Array() override = default; static std::shared_ptr create(std::vector const& items); @@ -21,7 +28,7 @@ class QPDF_Array: public QPDFValue int size() const noexcept { - return sparse ? sp_size : int(elements.size()); + return sp ? sp->size : int(elements.size()); } QPDFObjectHandle at(int n) const noexcept; bool setAt(int n, QPDFObjectHandle const& oh); @@ -39,9 +46,7 @@ class QPDF_Array: public QPDFValue void checkOwnership(QPDFObjectHandle const& item) const; - bool sparse{false}; - int sp_size{0}; - std::map> sp_elements; + std::unique_ptr sp; std::vector> elements; }; -- cgit v1.2.3-54-g00ecf