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.store; |
7 | |
8 | import java.lang.reflect.Array; |
9 | import org.h2.engine.Session; |
10 | import org.h2.util.CacheObject; |
11 | |
12 | /** |
13 | * A page. Format: |
14 | * <ul><li>0-3: parent page id (0 for root) |
15 | * </li><li>4-4: page type |
16 | * </li><li>page-type specific data |
17 | * </li></ul> |
18 | */ |
19 | public abstract class Page extends CacheObject { |
20 | |
21 | /** |
22 | * This is the last page of a chain. |
23 | */ |
24 | public static final int FLAG_LAST = 16; |
25 | |
26 | /** |
27 | * An empty page. |
28 | */ |
29 | public static final int TYPE_EMPTY = 0; |
30 | |
31 | /** |
32 | * A data leaf page (without overflow: + FLAG_LAST). |
33 | */ |
34 | public static final int TYPE_DATA_LEAF = 1; |
35 | |
36 | /** |
37 | * A data node page (never has overflow pages). |
38 | */ |
39 | public static final int TYPE_DATA_NODE = 2; |
40 | |
41 | /** |
42 | * A data overflow page (the last page: + FLAG_LAST). |
43 | */ |
44 | public static final int TYPE_DATA_OVERFLOW = 3; |
45 | |
46 | /** |
47 | * A b-tree leaf page (without overflow: + FLAG_LAST). |
48 | */ |
49 | public static final int TYPE_BTREE_LEAF = 4; |
50 | |
51 | /** |
52 | * A b-tree node page (never has overflow pages). |
53 | */ |
54 | public static final int TYPE_BTREE_NODE = 5; |
55 | |
56 | /** |
57 | * A page containing a list of free pages (the last page: + FLAG_LAST). |
58 | */ |
59 | public static final int TYPE_FREE_LIST = 6; |
60 | |
61 | /** |
62 | * A stream trunk page. |
63 | */ |
64 | public static final int TYPE_STREAM_TRUNK = 7; |
65 | |
66 | /** |
67 | * A stream data page. |
68 | */ |
69 | public static final int TYPE_STREAM_DATA = 8; |
70 | |
71 | private static final int COPY_THRESHOLD = 4; |
72 | |
73 | /** |
74 | * When this page was changed the last time. |
75 | */ |
76 | protected long changeCount; |
77 | |
78 | /** |
79 | * Copy the data to a new location, change the parent to point to the new |
80 | * location, and free up the current page. |
81 | * |
82 | * @param session the session |
83 | * @param newPos the new position |
84 | */ |
85 | public abstract void moveTo(Session session, int newPos); |
86 | |
87 | /** |
88 | * Write the page. |
89 | */ |
90 | public abstract void write(); |
91 | |
92 | /** |
93 | * Insert a value in an array. A new array is created if required. |
94 | * |
95 | * @param old the old array |
96 | * @param oldSize the old size |
97 | * @param pos the position |
98 | * @param x the value to insert |
99 | * @return the (new) array |
100 | */ |
101 | @SuppressWarnings("unchecked") |
102 | public static <T> T[] insert(T[] old, int oldSize, int pos, T x) { |
103 | T[] result; |
104 | if (old.length > oldSize) { |
105 | result = old; |
106 | } else { |
107 | // according to a test, this is as fast as "new Row[..]" |
108 | result = (T[]) Array.newInstance( |
109 | old.getClass().getComponentType(), oldSize + 1 + COPY_THRESHOLD); |
110 | if (pos > 0) { |
111 | System.arraycopy(old, 0, result, 0, pos); |
112 | } |
113 | } |
114 | if (oldSize - pos > 0) { |
115 | System.arraycopy(old, pos, result, pos + 1, oldSize - pos); |
116 | } |
117 | result[pos] = x; |
118 | return result; |
119 | } |
120 | |
121 | /** |
122 | * Delete a value in an array. A new array is created if required. |
123 | * |
124 | * @param old the old array |
125 | * @param oldSize the old size |
126 | * @param pos the position |
127 | * @return the (new) array |
128 | */ |
129 | @SuppressWarnings("unchecked") |
130 | public |
131 | static <T> T[] remove(T[] old, int oldSize, int pos) { |
132 | T[] result; |
133 | if (old.length - oldSize < COPY_THRESHOLD) { |
134 | result = old; |
135 | } else { |
136 | // according to a test, this is as fast as "new Row[..]" |
137 | result = (T[]) Array.newInstance( |
138 | old.getClass().getComponentType(), oldSize - 1); |
139 | System.arraycopy(old, 0, result, 0, Math.min(oldSize - 1, pos)); |
140 | } |
141 | if (pos < oldSize) { |
142 | System.arraycopy(old, pos + 1, result, pos, oldSize - pos - 1); |
143 | } |
144 | return result; |
145 | } |
146 | |
147 | /** |
148 | * Insert a value in an array. A new array is created if required. |
149 | * |
150 | * @param old the old array |
151 | * @param oldSize the old size |
152 | * @param pos the position |
153 | * @param x the value to insert |
154 | * @return the (new) array |
155 | */ |
156 | protected static long[] insert(long[] old, int oldSize, int pos, long x) { |
157 | long[] result; |
158 | if (old != null && old.length > oldSize) { |
159 | result = old; |
160 | } else { |
161 | result = new long[oldSize + 1 + COPY_THRESHOLD]; |
162 | if (pos > 0) { |
163 | System.arraycopy(old, 0, result, 0, pos); |
164 | } |
165 | } |
166 | if (old != null && oldSize - pos > 0) { |
167 | System.arraycopy(old, pos, result, pos + 1, oldSize - pos); |
168 | } |
169 | result[pos] = x; |
170 | return result; |
171 | } |
172 | |
173 | /** |
174 | * Delete a value in an array. A new array is created if required. |
175 | * |
176 | * @param old the old array |
177 | * @param oldSize the old size |
178 | * @param pos the position |
179 | * @return the (new) array |
180 | */ |
181 | protected static long[] remove(long[] old, int oldSize, int pos) { |
182 | long[] result; |
183 | if (old.length - oldSize < COPY_THRESHOLD) { |
184 | result = old; |
185 | } else { |
186 | result = new long[oldSize - 1]; |
187 | System.arraycopy(old, 0, result, 0, pos); |
188 | } |
189 | System.arraycopy(old, pos + 1, result, pos, oldSize - pos - 1); |
190 | return result; |
191 | } |
192 | |
193 | /** |
194 | * Insert a value in an array. A new array is created if required. |
195 | * |
196 | * @param old the old array |
197 | * @param oldSize the old size |
198 | * @param pos the position |
199 | * @param x the value to insert |
200 | * @return the (new) array |
201 | */ |
202 | protected static int[] insert(int[] old, int oldSize, int pos, int x) { |
203 | int[] result; |
204 | if (old != null && old.length > oldSize) { |
205 | result = old; |
206 | } else { |
207 | result = new int[oldSize + 1 + COPY_THRESHOLD]; |
208 | if (pos > 0 && old != null) { |
209 | System.arraycopy(old, 0, result, 0, pos); |
210 | } |
211 | } |
212 | if (old != null && oldSize - pos > 0) { |
213 | System.arraycopy(old, pos, result, pos + 1, oldSize - pos); |
214 | } |
215 | result[pos] = x; |
216 | return result; |
217 | } |
218 | |
219 | /** |
220 | * Delete a value in an array. A new array is created if required. |
221 | * |
222 | * @param old the old array |
223 | * @param oldSize the old size |
224 | * @param pos the position |
225 | * @return the (new) array |
226 | */ |
227 | protected static int[] remove(int[] old, int oldSize, int pos) { |
228 | int[] result; |
229 | if (old.length - oldSize < COPY_THRESHOLD) { |
230 | result = old; |
231 | } else { |
232 | result = new int[oldSize - 1]; |
233 | System.arraycopy(old, 0, result, 0, Math.min(oldSize - 1, pos)); |
234 | } |
235 | if (pos < oldSize) { |
236 | System.arraycopy(old, pos + 1, result, pos, oldSize - pos - 1); |
237 | } |
238 | return result; |
239 | } |
240 | |
241 | /** |
242 | * Add a value to a subset of the array. |
243 | * |
244 | * @param array the array |
245 | * @param from the index of the first element (including) |
246 | * @param to the index of the last element (excluding) |
247 | * @param x the value to add |
248 | */ |
249 | protected static void add(int[] array, int from, int to, int x) { |
250 | for (int i = from; i < to; i++) { |
251 | array[i] += x; |
252 | } |
253 | } |
254 | |
255 | /** |
256 | * If this page can be moved. Transaction log and free-list pages can not. |
257 | * |
258 | * @return true if moving is allowed |
259 | */ |
260 | public boolean canMove() { |
261 | return true; |
262 | } |
263 | |
264 | } |