0001: /*
0002: Copyright (c) 2005 Health Market Science, Inc.
0003:
0004: This library is free software; you can redistribute it and/or
0005: modify it under the terms of the GNU Lesser General Public
0006: License as published by the Free Software Foundation; either
0007: version 2.1 of the License, or (at your option) any later version.
0008:
0009: This library is distributed in the hope that it will be useful,
0010: but WITHOUT ANY WARRANTY; without even the implied warranty of
0011: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0012: Lesser General Public License for more details.
0013:
0014: You should have received a copy of the GNU Lesser General Public
0015: License along with this library; if not, write to the Free Software
0016: Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
0017: USA
0018:
0019: You can contact Health Market Science at info@healthmarketscience.com
0020: or at the following address:
0021:
0022: Health Market Science
0023: 2700 Horizon Drive
0024: Suite 200
0025: King of Prussia, PA 19406
0026: */
0027:
0028: package com.healthmarketscience.jackcess;
0029:
0030: import java.io.ByteArrayOutputStream;
0031: import java.io.IOException;
0032: import java.nio.ByteBuffer;
0033: import java.nio.ByteOrder;
0034: import java.util.ArrayList;
0035: import java.util.Arrays;
0036: import java.util.Collection;
0037: import java.util.Collections;
0038: import java.util.Comparator;
0039: import java.util.Iterator;
0040: import java.util.LinkedList;
0041: import java.util.List;
0042: import java.util.Map;
0043:
0044: import org.apache.commons.logging.Log;
0045: import org.apache.commons.logging.LogFactory;
0046:
0047: import static com.healthmarketscience.jackcess.IndexCodes.*;
0048:
0049: /**
0050: * Access table index
0051: * @author Tim McCune
0052: */
0053: public class Index implements Comparable<Index> {
0054:
0055: private static final Log LOG = LogFactory.getLog(Index.class);
0056:
0057: /** special entry which is less than any other entry */
0058: public static final Entry FIRST_ENTRY = createSpecialEntry(RowId.FIRST_ROW_ID);
0059:
0060: /** special entry which is greater than any other entry */
0061: public static final Entry LAST_ENTRY = createSpecialEntry(RowId.LAST_ROW_ID);
0062:
0063: /** index of the first (exclusive) index entry */
0064: private static final int FIRST_ENTRY_IDX = -1;
0065: /** index of the last (exclusive) index entry */
0066: private static final int LAST_ENTRY_IDX = -2;
0067:
0068: /** the first position for a cursor */
0069: private static final Position FIRST_POSITION = new Position(
0070: FIRST_ENTRY_IDX, FIRST_ENTRY);
0071:
0072: /** the last position for a cursor */
0073: private static final Position LAST_POSITION = new Position(
0074: LAST_ENTRY_IDX, LAST_ENTRY);
0075:
0076: /** Max number of columns in an index */
0077: private static final int MAX_COLUMNS = 10;
0078:
0079: private static final short COLUMN_UNUSED = -1;
0080:
0081: private static final byte INDEX_NODE_PAGE_TYPE = (byte) 0x03;
0082: private static final byte INDEX_LEAF_PAGE_TYPE = (byte) 0x04;
0083:
0084: private static final byte ASCENDING_COLUMN_FLAG = (byte) 0x01;
0085:
0086: private static final byte UNIQUE_INDEX_FLAG = (byte) 0x01;
0087: private static final byte IGNORE_NULLS_INDEX_FLAG = (byte) 0x02;
0088:
0089: /** index type for primary key indexes */
0090: private static final byte PRIMARY_KEY_INDEX_TYPE = (byte) 1;
0091:
0092: /** index type for foreign key indexes */
0093: private static final byte FOREIGN_KEY_INDEX_TYPE = (byte) 2;
0094:
0095: private static final int MAX_TEXT_INDEX_CHAR_LENGTH = (JetFormat.TEXT_FIELD_MAX_LENGTH / JetFormat.TEXT_FIELD_UNIT_SIZE);
0096:
0097: /** type attributes for Entries which simplify comparisons */
0098: public enum EntryType {
0099: /** comparable type indicating this Entry should always compare less than
0100: valid RowIds */
0101: ALWAYS_FIRST,
0102: /** comparable type indicating this Entry should always compare less than
0103: other valid entries with equal entryBytes */
0104: FIRST_VALID,
0105: /** comparable type indicating this RowId should always compare
0106: normally */
0107: NORMAL,
0108: /** comparable type indicating this Entry should always compare greater
0109: than other valid entries with equal entryBytes */
0110: LAST_VALID,
0111: /** comparable type indicating this Entry should always compare greater
0112: than valid RowIds */
0113: ALWAYS_LAST;
0114: }
0115:
0116: static final Comparator<byte[]> BYTE_CODE_COMPARATOR = new Comparator<byte[]>() {
0117: public int compare(byte[] left, byte[] right) {
0118: if (left == right) {
0119: return 0;
0120: }
0121: if (left == null) {
0122: return -1;
0123: }
0124: if (right == null) {
0125: return 1;
0126: }
0127:
0128: int len = Math.min(left.length, right.length);
0129: int pos = 0;
0130: while ((pos < len) && (left[pos] == right[pos])) {
0131: ++pos;
0132: }
0133: if (pos < len) {
0134: return ((ByteUtil.asUnsignedByte(left[pos]) < ByteUtil
0135: .asUnsignedByte(right[pos])) ? -1 : 1);
0136: }
0137: return ((left.length < right.length) ? -1
0138: : ((left.length > right.length) ? 1 : 0));
0139: }
0140: };
0141:
0142: /** owning table */
0143: private final Table _table;
0144: /** Page number of the index data */
0145: private int _pageNumber;
0146: /** offset within the tableDefinition buffer of the uniqueEntryCount for
0147: this index */
0148: private final int _uniqueEntryCountOffset;
0149: /** The number of unique entries which have been added to this index. note,
0150: however, that it is never decremented, only incremented (as observed in
0151: Access). */
0152: private int _uniqueEntryCount;
0153: /** sorted collection of index entries. this is kept in a list instead of a
0154: SortedSet because the SortedSet has lame traversal utilities */
0155: private final List<Entry> _entries = new ArrayList<Entry>();
0156: /** List of columns and flags */
0157: private final List<ColumnDescriptor> _columns = new ArrayList<ColumnDescriptor>();
0158: /** 0-based index number */
0159: private int _indexNumber;
0160: /** flags for this index */
0161: private byte _indexFlags;
0162: /** the type of the index */
0163: private byte _indexType;
0164: /** Index name */
0165: private String _name;
0166: /** <code>true</code> if the index entries have been initialized,
0167: <code>false</code> otherwise */
0168: private boolean _initialized;
0169: /** modification count for the table, keeps cursors up-to-date */
0170: private int _modCount;
0171: /** temp buffer used to writing the index */
0172: private final TempBufferHolder _indexBufferH = TempBufferHolder
0173: .newHolder(TempBufferHolder.Type.SOFT, true);
0174: /** FIXME, for now, we can't write multi-page indexes or indexes using the funky primary key compression scheme */
0175: boolean _readOnly;
0176:
0177: public Index(Table table, int uniqueEntryCount,
0178: int uniqueEntryCountOffset) {
0179: _table = table;
0180: _uniqueEntryCount = uniqueEntryCount;
0181: _uniqueEntryCountOffset = uniqueEntryCountOffset;
0182: }
0183:
0184: public Table getTable() {
0185: return _table;
0186: }
0187:
0188: public JetFormat getFormat() {
0189: return getTable().getFormat();
0190: }
0191:
0192: public PageChannel getPageChannel() {
0193: return getTable().getPageChannel();
0194: }
0195:
0196: public void setIndexNumber(int indexNumber) {
0197: _indexNumber = indexNumber;
0198: }
0199:
0200: public int getIndexNumber() {
0201: return _indexNumber;
0202: }
0203:
0204: public void setIndexType(byte indexType) {
0205: _indexType = indexType;
0206: }
0207:
0208: public byte getIndexFlags() {
0209: return _indexFlags;
0210: }
0211:
0212: public int getUniqueEntryCount() {
0213: return _uniqueEntryCount;
0214: }
0215:
0216: public int getUniqueEntryCountOffset() {
0217: return _uniqueEntryCountOffset;
0218: }
0219:
0220: public String getName() {
0221: return _name;
0222: }
0223:
0224: public void setName(String name) {
0225: _name = name;
0226: }
0227:
0228: public boolean isPrimaryKey() {
0229: return _indexType == PRIMARY_KEY_INDEX_TYPE;
0230: }
0231:
0232: public boolean isForeignKey() {
0233: return _indexType == FOREIGN_KEY_INDEX_TYPE;
0234: }
0235:
0236: /**
0237: * Whether or not {@code null} values are actually recorded in the index.
0238: */
0239: public boolean shouldIgnoreNulls() {
0240: return ((_indexFlags & IGNORE_NULLS_INDEX_FLAG) != 0);
0241: }
0242:
0243: /**
0244: * Whether or not index entries must be unique.
0245: * <p>
0246: * Some notes about uniqueness:
0247: * <ul>
0248: * <li>Access does not seem to consider multiple {@code null} entries
0249: * invalid for a unique index</li>
0250: * <li>text indexes collapse case, and Access seems to compare <b>only</b>
0251: * the index entry bytes, therefore two strings which differ only in
0252: * case <i>will violate</i> the unique constraint</li>
0253: * </ul>
0254: */
0255: public boolean isUnique() {
0256: return (isPrimaryKey() || ((_indexFlags & UNIQUE_INDEX_FLAG) != 0));
0257: }
0258:
0259: /**
0260: * Returns the Columns for this index (unmodifiable)
0261: */
0262: public List<ColumnDescriptor> getColumns() {
0263: return Collections.unmodifiableList(_columns);
0264: }
0265:
0266: /**
0267: * Returns the number of index entries in the index. Only called by unit
0268: * tests.
0269: * <p>
0270: * Forces index initialization.
0271: */
0272: int getEntryCount() throws IOException {
0273: initialize();
0274: return _entries.size();
0275: }
0276:
0277: /**
0278: * Whether or not the complete index state has been read.
0279: */
0280: public boolean isInitialized() {
0281: return _initialized;
0282: }
0283:
0284: /**
0285: * Forces initialization of this index (actual parsing of index pages).
0286: * normally, the index will not be initialized until the entries are
0287: * actually needed.
0288: */
0289: public void initialize() throws IOException {
0290: if (!_initialized) {
0291: readIndexEntries();
0292: _initialized = true;
0293: }
0294: }
0295:
0296: /**
0297: * Writes the current index state to the database.
0298: * <p>
0299: * Forces index initialization.
0300: */
0301: public void update() throws IOException {
0302: // make sure we've parsed the entries
0303: initialize();
0304:
0305: if (_readOnly) {
0306: throw new UnsupportedOperationException(
0307: "FIXME cannot write indexes of this type yet");
0308: }
0309: getPageChannel().writePage(write(), _pageNumber);
0310: }
0311:
0312: /**
0313: * Write this index out to a buffer
0314: */
0315: private ByteBuffer write() throws IOException {
0316: ByteBuffer buffer = _indexBufferH
0317: .getPageBuffer(getPageChannel());
0318: buffer.put((byte) 0x04); //Page type
0319: buffer.put((byte) 0x01); //Unknown
0320: buffer.putShort((short) 0); //Free space
0321: buffer.putInt(getTable().getTableDefPageNumber());
0322: buffer.putInt(0); //Prev page
0323: buffer.putInt(0); //Next page
0324: buffer.putInt(0); //Leaf page
0325: buffer.putInt(0); //Unknown
0326: buffer.put((byte) 0); // compressed byte count
0327: buffer.put((byte) 0); //Unknown
0328: buffer.put((byte) 0); //Unknown
0329: byte[] entryMask = new byte[getFormat().SIZE_INDEX_ENTRY_MASK];
0330: int totalSize = 0;
0331: for (Entry entry : _entries) {
0332: int size = entry.size();
0333: totalSize += size;
0334: int idx = totalSize / 8;
0335: if (idx >= entryMask.length) {
0336: throw new UnsupportedOperationException(
0337: "FIXME cannot write large index yet");
0338: }
0339: entryMask[idx] |= (1 << (totalSize % 8));
0340: }
0341: buffer.put(entryMask);
0342: for (Entry entry : _entries) {
0343: entry.write(buffer);
0344: }
0345: buffer.putShort(2, (short) (getFormat().PAGE_SIZE - buffer
0346: .position()));
0347: return buffer;
0348: }
0349:
0350: /**
0351: * Read the index info from a tableBuffer
0352: * @param tableBuffer table definition buffer to read from initial info
0353: * @param availableColumns Columns that this index may use
0354: */
0355: public void read(ByteBuffer tableBuffer,
0356: List<Column> availableColumns) throws IOException {
0357: for (int i = 0; i < MAX_COLUMNS; i++) {
0358: short columnNumber = tableBuffer.getShort();
0359: byte colFlags = tableBuffer.get();
0360: if (columnNumber != COLUMN_UNUSED) {
0361: // find the desired column by column number (which is not necessarily
0362: // the same as the column index)
0363: Column idxCol = null;
0364: for (Column col : availableColumns) {
0365: if (col.getColumnNumber() == columnNumber) {
0366: idxCol = col;
0367: break;
0368: }
0369: }
0370: if (idxCol == null) {
0371: throw new IOException(
0372: "Could not find column with number "
0373: + columnNumber + " for index "
0374: + getName());
0375: }
0376: _columns.add(newColumnDescriptor(idxCol, colFlags));
0377: }
0378: }
0379: tableBuffer.getInt(); //Forward past Unknown
0380: _pageNumber = tableBuffer.getInt();
0381: tableBuffer.getInt(); //Forward past Unknown
0382: _indexFlags = tableBuffer.get();
0383: tableBuffer.position(tableBuffer.position() + 5); //Forward past other stuff
0384: }
0385:
0386: /**
0387: * Reads the actual index entries.
0388: */
0389: private void readIndexEntries() throws IOException {
0390: ByteBuffer indexPage = getPageChannel().createPageBuffer();
0391:
0392: // find first leaf page
0393: int leafPageNumber = _pageNumber;
0394: while (true) {
0395: getPageChannel().readPage(indexPage, leafPageNumber);
0396:
0397: if (indexPage.get(0) == INDEX_NODE_PAGE_TYPE) {
0398: // FIXME we can't modify this index at this point in time
0399: _readOnly = true;
0400:
0401: // found another node page
0402: leafPageNumber = readNodePage(indexPage);
0403: } else {
0404: // found first leaf
0405: indexPage.rewind();
0406: break;
0407: }
0408: }
0409:
0410: // read all leaf pages. since we read all the entries in sort order, we
0411: // can insert them directly into the _entries list
0412: while (true) {
0413:
0414: leafPageNumber = readLeafPage(indexPage, _entries);
0415: if (leafPageNumber != 0) {
0416: // FIXME we can't modify this index at this point in time
0417: _readOnly = true;
0418:
0419: // found another one
0420: getPageChannel().readPage(indexPage, leafPageNumber);
0421:
0422: } else {
0423: // all done
0424: break;
0425: }
0426: }
0427:
0428: // check the entry order, just to be safe
0429: for (int i = 0; i < (_entries.size() - 1); ++i) {
0430: Entry e1 = _entries.get(i);
0431: Entry e2 = _entries.get(i + 1);
0432: if (e1.compareTo(e2) > 0) {
0433: throw new IOException(
0434: "Unexpected order in index entries, " + e1
0435: + " is greater than " + e2);
0436: }
0437: }
0438: }
0439:
0440: /**
0441: * Reads the first entry off of an index node page and returns the next page
0442: * number.
0443: */
0444: private int readNodePage(ByteBuffer nodePage) throws IOException {
0445: if (nodePage.get(0) != INDEX_NODE_PAGE_TYPE) {
0446: throw new IOException("expected index node page, found "
0447: + nodePage.get(0));
0448: }
0449:
0450: List<NodeEntry> nodeEntries = new ArrayList<NodeEntry>();
0451: readIndexPage(nodePage, false, null, nodeEntries);
0452:
0453: // grab the first entry
0454: // FIXME, need to parse all...?
0455: return nodeEntries.get(0).getSubPageNumber();
0456: }
0457:
0458: /**
0459: * Reads an index leaf page.
0460: * @return the next leaf page number, 0 if none
0461: */
0462: private int readLeafPage(ByteBuffer leafPage,
0463: Collection<Entry> entries) throws IOException {
0464: if (leafPage.get(0) != INDEX_LEAF_PAGE_TYPE) {
0465: throw new IOException("expected index leaf page, found "
0466: + leafPage.get(0));
0467: }
0468:
0469: // note, "header" data is in LITTLE_ENDIAN format, entry data is in
0470: // BIG_ENDIAN format
0471:
0472: int nextLeafPage = leafPage
0473: .getInt(getFormat().OFFSET_NEXT_INDEX_LEAF_PAGE);
0474: readIndexPage(leafPage, true, entries, null);
0475:
0476: return nextLeafPage;
0477: }
0478:
0479: /**
0480: * Reads an index page, populating the correct collection based on the page
0481: * type (node or leaf).
0482: */
0483: private void readIndexPage(ByteBuffer indexPage, boolean isLeaf,
0484: Collection<Entry> entries, Collection<NodeEntry> nodeEntries)
0485: throws IOException {
0486: // note, "header" data is in LITTLE_ENDIAN format, entry data is in
0487: // BIG_ENDIAN format
0488: int numCompressedBytes = ByteUtil.getUnsignedByte(indexPage,
0489: getFormat().OFFSET_INDEX_COMPRESSED_BYTE_COUNT);
0490: int entryMaskLength = getFormat().SIZE_INDEX_ENTRY_MASK;
0491: int entryMaskPos = getFormat().OFFSET_INDEX_ENTRY_MASK;
0492: int entryPos = entryMaskPos + getFormat().SIZE_INDEX_ENTRY_MASK;
0493: int lastStart = 0;
0494: byte[] valuePrefix = null;
0495: boolean firstEntry = true;
0496: TempBufferHolder tmpEntryBufferH = TempBufferHolder.newHolder(
0497: TempBufferHolder.Type.HARD, true, ByteOrder.BIG_ENDIAN);
0498:
0499: for (int i = 0; i < entryMaskLength; i++) {
0500: byte entryMask = indexPage.get(entryMaskPos + i);
0501: for (int j = 0; j < 8; j++) {
0502: if ((entryMask & (1 << j)) != 0) {
0503: int length = (i * 8) + j - lastStart;
0504: indexPage.position(entryPos + lastStart);
0505:
0506: // determine if we can read straight from the index page (if no
0507: // valuePrefix). otherwise, create temp buf with complete entry.
0508: ByteBuffer curEntryBuffer = indexPage;
0509: int curEntryLen = length;
0510: if (valuePrefix != null) {
0511: curEntryBuffer = getTempEntryBuffer(indexPage,
0512: length, valuePrefix, tmpEntryBufferH);
0513: curEntryLen += valuePrefix.length;
0514: }
0515:
0516: if (isLeaf) {
0517: entries.add(new Entry(curEntryBuffer,
0518: curEntryLen));
0519: } else {
0520: nodeEntries.add(new NodeEntry(curEntryBuffer,
0521: curEntryLen));
0522: }
0523:
0524: // read any shared "compressed" bytes
0525: if (firstEntry) {
0526: firstEntry = false;
0527: if (numCompressedBytes > 0) {
0528: // FIXME we can't modify this index at this point in time
0529: _readOnly = true;
0530:
0531: valuePrefix = new byte[numCompressedBytes];
0532: indexPage.position(entryPos + lastStart);
0533: indexPage.get(valuePrefix);
0534: }
0535: }
0536:
0537: lastStart += length;
0538: }
0539: }
0540: }
0541: }
0542:
0543: /**
0544: * Returns an entry buffer containing the relevant data for an entry given
0545: * the valuePrefix.
0546: */
0547: private ByteBuffer getTempEntryBuffer(ByteBuffer indexPage,
0548: int entryLen, byte[] valuePrefix,
0549: TempBufferHolder tmpEntryBufferH) {
0550: ByteBuffer tmpEntryBuffer = tmpEntryBufferH.getBuffer(
0551: getPageChannel(), valuePrefix.length + entryLen);
0552:
0553: // combine valuePrefix and rest of entry from indexPage, then prep for
0554: // reading
0555: tmpEntryBuffer.put(valuePrefix);
0556: tmpEntryBuffer.put(indexPage.array(), indexPage.position(),
0557: entryLen);
0558: tmpEntryBuffer.flip();
0559:
0560: return tmpEntryBuffer;
0561: }
0562:
0563: /**
0564: * Adds a row to this index
0565: * <p>
0566: * Forces index initialization.
0567: *
0568: * @param row Row to add
0569: * @param rowId rowId of the row to be added
0570: */
0571: public void addRow(Object[] row, RowId rowId) throws IOException {
0572: int nullCount = countNullValues(row);
0573: boolean isNullEntry = (nullCount == _columns.size());
0574: if (shouldIgnoreNulls() && isNullEntry) {
0575: // nothing to do
0576: return;
0577: }
0578: if (isPrimaryKey() && (nullCount > 0)) {
0579: throw new IOException("Null value found in row "
0580: + Arrays.asList(row) + " for primary key index "
0581: + this );
0582: }
0583:
0584: // make sure we've parsed the entries
0585: initialize();
0586:
0587: Entry newEntry = new Entry(createEntryBytes(row), rowId);
0588: if (addEntry(newEntry, isNullEntry, row)) {
0589: ++_modCount;
0590: } else {
0591: LOG.warn("Added duplicate index entry " + newEntry
0592: + " for row: " + Arrays.asList(row));
0593: }
0594: }
0595:
0596: /**
0597: * Removes a row from this index
0598: * <p>
0599: * Forces index initialization.
0600: *
0601: * @param row Row to remove
0602: * @param rowId rowId of the row to be removed
0603: */
0604: public void deleteRow(Object[] row, RowId rowId) throws IOException {
0605: int nullCount = countNullValues(row);
0606: if (shouldIgnoreNulls() && (nullCount == _columns.size())) {
0607: // nothing to do
0608: return;
0609: }
0610:
0611: // make sure we've parsed the entries
0612: initialize();
0613:
0614: Entry oldEntry = new Entry(createEntryBytes(row), rowId);
0615: if (removeEntry(oldEntry)) {
0616: ++_modCount;
0617: } else {
0618: LOG.warn("Failed removing index entry " + oldEntry
0619: + " for row: " + Arrays.asList(row));
0620: }
0621: }
0622:
0623: /**
0624: * Gets a new cursor for this index.
0625: * <p>
0626: * Forces index initialization.
0627: */
0628: public EntryCursor cursor() throws IOException {
0629: return cursor(null, true, null, true);
0630: }
0631:
0632: /**
0633: * Gets a new cursor for this index, narrowed to the range defined by the
0634: * given startRow and endRow.
0635: * <p>
0636: * Forces index initialization.
0637: *
0638: * @param startRow the first row of data for the cursor, or {@code null} for
0639: * the first entry
0640: * @param startInclusive whether or not startRow is inclusive or exclusive
0641: * @param endRow the last row of data for the cursor, or {@code null} for
0642: * the last entry
0643: * @param endInclusive whether or not endRow is inclusive or exclusive
0644: */
0645: public EntryCursor cursor(Object[] startRow,
0646: boolean startInclusive, Object[] endRow,
0647: boolean endInclusive) throws IOException {
0648: initialize();
0649: Position startPos = FIRST_POSITION;
0650: byte[] startEntryBytes = null;
0651: if (startRow != null) {
0652: startEntryBytes = createEntryBytes(startRow);
0653: Entry startEntry = new Entry(startEntryBytes,
0654: (startInclusive ? RowId.FIRST_ROW_ID
0655: : RowId.LAST_ROW_ID));
0656: startPos = new Position(FIRST_ENTRY_IDX, startEntry);
0657: }
0658: Position endPos = LAST_POSITION;
0659: if (endRow != null) {
0660: // reuse startEntryBytes if startRow and endRow are same array. this is
0661: // common for "lookup" code
0662: byte[] endEntryBytes = ((startRow == endRow) ? startEntryBytes
0663: : createEntryBytes(endRow));
0664: Entry endEntry = new Entry(endEntryBytes,
0665: (endInclusive ? RowId.LAST_ROW_ID
0666: : RowId.FIRST_ROW_ID));
0667: endPos = new Position(LAST_ENTRY_IDX, endEntry);
0668: }
0669: return new EntryCursor(startPos, endPos);
0670: }
0671:
0672: /**
0673: * Finds the index of given entry in the _entries list.
0674: * @return the index if found, (-<insertion_point> - 1) if not found
0675: */
0676: private int findEntry(Entry entry) {
0677: return Collections.binarySearch(_entries, entry);
0678: }
0679:
0680: /**
0681: * Returns the valid insertion point for an index indicating a missing
0682: * entry.
0683: */
0684: private static int missingIndexToInsertionPoint(int idx) {
0685: return -(idx + 1);
0686: }
0687:
0688: /**
0689: * Adds an entry to the _entries list, maintaining the order.
0690: */
0691: private boolean addEntry(Entry newEntry, boolean isNullEntry,
0692: Object[] row) throws IOException {
0693: int idx = findEntry(newEntry);
0694: if (idx < 0) {
0695: // this is a new entry
0696: idx = missingIndexToInsertionPoint(idx);
0697:
0698: // determine if the addition of this entry would break the uniqueness
0699: // constraint. See isUnique() for some notes about uniqueness as
0700: // defined by Access.
0701: boolean isDupeEntry = (((idx > 0) && newEntry
0702: .equalsEntryBytes(_entries.get(idx - 1))) || ((idx < _entries
0703: .size()) && newEntry.equalsEntryBytes(_entries
0704: .get(idx))));
0705: if (isUnique() && !isNullEntry && isDupeEntry) {
0706: throw new IOException("New row " + Arrays.asList(row)
0707: + " violates uniqueness constraint for index "
0708: + this );
0709: }
0710:
0711: if (!isDupeEntry) {
0712: ++_uniqueEntryCount;
0713: }
0714:
0715: _entries.add(idx, newEntry);
0716: return true;
0717: }
0718: return false;
0719: }
0720:
0721: /**
0722: * Removes an entry from the _entries list, maintaining the order. Will
0723: * search by RowId if entry is not found in case a partial entry was
0724: * provided.
0725: */
0726: private boolean removeEntry(Entry oldEntry) {
0727: int idx = findEntry(oldEntry);
0728: boolean removed = false;
0729: if (idx < 0) {
0730: // the caller may have only read some of the row data, if this is the
0731: // case, just search for the page/row numbers
0732: for (Iterator<Entry> iter = _entries.iterator(); iter
0733: .hasNext();) {
0734: Entry entry = iter.next();
0735: if (entry.getRowId().equals(oldEntry.getRowId())) {
0736: iter.remove();
0737: removed = true;
0738: break;
0739: }
0740: }
0741: } else {
0742: // found it!
0743: _entries.remove(idx);
0744: removed = true;
0745: }
0746:
0747: return removed;
0748: }
0749:
0750: /**
0751: * Constructs an array of values appropriate for this index from the given
0752: * column values, expected to match the columns for this index.
0753: * @return the appropriate sparse array of data
0754: * @throws IllegalArgumentException if the wrong number of values are
0755: * provided
0756: */
0757: public Object[] constructIndexRowFromEntry(Object... values) {
0758: if (values.length != _columns.size()) {
0759: throw new IllegalArgumentException(
0760: "Wrong number of column values given "
0761: + values.length + ", expected "
0762: + _columns.size());
0763: }
0764: int valIdx = 0;
0765: Object[] idxRow = new Object[getTable().getColumnCount()];
0766: for (ColumnDescriptor col : _columns) {
0767: idxRow[col.getColumnIndex()] = values[valIdx++];
0768: }
0769: return idxRow;
0770: }
0771:
0772: /**
0773: * Constructs an array of values appropriate for this index from the given
0774: * column value.
0775: * @return the appropriate sparse array of data or {@code null} if not all
0776: * columns for this index were provided
0777: */
0778: public Object[] constructIndexRow(String colName, Object value) {
0779: return constructIndexRow(Collections.singletonMap(colName,
0780: value));
0781: }
0782:
0783: /**
0784: * Constructs an array of values appropriate for this index from the given
0785: * column values.
0786: * @return the appropriate sparse array of data or {@code null} if not all
0787: * columns for this index were provided
0788: */
0789: public Object[] constructIndexRow(Map<String, Object> row) {
0790: for (ColumnDescriptor col : _columns) {
0791: if (!row.containsKey(col.getName())) {
0792: return null;
0793: }
0794: }
0795:
0796: Object[] idxRow = new Object[getTable().getColumnCount()];
0797: for (ColumnDescriptor col : _columns) {
0798: idxRow[col.getColumnIndex()] = row.get(col.getName());
0799: }
0800: return idxRow;
0801: }
0802:
0803: @Override
0804: public String toString() {
0805: StringBuilder rtn = new StringBuilder();
0806: rtn.append("\tName: (" + _table.getName() + ") " + _name);
0807: rtn.append("\n\tNumber: " + _indexNumber);
0808: rtn.append("\n\tPage number: " + _pageNumber);
0809: rtn.append("\n\tIs Primary Key: " + isPrimaryKey());
0810: rtn.append("\n\tColumns: " + _columns);
0811: rtn.append("\n\tInitialized: " + _initialized);
0812: rtn.append("\n\tEntries: " + _entries);
0813: rtn.append("\n\n");
0814: return rtn.toString();
0815: }
0816:
0817: public int compareTo(Index other) {
0818: if (_indexNumber > other.getIndexNumber()) {
0819: return 1;
0820: } else if (_indexNumber < other.getIndexNumber()) {
0821: return -1;
0822: } else {
0823: return 0;
0824: }
0825: }
0826:
0827: /**
0828: * Determines the number of {@code null} values for this index from the
0829: * given row.
0830: */
0831: private int countNullValues(Object[] values) {
0832: if (values == null) {
0833: return _columns.size();
0834: }
0835:
0836: // annoyingly, the values array could come from different sources, one
0837: // of which will make it a different size than the other. we need to
0838: // handle both situations.
0839: int nullCount = 0;
0840: for (ColumnDescriptor col : _columns) {
0841: Object value = values[col.getColumnIndex()];
0842: if (col.isNullValue(value)) {
0843: ++nullCount;
0844: }
0845: }
0846:
0847: return nullCount;
0848: }
0849:
0850: /**
0851: * Creates the entry bytes for a row of values.
0852: */
0853: private byte[] createEntryBytes(Object[] values) throws IOException {
0854: if (values == null) {
0855: return null;
0856: }
0857:
0858: ByteArrayOutputStream bout = new ByteArrayOutputStream();
0859:
0860: // annoyingly, the values array could come from different sources, one
0861: // of which will make it a different size than the other. we need to
0862: // handle both situations.
0863: for (ColumnDescriptor col : _columns) {
0864: Object value = values[col.getColumnIndex()];
0865: col.writeValue(value, bout);
0866: }
0867:
0868: return bout.toByteArray();
0869: }
0870:
0871: /**
0872: * Flips the first bit in the byte at the given index.
0873: */
0874: private static byte[] flipFirstBitInByte(byte[] value, int index) {
0875: value[index] = (byte) (value[index] ^ 0x80);
0876:
0877: return value;
0878: }
0879:
0880: /**
0881: * Flips all the bits in the byte array.
0882: */
0883: private static byte[] flipBytes(byte[] value) {
0884: for (int i = 0; i < value.length; ++i) {
0885: value[i] = (byte) (~value[i]);
0886: }
0887: return value;
0888: }
0889:
0890: /**
0891: * Writes the value of the given column type to a byte array and returns it.
0892: */
0893: private static byte[] encodeNumberColumnValue(Object value,
0894: Column column) throws IOException {
0895: // always write in big endian order
0896: return column.write(value, 0, ByteOrder.BIG_ENDIAN).array();
0897: }
0898:
0899: /**
0900: * Converts an index value for a text column into the entry value (which
0901: * is based on a variety of nifty codes).
0902: */
0903: private static void writeNonNullIndexTextValue(Object value,
0904: ByteArrayOutputStream bout, boolean isAscending)
0905: throws IOException {
0906: // first, convert to string
0907: String str = Column.toCharSequence(value).toString();
0908:
0909: // all text columns (including memos) are only indexed up to the max
0910: // number of chars in a VARCHAR column
0911: if (str.length() > MAX_TEXT_INDEX_CHAR_LENGTH) {
0912: str = str.substring(0, MAX_TEXT_INDEX_CHAR_LENGTH);
0913: }
0914:
0915: ByteArrayOutputStream tmpBout = bout;
0916: if (!isAscending) {
0917: // we need to accumulate the bytes in a temp array in order to negate
0918: // them before writing them to the final array
0919: tmpBout = new ByteArrayOutputStream();
0920: }
0921:
0922: // now, convert each character to a "code" of one or more bytes
0923: List<ExtraCodes> unprintableCodes = null;
0924: List<ExtraCodes> internationalCodes = null;
0925: int charOffset = 0;
0926: for (int i = 0; i < str.length(); ++i) {
0927: char c = str.charAt(i);
0928: Character cKey = c;
0929:
0930: byte[] bytes = CODES.get(cKey);
0931: if (bytes != null) {
0932: // simple case, write the codes we found
0933: tmpBout.write(bytes);
0934: ++charOffset;
0935: continue;
0936: }
0937:
0938: bytes = UNPRINTABLE_CODES.get(cKey);
0939: if (bytes != null) {
0940: // we do not write anything to tmpBout
0941: if (bytes.length > 0) {
0942: if (unprintableCodes == null) {
0943: unprintableCodes = new LinkedList<ExtraCodes>();
0944: }
0945:
0946: // keep track of the extra codes for later
0947: unprintableCodes.add(new ExtraCodes(charOffset,
0948: bytes));
0949: }
0950:
0951: // note, we do _not_ increment the charOffset for unprintable chars
0952: continue;
0953: }
0954:
0955: InternationalCodes inatCodes = INTERNATIONAL_CODES
0956: .get(cKey);
0957: if (inatCodes != null) {
0958:
0959: // we write the "inline" portion of the international codes
0960: // immediately, and queue the extra codes for later
0961: tmpBout.write(inatCodes._inlineCodes);
0962:
0963: if (internationalCodes == null) {
0964: internationalCodes = new LinkedList<ExtraCodes>();
0965: }
0966:
0967: // keep track of the extra codes for later
0968: internationalCodes.add(new ExtraCodes(charOffset,
0969: inatCodes._extraCodes));
0970:
0971: ++charOffset;
0972: continue;
0973: }
0974:
0975: // bummer, out of luck
0976: throw new IOException("unmapped string index value " + c);
0977: }
0978:
0979: // write end text flag
0980: tmpBout.write(END_TEXT);
0981:
0982: boolean hasExtraText = ((unprintableCodes != null) || (internationalCodes != null));
0983: if (hasExtraText) {
0984:
0985: // we write all the international extra bytes first
0986: if (internationalCodes != null) {
0987:
0988: // we write a placeholder char for each non-international char before
0989: // the extra chars for the international char
0990: charOffset = 0;
0991: Iterator<ExtraCodes> iter = internationalCodes
0992: .iterator();
0993: while (iter.hasNext()) {
0994: ExtraCodes extraCodes = iter.next();
0995: while (charOffset < extraCodes._charOffset) {
0996: tmpBout.write(INTERNATIONAL_EXTRA_PLACEHOLDER);
0997: ++charOffset;
0998: }
0999: tmpBout.write(extraCodes._extraCodes);
1000: ++charOffset;
1001: }
1002: }
1003:
1004: // then we write all the unprintable extra bytes
1005: if (unprintableCodes != null) {
1006:
1007: // write a single prefix for all unprintable chars
1008: tmpBout.write(UNPRINTABLE_COMMON_PREFIX);
1009:
1010: // we write a whacky combo of bytes for each unprintable char which
1011: // includes a funky offset and extra char itself
1012: Iterator<ExtraCodes> iter = unprintableCodes.iterator();
1013: while (iter.hasNext()) {
1014: ExtraCodes extraCodes = iter.next();
1015: int offset = (UNPRINTABLE_COUNT_START + (UNPRINTABLE_COUNT_MULTIPLIER * extraCodes._charOffset))
1016: | UNPRINTABLE_OFFSET_FLAGS;
1017:
1018: // write offset as big-endian short
1019: tmpBout.write((offset >> 8) & 0xFF);
1020: tmpBout.write(offset & 0xFF);
1021:
1022: tmpBout.write(UNPRINTABLE_MIDFIX);
1023: tmpBout.write(extraCodes._extraCodes);
1024: }
1025: }
1026:
1027: }
1028:
1029: // handle descending order by inverting the bytes
1030: if (!isAscending) {
1031:
1032: // we actually write the end byte before flipping the bytes, and write
1033: // another one after flipping
1034: tmpBout.write(END_EXTRA_TEXT);
1035:
1036: // we actually wrote into a temporary array so that we can invert the
1037: // bytes before writing them to the final array
1038: bout.write(flipBytes(tmpBout.toByteArray()));
1039:
1040: }
1041:
1042: // write end extra text
1043: bout.write(END_EXTRA_TEXT);
1044: }
1045:
1046: /**
1047: * Creates one of the special index entries.
1048: */
1049: private static Entry createSpecialEntry(RowId rowId) {
1050: try {
1051: return new Entry((byte[]) null, rowId);
1052: } catch (IOException e) {
1053: // should never happen
1054: throw new IllegalStateException(e);
1055: }
1056: }
1057:
1058: /**
1059: * Constructs a ColumnDescriptor of the relevant type for the given Column.
1060: */
1061: private ColumnDescriptor newColumnDescriptor(Column col, byte flags)
1062: throws IOException {
1063: switch (col.getType()) {
1064: case TEXT:
1065: case MEMO:
1066: return new TextColumnDescriptor(col, flags);
1067: case INT:
1068: case LONG:
1069: case MONEY:
1070: return new IntegerColumnDescriptor(col, flags);
1071: case FLOAT:
1072: case DOUBLE:
1073: case SHORT_DATE_TIME:
1074: return new FloatingPointColumnDescriptor(col, flags);
1075: case NUMERIC:
1076: return new FixedPointColumnDescriptor(col, flags);
1077: case BYTE:
1078: return new ByteColumnDescriptor(col, flags);
1079: case BOOLEAN:
1080: return new BooleanColumnDescriptor(col, flags);
1081:
1082: default:
1083: // FIXME we can't modify this index at this point in time
1084: _readOnly = true;
1085: return new ReadOnlyColumnDescriptor(col, flags);
1086: }
1087: }
1088:
1089: /**
1090: * Information about the columns in an index. Also encodes new index
1091: * values.
1092: */
1093: public static abstract class ColumnDescriptor {
1094: private final Column _column;
1095: private final byte _flags;
1096:
1097: private ColumnDescriptor(Column column, byte flags)
1098: throws IOException {
1099: _column = column;
1100: _flags = flags;
1101: }
1102:
1103: public Column getColumn() {
1104: return _column;
1105: }
1106:
1107: public byte getFlags() {
1108: return _flags;
1109: }
1110:
1111: public boolean isAscending() {
1112: return ((getFlags() & ASCENDING_COLUMN_FLAG) != 0);
1113: }
1114:
1115: public int getColumnIndex() {
1116: return getColumn().getColumnIndex();
1117: }
1118:
1119: public String getName() {
1120: return getColumn().getName();
1121: }
1122:
1123: protected boolean isNullValue(Object value) {
1124: return (value == null);
1125: }
1126:
1127: protected final void writeValue(Object value,
1128: ByteArrayOutputStream bout) throws IOException {
1129: if (isNullValue(value)) {
1130: // write null value
1131: bout.write(getNullEntryFlag(isAscending()));
1132: return;
1133: }
1134:
1135: // write the start flag
1136: bout.write(getStartEntryFlag(isAscending()));
1137: // write the rest of the value
1138: writeNonNullValue(value, bout);
1139: }
1140:
1141: protected abstract void writeNonNullValue(Object value,
1142: ByteArrayOutputStream bout) throws IOException;
1143:
1144: @Override
1145: public String toString() {
1146: return "ColumnDescriptor " + getColumn() + "\nflags: "
1147: + getFlags();
1148: }
1149: }
1150:
1151: /**
1152: * ColumnDescriptor for integer based columns.
1153: */
1154: private static final class IntegerColumnDescriptor extends
1155: ColumnDescriptor {
1156: private IntegerColumnDescriptor(Column column, byte flags)
1157: throws IOException {
1158: super (column, flags);
1159: }
1160:
1161: @Override
1162: protected void writeNonNullValue(Object value,
1163: ByteArrayOutputStream bout) throws IOException {
1164: byte[] valueBytes = encodeNumberColumnValue(value,
1165: getColumn());
1166:
1167: // bit twiddling rules:
1168: // - isAsc => flipFirstBit
1169: // - !isAsc => flipFirstBit, flipBytes
1170:
1171: flipFirstBitInByte(valueBytes, 0);
1172: if (!isAscending()) {
1173: flipBytes(valueBytes);
1174: }
1175:
1176: bout.write(valueBytes);
1177: }
1178: }
1179:
1180: /**
1181: * ColumnDescriptor for floating point based columns.
1182: */
1183: private static final class FloatingPointColumnDescriptor extends
1184: ColumnDescriptor {
1185: private FloatingPointColumnDescriptor(Column column, byte flags)
1186: throws IOException {
1187: super (column, flags);
1188: }
1189:
1190: @Override
1191: protected void writeNonNullValue(Object value,
1192: ByteArrayOutputStream bout) throws IOException {
1193: byte[] valueBytes = encodeNumberColumnValue(value,
1194: getColumn());
1195:
1196: // determine if the number is negative by testing if the first bit is
1197: // set
1198: boolean isNegative = ((valueBytes[0] & 0x80) != 0);
1199:
1200: // bit twiddling rules:
1201: // isAsc && !isNeg => flipFirstBit
1202: // isAsc && isNeg => flipBytes
1203: // !isAsc && !isNeg => flipFirstBit, flipBytes
1204: // !isAsc && isNeg => nothing
1205:
1206: if (!isNegative) {
1207: flipFirstBitInByte(valueBytes, 0);
1208: }
1209: if (isNegative == isAscending()) {
1210: flipBytes(valueBytes);
1211: }
1212:
1213: bout.write(valueBytes);
1214: }
1215: }
1216:
1217: /**
1218: * ColumnDescriptor for fixed point based columns.
1219: */
1220: private static final class FixedPointColumnDescriptor extends
1221: ColumnDescriptor {
1222: private FixedPointColumnDescriptor(Column column, byte flags)
1223: throws IOException {
1224: super (column, flags);
1225: }
1226:
1227: @Override
1228: protected void writeNonNullValue(Object value,
1229: ByteArrayOutputStream bout) throws IOException {
1230: byte[] valueBytes = encodeNumberColumnValue(value,
1231: getColumn());
1232:
1233: // determine if the number is negative by testing if the first bit is
1234: // set
1235: boolean isNegative = ((valueBytes[0] & 0x80) != 0);
1236:
1237: // bit twiddling rules:
1238: // isAsc && !isNeg => setReverseSignByte
1239: // isAsc && isNeg => flipBytes, setReverseSignByte
1240: // !isAsc && !isNeg => flipBytes, setReverseSignByte
1241: // !isAsc && isNeg => setReverseSignByte
1242:
1243: if (isNegative == isAscending()) {
1244: flipBytes(valueBytes);
1245: }
1246:
1247: // reverse the sign byte (after any previous byte flipping)
1248: valueBytes[0] = (isNegative ? (byte) 0x00 : (byte) 0xFF);
1249:
1250: bout.write(valueBytes);
1251: }
1252: }
1253:
1254: /**
1255: * ColumnDescriptor for byte based columns.
1256: */
1257: private static final class ByteColumnDescriptor extends
1258: ColumnDescriptor {
1259: private ByteColumnDescriptor(Column column, byte flags)
1260: throws IOException {
1261: super (column, flags);
1262: }
1263:
1264: @Override
1265: protected void writeNonNullValue(Object value,
1266: ByteArrayOutputStream bout) throws IOException {
1267: byte[] valueBytes = encodeNumberColumnValue(value,
1268: getColumn());
1269:
1270: // bit twiddling rules:
1271: // - isAsc => nothing
1272: // - !isAsc => flipBytes
1273: if (!isAscending()) {
1274: flipBytes(valueBytes);
1275: }
1276:
1277: bout.write(valueBytes);
1278: }
1279: }
1280:
1281: /**
1282: * ColumnDescriptor for boolean columns.
1283: */
1284: private static final class BooleanColumnDescriptor extends
1285: ColumnDescriptor {
1286: private BooleanColumnDescriptor(Column column, byte flags)
1287: throws IOException {
1288: super (column, flags);
1289: }
1290:
1291: @Override
1292: protected boolean isNullValue(Object value) {
1293: // null values are handled as booleans
1294: return false;
1295: }
1296:
1297: @Override
1298: protected void writeNonNullValue(Object value,
1299: ByteArrayOutputStream bout) throws IOException {
1300: bout
1301: .write(Column.toBooleanValue(value) ? (isAscending() ? ASC_BOOLEAN_TRUE
1302: : DESC_BOOLEAN_TRUE)
1303: : (isAscending() ? ASC_BOOLEAN_FALSE
1304: : DESC_BOOLEAN_FALSE));
1305: }
1306: }
1307:
1308: /**
1309: * ColumnDescriptor for text based columns.
1310: */
1311: private static final class TextColumnDescriptor extends
1312: ColumnDescriptor {
1313: private TextColumnDescriptor(Column column, byte flags)
1314: throws IOException {
1315: super (column, flags);
1316: }
1317:
1318: @Override
1319: protected void writeNonNullValue(Object value,
1320: ByteArrayOutputStream bout) throws IOException {
1321: writeNonNullIndexTextValue(value, bout, isAscending());
1322: }
1323: }
1324:
1325: /**
1326: * ColumnDescriptor for columns which we cannot currently write.
1327: */
1328: private static final class ReadOnlyColumnDescriptor extends
1329: ColumnDescriptor {
1330: private ReadOnlyColumnDescriptor(Column column, byte flags)
1331: throws IOException {
1332: super (column, flags);
1333: }
1334:
1335: @Override
1336: protected void writeNonNullValue(Object value,
1337: ByteArrayOutputStream bout) throws IOException {
1338: throw new UnsupportedOperationException(
1339: "should not be called");
1340: }
1341: }
1342:
1343: /**
1344: * A single leaf entry in an index (points to a single row)
1345: */
1346: public static class Entry implements Comparable<Entry> {
1347: /** page/row on which this row is stored */
1348: private final RowId _rowId;
1349: /** the entry value */
1350: private final byte[] _entryBytes;
1351: /** comparable type for the entry */
1352: private final EntryType _type;
1353:
1354: /**
1355: * Create a new entry
1356: * @param entryBytes encoded bytes for this index entry
1357: * @param rowId rowId in which the row is stored
1358: */
1359: private Entry(byte[] entryBytes, RowId rowId)
1360: throws IOException {
1361: _rowId = rowId;
1362: _entryBytes = entryBytes;
1363: if (_entryBytes != null) {
1364: _type = ((_rowId.getType() == RowId.Type.NORMAL) ? EntryType.NORMAL
1365: : ((_rowId.getType() == RowId.Type.ALWAYS_FIRST) ? EntryType.FIRST_VALID
1366: : EntryType.LAST_VALID));
1367: } else if (!_rowId.isValid()) {
1368: // this is a "special" entry (first/last)
1369: _type = ((_rowId.getType() == RowId.Type.ALWAYS_FIRST) ? EntryType.ALWAYS_FIRST
1370: : EntryType.ALWAYS_LAST);
1371: } else {
1372: throw new IllegalArgumentException(
1373: "Values was null for valid entry");
1374: }
1375: }
1376:
1377: /**
1378: * Read an existing entry in from a buffer
1379: */
1380: private Entry(ByteBuffer buffer, int entryLen)
1381: throws IOException {
1382: this (buffer, entryLen, 0);
1383: }
1384:
1385: /**
1386: * Read an existing entry in from a buffer
1387: */
1388: private Entry(ByteBuffer buffer, int entryLen,
1389: int extraTrailingLen) throws IOException {
1390: // we need 4 trailing bytes for the rowId, plus whatever the caller
1391: // wants
1392: int colEntryLen = entryLen - (4 + extraTrailingLen);
1393:
1394: // read the entry bytes
1395: _entryBytes = new byte[colEntryLen];
1396: buffer.get(_entryBytes);
1397:
1398: // read the rowId
1399: int page = ByteUtil.get3ByteInt(buffer,
1400: ByteOrder.BIG_ENDIAN);
1401: int row = ByteUtil.getUnsignedByte(buffer);
1402:
1403: _rowId = new RowId(page, row);
1404: _type = EntryType.NORMAL;
1405: }
1406:
1407: public RowId getRowId() {
1408: return _rowId;
1409: }
1410:
1411: public EntryType getType() {
1412: return _type;
1413: }
1414:
1415: public boolean isValid() {
1416: return (_entryBytes != null);
1417: }
1418:
1419: protected final byte[] getEntryBytes() {
1420: return _entryBytes;
1421: }
1422:
1423: /**
1424: * Size of this entry in the db.
1425: */
1426: protected int size() {
1427: // need 4 trailing bytes for the rowId
1428: return _entryBytes.length + 4;
1429: }
1430:
1431: /**
1432: * Write this entry into a buffer
1433: */
1434: protected void write(ByteBuffer buffer) throws IOException {
1435: buffer.put(_entryBytes);
1436: ByteUtil.put3ByteInt(buffer, getRowId().getPageNumber(),
1437: ByteOrder.BIG_ENDIAN);
1438: buffer.put((byte) getRowId().getRowNumber());
1439: }
1440:
1441: protected final String entryBytesToString() {
1442: return (isValid() ? ", Bytes = "
1443: + ByteUtil.toHexString(
1444: ByteBuffer.wrap(_entryBytes),
1445: _entryBytes.length) : "");
1446: }
1447:
1448: @Override
1449: public String toString() {
1450: return "RowId = " + _rowId + entryBytesToString() + "\n";
1451: }
1452:
1453: @Override
1454: public int hashCode() {
1455: return _rowId.hashCode();
1456: }
1457:
1458: @Override
1459: public boolean equals(Object o) {
1460: return ((this == o) || ((o != null)
1461: && (getClass() == o.getClass()) && (compareTo((Entry) o) == 0)));
1462: }
1463:
1464: /**
1465: * @return {@code true} iff the entryBytes are equal between this
1466: * Entry and the given Entry
1467: */
1468: public boolean equalsEntryBytes(Entry o) {
1469: return (BYTE_CODE_COMPARATOR.compare(_entryBytes,
1470: o._entryBytes) == 0);
1471: }
1472:
1473: public int compareTo(Entry other) {
1474: if (this == other) {
1475: return 0;
1476: }
1477:
1478: if (isValid() && other.isValid()) {
1479:
1480: // comparing two valid entries. first, compare by actual byte values
1481: int entryCmp = BYTE_CODE_COMPARATOR.compare(
1482: _entryBytes, other._entryBytes);
1483: if (entryCmp != 0) {
1484: return entryCmp;
1485: }
1486:
1487: } else {
1488:
1489: // if the entries are of mixed validity (or both invalid), we defer
1490: // next to the EntryType
1491: int typeCmp = _type.compareTo(other._type);
1492: if (typeCmp != 0) {
1493: return typeCmp;
1494: }
1495: }
1496:
1497: // at this point we let the RowId decide the final result
1498: return _rowId.compareTo(other.getRowId());
1499: }
1500:
1501: }
1502:
1503: /**
1504: * A single node entry in an index (points to a sub-page in the index)
1505: */
1506: private final class NodeEntry extends Entry {
1507:
1508: /** index page number of the page to which this node entry refers */
1509: private final int _subPageNumber;
1510:
1511: /**
1512: * Read an existing node entry in from a buffer
1513: */
1514: private NodeEntry(ByteBuffer buffer, int entryLen)
1515: throws IOException {
1516: // we need 4 trailing bytes for the sub-page number
1517: super (buffer, entryLen, 4);
1518:
1519: _subPageNumber = ByteUtil.getInt(buffer,
1520: ByteOrder.BIG_ENDIAN);
1521: }
1522:
1523: public int getSubPageNumber() {
1524: return _subPageNumber;
1525: }
1526:
1527: @Override
1528: protected int size() {
1529: // need 4 trailing bytes for the sub-page number
1530: return super .size() + 4;
1531: }
1532:
1533: @Override
1534: protected void write(ByteBuffer buffer) throws IOException {
1535: super .write(buffer);
1536: ByteUtil.putInt(buffer, _subPageNumber,
1537: ByteOrder.BIG_ENDIAN);
1538: }
1539:
1540: @Override
1541: public String toString() {
1542: return ("Node RowId = " + getRowId() + ", SubPage = "
1543: + _subPageNumber + entryBytesToString() + "\n");
1544: }
1545:
1546: }
1547:
1548: /**
1549: * Utility class to traverse the entries in the Index. Remains valid in the
1550: * face of index entry modifications.
1551: */
1552: public final class EntryCursor {
1553: /** handler for moving the page cursor forward */
1554: private final DirHandler _forwardDirHandler = new ForwardDirHandler();
1555: /** handler for moving the page cursor backward */
1556: private final DirHandler _reverseDirHandler = new ReverseDirHandler();
1557: /** the first (exclusive) row id for this cursor */
1558: private final Position _firstPos;
1559: /** the last (exclusive) row id for this cursor */
1560: private final Position _lastPos;
1561: /** the first valid index for this cursor */
1562: private int _minIndex;
1563: /** the last valid index for this cursor */
1564: private int _maxIndex;
1565: /** the current entry */
1566: private Position _curPos;
1567: /** the previous entry */
1568: private Position _prevPos;
1569: /** the last read modification count on the Index. we track this so that
1570: the cursor can detect updates to the index while traversing and act
1571: accordingly */
1572: private int _lastModCount;
1573:
1574: private EntryCursor(Position firstPos, Position lastPos) {
1575: _firstPos = firstPos;
1576: _lastPos = lastPos;
1577: // force bounds to be updated
1578: _lastModCount = Index.this ._modCount - 1;
1579: reset();
1580: }
1581:
1582: public Index getIndex() {
1583: return Index.this ;
1584: }
1585:
1586: /**
1587: * Returns the first entry (exclusive) as defined by this cursor.
1588: */
1589: public Entry getFirstEntry() {
1590: return _firstPos.getEntry();
1591: }
1592:
1593: /**
1594: * Returns the last entry (exclusive) as defined by this cursor.
1595: */
1596: public Entry getLastEntry() {
1597: return _lastPos.getEntry();
1598: }
1599:
1600: /**
1601: * Returns the DirHandler for the given direction
1602: */
1603: private DirHandler getDirHandler(boolean moveForward) {
1604: return (moveForward ? _forwardDirHandler
1605: : _reverseDirHandler);
1606: }
1607:
1608: /**
1609: * Returns {@code true} if this cursor is up-to-date with respect to its
1610: * index.
1611: */
1612: public boolean isUpToDate() {
1613: return (Index.this ._modCount == _lastModCount);
1614: }
1615:
1616: public void reset() {
1617: beforeFirst();
1618: }
1619:
1620: public void beforeFirst() {
1621: reset(true);
1622: }
1623:
1624: public void afterLast() {
1625: reset(false);
1626: }
1627:
1628: protected void reset(boolean moveForward) {
1629: _curPos = getDirHandler(moveForward).getBeginningPosition();
1630: _prevPos = _curPos;
1631: if (!isUpToDate()) {
1632: // update bounds
1633: updateBounds();
1634: _lastModCount = Index.this ._modCount;
1635: }
1636: }
1637:
1638: /**
1639: * Repositions the cursor so that the next row will be the first entry
1640: * >= the given row.
1641: */
1642: public void beforeEntry(Object[] row) throws IOException {
1643: restorePosition(new Entry(Index.this .createEntryBytes(row),
1644: RowId.FIRST_ROW_ID));
1645: }
1646:
1647: /**
1648: * Repositions the cursor so that the previous row will be the first
1649: * entry <= the given row.
1650: */
1651: public void afterEntry(Object[] row) throws IOException {
1652: restorePosition(new Entry(Index.this .createEntryBytes(row),
1653: RowId.LAST_ROW_ID));
1654: }
1655:
1656: /**
1657: * @return valid entry if there was a next entry,
1658: * {@code #getLastEntry} otherwise
1659: */
1660: public Entry getNextEntry() {
1661: return getAnotherEntry(true);
1662: }
1663:
1664: /**
1665: * @return valid entry if there was a next entry,
1666: * {@code #getFirstEntry} otherwise
1667: */
1668: public Entry getPreviousEntry() {
1669: return getAnotherEntry(false);
1670: }
1671:
1672: /**
1673: * Restores a current position for the cursor (current position becomes
1674: * previous position).
1675: */
1676: private void restorePosition(Entry curEntry) {
1677: restorePosition(curEntry, _curPos.getEntry());
1678: }
1679:
1680: /**
1681: * Restores a current and previous position for the cursor.
1682: */
1683: protected void restorePosition(Entry curEntry, Entry prevEntry) {
1684: if (!curEntry.equals(_curPos.getEntry())
1685: || !prevEntry.equals(_prevPos.getEntry())) {
1686: _prevPos = updatePosition(prevEntry);
1687: _curPos = updatePosition(curEntry);
1688: if (!isUpToDate()) {
1689: updateBounds();
1690: _lastModCount = Index.this ._modCount;
1691: }
1692: } else {
1693: checkForModification();
1694: }
1695: }
1696:
1697: /**
1698: * Checks the index for modifications and updates state accordingly.
1699: */
1700: private void checkForModification() {
1701: if (!isUpToDate()) {
1702: _prevPos = updatePosition(_prevPos.getEntry());
1703: _curPos = updatePosition(_curPos.getEntry());
1704: updateBounds();
1705: _lastModCount = Index.this ._modCount;
1706: }
1707: }
1708:
1709: private void updateBounds() {
1710: int idx = findEntry(_firstPos.getEntry());
1711: if (idx < 0) {
1712: idx = missingIndexToInsertionPoint(idx);
1713: }
1714: _minIndex = idx;
1715:
1716: idx = findEntry(_lastPos.getEntry());
1717: if (idx < 0) {
1718: idx = missingIndexToInsertionPoint(idx) - 1;
1719: }
1720: _maxIndex = idx;
1721: }
1722:
1723: /**
1724: * Gets an up-to-date position for the given entry.
1725: */
1726: private Position updatePosition(Entry entry) {
1727: if (entry.isValid()) {
1728:
1729: // find the new position for this entry
1730: int curIdx = findEntry(entry);
1731: boolean between = false;
1732: if (curIdx < 0) {
1733: // given entry was not found exactly. our current position is now
1734: // really between two indexes, but we cannot support that as an
1735: // integer value so we set a flag instead
1736: curIdx = missingIndexToInsertionPoint(curIdx);
1737: between = true;
1738: }
1739:
1740: if (curIdx < _minIndex) {
1741: curIdx = _minIndex;
1742: between = true;
1743: } else if (curIdx > _maxIndex) {
1744: curIdx = _maxIndex + 1;
1745: between = true;
1746: }
1747:
1748: return new Position(curIdx, entry, between);
1749:
1750: } else if (entry.equals(_firstPos.getEntry())) {
1751: return _firstPos;
1752: } else if (entry.equals(_lastPos.getEntry())) {
1753: return _lastPos;
1754: } else {
1755: throw new IllegalArgumentException(
1756: "Invalid entry given: " + entry);
1757: }
1758: }
1759:
1760: /**
1761: * Gets another entry in the given direction, returning the new entry.
1762: */
1763: private Entry getAnotherEntry(boolean moveForward) {
1764: DirHandler handler = getDirHandler(moveForward);
1765: if (_curPos.equals(handler.getEndPosition())) {
1766: if (!isUpToDate()) {
1767: restorePosition(_prevPos.getEntry());
1768: // drop through and retry moving to another entry
1769: } else {
1770: // at end, no more
1771: return _curPos.getEntry();
1772: }
1773: }
1774:
1775: checkForModification();
1776:
1777: _prevPos = _curPos;
1778: _curPos = handler.getAnotherPosition(_curPos.getIndex(),
1779: _curPos.isBetween());
1780: return _curPos.getEntry();
1781: }
1782:
1783: @Override
1784: public String toString() {
1785: return getClass().getSimpleName() + " CurPosition "
1786: + _curPos + ", PrevPosition " + _prevPos;
1787: }
1788:
1789: /**
1790: * Handles moving the cursor in a given direction. Separates cursor
1791: * logic from value storage.
1792: */
1793: private abstract class DirHandler {
1794: public abstract Position getAnotherPosition(int curIdx,
1795: boolean between);
1796:
1797: public abstract Position getBeginningPosition();
1798:
1799: public abstract Position getEndPosition();
1800:
1801: protected final Position newPosition(int curIdx) {
1802: return new Position(curIdx, _entries.get(curIdx));
1803: }
1804:
1805: protected final Position newForwardPosition(int curIdx) {
1806: return ((curIdx <= _maxIndex) ? newPosition(curIdx)
1807: : _lastPos);
1808: }
1809:
1810: protected final Position newReversePosition(int curIdx) {
1811: return ((curIdx >= _minIndex) ? newPosition(curIdx)
1812: : _firstPos);
1813: }
1814: }
1815:
1816: /**
1817: * Handles moving the cursor forward.
1818: */
1819: private final class ForwardDirHandler extends DirHandler {
1820: @Override
1821: public Position getAnotherPosition(int curIdx,
1822: boolean between) {
1823: // note, curIdx does not need to be advanced if it was pointing at a
1824: // between position
1825: if (!between) {
1826: curIdx = ((curIdx == getBeginningPosition()
1827: .getIndex()) ? _minIndex : (curIdx + 1));
1828: }
1829: return newForwardPosition(curIdx);
1830: }
1831:
1832: @Override
1833: public Position getBeginningPosition() {
1834: return _firstPos;
1835: }
1836:
1837: @Override
1838: public Position getEndPosition() {
1839: return _lastPos;
1840: }
1841: }
1842:
1843: /**
1844: * Handles moving the cursor backward.
1845: */
1846: private final class ReverseDirHandler extends DirHandler {
1847: @Override
1848: public Position getAnotherPosition(int curIdx,
1849: boolean between) {
1850: // note, we ignore the between flag here because the index will be
1851: // pointing at the correct next index in either the between or
1852: // non-between case
1853: curIdx = ((curIdx == getBeginningPosition().getIndex()) ? _maxIndex
1854: : (curIdx - 1));
1855: return newReversePosition(curIdx);
1856: }
1857:
1858: @Override
1859: public Position getBeginningPosition() {
1860: return _lastPos;
1861: }
1862:
1863: @Override
1864: public Position getEndPosition() {
1865: return _firstPos;
1866: }
1867: }
1868: }
1869:
1870: /**
1871: * Simple value object for maintaining some cursor state.
1872: */
1873: private static class Position {
1874: /** the last known index of the given entry */
1875: private final int _idx;
1876: /** the entry at the given index */
1877: private final Entry _entry;
1878: /** {@code true} if this entry does not currently exist in the entry list,
1879: {@code false} otherwise */
1880: private final boolean _between;
1881:
1882: private Position(int idx, Entry entry) {
1883: this (idx, entry, false);
1884: }
1885:
1886: private Position(int idx, Entry entry, boolean between) {
1887: _idx = idx;
1888: _entry = entry;
1889: _between = between;
1890: }
1891:
1892: public int getIndex() {
1893: return _idx;
1894: }
1895:
1896: public Entry getEntry() {
1897: return _entry;
1898: }
1899:
1900: public boolean isBetween() {
1901: return _between;
1902: }
1903:
1904: @Override
1905: public int hashCode() {
1906: return _entry.hashCode();
1907: }
1908:
1909: @Override
1910: public boolean equals(Object o) {
1911: return ((this == o) || ((o != null)
1912: && (getClass() == o.getClass())
1913: && (_idx == ((Position) o)._idx)
1914: && _entry.equals(((Position) o)._entry) && (_between == ((Position) o)._between)));
1915: }
1916:
1917: @Override
1918: public String toString() {
1919: return "Idx = " + _idx + ", Entry = " + _entry
1920: + ", Between = " + _between;
1921: }
1922: }
1923:
1924: private static final class ExtraCodes {
1925: public final int _charOffset;
1926: public final byte[] _extraCodes;
1927:
1928: private ExtraCodes(int charOffset, byte[] extraCodes) {
1929: _charOffset = charOffset;
1930: _extraCodes = extraCodes;
1931: }
1932: }
1933:
1934: }
|