Coverage Report

 /*
 Copyright (c) 2005 Health Market Science, Inc.
 
 This library is free software; you can redistribute it and/or
 modify it under the terms of the GNU Lesser General Public
 License as published by the Free Software Foundation; either
 version 2.1 of the License, or (at your option) any later version.
 
 This library is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 Lesser General Public License for more details.
 
 You should have received a copy of the GNU Lesser General Public
 License along with this library; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307
 USA
 
 You can contact Health Market Science at info@healthmarketscience.com
 or at the following address:
 
 Health Market Science
 2700 Horizon Drive
 Suite 200
 King of Prussia, PA 19406
 */
 
 package com.healthmarketscience.jackcess;
 
 import java.io.IOException;
 import java.nio.ByteBuffer;
 import java.util.BitSet;
 
 import org.apache.commons.logging.Log;
 import org.apache.commons.logging.LogFactory;
 
 /**
  * Describes which database pages a particular table uses
  * @author Tim McCune
  */
 public class UsageMap
 {
   private static final Log LOG = LogFactory.getLog(UsageMap.class);
   
   /** Inline map type */
   public static final byte MAP_TYPE_INLINE = 0x0;
   /** Reference map type, for maps that are too large to fit inline */
   public static final byte MAP_TYPE_REFERENCE = 0x1;
 
   /** bit index value for an invalid page number */
   private static final int INVALID_BIT_INDEX = -1;
   
   /** owning database */
   private final Database _database;
   /** Page number of the map table declaration */
   private final int _tablePageNum;
   /** Offset of the data page at which the usage map data starts */
   private int _startOffset;
   /** Offset of the data page at which the usage map declaration starts */
   private final short _rowStart;
   /** First page that this usage map applies to */
   private int _startPage;
   /** Last page that this usage map applies to */
   private int _endPage;
   /** bits representing page numbers used, offset from _startPage */
   private BitSet _pageNumbers = new BitSet();
   /** Buffer that contains the usage map table declaration page */
   private final ByteBuffer _tableBuffer;
   /** modification count on the usage map, used to keep the cursors in
       sync */
   private int _modCount;
   /** the current handler implementation for reading/writing the specific
       usage map type.  note, this may change over time. */
   private Handler _handler;
   
   /**
    * @param database database that contains this usage map
    * @param tableBuffer Buffer that contains this map's declaration
    * @param pageNum Page number that this usage map is contained in
    * @param rowStart Offset at which the declaration starts in the buffer
    */
   private UsageMap(Database database, ByteBuffer tableBuffer,
                    int pageNum, short rowStart)
   throws IOException
   {
     _database = database;
     _tableBuffer = tableBuffer;
     _tablePageNum = pageNum;
     _rowStart = rowStart;
     _tableBuffer.position(_rowStart + getFormat().OFFSET_USAGE_MAP_START);
     _startOffset = _tableBuffer.position();
     if (LOG.isDebugEnabled()) {
       LOG.debug("Usage map block:\n" + ByteUtil.toHexString(_tableBuffer, _rowStart,
           tableBuffer.limit() - _rowStart));
     }
   }
 
   public Database getDatabase() {
     return _database;
   }
   
   public JetFormat getFormat() {
     return getDatabase().getFormat();
   }
 
   public PageChannel getPageChannel() {
     return getDatabase().getPageChannel();
   }
   
   /**
    * @param database database that contains this usage map
    * @param pageNum Page number that this usage map is contained in
    * @param rowNum Number of the row on the page that contains this usage map
    * @return Either an InlineUsageMap or a ReferenceUsageMap, depending on
    *         which type of map is found
    */
   public static UsageMap read(Database database, int pageNum,
                               int rowNum, boolean assumeOutOfRangeBitsOn)
     throws IOException
   {
     JetFormat format = database.getFormat();
     PageChannel pageChannel = database.getPageChannel();
     ByteBuffer tableBuffer = pageChannel.createPageBuffer();
     pageChannel.readPage(tableBuffer, pageNum);
     short rowStart = Table.findRowStart(tableBuffer, rowNum, format);
     int rowEnd = Table.findRowEnd(tableBuffer, rowNum, format);
     tableBuffer.limit(rowEnd);    
     byte mapType = tableBuffer.get(rowStart);
     UsageMap rtn = new UsageMap(database, tableBuffer, pageNum, rowStart);
     rtn.initHandler(mapType, assumeOutOfRangeBitsOn);
     return rtn;
   }
 
   private void initHandler(byte mapType, boolean assumeOutOfRangeBitsOn)
     throws IOException
   {
     if (mapType == MAP_TYPE_INLINE) {
       _handler = new InlineHandler(assumeOutOfRangeBitsOn);
     } else if (mapType == MAP_TYPE_REFERENCE) {
       _handler = new ReferenceHandler();
     } else {
       throw new IOException("Unrecognized map type: " + mapType);
     }
   }
   
   public PageCursor cursor() {
     return new PageCursor();
   }
 
   protected short getRowStart() {
     return _rowStart;
   }
 
   protected int getRowEnd() {
     return getTableBuffer().limit();
   }
 
   protected void setStartOffset(int startOffset) {
     _startOffset = startOffset;
   }
   
   protected int getStartOffset() {
     return _startOffset;
   }
   
   protected ByteBuffer getTableBuffer() {
     return _tableBuffer;
   }
   
   protected int getTablePageNumber() {
     return _tablePageNum;
   }
   
   protected int getStartPage() {
     return _startPage;
   }
     
   protected int getEndPage() {
     return _endPage;
   }
     
   protected BitSet getPageNumbers() {
     return _pageNumbers;
   }
 
   protected void setPageRange(int newStartPage, int newEndPage) {
     _startPage = newStartPage;
     _endPage = newEndPage;
   }
 
   protected boolean isPageWithinRange(int pageNumber)
   {
     return((pageNumber >= _startPage) && (pageNumber < _endPage));
   }
 
   protected int getFirstPageNumber() {
     return bitIndexToPageNumber(getNextBitIndex(-1), RowId.LAST_PAGE_NUMBER);
   }
 
   protected int getNextPageNumber(int curPage) {
     return bitIndexToPageNumber(
         getNextBitIndex(pageNumberToBitIndex(curPage)),
         RowId.LAST_PAGE_NUMBER);
   }    
   
   protected int getNextBitIndex(int curIndex) {
     return _pageNumbers.nextSetBit(curIndex + 1);
   }    
   
   protected int getLastPageNumber() {
     return bitIndexToPageNumber(getPrevBitIndex(_pageNumbers.length()),
                                 RowId.FIRST_PAGE_NUMBER);
   }
 
   protected int getPrevPageNumber(int curPage) {
     return bitIndexToPageNumber(
         getPrevBitIndex(pageNumberToBitIndex(curPage)),
         RowId.FIRST_PAGE_NUMBER);
   }    
   
   protected int getPrevBitIndex(int curIndex) {
     --curIndex;
     while((curIndex >= 0) && !_pageNumbers.get(curIndex)) {
       --curIndex;
     }
     return curIndex;
   }    
   
   protected int bitIndexToPageNumber(int bitIndex,
                                      int invalidPageNumber) {
     return((bitIndex >= 0) ? (_startPage + bitIndex) : invalidPageNumber);
   }
 
   protected int pageNumberToBitIndex(int pageNumber) {
     return((pageNumber >= 0) ? (pageNumber - _startPage) :
            INVALID_BIT_INDEX);
   }
 
   protected void clearTableAndPages()
   {
     // reset some values
     _pageNumbers.clear();
     _startPage = 0;
     _endPage = 0;
     ++_modCount;
     
     // clear out the table data (everything except map type)
     int tableStart = getRowStart() + 1;
     int tableEnd = getRowEnd();
     ByteUtil.clearRange(_tableBuffer, tableStart, tableEnd);
   }
   
   protected void writeTable()
     throws IOException
   {
     // note, we only want to write the row data with which we are working
     getPageChannel().writePage(_tableBuffer, _tablePageNum, _rowStart);
   }
   
   /**
    * Read in the page numbers in this inline map
    */
   protected void processMap(ByteBuffer buffer, int bufferStartPage)
   {
     int byteCount = 0;
     while (buffer.hasRemaining()) {
       byte b = buffer.get();
       if(b != (byte)0) {
         for (int i = 0; i < 8; i++) {
           if ((b & (1 << i)) != 0) {
             int pageNumberOffset = (byteCount * 8 + i) + bufferStartPage;
             int pageNumber = bitIndexToPageNumber(
                 pageNumberOffset,
                 PageChannel.INVALID_PAGE_NUMBER);
             if(!isPageWithinRange(pageNumber)) {
               throw new IllegalStateException(
                   "found page number " + pageNumber
                   + " in usage map outside of expected range " +
                   _startPage + " to " + _endPage);
             }
             _pageNumbers.set(pageNumberOffset);
           }
         }
       }
       byteCount++;
     }
   }
 
   /**
    * Determines if the given page number is contained in this map.
    */
   public boolean containsPageNumber(int pageNumber) {
     return _handler.containsPageNumber(pageNumber);
   }
   
   /**
    * Add a page number to this usage map
    */
   public void addPageNumber(int pageNumber) throws IOException {
     ++_modCount;
     _handler.addOrRemovePageNumber(pageNumber, true);
   }
   
   /**
    * Remove a page number from this usage map
    */
   public void removePageNumber(int pageNumber) throws IOException {
     ++_modCount;
     _handler.addOrRemovePageNumber(pageNumber, false);
   }
   
   protected void updateMap(int absolutePageNumber,
                            int bufferRelativePageNumber,
                            ByteBuffer buffer, boolean add)
     throws IOException
   {
     //Find the byte to which to apply the bitmask and create the bitmask
     int offset = bufferRelativePageNumber / 8;
     int bitmask = 1 << (bufferRelativePageNumber % 8);
     byte b = buffer.get(_startOffset + offset);
 
     // check current value for this page number
     int pageNumberOffset = pageNumberToBitIndex(absolutePageNumber);
     boolean isOn = _pageNumbers.get(pageNumberOffset);
     if(isOn == add) {
       throw new IOException("Page number " + absolutePageNumber + " already " +
                             ((add) ? "added to" : "removed from") +
                             " usage map, expected range " +
                             _startPage + " to " + _endPage);
     }
     
     //Apply the bitmask
     if (add) {
       b |= bitmask;
       _pageNumbers.set(pageNumberOffset);
     } else {
       b &= ~bitmask;
       _pageNumbers.clear(pageNumberOffset);
     }
     buffer.put(_startOffset + offset, b);
   }
 
   /**
    * Promotes and inline usage map to a reference usage map.
    */
   private void promoteInlineHandlerToReferenceHandler(int newPageNumber)
     throws IOException
   {
     // copy current page number info to new references and then clear old
     int oldStartPage = _startPage;
     BitSet oldPageNumbers = (BitSet)_pageNumbers.clone();
 
     // clear out the main table (inline usage map data and start page)
     clearTableAndPages();
     
     // set the new map type
     _tableBuffer.put(getRowStart(), MAP_TYPE_REFERENCE);
 
     // write the new table data
     writeTable();
     
     // set new handler
     _handler = new ReferenceHandler();
 
     // update new handler with old data
     reAddPages(oldStartPage, oldPageNumbers, newPageNumber);
   }
 
   private void reAddPages(int oldStartPage, BitSet oldPageNumbers,
                           int newPageNumber)
     throws IOException
   {
     // add all the old pages back in
     for(int i = oldPageNumbers.nextSetBit(0); i >= 0;
         i = oldPageNumbers.nextSetBit(i + 1)) {
       addPageNumber(oldStartPage + i);
     }
 
     if(newPageNumber > PageChannel.INVALID_PAGE_NUMBER) {
       // and then add the new page
       addPageNumber(newPageNumber);
     }
   }
 
   @Override
   public String toString() {
     StringBuilder builder = new StringBuilder(
         "page numbers (range " + _startPage + " " + _endPage + "): [");
     PageCursor pCursor = cursor();
     while(true) {
       int nextPage = pCursor.getNextPage();
       if(nextPage < 0) {
         break;
       }
       builder.append(nextPage).append(", ");
     }
     builder.append("]");
     return builder.toString();
   }
   
   private abstract class Handler
   {
     protected Handler() {
     }
 
     public boolean containsPageNumber(int pageNumber) {
       return(isPageWithinRange(pageNumber) &&
              getPageNumbers().get(pageNumberToBitIndex(pageNumber)));
     }
     
     /**
      * @param pageNumber Page number to add or remove from this map
      * @param add True to add it, false to remove it
      */
     public abstract void addOrRemovePageNumber(int pageNumber, boolean add)
       throws IOException;
   }
 
   /**
    * Usage map whose map is written inline in the same page.  For Jet4, this
    * type of map can usually contains a maximum of 512 pages.  Free space maps
    * are always inline, used space maps may be inline or reference.  It has a
    * start page, which all page numbers in its map are calculated as starting
    * from.
    * @author Tim McCune
    */
   private class InlineHandler extends Handler
   {
     private final boolean _assumeOutOfRangeBitsOn;
     private final int _maxInlinePages;
     
     private InlineHandler(boolean assumeOutOfRangeBitsOn)
       throws IOException
     {
       _assumeOutOfRangeBitsOn = assumeOutOfRangeBitsOn;
       _maxInlinePages = (getInlineDataEnd() - getInlineDataStart()) * 8;
       int startPage = getTableBuffer().getInt(getRowStart() + 1);
       setInlinePageRange(startPage);
       processMap(getTableBuffer(), 0);
     }
 
     private int getMaxInlinePages() {
       return _maxInlinePages;
     }
 
     private int getInlineDataStart() {
       return getRowStart() + getFormat().OFFSET_USAGE_MAP_START;
     }
 
     private int getInlineDataEnd() {
       return getRowEnd();
     }
     
     /**
      * Sets the page range for an inline usage map starting from the given
      * page.
      */
     private void setInlinePageRange(int startPage) {
       setPageRange(startPage, startPage + getMaxInlinePages());
     }      
 
     @Override
     public boolean containsPageNumber(int pageNumber) {
       return(super.containsPageNumber(pageNumber) ||
              (_assumeOutOfRangeBitsOn && (pageNumber >= 0) &&
               !isPageWithinRange(pageNumber)));
     }
     
     @Override
     public void addOrRemovePageNumber(int pageNumber, boolean add)
       throws IOException
     {
       if(isPageWithinRange(pageNumber)) {
 
         // easy enough, just update the inline data
         int bufferRelativePageNumber = pageNumberToBitIndex(pageNumber);
         updateMap(pageNumber, bufferRelativePageNumber, getTableBuffer(), add);
         // Write the updated map back to disk
         writeTable();
         
       } else {
 
         // uh-oh, we've split our britches.  what now?  determine what our
         // status is
         int firstPage = getFirstPageNumber();
         int lastPage = getLastPageNumber();
         
         if(add) {
 
           // we can ignore out-of-range page addition if we are already
           // assuming out-of-range bits are "on".  Note, we are leaving small
           // holes in the database here (leaving behind some free pages), but
           // it's not the end of the world.
           if(!_assumeOutOfRangeBitsOn) {
             
             // we are adding, can we shift the bits and stay inline?
             if(firstPage <= PageChannel.INVALID_PAGE_NUMBER) {
               // no pages currently
               firstPage = pageNumber;
               lastPage = pageNumber;
             } else if(pageNumber > lastPage) {
               lastPage = pageNumber;
             } else {
               firstPage = pageNumber;
             }
             if((lastPage - firstPage + 1) < getMaxInlinePages()) {
 
               // we can still fit within an inline map
               moveToNewStartPage(firstPage, pageNumber);
             
             } else {
               // not going to happen, need to promote the usage map to a
               // reference map
               promoteInlineHandlerToReferenceHandler(pageNumber);
             }
           }
         } else {
 
           // we are removing, what does that mean?
           if(_assumeOutOfRangeBitsOn) {
 
             // we are using an inline map and assuming that anything not
             // within the current range is "on".  so, if we attempt to set a
             // bit which is before the current page, ignore it, we are not
             // going back for it.
             if((firstPage <= PageChannel.INVALID_PAGE_NUMBER) ||
                (pageNumber > lastPage)) {
 
               // move to new start page, filling in as we move
               moveToNewStartPageForRemove(firstPage, pageNumber);
               
             }
             
           } else {
 
             // this should not happen, we are removing a page which is not in
             // the map
             throw new IOException("Page number " + pageNumber +
                                   " already removed from usage map" +
                                   ", expected range " +
                                   _startPage + " to " + _endPage);
           }
         }
 
       }
     }
 
     /**
      * Shifts the inline usage map so that it now starts with the given page.
      * @param newStartPage new page at which to start
      * @param newPageNumber optional page number to add once the map has been
      *                      shifted to the new start page
      */
     private void moveToNewStartPage(int newStartPage, int newPageNumber)
       throws IOException
     {
       int oldStartPage = getStartPage();
       BitSet oldPageNumbers = (BitSet)getPageNumbers().clone();
 
       // clear out the main table (inline usage map data and start page)
       clearTableAndPages();
 
       // write new start page
       ByteBuffer tableBuffer = getTableBuffer();
       tableBuffer.position(getRowStart() + 1);
       tableBuffer.putInt(newStartPage);
 
       // write the new table data
       writeTable();
 
       // set new page range
       setInlinePageRange(newStartPage);
 
       // put the pages back in
       reAddPages(oldStartPage, oldPageNumbers, newPageNumber);
     }
 
     /**
      * Shifts the inline usage map so that it now starts with the given
      * firstPage (if valid), otherwise the newPageNumber.  Any page numbers
      * added to the end of the usage map are set to "on".
      * @param firstPage current first used page
      * @param newPageNumber page number to remove once the map has been
      *                      shifted to the new start page
      */
     private void moveToNewStartPageForRemove(int firstPage, int newPageNumber)
       throws IOException
     {
       int oldEndPage = getEndPage();
       int newStartPage = 
         ((firstPage <= PageChannel.INVALID_PAGE_NUMBER) ? newPageNumber :
          // just shift a little and discard any initial unused pages.
          (newPageNumber - (getMaxInlinePages() / 2)));
 
       // move the current data
       moveToNewStartPage(newStartPage, PageChannel.INVALID_PAGE_NUMBER);
 
       if(firstPage <= PageChannel.INVALID_PAGE_NUMBER) {
 
         // this is the common case where we left everything behind
         ByteUtil.fillRange(_tableBuffer, getInlineDataStart(),
                            getInlineDataEnd());
 
         // write out the updated table
         writeTable();
 
         // "add" all the page numbers
         getPageNumbers().set(0, getMaxInlinePages());
 
       } else {
 
         // add every new page manually
         for(int i = oldEndPage; i < getEndPage(); ++i) {
           addPageNumber(i);
         }
       }
 
       // lastly, remove the new page
       removePageNumber(newPageNumber);
     }
   }
 
   /**
    * Usage map whose map is written across one or more entire separate p

1		/*
2		Copyright (c) 2005 Health Market Science, Inc.
3
4		This library is free software; you can redistribute it and/or
5		modify it under the terms of the GNU Lesser General Public
6		License as published by the Free Software Foundation; either
7		version 2.1 of the License, or (at your option) any later version.
8
9		This library is distributed in the hope that it will be useful,
10		but WITHOUT ANY WARRANTY; without even the implied warranty of
11		MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12		Lesser General Public License for more details.
13
14		You should have received a copy of the GNU Lesser General Public
15		License along with this library; if not, write to the Free Software
16		Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
17		USA
18
19		You can contact Health Market Science at info@healthmarketscience.com
20		or at the following address:
21
22		Health Market Science
23		2700 Horizon Drive
24		Suite 200
25		King of Prussia, PA 19406
26		*/
27
28		package com.healthmarketscience.jackcess;
29
30		import java.io.IOException;
31		import java.nio.ByteBuffer;
32		import java.util.BitSet;
33
34		import org.apache.commons.logging.Log;
35		import org.apache.commons.logging.LogFactory;
36
37		/**
38		* Describes which database pages a particular table uses
39		* @author Tim McCune
40		*/
41	47331	public class UsageMap
42		{
43	1	private static final Log LOG = LogFactory.getLog(UsageMap.class);
44
45		/** Inline map type */
46		public static final byte MAP_TYPE_INLINE = 0x0;
47		/** Reference map type, for maps that are too large to fit inline */
48		public static final byte MAP_TYPE_REFERENCE = 0x1;
49
50		/** bit index value for an invalid page number */
51		private static final int INVALID_BIT_INDEX = -1;
52
53		/** owning database */
54		private final Database _database;
55		/** Page number of the map table declaration */
56		private final int _tablePageNum;
57		/** Offset of the data page at which the usage map data starts */
58		private int _startOffset;
59		/** Offset of the data page at which the usage map declaration starts */
60		private final short _rowStart;
61		/** First page that this usage map applies to */
62		private int _startPage;
63		/** Last page that this usage map applies to */
64		private int _endPage;
65		/** bits representing page numbers used, offset from _startPage */
66	605	private BitSet _pageNumbers = new BitSet();
67		/** Buffer that contains the usage map table declaration page */
68		private final ByteBuffer _tableBuffer;
69		/** modification count on the usage map, used to keep the cursors in
70		sync */
71		private int _modCount;
72		/** the current handler implementation for reading/writing the specific
73		usage map type. note, this may change over time. */
74		private Handler _handler;
75
76		/**
77		* @param database database that contains this usage map
78		* @param tableBuffer Buffer that contains this map's declaration
79		* @param pageNum Page number that this usage map is contained in
80		* @param rowStart Offset at which the declaration starts in the buffer
81		*/
82		private UsageMap(Database database, ByteBuffer tableBuffer,
83		int pageNum, short rowStart)
84		throws IOException
85	605	{
86	605	_database = database;
87	605	_tableBuffer = tableBuffer;
88	605	_tablePageNum = pageNum;
89	605	_rowStart = rowStart;
90	605	_tableBuffer.position(_rowStart + getFormat().OFFSET_USAGE_MAP_START);
91	605	_startOffset = _tableBuffer.position();
92	605	if (LOG.isDebugEnabled()) {
93	0	LOG.debug("Usage map block:\n" + ByteUtil.toHexString(_tableBuffer, _rowStart,
94		tableBuffer.limit() - _rowStart));
95		}
96	605	}
97
98		public Database getDatabase() {
99	9008	return _database;
100		}
101
102		public JetFormat getFormat() {
103	3354	return getDatabase().getFormat();
104		}
105
106		public PageChannel getPageChannel() {
107	5654	return getDatabase().getPageChannel();
108		}
109
110		/**
111		* @param database database that contains this usage map
112		* @param pageNum Page number that this usage map is contained in
113		* @param rowNum Number of the row on the page that contains this usage map
114		* @return Either an InlineUsageMap or a ReferenceUsageMap, depending on
115		* which type of map is found
116		*/
117		public static UsageMap read(Database database, int pageNum,
118		int rowNum, boolean assumeOutOfRangeBitsOn)
119		throws IOException
120		{
121	605	JetFormat format = database.getFormat();
122	605	PageChannel pageChannel = database.getPageChannel();
123	605	ByteBuffer tableBuffer = pageChannel.createPageBuffer();
124	605	pageChannel.readPage(tableBuffer, pageNum);
125	605	short rowStart = Table.findRowStart(tableBuffer, rowNum, format);
126	605	int rowEnd = Table.findRowEnd(tableBuffer, rowNum, format);
127	605	tableBuffer.limit(rowEnd);
128	605	byte mapType = tableBuffer.get(rowStart);
129	605	UsageMap rtn = new UsageMap(database, tableBuffer, pageNum, rowStart);
130	605	rtn.initHandler(mapType, assumeOutOfRangeBitsOn);
131	605	return rtn;
132		}
133
134		private void initHandler(byte mapType, boolean assumeOutOfRangeBitsOn)
135		throws IOException
136		{
137	605	if (mapType == MAP_TYPE_INLINE) {
138	567	_handler = new InlineHandler(assumeOutOfRangeBitsOn);
139	38	} else if (mapType == MAP_TYPE_REFERENCE) {
140	38	_handler = new ReferenceHandler();
141		} else {
142	0	throw new IOException("Unrecognized map type: " + mapType);
143		}
144	605	}
145
146		public PageCursor cursor() {
147	15530	return new PageCursor();
148		}
149
150		protected short getRowStart() {
151	2123	return _rowStart;
152		}
153
154		protected int getRowEnd() {
155	610	return getTableBuffer().limit();
156		}
157
158		protected void setStartOffset(int startOffset) {
159	38	_startOffset = startOffset;
160	38	}
161
162		protected int getStartOffset() {
163	0	return _startOffset;
164		}
165
166		protected ByteBuffer getTableBuffer() {
167	7760	return _tableBuffer;
168		}
169
170		protected int getTablePageNumber() {
171	0	return _tablePageNum;
172		}
173
174		protected int getStartPage() {
175	5	return _startPage;
176		}
177
178		protected int getEndPage() {
179	258	return _endPage;
180		}
181
182		protected BitSet getPageNumbers() {
183	63950	return _pageNumbers;
184		}
185
186		protected void setPageRange(int newStartPage, int newEndPage) {
187	610	_startPage = newStartPage;
188	610	_endPage = newEndPage;
189	610	}
190
191		protected boolean isPageWithinRange(int pageNumber)
192		{
193	98489	return((pageNumber >= _startPage) && (pageNumber < _endPage));
194		}
195
196		protected int getFirstPageNumber() {
197	193	return bitIndexToPageNumber(getNextBitIndex(-1), RowId.LAST_PAGE_NUMBER);
198		}
199
200		protected int getNextPageNumber(int curPage) {
201	1028	return bitIndexToPageNumber(
202		getNextBitIndex(pageNumberToBitIndex(curPage)),
203		RowId.LAST_PAGE_NUMBER);
204		}
205
206		protected int getNextBitIndex(int curIndex) {
207	1221	return _pageNumbers.nextSetBit(curIndex + 1);
208		}
209
210		protected int getLastPageNumber() {
211	15182	return bitIndexToPageNumber(getPrevBitIndex(_pageNumbers.length()),
212		RowId.FIRST_PAGE_NUMBER);
213		}
214
215		protected int getPrevPageNumber(int curPage) {
216	156	return bitIndexToPageNumber(
217		getPrevBitIndex(pageNumberToBitIndex(curPage)),
218		RowId.FIRST_PAGE_NUMBER);
219		}
220
221		protected int getPrevBitIndex(int curIndex) {
222	15338	--curIndex;
223	15643	while((curIndex >= 0) && !_pageNumbers.get(curIndex)) {
224	305	--curIndex;
225		}
226	15338	return curIndex;
227		}
228
229		protected int bitIndexToPageNumber(int bitIndex,
230		int invalidPageNumber) {
231	45740	return((bitIndex >= 0) ? (_startPage + bitIndex) : invalidPageNumber);
232		}
233
234		protected int pageNumberToBitIndex(int pageNumber) {
235	75544	return((pageNumber >= 0) ? (pageNumber - _startPage) :
236		INVALID_BIT_INDEX);
237		}
238
239		protected void clearTableAndPages()
240		{
241		// reset some values
242	5	_pageNumbers.clear();
243	5	_startPage = 0;
244	5	_endPage = 0;
245	5	++_modCount;
246
247		// clear out the table data (everything except map type)
248	5	int tableStart = getRowStart() + 1;
249	5	int tableEnd = getRowEnd();
250	5	ByteUtil.clearRange(_tableBuffer, tableStart, tableEnd);
251	5	}
252
253		protected void writeTable()
254		throws IOException
255		{
256		// note, we only want to write the row data with which we are working
257	5095	getPageChannel().writePage(_tableBuffer, _tablePageNum, _rowStart);
258	5095	}
259
260		/**
261		* Read in the page numbers in this inline map
262		*/
263		protected void processMap(ByteBuffer buffer, int bufferStartPage)
264		{
265	576	int byteCount = 0;
266	74128	while (buffer.hasRemaining()) {
267	73552	byte b = buffer.get();
268	73552	if(b != (byte)0) {
269	36576	for (int i = 0; i < 8; i++) {
270	32512	if ((b & (1 << i)) != 0) {
271	29181	int pageNumberOffset = (byteCount * 8 + i) + bufferStartPage;
272	29181	int pageNumber = bitIndexToPageNumber(
273		pageNumberOffset,
274		PageChannel.INVALID_PAGE_NUMBER);
275	29181	if(!isPageWithinRange(pageNumber)) {
276	0	throw new IllegalStateException(
277		"found page number " + pageNumber
278		+ " in usage map outside of expected range " +
279		_startPage + " to " + _endPage);
280		}
281	29181	_pageNumbers.set(pageNumberOffset);
282		}
283		}
284		}
285	73552	byteCount++;
286	73552	}
287	576	}
288
289		/**
290		* Determines if the given page number is contained in this map.
291		*/
292		public boolean containsPageNumber(int pageNumber) {
293	63945	return _handler.containsPageNumber(pageNumber);
294		}
295
296		/**
297		* Add a page number to this usage map
298		*/
299		public void addPageNumber(int pageNumber) throws IOException {
300	2887	++_modCount;
301	2887	_handler.addOrRemovePageNumber(pageNumber, true);
302	2887	}
303
304		/**
305		* Remove a page number from this usage map
306		*/
307		public void removePageNumber(int pageNumber) throws IOException {
308	2476	++_modCount;
309	2476	_handler.addOrRemovePageNumber(pageNumber, false);
310	2476	}
311
312		protected void updateMap(int absolutePageNumber,
313		int bufferRelativePageNumber,
314		ByteBuffer buffer, boolean add)
315		throws IOException
316		{
317		//Find the byte to which to apply the bitmask and create the bitmask
318	5345	int offset = bufferRelativePageNumber / 8;
319	5345	int bitmask = 1 << (bufferRelativePageNumber % 8);
320	5345	byte b = buffer.get(_startOffset + offset);
321
322		// check current value for this page number
323	5345	int pageNumberOffset = pageNumberToBitIndex(absolutePageNumber);
324	5345	boolean isOn = _pageNumbers.get(pageNumberOffset);
325	5345	if(isOn == add) {
326	0	throw new IOException("Page number " + absolutePageNumber + " already " +
327		((add) ? "added to" : "removed from") +
328		" usage map, expected range " +
329		_startPage + " to " + _endPage);
330		}
331
332		//Apply the bitmask
333	5345	if (add) {
334	2870	b \|= bitmask;
335	2870	_pageNumbers.set(pageNumberOffset);
336		} else {
337	2475	b &= ~bitmask;
338	2475	_pageNumbers.clear(pageNumberOffset);
339		}
340	5345	buffer.put(_startOffset + offset, b);
341	5345	}
342
343		/**
344		* Promotes and inline usage map to a reference usage map.
345		*/
346		private void promoteInlineHandlerToReferenceHandler(int newPageNumber)
347		throws IOException
348		{
349		// copy current page number info to new references and then clear old
350	0	int oldStartPage = _startPage;
351	0	BitSet oldPageNumbers = (BitSet)_pageNumbers.clone();
352
353		// clear out the main table (inline usage map data and start page)
354	0	clearTableAndPages();
355
356		// set the new map type
357	0	_tableBuffer.put(getRowStart(), MAP_TYPE_REFERENCE);
358
359		// write the new table data
360	0	writeTable();
361
362		// set new handler
363	0	_handler = new ReferenceHandler();
364
365		// update new handler with old data
366	0	reAddPages(oldStartPage, oldPageNumbers, newPageNumber);
367	0	}
368
369		private void reAddPages(int oldStartPage, BitSet oldPageNumbers,
370		int newPageNumber)
371		throws IOException
372		{
373		// add all the old pages back in
374	5	for(int i = oldPageNumbers.nextSetBit(0); i >= 0;
375	484	i = oldPageNumbers.nextSetBit(i + 1)) {
376	484	addPageNumber(oldStartPage + i);
377		}
378
379	5	if(newPageNumber > PageChannel.INVALID_PAGE_NUMBER) {
380		// and then add the new page
381	4	addPageNumber(newPageNumber);
382		}
383	5	}
384
385		@Override
386		public String toString() {
387	2	StringBuilder builder = new StringBuilder(
388		"page numbers (range " + _startPage + " " + _endPage + "): [");
389	2	PageCursor pCursor = cursor();
390		while(true) {
391	4	int nextPage = pCursor.getNextPage();
392	4	if(nextPage < 0) {
393	2	break;
394		}
395	2	builder.append(nextPage).append(", ");
396	2	}
397	2	builder.append("]");
398	2	return builder.toString();
399		}
400
401		private abstract class Handler
402		{
403	605	protected Handler() {
404	605	}
405
406		public boolean containsPageNumber(int pageNumber) {
407	63945	return(isPageWithinRange(pageNumber) &&
408		getPageNumbers().get(pageNumberToBitIndex(pageNumber)));
409		}
410
411		/**
412		* @param pageNumber Page number to add or remove from this map
413		* @param add True to add it, false to remove it
414		*/
415		public abstract void addOrRemovePageNumber(int pageNumber, boolean add)
416		throws IOException;
417		}
418
419		/**
420		* Usage map whose map is written inline in the same page. For Jet4, this
421		* type of map can usually contains a maximum of 512 pages. Free space maps
422		* are always inline, used space maps may be inline or reference. It has a
423		* start page, which all page numbers in its map are calculated as starting
424		* from.
425		* @author Tim McCune
426		*/
427	567	private class InlineHandler extends Handler
428		{
429		private final boolean _assumeOutOfRangeBitsOn;
430		private final int _maxInlinePages;
431
432		private InlineHandler(boolean assumeOutOfRangeBitsOn)
433		throws IOException
434	567	{
435	567	_assumeOutOfRangeBitsOn = assumeOutOfRangeBitsOn;
436	567	_maxInlinePages = (getInlineDataEnd() - getInlineDataStart()) * 8;
437	567	int startPage = getTableBuffer().getInt(getRowStart() + 1);
438	567	setInlinePageRange(startPage);
439	567	processMap(getTableBuffer(), 0);
440	567	}
441
442		private int getMaxInlinePages() {
443	577	return _maxInlinePages;
444		}
445
446		private int getInlineDataStart() {
447	567	return getRowStart() + getFormat().OFFSET_USAGE_MAP_START;
448		}
449
450		private int getInlineDataEnd() {
451	567	return getRowEnd();
452		}
453
454		/**
455		* Sets the page range for an inline usage map starting from the given
456		* page.
457		*/
458		private void setInlinePageRange(int startPage) {
459	572	setPageRange(startPage, startPage + getMaxInlinePages());
460	572	}
461
462		@Override
463		public boolean containsPageNumber(int pageNumber) {
464	37146	return(super.containsPageNumber(pageNumber) \|\|
465		(_assumeOutOfRangeBitsOn && (pageNumber >= 0) &&
466		!isPageWithinRange(pageNumber)));
467		}
468
469		@Override
470		public void addOrRemovePageNumber(int pageNumber, boolean add)
471		throws IOException
472		{
473	5088	if(isPageWithinRange(pageNumber)) {
474
475		// easy enough, just update the inline data
476	5070	int bufferRelativePageNumber = pageNumberToBitIndex(pageNumber);
477	5070	updateMap(pageNumber, bufferRelativePageNumber, getTableBuffer(), add);
478		// Write the updated map back to disk
479	5070	writeTable();
480
481	5070	} else {
482
483		// uh-oh, we've split our britches. what now? determine what our
484		// status is
485	18	int firstPage = getFirstPageNumber();
486	18	int lastPage = getLastPageNumber();
487
488	18	if(add) {
489
490		// we can ignore out-of-range page addition if we are already
491		// assuming out-of-range bits are "on". Note, we are leaving small
492		// holes in the database here (leaving behind some free pages), but
493		// it's not the end of the world.
494	17	if(!_assumeOutOfRangeBitsOn) {
495
496		// we are adding, can we shift the bits and stay inline?
497	4	if(firstPage <= PageChannel.INVALID_PAGE_NUMBER) {
498		// no pages currently
499	3	firstPage = pageNumber;
500	3	lastPage = pageNumber;
501	1	} else if(pageNumber > lastPage) {
502	1	lastPage = pageNumber;
503		} else {
504	0	firstPage = pageNumber;
505		}
506	4	if((lastPage - firstPage + 1) < getMaxInlinePages()) {
507
508		// we can still fit within an inline map
509	4	moveToNewStartPage(firstPage, pageNumber);
510
511		} else {
512		// not going to happen, need to promote the usage map to a
513		// reference map
514	0	promoteInlineHandlerToReferenceHandler(pageNumber);
515		}
516		}
517		} else {
518
519		// we are removing, what does that mean?
520	1	if(_assumeOutOfRangeBitsOn) {
521
522		// we are using an inline map and assuming that anything not
523		// within the current range is "on". so, if we attempt to set a
524		// bit which is before the current page, ignore it, we are not
525		// going back for it.
526	1	if((firstPage <= PageChannel.INVALID_PAGE_NUMBER) \|\|
527		(pageNumber > lastPage)) {
528
529		// move to new start page, filling in as we move
530	1	moveToNewStartPageForRemove(firstPage, pageNumber);
531
532		}
533
534		} else {
535
536		// this should not happen, we are removing a page which is not in
537		// the map
538	0	throw new IOException("Page number " + pageNumber +
539		" already removed from usage map" +
540		", expected range " +
541		_startPage + " to " + _endPage);
542		}
543		}
544
545		}
546	5088	}
547
548		/**
549		* Shifts the inline usage map so that it now starts with the given page.
550		* @param newStartPage new page at which to start
551		* @param newPageNumber optional page number to add once the map has been
552		* shifted to the new start page
553		*/
554		private void moveToNewStartPage(int newStartPage, int newPageNumber)
555		throws IOException
556		{
557	5	int oldStartPage = getStartPage();
558	5	BitSet oldPageNumbers = (BitSet)getPageNumbers().clone();
559
560		// clear out the main table (inline usage map data and start page)
561	5	clearTableAndPages();
562
563		// write new start page
564	5	ByteBuffer tableBuffer = getTableBuffer();
565	5	tableBuffer.position(getRowStart() + 1);
566	5	tableBuffer.putInt(newStartPage);
567
568		// write the new table data
569	5	writeTable();
570
571		// set new page range
572	5	setInlinePageRange(newStartPage);
573
574		// put the pages back in
575	5	reAddPages(oldStartPage, oldPageNumbers, newPageNumber);
576	5	}
577
578		/**
579		* Shifts the inline usage map so that it now starts with the given
580		* firstPage (if valid), otherwise the newPageNumber. Any page numbers
581		* added to the end of the usage map are set to "on".
582		* @param firstPage current first used page
583		* @param newPageNumber page number to remove once the map has been
584		* shifted to the new start page
585		*/
586		private void moveToNewStartPageForRemove(int firstPage, int newPageNumber)
587		throws IOException
588		{
589	1	int oldEndPage = getEndPage();
590	1	int newStartPage =
591		((firstPage <= PageChannel.INVALID_PAGE_NUMBER) ? newPageNumber :
592		// just shift a little and discard any initial unused pages.
593		(newPageNumber - (getMaxInlinePages() / 2)));
594
595		// move the current data
596	1	moveToNewStartPage(newStartPage, PageChannel.INVALID_PAGE_NUMBER);
597
598	1	if(firstPage <= PageChannel.INVALID_PAGE_NUMBER) {
599
600		// this is the common case where we left everything behind
601	0	ByteUtil.fillRange(_tableBuffer, getInlineDataStart(),
602		getInlineDataEnd());
603
604		// write out the updated table
605	0	writeTable();
606
607		// "add" all the page numbers
608	0	getPageNumbers().set(0, getMaxInlinePages());
609
610		} else {
611
612		// add every new page manually
613	257	for(int i = oldEndPage; i < getEndPage(); ++i) {
614	256	addPageNumber(i);
615		}
616		}
617
618		// lastly, remove the new page
619	1	removePageNumber(newPageNumber);
620	1	}
621		}
622
623		/**
624		* Usage map whose map is written across one or more entire separate p