File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\index\PageBtreeLeaf.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.constant.ErrorCode;
11 import org.h2.constant.SysProperties;
12 import org.h2.engine.Constants;
13 import org.h2.engine.Session;
14 import org.h2.message.DbException;
15 import org.h2.result.SearchRow;
16 import org.h2.store.Data;
17 import org.h2.store.Page;
18 import org.h2.store.PageStore;
19
20 /**
21 * A b-tree leaf page that contains index data. Format:
22 * <ul>
23 * <li>page type: byte</li>
24 * <li>checksum: short</li>
25 * <li>parent page id (0 for root): int</li>
26 * <li>index id: varInt</li>
27 * <li>entry count: short</li>
28 * <li>list of offsets: short</li>
29 * <li>data (key: varLong, value,...)</li>
30 * </ul>
31 */
32 public class PageBtreeLeaf extends PageBtree {
33
34 private static final int OFFSET_LENGTH = 2;
35
36 private final boolean optimizeUpdate;
37 private boolean writtenData;
38
39 private PageBtreeLeaf(PageBtreeIndex index, int pageId, Data data) {
40 super(index, pageId, data);
41 this.optimizeUpdate = index.getDatabase().getSettings().optimizeUpdate;
42 }
43
44 /**
45 * Read a b-tree leaf page.
46 *
47 * @param index the index
48 * @param data the data
49 * @param pageId the page id
50 * @return the page
51 */
52 public static Page read(PageBtreeIndex index, Data data, int pageId) {
53 PageBtreeLeaf p = new PageBtreeLeaf(index, pageId, data);
54 p.read();
55 return p;
56 }
57
58 /**
59 * Create a new page.
60 *
61 * @param index the index
62 * @param pageId the page id
63 * @param parentPageId the parent
64 * @return the page
65 */
66 static PageBtreeLeaf create(PageBtreeIndex index, int pageId, int parentPageId) {
67 PageBtreeLeaf p = new PageBtreeLeaf(index, pageId, index.getPageStore().createData());
68 index.getPageStore().logUndo(p, null);
69 p.rows = SearchRow.EMPTY_ARRAY;
70 p.parentPageId = parentPageId;
71 p.writeHead();
72 p.start = p.data.length();
73 return p;
74 }
75
76 private void read() {
77 data.reset();
78 int type = data.readByte();
79 data.readShortInt();
80 this.parentPageId = data.readInt();
81 onlyPosition = (type & Page.FLAG_LAST) == 0;
82 int indexId = data.readVarInt();
83 if (indexId != index.getId()) {
84 throw DbException.get(ErrorCode.FILE_CORRUPTED_1,
85 "page:" + getPos() + " expected index:" + index.getId() +
86 "got:" + indexId);
87 }
88 entryCount = data.readShortInt();
89 offsets = new int[entryCount];
90 rows = new SearchRow[entryCount];
91 for (int i = 0; i < entryCount; i++) {
92 offsets[i] = data.readShortInt();
93 }
94 start = data.length();
95 written = true;
96 writtenData = true;
97 }
98
99 int addRowTry(SearchRow row) {
100 int x = addRow(row, true);
101 memoryChange();
102 return x;
103 }
104
105 private int addRow(SearchRow row, boolean tryOnly) {
106 int rowLength = index.getRowSize(data, row, onlyPosition);
107 int pageSize = index.getPageStore().getPageSize();
108 int last = entryCount == 0 ? pageSize : offsets[entryCount - 1];
109 if (last - rowLength < start + OFFSET_LENGTH) {
110 if (tryOnly && entryCount > 1) {
111 int x = find(row, false, true, true);
112 if (entryCount < 5) {
113 // required, otherwise the index doesn't work correctly
114 return entryCount / 2;
115 }
116 // split near the insertion point to better fill pages
117 // split in half would be:
118 // return entryCount / 2;
119 int third = entryCount / 3;
120 return x < third ? third : x >= 2 * third ? 2 * third : x;
121 }
122 readAllRows();
123 writtenData = false;
124 onlyPosition = true;
125 // change the offsets (now storing only positions)
126 int o = pageSize;
127 for (int i = 0; i < entryCount; i++) {
128 o -= index.getRowSize(data, getRow(i), true);
129 offsets[i] = o;
130 }
131 last = entryCount == 0 ? pageSize : offsets[entryCount - 1];
132 rowLength = index.getRowSize(data, row, true);
133 if (SysProperties.CHECK && last - rowLength < start + OFFSET_LENGTH) {
134 throw DbException.throwInternalError();
135 }
136 }
137 index.getPageStore().logUndo(this, data);
138 if (!optimizeUpdate) {
139 readAllRows();
140 }
141 changeCount = index.getPageStore().getChangeCount();
142 written = false;
143 int x;
144 if (entryCount == 0) {
145 x = 0;
146 } else {
147 x = find(row, false, true, true);
148 }
149 start += OFFSET_LENGTH;
150 int offset = (x == 0 ? pageSize : offsets[x - 1]) - rowLength;
151 if (optimizeUpdate && writtenData) {
152 if (entryCount > 0) {
153 byte[] d = data.getBytes();
154 int dataStart = offsets[entryCount - 1];
155 int dataEnd = offset;
156 System.arraycopy(d, dataStart, d, dataStart - rowLength, dataEnd - dataStart + rowLength);
157 }
158 index.writeRow(data, offset, row, onlyPosition);
159 }
160 offsets = insert(offsets, entryCount, x, offset);
161 add(offsets, x + 1, entryCount + 1, -rowLength);
162 rows = insert(rows, entryCount, x, row);
163 entryCount++;
164 index.getPageStore().update(this);
165 return -1;
166 }
167
168 private void removeRow(int at) {
169 if (!optimizeUpdate) {
170 readAllRows();
171 }
172 index.getPageStore().logUndo(this, data);
173 entryCount--;
174 written = false;
175 changeCount = index.getPageStore().getChangeCount();
176 if (entryCount <= 0) {
177 DbException.throwInternalError();
178 }
179 int startNext = at > 0 ? offsets[at - 1] : index.getPageStore().getPageSize();
180 int rowLength = startNext - offsets[at];
181 start -= OFFSET_LENGTH;
182
183 if (optimizeUpdate) {
184 if (writtenData) {
185 byte[] d = data.getBytes();
186 int dataStart = offsets[entryCount];
187 System.arraycopy(d, dataStart, d, dataStart + rowLength, offsets[at] - dataStart);
188 Arrays.fill(d, dataStart, dataStart + rowLength, (byte) 0);
189 }
190 }
191
192 offsets = remove(offsets, entryCount + 1, at);
193 add(offsets, at, entryCount, rowLength);
194 rows = remove(rows, entryCount + 1, at);
195 }
196
197 int getEntryCount() {
198 return entryCount;
199 }
200
201 PageBtree split(int splitPoint) {
202 int newPageId = index.getPageStore().allocatePage();
203 PageBtreeLeaf p2 = PageBtreeLeaf.create(index, newPageId, parentPageId);
204 for (int i = splitPoint; i < entryCount;) {
205 p2.addRow(getRow(splitPoint), false);
206 removeRow(splitPoint);
207 }
208 memoryChange();
209 p2.memoryChange();
210 return p2;
211 }
212
213 PageBtreeLeaf getFirstLeaf() {
214 return this;
215 }
216
217 PageBtreeLeaf getLastLeaf() {
218 return this;
219 }
220
221 SearchRow remove(SearchRow row) {
222 int at = find(row, false, false, true);
223 SearchRow delete = getRow(at);
224 if (index.compareRows(row, delete) != 0 || delete.getKey() != row.getKey()) {
225 throw DbException.get(ErrorCode.ROW_NOT_FOUND_WHEN_DELETING_1, index.getSQL() + ": " + row);
226 }
227 index.getPageStore().logUndo(this, data);
228 if (entryCount == 1) {
229 // the page is now empty
230 return row;
231 }
232 removeRow(at);
233 memoryChange();
234 index.getPageStore().update(this);
235 if (at == entryCount) {
236 // the last row changed
237 return getRow(at - 1);
238 }
239 // the last row didn't change
240 return null;
241 }
242
243 void freeRecursive() {
244 index.getPageStore().logUndo(this, data);
245 index.getPageStore().free(getPos());
246 }
247
248 int getRowCount() {
249 return entryCount;
250 }
251
252 void setRowCountStored(int rowCount) {
253 // ignore
254 }
255
256 public void write() {
257 writeData();
258 index.getPageStore().writePage(getPos(), data);
259 }
260
261 private void writeHead() {
262 data.reset();
263 data.writeByte((byte) (Page.TYPE_BTREE_LEAF | (onlyPosition ? 0 : Page.FLAG_LAST)));
264 data.writeShortInt(0);
265 data.writeInt(parentPageId);
266 data.writeVarInt(index.getId());
267 data.writeShortInt(entryCount);
268 }
269
270 private void writeData() {
271 if (written) {
272 return;
273 }
274 if (!optimizeUpdate) {
275 readAllRows();
276 }
277 writeHead();
278 for (int i = 0; i < entryCount; i++) {
279 data.writeShortInt(offsets[i]);
280 }
281 if (!writtenData || !optimizeUpdate) {
282 for (int i = 0; i < entryCount; i++) {
283 index.writeRow(data, offsets[i], rows[i], onlyPosition);
284 }
285 writtenData = true;
286 }
287 written = true;
288 memoryChange();
289 }
290
291 void find(PageBtreeCursor cursor, SearchRow first, boolean bigger) {
292 int i = find(first, bigger, false, false);
293 if (i > entryCount) {
294 if (parentPageId == PageBtree.ROOT) {
295 return;
296 }
297 PageBtreeNode next = (PageBtreeNode) index.getPage(parentPageId);
298 next.find(cursor, first, bigger);
299 return;
300 }
301 cursor.setCurrent(this, i);
302 }
303
304 void last(PageBtreeCursor cursor) {
305 cursor.setCurrent(this, entryCount - 1);
306 }
307
308 void remapChildren() {
309 // nothing to do
310 }
311
312 /**
313 * Set the cursor to the first row of the next page.
314 *
315 * @param cursor the cursor
316 */
317 void nextPage(PageBtreeCursor cursor) {
318 if (parentPageId == PageBtree.ROOT) {
319 cursor.setCurrent(null, 0);
320 return;
321 }
322 PageBtreeNode next = (PageBtreeNode) index.getPage(parentPageId);
323 next.nextPage(cursor, getPos());
324 }
325
326 /**
327 * Set the cursor to the last row of the previous page.
328 *
329 * @param cursor the cursor
330 */
331 void previousPage(PageBtreeCursor cursor) {
332 if (parentPageId == PageBtree.ROOT) {
333 cursor.setCurrent(null, 0);
334 return;
335 }
336 PageBtreeNode next = (PageBtreeNode) index.getPage(parentPageId);
337 next.previousPage(cursor, getPos());
338 }
339
340 public String toString() {
341 return "page[" + getPos() + "] b-tree leaf table:" + index.getId() + " entries:" + entryCount;
342 }
343
344 public void moveTo(Session session, int newPos) {
345 PageStore store = index.getPageStore();
346 readAllRows();
347 PageBtreeLeaf p2 = PageBtreeLeaf.create(index, newPos, parentPageId);
348 store.logUndo(this, data);
349 store.logUndo(p2, null);
350 p2.rows = rows;
351 p2.entryCount = entryCount;
352 p2.offsets = offsets;
353 p2.onlyPosition = onlyPosition;
354 p2.parentPageId = parentPageId;
355 p2.start = start;
356 store.update(p2);
357 if (parentPageId == ROOT) {
358 index.setRootPageId(session, newPos);
359 } else {
360 PageBtreeNode p = (PageBtreeNode) store.getPage(parentPageId);
361 p.moveChild(getPos(), newPos);
362 }
363 store.free(getPos());
364 }
365
366 protected void memoryChange() {
367 if (!PageBtreeIndex.isMemoryChangeRequired()) {
368 return;
369 }
370 int memory = Constants.MEMORY_PAGE_BTREE + index.getPageStore().getPageSize();
371 if (rows != null) {
372 memory += getEntryCount() * (4 + Constants.MEMORY_POINTER);
373 for (int i = 0; i < entryCount; i++) {
374 SearchRow r = rows[i];
375 if (r != null) {
376 memory += r.getMemory();
377 }
378 }
379 }
380 index.memoryChange(memory >> 2);
381 }
382
383 }
384