File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\index\PageBtree.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 org.h2.result.SearchRow;
10 import org.h2.store.Data;
11 import org.h2.store.Page;
12
13 /**
14 * A page that contains index data.
15 */
16 public abstract class PageBtree extends Page {
17
18 /**
19 * This is a root page.
20 */
21 static final int ROOT = 0;
22
23 /**
24 * Indicator that the row count is not known.
25 */
26 static final int UNKNOWN_ROWCOUNT = -1;
27
28 /**
29 * The index.
30 */
31 protected final PageBtreeIndex index;
32
33 /**
34 * The page number of the parent.
35 */
36 protected int parentPageId;
37
38 /**
39 * The data page.
40 */
41 protected final Data data;
42
43 /**
44 * The row offsets.
45 */
46 protected int[] offsets;
47
48 /**
49 * The number of entries.
50 */
51 protected int entryCount;
52
53 /**
54 * The index data
55 */
56 protected SearchRow[] rows;
57
58 /**
59 * The start of the data area.
60 */
61 protected int start;
62
63 /**
64 * If only the position of the row is stored in the page
65 */
66 protected boolean onlyPosition;
67
68 /**
69 * Whether the data page is up-to-date.
70 */
71 protected boolean written;
72
73 /**
74 * The estimated memory used by this object.
75 */
76 private final int memoryEstimated;
77
78 PageBtree(PageBtreeIndex index, int pageId, Data data) {
79 this.index = index;
80 this.data = data;
81 setPos(pageId);
82 memoryEstimated = index.getMemoryPerPage();
83 }
84
85 /**
86 * Get the real row count. If required, this will read all child pages.
87 *
88 * @return the row count
89 */
90 abstract int getRowCount();
91
92 /**
93 * Set the stored row count. This will write the page.
94 *
95 * @param rowCount the stored row count
96 */
97 abstract void setRowCountStored(int rowCount);
98
99 /**
100 * Find an entry.
101 *
102 * @param compare the row
103 * @param bigger if looking for a larger row
104 * @param add if the row should be added (check for duplicate keys)
105 * @param compareKeys compare the row keys as well
106 * @return the index of the found row
107 */
108 int find(SearchRow compare, boolean bigger, boolean add, boolean compareKeys) {
109 if (compare == null) {
110 return 0;
111 }
112 int l = 0, r = entryCount;
113 int comp = 1;
114 while (l < r) {
115 int i = (l + r) >>> 1;
116 SearchRow row = getRow(i);
117 comp = index.compareRows(row, compare);
118 if (comp == 0) {
119 if (add && index.indexType.isUnique()) {
120 if (!index.containsNullAndAllowMultipleNull(compare)) {
121 throw index.getDuplicateKeyException();
122 }
123 }
124 if (compareKeys) {
125 comp = index.compareKeys(row, compare);
126 if (comp == 0) {
127 return i;
128 }
129 }
130 }
131 if (comp > 0 || (!bigger && comp == 0)) {
132 r = i;
133 } else {
134 l = i + 1;
135 }
136 }
137 return l;
138 }
139
140 /**
141 * Add a row if possible. If it is possible this method returns -1, otherwise
142 * the split point. It is always possible to add one row.
143 *
144 * @param row the row to add
145 * @return the split point of this page, or -1 if no split is required
146 */
147 abstract int addRowTry(SearchRow row);
148
149 /**
150 * Find the first row.
151 *
152 * @param cursor the cursor
153 * @param first the row to find
154 * @param bigger if the row should be bigger
155 */
156 abstract void find(PageBtreeCursor cursor, SearchRow first, boolean bigger);
157
158 /**
159 * Find the last row.
160 *
161 * @param cursor the cursor
162 */
163 abstract void last(PageBtreeCursor cursor);
164
165 /**
166 * Get the row at this position.
167 *
168 * @param at the index
169 * @return the row
170 */
171 SearchRow getRow(int at) {
172 SearchRow row = rows[at];
173 if (row == null) {
174 row = index.readRow(data, offsets[at], onlyPosition, true);
175 memoryChange();
176 rows[at] = row;
177 } else if (!index.hasData(row)) {
178 row = index.readRow(row.getKey());
179 memoryChange();
180 rows[at] = row;
181 }
182 return row;
183 }
184
185 /**
186 * The memory usage of this page was changed. Propagate the change if
187 * needed.
188 */
189 protected void memoryChange() {
190 // nothing to do
191 }
192
193 /**
194 * Split the index page at the given point.
195 *
196 * @param splitPoint the index where to split
197 * @return the new page that contains about half the entries
198 */
199 abstract PageBtree split(int splitPoint);
200
201 /**
202 * Change the page id.
203 *
204 * @param id the new page id
205 */
206 void setPageId(int id) {
207 changeCount = index.getPageStore().getChangeCount();
208 written = false;
209 index.getPageStore().removeRecord(getPos());
210 setPos(id);
211 index.getPageStore().logUndo(this, null);
212 remapChildren();
213 }
214
215 /**
216 * Get the first child leaf page of a page.
217 *
218 * @return the page
219 */
220 abstract PageBtreeLeaf getFirstLeaf();
221
222 /**
223 * Get the first child leaf page of a page.
224 *
225 * @return the page
226 */
227 abstract PageBtreeLeaf getLastLeaf();
228
229 /**
230 * Change the parent page id.
231 *
232 * @param id the new parent page id
233 */
234 void setParentPageId(int id) {
235 index.getPageStore().logUndo(this, data);
236 changeCount = index.getPageStore().getChangeCount();
237 written = false;
238 parentPageId = id;
239 }
240
241 /**
242 * Update the parent id of all children.
243 */
244 abstract void remapChildren();
245
246 /**
247 * Remove a row.
248 *
249 * @param row the row to remove
250 * @return null if the last row didn't change,
251 * the deleted row if the page is now empty,
252 * otherwise the new last row of this page
253 */
254 abstract SearchRow remove(SearchRow row);
255
256 /**
257 * Free this page and all child pages.
258 */
259 abstract void freeRecursive();
260
261 /**
262 * Ensure all rows are read in memory.
263 */
264 protected void readAllRows() {
265 for (int i = 0; i < entryCount; i++) {
266 SearchRow row = rows[i];
267 if (row == null) {
268 row = index.readRow(data, offsets[i], onlyPosition, false);
269 rows[i] = row;
270 }
271 }
272 }
273
274 /**
275 * Get the estimated memory size.
276 *
277 * @return number of double words (4 bytes)
278 */
279 public int getMemory() {
280 // need to always return the same value for the same object (otherwise
281 // the cache size would change after adding and then removing the same
282 // page from the cache) but index.getMemoryPerPage() can adopt according
283 // to how much memory a row needs on average
284 return memoryEstimated;
285 }
286
287 public boolean canRemove() {
288 if (changeCount >= index.getPageStore().getChangeCount()) {
289 return false;
290 }
291 return true;
292 }
293
294 }
295