|
1
5 package org.h2.index;
6
7 import java.sql.SQLException  ;
8
9 import org.h2.engine.Constants;
10 import org.h2.engine.Session;
11 import org.h2.message.Message;
12 import org.h2.result.Row;
13 import org.h2.result.SearchRow;
14 import org.h2.store.DataPage;
15 import org.h2.store.DiskFile;
16 import org.h2.table.Column;
17 import org.h2.util.ObjectArray;
18 import org.h2.value.Value;
19
20
26 public class BtreeLeaf extends BtreePage {
27
28 private boolean writePos;
29 private int cachedRealByteCount;
30
31 BtreeLeaf(BtreeIndex index, DataPage s) throws SQLException {
32 super(index);
33 writePos = s.readByte() == 'P';
34 if(writePos) {
35 int size = s.readInt();
36 pageData = new ObjectArray(size);
38 for(int i=0; i<size; i++) {
39 Row r = index.getRow(s.readInt());
40 pageData.add(r);
41 }
42 } else {
43 pageData = index.readRowArray(s);
44 }
45 }
46
47 BtreeLeaf(BtreeIndex index, ObjectArray pageData) {
48 super(index);
49 this.pageData = pageData;
50 }
51
52 public int add(Row newRow, Session session) throws SQLException {
53 int l = 0, r = pageData.size();
54 while (l < r) {
55 int i = (l + r) >>> 1;
56 SearchRow row = (SearchRow) pageData.get(i);
57 int comp = index.compareRows(row, newRow);
58 if (comp == 0) {
59 if(index.indexType.isUnique()) {
60 if(!index.isNull(newRow)) {
61 throw index.getDuplicateKeyException();
62 }
63 }
64 comp = index.compareKeys(row, newRow);
65 }
66 if(comp > 0) {
67 r = i;
68 } else {
69 l = i + 1;
70 }
71 }
72 index.deletePage(session, this);
73 int at = l;
74 pageData.add(at, newRow);
75 updateRealByteCount(true, newRow);
76 int splitPoint = getSplitPoint();
77 if(splitPoint == 0) {
78 index.updatePage(session, this);
79 }
80 return splitPoint;
81 }
82
83 public SearchRow remove(Session session, Row oldRow, int level) throws SQLException {
84 int l = 0, r = pageData.size();
85 if (r == 0) {
86 if(!Constants.ALLOW_EMTPY_BTREE_PAGES && !root) {
87 throw Message.getInternalError("Empty btree page");
88 }
89 }
90 while (l < r) {
91 int i = (l + r) >>> 1;
92 SearchRow row = (SearchRow) pageData.get(i);
93 if(Constants.CHECK && row == null) {
94 throw Message.getInternalError("btree currupted");
95 }
96 int comp = index.compareRows(row, oldRow);
97 if (comp == 0) {
98 comp = index.compareKeys(row, oldRow);
99 }
100 if(comp == 0) {
101 index.deletePage(session, this);
102 if(pageData.size()==1 && !root) {
103 return oldRow;
105 }
106 pageData.remove(i);
107 updateRealByteCount(false, row);
108 index.updatePage(session, this);
109 if(i > 0) {
110 return null;
112 } else {
113 if(pageData.size() == 0) {
114 return null;
115 } else {
116 return getData(0);
117 }
118 }
119 }
120 if(comp > 0) {
121 r = i;
122 } else {
123 l = i + 1;
124 }
125 }
126 throw Message.getSQLException(Message.ROW_NOT_FOUND_WHEN_DELETING_1, index.getSQL());
127 }
128
129 public BtreePage split(Session session, int splitPoint) throws SQLException {
130 ObjectArray data = new ObjectArray();
131 int max = pageData.size();
132 for (int i = splitPoint; i < max; i++) {
133 data.add(getData(splitPoint));
134 pageData.remove(splitPoint);
135 }
136 cachedRealByteCount = 0;
137 BtreeLeaf n2 = new BtreeLeaf(index, data);
138 index.updatePage(session, this);
139 index.addPage(session, n2);
140 return n2;
141 }
142
143 public boolean findFirst(BtreeCursor cursor, SearchRow compare) throws SQLException {
144 int l = 0, r = pageData.size();
145 if (r == 0 && !Constants.ALLOW_EMTPY_BTREE_PAGES && !root) {
146 throw Message.getInternalError("Empty btree page");
147 }
148 while (l < r) {
149 int i = (l + r) >>> 1;
150 SearchRow row = (SearchRow) pageData.get(i);
151 int comp = index.compareRows(row, compare);
152 if(comp >= 0) {
153 r = i;
154 } else {
155 l = i + 1;
156 }
157 }
158 if(l>=pageData.size()) {
159 return false;
160 }
161 cursor.push(this, l);
162 SearchRow row = (SearchRow) pageData.get(l);
163 cursor.setCurrentRow(row.getPos());
164 return true;
165 }
166
167 public void next(BtreeCursor cursor, int i) throws SQLException {
168 i++;
169 if (i < pageData.size()) {
170 SearchRow r = (SearchRow) pageData.get(i);
171 cursor.setCurrentRow(r.getPos());
172 cursor.setStackPosition(i);
173 return;
174 }
175 cursor.pop();
176 nextUpper(cursor);
177 }
178
179 public void first(BtreeCursor cursor) throws SQLException {
180 if (pageData.size() == 0) {
181 if (!Constants.ALLOW_EMTPY_BTREE_PAGES && !root) {
182 throw Message.getInternalError("Empty btree page");
183 }
184 nextUpper(cursor);
185 return;
186 }
187 cursor.push(this, 0);
188 SearchRow row = (SearchRow) pageData.get(0);
189 cursor.setCurrentRow(row.getPos());
190 }
191
192 private void nextUpper(BtreeCursor cursor) throws SQLException {
193 BtreePosition upper = cursor.pop();
194 if (upper == null) {
195 cursor.setCurrentRow(Cursor.POS_NO_ROW);
196 } else {
197 cursor.push(upper.page, upper.position);
198 upper.page.next(cursor, upper.position);
199 }
200 }
201
202 public void prepareWrite() throws SQLException {
203 if(getRealByteCount() >= DiskFile.BLOCK_SIZE*BLOCKS_PER_PAGE) {
204 writePos = true;
205 } else {
206 writePos = false;
207 }
208 }
209
210 public void write(DataPage buff) throws SQLException {
211 buff.writeByte((byte)'L');
212 int len = pageData.size();
213 if(writePos) {
214 buff.writeByte((byte)'P');
215 } else {
216 buff.writeByte((byte)'D');
217 }
218 buff.writeInt(len);
219 Column[] columns = index.getColumns();
220 for (int i = 0; i < len; i++) {
221 SearchRow row = (SearchRow) pageData.get(i);
222 buff.writeInt(row.getPos());
223 if(!writePos) {
224 for (int j = 0; j < columns.length; j++) {
225 Value v = row.getValue(columns[j].getColumnId());
226 buff.writeValue(v);
227 }
228 }
229 }
230 }
231
232 private void updateRealByteCount(boolean add, SearchRow row) throws SQLException {
233 if(cachedRealByteCount == 0) {
234 return;
235 }
236 DataPage dummy = index.getDatabase().getDataPage();
237 cachedRealByteCount += getRowSize(dummy, row) + dummy.getIntLen();
238 if(cachedRealByteCount+index.getRecordOverhead() >= DiskFile.BLOCK_SIZE*BLOCKS_PER_PAGE) {
239 cachedRealByteCount = 0;
240 }
241 }
242
243 public int getRealByteCount() throws SQLException {
244 if(cachedRealByteCount > 0) {
245 return cachedRealByteCount;
246 }
247 DataPage dummy = index.getDatabase().getDataPage();
248 int len = pageData.size();
249 int size = 2 + dummy.getIntLen() * (len+1);
250 for (int i = 0; i < len; i++) {
251 SearchRow row = (SearchRow) pageData.get(i);
252 size += getRowSize(dummy, row);
253 }
254 size += index.getRecordOverhead();
255 cachedRealByteCount = size;
256 return size;
257 }
258
259 SearchRow getLast() throws SQLException {
260 if(pageData.size()==0) {
261 if(!Constants.ALLOW_EMTPY_BTREE_PAGES && !root) {
262 throw Message.getInternalError("Empty btree page");
263 }
264 return null;
265 }
266 return (SearchRow)pageData.get(pageData.size()-1);
267 }
268
269 SearchRow getFirst() throws SQLException {
270 if(pageData.size()==0) {
271 if(!Constants.ALLOW_EMTPY_BTREE_PAGES && !root) {
272 throw Message.getInternalError("Empty btree page");
273 }
274 return null;
275 }
276 return (SearchRow)pageData.get(0);
277 }
278
279 public String print(String indent) throws SQLException {
280 System.out.println(indent + "leaf:");
281 for(int i=0; i<pageData.size(); i++) {
282 System.out.println(indent + " " + getData(i).getValue(1).getString().substring(4150));
283 }
284 return getData(0).getValue(1).getString().substring(4150);
285 }
286
287 }
288 |
Popular Tags |
Java API By Example, From Geeks To Geeks.