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