View Javadoc
1   /*
2   Copyright (c) 2005 Health Market Science, Inc.
3   
4   Licensed under the Apache License, Version 2.0 (the "License");
5   you may not use this file except in compliance with the License.
6   You may obtain a copy of the License at
7   
8       http://www.apache.org/licenses/LICENSE-2.0
9   
10  Unless required by applicable law or agreed to in writing, software
11  distributed under the License is distributed on an "AS IS" BASIS,
12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  See the License for the specific language governing permissions and
14  limitations under the License.
15  */
16  
17  package com.healthmarketscience.jackcess.impl;
18  
19  import java.io.IOException;
20  import java.nio.ByteBuffer;
21  import java.nio.ByteOrder;
22  import java.util.ArrayList;
23  import java.util.Arrays;
24  import java.util.Collection;
25  import java.util.Collections;
26  import java.util.Comparator;
27  import java.util.List;
28  import java.util.Map;
29  
30  import com.healthmarketscience.jackcess.ConstraintViolationException;
31  import com.healthmarketscience.jackcess.Index;
32  import com.healthmarketscience.jackcess.IndexBuilder;
33  import com.healthmarketscience.jackcess.RuntimeIOException;
34  import static com.healthmarketscience.jackcess.impl.ByteUtil.ByteStream;
35  import static com.healthmarketscience.jackcess.impl.IndexCodes.*;
36  import org.apache.commons.lang.builder.ToStringBuilder;
37  import org.apache.commons.logging.Log;
38  import org.apache.commons.logging.LogFactory;
39  
40  /**
41   * Access table index data.  This is the actual data which backs a logical
42   * Index, where one or more logical indexes can be backed by the same index
43   * data.
44   * 
45   * @author Tim McCune
46   */
47  public class IndexData {
48    
49    protected static final Log LOG = LogFactory.getLog(Index.class);
50  
51    /** special entry which is less than any other entry */
52    public static final Entry FIRST_ENTRY =
53      createSpecialEntry(RowIdImpl.FIRST_ROW_ID);
54    
55    /** special entry which is greater than any other entry */
56    public static final Entry LAST_ENTRY =
57      createSpecialEntry(RowIdImpl.LAST_ROW_ID);
58  
59    /** special object which will always be greater than any other value, when
60        searching for an index entry range in a multi-value index */
61    public static final Object MAX_VALUE = new Object();
62  
63    /** special object which will always be greater than any other value, when
64        searching for an index entry range in a multi-value index */
65    public static final Object MIN_VALUE = new Object();
66  
67    private static final DataPage NEW_ROOT_DATA_PAGE = new RootDataPage();
68    
69    protected static final int INVALID_INDEX_PAGE_NUMBER = 0;          
70    
71    /** Max number of columns in an index */
72    public static final int MAX_COLUMNS = 10;
73    
74    protected static final byte[] EMPTY_PREFIX = new byte[0];
75  
76    static final short COLUMN_UNUSED = -1;
77  
78    public static final byte ASCENDING_COLUMN_FLAG = (byte)0x01;
79  
80    public static final byte UNIQUE_INDEX_FLAG = (byte)0x01;
81    public static final byte IGNORE_NULLS_INDEX_FLAG = (byte)0x02;
82    public static final byte REQUIRED_INDEX_FLAG = (byte)0x08;
83    public static final byte UNKNOWN_INDEX_FLAG = (byte)0x80; // always seems to be set on indexes in access 2000+
84  
85    private static final int MAGIC_INDEX_NUMBER = 1923;
86  
87    private static final ByteOrder ENTRY_BYTE_ORDER = ByteOrder.BIG_ENDIAN;
88    
89    /** type attributes for Entries which simplify comparisons */
90    public enum EntryType {
91      /** comparable type indicating this Entry should always compare less than
92          valid RowIds */
93      ALWAYS_FIRST,
94      /** comparable type indicating this Entry should always compare less than
95          other valid entries with equal entryBytes */
96      FIRST_VALID,
97      /** comparable type indicating this RowId should always compare
98          normally */
99      NORMAL,
100     /** comparable type indicating this Entry should always compare greater
101         than other valid entries with equal entryBytes */
102     LAST_VALID,
103     /** comparable type indicating this Entry should always compare greater
104         than valid RowIds */
105     ALWAYS_LAST;
106   }
107   
108   public static final Comparator<byte[]> BYTE_CODE_COMPARATOR =
109     new Comparator<byte[]>() {
110       public int compare(byte[] left, byte[] right) {
111         if(left == right) {
112           return 0;
113         }
114         if(left == null) {
115           return -1;
116         }
117         if(right == null) {
118           return 1;
119         }
120 
121         int len = Math.min(left.length, right.length);
122         int pos = 0;
123         while((pos < len) && (left[pos] == right[pos])) {
124           ++pos;
125         }
126         if(pos < len) {
127           return ((ByteUtil.asUnsignedByte(left[pos]) <
128                    ByteUtil.asUnsignedByte(right[pos])) ? -1 : 1);
129         }
130         return ((left.length < right.length) ? -1 :
131                 ((left.length > right.length) ? 1 : 0));
132       }
133     };
134         
135   
136   /** name, generated on demand */
137   private String _name;
138   /** owning table */
139   private final TableImpl _table;
140   /** 0-based index data number */
141   private final int _number;
142   /** Page number of the root index data */
143   private int _rootPageNumber;
144   /** offset within the tableDefinition buffer of the uniqueEntryCount for
145       this index */
146   private final int _uniqueEntryCountOffset;
147   /** The number of unique entries which have been added to this index.  note,
148       however, that it is never decremented, only incremented (as observed in
149       Access). */
150   private int _uniqueEntryCount;
151   /** List of columns and flags */
152   private final List<ColumnDescriptor> _columns =
153     new ArrayList<ColumnDescriptor>();
154   /** the logical indexes which this index data backs */
155   private final List<Index> _indexes = new ArrayList<Index>();
156   /** flags for this index */
157   private byte _indexFlags;
158   /** Usage map of pages that this index owns */
159   private UsageMap _ownedPages;
160   /** <code>true</code> if the index entries have been initialized,
161       <code>false</code> otherwise */
162   private boolean _initialized;
163   /** modification count for the table, keeps cursors up-to-date */
164   private int _modCount;
165   /** temp buffer used to read/write the index pages */
166   private final TempBufferHolder _indexBufferH =
167     TempBufferHolder.newHolder(TempBufferHolder.Type.SOFT, true);
168   /** temp buffer used to create index entries */
169   private ByteStream _entryBuffer;
170   /** max size for all the entries written to a given index data page */
171   private final int _maxPageEntrySize;
172   /** whether or not this index data is backing a primary key logical index */
173   private boolean _primaryKey;
174   /** if non-null, the reason why we cannot create entries for this index */
175   private String _unsupportedReason;
176   /** Cache which manages the index pages */
177   private final IndexPageCache _pageCache;
178   
179   protected IndexData(TableImpl table, int number, int uniqueEntryCount,
180                       int uniqueEntryCountOffset)
181   {
182     _table  = table;
183     _number = number;
184     _uniqueEntryCount = uniqueEntryCount;
185     _uniqueEntryCountOffset = uniqueEntryCountOffset;
186     _maxPageEntrySize = calcMaxPageEntrySize(_table.getFormat());
187     _pageCache = new IndexPageCache(this);
188   }
189 
190   /**
191    * Creates an IndexData appropriate for the given table, using information
192    * from the given table definition buffer.
193    */
194   public static IndexData create(TableImpl table, ByteBuffer tableBuffer,
195                                  int number, JetFormat format)
196     throws IOException
197   {
198     int uniqueEntryCountOffset =
199       (format.OFFSET_INDEX_DEF_BLOCK +
200        (number * format.SIZE_INDEX_DEFINITION) + 4);
201     int uniqueEntryCount = tableBuffer.getInt(uniqueEntryCountOffset);
202 
203     return new IndexData(table, number, uniqueEntryCount, uniqueEntryCountOffset);
204   }
205 
206   public String getName() {
207     if(_name == null) {
208       if(_indexes.size() == 1) {
209         _name = _indexes.get(0).getName();
210       } else if(!_indexes.isEmpty()) {
211         List<String> names = new ArrayList<String>(_indexes.size());
212         for(Index idx : _indexes) {
213           names.add(idx.getName());
214         }
215         _name = names.toString();
216       } else {
217         _name = String.valueOf(_number);
218       }
219     } 
220     return _name;
221   }
222 
223   public TableImpl getTable() {
224     return _table;
225   }
226   
227   public JetFormat getFormat() {
228     return getTable().getFormat();
229   }
230 
231   public PageChannel getPageChannel() {
232     return getTable().getPageChannel();
233   }
234 
235   /**
236    * @return the "main" logical index which is backed by this data.
237    */
238   public Index getPrimaryIndex() {
239     return _indexes.get(0);
240   }
241 
242   /**
243    * @return All of the Indexes backed by this data (unmodifiable List)
244    */
245   public List<Index> getIndexes() {
246     return Collections.unmodifiableList(_indexes);
247   }
248 
249   /**
250    * Adds a logical index which this data is backing.
251    */
252   void addIndex(Index index) {
253 
254     // we keep foreign key indexes at the back of the list.  this way the
255     // primary index will be a non-foreign key index (if any)
256     if(index.isForeignKey()) {
257       _indexes.add(index);
258     } else {
259       int pos = _indexes.size();
260       while(pos > 0) {
261         if(!_indexes.get(pos - 1).isForeignKey()) {
262           break;
263         }
264         --pos;
265       }
266       _indexes.add(pos, index);
267 
268       // also, keep track of whether or not this is a primary key index
269       _primaryKey |= index.isPrimaryKey();
270     }
271 
272     // force name to be regenerated
273     _name = null;
274   }
275 
276   public byte getIndexFlags() {
277     return _indexFlags;
278   }
279 
280   public int getIndexDataNumber() {
281     return _number;
282   }
283   
284   public int getUniqueEntryCount() {
285     return _uniqueEntryCount;
286   }
287 
288   public int getUniqueEntryCountOffset() {
289     return _uniqueEntryCountOffset;
290   }
291 
292   protected boolean isBackingPrimaryKey() {
293     return _primaryKey;
294   }
295 
296   /**
297    * Whether or not {@code null} values are actually recorded in the index.
298    */
299   public boolean shouldIgnoreNulls() {
300     return((_indexFlags & IGNORE_NULLS_INDEX_FLAG) != 0);
301   }
302 
303   /**
304    * Whether or not index entries must be unique.
305    * <p>
306    * Some notes about uniqueness:
307    * <ul>
308    * <li>Access does not seem to consider multiple {@code null} entries
309    *     invalid for a unique index</li>
310    * <li>text indexes collapse case, and Access seems to compare <b>only</b>
311    *     the index entry bytes, therefore two strings which differ only in
312    *     case <i>will violate</i> the unique constraint</li>
313    * </ul>
314    */
315   public boolean isUnique() {
316     return(isBackingPrimaryKey() || ((_indexFlags & UNIQUE_INDEX_FLAG) != 0));
317   }
318   
319   /**
320    * Whether or not values are required in the columns.
321    */
322   public boolean isRequired() {
323     return((_indexFlags & REQUIRED_INDEX_FLAG) != 0);
324   }
325 
326   /**
327    * Returns the Columns for this index (unmodifiable)
328    */
329   public List<ColumnDescriptor> getColumns() {
330     return Collections.unmodifiableList(_columns);
331   }
332 
333   public int getColumnCount() {
334     return _columns.size();
335   }
336 
337   /**
338    * Whether or not the complete index state has been read.
339    */
340   public boolean isInitialized() {
341     return _initialized;
342   }
343 
344   protected int getRootPageNumber() {
345     return _rootPageNumber;
346   }
347 
348   private void setUnsupportedReason(String reason, ColumnImpl col) {    
349     _unsupportedReason = withErrorContext(reason);
350     if(!col.getTable().isSystem()) {
351       LOG.warn(_unsupportedReason + ", making read-only");
352     } else {
353       if(LOG.isDebugEnabled()) {
354         LOG.debug(_unsupportedReason + ", making read-only");
355       }
356     }
357   }
358 
359   String getUnsupportedReason() {
360     return _unsupportedReason;
361   }
362 
363   protected int getMaxPageEntrySize() {
364     return _maxPageEntrySize;
365   }
366 
367   /**
368    * Returns the number of database pages owned by this index data.
369    * @usage _intermediate_method_
370    */
371   public int getOwnedPageCount() {
372     return _ownedPages.getPageCount();
373   }
374   
375   void addOwnedPage(int pageNumber) throws IOException {
376     _ownedPages.addPageNumber(pageNumber);
377   }
378 
379   void collectUsageMapPages(Collection<Integer> pages) {
380     pages.add(_ownedPages.getTablePageNumber());
381   }
382   
383   /**
384    * Used by unit tests to validate the internal status of the index.
385    * @usage _advanced_method_
386    */
387   public void validate() throws IOException {
388     _pageCache.validate();
389   }
390 
391   /**
392    * Returns the number of index entries in the index.  Only called by unit
393    * tests.
394    * <p>
395    * Forces index initialization.
396    * @usage _advanced_method_
397    */
398   public int getEntryCount()
399     throws IOException
400   {
401     initialize();
402     EntryCursor cursor = cursor();
403     Entry endEntry = cursor.getLastEntry();
404     int count = 0;
405     while(!endEntry.equals(cursor.getNextEntry())) {
406       ++count;
407     }
408     return count;
409   }
410   
411   /**
412    * Forces initialization of this index (actual parsing of index pages).
413    * normally, the index will not be initialized until the entries are
414    * actually needed.
415    */
416   public void initialize() throws IOException {
417     if(!_initialized) {
418       _pageCache.setRootPageNumber(getRootPageNumber());
419       _initialized = true;
420     }
421   }
422 
423   /**
424    * Writes the current index state to the database.
425    * <p>
426    * Forces index initialization.
427    */
428   public void update() throws IOException
429   {
430     // make sure we've parsed the entries
431     initialize();
432     
433     if(_unsupportedReason != null) {
434       throw new UnsupportedOperationException(
435           "Cannot write indexes of this type due to " + _unsupportedReason);
436     }
437     _pageCache.write();
438   }
439 
440   /**
441    * Read the rest of the index info from a tableBuffer
442    * @param tableBuffer table definition buffer to read from initial info
443    * @param availableColumns Columns that this index may use
444    */
445   public void read(ByteBuffer tableBuffer, List<ColumnImpl> availableColumns)
446     throws IOException
447   {
448     ByteUtil.forward(tableBuffer, getFormat().SKIP_BEFORE_INDEX); //Forward past Unknown
449 
450     for (int i = 0; i < MAX_COLUMNS; i++) {
451       short columnNumber = tableBuffer.getShort();
452       byte colFlags = tableBuffer.get();
453       if (columnNumber != COLUMN_UNUSED) {
454         // find the desired column by column number (which is not necessarily
455         // the same as the column index)
456         ColumnImpl idxCol = null;
457         for(ColumnImpl col : availableColumns) {
458           if(col.getColumnNumber() == columnNumber) {
459             idxCol = col;
460             break;
461           }
462         }
463         if(idxCol == null) {
464           throw new IOException(withErrorContext(
465                   "Could not find column with number "
466                   + columnNumber + " for index"));
467         }
468         _columns.add(newColumnDescriptor(idxCol, colFlags));
469       }
470     }
471 
472     _ownedPages = UsageMap.read(getTable().getDatabase(), tableBuffer);
473     
474     _rootPageNumber = tableBuffer.getInt();
475 
476     ByteUtil.forward(tableBuffer, getFormat().SKIP_BEFORE_INDEX_FLAGS); //Forward past Unknown
477     _indexFlags = tableBuffer.get();
478     ByteUtil.forward(tableBuffer, getFormat().SKIP_AFTER_INDEX_FLAGS); //Forward past other stuff
479   }
480 
481   /**
482    * Writes the index row count definitions into a table definition buffer.
483    * @param creator description of the indexes to write
484    * @param buffer Buffer to write to
485    */
486   protected static void writeRowCountDefinitions(
487       TableCreator creator, ByteBuffer buffer)
488   {
489     writeRowCountDefinitions(creator, buffer, creator.getIndexCount());
490   }
491 
492   /**
493    * Writes the index row count definitions into a table definition buffer.
494    * @param creator description of the indexes to write
495    * @param buffer Buffer to write to
496    * @param idxCount num indexes to write
497    */
498   protected static void writeRowCountDefinitions(
499       TableMutator creator, ByteBuffer buffer, int idxCount)
500   {
501     // index row counts (empty data)
502     ByteUtil.forward(buffer, (idxCount *
503                               creator.getFormat().SIZE_INDEX_DEFINITION));
504   }
505 
506   /**
507    * Writes the index definitions into a table definition buffer.
508    * @param creator description of the indexes to write
509    * @param buffer Buffer to write to
510    */
511   protected static void writeDefinitions(
512       TableCreator creator, ByteBuffer buffer)
513     throws IOException
514   {
515     ByteBuffer rootPageBuffer = createRootPageBuffer(creator);
516 
517     for(TableMutator.IndexDataState idxDataState : creator.getIndexDataStates()) {
518       writeDefinition(creator, buffer, idxDataState, rootPageBuffer);
519     }
520   }
521 
522   /**
523    * Writes the index definitions into a table definition buffer.
524    * @param creator description of the indexes to write
525    * @param buffer Buffer to write to
526    */
527   protected static void writeDefinition(
528       TableMutator creator, ByteBuffer buffer, 
529       TableMutator.IndexDataState idxDataState, ByteBuffer rootPageBuffer)
530     throws IOException
531   {
532     if(rootPageBuffer == null) {
533       rootPageBuffer = createRootPageBuffer(creator);
534     }
535 
536     buffer.putInt(MAGIC_INDEX_NUMBER); // seemingly constant magic value
537 
538     // write column information (always MAX_COLUMNS entries)
539     IndexBuilder idx = idxDataState.getFirstIndex();
540     List<IndexBuilder.Column> idxColumns = idx.getColumns();
541     for(int i = 0; i < MAX_COLUMNS; ++i) {
542 
543       short columnNumber = COLUMN_UNUSED;
544       byte flags = 0;
545 
546       if(i < idxColumns.size()) {
547 
548         // determine column info
549         IndexBuilder.Column idxCol = idxColumns.get(i);
550         flags = idxCol.getFlags();
551 
552         // find actual table column number
553         columnNumber = creator.getColumnNumber(idxCol.getName());
554         if(columnNumber == COLUMN_UNUSED) {
555           // should never happen as this is validated before
556           throw new IllegalArgumentException(
557               withErrorContext(
558                   "Column with name " + idxCol.getName() + " not found",
559                   creator.getDatabase(), creator.getTableName(), idx.getName()));
560         }
561       }
562          
563       buffer.putShort(columnNumber); // table column number
564       buffer.put(flags); // column flags (e.g. ordering)
565     }
566 
567     buffer.put(idxDataState.getUmapRowNumber()); // umap row
568     ByteUtil.put3ByteInt(buffer, idxDataState.getUmapPageNumber()); // umap page
569 
570     // write empty root index page
571     creator.getPageChannel().writePage(rootPageBuffer, 
572                                        idxDataState.getRootPageNumber());
573 
574     buffer.putInt(idxDataState.getRootPageNumber());
575     buffer.putInt(0); // unknown
576     buffer.put(idx.getFlags()); // index flags (unique, etc.)
577     ByteUtil.forward(buffer, 5); // unknown
578   }
579 
580   private static ByteBuffer createRootPageBuffer(TableMutator creator) 
581     throws IOException
582   {
583     ByteBuffer rootPageBuffer = creator.getPageChannel().createPageBuffer();
584     writeDataPage(rootPageBuffer, NEW_ROOT_DATA_PAGE, 
585                   creator.getTdefPageNumber(), creator.getFormat());
586     return rootPageBuffer;
587   }
588 
589   /**
590    * Prepares to add a row to this index.  All constraints are checked before
591    * this method returns.
592    * <p>
593    * Forces index initialization.
594    * 
595    * @param row Row to add
596    * @param rowId rowId of the row to be added
597    *
598    * @return a PendingChange which can complete the addition or roll it back
599    */
600   public PendingChange prepareAddRow(Object[] row, RowIdImpl rowId,
601                                      PendingChange nextChange)
602     throws IOException
603   {
604     return prepareAddRow(row, rowId, new AddRowPendingChange(nextChange));
605   }
606   
607   private PendingChange prepareAddRow(Object[] row, RowIdImpl rowId,
608                                       AddRowPendingChange change)
609     throws IOException
610   {
611     int nullCount = countNullValues(row);
612     boolean isNullEntry = (nullCount == _columns.size());
613     if(shouldIgnoreNulls() && isNullEntry) {
614       // nothing to do
615       return change;
616     }
617     if((nullCount > 0) && (isBackingPrimaryKey() || isRequired())) {
618       throw new ConstraintViolationException(withErrorContext(
619           "Null value found in row " + Arrays.asList(row) +
620           " for primary key or required index"));
621     }
622     
623     // make sure we've parsed the entries
624     initialize();
625 
626     return prepareAddEntry(new Entry(createEntryBytes(row), rowId), isNullEntry,
627                            row, change);
628   }
629 
630   /**
631    * Adds an entry to the correct index dataPage, maintaining the order.
632    */
633   private PendingChange prepareAddEntry(Entry newEntry, boolean isNullEntry,
634                                         Object[] row, AddRowPendingChange change)
635     throws IOException
636   {
637     DataPage dataPage = findDataPage(newEntry);
638     int idx = dataPage.findEntry(newEntry);
639     if(idx < 0) {
640       
641       // this is a new entry
642       idx = missingIndexToInsertionPoint(idx);
643 
644       Position newPos = new Position(dataPage, idx, newEntry, true);
645       Position nextPos = getNextPosition(newPos);
646       Position prevPos = getPreviousPosition(newPos);
647       
648       // determine if the addition of this entry would break the uniqueness
649       // constraint.  See isUnique() for some notes about uniqueness as
650       // defined by Access.
651       boolean isDupeEntry =
652         (((nextPos != null) &&
653           newEntry.equalsEntryBytes(nextPos.getEntry())) ||
654           ((prevPos != null) &&
655            newEntry.equalsEntryBytes(prevPos.getEntry())));
656       if(isUnique() && !isNullEntry && isDupeEntry) {
657         throw new ConstraintViolationException(withErrorContext(
658             "New row " + Arrays.asList(row) +
659             " violates uniqueness constraint for index"));
660       }
661 
662       change.setAddRow(newEntry, dataPage, idx, isDupeEntry);
663 
664     } else {
665 
666       change.setOldRow(newEntry);
667     }
668     return change;
669   }
670 
671   /**
672    * Completes a prepared row addition.
673    */
674   private void commitAddRow(Entry newEntry, DataPage dataPage, int idx,
675                             boolean isDupeEntry, Entry oldEntry)
676     throws IOException
677   {
678     if(newEntry != null) {
679       dataPage.addEntry(idx, newEntry);
680       if(!isDupeEntry) {
681         ++_uniqueEntryCount;
682       }
683       ++_modCount;
684     } else {
685       LOG.warn(withErrorContext("Added duplicate index entry " + oldEntry));
686     }
687   }
688 
689   /**
690    * Prepares to update a row in this index.  All constraints are checked
691    * before this method returns.
692    * <p>
693    * Forces index initialization.
694    * 
695    * @param oldRow Row to be removed
696    * @param newRow Row to be added
697    * @param rowId rowId of the row to be updated
698    *
699    * @return a PendingChange which can complete the update or roll it back
700    */
701   public PendingChange prepareUpdateRow(Object[] oldRow, RowIdImpl rowId,
702                                         Object[] newRow, 
703                                         PendingChange nextChange)
704     throws IOException
705   {
706     UpdateRowPendingChange change = new UpdateRowPendingChange(nextChange);
707     change.setOldRow(deleteRowImpl(oldRow, rowId));
708 
709     try {
710       prepareAddRow(newRow, rowId, change);
711       return change;
712     } catch(ConstraintViolationException e) {
713       // need to undo the deletion before bailing
714       change.rollback();
715       throw e;
716     }
717   }
718   
719   /**
720    * Removes a row from this index
721    * <p>
722    * Forces index initialization.
723    * 
724    * @param row Row to remove
725    * @param rowId rowId of the row to be removed
726    */
727   public void deleteRow(Object[] row, RowIdImpl rowId)
728     throws IOException
729   {
730     deleteRowImpl(row, rowId);
731   }
732   
733   private Entry deleteRowImpl(Object[] row, RowIdImpl rowId)
734     throws IOException
735   {
736     int nullCount = countNullValues(row);
737     if(shouldIgnoreNulls() && (nullCount == _columns.size())) {
738       // nothing to do
739       return null;
740     }
741     
742     // make sure we've parsed the entries
743     initialize();
744 
745     Entry oldEntry = new Entry(createEntryBytes(row), rowId);
746     Entry removedEntry = removeEntry(oldEntry);
747     if(removedEntry != null) {
748       ++_modCount;
749     } else {
750       LOG.warn(withErrorContext(
751           "Failed removing index entry " + oldEntry + " for row: " + 
752           Arrays.asList(row)));
753     }
754     return removedEntry;
755   }
756 
757   /**
758    * Undoes a previous row deletion.
759    */
760   private void rollbackDeletedRow(Entry removedEntry)
761     throws IOException
762   {
763     if(removedEntry == null) {
764       // no change was made
765       return;
766     }
767 
768     // unfortunately, stuff might have shuffled around when we first removed
769     // the row, so in order to re-insert it, we need to re-find and insert it.
770     DataPage dataPage = findDataPage(removedEntry);
771     int idx = dataPage.findEntry(removedEntry);
772     if(idx < 0) {
773       dataPage.addEntry(missingIndexToInsertionPoint(idx), removedEntry);
774     }
775   }
776   
777   /**
778    * Removes an entry from the relevant index dataPage, maintaining the order.
779    * Will search by RowId if entry is not found (in case a partial entry was
780    * provided).
781    */
782   private Entry removeEntry(Entry oldEntry)
783     throws IOException
784   {
785     DataPage dataPage = findDataPage(oldEntry);
786     int idx = dataPage.findEntry(oldEntry);
787     boolean doRemove = false;
788     if(idx < 0) {
789       // the caller may have only read some of the row data, if this is the
790       // case, just search for the page/row numbers
791       // TODO, we could force caller to get relevant values?
792       EntryCursor cursor = cursor();
793       Position tmpPos = null;
794       Position endPos = cursor._lastPos;
795       while(!endPos.equals(
796                 tmpPos = cursor.getAnotherPosition(CursorImpl.MOVE_FORWARD))) {
797         if(tmpPos.getEntry().getRowId().equals(oldEntry.getRowId())) {
798           dataPage = tmpPos.getDataPage();
799           idx = tmpPos.getIndex();
800           doRemove = true;
801           break;
802         }
803       }
804     } else {
805       doRemove = true;
806     }
807 
808     Entry removedEntry = null;
809     if(doRemove) {
810       // found it!
811       removedEntry = dataPage.removeEntry(idx);
812     }
813     
814     return removedEntry;
815   }
816       
817   public static void commitAll(PendingChange change) throws IOException {
818     while(change != null) {
819       change.commit();
820       change = change.getNext();
821     }
822   }
823 
824   public static void rollbackAll(PendingChange change) throws IOException {
825     while(change != null) {
826       change.rollback();
827       change = change.getNext();
828     }
829   }
830       
831   /**
832    * Gets a new cursor for this index.
833    * <p>
834    * Forces index initialization.
835    */
836   public EntryCursor cursor()
837     throws IOException
838   {
839     return cursor(null, true, null, true);
840   }
841   
842   /**
843    * Gets a new cursor for this index, narrowed to the range defined by the
844    * given startRow and endRow.
845    * <p>
846    * Forces index initialization.
847    * 
848    * @param startRow the first row of data for the cursor, or {@code null} for
849    *                 the first entry
850    * @param startInclusive whether or not startRow is inclusive or exclusive
851    * @param endRow the last row of data for the cursor, or {@code null} for
852    *               the last entry
853    * @param endInclusive whether or not endRow is inclusive or exclusive
854    */
855   public EntryCursor cursor(Object[] startRow,
856                             boolean startInclusive,
857                             Object[] endRow,
858                             boolean endInclusive)
859     throws IOException
860   {
861     initialize();
862     Entry startEntry = FIRST_ENTRY;
863     byte[] startEntryBytes = null;
864     if(startRow != null) {
865       startEntryBytes = createEntryBytes(startRow);
866       startEntry = new Entry(startEntryBytes,
867                              (startInclusive ?
868                               RowIdImpl.FIRST_ROW_ID : RowIdImpl.LAST_ROW_ID));
869     }
870     Entry endEntry = LAST_ENTRY;
871     if(endRow != null) {
872       // reuse startEntryBytes if startRow and endRow are same array.  this is
873       // common for "lookup" code
874       byte[] endEntryBytes = ((startRow == endRow) ?
875                               startEntryBytes :
876                               createEntryBytes(endRow));
877       endEntry = new Entry(endEntryBytes,
878                            (endInclusive ?
879                             RowIdImpl.LAST_ROW_ID : RowIdImpl.FIRST_ROW_ID));
880     }
881     return new EntryCursor(findEntryPosition(startEntry),
882                            findEntryPosition(endEntry));
883   }
884 
885   private Position findEntryPosition(Entry entry)
886     throws IOException
887   {
888     DataPage dataPage = findDataPage(entry);
889     int idx = dataPage.findEntry(entry);
890     boolean between = false;
891     if(idx < 0) {
892       // given entry was not found exactly.  our current position is now
893       // really between two indexes, but we cannot support that as an integer
894       // value, so we set a flag instead
895       idx = missingIndexToInsertionPoint(idx);
896       between = true;
897     }
898     return new Position(dataPage, idx, entry, between);
899   }
900 
901   private Position getNextPosition(Position curPos)
902     throws IOException
903   {
904     // get the next index (between-ness is handled internally)
905     int nextIdx = curPos.getNextIndex();
906     Position nextPos = null;
907     if(nextIdx < curPos.getDataPage().getEntries().size()) {
908       nextPos = new Position(curPos.getDataPage(), nextIdx);
909     } else {
910       int nextPageNumber = curPos.getDataPage().getNextPageNumber();
911       DataPage nextDataPage = null;
912       while(nextPageNumber != INVALID_INDEX_PAGE_NUMBER) {
913         DataPage dp = getDataPage(nextPageNumber);
914         if(!dp.isEmpty()) {
915           nextDataPage = dp;
916           break;
917         }
918         nextPageNumber = dp.getNextPageNumber();
919       }
920       if(nextDataPage != null) {
921         nextPos = new Position(nextDataPage, 0);
922       }
923     }
924     return nextPos;
925   }
926 
927   /**
928    * Returns the Position before the given one, or {@code null} if none.
929    */
930   private Position getPreviousPosition(Position curPos)
931     throws IOException
932   {
933     // get the previous index (between-ness is handled internally)
934     int prevIdx = curPos.getPrevIndex();
935     Position prevPos = null;
936     if(prevIdx >= 0) {
937       prevPos = new Position(curPos.getDataPage(), prevIdx);
938     } else {
939       int prevPageNumber = curPos.getDataPage().getPrevPageNumber();
940       DataPage prevDataPage = null;
941       while(prevPageNumber != INVALID_INDEX_PAGE_NUMBER) {
942         DataPage dp = getDataPage(prevPageNumber);
943         if(!dp.isEmpty()) {
944           prevDataPage = dp;
945           break;
946         }
947         prevPageNumber = dp.getPrevPageNumber();
948       }
949       if(prevDataPage != null) {
950         prevPos = new Position(prevDataPage,
951                                (prevDataPage.getEntries().size() - 1));
952       }
953     }
954     return prevPos;
955   }
956 
957   /**
958    * Returns the valid insertion point for an index indicating a missing
959    * entry.
960    */
961   protected static int missingIndexToInsertionPoint(int idx) {
962     return -(idx + 1);
963   }
964 
965   /**
966    * Constructs an array of values appropriate for this index from the given
967    * column values, expected to match the columns for this index.
968    * @return the appropriate sparse array of data
969    * @throws IllegalArgumentException if the wrong number of values are
970    *         provided
971    */
972   public Object[] constructIndexRowFromEntry(Object... values)
973   {
974     if(values.length != _columns.size()) {
975       throw new IllegalArgumentException(withErrorContext(
976           "Wrong number of column values given " + values.length +
977           ", expected " + _columns.size()));
978     }
979     int valIdx = 0;
980     Object[] idxRow = new Object[getTable().getColumnCount()];
981     for(ColumnDescriptor col : _columns) {
982       idxRow[col.getColumnIndex()] = values[valIdx++];
983     }
984     return idxRow;
985   }
986 
987   /**
988    * Constructs an array of values appropriate for this index from the given
989    * column values, possibly only providing a prefix subset of the index
990    * columns (at least one value must be provided).  If a prefix entry is
991    * provided, any missing, trailing index entry values will use the given
992    * filler value.
993    * @return the appropriate sparse array of data
994    * @throws IllegalArgumentException if at least one value is not provided
995    */
996   public Object[] constructPartialIndexRowFromEntry(
997       Object filler, Object... values)
998   {
999     if(values.length == 0) {
1000       throw new IllegalArgumentException(withErrorContext(
1001           "At least one column value must be provided"));
1002     }
1003     if(values.length > _columns.size()) {
1004       throw new IllegalArgumentException(withErrorContext(
1005           "Too many column values given " + values.length +
1006           ", expected at most " + _columns.size()));
1007     }
1008     int valIdx = 0;
1009     Object[] idxRow = new Object[getTable().getColumnCount()];
1010     for(ColumnDescriptor col : _columns) {
1011       idxRow[col.getColumnIndex()] = 
1012         ((valIdx < values.length) ? values[valIdx] : filler);
1013       ++valIdx;
1014     }
1015     return idxRow;
1016   }
1017     
1018   /**
1019    * Constructs an array of values appropriate for this index from the given
1020    * column value.
1021    * @return the appropriate sparse array of data or {@code null} if not all
1022    *         columns for this index were provided
1023    */
1024   public Object[] constructIndexRow(String colName, Object value)
1025   {
1026     return constructIndexRow(Collections.singletonMap(colName, value));
1027   }
1028 
1029   /**
1030    * Constructs an array of values appropriate for this index from the given
1031    * column value, which must be the first column of the index.  Any missing,
1032    * trailing index entry values will use the given filler value.
1033    * @return the appropriate sparse array of data or {@code null} if no prefix
1034    *         list of columns for this index were provided
1035    */
1036   public Object[] constructPartialIndexRow(Object filler, String colName, Object value)
1037   {
1038     return constructPartialIndexRow(filler, Collections.singletonMap(colName, value));
1039   }
1040 
1041   /**
1042    * Constructs an array of values appropriate for this index from the given
1043    * column values.
1044    * @return the appropriate sparse array of data or {@code null} if not all
1045    *         columns for this index were provided
1046    */
1047   public Object[] constructIndexRow(Map<String,?> row)
1048   {
1049     for(ColumnDescriptor col : _columns) {
1050       if(!row.containsKey(col.getName())) {
1051         return null;
1052       }
1053     }
1054 
1055     Object[] idxRow = new Object[getTable().getColumnCount()];
1056     for(ColumnDescriptor col : _columns) {
1057       idxRow[col.getColumnIndex()] = row.get(col.getName());
1058     }
1059     return idxRow;
1060   }  
1061 
1062   /**
1063    * Constructs an array of values appropriate for this index from the given
1064    * column values, possibly only using a subset of the given values.  A
1065    * partial row can be created if one or more prefix column values are
1066    * provided.  If a prefix can be found, any missing, trailing index entry
1067    * values will use the given filler value.
1068    * @return the appropriate sparse array of data or {@code null} if no prefix
1069    *         list of columns for this index were provided
1070    */
1071   public Object[] constructPartialIndexRow(Object filler, Map<String,?> row)
1072   {
1073     // see if we have at least one prefix column
1074     int numCols = 0;
1075     for(ColumnDescriptor col : _columns) {
1076       if(!row.containsKey(col.getName())) {
1077         if(numCols == 0) {
1078           // can't do it, need at least first column
1079           return null;
1080         }
1081         break;
1082       }
1083       ++numCols;
1084     }
1085 
1086     // fill in the row with either the prefix values or the filler value, as
1087     // appropriate
1088     Object[] idxRow = new Object[getTable().getColumnCount()];
1089     int valIdx = 0;
1090     for(ColumnDescriptor col : _columns) {
1091       idxRow[col.getColumnIndex()] = 
1092         ((valIdx < numCols) ? row.get(col.getName()) : filler);
1093       ++valIdx;
1094     }
1095     return idxRow;
1096   }
1097 
1098   @Override
1099   public String toString() {
1100     ToStringBuilder sb = CustomToStringStyle.builder(this)
1101       .append("dataNumber", _number)
1102       .append("pageNumber", _rootPageNumber)
1103       .append("isBackingPrimaryKey", isBackingPrimaryKey())
1104       .append("isUnique", isUnique())
1105       .append("ignoreNulls", shouldIgnoreNulls())
1106       .append("isRequired", isRequired())
1107       .append("columns", _columns)
1108       .append("initialized", _initialized);
1109     if(_initialized) {
1110       try {
1111         sb.append("entryCount", getEntryCount());
1112       } catch(IOException e) {
1113         throw new RuntimeIOException(e);
1114       }
1115     }
1116     sb.append("pageCache", _pageCache);
1117     return sb.toString();
1118   }
1119   
1120   /**
1121    * Write the given index page out to a buffer
1122    */
1123   protected void writeDataPage(DataPage dataPage)
1124     throws IOException
1125   {
1126     if(dataPage.getCompressedEntrySize() > _maxPageEntrySize) {
1127       throw new IllegalStateException(withErrorContext("data page is too large"));
1128     }
1129     
1130     ByteBuffer buffer = _indexBufferH.getPageBuffer(getPageChannel());
1131 
1132     writeDataPage(buffer, dataPage, getTable().getTableDefPageNumber(),
1133                   getFormat());
1134 
1135     getPageChannel().writePage(buffer, dataPage.getPageNumber());
1136   }
1137 
1138   /**
1139    * Writes the data page info to the given buffer.
1140    */
1141   protected static void writeDataPage(ByteBuffer buffer, DataPage dataPage,
1142                                       int tdefPageNumber, JetFormat format)
1143     throws IOException
1144   {
1145     buffer.put(dataPage.isLeaf() ?
1146                PageTypes.INDEX_LEAF :
1147                PageTypes.INDEX_NODE );  //Page type
1148     buffer.put((byte) 0x01);  //Unknown
1149     buffer.putShort((short) 0); //Free space
1150     buffer.putInt(tdefPageNumber);
1151 
1152     buffer.putInt(0); //Unknown
1153     buffer.putInt(dataPage.getPrevPageNumber()); //Prev page
1154     buffer.putInt(dataPage.getNextPageNumber()); //Next page
1155     buffer.putInt(dataPage.getChildTailPageNumber()); //ChildTail page
1156 
1157     byte[] entryPrefix = dataPage.getEntryPrefix();
1158     buffer.putShort((short) entryPrefix.length); // entry prefix byte count
1159     buffer.put((byte) 0); //Unknown
1160 
1161     byte[] entryMask = new byte[format.SIZE_INDEX_ENTRY_MASK];
1162     // first entry includes the prefix
1163     int totalSize = entryPrefix.length;
1164     for(Entry entry : dataPage.getEntries()) {
1165       totalSize += (entry.size() - entryPrefix.length);
1166       int idx = totalSize / 8;
1167       entryMask[idx] |= (1 << (totalSize % 8));
1168     }
1169     buffer.put(entryMask);
1170 
1171     // first entry includes the prefix
1172     buffer.put(entryPrefix);
1173     
1174     for(Entry entry : dataPage.getEntries()) {
1175       entry.write(buffer, entryPrefix);
1176     }
1177 
1178     // update free space
1179     buffer.putShort(2, (short) (format.PAGE_SIZE - buffer.position()));
1180   }
1181 
1182   /**
1183    * Reads an index page, populating the correct collection based on the page
1184    * type (node or leaf).
1185    */
1186   protected void readDataPage(DataPage dataPage)
1187     throws IOException
1188   {
1189     ByteBuffer buffer = _indexBufferH.getPageBuffer(getPageChannel());
1190     getPageChannel().readPage(buffer, dataPage.getPageNumber());
1191 
1192     boolean isLeaf = isLeafPage(buffer);
1193     dataPage.setLeaf(isLeaf);
1194 
1195     // note, "header" data is in LITTLE_ENDIAN format, entry data is in
1196     // BIG_ENDIAN format
1197     int entryPrefixLength = ByteUtil.getUnsignedShort(
1198         buffer, getFormat().OFFSET_INDEX_COMPRESSED_BYTE_COUNT);
1199     int entryMaskLength = getFormat().SIZE_INDEX_ENTRY_MASK;
1200     int entryMaskPos = getFormat().OFFSET_INDEX_ENTRY_MASK;
1201     int entryPos = entryMaskPos + entryMaskLength;
1202     int lastStart = 0;
1203     int totalEntrySize = 0;
1204     byte[] entryPrefix = null;
1205     List<Entry> entries = new ArrayList<Entry>();
1206     TempBufferHolder tmpEntryBufferH =
1207       TempBufferHolder.newHolder(TempBufferHolder.Type.HARD, true,
1208                                  ENTRY_BYTE_ORDER);
1209 
1210     Entry prevEntry = FIRST_ENTRY;
1211     for (int i = 0; i < entryMaskLength; i++) {
1212       byte entryMask = buffer.get(entryMaskPos + i);
1213       for (int j = 0; j < 8; j++) {
1214         if ((entryMask & (1 << j)) != 0) {
1215           int length = (i * 8) + j - lastStart;
1216           buffer.position(entryPos + lastStart);
1217 
1218           // determine if we can read straight from the index page (if no
1219           // entryPrefix).  otherwise, create temp buf with complete entry.
1220           ByteBuffer curEntryBuffer = buffer;
1221           int curEntryLen = length;
1222           if(entryPrefix != null) {
1223             curEntryBuffer = getTempEntryBuffer(
1224                 buffer, length, entryPrefix, tmpEntryBufferH);
1225             curEntryLen += entryPrefix.length;
1226           }
1227           totalEntrySize += curEntryLen;
1228 
1229           Entry entry = newEntry(curEntryBuffer, curEntryLen, isLeaf);
1230           if(prevEntry.compareTo(entry) >= 0) {
1231             throw new IOException(withErrorContext(
1232                     "Unexpected order in index entries, " +
1233                     prevEntry + " >= " + entry));
1234           }
1235           
1236           entries.add(entry);
1237 
1238           if((entries.size() == 1) && (entryPrefixLength > 0)) {
1239             // read any shared entry prefix
1240             entryPrefix = new byte[entryPrefixLength];
1241             buffer.position(entryPos + lastStart);
1242             buffer.get(entryPrefix);
1243           }
1244 
1245           lastStart += length;
1246           prevEntry = entry;
1247         }
1248       }
1249     }
1250 
1251     dataPage.setEntryPrefix(entryPrefix != null ? entryPrefix : EMPTY_PREFIX);
1252     dataPage.setEntries(entries);
1253     dataPage.setTotalEntrySize(totalEntrySize);
1254     
1255     int prevPageNumber = buffer.getInt(getFormat().OFFSET_PREV_INDEX_PAGE);
1256     int nextPageNumber = buffer.getInt(getFormat().OFFSET_NEXT_INDEX_PAGE);
1257     int childTailPageNumber =
1258       buffer.getInt(getFormat().OFFSET_CHILD_TAIL_INDEX_PAGE);
1259 
1260     dataPage.setPrevPageNumber(prevPageNumber);
1261     dataPage.setNextPageNumber(nextPageNumber);
1262     dataPage.setChildTailPageNumber(childTailPageNumber);
1263   }
1264 
1265   /**
1266    * Returns a new Entry of the correct type for the given data and page type.
1267    */
1268   private static Entry newEntry(ByteBuffer buffer, int entryLength, 
1269                                 boolean isLeaf)
1270     throws IOException
1271   {
1272     if(isLeaf) {
1273       return new Entry(buffer, entryLength);
1274     }
1275     return new NodeEntry(buffer, entryLength);
1276   }
1277 
1278   /**
1279    * Returns an entry buffer containing the relevant data for an entry given
1280    * the valuePrefix.
1281    */
1282   private ByteBuffer getTempEntryBuffer(
1283       ByteBuffer indexPage, int entryLen, byte[] valuePrefix,
1284       TempBufferHolder tmpEntryBufferH)
1285   {
1286     ByteBuffer tmpEntryBuffer = tmpEntryBufferH.getBuffer(
1287         getPageChannel(), valuePrefix.length + entryLen);
1288 
1289     // combine valuePrefix and rest of entry from indexPage, then prep for
1290     // reading
1291     tmpEntryBuffer.put(valuePrefix);
1292     tmpEntryBuffer.put(indexPage.array(), indexPage.position(), entryLen);
1293     tmpEntryBuffer.flip();
1294     
1295     return tmpEntryBuffer;
1296   }
1297     
1298   /**
1299    * Determines if the given index page is a leaf or node page.
1300    */
1301   private boolean isLeafPage(ByteBuffer buffer)
1302     throws IOException
1303   {
1304     byte pageType = buffer.get(0);
1305     if(pageType == PageTypes.INDEX_LEAF) {
1306       return true;
1307     } else if(pageType == PageTypes.INDEX_NODE) {
1308       return false;
1309     }
1310     throw new IOException(withErrorContext("Unexpected page type " + pageType));
1311   }
1312   
1313   /**
1314    * Determines the number of {@code null} values for this index from the
1315    * given row.
1316    */
1317   private int countNullValues(Object[] values)
1318   {
1319     if(values == null) {
1320       return _columns.size();
1321     }
1322     
1323     // annoyingly, the values array could come from different sources, one
1324     // of which will make it a different size than the other.  we need to
1325     // handle both situations.
1326     int nullCount = 0;
1327     for(ColumnDescriptor col : _columns) {
1328       Object value = values[col.getColumnIndex()];
1329       if(col.isNullValue(value)) {
1330         ++nullCount;
1331       }
1332     }
1333     
1334     return nullCount;
1335   }
1336 
1337   /**
1338    * Creates the entry bytes for a row of values.
1339    */
1340   private byte[] createEntryBytes(Object[] values) throws IOException
1341   {
1342     if(values == null) {
1343       return null;
1344     }
1345     
1346     if(_entryBuffer == null) {
1347       _entryBuffer = new ByteStream();
1348     }
1349     _entryBuffer.reset();
1350     
1351     for(ColumnDescriptor col : _columns) {
1352 
1353       Object value = values[col.getColumnIndex()];
1354       if(ColumnImpl.isRawData(value)) {
1355         // ignore it, we could not parse it
1356         continue;
1357       }
1358 
1359       if(value == MIN_VALUE) {
1360         // null is the "least" value (note the column "ascending" flag is
1361         // irrelevant here because the entry bytes are _always_ interpreted
1362         // least to greatest)
1363         _entryBuffer.write(getNullEntryFlag(true));
1364         continue;
1365       }
1366       if(value == MAX_VALUE) {
1367         // the opposite null is the "greatest" value (note the column
1368         // "ascending" flag is irrelevant here because the entry bytes are
1369         // _always_ interpreted least to greatest)
1370         _entryBuffer.write(getNullEntryFlag(false));
1371         continue;
1372       }
1373 
1374       col.writeValue(value, _entryBuffer);
1375     }
1376     
1377     return _entryBuffer.toByteArray();
1378   }  
1379 
1380   /**
1381    * Finds the data page for the given entry.
1382    */
1383   protected DataPage findDataPage(Entry entry)
1384     throws IOException
1385   {
1386     return _pageCache.findCacheDataPage(entry);
1387   }
1388   
1389   /**
1390    * Gets the data page for the pageNumber.
1391    */
1392   protected DataPage getDataPage(int pageNumber)
1393     throws IOException
1394   {
1395     return _pageCache.getCacheDataPage(pageNumber);
1396   }
1397   
1398   /**
1399    * Flips the first bit in the byte at the given index.
1400    */
1401   private static byte[] flipFirstBitInByte(byte[] value, int index)
1402   {
1403     value[index] = (byte)(value[index] ^ 0x80);
1404 
1405     return value;
1406   }
1407 
1408   /**
1409    * Flips all the bits in the byte array.
1410    */
1411   private static byte[] flipBytes(byte[] value) {
1412     return flipBytes(value, 0, value.length);
1413   }
1414 
1415   /**
1416    * Flips the bits in the specified bytes in the byte array.
1417    */
1418   static byte[] flipBytes(byte[] value, int offset, int length) {
1419     for(int i = offset; i < (offset + length); ++i) {
1420       value[i] = (byte)(~value[i]);
1421     } 
1422     return value;
1423   }
1424 
1425   /**
1426    * Writes the value of the given column type to a byte array and returns it.
1427    */
1428   private static byte[] encodeNumberColumnValue(Object value, ColumnImpl column)
1429     throws IOException
1430   {
1431     // always write in big endian order
1432     return column.write(value, 0, ENTRY_BYTE_ORDER).array();
1433   }    
1434 
1435   /**
1436    * Writes a binary value using the general binary entry encoding rules.
1437    */
1438   private static void writeGeneralBinaryEntry(byte[] valueBytes, boolean isAsc,
1439                                               ByteStream bout)
1440   {
1441     int dataLen = valueBytes.length;
1442     int extraLen = (dataLen + 7) / 8;
1443     int entryLen = ((dataLen + extraLen + 8) / 9) * 9;
1444 
1445     // reserve space for the full entry
1446     bout.ensureNewCapacity(entryLen);
1447 
1448     // binary data is written in 8 byte segments with a trailing length byte.
1449     // The length byte is the amount of valid bytes in the segment (where 9
1450     // indicates that there is more data _after_ this segment).
1451     byte[] partialEntryBytes = new byte[9];
1452 
1453     // bit twiddling rules:
1454     // - isAsc  => nothing
1455     // - !isAsc => flipBytes, _but keep intermediate 09 unflipped_!      
1456 
1457     // first, write any intermediate segements
1458     int segmentLen = dataLen;
1459     int pos = 0;
1460     while(segmentLen > 8) {
1461 
1462       System.arraycopy(valueBytes, pos, partialEntryBytes, 0, 8);
1463       if(!isAsc) {
1464         // note, we do _not_ flip the length byte for intermediate segments
1465         flipBytes(partialEntryBytes, 0, 8);
1466       }
1467 
1468       // we are writing intermediate segments (there is more data after this
1469       // segment), so the length is always 9.
1470       partialEntryBytes[8] = (byte)9;
1471 
1472       pos += 8;
1473       segmentLen -= 8;
1474 
1475       bout.write(partialEntryBytes);
1476     }
1477 
1478     // write the last segment (with slightly different rules)
1479     if(segmentLen > 0) {
1480 
1481       System.arraycopy(valueBytes, pos, partialEntryBytes, 0, segmentLen);
1482 
1483       // clear out an intermediate bytes between the real data and the final
1484       // length byte
1485       for(int i = segmentLen; i < 8; ++i) {
1486         partialEntryBytes[i] = 0;
1487       }
1488 
1489       partialEntryBytes[8] = (byte)segmentLen;
1490 
1491       if(!isAsc) {
1492         // note, we _do_ flip the last length byte
1493         flipBytes(partialEntryBytes, 0, 9);
1494       }
1495 
1496       bout.write(partialEntryBytes);
1497     }
1498   }
1499 
1500   /**
1501    * Creates one of the special index entries.
1502    */
1503   private static Entry createSpecialEntry(RowIdImpl rowId) {
1504     return new Entry((byte[])null, rowId);
1505   }
1506 
1507   /**
1508    * Constructs a ColumnDescriptor of the relevant type for the given Column.
1509    */
1510   private ColumnDescriptor newColumnDescriptor(ColumnImpl col, byte flags)
1511     throws IOException
1512   {
1513     switch(col.getType()) {
1514     case TEXT:
1515     case MEMO:
1516       ColumnImpl.SortOrder sortOrder = col.getTextSortOrder();
1517       if(ColumnImpl.GENERAL_LEGACY_SORT_ORDER.equals(sortOrder)) {
1518         return new GenLegTextColumnDescriptor(col, flags);
1519       }
1520       if(ColumnImpl.GENERAL_SORT_ORDER.equals(sortOrder)) {
1521         return new GenTextColumnDescriptor(col, flags);
1522       }
1523       // unsupported sort order
1524       setUnsupportedReason("unsupported collating sort order " + sortOrder +
1525                            " for text index", col);
1526       return new ReadOnlyColumnDescriptor(col, flags);
1527     case INT:
1528     case LONG:
1529     case MONEY:
1530     case COMPLEX_TYPE:
1531       return new IntegerColumnDescriptor(col, flags);
1532     case FLOAT:
1533     case DOUBLE:
1534     case SHORT_DATE_TIME:
1535       return new FloatingPointColumnDescriptor(col, flags);
1536     case NUMERIC:
1537       return (col.getFormat().LEGACY_NUMERIC_INDEXES ?
1538               new LegacyFixedPointColumnDescriptor(col, flags) :
1539               new FixedPointColumnDescriptor(col, flags));
1540     case BYTE:
1541       return new ByteColumnDescriptor(col, flags);
1542     case BOOLEAN:
1543       return new BooleanColumnDescriptor(col, flags);
1544     case GUID:
1545       return new GuidColumnDescriptor(col, flags);
1546     case BINARY:
1547       return new BinaryColumnDescriptor(col, flags);
1548 
1549     default:
1550       // we can't modify this index at this point in time
1551       setUnsupportedReason("unsupported data type " + col.getType() + 
1552                            " for index", col);
1553       return new ReadOnlyColumnDescriptor(col, flags);
1554     }
1555   }
1556 
1557   /**
1558    * Returns the EntryType based on the given entry info.
1559    */
1560   private static EntryType determineEntryType(byte[] entryBytes, RowIdImpl rowId)
1561   {
1562     if(entryBytes != null) {
1563       return ((rowId.getType() == RowIdImpl.Type.NORMAL) ?
1564               EntryType.NORMAL :
1565               ((rowId.getType() == RowIdImpl.Type.ALWAYS_FIRST) ?
1566                EntryType.FIRST_VALID : EntryType.LAST_VALID));
1567     } else if(!rowId.isValid()) {
1568       // this is a "special" entry (first/last)
1569       return ((rowId.getType() == RowIdImpl.Type.ALWAYS_FIRST) ?
1570               EntryType.ALWAYS_FIRST : EntryType.ALWAYS_LAST);
1571     }
1572     throw new IllegalArgumentException("Values was null for valid entry");
1573   }
1574 
1575   /**
1576    * Returns the maximum amount of entry data which can be encoded on any
1577    * index page.
1578    */
1579   private static int calcMaxPageEntrySize(JetFormat format)
1580   {
1581     // the max data we can fit on a page is the min of the space on the page
1582     // vs the number of bytes which can be encoded in the entry mask
1583     int pageDataSize = (format.PAGE_SIZE -
1584                         (format.OFFSET_INDEX_ENTRY_MASK +
1585                          format.SIZE_INDEX_ENTRY_MASK));
1586     int entryMaskSize = (format.SIZE_INDEX_ENTRY_MASK * 8);
1587     return Math.min(pageDataSize, entryMaskSize);
1588   }
1589 
1590   String withErrorContext(String msg) {
1591     return withErrorContext(msg, getTable().getDatabase(), getTable().getName(),
1592                             getName());
1593   }
1594 
1595   private static String withErrorContext(String msg, DatabaseImpl db,
1596                                          String tableName, String idxName) {
1597     return msg + " (Db=" + db.getName() + ";Table=" + tableName +
1598       ";Index=" + idxName + ")";
1599   }
1600   
1601   /**
1602    * Information about the columns in an index.  Also encodes new index
1603    * values.
1604    */
1605   public static abstract class ColumnDescriptor implements Index.Column
1606   {
1607     private final ColumnImpl _column;
1608     private final byte _flags;
1609 
1610     private ColumnDescriptor(ColumnImpl column, byte flags)
1611       throws IOException
1612     {
1613       _column = column;
1614       _flags = flags;
1615     }
1616 
1617     public ColumnImpl getColumn() {
1618       return _column;
1619     }
1620 
1621     public byte getFlags() {
1622       return _flags;
1623     }
1624 
1625     public boolean isAscending() {
1626       return((getFlags() & ASCENDING_COLUMN_FLAG) != 0);
1627     }
1628     
1629     public int getColumnIndex() {
1630       return getColumn().getColumnIndex();
1631     }
1632     
1633     public String getName() {
1634       return getColumn().getName();
1635     }
1636 
1637     protected boolean isNullValue(Object value) {
1638       return (value == null);
1639     }
1640     
1641     protected final void writeValue(Object value, ByteStream bout)
1642       throws IOException
1643     {
1644       if(isNullValue(value)) {
1645         // write null value
1646         bout.write(getNullEntryFlag(isAscending()));
1647         return;
1648       }
1649       
1650       // write the start flag
1651       bout.write(getStartEntryFlag(isAscending()));
1652       // write the rest of the value
1653       writeNonNullValue(value, bout);
1654     }
1655 
1656     protected abstract void writeNonNullValue(Object value, ByteStream bout)
1657       throws IOException; 
1658     
1659     @Override
1660     public String toString() {
1661       return CustomToStringStyle.builder(this)
1662         .append("column", getColumn())
1663         .append("flags", getFlags() + " " + (isAscending() ? "(ASC)" : "(DSC)"))
1664         .toString();
1665     }
1666   }
1667 
1668   /**
1669    * ColumnDescriptor for integer based columns.
1670    */
1671   private static final class IntegerColumnDescriptor extends ColumnDescriptor
1672   {
1673     private IntegerColumnDescriptor(ColumnImpl column, byte flags)
1674       throws IOException
1675     {
1676       super(column, flags);
1677     }
1678     
1679     @Override
1680     protected void writeNonNullValue(Object value, ByteStream bout)
1681       throws IOException
1682     {
1683       byte[] valueBytes = encodeNumberColumnValue(value, getColumn());
1684       
1685       // bit twiddling rules:
1686       // - isAsc  => flipFirstBit
1687       // - !isAsc => flipFirstBit, flipBytes
1688       
1689       flipFirstBitInByte(valueBytes, 0);
1690       if(!isAscending()) {
1691         flipBytes(valueBytes);
1692       }
1693       
1694       bout.write(valueBytes);
1695     }    
1696   }
1697   
1698   /**
1699    * ColumnDescriptor for floating point based columns.
1700    */
1701   private static final class FloatingPointColumnDescriptor
1702     extends ColumnDescriptor
1703   {
1704     private FloatingPointColumnDescriptor(ColumnImpl column, byte flags)
1705       throws IOException
1706     {
1707       super(column, flags);
1708     }
1709     
1710     @Override
1711     protected void writeNonNullValue(Object value, ByteStream bout)
1712       throws IOException
1713     {
1714       byte[] valueBytes = encodeNumberColumnValue(value, getColumn());
1715       
1716       // determine if the number is negative by testing if the first bit is
1717       // set
1718       boolean isNegative = ((valueBytes[0] & 0x80) != 0);
1719 
1720       // bit twiddling rules:
1721       // isAsc && !isNeg => flipFirstBit
1722       // isAsc && isNeg => flipBytes
1723       // !isAsc && !isNeg => flipFirstBit, flipBytes
1724       // !isAsc && isNeg => nothing
1725       
1726       if(!isNegative) {
1727         flipFirstBitInByte(valueBytes, 0);
1728       }
1729       if(isNegative == isAscending()) {
1730         flipBytes(valueBytes);
1731       }
1732       
1733       bout.write(valueBytes);
1734     }    
1735   }
1736   
1737   /**
1738    * ColumnDescriptor for fixed point based columns (legacy sort order).
1739    */
1740   private static class LegacyFixedPointColumnDescriptor
1741     extends ColumnDescriptor
1742   {
1743     private LegacyFixedPointColumnDescriptor(ColumnImpl column, byte flags)
1744       throws IOException
1745     {
1746       super(column, flags);
1747     }
1748 
1749     protected void handleNegationAndOrder(boolean isNegative,
1750                                           byte[] valueBytes)
1751     {
1752       if(isNegative == isAscending()) {
1753         flipBytes(valueBytes);
1754       }
1755 
1756       // reverse the sign byte (after any previous byte flipping)
1757       valueBytes[0] = (isNegative ? (byte)0x00 : (byte)0xFF);      
1758     }
1759     
1760     @Override
1761     protected void writeNonNullValue(Object value, ByteStream bout)
1762       throws IOException
1763     {
1764       byte[] valueBytes = encodeNumberColumnValue(value, getColumn());
1765       
1766       // determine if the number is negative by testing if the first bit is
1767       // set
1768       boolean isNegative = ((valueBytes[0] & 0x80) != 0);
1769 
1770       // bit twiddling rules:
1771       // isAsc && !isNeg => setReverseSignByte             => FF 00 00 ...
1772       // isAsc && isNeg => flipBytes, setReverseSignByte   => 00 FF FF ...
1773       // !isAsc && !isNeg => flipBytes, setReverseSignByte => FF FF FF ...
1774       // !isAsc && isNeg => setReverseSignByte             => 00 00 00 ...
1775       
1776       // v2007 bit twiddling rules (old ordering was a bug, MS kb 837148):
1777       // isAsc && !isNeg => setSignByte 0xFF            => FF 00 00 ...
1778       // isAsc && isNeg => setSignByte 0xFF, flipBytes  => 00 FF FF ...
1779       // !isAsc && !isNeg => setSignByte 0xFF           => FF 00 00 ...
1780       // !isAsc && isNeg => setSignByte 0xFF, flipBytes => 00 FF FF ...
1781       handleNegationAndOrder(isNegative, valueBytes);
1782 
1783       bout.write(valueBytes);
1784     }    
1785   }
1786   
1787   /**
1788    * ColumnDescriptor for new-style fixed point based columns.
1789    */
1790   private static final class FixedPointColumnDescriptor
1791     extends LegacyFixedPointColumnDescriptor
1792   {
1793     private FixedPointColumnDescriptor(ColumnImpl column, byte flags)
1794       throws IOException
1795     {
1796       super(column, flags);
1797     }
1798     
1799     @Override
1800     protected void handleNegationAndOrder(boolean isNegative,
1801                                           byte[] valueBytes)
1802     {
1803       // see notes above in FixedPointColumnDescriptor for bit twiddling rules
1804 
1805       // reverse the sign byte (before any byte flipping)
1806       valueBytes[0] = (byte)0xFF;
1807 
1808       if(isNegative == isAscending()) {
1809         flipBytes(valueBytes);
1810       }
1811     }    
1812   }
1813   
1814   /**
1815    * ColumnDescriptor for byte based columns.
1816    */
1817   private static final class ByteColumnDescriptor extends ColumnDescriptor
1818   {
1819     private ByteColumnDescriptor(ColumnImpl column, byte flags)
1820       throws IOException
1821     {
1822       super(column, flags);
1823     }
1824     
1825     @Override
1826     protected void writeNonNullValue(Object value, ByteStream bout)
1827       throws IOException
1828     {
1829       byte[] valueBytes = encodeNumberColumnValue(value, getColumn());
1830       
1831       // bit twiddling rules:
1832       // - isAsc  => nothing
1833       // - !isAsc => flipBytes
1834       if(!isAscending()) {
1835         flipBytes(valueBytes);
1836       }
1837       
1838       bout.write(valueBytes);
1839     }    
1840   }
1841   
1842   /**
1843    * ColumnDescriptor for boolean columns.
1844    */
1845   private static final class BooleanColumnDescriptor extends ColumnDescriptor
1846   {
1847     private BooleanColumnDescriptor(ColumnImpl column, byte flags)
1848       throws IOException
1849     {
1850       super(column, flags);
1851     }
1852 
1853     @Override
1854     protected boolean isNullValue(Object value) {
1855       // null values are handled as booleans
1856       return false;
1857     }
1858     
1859     @Override
1860     protected void writeNonNullValue(Object value, ByteStream bout)
1861       throws IOException
1862     {
1863       bout.write(
1864           ColumnImpl.toBooleanValue(value) ?
1865           (isAscending() ? ASC_BOOLEAN_TRUE : DESC_BOOLEAN_TRUE) :
1866           (isAscending() ? ASC_BOOLEAN_FALSE : DESC_BOOLEAN_FALSE));
1867     }
1868   }
1869   
1870   /**
1871    * ColumnDescriptor for "general legacy" sort order text based columns.
1872    */
1873   private static final class GenLegTextColumnDescriptor 
1874     extends ColumnDescriptor
1875   {
1876     private GenLegTextColumnDescriptor(ColumnImpl column, byte flags)
1877       throws IOException
1878     {
1879       super(column, flags);
1880     }
1881     
1882     @Override
1883     protected void writeNonNullValue(Object value, ByteStream bout)
1884       throws IOException
1885     {
1886       GeneralLegacyIndexCodes.GEN_LEG_INSTANCE.writeNonNullIndexTextValue(
1887           value, bout, isAscending());
1888     }    
1889   }
1890 
1891   /**
1892    * ColumnDescriptor for "general" sort order (2010+) text based columns.
1893    */
1894   private static final class GenTextColumnDescriptor extends ColumnDescriptor
1895   {
1896     private GenTextColumnDescriptor(ColumnImpl column, byte flags)
1897       throws IOException
1898     {
1899       super(column, flags);
1900     }
1901     
1902     @Override
1903     protected void writeNonNullValue(Object value, ByteStream bout)
1904       throws IOException
1905     {
1906       GeneralIndexCodes.GEN_INSTANCE.writeNonNullIndexTextValue(
1907           value, bout, isAscending());
1908     }    
1909   }
1910 
1911   /**
1912    * ColumnDescriptor for guid columns.
1913    */
1914   private static final class GuidColumnDescriptor extends ColumnDescriptor
1915   {
1916     private GuidColumnDescriptor(ColumnImpl column, byte flags)
1917       throws IOException
1918     {
1919       super(column, flags);
1920     }
1921     
1922     @Override
1923     protected void writeNonNullValue(Object value, ByteStream bout)
1924       throws IOException
1925     {
1926       writeGeneralBinaryEntry(
1927           encodeNumberColumnValue(value, getColumn()), isAscending(),
1928           bout);
1929     }
1930   }
1931   
1932 
1933   /**
1934    * ColumnDescriptor for BINARY columns.
1935    */
1936   private static final class BinaryColumnDescriptor extends ColumnDescriptor
1937   {
1938     private BinaryColumnDescriptor(ColumnImpl column, byte flags)
1939       throws IOException
1940     {
1941       super(column, flags);
1942     }
1943 
1944     @Override
1945     protected void writeNonNullValue(Object value, ByteStream bout)
1946       throws IOException
1947     {
1948       writeGeneralBinaryEntry(
1949           ColumnImpl.toByteArray(value), isAscending(), bout);
1950     }
1951   }
1952   
1953   
1954   /**
1955    * ColumnDescriptor for columns which we cannot currently write.
1956    */
1957   private final class ReadOnlyColumnDescriptor extends ColumnDescriptor
1958   {
1959     private ReadOnlyColumnDescriptor(ColumnImpl column, byte flags)
1960       throws IOException
1961     {
1962       super(column, flags);
1963     }
1964 
1965     @Override
1966     protected void writeNonNullValue(Object value, ByteStream bout)
1967       throws IOException
1968     {
1969       throw new UnsupportedOperationException(
1970           "Cannot write indexes of this type due to " + _unsupportedReason);
1971     }
1972   }
1973     
1974   /**
1975    * A single leaf entry in an index (points to a single row)
1976    */
1977   public static class Entry implements Comparable<Entry>
1978   {
1979     /** page/row on which this row is stored */
1980     private final RowIdImpl _rowId;
1981     /** the entry value */
1982     private final byte[] _entryBytes;
1983     /** comparable type for the entry */
1984     private final EntryType _type;
1985     
1986     /**
1987      * Create a new entry
1988      * @param entryBytes encoded bytes for this index entry
1989      * @param rowId rowId in which the row is stored
1990      * @param type the type of the entry
1991      */
1992     private Entry(byte[] entryBytes, RowIdImpl rowId, EntryType type) {
1993       _rowId = rowId;
1994       _entryBytes = entryBytes;
1995       _type = type;
1996     }
1997     
1998     /**
1999      * Create a new entry
2000      * @param entryBytes encoded bytes for this index entry
2001      * @param rowId rowId in which the row is stored
2002      */
2003     private Entry(byte[] entryBytes, RowIdImpl rowId)
2004     {
2005       this(entryBytes, rowId, determineEntryType(entryBytes, rowId));
2006     }
2007 
2008     /**
2009      * Read an existing entry in from a buffer
2010      */
2011     private Entry(ByteBuffer buffer, int entryLen)
2012       throws IOException
2013     {
2014       this(buffer, entryLen, 0);
2015     }
2016     
2017     /**
2018      * Read an existing entry in from a buffer
2019      */
2020     private Entry(ByteBuffer buffer, int entryLen, int extraTrailingLen)
2021       throws IOException
2022     {
2023       // we need 4 trailing bytes for the rowId, plus whatever the caller
2024       // wants
2025       int colEntryLen = entryLen - (4 + extraTrailingLen);
2026 
2027       // read the entry bytes
2028       _entryBytes = ByteUtil.getBytes(buffer, colEntryLen);
2029 
2030       // read the rowId
2031       int page = ByteUtil.get3ByteInt(buffer, ENTRY_BYTE_ORDER);
2032       int row = ByteUtil.getUnsignedByte(buffer);
2033       
2034       _rowId = new RowIdImpl(page, row);
2035       _type = EntryType.NORMAL;
2036     }
2037     
2038     public RowIdImpl getRowId() {
2039       return _rowId;
2040     }
2041 
2042     public EntryType getType() {
2043       return _type;
2044     }
2045 
2046     public Integer getSubPageNumber() {
2047       throw new UnsupportedOperationException();
2048     }
2049     
2050     public boolean isLeafEntry() {
2051       return true;
2052     }
2053     
2054     public boolean isValid() {
2055       return(_entryBytes != null);
2056     }
2057 
2058     protected final byte[] getEntryBytes() {
2059       return _entryBytes;
2060     }
2061     
2062     /**
2063      * Size of this entry in the db.
2064      */
2065     protected int size() {
2066       // need 4 trailing bytes for the rowId
2067       return _entryBytes.length + 4;
2068     }
2069     
2070     /**
2071      * Write this entry into a buffer
2072      */
2073     protected void write(ByteBuffer buffer,
2074                          byte[] prefix)
2075       throws IOException
2076     {
2077       if(prefix.length <= _entryBytes.length) {
2078         
2079         // write entry bytes, not including prefix
2080         buffer.put(_entryBytes, prefix.length,
2081                    (_entryBytes.length - prefix.length));
2082         ByteUtil.put3ByteInt(buffer, getRowId().getPageNumber(),
2083                              ENTRY_BYTE_ORDER);
2084         
2085       } else if(prefix.length <= (_entryBytes.length + 3)) {
2086         
2087         // the prefix includes part of the page number, write to temp buffer
2088         // and copy last bytes to output buffer
2089         ByteBuffer tmp = ByteBuffer.allocate(3);
2090         ByteUtil.put3ByteInt(tmp, getRowId().getPageNumber(),
2091                              ENTRY_BYTE_ORDER);
2092         tmp.flip();
2093         tmp.position(prefix.length - _entryBytes.length);
2094         buffer.put(tmp);
2095         
2096       } else {
2097         
2098         // since the row number would never be the same if the page number is
2099         // the same, nothing past the page number should ever be included in
2100         // the prefix.
2101         // FIXME, this could happen if page has only one row...
2102         throw new IllegalStateException("prefix should never be this long");
2103       }
2104       
2105       buffer.put((byte)getRowId().getRowNumber());
2106     }
2107 
2108     protected final ToStringBuilder entryBytesToStringBuilder(
2109         ToStringBuilder sb) {
2110       if(isValid()) {
2111         sb.append("bytes", _entryBytes);
2112       }
2113       return sb;
2114     }
2115     
2116     @Override
2117     public String toString() {
2118       return entryBytesToStringBuilder(
2119           CustomToStringStyle.valueBuilder(this)
2120           .append("rowId", _rowId))
2121         .toString();
2122     }
2123 
2124     @Override
2125     public int hashCode() {
2126       return _rowId.hashCode();
2127     }
2128 
2129     @Override
2130     public boolean equals(Object o) {
2131       return((this == o) ||
2132              ((o != null) && (getClass() == o.getClass()) &&
2133               (compareTo((Entry)o) == 0)));
2134     }
2135 
2136     /**
2137      * @return {@code true} iff the entryBytes are equal between this
2138      *         Entry and the given Entry
2139      */
2140     public boolean equalsEntryBytes(Entry o) {
2141       return(BYTE_CODE_COMPARATOR.compare(_entryBytes, o._entryBytes) == 0);
2142     }
2143     
2144     public int compareTo(Entry other) {
2145       if (this == other) {
2146         return 0;
2147       }
2148 
2149       if(isValid() && other.isValid()) {
2150 
2151         // comparing two valid entries.  first, compare by actual byte values
2152         int entryCmp = BYTE_CODE_COMPARATOR.compare(
2153             _entryBytes, other._entryBytes);
2154         if(entryCmp != 0) {
2155           return entryCmp;
2156         }
2157 
2158       } else {
2159 
2160         // if the entries are of mixed validity (or both invalid), we defer
2161         // next to the EntryType
2162         int typeCmp = _type.compareTo(other._type);
2163         if(typeCmp != 0) {
2164           return typeCmp;
2165         }
2166       }
2167       
2168       // at this point we let the RowId decide the final result
2169       return _rowId.compareTo(other.getRowId());
2170     }
2171 
2172     /**
2173      * Returns a copy of this entry as a node Entry with the given
2174      * subPageNumber.
2175      */
2176     protected Entry asNodeEntry(Integer subPageNumber) {
2177       return new NodeEntry(_entryBytes, _rowId, _type, subPageNumber);
2178     }
2179     
2180   }
2181 
2182   /**
2183    * A single node entry in an index (points to a sub-page in the index)
2184    */
2185   private static final class NodeEntry extends Entry {
2186 
2187     /** index page number of the page to which this node entry refers */
2188     private final Integer _subPageNumber;
2189 
2190     /**
2191      * Create a new node entry
2192      * @param entryBytes encoded bytes for this index entry
2193      * @param rowId rowId in which the row is stored
2194      * @param type the type of the entry
2195      * @param subPageNumber the sub-page to which this node entry refers
2196      */
2197     private NodeEntry(byte[] entryBytes, RowIdImpl rowId, EntryType type,
2198                       Integer subPageNumber) {
2199       super(entryBytes, rowId, type);
2200       _subPageNumber = subPageNumber;
2201     }
2202     
2203     /**
2204      * Read an existing node entry in from a buffer
2205      */
2206     private NodeEntry(ByteBuffer buffer, int entryLen)
2207       throws IOException
2208     {
2209       // we need 4 trailing bytes for the sub-page number
2210       super(buffer, entryLen, 4);
2211 
2212       _subPageNumber = ByteUtil.getInt(buffer, ENTRY_BYTE_ORDER);
2213     }
2214 
2215     @Override
2216     public Integer getSubPageNumber() {
2217       return _subPageNumber;
2218     }
2219 
2220     @Override
2221     public boolean isLeafEntry() {
2222       return false;
2223     }
2224     
2225     @Override
2226     protected int size() {
2227       // need 4 trailing bytes for the sub-page number
2228       return super.size() + 4;
2229     }
2230     
2231     @Override
2232     protected void write(ByteBuffer buffer, byte[] prefix) throws IOException {
2233       super.write(buffer, prefix);
2234       ByteUtil.putInt(buffer, _subPageNumber, ENTRY_BYTE_ORDER);
2235     }
2236     
2237     @Override
2238     public boolean equals(Object o) {
2239       return((this == o) ||
2240              ((o != null) && (getClass() == o.getClass()) &&
2241               (compareTo((Entry)o) == 0) &&
2242               (getSubPageNumber().equals(((Entry)o).getSubPageNumber()))));
2243     }
2244 
2245     @Override
2246     public String toString() {
2247       return entryBytesToStringBuilder(
2248           CustomToStringStyle.valueBuilder(this)
2249           .append("rowId", getRowId())
2250           .append("subPage", _subPageNumber))
2251         .toString();
2252     }        
2253   }
2254 
2255   /**
2256    * Utility class to traverse the entries in the Index.  Remains valid in the
2257    * face of index entry modifications.
2258    */
2259   public final class EntryCursor
2260   {
2261     /** handler for moving the page cursor forward */
2262     private final DirHandler _forwardDirHandler = new ForwardDirHandler();
2263     /** handler for moving the page cursor backward */
2264     private final DirHandler _reverseDirHandler = new ReverseDirHandler();
2265     /** the first (exclusive) row id for this cursor */
2266     private Position _firstPos;
2267     /** the last (exclusive) row id for this cursor */
2268     private Position _lastPos;
2269     /** the current entry */
2270     private Position _curPos;
2271     /** the previous entry */
2272     private Position _prevPos;
2273     /** the last read modification count on the Index.  we track this so that
2274         the cursor can detect updates to the index while traversing and act
2275         accordingly */
2276     private int _lastModCount;
2277 
2278     private EntryCursor(Position firstPos, Position lastPos)
2279     {
2280       _firstPos = firstPos;
2281       _lastPos = lastPos;
2282       _lastModCount = getIndexModCount();
2283       reset();
2284     }
2285 
2286     /**
2287      * Returns the DirHandler for the given direction
2288      */
2289     private DirHandler getDirHandler(boolean moveForward) {
2290       return (moveForward ? _forwardDirHandler : _reverseDirHandler);
2291     }
2292 
2293     public IndexData getIndexData() {
2294       return IndexData.this;
2295     }
2296 
2297     private int getIndexModCount() {
2298       return IndexData.this._modCount;
2299     }
2300     
2301     /**
2302      * Returns the first entry (exclusive) as defined by this cursor.
2303      */
2304     public Entry getFirstEntry() {
2305       return _firstPos.getEntry();
2306     }
2307   
2308     /**
2309      * Returns the last entry (exclusive) as defined by this cursor.
2310      */
2311     public Entry getLastEntry() {
2312       return _lastPos.getEntry();
2313     }
2314 
2315     /**
2316      * Returns {@code true} if this cursor is up-to-date with respect to its
2317      * index.
2318      */
2319     public boolean isUpToDate() {
2320       return(getIndexModCount() == _lastModCount);
2321     }
2322         
2323     public void reset() {
2324       beforeFirst();
2325     }
2326 
2327     public void beforeFirst() {
2328       reset(CursorImpl.MOVE_FORWARD);
2329     }
2330 
2331     public void afterLast() {
2332       reset(CursorImpl.MOVE_REVERSE);
2333     }
2334 
2335     protected void reset(boolean moveForward)
2336     {
2337       _curPos = getDirHandler(moveForward).getBeginningPosition();
2338       _prevPos = _curPos;
2339     }
2340 
2341     /**
2342      * Repositions the cursor so that the next row will be the first entry
2343      * >= the given row.
2344      */
2345     public void beforeEntry(Object[] row)
2346       throws IOException
2347     {
2348       restorePosition(new Entry(IndexData.this.createEntryBytes(row), 
2349                                 RowIdImpl.FIRST_ROW_ID));
2350     }
2351     
2352     /**
2353      * Repositions the cursor so that the previous row will be the first
2354      * entry <= the given row.
2355      */
2356     public void afterEntry(Object[] row)
2357       throws IOException
2358     {
2359       restorePosition(new Entry(IndexData.this.createEntryBytes(row), 
2360                                 RowIdImpl.LAST_ROW_ID));
2361     }
2362     
2363     /**
2364      * @return valid entry if there was a next entry,
2365      *         {@code #getLastEntry} otherwise
2366      */
2367     public Entry getNextEntry() throws IOException {
2368       return getAnotherPosition(CursorImpl.MOVE_FORWARD).getEntry();
2369     }
2370 
2371     /**
2372      * @return valid entry if there was a next entry,
2373      *         {@code #getFirstEntry} otherwise
2374      */
2375     public Entry getPreviousEntry() throws IOException {
2376       return getAnotherPosition(CursorImpl.MOVE_REVERSE).getEntry();
2377     }
2378 
2379     /**
2380      * Restores a current position for the cursor (current position becomes
2381      * previous position).
2382      */
2383     protected void restorePosition(Entry curEntry)
2384       throws IOException
2385     {
2386       restorePosition(curEntry, _curPos.getEntry());
2387     }
2388     
2389     /**
2390      * Restores a current and previous position for the cursor.
2391      */
2392     protected void restorePosition(Entry curEntry, Entry prevEntry)
2393       throws IOException
2394     {
2395       if(!_curPos.equalsEntry(curEntry) ||
2396          !_prevPos.equalsEntry(prevEntry))
2397       {
2398         if(!isUpToDate()) {
2399           updateBounds();
2400           _lastModCount = getIndexModCount();
2401         }
2402         _prevPos = updatePosition(prevEntry);
2403         _curPos = updatePosition(curEntry);
2404       } else {
2405         checkForModification();
2406       }
2407     }
2408     
2409     /**
2410      * Gets another entry in the given direction, returning the new entry.
2411      */
2412     private Position getAnotherPosition(boolean moveForward)
2413       throws IOException
2414     {
2415       DirHandler handler = getDirHandler(moveForward);
2416       if(_curPos.equals(handler.getEndPosition())) {
2417         if(!isUpToDate()) {
2418           restorePosition(_prevPos.getEntry());
2419           // drop through and retry moving to another entry
2420         } else {
2421           // at end, no more
2422           return _curPos;
2423         }
2424       }
2425 
2426       checkForModification();
2427 
2428       _prevPos = _curPos;
2429       _curPos = handler.getAnotherPosition(_curPos);
2430       return _curPos;
2431     }
2432 
2433     /**
2434      * Checks the index for modifications and updates state accordingly.
2435      */
2436     private void checkForModification()
2437       throws IOException
2438     {
2439       if(!isUpToDate()) {
2440         updateBounds();
2441         _prevPos = updatePosition(_prevPos.getEntry());
2442         _curPos = updatePosition(_curPos.getEntry());
2443         _lastModCount = getIndexModCount();
2444       }
2445     }
2446 
2447     /**
2448      * Updates the given position, taking boundaries into account.
2449      */
2450     private Position updatePosition(Entry entry)
2451       throws IOException
2452     {
2453       if(!entry.isValid()) {
2454         // no use searching if "updating" the first/last pos
2455         if(_firstPos.equalsEntry(entry)) {
2456           return _firstPos;
2457         } else if(_lastPos.equalsEntry(entry)) {
2458           return _lastPos;
2459         } else {
2460           throw new IllegalArgumentException(
2461               withErrorContext("Invalid entry given " + entry));
2462         }
2463       }
2464       
2465       Position pos = findEntryPosition(entry);
2466       if(pos.compareTo(_lastPos) >= 0) {
2467         return _lastPos;
2468       } else if(pos.compareTo(_firstPos) <= 0) {
2469         return _firstPos;
2470       }
2471       return pos;
2472     }
2473     
2474     /**
2475      * Updates any the boundary info (_firstPos/_lastPos).
2476      */
2477     private void updateBounds()
2478       throws IOException
2479     {
2480       _firstPos = findEntryPosition(_firstPos.getEntry());
2481       _lastPos = findEntryPosition(_lastPos.getEntry());
2482     }
2483         
2484     @Override
2485     public String toString() {
2486       return CustomToStringStyle.valueBuilder(this)
2487         .append("curPosition", _curPos)
2488         .append("prevPosition", _prevPos)
2489         .toString();
2490     }
2491     
2492     /**
2493      * Handles moving the cursor in a given direction.  Separates cursor
2494      * logic from value storage.
2495      */
2496     private abstract class DirHandler {
2497       public abstract Position getAnotherPosition(Position curPos)
2498         throws IOException;
2499       public abstract Position getBeginningPosition();
2500       public abstract Position getEndPosition();
2501     }
2502         
2503     /**
2504      * Handles moving the cursor forward.
2505      */
2506     private final class ForwardDirHandler extends DirHandler {
2507       @Override
2508       public Position getAnotherPosition(Position curPos)
2509         throws IOException
2510       {
2511         Position newPos = getNextPosition(curPos);
2512         if((newPos == null) || (newPos.compareTo(_lastPos) >= 0)) {
2513           newPos = _lastPos;
2514         }
2515         return newPos;
2516       }
2517       @Override
2518       public Position getBeginningPosition() {
2519         return _firstPos;
2520       }
2521       @Override
2522       public Position getEndPosition() {
2523         return _lastPos;
2524       }
2525     }
2526         
2527     /**
2528      * Handles moving the cursor backward.
2529      */
2530     private final class ReverseDirHandler extends DirHandler {
2531       @Override
2532       public Position getAnotherPosition(Position curPos)
2533         throws IOException
2534       {
2535         Position newPos = getPreviousPosition(curPos);
2536         if((newPos == null) || (newPos.compareTo(_firstPos) <= 0)) {
2537           newPos = _firstPos;
2538         }
2539         return newPos;
2540       }
2541       @Override
2542       public Position getBeginningPosition() {
2543         return _lastPos;
2544       }
2545       @Override
2546       public Position getEndPosition() {
2547         return _firstPos;
2548       }
2549     }
2550   }
2551 
2552   /**
2553    * Simple value object for maintaining some cursor state.
2554    */
2555   private static final class Position implements Comparable<Position> {
2556     /** the last known page of the given entry */
2557     private final DataPage _dataPage;
2558     /** the last known index of the given entry */
2559     private final int _idx;
2560     /** the entry at the given index */
2561     private final Entry _entry;
2562     /** {@code true} if this entry does not currently exist in the entry list,
2563         {@code false} otherwise (this is equivalent to adding -0.5 to the
2564         _idx) */
2565     private final boolean _between;
2566 
2567     private Position(DataPage dataPage, int idx)
2568     {
2569       this(dataPage, idx, dataPage.getEntries().get(idx), false);
2570     }
2571     
2572     private Position(DataPage dataPage, int idx, Entry entry, boolean between)
2573     {
2574       _dataPage = dataPage;
2575       _idx = idx;
2576       _entry = entry;
2577       _between = between;
2578     }
2579 
2580     public DataPage getDataPage() {
2581       return _dataPage;
2582     }
2583     
2584     public int getIndex() {
2585       return _idx;
2586     }
2587 
2588     public int getNextIndex() {
2589       // note, _idx does not need to be advanced if it was pointing at a
2590       // between position
2591       return(_between ? _idx : (_idx + 1));
2592     }
2593 
2594     public int getPrevIndex() {
2595       // note, we ignore the between flag here because the index will be
2596       // pointing at the correct next index in either the between or
2597       // non-between case
2598       return(_idx - 1);
2599     }
2600     
2601     public Entry getEntry() {
2602       return _entry;
2603     }
2604 
2605     public boolean isBetween() {
2606       return _between;
2607     }
2608 
2609     public boolean equalsEntry(Entry entry) {
2610       return _entry.equals(entry);
2611     }
2612     
2613     public int compareTo(Position other)
2614     {
2615       if(this == other) {
2616         return 0;
2617       }
2618 
2619       if(_dataPage.equals(other._dataPage)) {
2620         // "simple" index comparison (handle between-ness)
2621         int idxCmp = ((_idx < other._idx) ? -1 :
2622                       ((_idx > other._idx) ? 1 :
2623                        ((_between == other._between) ? 0 :
2624                         (_between ? -1 : 1))));
2625         if(idxCmp != 0) {
2626           return idxCmp;
2627         }
2628       }
2629       
2630       // compare the entries.
2631       return _entry.compareTo(other._entry);
2632     }
2633     
2634     @Override
2635     public int hashCode() {
2636       return _entry.hashCode();
2637     }
2638     
2639     @Override
2640     public boolean equals(Object o) {
2641       return((this == o) ||
2642              ((o != null) && (getClass() == o.getClass()) &&
2643               (compareTo((Position)o) == 0)));
2644     }
2645 
2646     @Override
2647     public String toString() {
2648       return CustomToStringStyle.valueBuilder(this)
2649         .append("page", _dataPage.getPageNumber())
2650         .append("idx", _idx)
2651         .append("entry", _entry)
2652         .append("between", _between)
2653         .toString();
2654     }
2655   }
2656 
2657   /**
2658    * Object used to maintain state about an Index page.
2659    */
2660   protected static abstract class DataPage {
2661 
2662     public abstract int getPageNumber();
2663     
2664     public abstract boolean isLeaf();
2665     public abstract void setLeaf(boolean isLeaf);
2666 
2667     public abstract int getPrevPageNumber();
2668     public abstract void setPrevPageNumber(int pageNumber);
2669     public abstract int getNextPageNumber();
2670     public abstract void setNextPageNumber(int pageNumber);
2671     public abstract int getChildTailPageNumber();
2672     public abstract void setChildTailPageNumber(int pageNumber);
2673     
2674     public abstract int getTotalEntrySize();
2675     public abstract void setTotalEntrySize(int totalSize);
2676     public abstract byte[] getEntryPrefix();
2677     public abstract void setEntryPrefix(byte[] entryPrefix);
2678 
2679     public abstract List<Entry> getEntries();
2680     public abstract void setEntries(List<Entry> entries);
2681 
2682     public abstract void addEntry(int idx, Entry entry)
2683       throws IOException;
2684     public abstract Entry removeEntry(int idx)
2685       throws IOException;
2686 
2687     public final boolean isEmpty() {
2688       return getEntries().isEmpty();
2689     }
2690     
2691     public final int getCompressedEntrySize() {
2692       // when written to the index page, the entryPrefix bytes will only be
2693       // written for the first entry, so we subtract the entry prefix size
2694       // from all the other entries to determine the compressed size
2695       return getTotalEntrySize() -
2696         (getEntryPrefix().length * (getEntries().size() - 1));
2697     }
2698 
2699     public final int findEntry(Entry entry) {
2700       return Collections.binarySearch(getEntries(), entry);
2701     }
2702 
2703     @Override
2704     public final int hashCode() {
2705       return getPageNumber();
2706     }
2707 
2708     @Override
2709     public final boolean equals(Object o) {
2710       return((this == o) ||
2711              ((o != null) && (getClass() == o.getClass()) &&
2712               (getPageNumber() == ((DataPage)o).getPageNumber())));
2713     }
2714 
2715     @Override
2716     public final String toString() {
2717       List<Entry> entries = getEntries();
2718 
2719       String objName = 
2720         (isLeaf() ? "Leaf" : "Node") + "DataPage[" + getPageNumber() +
2721         "] " + getPrevPageNumber() + ", " + getNextPageNumber() + ", (" +
2722         getChildTailPageNumber() + ")";
2723       ToStringBuilder sb = CustomToStringStyle.valueBuilder(objName);
2724 
2725       if((isLeaf() && !entries.isEmpty())) {
2726         sb.append("entryRange", "[" + entries.get(0) + ", " +
2727                   entries.get(entries.size() - 1) + "]");
2728       } else {
2729         sb.append("entries", entries);
2730       }
2731       return sb.toString();
2732     }
2733   }
2734 
2735   /**
2736    * Simple implementation of a DataPage
2737    */
2738   private static final class RootDataPage extends DataPage {
2739 
2740     @Override
2741     public int getPageNumber() { return 0; }
2742     
2743     @Override
2744     public boolean isLeaf() { return true; }
2745     @Override
2746     public void setLeaf(boolean isLeaf) { }
2747 
2748     @Override
2749     public int getPrevPageNumber() { return 0; }
2750     @Override
2751     public void setPrevPageNumber(int pageNumber) { }
2752 
2753     @Override
2754     public int getNextPageNumber() { return 0; }
2755     @Override
2756     public void setNextPageNumber(int pageNumber) { }
2757 
2758     @Override
2759     public int getChildTailPageNumber() { return 0; }
2760     @Override
2761     public void setChildTailPageNumber(int pageNumber) { }
2762     
2763     @Override
2764     public int getTotalEntrySize() { return 0; }
2765     @Override
2766     public void setTotalEntrySize(int totalSize) { }
2767 
2768     @Override
2769     public byte[] getEntryPrefix() { return EMPTY_PREFIX; }
2770     @Override
2771     public void setEntryPrefix(byte[] entryPrefix) { }
2772 
2773     @Override
2774     public List<Entry> getEntries() { return Collections.emptyList(); }    
2775     @Override
2776     public void setEntries(List<Entry> entries) { }
2777     @Override
2778     public void addEntry(int idx, Entry entry) { }
2779     @Override
2780     public Entry removeEntry(int idx) { return null; }
2781   }
2782 
2783   /**
2784    * Utility class which maintains information about a pending index update.
2785    * An instance of this class can be used to complete the change (by calling
2786    * {@link #commit}) or undo the change (by calling {@link #rollback}).
2787    */
2788   public static abstract class PendingChange
2789   {
2790     private final PendingChange _next;
2791 
2792     private PendingChange(PendingChange next) {
2793       _next = next;
2794     }
2795 
2796     /**
2797      * Returns the next pending change, if any
2798      */
2799     public PendingChange getNext() {
2800       return _next;
2801     }
2802     
2803     /**
2804      * Completes the pending change.
2805      */
2806     public abstract void commit() throws IOException;
2807 
2808     /**
2809      * Undoes the pending change.
2810      */
2811     public abstract void rollback() throws IOException;
2812   }
2813 
2814   /**
2815    * PendingChange for a row addition.
2816    */
2817   private class AddRowPendingChange extends PendingChange
2818   {
2819     protected Entry _addEntry;
2820     protected DataPage _addDataPage;
2821     protected int _addIdx;
2822     protected boolean _isDupe;
2823     protected Entry _oldEntry;
2824 
2825     private AddRowPendingChange(PendingChange next) {
2826       super(next);
2827     }
2828 
2829     public void setAddRow(Entry addEntry, DataPage dataPage, int idx, 
2830                           boolean isDupe) {
2831       _addEntry = addEntry;
2832       _addDataPage = dataPage;
2833       _addIdx = idx;
2834       _isDupe = isDupe;
2835     }
2836 
2837     public void setOldRow(Entry oldEntry) {
2838       _oldEntry = oldEntry;
2839     }
2840 
2841     @Override
2842     public void commit() throws IOException {
2843       commitAddRow(_addEntry, _addDataPage, _addIdx, _isDupe, _oldEntry);
2844     }
2845     
2846     @Override
2847     public void rollback() throws IOException {
2848       _addEntry = null;
2849       _addDataPage = null;
2850       _addIdx = -1;
2851     }
2852   }
2853 
2854   /**
2855    * PendingChange for a row update (which is essentially a deletion followed
2856    * by an addition).
2857    */
2858   private class UpdateRowPendingChange extends AddRowPendingChange
2859   {
2860     private UpdateRowPendingChange(PendingChange next) {
2861       super(next);
2862     }
2863 
2864     @Override
2865     public void rollback() throws IOException {
2866       super.rollback();
2867       rollbackDeletedRow(_oldEntry);
2868     }
2869   }
2870 
2871 }