source: trunk/src/xmlpatterns/acceltree/qacceltree_p.h@ 117

Last change on this file since 117 was 2, checked in by Dmitry A. Kuminov, 16 years ago

Initially imported qt-all-opensource-src-4.5.1 from Trolltech.
File size: 14.7 KB
Line 
1/****************************************************************************
2**
3** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
4** Contact: Qt Software Information ([email protected])
5**
6** This file is part of the QtXmlPatterns module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial Usage
10** Licensees holding valid Qt Commercial licenses may use this file in
11** accordance with the Qt Commercial License Agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and Nokia.
14**
15** GNU Lesser General Public License Usage
16** Alternatively, this file may be used under the terms of the GNU Lesser
17** General Public License version 2.1 as published by the Free Software
18** Foundation and appearing in the file LICENSE.LGPL included in the
19** packaging of this file. Please review the following information to
20** ensure the GNU Lesser General Public License version 2.1 requirements
21** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
22**
23** In addition, as a special exception, Nokia gives you certain
24** additional rights. These rights are described in the Nokia Qt LGPL
25** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this
26** package.
27**
28** GNU General Public License Usage
29** Alternatively, this file may be used under the terms of the GNU
30** General Public License version 3.0 as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL included in the
32** packaging of this file. Please review the following information to
33** ensure the GNU General Public License version 3.0 requirements will be
34** met: http://www.gnu.org/copyleft/gpl.html.
35**
36** If you are unsure which license is appropriate for your use, please
37** contact the sales department at [email protected].
38** $QT_END_LICENSE$
39**
40****************************************************************************/
41
42//
43// W A R N I N G
44// -------------
45//
46// This file is not part of the Qt API. It exists purely as an
47// implementation detail. This header file may change from version to
48// version without notice, or even be removed.
49//
50// We mean it.
51
52#ifndef Patternist_AccelTree_H
53#define Patternist_AccelTree_H
54
55#include <QHash>
56#include <QUrl>
57#include <QVector>
58#include <QXmlName>
59
60#include "qitem_p.h"
61#include "qnamepool_p.h"
62
63QT_BEGIN_HEADER
64
65QT_BEGIN_NAMESPACE
66
67namespace QPatternist
68{
69 template<bool> class AccelTreeBuilder;
70
71 /**
72 * @short Stores an XML document using the XPath Accelerator scheme, also
73 * known as pre/post numbering.
74 *
75 * Working on this code will be destructive without a proper understanding of
76 * the Accelerator scheme, so do check out the links. We don't implement any form
77 * of staircase join, although that is only due to time constraints.
78 *
79 * @author Frans Englich <[email protected]>
80 * @see <a href="http://www.pathfinder-xquery.org/?q=research/xpath-accel">XPath
81 * Accelerator</a>
82 * @see <a href="http://www.pathfinder-xquery.org/files/xpath-accel.pdf">Accelerating
83 * XPath Location Steps, Torsten Grust</a>
84 * @see <a href="http://citeseer.ist.psu.edu/cache/papers/cs/29367/http:zSzzSzwww.informatik.uni-konstanz.dezSz~grustzSzfileszSzstaircase-join.pdf/grust03staircase.pdf">Staircase Join:
85 * Teach a Relational DBMS to Watch its (Axis) Steps</a>
86 * @see <a href="http://ftp.cwi.nl/CWIreports/INS/INS-E0510.pdf">Loop-lifted
87 * staircase join: from XPath to XQuery, Torsten Grust</a>
88 * @see <a href="http://englich.wordpress.com/2007/01/09/xmlstat/">xmlstat, Frans Englich</a>
89 * @see <a href"http://www.inf.uni-konstanz.de/dbis/publications/download/accelerating-locsteps.pdf">Accelerating
90 * XPath Evaluation in Any RDBMS, Torsten Grust</a>
91 */
92 class AccelTree : public QAbstractXmlNodeModel
93 {
94 public:
95 using QAbstractXmlNodeModel::createIndex;
96
97 typedef QExplicitlySharedDataPointer<AccelTree> Ptr;
98 typedef qint32 PreNumber;
99 typedef PreNumber PostNumber;
100 typedef qint8 Depth;
101
102 inline AccelTree(const QUrl &docURI,
103 const QUrl &bURI) : m_documentURI(docURI),
104 m_baseURI(bURI)
105 {
106 /* Pre-allocate at least a little bit. */
107 // TODO. Do it according to what an average 4 KB doc contains.
108 basicData.reserve(100);
109 data.reserve(30);
110 }
111
112 /**
113 * @short Houses data for a node, and that all node kinds have.
114 *
115 * BasicNodeData is internal to the Accel tree implementation, and is
116 * only used by those classes.
117 *
118 * @author Frans Englich <[email protected]>
119 * @todo Can't m_kind be coded somewhere else? If m_name is invalid,
120 * its bits can be used to distinguish the node types that doesn't have
121 * names, and for elements, attributes and processing instructions, we need
122 * two bits, somewhere. Attributes and processing instructions can't have a
123 * size, is that of help? There's also certain rules for the names. For instance,
124 * a processing instruction will never have a prefix nor namespace. Neither
125 * will an attribute node have a default, non-empty namespace, right?
126 * @todo Compress text nodes, add general support for it in Patternist.
127 */
128 class BasicNodeData
129 {
130 public:
131 inline BasicNodeData()
132 {
133 }
134
135 inline BasicNodeData(const PreNumber aDepth,
136 const PreNumber aParent,
137 const QXmlNodeModelIndex::NodeKind k,
138 const PreNumber s,
139 const QXmlName n = QXmlName()) : m_parent(aParent)
140 , m_size(s)
141 , m_name(n)
142 , m_depth(aDepth)
143 , m_kind(k)
144 {
145 }
146
147 inline Depth depth() const
148 {
149 return m_depth;
150 }
151
152 inline PreNumber parent() const
153 {
154 return m_parent;
155 }
156
157 /**
158 * @see AccelTree::size()
159 */
160 inline PreNumber size() const
161 {
162 /* Remember that we use the m_size to signal compression if
163 * we're a text node. */
164 if(m_kind == QXmlNodeModelIndex::Text)
165 return 0;
166 else
167 return m_size;
168 }
169
170 inline void setSize(const PreNumber aSize)
171 {
172 m_size = aSize;
173 }
174
175 inline QXmlNodeModelIndex::NodeKind kind() const
176 {
177 return m_kind;
178 }
179
180 inline QXmlName name() const
181 {
182 return m_name;
183 }
184
185 inline bool isCompressed() const
186 {
187 Q_ASSERT_X(m_kind == QXmlNodeModelIndex::Text, Q_FUNC_INFO,
188 "Currently, only text nodes are compressed.");
189 /* Note, we don't call size() here, since it has logic for text
190 * nodes. */
191 return m_size == IsCompressed;
192 }
193
194 private:
195 /**
196 * This is the pre number of the parent.
197 */
198 PreNumber m_parent;
199
200 /**
201 * This is the count of children this node has.
202 *
203 * In the case of a text node, which cannot have children,
204 * it is set to IsCompressed, if the content has been the result
205 * of CompressedWhitespace::compress(). If it's not compressed,
206 * it is zero.
207 */
208 PreNumber m_size;
209
210 /**
211 * For text nodes, and less importantly, comments,
212 * this variable is not used.
213 */
214 QXmlName m_name;
215
216 Depth m_depth;
217
218 /**
219 * Technically it is sufficient with 8 bits. However, at least MSVC
220 * 2005 miscompiles it such that QXmlNodeModelIndex::Text becomes
221 * -64 instead of 64 with hilarious crashes as result.
222 *
223 * Fortunately this extra bit would be padded anyway.
224 */
225 QXmlNodeModelIndex::NodeKind m_kind : 8;
226 };
227
228 virtual QUrl baseUri(const QXmlNodeModelIndex &ni) const;
229 virtual QUrl documentUri(const QXmlNodeModelIndex &ni) const;
230 virtual QXmlNodeModelIndex::NodeKind kind(const QXmlNodeModelIndex &ni) const;
231 virtual QXmlNodeModelIndex::DocumentOrder compareOrder(const QXmlNodeModelIndex &ni1,
232 const QXmlNodeModelIndex &ni2) const;
233
234 /**
235 * @short Returns the root node.
236 *
237 * This function does not use @p n, so a default constructed
238 * QXmlNodeModelIndex may be passed.
239 */
240 virtual QXmlNodeModelIndex root(const QXmlNodeModelIndex &n) const;
241
242 virtual QXmlNodeModelIndex parent(const QXmlNodeModelIndex &ni) const;
243 virtual QXmlNodeModelIndex::Iterator::Ptr iterate(const QXmlNodeModelIndex &ni,
244 QXmlNodeModelIndex::Axis axis) const;
245 virtual QXmlName name(const QXmlNodeModelIndex &ni) const;
246 virtual QVector<QXmlName> namespaceBindings(const QXmlNodeModelIndex &n) const;
247 virtual void sendNamespaces(const QXmlNodeModelIndex &n,
248 QAbstractXmlReceiver *const receiver) const;
249 virtual QString stringValue(const QXmlNodeModelIndex &n) const;
250 virtual QVariant typedValue(const QXmlNodeModelIndex &n) const;
251 virtual Item::Iterator::Ptr sequencedTypedValue(const QXmlNodeModelIndex &n) const;
252 virtual ItemType::Ptr type(const QXmlNodeModelIndex &ni) const;
253 virtual QXmlNodeModelIndex elementById(const QXmlName &id) const;
254 virtual QVector<QXmlNodeModelIndex> nodesByIdref(const QXmlName &idref) const;
255 virtual void copyNodeTo(const QXmlNodeModelIndex &node,
256 QAbstractXmlReceiver *const receiver,
257 const NodeCopySettings &settings) const;
258
259 friend class AccelTreeBuilder<false>;
260 friend class AccelTreeBuilder<true>;
261
262 enum Constants
263 {
264 IsCompressed = 1
265 };
266
267 /**
268 * The key is the pre number of an element, and the value is a vector
269 * containing the namespace declarations being declared on that
270 * element. Therefore, it does not reflect the namespaces being in
271 * scope for that element. For that, a walk along axis ancestor is
272 * necessary.
273 */
274 QHash<PreNumber, QVector<QXmlName> > namespaces;
275
276 /**
277 * Stores data for nodes. The QHash's value is the data of the processing instruction, and the
278 * content of a text node or comment.
279 */
280 QHash<PreNumber, QString> data;
281
282 QVector<BasicNodeData> basicData;
283
284 inline QUrl documentUri() const
285 {
286 return m_documentURI;
287 }
288
289 inline QUrl baseUri() const
290 {
291 return m_baseURI;
292 }
293
294 /**
295 * @short Returns @c true if the node identified by @p pre has child
296 * nodes(in the sense of the XDM), but also if it has namespace nodes,
297 * or attribute nodes.
298 */
299 inline bool hasChildren(const PreNumber pre) const
300 {
301 return basicData.at(pre).size() > 0;
302 }
303
304 /**
305 * @short Returns the parent node of @p pre.
306 *
307 * If @p pre parent doesn't have a parent node, the return value is
308 * undefined.
309 *
310 * @see hasParent()
311 */
312 inline PreNumber parent(const PreNumber pre) const
313 {
314 return basicData.at(pre).parent();
315 }
316
317 inline bool hasParent(const PreNumber pre) const
318 {
319 return basicData.at(pre).depth() > 0;
320 }
321
322 inline bool hasFollowingSibling(const PreNumber pre) const
323 {
324 return pre < maximumPreNumber();
325 }
326
327 inline PostNumber postNumber(const PreNumber pre) const
328 {
329 const BasicNodeData &b = basicData.at(pre);
330 return pre + b.size() - b.depth();
331 }
332
333 inline QXmlNodeModelIndex::NodeKind kind(const PreNumber pre) const
334 {
335 return basicData.at(pre).kind();
336 }
337
338 inline PreNumber maximumPreNumber() const
339 {
340 return basicData.count() - 1;
341 }
342
343 inline PreNumber toPreNumber(const QXmlNodeModelIndex n) const
344 {
345 return n.data();
346 }
347
348 inline PreNumber size(const PreNumber pre) const
349 {
350 Q_ASSERT_X(basicData.at(pre).size() != -1, Q_FUNC_INFO,
351 "The size cannot be -1. That means an uninitialized value is attempted to be used.");
352 return basicData.at(pre).size();
353 }
354
355 inline Depth depth(const PreNumber pre) const
356 {
357 return basicData.at(pre).depth();
358 }
359
360 void printStats(const NamePool::Ptr &np) const;
361
362 inline QXmlName name(const PreNumber pre) const
363 {
364 return basicData.at(pre).name();
365 }
366
367 inline bool isCompressed(const PreNumber pre) const
368 {
369 return basicData.at(pre).isCompressed();
370 }
371
372 static inline bool hasPrefix(const QVector<QXmlName> &nbs, const QXmlName::PrefixCode prefix);
373
374 QUrl m_documentURI;
375 QUrl m_baseURI;
376
377 protected:
378 virtual QXmlNodeModelIndex nextFromSimpleAxis(QAbstractXmlNodeModel::SimpleAxis,
379 const QXmlNodeModelIndex&) const;
380 virtual QVector<QXmlNodeModelIndex> attributes(const QXmlNodeModelIndex &element) const;
381
382 private:
383 /**
384 * Copies the children of @p node to @p receiver.
385 */
386 inline void copyChildren(const QXmlNodeModelIndex &node,
387 QAbstractXmlReceiver *const receiver,
388 const NodeCopySettings &settings) const;
389
390 /**
391 * The key is the xml:id value, and the value is the element
392 * with that value.
393 */
394 QHash<QXmlName::LocalNameCode, PreNumber> m_IDs;
395 };
396}
397
398Q_DECLARE_TYPEINFO(QPatternist::AccelTree::BasicNodeData, Q_MOVABLE_TYPE);
399
400QT_END_NAMESPACE
401
402QT_END_HEADER
403
404#endif
Note: See TracBrowser for help on using the repository browser.