SparseOHArray

8 files changed, 297 insertions, 1 deletions

diff --git a/include/qpdf/QPDFObjectHandle.hh b/include/qpdf/QPDFObjectHandle.hh
index 28f6f491..ad542c09 100644
--- a/include/qpdf/QPDFObjectHandle.hh
+++ b/include/qpdf/QPDFObjectHandle.hh
@@ -275,6 +275,14 @@ class QPDFObjectHandle
     QPDF_DLL
     bool isReserved();
 
+    // True for objects that are direct nulls or have previously been
+    // resolved to be nulls. Does not attempt to resolve objects. This
+    // is intended for internal use, but it can be used as an
+    // efficient way to check for nulls if you don't mind unresolved
+    // indirect nulls being false negatives.
+    QPDF_DLL
+    bool isResolvedNull() const;
+
     // This returns true in addition to the query for the specific
     // type for indirect objects.
     QPDF_DLL
@@ -926,6 +934,7 @@ class QPDFObjectHandle
 	friend class QPDF_Dictionary;
 	friend class QPDF_Array;
         friend class QPDF_Stream;
+        friend class SparseOHArray;
       private:
 	static void releaseResolved(QPDFObjectHandle& o)
 	{
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
diff --git a/libtests/build.mk b/libtests/build.mk
index 4313b630..c8cc4d83 100644
--- a/libtests/build.mk
+++ b/libtests/build.mk
@@ -22,7 +22,8 @@ BINS_libtests = \
 	random \
 	rc4 \
 	runlength \
-	sha2
+	sha2 \
+	sparse_array
 
 TARGETS_libtests = $(foreach B,$(BINS_libtests),libtests/$(OUTPUT_DIR)/$(call binname,$(B)))
 
diff --git a/libtests/qtest/sparse_array.test b/libtests/qtest/sparse_array.test
new file mode 100644
index 00000000..c3535d85
--- /dev/null
+++ b/libtests/qtest/sparse_array.test
@@ -0,0 +1,16 @@
+#!/usr/bin/env perl
+require 5.008;
+use warnings;
+use strict;
+
+require TestDriver;
+
+my $td = new TestDriver('sparse array');
+
+$td->runtest("sparse_array",
+	     {$td->COMMAND => "sparse_array"},
+	     {$td->STRING => "sparse array tests done\n",
+                  $td->EXIT_STATUS => 0},
+             $td->NORMALIZE_NEWLINES);
+
+$td->report(1);
diff --git a/libtests/sparse_array.cc b/libtests/sparse_array.cc
new file mode 100644
index 00000000..9c3e00b4
--- /dev/null
+++ b/libtests/sparse_array.cc
@@ -0,0 +1,82 @@
+#include <qpdf/SparseOHArray.hh>
+#include <assert.h>
+#include <iostream>
+
+int main()
+{
+    SparseOHArray a;
+    assert(a.size() == 0);
+
+    a.append(QPDFObjectHandle::parse("1"));
+    a.append(QPDFObjectHandle::parse("(potato)"));
+    a.append(QPDFObjectHandle::parse("null"));
+    a.append(QPDFObjectHandle::parse("null"));
+    a.append(QPDFObjectHandle::parse("/Quack"));
+    assert(a.size() == 5);
+    assert(a.at(0).isInteger() && (a.at(0).getIntValue() == 1));
+    assert(a.at(1).isString() && (a.at(1).getStringValue() == "potato"));
+    assert(a.at(2).isNull());
+    assert(a.at(3).isNull());
+    assert(a.at(4).isName() && (a.at(4).getName() == "/Quack"));
+
+    a.insert(4, QPDFObjectHandle::parse("/BeforeQuack"));
+    assert(a.size() == 6);
+    assert(a.at(0).isInteger() && (a.at(0).getIntValue() == 1));
+    assert(a.at(4).isName() && (a.at(4).getName() == "/BeforeQuack"));
+    assert(a.at(5).isName() && (a.at(5).getName() == "/Quack"));
+
+    a.insert(2, QPDFObjectHandle::parse("/Third"));
+    assert(a.size() == 7);
+    assert(a.at(1).isString() && (a.at(1).getStringValue() == "potato"));
+    assert(a.at(2).isName() && (a.at(2).getName() == "/Third"));
+    assert(a.at(3).isNull());
+    assert(a.at(6).isName() && (a.at(6).getName() == "/Quack"));
+
+    a.insert(0, QPDFObjectHandle::parse("/First"));
+    assert(a.size() == 8);
+    assert(a.at(0).isName() && (a.at(0).getName() == "/First"));
+    assert(a.at(1).isInteger() && (a.at(1).getIntValue() == 1));
+    assert(a.at(7).isName() && (a.at(7).getName() == "/Quack"));
+
+    a.erase(6);
+    assert(a.size() == 7);
+    assert(a.at(0).isName() && (a.at(0).getName() == "/First"));
+    assert(a.at(1).isInteger() && (a.at(1).getIntValue() == 1));
+    assert(a.at(5).isNull());
+    assert(a.at(6).isName() && (a.at(6).getName() == "/Quack"));
+
+    a.erase(6);
+    assert(a.size() == 6);
+    assert(a.at(0).isName() && (a.at(0).getName() == "/First"));
+    assert(a.at(1).isInteger() && (a.at(1).getIntValue() == 1));
+    assert(a.at(3).isName() && (a.at(3).getName() == "/Third"));
+    assert(a.at(4).isNull());
+    assert(a.at(5).isNull());
+
+    a.setAt(4, QPDFObjectHandle::parse("12"));
+    assert(a.at(4).isInteger() && (a.at(4).getIntValue() == 12));
+    a.setAt(4, QPDFObjectHandle::newNull());
+    assert(a.at(4).isNull());
+
+    a.remove_last();
+    assert(a.size() == 5);
+    assert(a.at(0).isName() && (a.at(0).getName() == "/First"));
+    assert(a.at(1).isInteger() && (a.at(1).getIntValue() == 1));
+    assert(a.at(3).isName() && (a.at(3).getName() == "/Third"));
+    assert(a.at(4).isNull());
+
+    a.remove_last();
+    assert(a.size() == 4);
+    assert(a.at(0).isName() && (a.at(0).getName() == "/First"));
+    assert(a.at(1).isInteger() && (a.at(1).getIntValue() == 1));
+    assert(a.at(3).isName() && (a.at(3).getName() == "/Third"));
+
+    a.remove_last();
+    assert(a.size() == 3);
+    assert(a.at(0).isName() && (a.at(0).getName() == "/First"));
+    assert(a.at(1).isInteger() && (a.at(1).getIntValue() == 1));
+    assert(a.at(2).isString() && (a.at(2).getStringValue() == "potato"));
+
+    std::cout << "sparse array tests done" << std::endl;
+    return 0;
+}