001: /* Copyright (c) 1995-2000, The Hypersonic SQL Group.
002: * All rights reserved.
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, are permitted provided that the following conditions are met:
006: *
007: * Redistributions of source code must retain the above copyright notice, this
008: * list of conditions and the following disclaimer.
009: *
010: * Redistributions in binary form must reproduce the above copyright notice,
011: * this list of conditions and the following disclaimer in the documentation
012: * and/or other materials provided with the distribution.
013: *
014: * Neither the name of the Hypersonic SQL Group nor the names of its
015: * contributors may be used to endorse or promote products derived from this
016: * software without specific prior written permission.
017: *
018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021: * ARE DISCLAIMED. IN NO EVENT SHALL THE HYPERSONIC SQL GROUP,
022: * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
023: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
024: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
026: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029: *
030: * This software consists of voluntary contributions made by many individuals
031: * on behalf of the Hypersonic SQL Group.
032: *
033: *
034: * For work added by the HSQL Development Group:
035: *
036: * Copyright (c) 2001-2005, The HSQL Development Group
037: * All rights reserved.
038: *
039: * Redistribution and use in source and binary forms, with or without
040: * modification, are permitted provided that the following conditions are met:
041: *
042: * Redistributions of source code must retain the above copyright notice, this
043: * list of conditions and the following disclaimer.
044: *
045: * Redistributions in binary form must reproduce the above copyright notice,
046: * this list of conditions and the following disclaimer in the documentation
047: * and/or other materials provided with the distribution.
048: *
049: * Neither the name of the HSQL Development Group nor the names of its
050: * contributors may be used to endorse or promote products derived from this
051: * software without specific prior written permission.
052: *
053: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
054: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
055: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
056: * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
057: * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
058: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
059: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
060: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
061: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
062: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
063: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
064: */
065:
066: package org.hsqldb;
067:
068: import java.io.IOException;
069:
070: import org.hsqldb.lib.IntLookup;
071: import org.hsqldb.rowio.RowInputInterface;
072: import org.hsqldb.rowio.RowOutputInterface;
073:
074: // fredt@users 20020221 - patch 513005 by sqlbob@users (RMP)
075: // fredt@users 20020920 - path 1.7.1 - refactoring to cut mamory footprint
076: // fredt@users 20021205 - path 1.7.2 - enhancements
077:
078: /**
079: * Cached table Node implementation.<p>
080: * Only integral references to left, right and parent nodes in the AVL tree
081: * are held and used as pointers data.<p>
082: *
083: * iId is a reference to the Index object that contains this node.<br>
084: * This fields can be eliminated in the future, by changing the
085: * method signatures to take a Index parameter from Index.java (fredt@users)
086: *
087: * New class derived from the Hypersonic code
088: *
089: * @author Thomas Mueller (Hypersonic SQL Group)
090: * @version 1.7.2
091: * @since Hypersonic SQL
092: */
093: class DiskNode extends Node {
094:
095: protected Row rData;
096: private int iLeft = NO_POS;
097: private int iRight = NO_POS;
098: private int iParent = NO_POS;
099: private int iId; // id of Index object for this Node
100: static final int SIZE_IN_BYTE = 4 * 4;
101:
102: DiskNode(CachedRow r, RowInputInterface in, int id)
103: throws IOException, HsqlException {
104:
105: iId = id;
106: rData = r;
107: iBalance = in.readIntData();
108: iLeft = in.readIntData();
109:
110: if (iLeft <= 0) {
111: iLeft = NO_POS;
112: }
113:
114: iRight = in.readIntData();
115:
116: if (iRight <= 0) {
117: iRight = NO_POS;
118: }
119:
120: iParent = in.readIntData();
121:
122: if (iParent <= 0) {
123: iParent = NO_POS;
124: }
125:
126: if (Trace.DOASSERT) {
127:
128: // fredt - assert not correct - row can be deleted from one index but
129: // not yet deleted from other indexes while the process of finding
130: // the node is in progress which may require saving the row
131: // to make way for new rows in the cache and loading it back
132: // Trace.doAssert(iBalance != -2);
133: }
134: }
135:
136: DiskNode(CachedRow r, int id) {
137: iId = id;
138: rData = r;
139: }
140:
141: void delete() {
142: rData = null;
143: iBalance = -2;
144: }
145:
146: int getKey() {
147:
148: if (rData != null) {
149: return ((CachedRow) rData).iPos;
150: }
151:
152: return NO_POS;
153: }
154:
155: Row getRow() throws HsqlException {
156:
157: if (Trace.DOASSERT) {
158: Trace.doAssert(rData != null);
159: }
160:
161: return rData;
162: }
163:
164: private Node findNode(int pos) throws HsqlException {
165:
166: Node ret = null;
167: Row r = ((CachedRow) rData).getTable().getRow(pos);
168:
169: if (r != null) {
170: ret = r.getNode(iId);
171: }
172:
173: return ret;
174: }
175:
176: boolean isLeft(Node node) throws HsqlException {
177:
178: if (node == null) {
179: return iLeft == NO_POS;
180: }
181:
182: return iLeft == ((DiskNode) node).getKey();
183: }
184:
185: boolean isRight(Node node) throws HsqlException {
186:
187: if (node == null) {
188: return iRight == NO_POS;
189: }
190:
191: return iRight == ((DiskNode) node).getKey();
192: }
193:
194: Node getLeft() throws HsqlException {
195:
196: if (Trace.DOASSERT) {
197: Trace.doAssert(iBalance != -2);
198: }
199:
200: if (iLeft == NO_POS) {
201: return null;
202: }
203:
204: return findNode(iLeft);
205: }
206:
207: Node getRight() throws HsqlException {
208:
209: if (Trace.DOASSERT) {
210: Trace.doAssert(iBalance != -2);
211: }
212:
213: if (iRight == NO_POS) {
214: return null;
215: }
216:
217: return findNode(iRight);
218: }
219:
220: Node getParent() throws HsqlException {
221:
222: if (Trace.DOASSERT) {
223: Trace.doAssert(iBalance != -2);
224: }
225:
226: if (iParent == NO_POS) {
227: return null;
228: }
229:
230: return findNode(iParent);
231: }
232:
233: boolean isRoot() {
234: return iParent == Node.NO_POS;
235: }
236:
237: boolean isFromLeft() throws HsqlException {
238:
239: if (this .isRoot()) {
240: return true;
241: }
242:
243: if (Trace.DOASSERT) {
244: Trace.doAssert(getParent() != null);
245: }
246:
247: DiskNode parent = (DiskNode) getParent();
248:
249: return getKey() == parent.iLeft;
250: }
251:
252: Object[] getData() throws HsqlException {
253:
254: if (Trace.DOASSERT) {
255: Trace.doAssert(iBalance != -2);
256: }
257:
258: return rData.getData();
259: }
260:
261: void setParent(Node n) throws HsqlException {
262:
263: if (Trace.DOASSERT) {
264: Trace.doAssert(iBalance != -2);
265: }
266:
267: ((CachedRow) rData).setChanged();
268:
269: iParent = n == null ? NO_POS : n.getKey();
270: }
271:
272: void setBalance(int b) throws HsqlException {
273:
274: if (Trace.DOASSERT) {
275: Trace.doAssert(iBalance != -2);
276: }
277:
278: if (iBalance != b) {
279: ((CachedRow) rData).setChanged();
280:
281: iBalance = b;
282: }
283: }
284:
285: void setLeft(Node n) throws HsqlException {
286:
287: if (Trace.DOASSERT) {
288: Trace.doAssert(iBalance != -2);
289: }
290:
291: ((CachedRow) rData).setChanged();
292:
293: iLeft = n == null ? NO_POS : n.getKey();
294: }
295:
296: void setRight(Node n) throws HsqlException {
297:
298: if (Trace.DOASSERT) {
299: Trace.doAssert(iBalance != -2);
300: }
301:
302: ((CachedRow) rData).setChanged();
303:
304: iRight = n == null ? NO_POS : n.getKey();
305: }
306:
307: boolean equals(Node n) {
308:
309: /*
310: if (Trace.DOASSERT) {
311: Trace.doAssert(iBalance != -2);
312:
313: if (n != this) {
314: boolean test = (getKey() == NO_POS) || (n == null)
315: || (n.getKey() != getKey());
316:
317: if (test == false) {
318: test = iParent == ((DiskNode) n).iParent
319: && iLeft == ((DiskNode) n).iLeft
320: && iRight == ((DiskNode) n).iRight;
321:
322: if (test == false) {
323: int aA = ((CachedRow) getRow()).iLastAccess;
324: int bA = ((CachedRow) n.getRow()).iLastAccess;
325:
326: Trace.doAssert(test,
327: "a: " + aA + ", " + iParent + ", "
328: + iLeft + ", " + iRight + " b: " + bA
329: + ", " + ((DiskNode) n).iParent + ", "
330: + ((DiskNode) n).iLeft + ", "
331: + ((DiskNode) n).iRight);
332: }
333: }
334: }
335: }
336: */
337: return this == n
338: || (n != null && getKey() == ((DiskNode) n).getKey());
339: }
340:
341: void write(RowOutputInterface out) throws IOException {
342:
343: if (Trace.DOASSERT) {
344:
345: // fredt - assert not correct - row can be deleted from one index but
346: // not yet deleted from other indexes while the process of finding
347: // the node is in progress which may require saving the row
348: // to make way for new rows in the cache
349: // Trace.doAssert(iBalance != -2);
350: }
351:
352: out.writeIntData(iBalance);
353: out.writeIntData((iLeft == NO_POS) ? 0 : iLeft);
354: out.writeIntData((iRight == NO_POS) ? 0 : iRight);
355: out.writeIntData((iParent == NO_POS) ? 0 : iParent);
356: }
357:
358: Node getUpdatedNode() throws HsqlException {
359:
360: Row row = rData.getUpdatedRow();
361:
362: return row == null ? null : row.getNode(iId);
363: }
364:
365: void writeTranslate(RowOutputInterface out, IntLookup lookup) {
366:
367: out.writeIntData(iBalance);
368: writeTranslatePointer(iLeft, out, lookup);
369: writeTranslatePointer(iRight, out, lookup);
370: writeTranslatePointer(iParent, out, lookup);
371: }
372:
373: private void writeTranslatePointer(int pointer,
374: RowOutputInterface out, IntLookup lookup) {
375:
376: int newPointer = 0;
377:
378: if (pointer != Node.NO_POS) {
379: newPointer = lookup.lookupFirstEqual(pointer);
380: }
381:
382: out.writeIntData(newPointer);
383: }
384: }
|