Coverage Report

 /*
 Copyright (c) 2008 Health Market Science, Inc.
 
 This library is free software; you can redistribute it and/or
 modify it under the terms of the GNU Lesser General Public
 License as published by the Free Software Foundation; either
 version 2.1 of the License, or (at your option) any later version.
 
 This library is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 Lesser General Public License for more details.
 
 You should have received a copy of the GNU Lesser General Public
 License along with this library; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307
 USA
 
 You can contact Health Market Science at info@healthmarketscience.com
 or at the following address:
 
 Health Market Science
 2700 Horizon Drive
 Suite 200
 King of Prussia, PA 19406
 */
 
 package com.healthmarketscience.jackcess;
 
 import java.io.IOException;
 import java.lang.ref.Reference;
 import java.lang.ref.SoftReference;
 import java.util.AbstractList;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.RandomAccess;
 
 
 import static com.healthmarketscience.jackcess.Index.*;
 
 /**
  * Manager of the index pages for a BigIndex.
  * @author James Ahlborn
  */
 public class IndexPageCache
 {
   private enum UpdateType {
     ADD, REMOVE, REPLACE;
   }
 
   /** the index whose pages this cache is managing */
   private final BigIndex _index;
   /** the root page for the index */
   private DataPageMain _rootPage;
   /** the currently loaded pages for this index, pageNumber -> page */
   private final Map<Integer, DataPageMain> _dataPages =
     new HashMap<Integer, DataPageMain>();
   /** the currently modified index pages */
   private final List<CacheDataPage> _modifiedPages =
     new ArrayList<CacheDataPage>();
   
   public IndexPageCache(BigIndex index) {
     _index = index;
   }
 
   public BigIndex getIndex() {
     return _index;
   }
   
   public PageChannel getPageChannel() {
     return getIndex().getPageChannel();
   }
 
   /**
    * Sets the root page for this index, must be called before normal usage.
    *
    * @param pageNumber the root page number
    */
   public void setRootPageNumber(int pageNumber) throws IOException {
     _rootPage = getDataPage(pageNumber);
     // root page has no parent
     _rootPage.initParentPage(INVALID_INDEX_PAGE_NUMBER, false);
   }
   
   /**
    * Writes any outstanding changes for this index to the file.
    */
   public void write()
     throws IOException
   {
     // first discard any empty pages
     handleEmptyPages();
     // next, handle any necessary page splitting
     preparePagesForWriting();
     // finally, write all the modified pages (which are not being deleted)
     writeDataPages();
   }
 
   /**
    * Handles any modified pages which are empty as the first pass during a
    * {@link #write} call.  All empty pages are removed from the _modifiedPages
    * collection by this method.
    */
   private void handleEmptyPages() throws IOException
   {
     for(Iterator<CacheDataPage> iter = _modifiedPages.iterator();
         iter.hasNext(); ) {
       CacheDataPage cacheDataPage = iter.next();
       if(cacheDataPage._extra._entryView.isEmpty()) {
         if(!cacheDataPage._main.isRoot()) {
           deleteDataPage(cacheDataPage);
         } else {
           writeDataPage(cacheDataPage);
         }
         iter.remove();
       }
     }
   }
   
   /**
    * Prepares any non-empty modified pages for writing as the second pass
    * during a {@link #write} call.  Updates entry prefixes, promotes/demotes
    * tail pages, and splits pages as needed.
    */
   private void preparePagesForWriting() throws IOException
   {
     boolean splitPages = false;
     int maxPageEntrySize = getIndex().getMaxPageEntrySize();
 
     // we need to continue looping through all the pages until we do not split
     // any pages (because a split may cascade up the tree)
     do {
       splitPages = false;
 
       // we might be adding to this list while iterating, so we can't use an
       // iterator
       for(int i = 0; i < _modifiedPages.size(); ++i) {
 
         CacheDataPage cacheDataPage = _modifiedPages.get(i);
 
         if(!cacheDataPage.isLeaf()) {
           // see if we need to update any child tail status
           DataPageMain dpMain = cacheDataPage._main;
           int size = cacheDataPage._extra._entryView.size();
           if(dpMain.hasChildTail()) {
             if(size == 1) {
               demoteTail(cacheDataPage);
             } 
           } else {
             if(size > 1) {
               promoteTail(cacheDataPage);
             }
           }
         }
         
         // look for pages with more entries than can fit on a page
         if(cacheDataPage.getTotalEntrySize() > maxPageEntrySize) {
 
           // make sure the prefix is up-to-date (this may have gotten
           // discarded by one of the update entry methods)
           cacheDataPage._extra.updateEntryPrefix();
 
           // now, see if the page will fit when compressed
           if(cacheDataPage.getCompressedEntrySize() > maxPageEntrySize) {
             // need to split this page
             splitPages = true;
             splitDataPage(cacheDataPage);
           }
         }
       }
       
     } while(splitPages);
   }
 
   /**
    * Writes any non-empty modified pages as the last pass during a
    * {@link #write} call.  Clears the _modifiedPages collection when finised.
    */
   private void writeDataPages() throws IOException
   {
     for(CacheDataPage cacheDataPage : _modifiedPages) {
       if(cacheDataPage._extra._entryView.isEmpty()) {
         throw new IllegalStateException("Unexpected empty page " +
                                         cacheDataPage);
       }
       writeDataPage(cacheDataPage);
     }
     _modifiedPages.clear();
   }
 
   /**
    * Returns a CacheDataPage for the given page number, may be {@code null} if
    * the given page number is invalid.  Loads the given page if necessary.
    */
   public CacheDataPage getCacheDataPage(Integer pageNumber)
     throws IOException
   {
     DataPageMain main = getDataPage(pageNumber);
     return((main != null) ? new CacheDataPage(main) : null);
   }
   
   /**
    * Returns a DataPageMain for the given page number, may be {@code null} if
    * the given page number is invalid.  Loads the given page if necessary.
    */
   private DataPageMain getDataPage(Integer pageNumber)
     throws IOException
   {
     DataPageMain dataPage = _dataPages.get(pageNumber);
     if((dataPage == null) && (pageNumber > INVALID_INDEX_PAGE_NUMBER)) {
       dataPage = readDataPage(pageNumber)._main;
       _dataPages.put(pageNumber, dataPage);
     }
     return dataPage;
   }
 
   /**
    * Writes the given index page to the file.
    */
   private void writeDataPage(CacheDataPage cacheDataPage)
     throws IOException
   {
     getIndex().writeDataPage(cacheDataPage);
 
     // lastly, mark the page as no longer modified
     cacheDataPage._extra._modified = false;    
   }
   
   /**
    * Deletes the given index page from the file (clears the page).
    */
   private void deleteDataPage(CacheDataPage cacheDataPage)
     throws IOException
   {
     // free this database page
     getPageChannel().deallocatePage(cacheDataPage._main._pageNumber);
 
     // discard from our cache
     _dataPages.remove(cacheDataPage._main._pageNumber);
     
     // lastly, mark the page as no longer modified
     cacheDataPage._extra._modified = false;    
   }
   
   /**
    * Reads the given index page from the file.
    */
   private CacheDataPage readDataPage(Integer pageNumber)
     throws IOException
   {
     DataPageMain dataPage = new DataPageMain(pageNumber);
     DataPageExtra extra = new DataPageExtra();
     CacheDataPage cacheDataPage = new CacheDataPage(dataPage, extra);
     getIndex().readDataPage(cacheDataPage);
 
     // associate the extra info with the main data page
     dataPage.setExtra(extra);
     
     return cacheDataPage;
   }  
 
   /**
    * Removes the entry with the given index from the given page.
    *
    * @param cacheDataPage the page from which to remove the entry
    * @param entryIdx the index of the entry to remove
    */
   private void removeEntry(CacheDataPage cacheDataPage, int entryIdx)
     throws IOException
   {
     updateEntry(cacheDataPage, entryIdx, null, UpdateType.REMOVE);
   }
 
   /**
    * Adds the entry to the given page at the given index.
    *
    * @param cacheDataPage the page to which to add the entry
    * @param entryIdx the index at which to add the entry
    * @param newEntry the entry to add
    */
   private void addEntry(CacheDataPage cacheDataPage,
                         int entryIdx,
                         Entry newEntry)
     throws IOException
   {
     updateEntry(cacheDataPage, entryIdx, newEntry, UpdateType.ADD);
   }
   
   /**
    * Updates the entries on the given page according to the given updateType.
    *
    * @param cacheDataPage the page to update
    * @param entryIdx the index at which to add/remove/replace the entry
    * @param newEntry the entry to add/replace
    * @param upType the type of update to make
    */
   private void updateEntry(CacheDataPage cacheDataPage,
                            int entryIdx,
                            Entry newEntry,
                            UpdateType upType)
     throws IOException
   {
     DataPageMain dpMain = cacheDataPage._main;
     DataPageExtra dpExtra = cacheDataPage._extra;
 
     if(newEntry != null) {
       validateEntryForPage(dpMain, newEntry);
     }
 
     // note, it's slightly ucky, but we need to load the parent page before we
     // start mucking with our entries because our parent may use our entries.
     CacheDataPage parentDataPage = (!dpMain.isRoot() ?
                                     new CacheDataPage(dpMain.getParentPage()) :
                                     null);
     
     Entry oldLastEntry = dpExtra._entryView.getLast();
     Entry oldEntry = null;
     int entrySizeDiff = 0;
 
     switch(upType) {
     case ADD:
       dpExtra._entryView.add(entryIdx, newEntry);
       entrySizeDiff += newEntry.size();
       break;
 
     case REPLACE:
       oldEntry = dpExtra._entryView.set(entryIdx, newEntry);
       entrySizeDiff += newEntry.size() - oldEntry.size();
       break;
 
     case REMOVE: {
       oldEntry = dpExtra._entryView.remove(entryIdx);
       entrySizeDiff -= oldEntry.size();
       break;
     }
     default:
       throw new RuntimeException("unknown update type " + upType);
     }
 
     boolean updateLast = (oldLastEntry != dpExtra._entryView.getLast());
     
     // child tail entry updates do not modify the page
     if(!updateLast || !dpMain.hasChildTail()) {
       dpExtra._totalEntrySize += entrySizeDiff;
       setModified(cacheDataPage);
 
       // for now, just clear the prefix, we'll fix it later
       dpExtra._entryPrefix = EMPTY_PREFIX;
     }
 
     if(dpExtra._entryView.isEmpty()) {
       // this page is dead
       removeDataPage(parentDataPage, cacheDataPage, oldLastEntry);
       return;
     }
 
     // determine if we need to update our parent page 
     if(!updateLast || dpMain.isRoot()) {
       // no parent
       return;
     }
 
     // the update to the last entry needs to be propagated to our parent
     replaceParentEntry(parentDataPage, cacheDataPage, oldLastEntry);
   }
 
   /**
    * Removes an index page which has become empty.  If this page is the root
    * page, just clears it.
    *
    * @param parentDataPage the parent of the removed page
    * @param cacheDataPage the page to remove
    * @param oldLastEntry the last entry for this page (before it was removed)
    */
   private void removeDataPage(CacheDataPage parentDataPage,
                               CacheDataPage cacheDataPage,
                               Entry oldLastEntry)
     throws IOException
   {
     DataPageMain dpMain = cacheDataPage._main;
     DataPageExtra dpExtra = cacheDataPage._extra;
 
     if(dpMain.hasChildTail()) {
       throw new IllegalStateException("Still has child tail?");
     }
 
     if(dpExtra._totalEntrySize != 0) {
       throw new IllegalStateException("Empty page but size is not 0? " +
                                       dpExtra._totalEntrySize + ", " +
                                       cacheDataPage);
     }
     
     if(dpMain.isRoot()) {
       // clear out this page (we don't actually remove it)
       dpExtra._entryPrefix = EMPTY_PREFIX;
       // when the root page becomes empty, it becomes a leaf page again
       dpMain._leaf = true;
       return;
     }
 
     // remove this page from its parent page
     updateParentEntry(parentDataPage, cacheDataPage, oldLastEntry, null,
                       UpdateType.REMOVE);
 
     // remove this page from any next/prev pages
     removeFromPeers(cacheDataPage);
   }
 
   /**
    * Removes a now empty index page from its next and previous peers.
    *
    * @param cacheDataPage the page to remove
    */
   private void removeFromPeers(CacheDataPage cacheDataPage)
     throws IOException
   {
     DataPageMain dpMain = cacheDataPage._main;
 
     Integer prevPageNumber = dpMain._prevPageNumber;
     Integer nextPageNumber = dpMain._nextPageNumber;
     
     DataPageMain prevMain = dpMain.getPrevPage();
     if(prevMain != null) {
       setModified(new CacheDataPage(prevMain));
       prevMain._nextPageNumber = nextPageNumber;
     }
 
     DataPageMain nextMain = dpMain.getNextPage();
     if(nextMain != null) {
       setModified(new CacheDataPage(nextMain));
       nextMain._prevPageNumber = prevPageNumber;
     }
   }
 
   /**
    * Adds an entry for the given child page to the given parent page.
    *
    * @param parentDataPage the parent page to which to add the entry
    * @param childDataPage the child from which to get the entry to add
    */
   private void addParentEntry(CacheDataPage parentDataPage,
                               CacheDataPage childDataPage)
     throws IOException
   {
     DataPageExtra childExtra = childDataPage._extra;
     updateParentEntry(parentDataPage, childDataPage, null,
                       childExtra._entryView.getLast(), UpdateType.ADD);
   }
   
   /**
    * Replaces the entry for the given child page in the given parent page.
    *
    * @param parentDataPage the parent page in which to replace the entry
    * @param childDataPage the child for which the entry is being replaced
    * @param oldEntry the old child entry for the child page
    */
   private void replaceParentEntry(CacheDataPage parentDataPage,
                                   CacheDataPage childDataPage,
                                   Entry oldEntry)
     throws IOException
   {
     DataPageExtra childExtra = childDataPage._extra;
     updateParentEntry(parentDataPage, childDataPage, oldEntry,
                       childExtra._entryView.getLast(), UpdateType.REPLACE);
   }
   
   /**
    * Updates the entry for the given child page in the given parent page
    * according to the given updateType.
    *
    * @param parentDataPage the parent page in which to update the entry
    * @param childDataPage the child for which the entry is being updated
    * @param oldEntry the old child entry to remove/replace
    * @param newEntry the new child entry to replace/add
    * @param upType the type of update to make
    */
   private void updateParentEntry(CacheDataPage parentDataPage,
                                  CacheDataPage childDataPage,
                                  Entry oldEntry, Entry newEntry,
                                  UpdateType upType)
     throws IOException
   {
     DataPageMain childMain = childDataPage._main;
     DataPageExtra parentExtra = parentDataPage._extra;
 
     if(childMain.isTail() && (upType != UpdateType.REMOVE)) {
       // for add or replace, update the child tail info before updating the
       // parent entries
       updateParentTail(parentDataPage, childDataPage, upType);
     }
 
     if(oldEntry != null) {
       oldEntry = oldEntry.asNodeEntry(childMain._pageNumber);
     }
     if(newEntry != null) {
       newEntry = newEntry.asNodeEntry(childMain._pageNumber);
     }
 
     boolean expectFound = true;
     int idx = 0;
     
     switch(upType) {
     case ADD:
       expectFound = false;
       idx = parentExtra._entryView.find(newEntry);
       break;
 
     case REPLACE:
     case REMOVE:
       idx = parentExtra._entryView.find(oldEntry);
       break;
     
     default:
       throw new RuntimeException("unknown update type " + upType);
     }
         
     if(idx < 0) {
       if(expectFound) {
         throw new IllegalStateException(
             "Could not find child entry in parent; childEntry " + oldEntry +
             "; parent " + parentDataPage);
       }
       idx = missingIndexToInsertionPoint(idx);
     } else {
       if(!expectFound) {
         throw new IllegalStateException(
             "Unexpectedly found child entry in parent; childEntry " +
             newEntry + "; parent " + parentDataPage);
       }
     }
     updateEntry(parentDataPage, idx, newEntry, upType);
 
     if(childMain.isTail() && (upType == UpdateType.REMOVE)) {
       // for remove, update the child tail info after updating the parent
       // entries
       updateParentTail(parentDataPage, childDataPage, upType);
     }
   }
 
   /**
    * Updates the child tail info in the given parent page according to the
    * given updateType.
    *
    * @param parentDataPage the parent page in which to update the child tail
    * @param childDataPage the child to add/replace
    * @param upType the type of update to make
    */
   private void updateParentTail(CacheDataPage parentDataPage,
                                 CacheDataPage childDataPage,
                                 UpdateType upType)
     throws IOException
   {
     DataPageMain parentMain = parentDataPage._main;
 
     int newChildTailPageNumber =
       ((upType == UpdateType.REMOVE) ?
        INVALID_INDEX_PAGE_NUMBER :
        childDataPage._main._pageNumber);
     if(!parentMain.isChildTailPageNumber(newChildTailPageNumber)) {
       setModified(parentDataPage);
       parentMain._childTailPageNumber = newChildTailPageNumber;
     }
   }
   
   /**
    * Verifies that the given entry type (node/leaf) is valid for the given
    * page (node/leaf).
    *
    * @param dpMain the page to which the entry will be added
    * @param entry the entry being added
    * @throws IllegalStateException if the entry type does not match the page
    *         type
    */
   private void validateEntryForPage(DataPageMain dpMain, Entry entry) {
     if(dpMain._leaf != entry.isLeafEntry()) {
       throw new IllegalStateException(
           "Trying to update page with wrong entry type; pageLeaf " +
           dpMain._leaf + ", entryLeaf " + entry.isLeafEntry());
     }
   }
 
   /**
    * Splits an index page which has too many entries on it.
    *
    * @param origDataPage the page to split
    */
   private void splitDataPage(CacheDataPage origDataPage)
     throws IOException
   {
     DataPageMain origMain = origDataPage._main;
     DataPageExtra origExtra = origDataPage._extra;
 
     setModified(origDataPage);
     
     int numEntries = origExtra._entries.size();
     if(numEntries < 2) {
       throw new IllegalStateException(
           "Cannot split page with less than 2 entries " + origDataPage);
     }
     
     if(origMain.isRoot()) {
       // we can't split the root page directly, so we need to put another page
       // between the root page and its sub-pages, and then split that page.
       CacheDataPage newDataPage = nestRootDataPage(origDataPage);
 
       // now, split this new page instead
       origDataPage = newDataPage;
       origMain = newDataPage._main;
       origExtra = newDataPage._extra;
     }
 
     // note, it's slightly ucky, but we need to load the parent page before we
     // start mucking with our entries because our parent may use our entries.
     DataPageMain parentMain = origMain.getParentPage();
     CacheDataPage parentDataPage = new CacheDataPage(parentMain);
     
     // note, there are many, many ways this could be improved/tweaked.  for
     // now, we just want it to be functional...
     // so, we will naively move half the entries from one page to a new page.
 
     CacheDataPage newDataPage = allocateNewCacheDataPage(
         parentMain._pageNumber, origMain._leaf);
     DataPageMain newMain = newDataPage._main;
     DataPageExtra newExtra = newDataPage._extra;
     
     List<Entry> headEntries =
       origExtra._entries.subList(0, ((numEntries + 1) / 2));
 
     // move first half of the entries from old page to new page (so we do not
     // need to muck with any tail entries)
     for(Entry headEntry : headEntries) {
       newExtra._totalEntrySize += headEntry.size();


1		/*
2		Copyright (c) 2008 Health Market Science, Inc.
3
4		This library is free software; you can redistribute it and/or
5		modify it under the terms of the GNU Lesser General Public
6		License as published by the Free Software Foundation; either
7		version 2.1 of the License, or (at your option) any later version.
8
9		This library is distributed in the hope that it will be useful,
10		but WITHOUT ANY WARRANTY; without even the implied warranty of
11		MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12		Lesser General Public License for more details.
13
14		You should have received a copy of the GNU Lesser General Public
15		License along with this library; if not, write to the Free Software
16		Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
17		USA
18
19		You can contact Health Market Science at info@healthmarketscience.com
20		or at the following address:
21
22		Health Market Science
23		2700 Horizon Drive
24		Suite 200
25		King of Prussia, PA 19406
26		*/
27
28		package com.healthmarketscience.jackcess;
29
30		import java.io.IOException;
31		import java.lang.ref.Reference;
32		import java.lang.ref.SoftReference;
33		import java.util.AbstractList;
34		import java.util.ArrayList;
35		import java.util.Collections;
36		import java.util.HashMap;
37		import java.util.Iterator;
38		import java.util.List;
39		import java.util.Map;
40		import java.util.RandomAccess;
41
42
43		import static com.healthmarketscience.jackcess.Index.*;
44
45		/**
46		* Manager of the index pages for a BigIndex.
47		* @author James Ahlborn
48		*/
49	78992	public class IndexPageCache
50		{
51	5	private enum UpdateType {
52	1	ADD, REMOVE, REPLACE;
53		}
54
55		/** the index whose pages this cache is managing */
56		private final BigIndex _index;
57		/** the root page for the index */
58		private DataPageMain _rootPage;
59		/** the currently loaded pages for this index, pageNumber -> page */
60	13	private final Map<Integer, DataPageMain> _dataPages =
61		new HashMap<Integer, DataPageMain>();
62		/** the currently modified index pages */
63	13	private final List<CacheDataPage> _modifiedPages =
64		new ArrayList<CacheDataPage>();
65
66	13	public IndexPageCache(BigIndex index) {
67	13	_index = index;
68	13	}
69
70		public BigIndex getIndex() {
71	10968	return _index;
72		}
73
74		public PageChannel getPageChannel() {
75	462	return getIndex().getPageChannel();
76		}
77
78		/**
79		* Sets the root page for this index, must be called before normal usage.
80		*
81		* @param pageNumber the root page number
82		*/
83		public void setRootPageNumber(int pageNumber) throws IOException {
84	4	_rootPage = getDataPage(pageNumber);
85		// root page has no parent
86	4	_rootPage.initParentPage(INVALID_INDEX_PAGE_NUMBER, false);
87	4	}
88
89		/**
90		* Writes any outstanding changes for this index to the file.
91		*/
92		public void write()
93		throws IOException
94		{
95		// first discard any empty pages
96	4002	handleEmptyPages();
97		// next, handle any necessary page splitting
98	4002	preparePagesForWriting();
99		// finally, write all the modified pages (which are not being deleted)
100	4002	writeDataPages();
101	4002	}
102
103		/**
104		* Handles any modified pages which are empty as the first pass during a
105		* {@link #write} call. All empty pages are removed from the _modifiedPages
106		* collection by this method.
107		*/
108		private void handleEmptyPages() throws IOException
109		{
110	4002	for(Iterator<CacheDataPage> iter = _modifiedPages.iterator();
111	9842	iter.hasNext(); ) {
112	5840	CacheDataPage cacheDataPage = iter.next();
113	5840	if(cacheDataPage._extra._entryView.isEmpty()) {
114	233	if(!cacheDataPage._main.isRoot()) {
115	231	deleteDataPage(cacheDataPage);
116		} else {
117	2	writeDataPage(cacheDataPage);
118		}
119	233	iter.remove();
120		}
121	5840	}
122	4002	}
123
124		/**
125		* Prepares any non-empty modified pages for writing as the second pass
126		* during a {@link #write} call. Updates entry prefixes, promotes/demotes
127		* tail pages, and splits pages as needed.
128		*/
129		private void preparePagesForWriting() throws IOException
130		{
131	4002	boolean splitPages = false;
132	4002	int maxPageEntrySize = getIndex().getMaxPageEntrySize();
133
134		// we need to continue looping through all the pages until we do not split
135		// any pages (because a split may cascade up the tree)
136		do {
137	4201	splitPages = false;
138
139		// we might be adding to this list while iterating, so we can't use an
140		// iterator
141	11417	for(int i = 0; i < _modifiedPages.size(); ++i) {
142
143	7216	CacheDataPage cacheDataPage = _modifiedPages.get(i);
144
145	7216	if(!cacheDataPage.isLeaf()) {
146		// see if we need to update any child tail status
147	2039	DataPageMain dpMain = cacheDataPage._main;
148	2039	int size = cacheDataPage._extra._entryView.size();
149	2039	if(dpMain.hasChildTail()) {
150	515	if(size == 1) {
151	1	demoteTail(cacheDataPage);
152		}
153		} else {
154	1524	if(size > 1) {
155	205	promoteTail(cacheDataPage);
156		}
157		}
158		}
159
160		// look for pages with more entries than can fit on a page
161	7216	if(cacheDataPage.getTotalEntrySize() > maxPageEntrySize) {
162
163		// make sure the prefix is up-to-date (this may have gotten
164		// discarded by one of the update entry methods)
165	231	cacheDataPage._extra.updateEntryPrefix();
166
167		// now, see if the page will fit when compressed
168	231	if(cacheDataPage.getCompressedEntrySize() > maxPageEntrySize) {
169		// need to split this page
170	227	splitPages = true;
171	227	splitDataPage(cacheDataPage);
172		}
173		}
174		}
175
176	4201	} while(splitPages);
177	4002	}
178
179		/**
180		* Writes any non-empty modified pages as the last pass during a
181		* {@link #write} call. Clears the _modifiedPages collection when finised.
182		*/
183		private void writeDataPages() throws IOException
184		{
185	4002	for(CacheDataPage cacheDataPage : _modifiedPages) {
186	6270	if(cacheDataPage._extra._entryView.isEmpty()) {
187	0	throw new IllegalStateException("Unexpected empty page " +
188		cacheDataPage);
189		}
190	6270	writeDataPage(cacheDataPage);
191		}
192	4002	_modifiedPages.clear();
193	4002	}
194
195		/**
196		* Returns a CacheDataPage for the given page number, may be {@code null} if
197		* the given page number is invalid. Loads the given page if necessary.
198		*/
199		public CacheDataPage getCacheDataPage(Integer pageNumber)
200		throws IOException
201		{
202	206558	DataPageMain main = getDataPage(pageNumber);
203	206558	return((main != null) ? new CacheDataPage(main) : null);
204		}
205
206		/**
207		* Returns a DataPageMain for the given page number, may be {@code null} if
208		* the given page number is invalid. Loads the given page if necessary.
209		*/
210		private DataPageMain getDataPage(Integer pageNumber)
211		throws IOException
212		{
213	262405	DataPageMain dataPage = _dataPages.get(pageNumber);
214	262405	if((dataPage == null) && (pageNumber > INVALID_INDEX_PAGE_NUMBER)) {
215	232	dataPage = readDataPage(pageNumber)._main;
216	232	_dataPages.put(pageNumber, dataPage);
217		}
218	262405	return dataPage;
219		}
220
221		/**
222		* Writes the given index page to the file.
223		*/
224		private void writeDataPage(CacheDataPage cacheDataPage)
225		throws IOException
226		{
227	6272	getIndex().writeDataPage(cacheDataPage);
228
229		// lastly, mark the page as no longer modified
230	6272	cacheDataPage._extra._modified = false;
231	6272	}
232
233		/**
234		* Deletes the given index page from the file (clears the page).
235		*/
236		private void deleteDataPage(CacheDataPage cacheDataPage)
237		throws IOException
238		{
239		// free this database page
240	231	getPageChannel().deallocatePage(cacheDataPage._main._pageNumber);
241
242		// discard from our cache
243	231	_dataPages.remove(cacheDataPage._main._pageNumber);
244
245		// lastly, mark the page as no longer modified
246	231	cacheDataPage._extra._modified = false;
247	231	}
248
249		/**
250		* Reads the given index page from the file.
251		*/
252		private CacheDataPage readDataPage(Integer pageNumber)
253		throws IOException
254		{
255	232	DataPageMain dataPage = new DataPageMain(pageNumber);
256	232	DataPageExtra extra = new DataPageExtra();
257	232	CacheDataPage cacheDataPage = new CacheDataPage(dataPage, extra);
258	232	getIndex().readDataPage(cacheDataPage);
259
260		// associate the extra info with the main data page
261	232	dataPage.setExtra(extra);
262
263	232	return cacheDataPage;
264		}
265
266		/**
267		* Removes the entry with the given index from the given page.
268		*
269		* @param cacheDataPage the page from which to remove the entry
270		* @param entryIdx the index of the entry to remove
271		*/
272		private void removeEntry(CacheDataPage cacheDataPage, int entryIdx)
273		throws IOException
274		{
275	2050	updateEntry(cacheDataPage, entryIdx, null, UpdateType.REMOVE);
276	2050	}
277
278		/**
279		* Adds the entry to the given page at the given index.
280		*
281		* @param cacheDataPage the page to which to add the entry
282		* @param entryIdx the index at which to add the entry
283		* @param newEntry the entry to add
284		*/
285		private void addEntry(CacheDataPage cacheDataPage,
286		int entryIdx,
287		Entry newEntry)
288		throws IOException
289		{
290	2050	updateEntry(cacheDataPage, entryIdx, newEntry, UpdateType.ADD);
291	2050	}
292
293		/**
294		* Updates the entries on the given page according to the given updateType.
295		*
296		* @param cacheDataPage the page to update
297		* @param entryIdx the index at which to add/remove/replace the entry
298		* @param newEntry the entry to add/replace
299		* @param upType the type of update to make
300		*/
301		private void updateEntry(CacheDataPage cacheDataPage,
302		int entryIdx,
303		Entry newEntry,
304		UpdateType upType)
305		throws IOException
306		{
307	10336	DataPageMain dpMain = cacheDataPage._main;
308	10336	DataPageExtra dpExtra = cacheDataPage._extra;
309
310	10336	if(newEntry != null) {
311	8055	validateEntryForPage(dpMain, newEntry);
312		}
313
314		// note, it's slightly ucky, but we need to load the parent page before we
315		// start mucking with our entries because our parent may use our entries.
316	10336	CacheDataPage parentDataPage = (!dpMain.isRoot() ?
317		new CacheDataPage(dpMain.getParentPage()) :
318		null);
319
320	10336	Entry oldLastEntry = dpExtra._entryView.getLast();
321	10336	Entry oldEntry = null;
322	10336	int entrySizeDiff = 0;
323
324	1	switch(upType) {
325		case ADD:
326	2281	dpExtra._entryView.add(entryIdx, newEntry);
327	2281	entrySizeDiff += newEntry.size();
328	2281	break;
329
330		case REPLACE:
331	5774	oldEntry = dpExtra._entryView.set(entryIdx, newEntry);
332	5774	entrySizeDiff += newEntry.size() - oldEntry.size();
333	5774	break;
334
335		case REMOVE: {
336	2281	oldEntry = dpExtra._entryView.remove(entryIdx);
337	2281	entrySizeDiff -= oldEntry.size();
338	2281	break;
339		}
340		default:
341	0	throw new RuntimeException("unknown update type " + upType);
342		}
343
344	10336	boolean updateLast = (oldLastEntry != dpExtra._entryView.getLast());
345
346		// child tail entry updates do not modify the page
347	10336	if(!updateLast \|\| !dpMain.hasChildTail()) {
348	5655	dpExtra._totalEntrySize += entrySizeDiff;
349	5655	setModified(cacheDataPage);
350
351		// for now, just clear the prefix, we'll fix it later
352	5655	dpExtra._entryPrefix = EMPTY_PREFIX;
353		}
354
355	10336	if(dpExtra._entryView.isEmpty()) {
356		// this page is dead
357	233	removeDataPage(parentDataPage, cacheDataPage, oldLastEntry);
358	233	return;
359		}
360
361		// determine if we need to update our parent page
362	10103	if(!updateLast \|\| dpMain.isRoot()) {
363		// no parent
364	4329	return;
365		}
366
367		// the update to the last entry needs to be propagated to our parent
368	5774	replaceParentEntry(parentDataPage, cacheDataPage, oldLastEntry);
369	5774	}
370
371		/**
372		* Removes an index page which has become empty. If this page is the root
373		* page, just clears it.
374		*
375		* @param parentDataPage the parent of the removed page
376		* @param cacheDataPage the page to remove
377		* @param oldLastEntry the last entry for this page (before it was removed)
378		*/
379		private void removeDataPage(CacheDataPage parentDataPage,
380		CacheDataPage cacheDataPage,
381		Entry oldLastEntry)
382		throws IOException
383		{
384	233	DataPageMain dpMain = cacheDataPage._main;
385	233	DataPageExtra dpExtra = cacheDataPage._extra;
386
387	233	if(dpMain.hasChildTail()) {
388	0	throw new IllegalStateException("Still has child tail?");
389		}
390
391	233	if(dpExtra._totalEntrySize != 0) {
392	0	throw new IllegalStateException("Empty page but size is not 0? " +
393		dpExtra._totalEntrySize + ", " +
394		cacheDataPage);
395		}
396
397	233	if(dpMain.isRoot()) {
398		// clear out this page (we don't actually remove it)
399	2	dpExtra._entryPrefix = EMPTY_PREFIX;
400		// when the root page becomes empty, it becomes a leaf page again
401	2	dpMain._leaf = true;
402	2	return;
403		}
404
405		// remove this page from its parent page
406	231	updateParentEntry(parentDataPage, cacheDataPage, oldLastEntry, null,
407		UpdateType.REMOVE);
408
409		// remove this page from any next/prev pages
410	231	removeFromPeers(cacheDataPage);
411	231	}
412
413		/**
414		* Removes a now empty index page from its next and previous peers.
415		*
416		* @param cacheDataPage the page to remove
417		*/
418		private void removeFromPeers(CacheDataPage cacheDataPage)
419		throws IOException
420		{
421	231	DataPageMain dpMain = cacheDataPage._main;
422
423	231	Integer prevPageNumber = dpMain._prevPageNumber;
424	231	Integer nextPageNumber = dpMain._nextPageNumber;
425
426	231	DataPageMain prevMain = dpMain.getPrevPage();
427	231	if(prevMain != null) {
428	222	setModified(new CacheDataPage(prevMain));
429	222	prevMain._nextPageNumber = nextPageNumber;
430		}
431
432	231	DataPageMain nextMain = dpMain.getNextPage();
433	231	if(nextMain != null) {
434	4	setModified(new CacheDataPage(nextMain));
435	4	nextMain._prevPageNumber = prevPageNumber;
436		}
437	231	}
438
439		/**
440		* Adds an entry for the given child page to the given parent page.
441		*
442		* @param parentDataPage the parent page to which to add the entry
443		* @param childDataPage the child from which to get the entry to add
444		*/
445		private void addParentEntry(CacheDataPage parentDataPage,
446		CacheDataPage childDataPage)
447		throws IOException
448		{
449	231	DataPageExtra childExtra = childDataPage._extra;
450	231	updateParentEntry(parentDataPage, childDataPage, null,
451		childExtra._entryView.getLast(), UpdateType.ADD);
452	231	}
453
454		/**
455		* Replaces the entry for the given child page in the given parent page.
456		*
457		* @param parentDataPage the parent page in which to replace the entry
458		* @param childDataPage the child for which the entry is being replaced
459		* @param oldEntry the old child entry for the child page
460		*/
461		private void replaceParentEntry(CacheDataPage parentDataPage,
462		CacheDataPage childDataPage,
463		Entry oldEntry)
464		throws IOException
465		{
466	5774	DataPageExtra childExtra = childDataPage._extra;
467	5774	updateParentEntry(parentDataPage, childDataPage, oldEntry,
468		childExtra._entryView.getLast(), UpdateType.REPLACE);
469	5774	}
470
471		/**
472		* Updates the entry for the given child page in the given parent page
473		* according to the given updateType.
474		*
475		* @param parentDataPage the parent page in which to update the entry
476		* @param childDataPage the child for which the entry is being updated
477		* @param oldEntry the old child entry to remove/replace
478		* @param newEntry the new child entry to replace/add
479		* @param upType the type of update to make
480		*/
481		private void updateParentEntry(CacheDataPage parentDataPage,
482		CacheDataPage childDataPage,
483		Entry oldEntry, Entry newEntry,
484		UpdateType upType)
485		throws IOException
486		{
487	6236	DataPageMain childMain = childDataPage._main;
488	6236	DataPageExtra parentExtra = parentDataPage._extra;
489
490	6236	if(childMain.isTail() && (upType != UpdateType.REMOVE)) {
491		// for add or replace, update the child tail info before updating the
492		// parent entries
493	4477	updateParentTail(parentDataPage, childDataPage, upType);
494		}
495
496	6236	if(oldEntry != null) {
497	6005	oldEntry = oldEntry.asNodeEntry(childMain._pageNumber);
498		}
499	6236	if(newEntry != null) {
500	6005	newEntry = newEntry.asNodeEntry(childMain._pageNumber);
501		}
502
503	6236	boolean expectFound = true;
504	6236	int idx = 0;
505
506	6236	switch(upType) {
507		case ADD:
508	231	expectFound = false;
509	231	idx = parentExtra._entryView.find(newEntry);
510	231	break;
511
512		case REPLACE:
513		case REMOVE:
514	6005	idx = parentExtra._entryView.find(oldEntry);
515	6005	break;
516
517		default:
518	0	throw new RuntimeException("unknown update type " + upType);
519		}
520
521	6236	if(idx < 0) {
522	231	if(expectFound) {
523	0	throw new IllegalStateException(
524		"Could not find child entry in parent; childEntry " + oldEntry +
525		"; parent " + parentDataPage);
526		}
527	231	idx = missingIndexToInsertionPoint(idx);
528		} else {
529	6005	if(!expectFound) {
530	0	throw new IllegalStateException(
531		"Unexpectedly found child entry in parent; childEntry " +
532		newEntry + "; parent " + parentDataPage);
533		}
534		}
535	6236	updateEntry(parentDataPage, idx, newEntry, upType);
536
537	6236	if(childMain.isTail() && (upType == UpdateType.REMOVE)) {
538		// for remove, update the child tail info after updating the parent
539		// entries
540	204	updateParentTail(parentDataPage, childDataPage, upType);
541		}
542	6236	}
543
544		/**
545		* Updates the child tail info in the given parent page according to the
546		* given updateType.
547		*
548		* @param parentDataPage the parent page in which to update the child tail
549		* @param childDataPage the child to add/replace
550		* @param upType the type of update to make
551		*/
552		private void updateParentTail(CacheDataPage parentDataPage,
553		CacheDataPage childDataPage,
554		UpdateType upType)
555		throws IOException
556		{
557	4887	DataPageMain parentMain = parentDataPage._main;
558
559	4887	int newChildTailPageNumber =
560		((upType == UpdateType.REMOVE) ?
561		INVALID_INDEX_PAGE_NUMBER :
562		childDataPage._main._pageNumber);
563	4887	if(!parentMain.isChildTailPageNumber(newChildTailPageNumber)) {
564	410	setModified(parentDataPage);
565	410	parentMain._childTailPageNumber = newChildTailPageNumber;
566		}
567	4887	}
568
569		/**
570		* Verifies that the given entry type (node/leaf) is valid for the given
571		* page (node/leaf).
572		*
573		* @param dpMain the page to which the entry will be added
574		* @param entry the entry being added
575		* @throws IllegalStateException if the entry type does not match the page
576		* type
577		*/
578		private void validateEntryForPage(DataPageMain dpMain, Entry entry) {
579	8339	if(dpMain._leaf != entry.isLeafEntry()) {
580	0	throw new IllegalStateException(
581		"Trying to update page with wrong entry type; pageLeaf " +
582		dpMain._leaf + ", entryLeaf " + entry.isLeafEntry());
583		}
584	8339	}
585
586		/**
587		* Splits an index page which has too many entries on it.
588		*
589		* @param origDataPage the page to split
590		*/
591		private void splitDataPage(CacheDataPage origDataPage)
592		throws IOException
593		{
594	227	DataPageMain origMain = origDataPage._main;
595	227	DataPageExtra origExtra = origDataPage._extra;
596
597	227	setModified(origDataPage);
598
599	227	int numEntries = origExtra._entries.size();
600	227	if(numEntries < 2) {
601	0	throw new IllegalStateException(
602		"Cannot split page with less than 2 entries " + origDataPage);
603		}
604
605	227	if(origMain.isRoot()) {
606		// we can't split the root page directly, so we need to put another page
607		// between the root page and its sub-pages, and then split that page.
608	4	CacheDataPage newDataPage = nestRootDataPage(origDataPage);
609
610		// now, split this new page instead
611	4	origDataPage = newDataPage;
612	4	origMain = newDataPage._main;
613	4	origExtra = newDataPage._extra;
614		}
615
616		// note, it's slightly ucky, but we need to load the parent page before we
617		// start mucking with our entries because our parent may use our entries.
618	227	DataPageMain parentMain = origMain.getParentPage();
619	227	CacheDataPage parentDataPage = new CacheDataPage(parentMain);
620
621		// note, there are many, many ways this could be improved/tweaked. for
622		// now, we just want it to be functional...
623		// so, we will naively move half the entries from one page to a new page.
624
625	227	CacheDataPage newDataPage = allocateNewCacheDataPage(
626		parentMain._pageNumber, origMain._leaf);
627	227	DataPageMain newMain = newDataPage._main;
628	227	DataPageExtra newExtra = newDataPage._extra;
629
630	227	List<Entry> headEntries =
631		origExtra._entries.subList(0, ((numEntries + 1) / 2));
632
633		// move first half of the entries from old page to new page (so we do not
634		// need to muck with any tail entries)
635	227	for(Entry headEntry : headEntries) {
636	1818	newExtra._totalEntrySize += headEntry.size();
637