001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package com.db4o.internal.ix;
022:
023: import com.db4o.*;
024: import com.db4o.foundation.Tree;
025: import com.db4o.internal.*;
026:
027: /**
028: * @exclude
029: */
030: class IxFileRangeReader {
031:
032: private int _baseAddress;
033: private int _baseAddressOffset;
034: private int _addressOffset;
035:
036: private final Indexable4 _handler;
037:
038: private int _lower;
039: private int _upper;
040: private int _cursor;
041:
042: private final Buffer _reader;
043:
044: final int _slotLength;
045:
046: final int _linkLegth;
047:
048: IxFileRangeReader(Indexable4 handler) {
049: _handler = handler;
050: _linkLegth = handler.linkLength();
051: _slotLength = _linkLegth + Const4.INT_LENGTH;
052: _reader = new Buffer(_slotLength);
053: }
054:
055: Tree add(IxFileRange fileRange, final Tree newTree)
056: throws IxException {
057: setFileRange(fileRange);
058: LocalObjectContainer yf = fileRange.stream();
059: Transaction trans = fileRange.trans();
060: while (true) {
061: int offset = _baseAddressOffset + _addressOffset;
062: _reader.read(yf, _baseAddress, offset);
063: _reader._offset = 0;
064:
065: int cmp = compare(trans);
066:
067: if (cmp == 0) {
068: int parentID = _reader.readInt();
069: cmp = parentID - ((IxPatch) newTree)._parentID;
070: }
071: if (cmp > 0) {
072: _upper = _cursor - 1;
073: if (_upper < _lower) {
074: _upper = _lower;
075: }
076: } else if (cmp < 0) {
077: _lower = _cursor + 1;
078: if (_lower > _upper) {
079: _lower = _upper;
080: }
081: } else {
082: if (newTree instanceof IxRemove) {
083: if (_cursor == 0) {
084: newTree._preceding = fileRange._preceding;
085: if (fileRange._entries == 1) {
086: newTree._subsequent = fileRange._subsequent;
087: return newTree.balanceCheckNulls();
088: }
089: fileRange._entries--;
090: fileRange.incrementAddress(_slotLength);
091: fileRange._preceding = null;
092: newTree._subsequent = fileRange;
093: } else if (_cursor + 1 == fileRange._entries) {
094: newTree._preceding = fileRange;
095: newTree._subsequent = fileRange._subsequent;
096: fileRange._subsequent = null;
097: fileRange._entries--;
098: } else {
099: return insert(fileRange, newTree, _cursor, 0);
100: }
101: fileRange.calculateSize();
102: return newTree.balanceCheckNulls();
103: }
104: if (_cursor == 0) {
105: newTree._subsequent = fileRange;
106: return newTree.rotateLeft();
107: } else if (_cursor == fileRange._entries) {
108: newTree._preceding = fileRange;
109: return newTree.rotateRight();
110: }
111: return insert(fileRange, newTree, _cursor, cmp);
112: }
113: if (!adjustCursor()) {
114: if (_cursor == 0 && cmp > 0) {
115: return fileRange.add(newTree, 1);
116: }
117: if (_cursor == fileRange._entries - 1 && cmp < 0) {
118: return fileRange.add(newTree, -1);
119: }
120: return insert(fileRange, newTree, _cursor, cmp);
121: }
122: }
123: }
124:
125: private boolean adjustCursor() {
126: if (_upper < _lower) {
127: return false;
128: }
129: int oldCursor = _cursor;
130: _cursor = _lower + ((_upper - _lower) / 2);
131: if (_cursor == oldCursor && _cursor == _lower
132: && _lower < _upper) {
133: _cursor++;
134: }
135: _addressOffset = _cursor * _slotLength;
136: return _cursor != oldCursor;
137: }
138:
139: int compare(IxFileRange fileRange, int[] matches)
140: throws IxException {
141:
142: setFileRange(fileRange);
143: LocalObjectContainer yf = fileRange.stream();
144: Transaction trans = fileRange.trans();
145:
146: int res = 0;
147:
148: while (true) {
149: int offset = _baseAddressOffset + _addressOffset;
150: _reader.read(yf, _baseAddress, offset);
151: _reader._offset = 0;
152: int cmp = compare(trans);
153: if (cmp > 0) {
154: _upper = _cursor - 1;
155: } else if (cmp < 0) {
156: _lower = _cursor + 1;
157: } else {
158: break;
159: }
160: if (!adjustCursor()) {
161: if (_cursor <= 0) {
162: if (!(cmp < 0 && fileRange._entries > 1)) {
163: res = cmp;
164: }
165: } else if (_cursor >= (fileRange._entries - 1)) {
166: if (cmp < 0) {
167: res = cmp;
168: }
169: }
170: break;
171: }
172: }
173:
174: matches[0] = _lower;
175: matches[1] = _upper;
176:
177: if (_lower > _upper) {
178: return res;
179: }
180:
181: int tempCursor = _cursor;
182: _upper = _cursor;
183: adjustCursor();
184: while (true) {
185: int offset = _baseAddressOffset + _addressOffset;
186: _reader.read(yf, _baseAddress, offset);
187: _reader._offset = 0;
188: int cmp = compare(trans);
189: if (cmp == 0) {
190: _upper = _cursor;
191: } else {
192: _lower = _cursor + 1;
193: if (_lower > _upper) {
194: matches[0] = _upper;
195: break;
196: }
197: }
198: if (!adjustCursor()) {
199: matches[0] = _upper;
200: break;
201: }
202: }
203: _upper = matches[1];
204: _lower = tempCursor;
205: if (_lower > _upper) {
206: _lower = _upper;
207: }
208: adjustCursor();
209: while (true) {
210: int offset = _baseAddressOffset + _addressOffset;
211: _reader.read(yf, _baseAddress, offset);
212: _reader._offset = 0;
213: int cmp = compare(trans);
214: if (cmp == 0) {
215: _lower = _cursor;
216: } else {
217: _upper = _cursor - 1;
218: if (_upper < _lower) {
219: matches[1] = _lower;
220: break;
221: }
222: }
223: if (!adjustCursor()) {
224: matches[1] = _lower;
225: break;
226: }
227: }
228: return res;
229: }
230:
231: private final int compare(Transaction trans) {
232: return _handler.compareTo(IxDeprecationHelper.comparableObject(
233: _handler, trans, _handler.readIndexEntry(_reader)));
234: }
235:
236: private Tree insert(IxFileRange fileRange, Tree a_new,
237: int a_cursor, int a_cmp) {
238: int incStartNewAt = a_cmp <= 0 ? 1 : 0;
239: int newAddressOffset = (a_cursor + incStartNewAt) * _slotLength;
240: int newEntries = fileRange._entries - a_cursor - incStartNewAt;
241: if (Deploy.debug) {
242: if (newEntries == 0) {
243: // A bug in P1Object made this happen.
244: // It looke like it occurs if (a_cmp == 0)
245: // We may have to deal with this again, if we get similar
246: // entries on the same object (indexing arrays),
247: // so (a_cmp == 0)
248: throw new RuntimeException(
249: "No zero new entries permitted here.");
250: }
251: }
252:
253: fileRange._entries = a_cmp < 0 ? a_cursor + 1 : a_cursor;
254: IxFileRange ifr = new IxFileRange(fileRange._fieldTransaction,
255: _baseAddress, _baseAddressOffset + newAddressOffset,
256: newEntries);
257: ifr._subsequent = fileRange._subsequent;
258: fileRange._subsequent = null;
259: a_new._preceding = fileRange.balanceCheckNulls();
260: a_new._subsequent = ifr.balanceCheckNulls();
261: return a_new.balance();
262: }
263:
264: private void setFileRange(IxFileRange a_fr) {
265: _lower = 0;
266: _upper = a_fr._entries - 1;
267: _baseAddress = a_fr._address;
268: _baseAddressOffset = a_fr._addressOffset;
269: adjustCursor();
270: }
271: }
|