View Javadoc
1   /*
2   Copyright (c) 2008 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.lang.ref.Reference;
21  import java.lang.ref.SoftReference;
22  import java.util.AbstractList;
23  import java.util.ArrayList;
24  import java.util.Collections;
25  import java.util.Iterator;
26  import java.util.LinkedHashMap;
27  import java.util.List;
28  import java.util.Map;
29  import java.util.RandomAccess;
30  
31  import static com.healthmarketscience.jackcess.impl.IndexData.*;
32  import org.apache.commons.lang.builder.ToStringBuilder;
33  
34  /**
35   * Manager of the index pages for a IndexData.
36   * @author James Ahlborn
37   */
38  public class IndexPageCache
39  {
40    private enum UpdateType {
41      ADD, REMOVE, REPLACE;
42    }
43  
44    /** max number of pages to cache (unless a write operation is in
45        progress) */
46    private static final int MAX_CACHE_SIZE = 25;
47    
48    /** the index whose pages this cache is managing */
49    private final IndexData _indexData;
50    /** the root page for the index */
51    private DataPageMain _rootPage;
52    /** the currently loaded pages for this index, pageNumber -> page */
53    private final Map<Integer, DataPageMain> _dataPages =
54      new LinkedHashMap<Integer, DataPageMain>(16, 0.75f, true) {
55      private static final long serialVersionUID = 0L;
56      @Override
57      protected boolean removeEldestEntry(Map.Entry<Integer, DataPageMain> e) {
58        // only purge when the size is too big and a logical write operation is
59        // not in progress (while an update is happening, the pages can be in
60        // flux and removing pages from the cache can cause problems)
61        if((size() > MAX_CACHE_SIZE) && !getPageChannel().isWriting()) {
62          purgeOldPages();
63        }
64        return false;
65      }
66    };
67    /** the currently modified index pages */
68    private final List<CacheDataPage> _modifiedPages =
69      new ArrayList<CacheDataPage>();
70    
71    public IndexPageCache(IndexData indexData) {
72      _indexData = indexData;
73    }
74  
75    public IndexData getIndexData() {
76      return _indexData;
77    }
78    
79    public PageChannel getPageChannel() {
80      return getIndexData().getPageChannel();
81    }
82    
83    /**
84     * Sets the root page for this index, must be called before normal usage.
85     *
86     * @param pageNumber the root page number
87     */
88    public void setRootPageNumber(int pageNumber) throws IOException {
89      _rootPage = getDataPage(pageNumber);
90      // root page has no parent
91      _rootPage.initParentPage(INVALID_INDEX_PAGE_NUMBER, false);
92    }
93    
94    /**
95     * Writes any outstanding changes for this index to the file.
96     */
97    public void write()
98      throws IOException
99    {
100     // first discard any empty pages
101     handleEmptyPages();
102     // next, handle any necessary page splitting
103     preparePagesForWriting();
104     // finally, write all the modified pages (which are not being deleted)
105     writeDataPages();
106     // after we write everything, we can purge our cache if necessary
107     if(_dataPages.size() > MAX_CACHE_SIZE) {
108       purgeOldPages();
109     }
110   }
111 
112   /**
113    * Handles any modified pages which are empty as the first pass during a
114    * {@link #write} call.  All empty pages are removed from the _modifiedPages
115    * collection by this method.
116    */
117   private void handleEmptyPages() throws IOException
118   {
119     for(Iterator<CacheDataPage> iter = _modifiedPages.iterator();
120         iter.hasNext(); ) {
121       CacheDataPage cacheDataPage = iter.next();
122       if(cacheDataPage._extra._entryView.isEmpty()) {
123         if(!cacheDataPage._main.isRoot()) {
124           deleteDataPage(cacheDataPage);
125         } else {
126           writeDataPage(cacheDataPage);
127         }
128         iter.remove();
129       }
130     }
131   }
132   
133   /**
134    * Prepares any non-empty modified pages for writing as the second pass
135    * during a {@link #write} call.  Updates entry prefixes, promotes/demotes
136    * tail pages, and splits pages as needed.
137    */
138   private void preparePagesForWriting() throws IOException
139   {
140     boolean splitPages = false;
141     int maxPageEntrySize = getIndexData().getMaxPageEntrySize();
142 
143     // we need to continue looping through all the pages until we do not split
144     // any pages (because a split may cascade up the tree)
145     do {
146       splitPages = false;
147 
148       // we might be adding to this list while iterating, so we can't use an
149       // iterator
150       for(int i = 0; i < _modifiedPages.size(); ++i) {
151 
152         CacheDataPage cacheDataPage = _modifiedPages.get(i);
153 
154         if(!cacheDataPage.isLeaf()) {
155           // see if we need to update any child tail status
156           DataPageMain dpMain = cacheDataPage._main;
157           int size = cacheDataPage._extra._entryView.size();
158           if(dpMain.hasChildTail()) {
159             if(size == 1) {
160               demoteTail(cacheDataPage);
161             } 
162           } else {
163             if(size > 1) {
164               promoteTail(cacheDataPage);
165             }
166           }
167         }
168         
169         // look for pages with more entries than can fit on a page
170         if(cacheDataPage.getTotalEntrySize() > maxPageEntrySize) {
171 
172           // make sure the prefix is up-to-date (this may have gotten
173           // discarded by one of the update entry methods)
174           cacheDataPage._extra.updateEntryPrefix();
175 
176           // now, see if the page will fit when compressed
177           if(cacheDataPage.getCompressedEntrySize() > maxPageEntrySize) {
178             // need to split this page
179             splitPages = true;
180             splitDataPage(cacheDataPage);
181           }
182         }
183       }
184       
185     } while(splitPages);
186   }
187 
188   /**
189    * Writes any non-empty modified pages as the last pass during a
190    * {@link #write} call.  Clears the _modifiedPages collection when finised.
191    */
192   private void writeDataPages() throws IOException
193   {
194     for(CacheDataPage cacheDataPage : _modifiedPages) {
195       if(cacheDataPage._extra._entryView.isEmpty()) {
196         throw new IllegalStateException(withErrorContext(
197                 "Unexpected empty page " + cacheDataPage));
198       }
199       writeDataPage(cacheDataPage);
200     }
201     _modifiedPages.clear();
202   }
203 
204   /**
205    * Returns a CacheDataPage for the given page number, may be {@code null} if
206    * the given page number is invalid.  Loads the given page if necessary.
207    */
208   public CacheDataPage getCacheDataPage(Integer pageNumber)
209     throws IOException
210   {
211     DataPageMain main = getDataPage(pageNumber);
212     return((main != null) ? new CacheDataPage(main) : null);
213   }
214   
215   /**
216    * Returns a DataPageMain for the given page number, may be {@code null} if
217    * the given page number is invalid.  Loads the given page if necessary.
218    */
219   private DataPageMain getDataPage(Integer pageNumber)
220     throws IOException
221   {
222     DataPageMain dataPage = _dataPages.get(pageNumber);
223     if((dataPage == null) && (pageNumber > INVALID_INDEX_PAGE_NUMBER)) {
224       dataPage = readDataPage(pageNumber)._main;
225       _dataPages.put(pageNumber, dataPage);
226     }
227     return dataPage;
228   }
229 
230   /**
231    * Writes the given index page to the file.
232    */
233   private void writeDataPage(CacheDataPage cacheDataPage)
234     throws IOException
235   {
236     getIndexData().writeDataPage(cacheDataPage);
237 
238     // lastly, mark the page as no longer modified
239     cacheDataPage._extra._modified = false;    
240   }
241   
242   /**
243    * Deletes the given index page from the file (clears the page).
244    */
245   private void deleteDataPage(CacheDataPage cacheDataPage)
246     throws IOException
247   {
248     // free this database page
249     getPageChannel().deallocatePage(cacheDataPage._main._pageNumber);
250 
251     // discard from our cache
252     _dataPages.remove(cacheDataPage._main._pageNumber);
253     
254     // lastly, mark the page as no longer modified
255     cacheDataPage._extra._modified = false;    
256   }
257   
258   /**
259    * Reads the given index page from the file.
260    */
261   private CacheDataPage readDataPage(Integer pageNumber)
262     throws IOException
263   {
264     DataPageMain dataPage = new DataPageMain(pageNumber);
265     DataPageExtra extra = new DataPageExtra();
266     CacheDataPage cacheDataPage = new CacheDataPage(dataPage, extra);
267     getIndexData().readDataPage(cacheDataPage);
268 
269     // associate the extra info with the main data page
270     dataPage.setExtra(extra);
271     
272     return cacheDataPage;
273   }  
274 
275   /**
276    * Removes the entry with the given index from the given page.
277    *
278    * @param cacheDataPage the page from which to remove the entry
279    * @param entryIdx the index of the entry to remove
280    */
281   private Entry removeEntry(CacheDataPage cacheDataPage, int entryIdx)
282     throws IOException
283   {
284     return updateEntry(cacheDataPage, entryIdx, null, UpdateType.REMOVE);
285   }
286 
287   /**
288    * Adds the entry to the given page at the given index.
289    *
290    * @param cacheDataPage the page to which to add the entry
291    * @param entryIdx the index at which to add the entry
292    * @param newEntry the entry to add
293    */
294   private void addEntry(CacheDataPage cacheDataPage,
295                         int entryIdx,
296                         Entry newEntry)
297     throws IOException
298   {
299     updateEntry(cacheDataPage, entryIdx, newEntry, UpdateType.ADD);
300   }
301   
302   /**
303    * Updates the entries on the given page according to the given updateType.
304    *
305    * @param cacheDataPage the page to update
306    * @param entryIdx the index at which to add/remove/replace the entry
307    * @param newEntry the entry to add/replace
308    * @param upType the type of update to make
309    */
310   private Entry updateEntry(CacheDataPage cacheDataPage,
311                             int entryIdx,
312                             Entry newEntry,
313                             UpdateType upType)
314     throws IOException
315   {
316     DataPageMain dpMain = cacheDataPage._main;
317     DataPageExtra dpExtra = cacheDataPage._extra;
318 
319     if(newEntry != null) {
320       validateEntryForPage(dpMain, newEntry);
321     }
322 
323     // note, it's slightly ucky, but we need to load the parent page before we
324     // start mucking with our entries because our parent may use our entries.
325     CacheDataPage parentDataPage = (!dpMain.isRoot() ?
326                                     new CacheDataPage(dpMain.getParentPage()) :
327                                     null);
328     
329     Entry oldLastEntry = dpExtra._entryView.getLast();
330     Entry oldEntry = null;
331     int entrySizeDiff = 0;
332 
333     switch(upType) {
334     case ADD:
335       dpExtra._entryView.add(entryIdx, newEntry);
336       entrySizeDiff += newEntry.size();
337       break;
338 
339     case REPLACE:
340       oldEntry = dpExtra._entryView.set(entryIdx, newEntry);
341       entrySizeDiff += newEntry.size() - oldEntry.size();
342       break;
343 
344     case REMOVE: {
345       oldEntry = dpExtra._entryView.remove(entryIdx);
346       entrySizeDiff -= oldEntry.size();
347       break;
348     }
349     default:
350       throw new RuntimeException(withErrorContext(
351               "unknown update type " + upType));
352     }
353 
354     boolean updateLast = (oldLastEntry != dpExtra._entryView.getLast());
355     
356     // child tail entry updates do not modify the page
357     if(!updateLast || !dpMain.hasChildTail()) {
358       dpExtra._totalEntrySize += entrySizeDiff;
359       setModified(cacheDataPage);
360 
361       // for now, just clear the prefix, we'll fix it later
362       dpExtra._entryPrefix = EMPTY_PREFIX;
363     }
364 
365     if(dpExtra._entryView.isEmpty()) {
366       // this page is dead
367       removeDataPage(parentDataPage, cacheDataPage, oldLastEntry);
368       return oldEntry;
369     }
370 
371     // determine if we need to update our parent page 
372     if(!updateLast || dpMain.isRoot()) {
373       // no parent
374       return oldEntry;
375     }
376 
377     // the update to the last entry needs to be propagated to our parent
378     replaceParentEntry(parentDataPage, cacheDataPage, oldLastEntry);
379     return oldEntry;
380   }
381 
382   /**
383    * Removes an index page which has become empty.  If this page is the root
384    * page, just clears it.
385    *
386    * @param parentDataPage the parent of the removed page
387    * @param cacheDataPage the page to remove
388    * @param oldLastEntry the last entry for this page (before it was removed)
389    */
390   private void removeDataPage(CacheDataPage parentDataPage,
391                               CacheDataPage cacheDataPage,
392                               Entry oldLastEntry)
393     throws IOException
394   {
395     DataPageMain dpMain = cacheDataPage._main;
396     DataPageExtra dpExtra = cacheDataPage._extra;
397 
398     if(dpMain.hasChildTail()) {
399       throw new IllegalStateException(withErrorContext("Still has child tail?"));
400     }
401 
402     if(dpExtra._totalEntrySize != 0) {
403       throw new IllegalStateException(withErrorContext(
404               "Empty page but size is not 0? " + dpExtra._totalEntrySize + ", " +
405               cacheDataPage));
406     }
407     
408     if(dpMain.isRoot()) {
409       // clear out this page (we don't actually remove it)
410       dpExtra._entryPrefix = EMPTY_PREFIX;
411       // when the root page becomes empty, it becomes a leaf page again
412       dpMain._leaf = true;
413       return;
414     }
415 
416     // remove this page from its parent page
417     updateParentEntry(parentDataPage, cacheDataPage, oldLastEntry, null,
418                       UpdateType.REMOVE);
419 
420     // remove this page from any next/prev pages
421     removeFromPeers(cacheDataPage);
422   }
423 
424   /**
425    * Removes a now empty index page from its next and previous peers.
426    *
427    * @param cacheDataPage the page to remove
428    */
429   private void removeFromPeers(CacheDataPage cacheDataPage)
430     throws IOException
431   {
432     DataPageMain dpMain = cacheDataPage._main;
433 
434     Integer prevPageNumber = dpMain._prevPageNumber;
435     Integer nextPageNumber = dpMain._nextPageNumber;
436     
437     DataPageMain prevMain = dpMain.getPrevPage();
438     if(prevMain != null) {
439       setModified(new CacheDataPage(prevMain));
440       prevMain._nextPageNumber = nextPageNumber;
441     }
442 
443     DataPageMain nextMain = dpMain.getNextPage();
444     if(nextMain != null) {
445       setModified(new CacheDataPage(nextMain));
446       nextMain._prevPageNumber = prevPageNumber;
447     }
448   }
449 
450   /**
451    * Adds an entry for the given child page to the given parent page.
452    *
453    * @param parentDataPage the parent page to which to add the entry
454    * @param childDataPage the child from which to get the entry to add
455    */
456   private void addParentEntry(CacheDataPage parentDataPage,
457                               CacheDataPage childDataPage)
458     throws IOException
459   {
460     DataPageExtra childExtra = childDataPage._extra;
461     updateParentEntry(parentDataPage, childDataPage, null,
462                       childExtra._entryView.getLast(), UpdateType.ADD);
463   }
464   
465   /**
466    * Replaces the entry for the given child page in the given parent page.
467    *
468    * @param parentDataPage the parent page in which to replace the entry
469    * @param childDataPage the child for which the entry is being replaced
470    * @param oldEntry the old child entry for the child page
471    */
472   private void replaceParentEntry(CacheDataPage parentDataPage,
473                                   CacheDataPage childDataPage,
474                                   Entry oldEntry)
475     throws IOException
476   {
477     DataPageExtra childExtra = childDataPage._extra;
478     updateParentEntry(parentDataPage, childDataPage, oldEntry,
479                       childExtra._entryView.getLast(), UpdateType.REPLACE);
480   }
481   
482   /**
483    * Updates the entry for the given child page in the given parent page
484    * according to the given updateType.
485    *
486    * @param parentDataPage the parent page in which to update the entry
487    * @param childDataPage the child for which the entry is being updated
488    * @param oldEntry the old child entry to remove/replace
489    * @param newEntry the new child entry to replace/add
490    * @param upType the type of update to make
491    */
492   private void updateParentEntry(CacheDataPage parentDataPage,
493                                  CacheDataPage childDataPage,
494                                  Entry oldEntry, Entry newEntry,
495                                  UpdateType upType)
496     throws IOException
497   {
498     DataPageMain childMain = childDataPage._main;
499     DataPageExtra parentExtra = parentDataPage._extra;
500 
501     if(childMain.isTail() && (upType != UpdateType.REMOVE)) {
502       // for add or replace, update the child tail info before updating the
503       // parent entries
504       updateParentTail(parentDataPage, childDataPage, upType);
505     }
506 
507     if(oldEntry != null) {
508       oldEntry = oldEntry.asNodeEntry(childMain._pageNumber);
509     }
510     if(newEntry != null) {
511       newEntry = newEntry.asNodeEntry(childMain._pageNumber);
512     }
513 
514     boolean expectFound = true;
515     int idx = 0;
516     
517     switch(upType) {
518     case ADD:
519       expectFound = false;
520       idx = parentExtra._entryView.find(newEntry);
521       break;
522 
523     case REPLACE:
524     case REMOVE:
525       idx = parentExtra._entryView.find(oldEntry);
526       break;
527     
528     default:
529       throw new RuntimeException(withErrorContext(
530               "unknown update type " + upType));
531     }
532         
533     if(idx < 0) {
534       if(expectFound) {
535         throw new IllegalStateException(withErrorContext(
536             "Could not find child entry in parent; childEntry " + oldEntry +
537             "; parent " + parentDataPage));
538       }
539       idx = missingIndexToInsertionPoint(idx);
540     } else {
541       if(!expectFound) {
542         throw new IllegalStateException(withErrorContext(
543             "Unexpectedly found child entry in parent; childEntry " +
544             newEntry + "; parent " + parentDataPage));
545       }
546     }
547     updateEntry(parentDataPage, idx, newEntry, upType);
548 
549     if(childMain.isTail() && (upType == UpdateType.REMOVE)) {
550       // for remove, update the child tail info after updating the parent
551       // entries
552       updateParentTail(parentDataPage, childDataPage, upType);
553     }
554   }
555 
556   /**
557    * Updates the child tail info in the given parent page according to the
558    * given updateType.
559    *
560    * @param parentDataPage the parent page in which to update the child tail
561    * @param childDataPage the child to add/replace
562    * @param upType the type of update to make
563    */
564   private void updateParentTail(CacheDataPage parentDataPage,
565                                 CacheDataPage childDataPage,
566                                 UpdateType upType)
567     throws IOException
568   {
569     DataPageMain parentMain = parentDataPage._main;
570 
571     int newChildTailPageNumber =
572       ((upType == UpdateType.REMOVE) ?
573        INVALID_INDEX_PAGE_NUMBER :
574        childDataPage._main._pageNumber);
575     if(!parentMain.isChildTailPageNumber(newChildTailPageNumber)) {
576       setModified(parentDataPage);
577       parentMain._childTailPageNumber = newChildTailPageNumber;
578     }
579   }
580   
581   /**
582    * Verifies that the given entry type (node/leaf) is valid for the given
583    * page (node/leaf).
584    *
585    * @param dpMain the page to which the entry will be added
586    * @param entry the entry being added
587    * @throws IllegalStateException if the entry type does not match the page
588    *         type
589    */
590   private void validateEntryForPage(DataPageMain dpMain, Entry entry) {
591     if(dpMain._leaf != entry.isLeafEntry()) {
592       throw new IllegalStateException(withErrorContext(
593           "Trying to update page with wrong entry type; pageLeaf " +
594           dpMain._leaf + ", entryLeaf " + entry.isLeafEntry()));
595     }
596   }
597 
598   /**
599    * Splits an index page which has too many entries on it.
600    *
601    * @param origDataPage the page to split
602    */
603   private void splitDataPage(CacheDataPage origDataPage)
604     throws IOException
605   {
606     DataPageMain origMain = origDataPage._main;
607     DataPageExtra origExtra = origDataPage._extra;
608 
609     setModified(origDataPage);
610     
611     int numEntries = origExtra._entries.size();
612     if(numEntries < 2) {
613       throw new IllegalStateException(withErrorContext(
614               "Cannot split page with less than 2 entries " + origDataPage));
615     }
616     
617     if(origMain.isRoot()) {
618       // we can't split the root page directly, so we need to put another page
619       // between the root page and its sub-pages, and then split that page.
620       CacheDataPage newDataPage = nestRootDataPage(origDataPage);
621 
622       // now, split this new page instead
623       origDataPage = newDataPage;
624       origMain = newDataPage._main;
625       origExtra = newDataPage._extra;
626     }
627 
628     // note, it's slightly ucky, but we need to load the parent page before we
629     // start mucking with our entries because our parent may use our entries.
630     DataPageMain parentMain = origMain.getParentPage();
631     CacheDataPage parentDataPage = new CacheDataPage(parentMain);
632     
633     // note, there are many, many ways this could be improved/tweaked.  for
634     // now, we just want it to be functional...
635     // so, we will naively move half the entries from one page to a new page.
636 
637     CacheDataPage newDataPage = allocateNewCacheDataPage(
638         parentMain._pageNumber, origMain._leaf);
639     DataPageMain newMain = newDataPage._main;
640     DataPageExtra newExtra = newDataPage._extra;
641     
642     List<Entry> headEntries =
643       origExtra._entries.subList(0, ((numEntries + 1) / 2));
644 
645     // move first half of the entries from old page to new page (so we do not
646     // need to muck with any tail entries)
647     for(Entry headEntry : headEntries) {
648       newExtra._totalEntrySize += headEntry.size();
649       newExtra._entries.add(headEntry);
650     }
651     newExtra.setEntryView(newMain);
652 
653     // remove the moved entries from the old page
654     headEntries.clear();
655     origExtra._entryPrefix = EMPTY_PREFIX;
656     origExtra._totalEntrySize -= newExtra._totalEntrySize;
657 
658     // insert this new page between the old page and any previous page
659     addToPeersBefore(newDataPage, origDataPage);
660     
661     if(!newMain._leaf) {
662       // reparent the children pages of the new page
663       reparentChildren(newDataPage);
664 
665       // if the children of this page are also node pages, then the next/prev
666       // links should not cross parent boundaries (the leaf pages are linked
667       // from beginning to end, but child node pages are only linked within
668       // the same parent)
669       DataPageMain childMain = newMain.getChildPage(
670           newExtra._entryView.getLast());
671       if(!childMain._leaf) {
672         separateFromNextPeer(new CacheDataPage(childMain));
673       }
674     }
675 
676     // lastly, we need to add the new page to the parent page's entries
677     addParentEntry(parentDataPage, newDataPage);
678   }
679 
680   /**
681    * Copies the current root page info into a new page and nests this page
682    * under the root page.  This must be done when the root page needs to be
683    * split.
684    *
685    * @param rootDataPage the root data page
686    * 
687    * @return the newly created page nested under the root page
688    */
689   private CacheDataPage nestRootDataPage(CacheDataPage rootDataPage)
690     throws IOException
691   {
692     DataPageMain rootMain = rootDataPage._main;
693     DataPageExtra rootExtra = rootDataPage._extra;
694 
695     if(!rootMain.isRoot()) {
696       throw new IllegalArgumentException(withErrorContext(
697               "should be called with root, duh"));
698     }
699     
700     CacheDataPage newDataPage =
701       allocateNewCacheDataPage(rootMain._pageNumber, rootMain._leaf);
702     DataPageMain newMain = newDataPage._main;
703     DataPageExtra newExtra = newDataPage._extra;
704 
705     // move entries to new page
706     newMain._childTailPageNumber = rootMain._childTailPageNumber;
707     newExtra._entries = rootExtra._entries;
708     newExtra._entryPrefix = rootExtra._entryPrefix;
709     newExtra._totalEntrySize = rootExtra._totalEntrySize;
710     newExtra.setEntryView(newMain);
711 
712     if(!newMain._leaf) {
713       // we need to re-parent all the child pages
714       reparentChildren(newDataPage);
715     }
716       
717     // clear the root page
718     rootMain._leaf = false;
719     rootMain._childTailPageNumber = INVALID_INDEX_PAGE_NUMBER;
720     rootExtra._entries = new ArrayList<Entry>();
721     rootExtra._entryPrefix = EMPTY_PREFIX;
722     rootExtra._totalEntrySize = 0;
723     rootExtra.setEntryView(rootMain);
724 
725     // add the new page as the first child of the root page
726     addParentEntry(rootDataPage, newDataPage);
727 
728     return newDataPage;
729   }
730   
731   /**
732    * Allocates a new index page with the given parent page and type.
733    *
734    * @param parentPageNumber the parent page for the new page
735    * @param isLeaf whether or not the new page is a leaf page
736    *
737    * @return the newly created page
738    */
739   private CacheDataPage allocateNewCacheDataPage(Integer parentPageNumber,
740                                                  boolean isLeaf)
741     throws IOException
742   {
743     DataPageMain dpMain = new DataPageMain(getPageChannel().allocateNewPage());
744     DataPageExtra dpExtra = new DataPageExtra();
745     dpMain.initParentPage(parentPageNumber, false);
746     dpMain._leaf = isLeaf;
747     dpMain._prevPageNumber = INVALID_INDEX_PAGE_NUMBER;
748     dpMain._nextPageNumber = INVALID_INDEX_PAGE_NUMBER;
749     dpMain._childTailPageNumber = INVALID_INDEX_PAGE_NUMBER;
750     dpExtra._entries = new ArrayList<Entry>();
751     dpExtra._entryPrefix = EMPTY_PREFIX;
752     dpMain.setExtra(dpExtra);
753 
754     // add to our page cache
755     _dataPages.put(dpMain._pageNumber, dpMain);
756 
757     // update owned pages cache
758     _indexData.addOwnedPage(dpMain._pageNumber);
759 
760     // needs to be written out
761     CacheDataPage cacheDataPage = new CacheDataPage(dpMain, dpExtra);
762     setModified(cacheDataPage);
763 
764     return cacheDataPage;
765   }
766 
767   /**
768    * Inserts the new page as a peer between the given original page and any
769    * previous peer page.
770    *
771    * @param newDataPage the new index page
772    * @param origDataPage the current index page
773    */
774   private void addToPeersBefore(CacheDataPage newDataPage,
775                                 CacheDataPage origDataPage)
776     throws IOException
777   {
778     DataPageMain origMain = origDataPage._main;
779     DataPageMain newMain = newDataPage._main;
780 
781     DataPageMain prevMain = origMain.getPrevPage();
782 
783     newMain._nextPageNumber = origMain._pageNumber;
784     newMain._prevPageNumber = origMain._prevPageNumber;
785     origMain._prevPageNumber = newMain._pageNumber;
786     
787     if(prevMain != null) {
788       setModified(new CacheDataPage(prevMain));
789       prevMain._nextPageNumber = newMain._pageNumber;
790     }
791   }
792 
793   /**
794    * Separates the given index page from any next peer page.
795    *
796    * @param cacheDataPage the index page to be separated
797    */
798   private void separateFromNextPeer(CacheDataPage cacheDataPage)
799     throws IOException
800   {
801     DataPageMain dpMain = cacheDataPage._main;
802 
803     setModified(cacheDataPage);
804 
805     DataPageMain nextMain = dpMain.getNextPage();
806     setModified(new CacheDataPage(nextMain));
807 
808     nextMain._prevPageNumber = INVALID_INDEX_PAGE_NUMBER;
809     dpMain._nextPageNumber = INVALID_INDEX_PAGE_NUMBER;
810   }
811   
812   /**
813    * Sets the parent info for the children of the given page to the given
814    * page.
815    *
816    * @param cacheDataPage the page whose children need to be updated
817    */
818   private void reparentChildren(CacheDataPage cacheDataPage)
819     throws IOException
820   {
821     DataPageMain dpMain = cacheDataPage._main;
822     DataPageExtra dpExtra = cacheDataPage._extra;
823 
824     // note, the "parent" page number is not actually persisted, so we do not
825     // need to mark any updated pages as modified.  for the same reason, we
826     // don't need to load the pages if not already loaded
827     for(Entry entry : dpExtra._entryView) {
828       Integer childPageNumber = entry.getSubPageNumber();
829       DataPageMain childMain = _dataPages.get(childPageNumber);
830       if(childMain != null) {
831         childMain.setParentPage(dpMain._pageNumber,
832                                 dpMain.isChildTailPageNumber(childPageNumber));
833       }
834     }
835   }
836 
837   /**
838    * Makes the tail entry of the given page a normal entry on that page, done
839    * when there is only one entry left on a page, and it is the tail.
840    *
841    * @param cacheDataPage the page whose tail must be updated
842    */
843   private void demoteTail(CacheDataPage cacheDataPage)
844     throws IOException
845   {
846     // there's only one entry on the page, and it's the tail.  make it a
847     // normal entry
848     DataPageMain dpMain = cacheDataPage._main;
849     DataPageExtra dpExtra = cacheDataPage._extra;
850 
851     setModified(cacheDataPage);
852     
853     DataPageMain tailMain = dpMain.getChildTailPage();
854     CacheDataPage tailDataPage = new CacheDataPage(tailMain);
855 
856     // move the tail entry to the last normal entry
857     updateParentTail(cacheDataPage, tailDataPage, UpdateType.REMOVE);
858     Entry tailEntry = dpExtra._entryView.demoteTail();
859     dpExtra._totalEntrySize += tailEntry.size();
860     dpExtra._entryPrefix = EMPTY_PREFIX;
861     
862     tailMain.setParentPage(dpMain._pageNumber, false);
863   }
864   
865   /**
866    * Makes the last normal entry of the given page the tail entry on that
867    * page, done when there are multiple entries on a page and no tail entry.
868    *
869    * @param cacheDataPage the page whose tail must be updated
870    */
871   private void promoteTail(CacheDataPage cacheDataPage)
872     throws IOException
873   {
874     // there's not tail currently on this page, make last entry a tail
875     DataPageMain dpMain = cacheDataPage._main;
876     DataPageExtra dpExtra = cacheDataPage._extra;
877 
878     setModified(cacheDataPage);
879     
880     DataPageMain lastMain = dpMain.getChildPage(dpExtra._entryView.getLast());
881     CacheDataPage lastDataPage = new CacheDataPage(lastMain);
882 
883     // move the "last" normal entry to the tail entry
884     updateParentTail(cacheDataPage, lastDataPage, UpdateType.ADD);
885     Entry lastEntry = dpExtra._entryView.promoteTail();
886     dpExtra._totalEntrySize -= lastEntry.size();
887     dpExtra._entryPrefix = EMPTY_PREFIX;
888 
889     lastMain.setParentPage(dpMain._pageNumber, true);
890   }
891   
892   /**
893    * Finds the index page on which the given entry does or should reside.
894    *
895    * @param e the entry to find
896    */
897   public CacheDataPage findCacheDataPage(Entry e)
898     throws IOException
899   {
900     DataPageMain curPage = _rootPage;
901     while(true) {
902 
903       if(curPage._leaf) {
904         // nowhere to go from here
905         return new CacheDataPage(curPage);
906       }
907       
908       DataPageExtra extra = curPage.getExtra();
909 
910       // need to descend
911       int idx = extra._entryView.find(e);
912       if(idx < 0) {
913         idx = missingIndexToInsertionPoint(idx);
914         if(idx == extra._entryView.size()) {
915           // just move to last child page
916           --idx;
917         }
918       }
919 
920       Entry nodeEntry = extra._entryView.get(idx);
921       curPage = curPage.getChildPage(nodeEntry);
922     }
923   }
924 
925   /**
926    * Marks the given index page as modified and saves it for writing, if
927    * necessary (if the page is already marked, does nothing).
928    *
929    * @param cacheDataPage the modified index page
930    */
931   private void setModified(CacheDataPage cacheDataPage)
932   {
933     if(!cacheDataPage._extra._modified) {
934       _modifiedPages.add(cacheDataPage);
935       cacheDataPage._extra._modified = true;
936     }
937   }
938 
939   /**
940    * Finds the valid entry prefix given the first/last entries on an index
941    * page.
942    *
943    * @param e1 the first entry on the page
944    * @param e2 the last entry on the page
945    *
946    * @return a valid entry prefix for the page
947    */
948   private static byte[] findCommonPrefix(Entry e1, Entry e2)
949   {
950     byte[] b1 = e1.getEntryBytes();
951     byte[] b2 = e2.getEntryBytes();
952     
953     int maxLen = b1.length;
954     byte[] prefix = b1;
955     if(b1.length > b2.length) {
956       maxLen = b2.length;
957       prefix = b2;
958     }
959     
960     int len = 0;
961     while((len < maxLen) && (b1[len] == b2[len])) {
962       ++len;
963     }
964     
965     if(len < prefix.length) {
966       if(len == 0) {
967         return EMPTY_PREFIX;
968       }
969       
970       // need new prefix
971       prefix = ByteUtil.copyOf(prefix, len);
972     }
973 
974     return prefix;
975   }
976 
977   /**
978    * Used by unit tests to validate the internal status of the index.
979    */
980   void validate() throws IOException {
981     // copy the values as the validation methods might trigger map updates
982     for(DataPageMain dpMain : new ArrayList<DataPageMain>(_dataPages.values())) {
983       DataPageExtra dpExtra = dpMain.getExtra();
984       validateEntries(dpExtra);
985       validateChildren(dpMain, dpExtra);
986       validatePeers(dpMain);
987     }
988   }
989 
990   /**
991    * Validates the entries for an index page
992    *
993    * @param dpExtra the entries to validate
994    */
995   private void validateEntries(DataPageExtra dpExtra) throws IOException {
996     int entrySize = 0;
997     Entry prevEntry = FIRST_ENTRY;
998     for(Entry e : dpExtra._entries) {
999       entrySize += e.size();
1000       if(prevEntry.compareTo(e) >= 0) {
1001         throw new IOException(withErrorContext(
1002                 "Unexpected order in index entries, " + prevEntry + " >= " + e));
1003       }
1004       prevEntry = e;
1005     }
1006     if(entrySize != dpExtra._totalEntrySize) {
1007       throw new IllegalStateException(withErrorContext(
1008               "Expected size " + entrySize +
1009               " but was " + dpExtra._totalEntrySize));
1010     }
1011   }
1012 
1013   /**
1014    * Validates the children for an index page
1015    *
1016    * @param dpMain the index page
1017    * @param dpExtra the child entries to validate
1018    */
1019   private void validateChildren(DataPageMain dpMain,
1020                                 DataPageExtra dpExtra) throws IOException {
1021     int childTailPageNumber = dpMain._childTailPageNumber;
1022     if(dpMain._leaf) {
1023       if(childTailPageNumber != INVALID_INDEX_PAGE_NUMBER) {
1024         throw new IllegalStateException(withErrorContext(
1025                 "Leaf page has tail " + dpMain));
1026       }
1027       return;
1028     }
1029     if((dpExtra._entryView.size() == 1) && dpMain.hasChildTail()) {
1030       throw new IllegalStateException(withErrorContext(
1031               "Single child is tail " + dpMain));
1032     }
1033     for(Entry e : dpExtra._entryView) {
1034       validateEntryForPage(dpMain, e);
1035       Integer subPageNumber = e.getSubPageNumber();
1036       DataPageMain childMain = _dataPages.get(subPageNumber);
1037       if(childMain != null) {
1038         if(childMain._parentPageNumber != null) {
1039           if(childMain._parentPageNumber != dpMain._pageNumber) {
1040             throw new IllegalStateException(withErrorContext(
1041                     "Child's parent is incorrect " + childMain));
1042           }
1043           boolean expectTail = (subPageNumber == childTailPageNumber);
1044           if(expectTail != childMain._tail) {
1045             throw new IllegalStateException(withErrorContext(
1046                     "Child tail status incorrect " + childMain));
1047           }
1048         }
1049         Entry lastEntry = childMain.getExtra()._entryView.getLast();
1050         if(e.compareTo(lastEntry) != 0) {
1051           throw new IllegalStateException(withErrorContext(
1052                   "Invalid entry " + e + " but child is " + lastEntry));
1053         }
1054       }
1055     }
1056   }
1057 
1058   /**
1059    * Validates the peer pages for an index page.
1060    *
1061    * @param dpMain the index page
1062    */
1063   private void validatePeers(DataPageMain dpMain) throws IOException {
1064     DataPageMain prevMain = _dataPages.get(dpMain._prevPageNumber);
1065     if(prevMain != null) {
1066       if(prevMain._nextPageNumber != dpMain._pageNumber) {
1067         throw new IllegalStateException(withErrorContext(
1068                 "Prev page " + prevMain + " does not ref " + dpMain));
1069       }
1070       validatePeerStatus(dpMain, prevMain);
1071     }
1072     
1073     DataPageMain nextMain = _dataPages.get(dpMain._nextPageNumber);
1074     if(nextMain != null) {
1075       if(nextMain._prevPageNumber != dpMain._pageNumber) {
1076         throw new IllegalStateException(withErrorContext(
1077                 "Next page " + nextMain + " does not ref " + dpMain));
1078       }
1079       validatePeerStatus(dpMain, nextMain);
1080     }
1081   }
1082 
1083   /**
1084    * Validates the given peer page against the given index page
1085    *
1086    * @param dpMain the index page
1087    * @param peerMain the peer index page
1088    */
1089   private void validatePeerStatus(DataPageMain dpMain, DataPageMain peerMain)
1090     throws IOException
1091   {
1092     if(dpMain._leaf != peerMain._leaf) {
1093       throw new IllegalStateException(withErrorContext(
1094               "Mismatched peer status " + dpMain._leaf + " " + peerMain._leaf));
1095     }
1096     if(!dpMain._leaf) {
1097       if((dpMain._parentPageNumber != null) &&
1098          (peerMain._parentPageNumber != null) &&
1099          ((int)dpMain._parentPageNumber != (int)peerMain._parentPageNumber)) {
1100         throw new IllegalStateException(withErrorContext(
1101                 "Mismatched node parents " + dpMain._parentPageNumber + " " +
1102                 peerMain._parentPageNumber));
1103       }
1104     }
1105   }
1106   
1107   /**
1108    * Collects all the cache pages in the cache.
1109    *
1110    * @param pages the List to update
1111    * @param dpMain the index page to collect
1112    */
1113   private List<Object> collectPages(List<Object> pages, DataPageMain dpMain) {
1114     try {
1115       CacheDataPage cacheDataPage = new CacheDataPage(dpMain);
1116       pages.add(cacheDataPage);
1117       if(!dpMain._leaf) {
1118         for(Entry e : cacheDataPage._extra._entryView) {
1119           DataPageMain childMain = dpMain.getChildPage(e);
1120           collectPages(pages, childMain);
1121         }
1122       }
1123     } catch(IOException e) {
1124       pages.add("DataPage[" + dpMain._pageNumber + "]: <" + e + ">");
1125     }
1126     return pages;
1127   }
1128 
1129   /**
1130    * Trims the size of the _dataPages cache appropriately (assuming caller has
1131    * already verified that the cache needs trimming).
1132    */
1133   private void purgeOldPages() {
1134     Iterator<DataPageMain> iter = _dataPages.values().iterator();
1135     while(iter.hasNext()) {
1136       DataPageMain dpMain = iter.next();
1137       // note, we never purge the root page
1138       if(dpMain != _rootPage) {
1139         iter.remove();
1140         if(_dataPages.size() <= MAX_CACHE_SIZE) {
1141           break;
1142         } 
1143       }
1144     }
1145   }
1146   
1147   @Override
1148   public String toString() {
1149     ToStringBuilder sb = CustomToStringStyle.builder(this);
1150     if(_rootPage == null) {
1151       sb.append("pages", "(uninitialized)");
1152     } else {    
1153       sb.append("pages", collectPages(new ArrayList<Object>(), _rootPage));
1154     }
1155     return sb.toString();
1156   }
1157 
1158   private String withErrorContext(String msg) {
1159     return _indexData.withErrorContext(msg);
1160   }
1161   
1162 
1163   /**
1164    * Keeps track of the main info for an index page.
1165    */
1166   private class DataPageMain
1167   {
1168     public final int _pageNumber;
1169     public Integer _prevPageNumber;
1170     public Integer _nextPageNumber;
1171     public Integer _childTailPageNumber;
1172     public Integer _parentPageNumber;
1173     public boolean _leaf;
1174     public boolean _tail;
1175     private Reference<DataPageExtra> _extra;
1176 
1177     private DataPageMain(int pageNumber) {
1178       _pageNumber = pageNumber;
1179     }
1180 
1181     public IndexPageCache getCache() {
1182       return IndexPageCache.this;
1183     }
1184     
1185     public boolean isRoot() {
1186       return(this == _rootPage);
1187     }
1188     
1189     public boolean isTail() throws IOException
1190     {
1191       resolveParent();
1192       return _tail;
1193     }
1194 
1195     public boolean hasChildTail() {
1196       return(_childTailPageNumber != INVALID_INDEX_PAGE_NUMBER);
1197     }
1198 
1199     public boolean isChildTailPageNumber(int pageNumber) {
1200       return(_childTailPageNumber == pageNumber);
1201     }
1202     
1203     public DataPageMain getParentPage() throws IOException
1204     {
1205       resolveParent();
1206       return IndexPageCache.this.getDataPage(_parentPageNumber);
1207     }
1208 
1209     public void initParentPage(Integer parentPageNumber, boolean isTail) {
1210       // only set if not already set
1211       if(_parentPageNumber == null) {
1212         setParentPage(parentPageNumber, isTail);
1213       }
1214     }
1215     
1216     public void setParentPage(Integer parentPageNumber, boolean isTail) {
1217       _parentPageNumber = parentPageNumber;
1218       _tail = isTail;
1219     }
1220 
1221     public DataPageMain getPrevPage() throws IOException
1222     {
1223       return IndexPageCache.this.getDataPage(_prevPageNumber);
1224     }
1225     
1226     public DataPageMain getNextPage() throws IOException
1227     {
1228       return IndexPageCache.this.getDataPage(_nextPageNumber);
1229     }
1230     
1231     public DataPageMain getChildPage(Entry e) throws IOException
1232     {
1233       Integer childPageNumber = e.getSubPageNumber();
1234       return getChildPage(childPageNumber,
1235                           isChildTailPageNumber(childPageNumber));
1236     }
1237     
1238     public DataPageMain getChildTailPage() throws IOException
1239     {
1240       return getChildPage(_childTailPageNumber, true);
1241     }
1242 
1243     /**
1244      * Returns a child page for the given page number, updating its parent
1245      * info if necessary.
1246      */
1247     private DataPageMain getChildPage(Integer childPageNumber, boolean isTail)
1248       throws IOException
1249     {
1250       DataPageMain child = getDataPage(childPageNumber);
1251       if(child != null) {
1252         // set the parent info for this child (if necessary)
1253         child.initParentPage(_pageNumber, isTail);
1254       }
1255       return child;
1256     }
1257     
1258     public DataPageExtra getExtra() throws IOException
1259     {
1260       DataPageExtra extra = _extra.get();
1261       if(extra == null) {
1262         extra = readDataPage(_pageNumber)._extra;
1263         setExtra(extra);
1264       }
1265       
1266       return extra;
1267     }
1268     
1269     public void setExtra(DataPageExtra extra) throws IOException
1270     {
1271       extra.setEntryView(this);
1272       _extra = new SoftReference<DataPageExtra>(extra);
1273     }
1274 
1275     private void resolveParent() throws IOException {
1276       if(_parentPageNumber == null) {
1277         // the act of searching for the last entry should resolve any parent
1278         // pages along the path
1279         findCacheDataPage(getExtra()._entryView.getLast());
1280         if(_parentPageNumber == null) {
1281           throw new IllegalStateException(withErrorContext(
1282                   "Parent was not resolved"));
1283         }
1284       }
1285     }
1286 
1287     @Override
1288     public String toString() {
1289       return (_leaf ? "Leaf" : "Node") + "DPMain[" + _pageNumber +
1290         "] " + _prevPageNumber + ", " + _nextPageNumber + ", (" +
1291         _childTailPageNumber + ")";
1292     }
1293   }
1294 
1295   /**
1296    * Keeps track of the extra info for an index page.  This info (if
1297    * unmodified) may be re-read from disk as necessary.
1298    */
1299   private static class DataPageExtra
1300   {
1301     /** sorted collection of index entries.  this is kept in a list instead of
1302         a SortedSet because the SortedSet has lame traversal utilities */
1303     public List<Entry> _entries;
1304     public EntryListView _entryView;
1305     public byte[] _entryPrefix;
1306     public int _totalEntrySize;
1307     public boolean _modified;
1308 
1309     private DataPageExtra()
1310     {
1311     }
1312 
1313     public void setEntryView(DataPageMain main) throws IOException {
1314       _entryView = new EntryListView(main, this);
1315     }
1316     
1317     public void updateEntryPrefix() {
1318       if(_entryPrefix.length == 0) {
1319         // prefix is only related to *real* entries, tail not included
1320         _entryPrefix = findCommonPrefix(_entries.get(0),
1321                                         _entries.get(_entries.size() - 1));
1322       }
1323     }
1324     
1325     @Override
1326     public String toString() {
1327       return CustomToStringStyle.builder("DPExtra")
1328         .append(null, _entryView)
1329         .toString();
1330     }
1331   }
1332 
1333   /**
1334    * IndexPageCache implementation of an Index {@link DataPage}.
1335    */
1336   private static final class CacheDataPage extends DataPage
1337   {
1338     public final DataPageMain _main;
1339     public final DataPageExtra _extra;
1340 
1341     private CacheDataPage(DataPageMain dataPage) throws IOException {
1342       this(dataPage, dataPage.getExtra());
1343     }
1344     
1345     private CacheDataPage(DataPageMain dataPage, DataPageExtra extra) {
1346       _main = dataPage;
1347       _extra = extra;
1348     }
1349 
1350     @Override
1351     public int getPageNumber() {
1352       return _main._pageNumber;
1353     }
1354     
1355     @Override
1356     public boolean isLeaf() {
1357       return _main._leaf;
1358     }
1359 
1360     @Override
1361     public void setLeaf(boolean isLeaf) {
1362       _main._leaf = isLeaf;
1363     }
1364 
1365 
1366     @Override
1367     public int getPrevPageNumber() {
1368       return _main._prevPageNumber;
1369     }
1370 
1371     @Override
1372     public void setPrevPageNumber(int pageNumber) {
1373       _main._prevPageNumber = pageNumber;
1374     }
1375 
1376     @Override
1377     public int getNextPageNumber() {
1378       return _main._nextPageNumber;
1379     }
1380 
1381     @Override
1382     public void setNextPageNumber(int pageNumber) {
1383       _main._nextPageNumber = pageNumber;
1384     }
1385 
1386     @Override
1387     public int getChildTailPageNumber() {
1388       return _main._childTailPageNumber;
1389     }
1390 
1391     @Override
1392     public void setChildTailPageNumber(int pageNumber) {
1393       _main._childTailPageNumber = pageNumber;
1394     }
1395 
1396     
1397     @Override
1398     public int getTotalEntrySize() {
1399       return _extra._totalEntrySize;
1400     }
1401 
1402     @Override
1403     public void setTotalEntrySize(int totalSize) {
1404       _extra._totalEntrySize = totalSize;
1405     }
1406 
1407     @Override
1408     public byte[] getEntryPrefix() {
1409       return _extra._entryPrefix;
1410     }
1411 
1412     @Override
1413     public void setEntryPrefix(byte[] entryPrefix) {
1414       _extra._entryPrefix = entryPrefix;
1415     }
1416 
1417 
1418     @Override
1419     public List<Entry> getEntries() {
1420       return _extra._entries;
1421     }
1422 
1423     @Override
1424     public void setEntries(List<Entry> entries) {
1425       _extra._entries = entries;
1426     }
1427 
1428     @Override
1429     public void addEntry(int idx, Entry entry) throws IOException {
1430       _main.getCache().addEntry(this, idx, entry);
1431     }
1432     
1433     @Override
1434     public Entry removeEntry(int idx) throws IOException {
1435       return _main.getCache().removeEntry(this, idx);
1436     }
1437     
1438   }
1439 
1440   /**
1441    * A view of an index page's entries which combines the normal entries and
1442    * tail entry into one collection.
1443    */
1444   private static class EntryListView extends AbstractList<Entry>
1445     implements RandomAccess
1446   {
1447     private final DataPageExtra _extra;
1448     private Entry _childTailEntry;
1449 
1450     private EntryListView(DataPageMain main, DataPageExtra extra)
1451       throws IOException
1452     {
1453       if(main.hasChildTail()) {
1454         _childTailEntry = main.getChildTailPage().getExtra()._entryView
1455           .getLast().asNodeEntry(main._childTailPageNumber);
1456       }
1457       _extra = extra;
1458     }
1459 
1460     private List<Entry> getEntries() {
1461       return _extra._entries;
1462     }
1463     
1464     @Override
1465     public int size() {
1466       int size = getEntries().size();
1467       if(hasChildTail()) {
1468         ++size;
1469       }
1470       return size;
1471     }
1472 
1473     @Override
1474     public Entry get(int idx) {
1475       return (isCurrentChildTailIndex(idx) ?
1476               _childTailEntry :
1477               getEntries().get(idx));
1478     }
1479 
1480     @Override
1481     public Entry set(int idx, Entry newEntry) {
1482       return (isCurrentChildTailIndex(idx) ?
1483               setChildTailEntry(newEntry) :
1484               getEntries().set(idx, newEntry));
1485     }
1486     
1487     @Override
1488     public void add(int idx, Entry newEntry) {
1489       // note, we will never add to the "tail" entry, that will always be
1490       // handled through promoteTail
1491       getEntries().add(idx, newEntry);
1492     }
1493     
1494     @Override
1495     public Entry remove(int idx) {
1496       return (isCurrentChildTailIndex(idx) ?
1497               setChildTailEntry(null) :
1498               getEntries().remove(idx));
1499     }
1500     
1501     public Entry setChildTailEntry(Entry newEntry) {
1502       Entry old = _childTailEntry;
1503       _childTailEntry = newEntry;
1504       return old;
1505     }
1506     
1507     private boolean hasChildTail() {
1508       return(_childTailEntry != null);
1509     }
1510     
1511     private boolean isCurrentChildTailIndex(int idx) {
1512       return(idx == getEntries().size());
1513     }
1514 
1515     public Entry getLast() {
1516       return(hasChildTail() ? _childTailEntry :
1517              (!getEntries().isEmpty() ?
1518               getEntries().get(getEntries().size() - 1) : null));
1519     }
1520 
1521     public Entry demoteTail() {
1522       Entry tail = _childTailEntry;
1523       _childTailEntry = null;
1524       getEntries().add(tail);
1525       return tail;
1526     }
1527     
1528     public Entry promoteTail() {
1529       Entry last = getEntries().remove(getEntries().size() - 1);
1530       _childTailEntry = last;
1531       return last;
1532     }
1533     
1534     public int find(Entry e) {
1535       return Collections.binarySearch(this, e);
1536     }
1537 
1538   }
1539 
1540 }