1 // Copyright (c) 2005-2021 Jay Berkenbilt
2 //
3 // This file is part of qpdf.
4 //
5 // Licensed under the Apache License, Version 2.0 (the "License");
6 // you may not use this file except in compliance with the License.
7 // You may obtain a copy of the License at
8 //
9 //   http://www.apache.org/licenses/LICENSE-2.0
10 //
11 // Unless required by applicable law or agreed to in writing, software
12 // distributed under the License is distributed on an "AS IS" BASIS,
13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 // See the License for the specific language governing permissions and
15 // limitations under the License.
16 //
17 // Versions of qpdf prior to version 7 were released under the terms
18 // of version 2.0 of the Artistic License. At your option, you may
19 // continue to consider qpdf to be licensed under those terms. Please
20 // see the manual for additional information.
21 
22 #ifndef QPDFNUMBERTREEOBJECTHELPER_HH
23 #define QPDFNUMBERTREEOBJECTHELPER_HH
24 
25 #include <qpdf/QPDFObjectHelper.hh>
26 #include <qpdf/QPDFObjGen.hh>
27 #include <map>
28 #include <memory>
29 
30 #include <qpdf/DLL.h>
31 
32 // This is an object helper for number trees. See section 7.9.7 in the
33 // PDF spec (ISO 32000) for a description of number trees.
34 
35 // See examples/pdf-name-number-tree.cc for a demonstration of using
36 // QPDFNumberTreeObjectHelper.
37 
38 class NNTreeImpl;
39 class NNTreeIterator;
40 class NNTreeDetails;
41 
42 class QPDFNumberTreeObjectHelper: public QPDFObjectHelper
43 {
44   public:
45     // The qpdf object is required so that this class can issue
46     // warnings, attempt repairs, and add indirect objects.
47     QPDF_DLL
48     QPDFNumberTreeObjectHelper(QPDFObjectHandle, QPDF&,
49                                bool auto_repair = true);
50 
51     // ABI: Legacy Constructor will be removed in QPDF 11. A
52     // QPDFNumberTreeObjectHelper constructed in this way can't be
53     // modified or repaired and will silently ignore problems in the
54     // structure.
55     [[deprecated("use constructor that takes QPDF&")]]
56     QPDF_DLL
57     QPDFNumberTreeObjectHelper(QPDFObjectHandle);
58 
59     // ABI: = default
60     QPDF_DLL
~QPDFNumberTreeObjectHelper()61     virtual ~QPDFNumberTreeObjectHelper()
62     {
63     }
64 
65     // Create an empty number tree
66     QPDF_DLL
67     static QPDFNumberTreeObjectHelper newEmpty(QPDF&, bool auto_repair = true);
68 
69     typedef long long int numtree_number;
70 
71     // Return overall minimum and maximum indices
72     QPDF_DLL
73     numtree_number getMin();
74     QPDF_DLL
75     numtree_number getMax();
76 
77     // Return whether the number tree has an explicit entry for this
78     // number.
79     QPDF_DLL
80     bool hasIndex(numtree_number idx);
81 
82     // Find an object with a specific index. If found, returns true
83     // and initializes oh. See also find().
84     QPDF_DLL
85     bool findObject(numtree_number idx, QPDFObjectHandle& oh);
86     // Find the object at the index or, if not found, the object whose
87     // index is the highest index less than the requested index. If
88     // the requested index is less than the minimum, return false.
89     // Otherwise, return true, initialize oh to the object, and set
90     // offset to the difference between the requested index and the
91     // actual index. For example, if a number tree has values for 3
92     // and 6 and idx is 5, this method would return true, initialize
93     // oh to the value with index 3, and set offset to 2 (5 - 3). See
94     // also find().
95     QPDF_DLL
96     bool findObjectAtOrBelow(numtree_number idx, QPDFObjectHandle& oh,
97                              numtree_number& offset);
98 
99     class iterator: public std::iterator<
100         std::bidirectional_iterator_tag,
101         std::pair<numtree_number, QPDFObjectHandle>>
102     {
103         friend class QPDFNumberTreeObjectHelper;
104       public:
105         virtual ~iterator() = default;
106         QPDF_DLL
107         bool valid() const;
108         QPDF_DLL
109         iterator& operator++();
110         QPDF_DLL
operator ++(int)111         iterator operator++(int)
112         {
113             iterator t = *this;
114             ++(*this);
115             return t;
116         }
117         QPDF_DLL
118         iterator& operator--();
119         QPDF_DLL
operator --(int)120         iterator operator--(int)
121         {
122             iterator t = *this;
123             --(*this);
124             return t;
125         }
126         QPDF_DLL
127         reference operator*();
128         QPDF_DLL
129         pointer operator->();
130         QPDF_DLL
131         bool operator==(iterator const& other) const;
132         QPDF_DLL
operator !=(iterator const & other) const133         bool operator!=(iterator const& other) const
134         {
135             return ! operator==(other);
136         }
137 
138         // DANGER: this method can create inconsistent trees if not
139         // used properly! Insert a new item immediately after the
140         // current iterator and increment so that it points to the new
141         // item. If the current iterator is end(), insert at the
142         // beginning. This method does not check for proper ordering,
143         // so if you use it, you must ensure that the item you are
144         // inserting belongs where you are putting it. The reason for
145         // this method is that it is more efficient than insert() and
146         // can be used safely when you are creating a new tree and
147         // inserting items in sorted order.
148         QPDF_DLL
149         void insertAfter(numtree_number key, QPDFObjectHandle value);
150 
151         // Remove the current item and advance the iterator to the
152         // next item.
153         QPDF_DLL
154         void remove();
155 
156       private:
157         void updateIValue();
158 
159         iterator(std::shared_ptr<NNTreeIterator> const&);
160         std::shared_ptr<NNTreeIterator> impl;
161         value_type ivalue;
162     };
163 
164     // The iterator looks like map iterator, so i.first is a string
165     // and i.second is a QPDFObjectHandle. Incrementing end() brings
166     // you to the first item. Decrementing end() brings you to the
167     // last item.
168     QPDF_DLL
169     iterator begin() const;
170     QPDF_DLL
171     iterator end() const;
172     // Return a bidirectional iterator that points to the last item.
173     QPDF_DLL
174     iterator last() const;
175 
176     // Find the entry with the given key. If return_prev_if_not_found
177     // is true and the item is not found, return the next lower item.
178     QPDF_DLL
179     iterator find(numtree_number key, bool return_prev_if_not_found = false);
180 
181     // Insert a new item. If the key already exists, it is replaced.
182     QPDF_DLL
183     iterator insert(numtree_number key, QPDFObjectHandle value);
184 
185     // Remove an item. Return true if the item was found and removed;
186     // otherwise return false. If value is not null, initialize it to
187     // the value that was removed.
188     QPDF_DLL
189     bool remove(numtree_number key, QPDFObjectHandle* value = nullptr);
190 
191     // Return the contents of the number tree as a map. Note that
192     // number trees may be very large, so this may use a lot of RAM.
193     // It is more efficient to use QPDFNumberTreeObjectHelper's
194     // iterator.
195     typedef std::map<numtree_number, QPDFObjectHandle> idx_map;
196     QPDF_DLL
197     idx_map getAsMap() const;
198 
199     // Split a node if the number of items exceeds this value. There's
200     // no real reason to ever set this except for testing.
201     QPDF_DLL
202     void setSplitThreshold(int);
203 
204   private:
205     class Members
206     {
207         friend class QPDFNumberTreeObjectHelper;
208         typedef QPDFNumberTreeObjectHelper::numtree_number numtree_number;
209 
210       public:
211         QPDF_DLL
212         ~Members();
213 
214       private:
215         Members(QPDFObjectHandle& oh, QPDF*, bool auto_repair);
216         Members(Members const&) = delete;
217 
218         std::shared_ptr<NNTreeImpl> impl;
219     };
220 
221     PointerHolder<Members> m;
222 };
223 
224 #endif // QPDFNUMBERTREEOBJECTHELPER_HH
225