c0c447ce6da17b5ebb941b928959678424180c9b
[vxquery.git] / vxquery-core / src / main / java / org / apache / vxquery / datamodel / accessors / nodes / NodeTreePointable.java
1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. 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 package org.apache.vxquery.datamodel.accessors.nodes;
18
19 import org.apache.hyracks.api.dataflow.value.ITypeTraits;
20 import org.apache.hyracks.data.std.algorithms.BinarySearchAlgorithm;
21 import org.apache.hyracks.data.std.api.AbstractPointable;
22 import org.apache.hyracks.data.std.api.IPointable;
23 import org.apache.hyracks.data.std.api.IPointableFactory;
24 import org.apache.hyracks.data.std.collections.api.IValueReferenceVector;
25 import org.apache.hyracks.data.std.primitive.BytePointable;
26 import org.apache.hyracks.data.std.primitive.IntegerPointable;
27 import org.apache.hyracks.data.std.primitive.UTF8StringPointable;
28 import org.apache.hyracks.data.std.primitive.VoidPointable;
29 import org.apache.hyracks.util.string.UTF8StringUtil;
30 import org.apache.vxquery.datamodel.accessors.TaggedValuePointable;
31
32 /*
33 * NodeTree {
34 * NodeTreeHeader header;
35 * NodeId nodeId?;
36 * Dictionary dictionary?;
37 * ElementNode rootNode;
38 * }
39 *
40 * ElementHeader (padded) {
41 * bit nodeIdExists;
42 * bit dictionaryExists;
43 * bit headerTypeExists;
44 * }
45 *
46 * NodeId {
47 * int32 id;
48 * }
49 *
50 * Dictionary {
51 * int32 numberOfItems
52 * int32[numberOfItems] lengthOfItem
53 * int32[numberOfItems] sortedItemIndex
54 * bytes[] itemData
55 * }
56 */
57 public class NodeTreePointable extends AbstractPointable {
58 public static final int HEADER_NODEID_EXISTS_MASK = (1 << 0);
59 public static final int HEADER_DICTIONARY_EXISTS_MASK = (1 << 1);
60 public static final int HEADER_TYPE_EXISTS_MASK = (1 << 2);
61
62 private static final int HEADER_OFFSET = 0;
63 private static final int HEADER_SIZE = 1;
64 private static final int NODE_ID_SIZE = 4;
65
66 private static final int DICTIONARY_SIZE_SIZE = 4;
67 private static final int DICTIONARY_NENTRIES_SIZE = 4;
68 private static final int IDX_PTR_SLOT_SIZE = 4;
69 private static final int SORTED_PTR_SLOT_SIZE = 4;
70
71 public static final IPointableFactory FACTORY = new IPointableFactory() {
72 private static final long serialVersionUID = 1L;
73
74 @Override
75 public ITypeTraits getTypeTraits() {
76 return VoidPointable.TYPE_TRAITS;
77 }
78
79 @Override
80 public IPointable createPointable() {
81 return new NodeTreePointable();
82 }
83 };
84
85 private final IValueReferenceVector sortedStringVector = new IValueReferenceVector() {
86 @Override
87 public int getSize() {
88 return getDictionaryEntryCount();
89 }
90
91 @Override
92 public byte[] getBytes(int index) {
93 return bytes;
94 }
95
96 @Override
97 public int getStart(int index) {
98 int dataAreaStart = getDictionaryDataAreaStartOffset();
99 int sortedPtrArrayStart = getDictionarySortedPointerArrayOffset();
100 int sortedSlotValue = IntegerPointable.getInteger(bytes,
101 sortedPtrArrayStart + index * SORTED_PTR_SLOT_SIZE);
102 return dataAreaStart + sortedSlotValue;
103 }
104
105 @Override
106 public int getLength(int index) {
107 int utfLength = UTF8StringUtil.getUTFLength(bytes, getStart(index));
108 return utfLength + UTF8StringUtil.getNumBytesToStoreLength(utfLength);
109 }
110 };
111
112 private final BinarySearchAlgorithm binSearch = new BinarySearchAlgorithm();
113
114 public boolean nodeIdExists() {
115 return (getHeader() & HEADER_NODEID_EXISTS_MASK) != 0;
116 }
117
118 public boolean dictionaryExists() {
119 return (getHeader() & HEADER_DICTIONARY_EXISTS_MASK) != 0;
120 }
121
122 public boolean typeExists() {
123 return (getHeader() & HEADER_TYPE_EXISTS_MASK) != 0;
124 }
125
126 public int getRootNodeId() {
127 return nodeIdExists() ? IntegerPointable.getInteger(bytes, getNodeIdOffset()) : -1;
128 }
129
130 public int getDictionaryEntryCount() {
131 return dictionaryExists() ? IntegerPointable.getInteger(bytes, getDictionaryEntryCountOffset()) : 0;
132 }
133
134 public void getString(int idx, UTF8StringPointable string) {
135 int nEntries = getDictionaryEntryCount();
136 if (idx < 0 || idx >= nEntries) {
137 throw new IllegalArgumentException(idx + " not within [0, " + nEntries + ")");
138 }
139 int dataAreaStart = getDictionaryDataAreaStartOffset();
140 int idxSlotValue = idx == 0 ? 0
141 : IntegerPointable.getInteger(bytes,
142 getDictionaryIndexPointerArrayOffset() + (idx - 1) * IDX_PTR_SLOT_SIZE);
143 int strLen = UTF8StringUtil.getUTFLength(bytes, dataAreaStart + idxSlotValue);
144 int strMetaLen = UTF8StringUtil.getNumBytesToStoreLength(strLen);
145 string.set(bytes, dataAreaStart + idxSlotValue, strMetaLen + strLen);
146 }
147
148 public int lookupString(UTF8StringPointable key) {
149 boolean found = binSearch.find(sortedStringVector, key);
150 if (!found) {
151 return -1;
152 }
153 int index = binSearch.getIndex();
154 return IntegerPointable.getInteger(bytes,
155 sortedStringVector.getStart(index) + sortedStringVector.getLength(index));
156 }
157
158 public void getRootNode(TaggedValuePointable node) {
159 node.set(bytes, getRootNodeOffset(), length - getRootNodeOffset() + start);
160 }
161
162 private byte getHeader() {
163 return BytePointable.getByte(bytes, getHeaderOffset());
164 }
165
166 private int getHeaderOffset() {
167 return start + HEADER_OFFSET;
168 }
169
170 private int getHeaderSize() {
171 return HEADER_SIZE;
172 }
173
174 private int getNodeIdOffset() {
175 return getHeaderOffset() + getHeaderSize();
176 }
177
178 private int getNodeIdSize() {
179 return nodeIdExists() ? NODE_ID_SIZE : 0;
180 }
181
182 public int getDictionaryOffset() {
183 return getNodeIdOffset() + getNodeIdSize();
184 }
185
186 public int getDictionarySize() {
187 return dictionaryExists() ? IntegerPointable.getInteger(bytes, getDictionaryOffset()) : 0;
188 }
189
190 private int getDictionaryEntryCountOffset() {
191 return getDictionaryOffset() + DICTIONARY_SIZE_SIZE;
192 }
193
194 private int getDictionaryIndexPointerArrayOffset() {
195 return getDictionaryEntryCountOffset() + DICTIONARY_NENTRIES_SIZE;
196 }
197
198 private int getDictionarySortedPointerArrayOffset() {
199 return getDictionaryIndexPointerArrayOffset() + getDictionaryEntryCount() * IDX_PTR_SLOT_SIZE;
200 }
201
202 private int getDictionaryDataAreaStartOffset() {
203 return getDictionaryIndexPointerArrayOffset()
204 + getDictionaryEntryCount() * (IDX_PTR_SLOT_SIZE + SORTED_PTR_SLOT_SIZE);
205 }
206
207 private int getRootNodeOffset() {
208 return getDictionaryOffset() + getDictionarySize();
209 }
210 }