SparseOHArray

4 files changed, 188 insertions, 0 deletions

diff --git a/libqpdf/QPDFObjectHandle.cc b/libqpdf/QPDFObjectHandle.cc
index 6f9671d5..853fdb89 100644
--- a/libqpdf/QPDFObjectHandle.cc
+++ b/libqpdf/QPDFObjectHandle.cc
@@ -248,6 +248,10 @@ class QPDFObjectTypeAccessor
     {
 	return (o && dynamic_cast<T*>(o));
     }
+    static bool check(QPDFObject const* o)
+    {
+	return (o && dynamic_cast<T const*>(o));
+    }
 };
 
 bool
@@ -258,6 +262,12 @@ QPDFObjectHandle::isBool()
 }
 
 bool
+QPDFObjectHandle::isResolvedNull() const
+{
+    return QPDFObjectTypeAccessor<QPDF_Null>::check(m->obj.getPointer());
+}
+
+bool
 QPDFObjectHandle::isNull()
 {
     dereference();
diff --git a/libqpdf/SparseOHArray.cc b/libqpdf/SparseOHArray.cc
new file mode 100644
index 00000000..2c525ca8
--- /dev/null
+++ b/libqpdf/SparseOHArray.cc
@@ -0,0 +1,143 @@
+#include <qpdf/SparseOHArray.hh>
+#include <stdexcept>
+
+SparseOHArray::SparseOHArray() :
+    n_elements(0)
+{
+}
+
+size_t
+SparseOHArray::size() const
+{
+    return this->n_elements;
+}
+
+void
+SparseOHArray::append(QPDFObjectHandle oh)
+{
+    if (! oh.isResolvedNull())
+    {
+        this->elements[this->n_elements] = oh;
+    }
+    ++this->n_elements;
+}
+
+QPDFObjectHandle
+SparseOHArray::at(size_t idx) const
+{
+    if (idx >= this->n_elements)
+    {
+	throw std::logic_error(
+	    "INTERNAL ERROR: bounds error accessing SparseOHArray element");
+    }
+    std::map<size_t, QPDFObjectHandle>::const_iterator iter =
+        this->elements.find(idx);
+    if (iter == this->elements.end())
+    {
+        return QPDFObjectHandle::newNull();
+    }
+    else
+    {
+        return (*iter).second;
+    }
+}
+
+void
+SparseOHArray::remove_last()
+{
+    if (this->n_elements == 0)
+    {
+	throw std::logic_error(
+	    "INTERNAL ERROR: attempt to remove"
+            " last item from empty SparseOHArray");
+    }
+    --this->n_elements;
+    this->elements.erase(this->n_elements);
+}
+
+void
+SparseOHArray::releaseResolved()
+{
+    for (std::map<size_t, QPDFObjectHandle>::iterator iter =
+             this->elements.begin();
+	 iter != this->elements.end(); ++iter)
+    {
+	QPDFObjectHandle::ReleaseResolver::releaseResolved((*iter).second);
+    }
+}
+
+void
+SparseOHArray::setAt(size_t idx, QPDFObjectHandle oh)
+{
+    if (idx >= this->n_elements)
+    {
+	throw std::logic_error("bounds error setting item in SparseOHArray");
+    }
+    if (oh.isResolvedNull())
+    {
+        this->elements.erase(idx);
+    }
+    else
+    {
+        this->elements[idx] = oh;
+    }
+}
+
+void
+SparseOHArray::erase(size_t idx)
+{
+    if (idx >= this->n_elements)
+    {
+	throw std::logic_error("bounds error erasing item from SparseOHArray");
+    }
+    std::map<size_t, QPDFObjectHandle> dest;
+    for (std::map<size_t, QPDFObjectHandle>::iterator iter =
+             this->elements.begin();
+	 iter != this->elements.end(); ++iter)
+    {
+        if ((*iter).first < idx)
+        {
+            dest.insert(*iter);
+        }
+        else if ((*iter).first > idx)
+        {
+            dest[(*iter).first - 1] = (*iter).second;
+        }
+    }
+    this->elements = dest;
+    --this->n_elements;
+}
+
+void
+SparseOHArray::insert(size_t idx, QPDFObjectHandle oh)
+{
+    if (idx > this->n_elements)
+    {
+        throw std::logic_error("bounds error inserting item to SparseOHArray");
+    }
+    else if (idx == this->n_elements)
+    {
+        // Allow inserting to the last position
+        append(oh);
+    }
+    else
+    {
+        std::map<size_t, QPDFObjectHandle> dest;
+        for (std::map<size_t, QPDFObjectHandle>::iterator iter =
+                 this->elements.begin();
+             iter != this->elements.end(); ++iter)
+        {
+            if ((*iter).first < idx)
+            {
+                dest.insert(*iter);
+            }
+            else
+            {
+                dest[(*iter).first + 1] = (*iter).second;
+            }
+        }
+        this->elements = dest;
+        this->elements[idx] = oh;
+        ++this->n_elements;
+    }
+}
diff --git a/libqpdf/build.mk b/libqpdf/build.mk
index 4ef0688d..1da6c1a1 100644
--- a/libqpdf/build.mk
+++ b/libqpdf/build.mk
@@ -76,6 +76,7 @@ SRCS_libqpdf = \
 	libqpdf/QUtil.cc \
 	libqpdf/RC4.cc \
 	libqpdf/SecureRandomDataProvider.cc \
+	libqpdf/SparseOHArray.cc \
 	libqpdf/qpdf-c.cc \
 	libqpdf/rijndael.cc \
 	libqpdf/sha2.c \
diff --git a/libqpdf/qpdf/SparseOHArray.hh b/libqpdf/qpdf/SparseOHArray.hh
new file mode 100644
index 00000000..2e3f334c
--- /dev/null
+++ b/libqpdf/qpdf/SparseOHArray.hh
@@ -0,0 +1,34 @@
+#ifndef QPDF_SPARSEOHARRAY_HH
+#define QPDF_SPARSEOHARRAY_HH
+
+#include <qpdf/QPDFObjectHandle.hh>
+#include <map>
+
+class SparseOHArray
+{
+  public:
+    QPDF_DLL
+    SparseOHArray();
+    QPDF_DLL
+    size_t size() const;
+    QPDF_DLL
+    void append(QPDFObjectHandle oh);
+    QPDF_DLL
+    QPDFObjectHandle at(size_t idx) const;
+    QPDF_DLL
+    void remove_last();
+    QPDF_DLL
+    void releaseResolved();
+    QPDF_DLL
+    void setAt(size_t idx, QPDFObjectHandle oh);
+    QPDF_DLL
+    void erase(size_t idx);
+    QPDF_DLL
+    void insert(size_t idx, QPDFObjectHandle oh);
+
+  private:
+    std::map<size_t, QPDFObjectHandle> elements;
+    size_t n_elements;
+};
+
+#endif // QPDF_SPARSEOHARRAY_HH