File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\index\PageDataLeaf.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.lang.ref.SoftReference;
10 import java.util.Arrays;
11 import org.h2.constant.ErrorCode;
12 import org.h2.constant.SysProperties;
13 import org.h2.engine.Constants;
14 import org.h2.engine.Session;
15 import org.h2.message.DbException;
16 import org.h2.result.Row;
17 import org.h2.store.Data;
18 import org.h2.store.Page;
19 import org.h2.store.PageStore;
20 import org.h2.table.RegularTable;
21 import org.h2.value.Value;
22
23 /**
24 * A leaf page that contains data of one or multiple rows. Format:
25 * <ul>
26 * <li>page type: byte (0)</li>
27 * <li>checksum: short (1-2)</li>
28 * <li>parent page id (0 for root): int (3-6)</li>
29 * <li>table id: varInt</li>
30 * <li>column count: varInt</li>
31 * <li>entry count: short</li>
32 * <li>with overflow: the first overflow page id: int</li>
33 * <li>list of key / offset pairs (key: varLong, offset: shortInt)</li>
34 * <li>data</li>
35 * </ul>
36 */
37 public class PageDataLeaf extends PageData {
38
39 private final boolean optimizeUpdate;
40
41 /**
42 * The row offsets.
43 */
44 private int[] offsets;
45
46 /**
47 * The rows.
48 */
49 private Row[] rows;
50
51 /**
52 * For pages with overflow: the soft reference to the row
53 */
54 private SoftReference<Row> rowRef;
55
56 /**
57 * The page id of the first overflow page (0 if no overflow).
58 */
59 private int firstOverflowPageId;
60
61 /**
62 * The start of the data area.
63 */
64 private int start;
65
66 /**
67 * The size of the row in bytes for large rows.
68 */
69 private int overflowRowSize;
70
71 private int columnCount;
72
73 private int memoryData;
74
75 private boolean writtenData;
76
77 private PageDataLeaf(PageDataIndex index, int pageId, Data data) {
78 super(index, pageId, data);
79 this.optimizeUpdate = index.getDatabase().getSettings().optimizeUpdate;
80 }
81
82 /**
83 * Create a new page.
84 *
85 * @param index the index
86 * @param pageId the page id
87 * @param parentPageId the parent
88 * @return the page
89 */
90 static PageDataLeaf create(PageDataIndex index, int pageId, int parentPageId) {
91 PageDataLeaf p = new PageDataLeaf(index, pageId, index.getPageStore().createData());
92 index.getPageStore().logUndo(p, null);
93 p.rows = Row.EMPTY_ARRAY;
94 p.parentPageId = parentPageId;
95 p.columnCount = index.getTable().getColumns().length;
96 p.writeHead();
97 p.start = p.data.length();
98 return p;
99 }
100
101 /**
102 * Read a data leaf page.
103 *
104 * @param index the index
105 * @param data the data
106 * @param pageId the page id
107 * @return the page
108 */
109 public static Page read(PageDataIndex index, Data data, int pageId) {
110 PageDataLeaf p = new PageDataLeaf(index, pageId, data);
111 p.read();
112 return p;
113 }
114
115 private void read() {
116 data.reset();
117 int type = data.readByte();
118 data.readShortInt();
119 this.parentPageId = data.readInt();
120 int tableId = data.readVarInt();
121 if (tableId != index.getId()) {
122 throw DbException.get(ErrorCode.FILE_CORRUPTED_1,
123 "page:" + getPos() + " expected table:" + index.getId() +
124 " got:" + tableId + " type:" + type);
125 }
126 columnCount = data.readVarInt();
127 entryCount = data.readShortInt();
128 offsets = new int[entryCount];
129 keys = new long[entryCount];
130 rows = new Row[entryCount];
131 if (type == Page.TYPE_DATA_LEAF) {
132 if (entryCount != 1) {
133 DbException.throwInternalError("entries: " + entryCount);
134 }
135 firstOverflowPageId = data.readInt();
136 }
137 for (int i = 0; i < entryCount; i++) {
138 keys[i] = data.readVarLong();
139 offsets[i] = data.readShortInt();
140 }
141 start = data.length();
142 written = true;
143 writtenData = true;
144 }
145
146 private int getRowLength(Row row) {
147 int size = 0;
148 for (int i = 0; i < columnCount; i++) {
149 size += data.getValueLen(row.getValue(i));
150 }
151 return size;
152 }
153
154 private int findInsertionPoint(long key) {
155 int x = find(key);
156 if (x < entryCount && keys[x] == key) {
157 throw index.getDuplicateKeyException();
158 }
159 return x;
160 }
161
162 int addRowTry(Row row) {
163 index.getPageStore().logUndo(this, data);
164 int rowLength = getRowLength(row);
165 int pageSize = index.getPageStore().getPageSize();
166 int last = entryCount == 0 ? pageSize : offsets[entryCount - 1];
167 int keyOffsetPairLen = 2 + Data.getVarLongLen(row.getKey());
168 if (entryCount > 0 && last - rowLength < start + keyOffsetPairLen) {
169 int x = findInsertionPoint(row.getKey());
170 if (entryCount > 1) {
171 if (entryCount < 5) {
172 // required, otherwise the index doesn't work correctly
173 return entryCount / 2;
174 }
175 if (index.isSortedInsertMode()) {
176 return x < 2 ? 1 : x > entryCount - 1 ? entryCount - 1 : x;
177 }
178 // split near the insertion point to better fill pages
179 // split in half would be:
180 // return entryCount / 2;
181 int third = entryCount / 3;
182 return x < third ? third : x >= 2 * third ? 2 * third : x;
183 }
184 return x;
185 }
186 index.getPageStore().logUndo(this, data);
187 int x;
188 if (entryCount == 0) {
189 x = 0;
190 } else {
191 if (!optimizeUpdate) {
192 readAllRows();
193 }
194 x = findInsertionPoint(row.getKey());
195 }
196 written = false;
197 changeCount = index.getPageStore().getChangeCount();
198 last = x == 0 ? pageSize : offsets[x - 1];
199 int offset = last - rowLength;
200 start += keyOffsetPairLen;
201 offsets = insert(offsets, entryCount, x, offset);
202 add(offsets, x + 1, entryCount + 1, -rowLength);
203 keys = insert(keys, entryCount, x, row.getKey());
204 rows = insert(rows, entryCount, x, row);
205 entryCount++;
206 index.getPageStore().update(this);
207 if (optimizeUpdate) {
208 if (writtenData && offset >= start) {
209 byte[] d = data.getBytes();
210 int dataStart = offsets[entryCount - 1] + rowLength;
211 int dataEnd = offsets[x];
212 System.arraycopy(d, dataStart, d, dataStart - rowLength, dataEnd - dataStart + rowLength);
213 data.setPos(dataEnd);
214 for (int j = 0; j < columnCount; j++) {
215 data.writeValue(row.getValue(j));
216 }
217 }
218 }
219 if (offset < start) {
220 writtenData = false;
221 if (entryCount > 1) {
222 DbException.throwInternalError();
223 }
224 // need to write the overflow page id
225 start += 4;
226 int remaining = rowLength - (pageSize - start);
227 // fix offset
228 offset = start;
229 offsets[x] = offset;
230 int previous = getPos();
231 int dataOffset = pageSize;
232 int page = index.getPageStore().allocatePage();
233 firstOverflowPageId = page;
234 this.overflowRowSize = pageSize + rowLength;
235 writeData();
236 // free up the space used by the row
237 Row r = rows[0];
238 rowRef = new SoftReference<Row>(r);
239 rows[0] = null;
240 Data all = index.getPageStore().createData();
241 all.checkCapacity(data.length());
242 all.write(data.getBytes(), 0, data.length());
243 data.truncate(index.getPageStore().getPageSize());
244 do {
245 int type, size, next;
246 if (remaining <= pageSize - PageDataOverflow.START_LAST) {
247 type = Page.TYPE_DATA_OVERFLOW | Page.FLAG_LAST;
248 size = remaining;
249 next = 0;
250 } else {
251 type = Page.TYPE_DATA_OVERFLOW;
252 size = pageSize - PageDataOverflow.START_MORE;
253 next = index.getPageStore().allocatePage();
254 }
255 PageDataOverflow overflow = PageDataOverflow.create(index.getPageStore(),
256 page, type, previous, next, all, dataOffset, size);
257 index.getPageStore().update(overflow);
258 dataOffset += size;
259 remaining -= size;
260 previous = page;
261 page = next;
262 } while (remaining > 0);
263 }
264 if (rowRef == null) {
265 memoryChange(true, row);
266 } else {
267 memoryChange(true, null);
268 }
269 return -1;
270 }
271
272 private void removeRow(int i) {
273 index.getPageStore().logUndo(this, data);
274 written = false;
275 changeCount = index.getPageStore().getChangeCount();
276 if (!optimizeUpdate) {
277 readAllRows();
278 }
279 Row r = getRowAt(i);
280 if (r != null) {
281 memoryChange(false, r);
282 }
283 entryCount--;
284 if (entryCount < 0) {
285 DbException.throwInternalError();
286 }
287 if (firstOverflowPageId != 0) {
288 start -= 4;
289 freeOverflow();
290 firstOverflowPageId = 0;
291 overflowRowSize = 0;
292 rowRef = null;
293 }
294 int keyOffsetPairLen = 2 + Data.getVarLongLen(keys[i]);
295 int startNext = i > 0 ? offsets[i - 1] : index.getPageStore().getPageSize();
296 int rowLength = startNext - offsets[i];
297 if (optimizeUpdate) {
298 if (writtenData) {
299 byte[] d = data.getBytes();
300 int dataStart = offsets[entryCount];
301 System.arraycopy(d, dataStart, d, dataStart + rowLength, offsets[i] - dataStart);
302 Arrays.fill(d, dataStart, dataStart + rowLength, (byte) 0);
303 }
304 } else {
305 int clearStart = offsets[entryCount];
306 Arrays.fill(data.getBytes(), clearStart, clearStart + rowLength, (byte) 0);
307 }
308 start -= keyOffsetPairLen;
309 offsets = remove(offsets, entryCount + 1, i);
310 add(offsets, i, entryCount, rowLength);
311 keys = remove(keys, entryCount + 1, i);
312 rows = remove(rows, entryCount + 1, i);
313 }
314
315 Cursor find(Session session, long minKey, long maxKey, boolean multiVersion) {
316 int x = find(minKey);
317 return new PageDataCursor(session, this, x, maxKey, multiVersion);
318 }
319
320 /**
321 * Get the row at the given index.
322 *
323 * @param at the index
324 * @return the row
325 */
326 Row getRowAt(int at) {
327 Row r = rows[at];
328 if (r == null) {
329 if (firstOverflowPageId == 0) {
330 r = readRow(data, offsets[at], columnCount);
331 } else {
332 if (rowRef != null) {
333 r = rowRef.get();
334 if (r != null) {
335 return r;
336 }
337 }
338 PageStore store = index.getPageStore();
339 Data buff = store.createData();
340 int pageSize = store.getPageSize();
341 int offset = offsets[at];
342 buff.write(data.getBytes(), offset, pageSize - offset);
343 int next = firstOverflowPageId;
344 do {
345 PageDataOverflow page = index.getPageOverflow(next);
346 next = page.readInto(buff);
347 } while (next != 0);
348 overflowRowSize = pageSize + buff.length();
349 r = readRow(buff, 0, columnCount);
350 }
351 r.setKey(keys[at]);
352 if (firstOverflowPageId != 0) {
353 rowRef = new SoftReference<Row>(r);
354 } else {
355 rows[at] = r;
356 memoryChange(true, r);
357 }
358 }
359 return r;
360 }
361
362 int getEntryCount() {
363 return entryCount;
364 }
365
366 PageData split(int splitPoint) {
367 int newPageId = index.getPageStore().allocatePage();
368 PageDataLeaf p2 = PageDataLeaf.create(index, newPageId, parentPageId);
369 for (int i = splitPoint; i < entryCount;) {
370 int split = p2.addRowTry(getRowAt(splitPoint));
371 if (split != -1) {
372 DbException.throwInternalError("split " + split);
373 }
374 removeRow(splitPoint);
375 }
376 return p2;
377 }
378
379 long getLastKey() {
380 // TODO re-use keys, but remove this mechanism
381 if (entryCount == 0) {
382 return 0;
383 }
384 return getRowAt(entryCount - 1).getKey();
385 }
386
387 PageDataLeaf getNextPage() {
388 if (parentPageId == PageData.ROOT) {
389 return null;
390 }
391 PageDataNode next = (PageDataNode) index.getPage(parentPageId, -1);
392 return next.getNextPage(keys[entryCount - 1]);
393 }
394
395 PageDataLeaf getFirstLeaf() {
396 return this;
397 }
398
399 protected void remapChildren(int old) {
400 if (firstOverflowPageId == 0) {
401 return;
402 }
403 PageDataOverflow overflow = index.getPageOverflow(firstOverflowPageId);
404 overflow.setParentPageId(getPos());
405 index.getPageStore().update(overflow);
406 }
407
408 boolean remove(long key) {
409 int i = find(key);
410 if (keys == null || keys[i] != key) {
411 throw DbException.get(ErrorCode.ROW_NOT_FOUND_WHEN_DELETING_1,
412 index.getSQL() + ": " + key + " " + (keys == null ? -1 : keys[i]));
413 }
414 index.getPageStore().logUndo(this, data);
415 if (entryCount == 1) {
416 freeRecursive();
417 return true;
418 }
419 removeRow(i);
420 index.getPageStore().update(this);
421 return false;
422 }
423
424 void freeRecursive() {
425 index.getPageStore().logUndo(this, data);
426 index.getPageStore().free(getPos());
427 freeOverflow();
428 }
429
430 private void freeOverflow() {
431 if (firstOverflowPageId != 0) {
432 int next = firstOverflowPageId;
433 do {
434 PageDataOverflow page = index.getPageOverflow(next);
435 page.free();
436 next = page.getNextOverflow();
437 } while (next != 0);
438 }
439 }
440
441 Row getRowWithKey(long key) {
442 int at = find(key);
443 return getRowAt(at);
444 }
445
446 int getRowCount() {
447 return entryCount;
448 }
449
450 void setRowCountStored(int rowCount) {
451 // ignore
452 }
453
454 public void write() {
455 writeData();
456 index.getPageStore().writePage(getPos(), data);
457 data.truncate(index.getPageStore().getPageSize());
458 }
459
460 private void readAllRows() {
461 for (int i = 0; i < entryCount; i++) {
462 getRowAt(i);
463 }
464 }
465
466 private void writeHead() {
467 data.reset();
468 int type;
469 if (firstOverflowPageId == 0) {
470 type = Page.TYPE_DATA_LEAF | Page.FLAG_LAST;
471 } else {
472 type = Page.TYPE_DATA_LEAF;
473 }
474 data.writeByte((byte) type);
475 data.writeShortInt(0);
476 if (SysProperties.CHECK2) {
477 if (data.length() != START_PARENT) {
478 DbException.throwInternalError();
479 }
480 }
481 data.writeInt(parentPageId);
482 data.writeVarInt(index.getId());
483 data.writeVarInt(columnCount);
484 data.writeShortInt(entryCount);
485 }
486
487 private void writeData() {
488 if (written) {
489 return;
490 }
491 if (!optimizeUpdate) {
492 readAllRows();
493 }
494 writeHead();
495 if (firstOverflowPageId != 0) {
496 data.writeInt(firstOverflowPageId);
497 data.checkCapacity(overflowRowSize);
498 }
499 for (int i = 0; i < entryCount; i++) {
500 data.writeVarLong(keys[i]);
501 data.writeShortInt(offsets[i]);
502 }
503 if (!writtenData || !optimizeUpdate) {
504 for (int i = 0; i < entryCount; i++) {
505 data.setPos(offsets[i]);
506 Row r = getRowAt(i);
507 for (int j = 0; j < columnCount; j++) {
508 data.writeValue(r.getValue(j));
509 }
510 }
511 writtenData = true;
512 }
513 written = true;
514 }
515
516 public String toString() {
517 return "page[" + getPos() + "] data leaf table:" + index.getId() + " " + index.getTable().getName() +
518 " entries:" + entryCount + " parent:" + parentPageId +
519 (firstOverflowPageId == 0 ? "" : " overflow:" + firstOverflowPageId) +
520 " keys:" + Arrays.toString(keys) + " offsets:" + Arrays.toString(offsets);
521 }
522
523 public void moveTo(Session session, int newPos) {
524 PageStore store = index.getPageStore();
525 // load the pages into the cache, to ensure old pages
526 // are written
527 if (parentPageId != ROOT) {
528 store.getPage(parentPageId);
529 }
530 store.logUndo(this, data);
531 PageDataLeaf p2 = PageDataLeaf.create(index, newPos, parentPageId);
532 readAllRows();
533 p2.keys = keys;
534 p2.overflowRowSize = overflowRowSize;
535 p2.firstOverflowPageId = firstOverflowPageId;
536 p2.rowRef = rowRef;
537 p2.rows = rows;
538 if (firstOverflowPageId != 0) {
539 p2.rows[0] = getRowAt(0);
540 }
541 p2.entryCount = entryCount;
542 p2.offsets = offsets;
543 p2.start = start;
544 p2.remapChildren(getPos());
545 p2.writeData();
546 p2.data.truncate(index.getPageStore().getPageSize());
547 store.update(p2);
548 if (parentPageId == ROOT) {
549 index.setRootPageId(session, newPos);
550 } else {
551 PageDataNode p = (PageDataNode) store.getPage(parentPageId);
552 p.moveChild(getPos(), newPos);
553 }
554 store.free(getPos());
555 }
556
557 /**
558 * Set the overflow page id.
559 *
560 * @param old the old overflow page id
561 * @param overflow the new overflow page id
562 */
563 void setOverflow(int old, int overflow) {
564 if (SysProperties.CHECK && old != firstOverflowPageId) {
565 DbException.throwInternalError("move " + this + " " + firstOverflowPageId);
566 }
567 index.getPageStore().logUndo(this, data);
568 firstOverflowPageId = overflow;
569 if (written) {
570 changeCount = index.getPageStore().getChangeCount();
571 writeHead();
572 data.writeInt(firstOverflowPageId);
573 }
574 index.getPageStore().update(this);
575 }
576
577 private void memoryChange(boolean add, Row r) {
578 int diff = r == null ? 0 : 4 + 8 + Constants.MEMORY_POINTER + r.getMemory();
579 memoryData += add ? diff : -diff;
580 index.memoryChange((Constants.MEMORY_PAGE_DATA + memoryData + index.getPageStore().getPageSize()) >> 2);
581 }
582
583 public boolean isStream() {
584 return firstOverflowPageId > 0;
585 }
586
587 /**
588 * Read a row from the data page at the given position.
589 *
590 * @param data the data page
591 * @param pos the position to read from
592 * @param columnCount the number of columns
593 * @return the row
594 */
595 private static Row readRow(Data data, int pos, int columnCount) {
596 Value[] values = new Value[columnCount];
597 synchronized (data) {
598 data.setPos(pos);
599 for (int i = 0; i < columnCount; i++) {
600 values[i] = data.readValue();
601 }
602 }
603 return RegularTable.createRow(values);
604 }
605
606 }
607