File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\index\PageDataNode.java.html

1 /*
2 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
3 * Version 1.0, and under the Eclipse Public License, Version 1.0
4 * (http://h2database.com/html/license.html).
5 * Initial Developer: H2 Group
6 */
7 package org.h2.index;
8
9 import java.util.Arrays;
10 import org.h2.api.DatabaseEventListener;
11 import org.h2.constant.ErrorCode;
12 import org.h2.constant.SysProperties;
13 import org.h2.engine.Session;
14 import org.h2.message.DbException;
15 import org.h2.result.Row;
16 import org.h2.store.Data;
17 import org.h2.store.Page;
18 import org.h2.store.PageStore;
19 import org.h2.util.Utils;
20
21 /**
22 * A leaf page that contains data of one or multiple rows. Format:
23 * <ul>
24 * <li>page type: byte (0)</li>
25 * <li>checksum: short (1-2)</li>
26 * <li>parent page id (0 for root): int (3-6)</li>
27 * <li>table id: varInt</li>
28 * <li>count of all children (-1 if not known): int</li>
29 * <li>entry count: short</li>
30 * <li>rightmost child page id: int</li>
31 * <li>entries (child page id: int, key: varLong)</li>
32 * </ul>
33 * The key is the largest key of the respective child, meaning key[0] is the
34 * largest key of child[0].
35 */
36 public class PageDataNode extends PageData {
37
38 /**
39 * The page ids of the children.
40 */
41 private int[] childPageIds;
42
43 private int rowCountStored = UNKNOWN_ROWCOUNT;
44
45 private int rowCount = UNKNOWN_ROWCOUNT;
46
47 /**
48 * The number of bytes used in the page
49 */
50 private int length;
51
52 private PageDataNode(PageDataIndex index, int pageId, Data data) {
53 super(index, pageId, data);
54 }
55
56 /**
57 * Create a new page.
58 *
59 * @param index the index
60 * @param pageId the page id
61 * @param parentPageId the parent
62 * @return the page
63 */
64 static PageDataNode create(PageDataIndex index, int pageId, int parentPageId) {
65 PageDataNode p = new PageDataNode(index, pageId, index.getPageStore().createData());
66 index.getPageStore().logUndo(p, null);
67 p.parentPageId = parentPageId;
68 p.writeHead();
69 // 4 bytes for the rightmost child page id
70 p.length = p.data.length() + 4;
71 return p;
72 }
73
74 /**
75 * Read a data node page.
76 *
77 * @param index the index
78 * @param data the data
79 * @param pageId the page id
80 * @return the page
81 */
82 public static Page read(PageDataIndex index, Data data, int pageId) {
83 PageDataNode p = new PageDataNode(index, pageId, data);
84 p.read();
85 return p;
86 }
87
88 private void read() {
89 data.reset();
90 data.readByte();
91 data.readShortInt();
92 this.parentPageId = data.readInt();
93 int indexId = data.readVarInt();
94 if (indexId != index.getId()) {
95 throw DbException.get(ErrorCode.FILE_CORRUPTED_1,
96 "page:" + getPos() + " expected index:" + index.getId() +
97 "got:" + indexId);
98 }
99 rowCount = rowCountStored = data.readInt();
100 entryCount = data.readShortInt();
101 childPageIds = new int[entryCount + 1];
102 childPageIds[entryCount] = data.readInt();
103 keys = Utils.newLongArray(entryCount);
104 for (int i = 0; i < entryCount; i++) {
105 childPageIds[i] = data.readInt();
106 keys[i] = data.readVarLong();
107 }
108 length = data.length();
109 check();
110 written = true;
111 }
112
113 private void addChild(int x, int childPageId, long key) {
114 index.getPageStore().logUndo(this, data);
115 written = false;
116 changeCount = index.getPageStore().getChangeCount();
117 childPageIds = insert(childPageIds, entryCount + 1, x + 1, childPageId);
118 keys = insert(keys, entryCount, x, key);
119 entryCount++;
120 length += 4 + Data.getVarLongLen(key);
121 }
122
123 int addRowTry(Row row) {
124 index.getPageStore().logUndo(this, data);
125 int keyOffsetPairLen = 4 + Data.getVarLongLen(row.getKey());
126 while (true) {
127 int x = find(row.getKey());
128 PageData page = index.getPage(childPageIds[x], getPos());
129 int splitPoint = page.addRowTry(row);
130 if (splitPoint == -1) {
131 break;
132 }
133 if (length + keyOffsetPairLen > index.getPageStore().getPageSize()) {
134 return entryCount / 2;
135 }
136 long pivot = splitPoint == 0 ? row.getKey() : page.getKey(splitPoint - 1);
137 PageData page2 = page.split(splitPoint);
138 index.getPageStore().update(page);
139 index.getPageStore().update(page2);
140 addChild(x, page2.getPos(), pivot);
141 index.getPageStore().update(this);
142 }
143 updateRowCount(1);
144 return -1;
145 }
146
147 private void updateRowCount(int offset) {
148 if (rowCount != UNKNOWN_ROWCOUNT) {
149 rowCount += offset;
150 }
151 if (rowCountStored != UNKNOWN_ROWCOUNT) {
152 rowCountStored = UNKNOWN_ROWCOUNT;
153 index.getPageStore().logUndo(this, data);
154 if (written) {
155 writeHead();
156 }
157 index.getPageStore().update(this);
158 }
159 }
160
161 Cursor find(Session session, long minKey, long maxKey, boolean multiVersion) {
162 int x = find(minKey);
163 int child = childPageIds[x];
164 return index.getPage(child, getPos()).find(session, minKey, maxKey, multiVersion);
165 }
166
167 PageData split(int splitPoint) {
168 int newPageId = index.getPageStore().allocatePage();
169 PageDataNode p2 = PageDataNode.create(index, newPageId, parentPageId);
170 int firstChild = childPageIds[splitPoint];
171 for (int i = splitPoint; i < entryCount;) {
172 p2.addChild(p2.entryCount, childPageIds[splitPoint + 1], keys[splitPoint]);
173 removeChild(splitPoint);
174 }
175 int lastChild = childPageIds[splitPoint - 1];
176 removeChild(splitPoint - 1);
177 childPageIds[splitPoint - 1] = lastChild;
178 p2.childPageIds[0] = firstChild;
179 p2.remapChildren(getPos());
180 return p2;
181 }
182
183 protected void remapChildren(int old) {
184 for (int i = 0; i < entryCount + 1; i++) {
185 int child = childPageIds[i];
186 PageData p = index.getPage(child, old);
187 p.setParentPageId(getPos());
188 index.getPageStore().update(p);
189 }
190 }
191
192 /**
193 * Initialize the page.
194 *
195 * @param page1 the first child page
196 * @param pivot the pivot key
197 * @param page2 the last child page
198 */
199 void init(PageData page1, long pivot, PageData page2) {
200 entryCount = 1;
201 childPageIds = new int[] { page1.getPos(), page2.getPos() };
202 keys = new long[] { pivot };
203 length += 4 + Data.getVarLongLen(pivot);
204 check();
205 }
206
207 long getLastKey() {
208 return index.getPage(childPageIds[entryCount], getPos()).getLastKey();
209 }
210
211 /**
212 * Get the next leaf page.
213 *
214 * @param key the last key of the current page
215 * @return the next leaf page
216 */
217 PageDataLeaf getNextPage(long key) {
218 int i = find(key) + 1;
219 if (i > entryCount) {
220 if (parentPageId == PageData.ROOT) {
221 return null;
222 }
223 PageDataNode next = (PageDataNode) index.getPage(parentPageId, -1);
224 return next.getNextPage(key);
225 }
226 PageData page = index.getPage(childPageIds[i], getPos());
227 return page.getFirstLeaf();
228 }
229
230 PageDataLeaf getFirstLeaf() {
231 int child = childPageIds[0];
232 return index.getPage(child, getPos()).getFirstLeaf();
233 }
234
235 boolean remove(long key) {
236 int at = find(key);
237 // merge is not implemented to allow concurrent usage
238 // TODO maybe implement merge
239 PageData page = index.getPage(childPageIds[at], getPos());
240 boolean empty = page.remove(key);
241 index.getPageStore().logUndo(this, data);
242 updateRowCount(-1);
243 if (!empty) {
244 // the first row didn't change - nothing to do
245 return false;
246 }
247 // this child is now empty
248 index.getPageStore().free(page.getPos());
249 if (entryCount < 1) {
250 // no more children - this page is empty as well
251 return true;
252 }
253 removeChild(at);
254 index.getPageStore().update(this);
255 return false;
256 }
257
258 void freeRecursive() {
259 index.getPageStore().logUndo(this, data);
260 index.getPageStore().free(getPos());
261 for (int i = 0; i < entryCount + 1; i++) {
262 int child = childPageIds[i];
263 index.getPage(child, getPos()).freeRecursive();
264 }
265 }
266
267 Row getRowWithKey(long key) {
268 int at = find(key);
269 PageData page = index.getPage(childPageIds[at], getPos());
270 return page.getRowWithKey(key);
271 }
272
273 int getRowCount() {
274 if (rowCount == UNKNOWN_ROWCOUNT) {
275 int count = 0;
276 for (int i = 0; i < entryCount + 1; i++) {
277 int child = childPageIds[i];
278 PageData page = index.getPage(child, getPos());
279 if (getPos() == page.getPos()) {
280 throw DbException.throwInternalError("Page it its own child: " + getPos());
281 }
282 count += page.getRowCount();
283 index.getDatabase().setProgress(DatabaseEventListener.STATE_SCAN_FILE,
284 index.getTable() + "." + index.getName(), count, Integer.MAX_VALUE);
285 }
286 rowCount = count;
287 }
288 return rowCount;
289 }
290
291 void setRowCountStored(int rowCount) {
292 this.rowCount = rowCount;
293 if (rowCountStored != rowCount) {
294 rowCountStored = rowCount;
295 index.getPageStore().logUndo(this, data);
296 if (written) {
297 changeCount = index.getPageStore().getChangeCount();
298 writeHead();
299 }
300 index.getPageStore().update(this);
301 }
302 }
303
304 private void check() {
305 if (SysProperties.CHECK) {
306 for (int i = 0; i < entryCount + 1; i++) {
307 int child = childPageIds[i];
308 if (child == 0) {
309 DbException.throwInternalError();
310 }
311 }
312 }
313 }
314
315 public void write() {
316 writeData();
317 index.getPageStore().writePage(getPos(), data);
318 }
319
320 private void writeHead() {
321 data.reset();
322 data.writeByte((byte) Page.TYPE_DATA_NODE);
323 data.writeShortInt(0);
324 if (SysProperties.CHECK2) {
325 if (data.length() != START_PARENT) {
326 DbException.throwInternalError();
327 }
328 }
329 data.writeInt(parentPageId);
330 data.writeVarInt(index.getId());
331 data.writeInt(rowCountStored);
332 data.writeShortInt(entryCount);
333 }
334
335 private void writeData() {
336 if (written) {
337 return;
338 }
339 check();
340 writeHead();
341 data.writeInt(childPageIds[entryCount]);
342 for (int i = 0; i < entryCount; i++) {
343 data.writeInt(childPageIds[i]);
344 data.writeVarLong(keys[i]);
345 }
346 if (length != data.length()) {
347 DbException.throwInternalError("expected pos: " + length + " got: " + data.length());
348 }
349 written = true;
350 }
351
352 private void removeChild(int i) {
353 index.getPageStore().logUndo(this, data);
354 written = false;
355 changeCount = index.getPageStore().getChangeCount();
356 int removedKeyIndex = i < entryCount ? i : i - 1;
357 entryCount--;
358 length -= 4 + Data.getVarLongLen(keys[removedKeyIndex]);
359 if (entryCount < 0) {
360 DbException.throwInternalError();
361 }
362 keys = remove(keys, entryCount + 1, removedKeyIndex);
363 childPageIds = remove(childPageIds, entryCount + 2, i);
364 }
365
366 public String toString() {
367 return "page[" + getPos() + "] data node table:" + index.getId() +
368 " entries:" + entryCount + " " + Arrays.toString(childPageIds);
369 }
370
371 public void moveTo(Session session, int newPos) {
372 PageStore store = index.getPageStore();
373 // load the pages into the cache, to ensure old pages
374 // are written
375 for (int i = 0; i < entryCount + 1; i++) {
376 int child = childPageIds[i];
377 store.getPage(child);
378 }
379 if (parentPageId != ROOT) {
380 store.getPage(parentPageId);
381 }
382 store.logUndo(this, data);
383 PageDataNode p2 = PageDataNode.create(index, newPos, parentPageId);
384 p2.rowCountStored = rowCountStored;
385 p2.rowCount = rowCount;
386 p2.childPageIds = childPageIds;
387 p2.keys = keys;
388 p2.entryCount = entryCount;
389 p2.length = length;
390 store.update(p2);
391 if (parentPageId == ROOT) {
392 index.setRootPageId(session, newPos);
393 } else {
394 PageDataNode p = (PageDataNode) store.getPage(parentPageId);
395 p.moveChild(getPos(), newPos);
396 }
397 for (int i = 0; i < entryCount + 1; i++) {
398 int child = childPageIds[i];
399 PageData p = (PageData) store.getPage(child);
400 p.setParentPageId(newPos);
401 store.update(p);
402 }
403 store.free(getPos());
404 }
405
406 /**
407 * One of the children has moved to another page.
408 *
409 * @param oldPos the old position
410 * @param newPos the new position
411 */
412 void moveChild(int oldPos, int newPos) {
413 for (int i = 0; i < entryCount + 1; i++) {
414 if (childPageIds[i] == oldPos) {
415 index.getPageStore().logUndo(this, data);
416 written = false;
417 changeCount = index.getPageStore().getChangeCount();
418 childPageIds[i] = newPos;
419 index.getPageStore().update(this);
420 return;
421 }
422 }
423 throw DbException.throwInternalError();
424 }
425
426 }
427