001: /*
002: * Copyright 2004-2008 H2 Group. Licensed under the H2 License, Version 1.0
003: * (http://h2database.com/html/license.html).
004: * Initial Developer: H2 Group
005: */
006: package org.h2.index;
007:
008: import java.sql.SQLException;
009:
010: import org.h2.constant.ErrorCode;
011: import org.h2.constant.SysProperties;
012: import org.h2.engine.Constants;
013: import org.h2.engine.Session;
014: import org.h2.message.Message;
015: import org.h2.result.Row;
016: import org.h2.result.SearchRow;
017: import org.h2.store.DataPage;
018: import org.h2.store.DiskFile;
019: import org.h2.table.Column;
020: import org.h2.util.ObjectArray;
021: import org.h2.value.Value;
022:
023: /**
024: * An outer page of a btree index.
025: *
026: * Page format:
027: * <pre>
028: * L { P(pointers) | D(data) } data.len { data[0].pos [data[0]], ... }
029: * </pre>
030: */
031: public class BtreeLeaf extends BtreePage {
032:
033: private boolean writePos;
034: private int cachedRealByteCount;
035:
036: BtreeLeaf(BtreeIndex index, Session session, DataPage s)
037: throws SQLException {
038: super (index);
039: writePos = s.readByte() == 'P';
040: if (writePos) {
041: int size = s.readInt();
042: // should be 1, but may not be 1
043: pageData = new ObjectArray(size);
044: for (int i = 0; i < size; i++) {
045: Row r = index.getRow(session, s.readInt());
046: pageData.add(r);
047: }
048: } else {
049: pageData = index.readRowArray(s);
050: }
051: }
052:
053: BtreeLeaf(BtreeIndex index, ObjectArray pageData) {
054: super (index);
055: this .pageData = pageData;
056: }
057:
058: public int add(Row newRow, Session session) throws SQLException {
059: int l = 0, r = pageData.size();
060: while (l < r) {
061: int i = (l + r) >>> 1;
062: SearchRow row = (SearchRow) pageData.get(i);
063: int comp = index.compareRows(row, newRow);
064: if (comp == 0) {
065: if (index.indexType.isUnique()) {
066: if (!index.isNull(newRow)) {
067: throw index.getDuplicateKeyException();
068: }
069: }
070: comp = index.compareKeys(row, newRow);
071: }
072: if (comp > 0) {
073: r = i;
074: } else {
075: l = i + 1;
076: }
077: }
078: index.deletePage(session, this );
079: int at = l;
080: // safe memory
081: SearchRow row = index.getSearchRow(newRow);
082: pageData.add(at, row);
083: updateRealByteCount(true, newRow);
084: int splitPoint = getSplitPoint();
085: if (splitPoint == 0) {
086: index.updatePage(session, this );
087: }
088: return splitPoint;
089: }
090:
091: public SearchRow remove(Session session, Row oldRow)
092: throws SQLException {
093: int l = 0, r = pageData.size();
094: if (r == 0) {
095: if (!Constants.ALLOW_EMPTY_BTREE_PAGES && !root) {
096: throw Message.getInternalError("Empty btree page");
097: }
098: }
099: while (l < r) {
100: int i = (l + r) >>> 1;
101: SearchRow row = (SearchRow) pageData.get(i);
102: if (SysProperties.CHECK && row == null) {
103: throw Message.getInternalError("btree corrupt");
104: }
105: int comp = index.compareRows(row, oldRow);
106: if (comp == 0) {
107: comp = index.compareKeys(row, oldRow);
108: }
109: if (comp == 0) {
110: index.deletePage(session, this );
111: if (pageData.size() == 1 && !root) {
112: // the last row has been deleted
113: return oldRow;
114: }
115: pageData.remove(i);
116: updateRealByteCount(false, row);
117: index.updatePage(session, this );
118: if (i > 0) {
119: // the first row didn't change
120: return null;
121: } else {
122: if (pageData.size() == 0) {
123: return null;
124: } else {
125: return getData(0);
126: }
127: }
128: }
129: if (comp > 0) {
130: r = i;
131: } else {
132: l = i + 1;
133: }
134: }
135: throw Message
136: .getSQLException(
137: ErrorCode.ROW_NOT_FOUND_WHEN_DELETING_1, index
138: .getSQL());
139: }
140:
141: public BtreePage split(Session session, int splitPoint)
142: throws SQLException {
143: ObjectArray data = new ObjectArray();
144: int max = pageData.size();
145: for (int i = splitPoint; i < max; i++) {
146: data.add(getData(splitPoint));
147: pageData.remove(splitPoint);
148: }
149: cachedRealByteCount = 0;
150: BtreeLeaf n2 = new BtreeLeaf(index, data);
151: index.updatePage(session, this );
152: index.addPage(session, n2);
153: return n2;
154: }
155:
156: public boolean findFirst(BtreeCursor cursor, SearchRow compare,
157: boolean bigger) throws SQLException {
158: int l = 0, r = pageData.size();
159: if (r == 0 && !Constants.ALLOW_EMPTY_BTREE_PAGES && !root) {
160: throw Message.getInternalError("Empty btree page");
161: }
162: while (l < r) {
163: int i = (l + r) >>> 1;
164: SearchRow row = (SearchRow) pageData.get(i);
165: int comp = index.compareRows(row, compare);
166: if (comp > 0 || (!bigger && comp == 0)) {
167: r = i;
168: } else {
169: l = i + 1;
170: }
171: }
172: if (l >= pageData.size()) {
173: return false;
174: }
175: cursor.push(this , l);
176: SearchRow row = (SearchRow) pageData.get(l);
177: cursor.setCurrentRow(row);
178: return true;
179: }
180:
181: public void next(BtreeCursor cursor, int i) throws SQLException {
182: i++;
183: if (i < pageData.size()) {
184: SearchRow r = (SearchRow) pageData.get(i);
185: cursor.setCurrentRow(r);
186: cursor.setStackPosition(i);
187: return;
188: }
189: cursor.pop();
190: nextUpper(cursor);
191: }
192:
193: public void first(BtreeCursor cursor) throws SQLException {
194: if (pageData.size() == 0) {
195: if (!Constants.ALLOW_EMPTY_BTREE_PAGES && !root) {
196: throw Message.getInternalError("Empty btree page");
197: }
198: nextUpper(cursor);
199: return;
200: }
201: cursor.push(this , 0);
202: SearchRow row = (SearchRow) pageData.get(0);
203: cursor.setCurrentRow(row);
204: }
205:
206: private void nextUpper(BtreeCursor cursor) throws SQLException {
207: BtreePosition upper = cursor.pop();
208: if (upper == null) {
209: cursor.setCurrentRow(null);
210: } else {
211: cursor.push(upper.page, upper.position);
212: upper.page.next(cursor, upper.position);
213: }
214: }
215:
216: public void prepareWrite() throws SQLException {
217: if (getRealByteCount() >= DiskFile.BLOCK_SIZE * BLOCKS_PER_PAGE) {
218: writePos = true;
219: } else {
220: writePos = false;
221: }
222: }
223:
224: public void write(DataPage buff) throws SQLException {
225: buff.writeByte((byte) 'L');
226: int len = pageData.size();
227: if (writePos) {
228: buff.writeByte((byte) 'P');
229: } else {
230: buff.writeByte((byte) 'D');
231: }
232: buff.writeInt(len);
233: Column[] columns = index.getColumns();
234: for (int i = 0; i < len; i++) {
235: SearchRow row = (SearchRow) pageData.get(i);
236: buff.writeInt(row.getPos());
237: if (!writePos) {
238: for (int j = 0; j < columns.length; j++) {
239: Value v = row.getValue(columns[j].getColumnId());
240: buff.writeValue(v);
241: }
242: }
243: }
244: }
245:
246: private void updateRealByteCount(boolean add, SearchRow row)
247: throws SQLException {
248: if (cachedRealByteCount == 0) {
249: return;
250: }
251: DataPage dummy = index.getDatabase().getDataPage();
252: cachedRealByteCount += getRowSize(dummy, row)
253: + dummy.getIntLen();
254: if (cachedRealByteCount + index.getRecordOverhead() >= DiskFile.BLOCK_SIZE
255: * BLOCKS_PER_PAGE) {
256: cachedRealByteCount = 0;
257: }
258: }
259:
260: public int getRealByteCount() throws SQLException {
261: if (cachedRealByteCount > 0) {
262: return cachedRealByteCount;
263: }
264: DataPage dummy = index.getDatabase().getDataPage();
265: int len = pageData.size();
266: int size = 2 + dummy.getIntLen() * (len + 1);
267: for (int i = 0; i < len; i++) {
268: SearchRow row = (SearchRow) pageData.get(i);
269: size += getRowSize(dummy, row);
270: }
271: size += index.getRecordOverhead();
272: cachedRealByteCount = size;
273: return size;
274: }
275:
276: SearchRow getLast(Session session) throws SQLException {
277: if (pageData.size() == 0) {
278: if (!Constants.ALLOW_EMPTY_BTREE_PAGES && !root) {
279: throw Message.getInternalError("Empty btree page");
280: }
281: return null;
282: }
283: return (SearchRow) pageData.get(pageData.size() - 1);
284: }
285:
286: SearchRow getFirst(Session session) throws SQLException {
287: if (pageData.size() == 0) {
288: if (!Constants.ALLOW_EMPTY_BTREE_PAGES && !root) {
289: throw Message.getInternalError("Empty btree page");
290: }
291: return null;
292: }
293: return (SearchRow) pageData.get(0);
294: }
295:
296: }
|