Reimplement name and number tree object helpers

Create a computationally and memory efficient implementation of name
and number trees that does binary searches as intended by the data
structure rather than loading into a map, which can use a great deal
of memory and can be very slow.

1 files changed, 49 insertions, 55 deletions

diff --git a/libqpdf/QPDFNumberTreeObjectHelper.cc b/libqpdf/QPDFNumberTreeObjectHelper.cc
index 15930fcd..fa9a0c71 100644
--- a/libqpdf/QPDFNumberTreeObjectHelper.cc
+++ b/libqpdf/QPDFNumberTreeObjectHelper.cc
@@ -1,91 +1,84 @@
 #include <qpdf/QPDFNumberTreeObjectHelper.hh>
+#include <qpdf/NNTree.hh>
 
-QPDFNumberTreeObjectHelper::Members::~Members()
-{
-}
-
-QPDFNumberTreeObjectHelper::Members::Members()
+class NumberTreeDetails: public NNTreeDetails
 {
-}
-
-QPDFNumberTreeObjectHelper::QPDFNumberTreeObjectHelper(QPDFObjectHandle oh) :
-    QPDFObjectHelper(oh),
-    m(new Members())
-{
-    updateMap(oh);
-}
-
-void
-QPDFNumberTreeObjectHelper::updateMap(QPDFObjectHandle oh)
-{
-    if (this->m->seen.count(oh.getObjGen()))
+  public:
+    virtual std::string const& itemsKey() const override
     {
-        return;
+        static std::string k("/Nums");
+        return k;
     }
-    this->m->seen.insert(oh.getObjGen());
-    QPDFObjectHandle nums = oh.getKey("/Nums");
-    if (nums.isArray())
+    virtual bool keyValid(QPDFObjectHandle oh) const override
     {
-        int nitems = nums.getArrayNItems();
-        int i = 0;
-        while (i < nitems - 1)
-        {
-            QPDFObjectHandle num = nums.getArrayItem(i);
-            if (num.isInteger())
-            {
-                ++i;
-                QPDFObjectHandle obj = nums.getArrayItem(i);
-                this->m->entries[num.getIntValue()] = obj;
-            }
-            ++i;
-        }
+        return oh.isInteger();
     }
-    QPDFObjectHandle kids = oh.getKey("/Kids");
-    if (kids.isArray())
+    virtual int compareKeys(
+        QPDFObjectHandle a, QPDFObjectHandle b) const override
     {
-        int nitems = kids.getArrayNItems();
-        for (int i = 0; i < nitems; ++i)
+        if (! (keyValid(a) && keyValid(b)))
         {
-            updateMap(kids.getArrayItem(i));
+            // We don't call this without calling keyValid first
+            throw std::logic_error("comparing invalid keys");
         }
+        auto as = a.getIntValue();
+        auto bs = b.getIntValue();
+        return ((as < bs) ? -1 : (as > bs) ? 1 : 0);
     }
+};
+
+static NumberTreeDetails number_tree_details;
+
+QPDFNumberTreeObjectHelper::Members::~Members()
+{
+}
+
+QPDFNumberTreeObjectHelper::Members::Members(QPDFObjectHandle& oh) :
+    impl(std::make_shared<NNTreeImpl>(number_tree_details, nullptr, oh, false))
+{
 }
 
+QPDFNumberTreeObjectHelper::QPDFNumberTreeObjectHelper(QPDFObjectHandle oh) :
+    QPDFObjectHelper(oh),
+    m(new Members(oh))
+{
+}
 
 QPDFNumberTreeObjectHelper::numtree_number
 QPDFNumberTreeObjectHelper::getMin()
 {
-    if (this->m->entries.empty())
+    auto i = this->m->impl->begin();
+    if (i == this->m->impl->end())
     {
         return 0;
     }
-    // Our map is sorted in reverse.
-    return this->m->entries.rbegin()->first;
+    return (*i).first.getIntValue();
 }
 
 QPDFNumberTreeObjectHelper::numtree_number
 QPDFNumberTreeObjectHelper::getMax()
 {
-    if (this->m->entries.empty())
+    auto i = this->m->impl->last();
+    if (i == this->m->impl->end())
     {
         return 0;
     }
-    // Our map is sorted in reverse.
-    return this->m->entries.begin()->first;
+    return (*i).first.getIntValue();
 }
 
 bool
 QPDFNumberTreeObjectHelper::hasIndex(numtree_number idx)
 {
-    return this->m->entries.count(idx) != 0;
+    auto i = this->m->impl->find(QPDFObjectHandle::newInteger(idx));
+    return (i != this->m->impl->end());
 }
 
 bool
 QPDFNumberTreeObjectHelper::findObject(
     numtree_number idx, QPDFObjectHandle& oh)
 {
-    Members::idx_map::iterator i = this->m->entries.find(idx);
-    if (i == this->m->entries.end())
+    auto i = this->m->impl->find(QPDFObjectHandle::newInteger(idx));
+    if (i == this->m->impl->end())
     {
         return false;
     }
@@ -98,13 +91,13 @@ QPDFNumberTreeObjectHelper::findObjectAtOrBelow(
     numtree_number idx, QPDFObjectHandle& oh,
     numtree_number& offset)
 {
-    Members::idx_map::iterator i = this->m->entries.lower_bound(idx);
-    if (i == this->m->entries.end())
+    auto i = this->m->impl->find(QPDFObjectHandle::newInteger(idx), true);
+    if (i == this->m->impl->end())
     {
         return false;
     }
     oh = (*i).second;
-    offset = idx - (*i).first;
+    offset = idx - (*i).first.getIntValue();
     return true;
 }
 
@@ -112,10 +105,11 @@ std::map<QPDFNumberTreeObjectHelper::numtree_number, QPDFObjectHandle>
 QPDFNumberTreeObjectHelper::getAsMap() const
 {
     std::map<numtree_number, QPDFObjectHandle> result;
-    for (Members::idx_map::const_iterator iter = this->m->entries.begin();
-         iter != this->m->entries.end(); ++iter)
+    for (auto i: *(this->m->impl))
     {
-        result[(*iter).first] = (*iter).second;
+        result.insert(
+            std::make_pair(i.first.getIntValue(),
+                           i.second));
     }
     return result;
 }