Coverage Report

 /*
 Copyright (c) 2005 Health Market Science, Inc.
 
 This library is free software; you can redistribute it and/or
 modify it under the terms of the GNU Lesser General Public
 License as published by the Free Software Foundation; either
 version 2.1 of the License, or (at your option) any later version.
 
 This library is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 Lesser General Public License for more details.
 
 You should have received a copy of the GNU Lesser General Public
 License along with this library; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307
 USA
 
 You can contact Health Market Science at info@healthmarketscience.com
 or at the following address:
 
 Health Market Science
 2700 Horizon Drive
 Suite 200
 King of Prussia, PA 19406
 */
 
 package com.healthmarketscience.jackcess;
 
 import java.io.ByteArrayOutputStream;
 import java.io.IOException;
 import java.nio.ByteBuffer;
 import java.nio.ByteOrder;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
 
 import org.apache.commons.logging.Log;
 import org.apache.commons.logging.LogFactory;
 
 import static com.healthmarketscience.jackcess.IndexCodes.*;
 
 
 /**
  * Access table index
  * @author Tim McCune
  */
 public abstract class Index implements Comparable<Index> {
   
   protected static final Log LOG = LogFactory.getLog(Index.class);
 
   /** special entry which is less than any other entry */
   public static final Entry FIRST_ENTRY =
     createSpecialEntry(RowId.FIRST_ROW_ID);
   
   /** special entry which is greater than any other entry */
   public static final Entry LAST_ENTRY =
     createSpecialEntry(RowId.LAST_ROW_ID);
   
   protected static final int INVALID_INDEX_PAGE_NUMBER = 0;          
   
   /** Max number of columns in an index */
   private static final int MAX_COLUMNS = 10;
   
   protected static final byte[] EMPTY_PREFIX = new byte[0];
 
   private static final short COLUMN_UNUSED = -1;
 
   private static final byte ASCENDING_COLUMN_FLAG = (byte)0x01;
 
   private static final byte UNIQUE_INDEX_FLAG = (byte)0x01;
   private static final byte IGNORE_NULLS_INDEX_FLAG = (byte)0x02;
 
   /** index type for primary key indexes */
   private static final byte PRIMARY_KEY_INDEX_TYPE = (byte)1;
   
   /** index type for foreign key indexes */
   private static final byte FOREIGN_KEY_INDEX_TYPE = (byte)2;
 
   private static final int MAX_TEXT_INDEX_CHAR_LENGTH =
     (JetFormat.TEXT_FIELD_MAX_LENGTH / JetFormat.TEXT_FIELD_UNIT_SIZE);
   
   /** type attributes for Entries which simplify comparisons */
   public enum EntryType {
     /** comparable type indicating this Entry should always compare less than
         valid RowIds */
     ALWAYS_FIRST,
     /** comparable type indicating this Entry should always compare less than
         other valid entries with equal entryBytes */
     FIRST_VALID,
     /** comparable type indicating this RowId should always compare
         normally */
     NORMAL,
     /** comparable type indicating this Entry should always compare greater
         than other valid entries with equal entryBytes */
     LAST_VALID,
     /** comparable type indicating this Entry should always compare greater
         than valid RowIds */
     ALWAYS_LAST;
   }
   
   static final Comparator<byte[]> BYTE_CODE_COMPARATOR =
     new Comparator<byte[]>() {
       public int compare(byte[] left, byte[] right) {
         if(left == right) {
           return 0;
         }
         if(left == null) {
           return -1;
         }
         if(right == null) {
           return 1;
         }
 
         int len = Math.min(left.length, right.length);
         int pos = 0;
         while((pos < len) && (left[pos] == right[pos])) {
           ++pos;
         }
         if(pos < len) {
           return ((ByteUtil.asUnsignedByte(left[pos]) <
                    ByteUtil.asUnsignedByte(right[pos])) ? -1 : 1);
         }
         return ((left.length < right.length) ? -1 :
                 ((left.length > right.length) ? 1 : 0));
       }
     };
         
   
   /** owning table */
   private final Table _table;
   /** Page number of the root index data */
   private int _rootPageNumber;
   /** offset within the tableDefinition buffer of the uniqueEntryCount for
       this index */
   private final int _uniqueEntryCountOffset;
   /** The number of unique entries which have been added to this index.  note,
       however, that it is never decremented, only incremented (as observed in
       Access). */
   private int _uniqueEntryCount;
   /** List of columns and flags */
   private final List<ColumnDescriptor> _columns =
     new ArrayList<ColumnDescriptor>();
   /** 0-based index number */
   private int _indexNumber;
   /** flags for this index */
   private byte _indexFlags;
   /** the type of the index */
   private byte _indexType;
   /** Index name */
   private String _name;
   /** <code>true</code> if the index entries have been initialized,
       <code>false</code> otherwise */
   private boolean _initialized;
   /** modification count for the table, keeps cursors up-to-date */
   private int _modCount;
   /** temp buffer used to read/write the index pages */
   private final TempBufferHolder _indexBufferH =
     TempBufferHolder.newHolder(TempBufferHolder.Type.SOFT, true);
   /** max size for all the entries written to a given index data page */
   private final int _maxPageEntrySize;
   /** FIXME, for now, we can't write multi-page indexes or indexes using the funky primary key compression scheme */
   boolean _readOnly;
   
   protected Index(Table table, int uniqueEntryCount,
                   int uniqueEntryCountOffset)
   {
     _table  = table;
     _uniqueEntryCount = uniqueEntryCount;
     _uniqueEntryCountOffset = uniqueEntryCountOffset;
     _maxPageEntrySize = calcMaxPageEntrySize(_table.getFormat());
   }
 
   public Table getTable() {
     return _table;
   }
   
   public JetFormat getFormat() {
     return getTable().getFormat();
   }
 
   public PageChannel getPageChannel() {
     return getTable().getPageChannel();
   }
 
   public void setIndexNumber(int indexNumber) {
     _indexNumber = indexNumber;
   }
 
   public int getIndexNumber() {
     return _indexNumber;
   }
 
   public void setIndexType(byte indexType) {
     _indexType = indexType;
   }
 
   public byte getIndexFlags() {
     return _indexFlags;
   }
   
   public int getUniqueEntryCount() {
     return _uniqueEntryCount;
   }
 
   public int getUniqueEntryCountOffset() {
     return _uniqueEntryCountOffset;
   }
 
   public String getName() {
     return _name;
   }
   
   public void setName(String name) {
     _name = name;
   }
 
   public boolean isPrimaryKey() {
     return _indexType == PRIMARY_KEY_INDEX_TYPE;
   }
 
   public boolean isForeignKey() {
     return _indexType == FOREIGN_KEY_INDEX_TYPE;
   }
 
   /**
    * Whether or not {@code null} values are actually recorded in the index.
    */
   public boolean shouldIgnoreNulls() {
     return((_indexFlags & IGNORE_NULLS_INDEX_FLAG) != 0);
   }
 
   /**
    * Whether or not index entries must be unique.
    * <p>
    * Some notes about uniqueness:
    * <ul>
    * <li>Access does not seem to consider multiple {@code null} entries
    *     invalid for a unique index</li>
    * <li>text indexes collapse case, and Access seems to compare <b>only</b>
    *     the index entry bytes, therefore two strings which differ only in
    *     case <i>will violate</i> the unique constraint</li>
    * </ul>
    */
   public boolean isUnique() {
     return(isPrimaryKey() || ((_indexFlags & UNIQUE_INDEX_FLAG) != 0));
   }
   
   /**
    * Returns the Columns for this index (unmodifiable)
    */
   public List<ColumnDescriptor> getColumns() {
     return Collections.unmodifiableList(_columns);
   }
 
   /**
    * Whether or not the complete index state has been read.
    */
   public boolean isInitialized() {
     return _initialized;
   }
 
   protected int getRootPageNumber() {
     return _rootPageNumber;
   }
 
   protected void setReadOnly() {
     _readOnly = true;
   }
 
   protected int getMaxPageEntrySize() {
     return _maxPageEntrySize;
   }
 
   /**
    * Returns the number of index entries in the index.  Only called by unit
    * tests.
    * <p>
    * Forces index initialization.
    */
   protected int getEntryCount()
     throws IOException
   {
     initialize();
     EntryCursor cursor = cursor();
     Entry endEntry = cursor.getLastEntry();
     int count = 0;
     while(!endEntry.equals(cursor.getNextEntry())) {
       ++count;
     }
     return count;
   }
   
   /**
    * Forces initialization of this index (actual parsing of index pages).
    * normally, the index will not be initialized until the entries are
    * actually needed.
    */
   public void initialize() throws IOException {
     if(!_initialized) {
       readIndexEntries();
       _initialized = true;
     }
   }
 
   /**
    * Writes the current index state to the database.
    * <p>
    * Forces index initialization.
    */
   public void update() throws IOException
   {
     // make sure we've parsed the entries
     initialize();
     
     if(_readOnly) {
       throw new UnsupportedOperationException(
           "FIXME cannot write indexes of this type yet, see Database javadoc for info on enabling large index support");
     }
     updateImpl();
   }
 
   /**
    * Read the index info from a tableBuffer
    * @param tableBuffer table definition buffer to read from initial info
    * @param availableColumns Columns that this index may use
    */
   public void read(ByteBuffer tableBuffer, List<Column> availableColumns)
     throws IOException
   {
     for (int i = 0; i < MAX_COLUMNS; i++) {
       short columnNumber = tableBuffer.getShort();
       byte colFlags = tableBuffer.get();
       if (columnNumber != COLUMN_UNUSED) {
         // find the desired column by column number (which is not necessarily
         // the same as the column index)
         Column idxCol = null;
         for(Column col : availableColumns) {
           if(col.getColumnNumber() == columnNumber) {
             idxCol = col;
             break;
           }
         }
         if(idxCol == null) {
           throw new IOException("Could not find column with number "
                                 + columnNumber + " for index " + getName());
         }
         _columns.add(newColumnDescriptor(idxCol, colFlags));
       }
     }
     tableBuffer.getInt(); //Forward past Unknown
     _rootPageNumber = tableBuffer.getInt();
     tableBuffer.getInt(); //Forward past Unknown
     _indexFlags = tableBuffer.get();
     tableBuffer.position(tableBuffer.position() + 5);  //Forward past other stuff
   }
 
   /**
    * Adds a row to this index
    * <p>
    * Forces index initialization.
    * 
    * @param row Row to add
    * @param rowId rowId of the row to be added
    */
   public void addRow(Object[] row, RowId rowId)
     throws IOException
   {
     int nullCount = countNullValues(row);
     boolean isNullEntry = (nullCount == _columns.size());
     if(shouldIgnoreNulls() && isNullEntry) {
       // nothing to do
       return;
     }
     if(isPrimaryKey() && (nullCount > 0)) {
       throw new IOException("Null value found in row " + Arrays.asList(row)
                             + " for primary key index " + this);
     }
     
     // make sure we've parsed the entries
     initialize();
 
     Entry newEntry = new Entry(createEntryBytes(row), rowId);
     if(addEntry(newEntry, isNullEntry, row)) {
       ++_modCount;
     } else {
       LOG.warn("Added duplicate index entry " + newEntry + " for row: " +
                Arrays.asList(row));
     }
   }
 
   /**
    * Adds an entry to the correct index dataPage, maintaining the order.
    */
   private boolean addEntry(Entry newEntry, boolean isNullEntry, Object[] row)
     throws IOException
   {
     DataPage dataPage = findDataPage(newEntry);
     int idx = dataPage.findEntry(newEntry);
     if(idx < 0) {
       // this is a new entry
       idx = missingIndexToInsertionPoint(idx);
 
       Position newPos = new Position(dataPage, idx, newEntry, true);
       Position nextPos = getNextPosition(newPos);
       Position prevPos = getPreviousPosition(newPos);
       
       // determine if the addition of this entry would break the uniqueness
       // constraint.  See isUnique() for some notes about uniqueness as
       // defined by Access.
       boolean isDupeEntry =
         (((nextPos != null) &&
           newEntry.equalsEntryBytes(nextPos.getEntry())) ||
           ((prevPos != null) &&
            newEntry.equalsEntryBytes(prevPos.getEntry())));
       if(isUnique() && !isNullEntry && isDupeEntry)
       {
         throw new IOException(
             "New row " + Arrays.asList(row) +
             " violates uniqueness constraint for index " + this);
       }
 
       if(!isDupeEntry) {
         ++_uniqueEntryCount;
       }
 
       dataPage.addEntry(idx, newEntry);
       return true;
     }
     return false;
   }
   
   /**
    * Removes a row from this index
    * <p>
    * Forces index initialization.
    * 
    * @param row Row to remove
    * @param rowId rowId of the row to be removed
    */
   public void deleteRow(Object[] row, RowId rowId)
     throws IOException
   {
     int nullCount = countNullValues(row);
     if(shouldIgnoreNulls() && (nullCount == _columns.size())) {
       // nothing to do
       return;
     }
     
     // make sure we've parsed the entries
     initialize();
 
     Entry oldEntry = new Entry(createEntryBytes(row), rowId);
     if(removeEntry(oldEntry)) {
       ++_modCount;
     } else {
       LOG.warn("Failed removing index entry " + oldEntry + " for row: " +
                Arrays.asList(row));
     }
   }
 
   /**
    * Removes an entry from the relevant index dataPage, maintaining the order.
    * Will search by RowId if entry is not found (in case a partial entry was
    * provided).
    */
   private boolean removeEntry(Entry oldEntry)
     throws IOException
   {
     DataPage dataPage = findDataPage(oldEntry);
     int idx = dataPage.findEntry(oldEntry);
     boolean doRemove = false;
     if(idx < 0) {
       // the caller may have only read some of the row data, if this is the
       // case, just search for the page/row numbers
       // FIXME, we could force caller to get relevant values?
       EntryCursor cursor = cursor();
       Position tmpPos = null;
       Position endPos = cursor._lastPos;
       while(!endPos.equals(
                 tmpPos = cursor.getAnotherPosition(Cursor.MOVE_FORWARD))) {
         if(tmpPos.getEntry().getRowId().equals(oldEntry.getRowId())) {
           dataPage = tmpPos.getDataPage();
           idx = tmpPos.getIndex();
           doRemove = true;
           break;
         }
       }
     } else {
       doRemove = true;
     }
 
     if(doRemove) {
       // found it!
       dataPage.removeEntry(idx);
     }
     
     return doRemove;
   }
       
   /**
    * Gets a new cursor for this index.
    * <p>
    * Forces index initialization.
    */
   public EntryCursor cursor()
     throws IOException
   {
     return cursor(null, true, null, true);
   }
   
   /**
    * Gets a new cursor for this index, narrowed to the range defined by the
    * given startRow and endRow.
    * <p>
    * Forces index initialization.
    * 
    * @param startRow the first row of data for the cursor, or {@code null} for
    *                 the first entry
    * @param startInclusive whether or not startRow is inclusive or exclusive
    * @param endRow the last row of data for the cursor, or {@code null} for
    *               the last entry
    * @param endInclusive whether or not endRow is inclusive or exclusive
    */
   public EntryCursor cursor(Object[] startRow,
                             boolean startInclusive,
                             Object[] endRow,
                             boolean endInclusive)
     throws IOException
   {
     initialize();
     Entry startEntry = FIRST_ENTRY;
     byte[] startEntryBytes = null;
     if(startRow != null) {
       startEntryBytes = createEntryBytes(startRow);
       startEntry = new Entry(startEntryBytes,
                              (startInclusive ?
                               RowId.FIRST_ROW_ID : RowId.LAST_ROW_ID));
     }
     Entry endEntry = LAST_ENTRY;
     if(endRow != null) {
       // reuse startEntryBytes if startRow and endRow are same array.  this is
       // common for "lookup" code
       byte[] endEntryBytes = ((startRow == endRow) ?
                               startEntryBytes :
                               createEntryBytes(endRow));
       endEntry = new Entry(endEntryBytes,
                            (endInclusive ?
                             RowId.LAST_ROW_ID : RowId.FIRST_ROW_ID));
     }
     return new EntryCursor(findEntryPosition(startEntry),
                            findEntryPosition(endEntry));
   }
 
   private Position findEntryPosition(Entry entry)
     throws IOException
   {
     DataPage dataPage = findDataPage(entry);
     int idx = dataPage.findEntry(entry);
     boolean between = false;

1		/*
2		Copyright (c) 2005 Health Market Science, Inc.
3
4		This library is free software; you can redistribute it and/or
5		modify it under the terms of the GNU Lesser General Public
6		License as published by the Free Software Foundation; either
7		version 2.1 of the License, or (at your option) any later version.
8
9		This library is distributed in the hope that it will be useful,
10		but WITHOUT ANY WARRANTY; without even the implied warranty of
11		MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12		Lesser General Public License for more details.
13
14		You should have received a copy of the GNU Lesser General Public
15		License along with this library; if not, write to the Free Software
16		Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
17		USA
18
19		You can contact Health Market Science at info@healthmarketscience.com
20		or at the following address:
21
22		Health Market Science
23		2700 Horizon Drive
24		Suite 200
25		King of Prussia, PA 19406
26		*/
27
28		package com.healthmarketscience.jackcess;
29
30		import java.io.ByteArrayOutputStream;
31		import java.io.IOException;
32		import java.nio.ByteBuffer;
33		import java.nio.ByteOrder;
34		import java.util.ArrayList;
35		import java.util.Arrays;
36		import java.util.Collections;
37		import java.util.Comparator;
38		import java.util.Iterator;
39		import java.util.LinkedList;
40		import java.util.List;
41		import java.util.Map;
42
43		import org.apache.commons.logging.Log;
44		import org.apache.commons.logging.LogFactory;
45
46		import static com.healthmarketscience.jackcess.IndexCodes.*;
47
48
49		/**
50		* Access table index
51		* @author Tim McCune
52		*/
53	4050028	public abstract class Index implements Comparable<Index> {
54
55	1	protected static final Log LOG = LogFactory.getLog(Index.class);
56
57		/** special entry which is less than any other entry */
58	1	public static final Entry FIRST_ENTRY =
59		createSpecialEntry(RowId.FIRST_ROW_ID);
60
61		/** special entry which is greater than any other entry */
62	1	public static final Entry LAST_ENTRY =
63		createSpecialEntry(RowId.LAST_ROW_ID);
64
65		protected static final int INVALID_INDEX_PAGE_NUMBER = 0;
66
67		/** Max number of columns in an index */
68		private static final int MAX_COLUMNS = 10;
69
70	1	protected static final byte[] EMPTY_PREFIX = new byte[0];
71
72		private static final short COLUMN_UNUSED = -1;
73
74		private static final byte ASCENDING_COLUMN_FLAG = (byte)0x01;
75
76		private static final byte UNIQUE_INDEX_FLAG = (byte)0x01;
77		private static final byte IGNORE_NULLS_INDEX_FLAG = (byte)0x02;
78
79		/** index type for primary key indexes */
80		private static final byte PRIMARY_KEY_INDEX_TYPE = (byte)1;
81
82		/** index type for foreign key indexes */
83		private static final byte FOREIGN_KEY_INDEX_TYPE = (byte)2;
84
85		private static final int MAX_TEXT_INDEX_CHAR_LENGTH =
86		(JetFormat.TEXT_FIELD_MAX_LENGTH / JetFormat.TEXT_FIELD_UNIT_SIZE);
87
88		/** type attributes for Entries which simplify comparisons */
89	6	public enum EntryType {
90		/** comparable type indicating this Entry should always compare less than
91		valid RowIds */
92	1	ALWAYS_FIRST,
93		/** comparable type indicating this Entry should always compare less than
94		other valid entries with equal entryBytes */
95	1	FIRST_VALID,
96		/** comparable type indicating this RowId should always compare
97		normally */
98	1	NORMAL,
99		/** comparable type indicating this Entry should always compare greater
100		than other valid entries with equal entryBytes */
101	1	LAST_VALID,
102		/** comparable type indicating this Entry should always compare greater
103		than valid RowIds */
104	1	ALWAYS_LAST;
105		}
106
107	1	static final Comparator<byte[]> BYTE_CODE_COMPARATOR =
108		new Comparator<byte[]>() {
109	152415	public int compare(byte[] left, byte[] right) {
110	152414	if(left == right) {
111	7873	return 0;
112		}
113	144541	if(left == null) {
114	0	return -1;
115		}
116	144541	if(right == null) {
117	2	return 1;
118		}
119
120	144539	int len = Math.min(left.length, right.length);
121	144539	int pos = 0;
122	681283	while((pos < len) && (left[pos] == right[pos])) {
123	536744	++pos;
124		}
125	144539	if(pos < len) {
126	126205	return ((ByteUtil.asUnsignedByte(left[pos]) <
127		ByteUtil.asUnsignedByte(right[pos])) ? -1 : 1);
128		}
129	18334	return ((left.length < right.length) ? -1 :
130		((left.length > right.length) ? 1 : 0));
131		}
132		};
133
134
135		/** owning table */
136		private final Table _table;
137		/** Page number of the root index data */
138		private int _rootPageNumber;
139		/** offset within the tableDefinition buffer of the uniqueEntryCount for
140		this index */
141		private final int _uniqueEntryCountOffset;
142		/** The number of unique entries which have been added to this index. note,
143		however, that it is never decremented, only incremented (as observed in
144		Access). */
145		private int _uniqueEntryCount;
146		/** List of columns and flags */
147	353	private final List<ColumnDescriptor> _columns =
148		new ArrayList<ColumnDescriptor>();
149		/** 0-based index number */
150		private int _indexNumber;
151		/** flags for this index */
152		private byte _indexFlags;
153		/** the type of the index */
154		private byte _indexType;
155		/** Index name */
156		private String _name;
157		/** <code>true</code> if the index entries have been initialized,
158		<code>false</code> otherwise */
159		private boolean _initialized;
160		/** modification count for the table, keeps cursors up-to-date */
161		private int _modCount;
162		/** temp buffer used to read/write the index pages */
163	353	private final TempBufferHolder _indexBufferH =
164		TempBufferHolder.newHolder(TempBufferHolder.Type.SOFT, true);
165		/** max size for all the entries written to a given index data page */
166		private final int _maxPageEntrySize;
167		/** FIXME, for now, we can't write multi-page indexes or indexes using the funky primary key compression scheme */
168		boolean _readOnly;
169
170		protected Index(Table table, int uniqueEntryCount,
171		int uniqueEntryCountOffset)
172	353	{
173	353	_table = table;
174	353	_uniqueEntryCount = uniqueEntryCount;
175	353	_uniqueEntryCountOffset = uniqueEntryCountOffset;
176	353	_maxPageEntrySize = calcMaxPageEntrySize(_table.getFormat());
177	353	}
178
179		public Table getTable() {
180	43016	return _table;
181		}
182
183		public JetFormat getFormat() {
184	15910	return getTable().getFormat();
185		}
186
187		public PageChannel getPageChannel() {
188	16590	return getTable().getPageChannel();
189		}
190
191		public void setIndexNumber(int indexNumber) {
192	353	_indexNumber = indexNumber;
193	353	}
194
195		public int getIndexNumber() {
196	159	return _indexNumber;
197		}
198
199		public void setIndexType(byte indexType) {
200	353	_indexType = indexType;
201	353	}
202
203		public byte getIndexFlags() {
204	0	return _indexFlags;
205		}
206
207		public int getUniqueEntryCount() {
208	4407	return _uniqueEntryCount;
209		}
210
211		public int getUniqueEntryCountOffset() {
212	4399	return _uniqueEntryCountOffset;
213		}
214
215		public String getName() {
216	1979	return _name;
217		}
218
219		public void setName(String name) {
220	353	_name = name;
221	353	}
222
223		public boolean isPrimaryKey() {
224	5028	return _indexType == PRIMARY_KEY_INDEX_TYPE;
225		}
226
227		public boolean isForeignKey() {
228	11	return _indexType == FOREIGN_KEY_INDEX_TYPE;
229		}
230
231		/**
232		* Whether or not {@code null} values are actually recorded in the index.
233		*/
234		public boolean shouldIgnoreNulls() {
235	4596	return((_indexFlags & IGNORE_NULLS_INDEX_FLAG) != 0);
236		}
237
238		/**
239		* Whether or not index entries must be unique.
240		* <p>
241		* Some notes about uniqueness:
242		* <ul>
243		* <li>Access does not seem to consider multiple {@code null} entries
244		* invalid for a unique index</li>
245		* <li>text indexes collapse case, and Access seems to compare <b>only</b>
246		* the index entry bytes, therefore two strings which differ only in
247		* case <i>will violate</i> the unique constraint</li>
248		* </ul>
249		*/
250		public boolean isUnique() {
251	2509	return(isPrimaryKey() \|\| ((_indexFlags & UNIQUE_INDEX_FLAG) != 0));
252		}
253
254		/**
255		* Returns the Columns for this index (unmodifiable)
256		*/
257		public List<ColumnDescriptor> getColumns() {
258	100	return Collections.unmodifiableList(_columns);
259		}
260
261		/**
262		* Whether or not the complete index state has been read.
263		*/
264		public boolean isInitialized() {
265	3	return _initialized;
266		}
267
268		protected int getRootPageNumber() {
269	193	return _rootPageNumber;
270		}
271
272		protected void setReadOnly() {
273	8	_readOnly = true;
274	8	}
275
276		protected int getMaxPageEntrySize() {
277	4002	return _maxPageEntrySize;
278		}
279
280		/**
281		* Returns the number of index entries in the index. Only called by unit
282		* tests.
283		* <p>
284		* Forces index initialization.
285		*/
286		protected int getEntryCount()
287		throws IOException
288		{
289	28	initialize();
290	28	EntryCursor cursor = cursor();
291	28	Entry endEntry = cursor.getLastEntry();
292	28	int count = 0;
293	1361	while(!endEntry.equals(cursor.getNextEntry())) {
294	1333	++count;
295		}
296	28	return count;
297		}
298
299		/**
300		* Forces initialization of this index (actual parsing of index pages).
301		* normally, the index will not be initialized until the entries are
302		* actually needed.
303		*/
304		public void initialize() throws IOException {
305	13047	if(!_initialized) {
306	193	readIndexEntries();
307	193	_initialized = true;
308		}
309	13047	}
310
311		/**
312		* Writes the current index state to the database.
313		* <p>
314		* Forces index initialization.
315		*/
316		public void update() throws IOException
317		{
318		// make sure we've parsed the entries
319	4399	initialize();
320
321	4399	if(_readOnly) {
322	1	throw new UnsupportedOperationException(
323		"FIXME cannot write indexes of this type yet, see Database javadoc for info on enabling large index support");
324		}
325	4398	updateImpl();
326	4398	}
327
328		/**
329		* Read the index info from a tableBuffer
330		* @param tableBuffer table definition buffer to read from initial info
331		* @param availableColumns Columns that this index may use
332		*/
333		public void read(ByteBuffer tableBuffer, List<Column> availableColumns)
334		throws IOException
335		{
336	3883	for (int i = 0; i < MAX_COLUMNS; i++) {
337	3530	short columnNumber = tableBuffer.getShort();
338	3530	byte colFlags = tableBuffer.get();
339	3530	if (columnNumber != COLUMN_UNUSED) {
340		// find the desired column by column number (which is not necessarily
341		// the same as the column index)
342	427	Column idxCol = null;
343	427	for(Column col : availableColumns) {
344	794	if(col.getColumnNumber() == columnNumber) {
345	427	idxCol = col;
346	427	break;
347		}
348		}
349	427	if(idxCol == null) {
350	0	throw new IOException("Could not find column with number "
351		+ columnNumber + " for index " + getName());
352		}
353	427	_columns.add(newColumnDescriptor(idxCol, colFlags));
354		}
355		}
356	353	tableBuffer.getInt(); //Forward past Unknown
357	353	_rootPageNumber = tableBuffer.getInt();
358	353	tableBuffer.getInt(); //Forward past Unknown
359	353	_indexFlags = tableBuffer.get();
360	353	tableBuffer.position(tableBuffer.position() + 5); //Forward past other stuff
361	353	}
362
363		/**
364		* Adds a row to this index
365		* <p>
366		* Forces index initialization.
367		*
368		* @param row Row to add
369		* @param rowId rowId of the row to be added
370		*/
371		public void addRow(Object[] row, RowId rowId)
372		throws IOException
373		{
374	2503	int nullCount = countNullValues(row);
375	2503	boolean isNullEntry = (nullCount == _columns.size());
376	2503	if(shouldIgnoreNulls() && isNullEntry) {
377		// nothing to do
378	5	return;
379		}
380	2498	if(isPrimaryKey() && (nullCount > 0)) {
381	0	throw new IOException("Null value found in row " + Arrays.asList(row)
382		+ " for primary key index " + this);
383		}
384
385		// make sure we've parsed the entries
386	2498	initialize();
387
388	2498	Entry newEntry = new Entry(createEntryBytes(row), rowId);
389	2498	if(addEntry(newEntry, isNullEntry, row)) {
390	2489	++_modCount;
391		} else {
392	0	LOG.warn("Added duplicate index entry " + newEntry + " for row: " +
393		Arrays.asList(row));
394		}
395	2489	}
396
397		/**
398		* Adds an entry to the correct index dataPage, maintaining the order.
399		*/
400		private boolean addEntry(Entry newEntry, boolean isNullEntry, Object[] row)
401		throws IOException
402		{
403	2498	DataPage dataPage = findDataPage(newEntry);
404	2498	int idx = dataPage.findEntry(newEntry);
405	2498	if(idx < 0) {
406		// this is a new entry
407	2498	idx = missingIndexToInsertionPoint(idx);
408
409	2498	Position newPos = new Position(dataPage, idx, newEntry, true);
410	2498	Position nextPos = getNextPosition(newPos);
411	2498	Position prevPos = getPreviousPosition(newPos);
412
413		// determine if the addition of this entry would break the uniqueness
414		// constraint. See isUnique() for some notes about uniqueness as
415		// defined by Access.
416	2498	boolean isDupeEntry =
417		(((nextPos != null) &&
418		newEntry.equalsEntryBytes(nextPos.getEntry())) \|\|
419		((prevPos != null) &&
420		newEntry.equalsEntryBytes(prevPos.getEntry())));
421	2498	if(isUnique() && !isNullEntry && isDupeEntry)
422		{
423	9	throw new IOException(
424		"New row " + Arrays.asList(row) +
425		" violates uniqueness constraint for index " + this);
426		}
427
428	2489	if(!isDupeEntry) {
429	2405	++_uniqueEntryCount;
430		}
431
432	2489	dataPage.addEntry(idx, newEntry);
433	2489	return true;
434		}
435	0	return false;
436		}
437
438		/**
439		* Removes a row from this index
440		* <p>
441		* Forces index initialization.
442		*
443		* @param row Row to remove
444		* @param rowId rowId of the row to be removed
445		*/
446		public void deleteRow(Object[] row, RowId rowId)
447		throws IOException
448		{
449	2082	int nullCount = countNullValues(row);
450	2082	if(shouldIgnoreNulls() && (nullCount == _columns.size())) {
451		// nothing to do
452	0	return;
453		}
454
455		// make sure we've parsed the entries
456	2082	initialize();
457
458	2082	Entry oldEntry = new Entry(createEntryBytes(row), rowId);
459	2082	if(removeEntry(oldEntry)) {
460	2082	++_modCount;
461		} else {
462	0	LOG.warn("Failed removing index entry " + oldEntry + " for row: " +
463		Arrays.asList(row));
464		}
465	2082	}
466
467		/**
468		* Removes an entry from the relevant index dataPage, maintaining the order.
469		* Will search by RowId if entry is not found (in case a partial entry was
470		* provided).
471		*/
472		private boolean removeEntry(Entry oldEntry)
473		throws IOException
474		{
475	2082	DataPage dataPage = findDataPage(oldEntry);
476	2082	int idx = dataPage.findEntry(oldEntry);
477	2082	boolean doRemove = false;
478	2082	if(idx < 0) {
479		// the caller may have only read some of the row data, if this is the
480		// case, just search for the page/row numbers
481		// FIXME, we could force caller to get relevant values?
482	2063	EntryCursor cursor = cursor();
483	2063	Position tmpPos = null;
484	2063	Position endPos = cursor._lastPos;
485	2000094	while(!endPos.equals(
486		tmpPos = cursor.getAnotherPosition(Cursor.MOVE_FORWARD))) {
487	2000094	if(tmpPos.getEntry().getRowId().equals(oldEntry.getRowId())) {
488	2063	dataPage = tmpPos.getDataPage();
489	2063	idx = tmpPos.getIndex();
490	2063	doRemove = true;
491	2063	break;
492		}
493		}
494	2063	} else {
495	19	doRemove = true;
496		}
497
498	2082	if(doRemove) {
499		// found it!
500	2082	dataPage.removeEntry(idx);
501		}
502
503	2082	return doRemove;
504		}
505
506		/**
507		* Gets a new cursor for this index.
508		* <p>
509		* Forces index initialization.
510		*/
511		public EntryCursor cursor()
512		throws IOException
513		{
514	2091	return cursor(null, true, null, true);
515		}
516
517		/**
518		* Gets a new cursor for this index, narrowed to the range defined by the
519		* given startRow and endRow.
520		* <p>
521		* Forces index initialization.
522		*
523		* @param startRow the first row of data for the cursor, or {@code null} for
524		* the first entry
525		* @param startInclusive whether or not startRow is inclusive or exclusive
526		* @param endRow the last row of data for the cursor, or {@code null} for
527		* the last entry
528		* @param endInclusive whether or not endRow is inclusive or exclusive
529		*/
530		public EntryCursor cursor(Object[] startRow,
531		boolean startInclusive,
532		Object[] endRow,
533		boolean endInclusive)
534		throws IOException
535		{
536	4032	initialize();
537	4032	Entry startEntry = FIRST_ENTRY;
538	4032	byte[] startEntryBytes = null;
539	4032	if(startRow != null) {
540	1849	startEntryBytes = createEntryBytes(startRow);
541	1849	startEntry = new Entry(startEntryBytes,
542		(startInclusive ?
543		RowId.FIRST_ROW_ID : RowId.LAST_ROW_ID));
544		}
545	4032	Entry endEntry = LAST_ENTRY;
546	4032	if(endRow != null) {
547		// reuse startEntryBytes if startRow and endRow are same array. this is
548		// common for "lookup" code
549	1847	byte[] endEntryBytes = ((startRow == endRow) ?
550		startEntryBytes :
551		createEntryBytes(endRow));
552	1847	endEntry = new Entry(endEntryBytes,
553		(endInclusive ?
554		RowId.LAST_ROW_ID : RowId.FIRST_ROW_ID));
555		}
556	4032	return new EntryCursor(findEntryPosition(startEntry),
557		findEntryPosition(endEntry));
558		}
559
560		private Position findEntryPosition(Entry entry)
561		throws IOException
562		{
563	16517	DataPage dataPage = findDataPage(entry);
564	16517	int idx = dataPage.findEntry(entry);
565	16517	boolean between = false;