001: /*
002: * $Id: IntBTreeIndex.java,v 1.9 2005/12/20 18:32:30 ahimanikya Exp $
003: * =======================================================================
004: * Copyright (c) 2002-2005 Axion Development Team. All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: *
010: * 1. Redistributions of source code must retain the above
011: * copyright notice, this list of conditions and the following
012: * disclaimer.
013: *
014: * 2. Redistributions in binary form must reproduce the above copyright
015: * notice, this list of conditions and the following disclaimer in
016: * the documentation and/or other materials provided with the
017: * distribution.
018: *
019: * 3. The names "Tigris", "Axion", nor the names of its contributors may
020: * not be used to endorse or promote products derived from this
021: * software without specific prior written permission.
022: *
023: * 4. Products derived from this software may not be called "Axion", nor
024: * may "Tigris" or "Axion" appear in their names without specific prior
025: * written permission.
026: *
027: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
028: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
029: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
030: * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
031: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
032: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
033: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
034: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
035: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
036: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
037: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
038: * =======================================================================
039: */
040:
041: package org.axiondb.engine.indexes;
042:
043: import java.io.File;
044: import java.io.IOException;
045:
046: import org.apache.commons.collections.primitives.ArrayIntList;
047: import org.apache.commons.collections.primitives.IntListIterator;
048: import org.axiondb.AxionException;
049: import org.axiondb.Column;
050: import org.axiondb.DataType;
051: import org.axiondb.Function;
052: import org.axiondb.IndexLoader;
053: import org.axiondb.Row;
054: import org.axiondb.RowIterator;
055: import org.axiondb.RowSource;
056: import org.axiondb.Table;
057: import org.axiondb.engine.IntBTreeIndexLoader;
058: import org.axiondb.engine.rowiterators.EmptyRowIterator;
059: import org.axiondb.engine.rowiterators.LazyRowRowIterator;
060: import org.axiondb.event.RowEvent;
061: import org.axiondb.event.TableModificationListener;
062: import org.axiondb.functions.ComparisonFunction;
063: import org.axiondb.functions.EqualFunction;
064: import org.axiondb.functions.GreaterThanFunction;
065: import org.axiondb.functions.GreaterThanOrEqualFunction;
066: import org.axiondb.functions.IsNotNullFunction;
067: import org.axiondb.functions.IsNullFunction;
068: import org.axiondb.functions.LessThanFunction;
069: import org.axiondb.functions.LessThanOrEqualFunction;
070: import org.axiondb.util.IntBTree;
071: import org.axiondb.util.NullObject;
072:
073: /**
074: * A {@link BaseBTreeIndex B-Tree index}over integer keys.
075: *
076: * @version $Revision: 1.9 $ $Date: 2005/12/20 18:32:30 $
077: * @author Chuck Burdick
078: * @author Dave Pekarek Krohn
079: * @author Ritesh Adval
080: * @author Charles Ye
081: */
082: public class IntBTreeIndex extends BaseBTreeIndex implements
083: TableModificationListener {
084:
085: public IntBTreeIndex(String name, Column column, boolean unique)
086: throws AxionException {
087: this (name, column, unique, null);
088: }
089:
090: public IntBTreeIndex(String name, Column column, boolean unique,
091: File dataDirectory) throws AxionException {
092: super (name, column, unique);
093: try {
094: _dataDirectory = dataDirectory;
095: _tree = new IntBTree(_dataDirectory, getName(), 1000);
096: } catch (Exception e) {
097: String msg = "Unable to create index file for " + getName()
098: + " due to IOException";
099: throw new AxionException(msg, e);
100: }
101: }
102:
103: public void changeRowId(Table table, Row row, int oldId, int newId)
104: throws AxionException {
105: try {
106: int colnum = table.getColumnIndex(getIndexedColumn()
107: .getName());
108: Integer key = (Integer) row.get(colnum);
109: _tree.replaceId(key.intValue(), oldId, newId);
110: } catch (Exception e) {
111: String msg = "Unable to change row id in index "
112: + getName() + " due to IOException";
113: throw new AxionException(msg, e);
114: }
115: }
116:
117: public IntBTree getBTree() {
118: return _tree;
119: }
120:
121: public IndexLoader getIndexLoader() {
122: return LOADER;
123: }
124:
125: public final RowIterator getInorderRowIterator(RowSource source)
126: throws AxionException {
127: IntListIterator resultIds = null;
128: try {
129: resultIds = _tree.inorderIterator();
130: } catch (IOException e) {
131: String msg = "Unable to retrieve values from index"
132: + getName();
133: throw new AxionException(msg, e);
134: } catch (ClassNotFoundException e) {
135: String msg = "Unable to retrieve values from index"
136: + getName();
137: throw new AxionException(msg, e);
138: }
139:
140: return new LazyRowRowIterator(source, resultIds, _tree.size());
141: }
142:
143: public RowIterator getRowIterator(RowSource source,
144: Function function, Object value) throws AxionException {
145: IntListIterator resultIds = null;
146: try {
147: if (function instanceof ComparisonFunction) {
148: DataType type = getIndexedColumn().getDataType();
149:
150: Object convertedValue = type.convert(value);
151: if (null == convertedValue) {
152: // null fails all comparisions I support
153: return EmptyRowIterator.INSTANCE;
154: }
155: int iVal = type.toInt(convertedValue);
156: if (function instanceof EqualFunction) {
157: if (!isUnique()) {
158: resultIds = _tree.getAll(iVal);
159: } else {
160: Integer result = _tree.get(iVal);
161: if (result == null) {
162: return EmptyRowIterator.INSTANCE;
163: } else {
164: ArrayIntList ids = new ArrayIntList(1);
165: ids.add(result.intValue());
166: return new LazyRowRowIterator(source, ids
167: .listIterator(), 1);
168: }
169: }
170: } else if (function instanceof LessThanFunction) {
171: resultIds = _tree.getAllTo(iVal);
172: } else if (function instanceof LessThanOrEqualFunction) {
173: int iSuccessor = getSuccessor(type, convertedValue);
174: resultIds = _tree.getAllTo(iSuccessor);
175: } else if (function instanceof GreaterThanFunction) {
176:
177: int iSuccessor = getSuccessor(type, convertedValue);
178:
179: // NOTE: _tree.valueIterator returns a continuation rather than
180: // enumerating all elements of the RowIterator first. This is slightly
181: // slower than the getAllFrom for small tables, but faster and less
182: // memory consumptive memory for large tables, especially when we
183: // rarely visit the tail of the result set. This also postpones
184: // loading the index nodes until the data is actually read (in
185: // constrast, getAllFrom(<some small value>) will load all or nearly
186: // all nodes. For optimal performance it may be best to determine how
187: // large the index is and use that to figure out which
188: // approach--enumeration or continuation--is most appropriate for the
189: // given query.
190:
191: // resultIds = _tree.getAllFrom(iSuccessor);
192: resultIds = _tree
193: .valueIteratorGreaterThanOrEqualTo(iSuccessor);
194:
195: } else if (function instanceof GreaterThanOrEqualFunction) {
196: // NOTE: see note above.
197: // resultIds = _tree.getAllFrom(iVal);
198: resultIds = _tree
199: .valueIteratorGreaterThanOrEqualTo(iVal);
200:
201: } else {
202: throw new AxionException("Unsupported function "
203: + function);
204: }
205: } else if (function instanceof IsNotNullFunction) {
206: resultIds = _tree.getAllExcludingNull();
207: } else if (function instanceof IsNullFunction) {
208: resultIds = _tree
209: .getAll(NullObject.INSTANCE.intValue());
210: } else {
211: throw new AxionException("Unsupported function "
212: + function);
213: }
214: } catch (Exception e) {
215: String msg = "Unable to retrieve values from index "
216: + getName() + " due to IOException";
217: throw new AxionException(msg, e);
218: }
219: //return new LazyRowRowIterator(source, resultIds);
220:
221: // FIXME: There should be a better way to fix concurent modification issue
222: ArrayIntList ids = new ArrayIntList();
223: while (resultIds.hasNext()) {
224: ids.add(resultIds.next());
225: }
226: return new LazyRowRowIterator(source, ids.listIterator(), ids
227: .size());
228: }
229:
230: public void rowDeleted(RowEvent event) throws AxionException {
231: String colName = getIndexedColumn().getName();
232: int colIndex = event.getTable().getColumnIndex(colName);
233: Integer key = (Integer) event.getOldRow().get(colIndex);
234: int rowid = event.getOldRow().getIdentifier();
235: int intKey = (key == null) ? NullObject.INSTANCE.intValue()
236: : key.intValue();
237: try {
238: _tree.delete(intKey, rowid);
239: } catch (Exception e) {
240: String msg = "Unable to delete from index " + getName()
241: + " due to " + e.getMessage();
242: throw new AxionException(msg, e);
243: }
244: }
245:
246: // TABLE MODIFICATION LISTENER
247: public void rowInserted(RowEvent event) throws AxionException {
248: String colName = getIndexedColumn().getName();
249: int colIndex = event.getTable().getColumnIndex(colName);
250: Integer value = (Integer) event.getNewRow().get(colIndex);
251: int intValue = (value == null) ? NullObject.INSTANCE.intValue()
252: : value.intValue();
253:
254: try {
255: _tree.insert(intValue, event.getNewRow().getIdentifier());
256: } catch (Exception e) {
257: String msg = "Unable to insert into index " + getName()
258: + " due to IOException";
259: throw new AxionException(msg, e);
260: }
261: }
262:
263: public void rowUpdated(RowEvent event) throws AxionException {
264: rowDeleted(event);
265: rowInserted(event);
266: }
267:
268: public void truncate() throws AxionException {
269: _tree.truncate();
270: }
271:
272: private int getSuccessor(DataType type, Object convertedValue)
273: throws AxionException {
274: return type.toInt(type.successor(convertedValue));
275: }
276:
277: private static final IndexLoader LOADER = new IntBTreeIndexLoader();
278:
279: private File _dataDirectory;
280: private IntBTree _tree = null;
281: }
|