View Javadoc
1   /*
2   Copyright (c) 2005 Health Market Science, Inc.
3   
4   Licensed under the Apache License, Version 2.0 (the "License");
5   you may not use this file except in compliance with the License.
6   You may obtain a copy of the License at
7   
8       http://www.apache.org/licenses/LICENSE-2.0
9   
10  Unless required by applicable law or agreed to in writing, software
11  distributed under the License is distributed on an "AS IS" BASIS,
12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  See the License for the specific language governing permissions and
14  limitations under the License.
15  */
16  
17  package com.healthmarketscience.jackcess.impl;
18  
19  import java.io.IOException;
20  import java.nio.ByteBuffer;
21  import java.util.ArrayList;
22  import java.util.BitSet;
23  import java.util.List;
24  
25  
26  /**
27   * Describes which database pages a particular table uses
28   * @author Tim McCune
29   */
30  public class UsageMap
31  {
32    /** Inline map type */
33    public static final byte MAP_TYPE_INLINE = 0x0;
34    /** Reference map type, for maps that are too large to fit inline */
35    public static final byte MAP_TYPE_REFERENCE = 0x1;
36  
37    /** bit index value for an invalid page number */
38    private static final int INVALID_BIT_INDEX = -1;
39    
40    /** owning database */
41    private final DatabaseImpl _database;
42    /** Page number of the map table declaration */
43    private final int _tablePageNum;
44    /** Offset of the data page at which the usage map data starts */
45    private int _startOffset;
46    /** Offset of the data page at which the usage map declaration starts */
47    private final short _rowStart;
48    /** First page that this usage map applies to */
49    private int _startPage;
50    /** Last page that this usage map applies to */
51    private int _endPage;
52    /** bits representing page numbers used, offset from _startPage */
53    private BitSet _pageNumbers = new BitSet();
54    /** Buffer that contains the usage map table declaration page */
55    private final ByteBuffer _tableBuffer;
56    /** modification count on the usage map, used to keep the cursors in
57        sync */
58    private int _modCount;
59    /** the current handler implementation for reading/writing the specific
60        usage map type.  note, this may change over time. */
61    private Handler _handler;
62  
63    /** Error message prefix used when map type is unrecognized. */
64    static final String MSG_PREFIX_UNRECOGNIZED_MAP = "Unrecognized map type: ";
65  
66      /**
67     * @param database database that contains this usage map
68     * @param tableBuffer Buffer that contains this map's declaration
69     * @param pageNum Page number that this usage map is contained in
70     * @param rowStart Offset at which the declaration starts in the buffer
71     */
72    private UsageMap(DatabaseImpl database, ByteBuffer tableBuffer,
73                     int pageNum, short rowStart)
74      throws IOException
75    {
76      _database = database;
77      _tableBuffer = tableBuffer;
78      _tablePageNum = pageNum;
79      _rowStart = rowStart;
80      _tableBuffer.position(_rowStart + getFormat().OFFSET_USAGE_MAP_START);
81      _startOffset = _tableBuffer.position();
82    }
83  
84    public DatabaseImpl getDatabase() {
85      return _database;
86    }
87    
88    public JetFormat getFormat() {
89      return getDatabase().getFormat();
90    }
91  
92    public PageChannel getPageChannel() {
93      return getDatabase().getPageChannel();
94    }
95  
96    /**
97     * @param database database that contains this usage map
98     * @param buf buffer which contains the usage map row info
99     * @return Either an InlineUsageMap or a ReferenceUsageMap, depending on
100    *         which type of map is found
101    */
102   public static UsageMap read(DatabaseImpl database, ByteBuffer buf)
103     throws IOException
104   {
105     int umapRowNum = buf.get();
106     int umapPageNum = ByteUtil.get3ByteInt(buf);
107     return read(database, umapPageNum, umapRowNum, false);
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    * @param isGlobal whether or not we are reading the "global" usage map
115    * @return Either an InlineUsageMap or a ReferenceUsageMap, depending on
116    *         which type of map is found
117    */
118   static UsageMap read(DatabaseImpl database, int pageNum,
119                        int rowNum, boolean isGlobal)
120     throws IOException
121   {
122     if(pageNum <= 0) {
123       // usage maps will never appear on page 0 (or less)
124       throw new IllegalStateException("Invalid usage map page number " + pageNum);
125     }
126 
127     JetFormat format = database.getFormat();
128     PageChannel pageChannel = database.getPageChannel();
129     ByteBuffer tableBuffer = pageChannel.createPageBuffer();
130     pageChannel.readPage(tableBuffer, pageNum);
131     short rowStart = TableImpl.findRowStart(tableBuffer, rowNum, format);
132     int rowEnd = TableImpl.findRowEnd(tableBuffer, rowNum, format);
133     tableBuffer.limit(rowEnd);    
134     byte mapType = tableBuffer.get(rowStart);
135     UsageMap rtn = new UsageMap(database, tableBuffer, pageNum, rowStart);
136     rtn.initHandler(mapType, isGlobal);
137     return rtn;
138   }
139 
140   private void initHandler(byte mapType, boolean isGlobal)
141     throws IOException
142   {
143     if (mapType == MAP_TYPE_INLINE) {
144       _handler = (isGlobal ? new GlobalInlineHandler() : 
145                   new InlineHandler());
146     } else if (mapType == MAP_TYPE_REFERENCE) {
147       _handler = (isGlobal ? new GlobalReferenceHandler() : 
148                   new ReferenceHandler());
149     } else {
150       throw new IOException(MSG_PREFIX_UNRECOGNIZED_MAP + mapType);
151     }
152   }
153   
154   public PageCursor cursor() {
155     return new PageCursor();
156   }
157 
158   public int getPageCount() {
159     return _pageNumbers.cardinality();
160   }
161   
162   protected short getRowStart() {
163     return _rowStart;
164   }
165 
166   protected int getRowEnd() {
167     return getTableBuffer().limit();
168   }
169 
170   protected void setStartOffset(int startOffset) {
171     _startOffset = startOffset;
172   }
173   
174   protected int getStartOffset() {
175     return _startOffset;
176   }
177   
178   protected ByteBuffer getTableBuffer() {
179     return _tableBuffer;
180   }
181   
182   protected int getTablePageNumber() {
183     return _tablePageNum;
184   }
185   
186   protected int getStartPage() {
187     return _startPage;
188   }
189     
190   protected int getEndPage() {
191     return _endPage;
192   }
193     
194   protected BitSet getPageNumbers() {
195     return _pageNumbers;
196   }
197 
198   protected void setPageRange(int newStartPage, int newEndPage) {
199     _startPage = newStartPage;
200     _endPage = newEndPage;
201   }
202 
203   protected boolean isPageWithinRange(int pageNumber)
204   {
205     return((pageNumber >= _startPage) && (pageNumber < _endPage));
206   }
207 
208   protected int getFirstPageNumber() {
209     return bitIndexToPageNumber(getNextBitIndex(-1), 
210                                 RowIdImpl.LAST_PAGE_NUMBER);
211   }
212 
213   protected int getNextPageNumber(int curPage) {
214     return bitIndexToPageNumber(
215         getNextBitIndex(pageNumberToBitIndex(curPage)),
216         RowIdImpl.LAST_PAGE_NUMBER);
217   }    
218   
219   protected int getNextBitIndex(int curIndex) {
220     return _pageNumbers.nextSetBit(curIndex + 1);
221   }    
222   
223   protected int getLastPageNumber() {
224     return bitIndexToPageNumber(getPrevBitIndex(_pageNumbers.length()),
225                                 RowIdImpl.FIRST_PAGE_NUMBER);
226   }
227 
228   protected int getPrevPageNumber(int curPage) {
229     return bitIndexToPageNumber(
230         getPrevBitIndex(pageNumberToBitIndex(curPage)),
231         RowIdImpl.FIRST_PAGE_NUMBER);
232   }    
233   
234   protected int getPrevBitIndex(int curIndex) {
235     --curIndex;
236     while((curIndex >= 0) && !_pageNumbers.get(curIndex)) {
237       --curIndex;
238     }
239     return curIndex;
240   }    
241   
242   protected int bitIndexToPageNumber(int bitIndex,
243                                      int invalidPageNumber) {
244     return((bitIndex >= 0) ? (_startPage + bitIndex) : invalidPageNumber);
245   }
246 
247   protected int pageNumberToBitIndex(int pageNumber) {
248     return((pageNumber >= 0) ? (pageNumber - _startPage) :
249            INVALID_BIT_INDEX);
250   }
251 
252   protected void clearTableAndPages()
253   {
254     // reset some values
255     _pageNumbers.clear();
256     _startPage = 0;
257     _endPage = 0;
258     ++_modCount;
259     
260     // clear out the table data (everything except map type)
261     int tableStart = getRowStart() + 1;
262     int tableEnd = getRowEnd();
263     ByteUtil.clearRange(_tableBuffer, tableStart, tableEnd);
264   }
265   
266   protected void writeTable()
267     throws IOException
268   {
269     // note, we only want to write the row data with which we are working
270     getPageChannel().writePage(_tableBuffer, _tablePageNum, _rowStart);
271   }
272   
273   /**
274    * Read in the page numbers in this inline map
275    */
276   protected void processMap(ByteBuffer buffer, int bufferStartPage)
277   {
278     int byteCount = 0;
279     while (buffer.hasRemaining()) {
280       byte b = buffer.get();
281       if(b != (byte)0) {
282         for (int i = 0; i < 8; i++) {
283           if ((b & (1 << i)) != 0) {
284             int pageNumberOffset = (byteCount * 8 + i) + bufferStartPage;
285             int pageNumber = bitIndexToPageNumber(
286                 pageNumberOffset,
287                 PageChannel.INVALID_PAGE_NUMBER);
288             if(!isPageWithinRange(pageNumber)) {
289               throw new IllegalStateException(
290                   "found page number " + pageNumber
291                   + " in usage map outside of expected range " +
292                   _startPage + " to " + _endPage);
293             }
294             _pageNumbers.set(pageNumberOffset);
295           }
296         }
297       }
298       byteCount++;
299     }
300   }
301 
302   /**
303    * Determines if the given page number is contained in this map.
304    */
305   public boolean containsPageNumber(int pageNumber) {
306     return _handler.containsPageNumber(pageNumber);
307   }
308   
309   /**
310    * Add a page number to this usage map
311    */
312   public void addPageNumber(int pageNumber) throws IOException {
313     ++_modCount;
314     _handler.addOrRemovePageNumber(pageNumber, true, false);
315   }
316   
317   /**
318    * Remove a page number from this usage map
319    */
320   public void removePageNumber(int pageNumber) 
321     throws IOException 
322   {
323     removePageNumber(pageNumber, true);
324   }
325   
326   private void removePageNumber(int pageNumber, boolean force) 
327     throws IOException 
328   {
329     ++_modCount;
330     _handler.addOrRemovePageNumber(pageNumber, false, force);
331   }
332   
333   protected void updateMap(int absolutePageNumber,
334                            int bufferRelativePageNumber,
335                            ByteBuffer buffer, boolean add, boolean force)
336     throws IOException
337   {
338     //Find the byte to which to apply the bitmask and create the bitmask
339     int offset = bufferRelativePageNumber / 8;
340     int bitmask = 1 << (bufferRelativePageNumber % 8);
341     byte b = buffer.get(_startOffset + offset);
342 
343     // check current value for this page number
344     int pageNumberOffset = pageNumberToBitIndex(absolutePageNumber);
345     boolean isOn = _pageNumbers.get(pageNumberOffset);
346     if((isOn == add) && !force) {
347       throw new IOException("Page number " + absolutePageNumber + " already " +
348                             ((add) ? "added to" : "removed from") +
349                             " usage map, expected range " +
350                             _startPage + " to " + _endPage);
351     }
352     
353     //Apply the bitmask
354     if (add) {
355       b |= bitmask;
356       _pageNumbers.set(pageNumberOffset);
357     } else {
358       b &= ~bitmask;
359       _pageNumbers.clear(pageNumberOffset);
360     }
361     buffer.put(_startOffset + offset, b);
362   }
363 
364   /**
365    * Promotes and inline usage map to a reference usage map.
366    */
367   private void promoteInlineHandlerToReferenceHandler(int newPageNumber)
368     throws IOException
369   {
370     // copy current page number info to new references and then clear old
371     int oldStartPage = _startPage;
372     BitSet oldPageNumbers = (BitSet)_pageNumbers.clone();
373 
374     // clear out the main table (inline usage map data and start page)
375     clearTableAndPages();
376     
377     // set the new map type
378     _tableBuffer.put(getRowStart(), MAP_TYPE_REFERENCE);
379 
380     // write the new table data
381     writeTable();
382     
383     // set new handler
384     _handler = new ReferenceHandler();
385 
386     // update new handler with old data
387     reAddPages(oldStartPage, oldPageNumbers, newPageNumber);
388   }
389 
390   private void reAddPages(int oldStartPage, BitSet oldPageNumbers,
391                           int newPageNumber)
392     throws IOException
393   {
394     // add all the old pages back in
395     for(int i = oldPageNumbers.nextSetBit(0); i >= 0;
396         i = oldPageNumbers.nextSetBit(i + 1)) {
397       addPageNumber(oldStartPage + i);
398     }
399 
400     if(newPageNumber > PageChannel.INVALID_PAGE_NUMBER) {
401       // and then add the new page
402       addPageNumber(newPageNumber);
403     }
404   }
405 
406   @Override
407   public String toString() {
408 
409     List<String> ranges = new ArrayList<String>();
410     PageCursor pCursor = cursor();
411     int curRangeStart = Integer.MIN_VALUE;
412     int prevPage = Integer.MIN_VALUE;
413     while(true) {
414       int nextPage = pCursor.getNextPage();
415       if(nextPage < 0) {
416         break;
417       }
418 
419       if(nextPage != (prevPage + 1)) {
420         if(prevPage >= 0) {
421           rangeToString(ranges, curRangeStart, prevPage);
422         }
423         curRangeStart = nextPage;
424       }
425       prevPage = nextPage;
426     }
427     if(prevPage >= 0) {
428       rangeToString(ranges, curRangeStart, prevPage);
429     }
430 
431     return CustomToStringStyle.valueBuilder(
432         _handler.getClass().getSimpleName())
433       .append("range", "(" + _startPage + "-" + _endPage + ")")
434       .append("pageNumbers", ranges)
435       .toString();
436   }
437 
438   private static void rangeToString(List<String> ranges, int rangeStart,
439                                     int rangeEnd)
440   {
441     if(rangeEnd > rangeStart) {
442       ranges.add(rangeStart + "-" + rangeEnd);
443     } else {
444       ranges.add(String.valueOf(rangeStart));
445     }
446   }
447   
448   private abstract class Handler
449   {
450     protected Handler() {
451     }
452 
453     public boolean containsPageNumber(int pageNumber) {
454       return(isPageWithinRange(pageNumber) &&
455              getPageNumbers().get(pageNumberToBitIndex(pageNumber)));
456     }
457     
458     /**
459      * @param pageNumber Page number to add or remove from this map
460      * @param add True to add it, false to remove it
461      * @param force true to force add/remove and ignore certain inconsistencies
462      */
463     public abstract void addOrRemovePageNumber(int pageNumber, boolean add,
464                                                boolean force)
465       throws IOException;
466   }
467 
468   /**
469    * Usage map whose map is written inline in the same page.  For Jet4, this
470    * type of map can usually contains a maximum of 512 pages.  Free space maps
471    * are always inline, used space maps may be inline or reference.  It has a
472    * start page, which all page numbers in its map are calculated as starting
473    * from.
474    * @author Tim McCune
475    */
476   private class InlineHandler extends Handler
477   {
478     private final int _maxInlinePages;
479     
480     protected InlineHandler() throws IOException
481     {
482       _maxInlinePages = (getInlineDataEnd() - getInlineDataStart()) * 8;
483       int startPage = getTableBuffer().getInt(getRowStart() + 1);
484       setInlinePageRange(startPage);
485       processMap(getTableBuffer(), 0);
486     }
487 
488     protected final int getMaxInlinePages() {
489       return _maxInlinePages;
490     }
491 
492     protected final int getInlineDataStart() {
493       return getRowStart() + getFormat().OFFSET_USAGE_MAP_START;
494     }
495 
496     protected final int getInlineDataEnd() {
497       return getRowEnd();
498     }
499     
500     /**
501      * Sets the page range for an inline usage map starting from the given
502      * page.
503      */
504     private void setInlinePageRange(int startPage) {
505       setPageRange(startPage, startPage + getMaxInlinePages());
506     }      
507     
508     @Override
509     public void addOrRemovePageNumber(int pageNumber, boolean add,
510                                       boolean force)
511       throws IOException
512     {
513       if(isPageWithinRange(pageNumber)) {
514 
515         // easy enough, just update the inline data
516         int bufferRelativePageNumber = pageNumberToBitIndex(pageNumber);
517         updateMap(pageNumber, bufferRelativePageNumber, getTableBuffer(), add,
518                   force);
519         // Write the updated map back to disk
520         writeTable();
521         
522       } else {
523 
524         // uh-oh, we've split our britches.  what now?
525         addOrRemovePageNumberOutsideRange(pageNumber, add, force);
526       }
527     }
528 
529     protected void addOrRemovePageNumberOutsideRange(
530         int pageNumber, boolean add, boolean force)
531       throws IOException
532     {
533       // determine what our status is before taking action
534         
535       if(add) {
536 
537         int firstPage = getFirstPageNumber();
538         int lastPage = getLastPageNumber();
539 
540         // we are adding, can we shift the bits and stay inline?
541         if(firstPage <= PageChannel.INVALID_PAGE_NUMBER) {
542           // no pages currently
543           firstPage = pageNumber;
544           lastPage = pageNumber;
545         } else if(pageNumber > lastPage) {
546           lastPage = pageNumber;
547         } else {
548           firstPage = pageNumber;
549         }
550         if((lastPage - firstPage + 1) < getMaxInlinePages()) {
551 
552           // we can still fit within an inline map
553           moveToNewStartPage(firstPage, pageNumber);
554             
555         } else {
556           // not going to happen, need to promote the usage map to a
557           // reference map
558           promoteInlineHandlerToReferenceHandler(pageNumber);
559         }
560 
561       } else {
562 
563         // we are removing, what does that mean?
564         if(!force) {
565 
566           // this should not happen, we are removing a page which is not in
567           // the map
568           throw new IOException("Page number " + pageNumber +
569                                 " already removed from usage map" +
570                                 ", expected range " +
571                                 _startPage + " to " + _endPage);
572         }
573       }
574     }
575 
576     /**
577      * Shifts the inline usage map so that it now starts with the given page.
578      * @param newStartPage new page at which to start
579      * @param newPageNumber optional page number to add once the map has been
580      *                      shifted to the new start page
581      */
582     protected final void moveToNewStartPage(int newStartPage, int newPageNumber)
583       throws IOException
584     {
585       int oldStartPage = getStartPage();
586       BitSet oldPageNumbers = (BitSet)getPageNumbers().clone();
587 
588       // clear out the main table (inline usage map data and start page)
589       clearTableAndPages();
590 
591       // write new start page
592       ByteBuffer tableBuffer = getTableBuffer();
593       tableBuffer.position(getRowStart() + 1);
594       tableBuffer.putInt(newStartPage);
595 
596       // write the new table data
597       writeTable();
598 
599       // set new page range
600       setInlinePageRange(newStartPage);
601 
602       // put the pages back in
603       reAddPages(oldStartPage, oldPageNumbers, newPageNumber);
604     }
605   }
606 
607   /**
608    * Modified version of an "inline" usage map used for the global usage map.
609    * When an inline usage map is used for the global usage map, we assume
610    * out-of-range bits are on.  We never promote the global usage map to a
611    * reference usage map (although ms access may).
612    *
613    * Note, this UsageMap does not implement all the methods "correctly".  Only
614    * addPageNumber and removePageNumber should be called by PageChannel.
615    */
616   private class GlobalInlineHandler extends InlineHandler
617   {
618     private GlobalInlineHandler() throws IOException {
619     }
620 
621     @Override
622     public boolean containsPageNumber(int pageNumber) {
623       // should never be called on global map
624       throw new UnsupportedOperationException();
625     }
626 
627     @Override
628     protected void addOrRemovePageNumberOutsideRange(
629         int pageNumber, boolean add, boolean force)
630       throws IOException
631     {
632       // determine what our status is
633 
634       // for the global usage map, we can ignore out-of-range page addition
635       // since we assuming out-of-range bits are "on".  Note, we are leaving
636       // small holes in the database here (leaving behind some free pages),
637       // but it's not the end of the world.
638         
639       if(!add) {
640 
641         int firstPage = getFirstPageNumber();
642         int lastPage = getLastPageNumber();
643 
644         // we are using an inline map and assuming that anything not
645         // within the current range is "on".  so, if we attempt to set a
646         // bit which is before the current page, ignore it, we are not
647         // going back for it.
648         if((firstPage <= PageChannel.INVALID_PAGE_NUMBER) ||
649            (pageNumber > lastPage)) {
650 
651           // move to new start page, filling in as we move
652           moveToNewStartPageForRemove(firstPage, pageNumber);
653         }
654       }
655     }
656 
657     /**
658      * Shifts the inline usage map so that it now starts with the given
659      * firstPage (if valid), otherwise the newPageNumber.  Any page numbers
660      * added to the end of the usage map are set to "on".
661      * @param firstPage current first used page
662      * @param newPageNumber page number to remove once the map has been
663      *                      shifted to the new start page
664      */
665     private void moveToNewStartPageForRemove(int firstPage, int newPageNumber)
666       throws IOException
667     {
668       int oldEndPage = getEndPage();
669       int newStartPage = 
670         ((firstPage <= PageChannel.INVALID_PAGE_NUMBER) ? newPageNumber :
671          // just shift a little and discard any initial unused pages.
672          (newPageNumber - (getMaxInlinePages() / 2)));
673 
674       // move the current data
675       moveToNewStartPage(newStartPage, PageChannel.INVALID_PAGE_NUMBER);
676 
677       if(firstPage <= PageChannel.INVALID_PAGE_NUMBER) {
678 
679         // this is the common case where we left everything behind
680         ByteUtil.fillRange(_tableBuffer, getInlineDataStart(),
681                            getInlineDataEnd());
682 
683         // write out the updated table
684         writeTable();
685 
686         // "add" all the page numbers
687         getPageNumbers().set(0, getMaxInlinePages());
688 
689       } else {
690 
691         // add every new page manually
692         for(int i = oldEndPage; i < getEndPage(); ++i) {
693           addPageNumber(i);
694         }
695       }
696 
697       // lastly, remove the new page
698       removePageNumber(newPageNumber, false);
699     }
700   }
701 
702   /**
703    * Usage map whose map is written across one or more entire separate pages
704    * of page type USAGE_MAP.  For Jet4, this type of map can contain 32736
705    * pages per reference page, and a maximum of 17 reference map pages for a
706    * total maximum of 556512 pages (2 GB).
707    * @author Tim McCune
708    */
709   private class ReferenceHandler extends Handler
710   {
711     /** Buffer that contains the current reference map page */ 
712     private final TempPageHolder _mapPageHolder =
713       TempPageHolder.newHolder(TempBufferHolder.Type.SOFT);
714     private final int _maxPagesPerUsageMapPage;
715   
716     private ReferenceHandler() throws IOException
717     {
718       _maxPagesPerUsageMapPage = ((getFormat().PAGE_SIZE - 
719                                    getFormat().OFFSET_USAGE_MAP_PAGE_DATA) * 8);
720       int numUsagePages = (getRowEnd() - getRowStart() - 1) / 4;
721       setStartOffset(getFormat().OFFSET_USAGE_MAP_PAGE_DATA);
722       setPageRange(0, (numUsagePages * _maxPagesPerUsageMapPage));
723       
724       // there is no "start page" for a reference usage map, so we get an
725       // extra page reference on top of the number of page references that fit
726       // in the table
727       for (int i = 0; i < numUsagePages; i++) {
728         int mapPageNum = getTableBuffer().getInt(
729             calculateMapPagePointerOffset(i));
730         if (mapPageNum > 0) {
731           ByteBuffer mapPageBuffer =
732             _mapPageHolder.setPage(getPageChannel(), mapPageNum);
733           byte pageType = mapPageBuffer.get();
734           if (pageType != PageTypes.USAGE_MAP) {
735             throw new IOException("Looking for usage map at page " +
736                                   mapPageNum + ", but page type is " +
737                                   pageType);
738           }
739           mapPageBuffer.position(getFormat().OFFSET_USAGE_MAP_PAGE_DATA);
740           processMap(mapPageBuffer, (_maxPagesPerUsageMapPage * i));
741         }
742       }
743     }
744 
745     protected final int getMaxPagesPerUsagePage() {
746       return _maxPagesPerUsageMapPage;
747     }
748         
749     @Override
750     public void addOrRemovePageNumber(int pageNumber, boolean add,
751                                       boolean force)
752       throws IOException
753     {
754       if(!isPageWithinRange(pageNumber)) {
755         if(force) {
756           return;
757         }
758         throw new IOException("Page number " + pageNumber +
759                               " is out of supported range");
760       }
761       int pageIndex = (pageNumber / getMaxPagesPerUsagePage());
762       int mapPageNum = getTableBuffer().getInt(
763           calculateMapPagePointerOffset(pageIndex));
764       ByteBuffer mapPageBuffer = null;
765       if(mapPageNum > 0) {
766         mapPageBuffer = _mapPageHolder.setPage(getPageChannel(), mapPageNum);
767       } else {
768         // Need to create a new usage map page
769         mapPageBuffer = createNewUsageMapPage(pageIndex);
770         mapPageNum = _mapPageHolder.getPageNumber();
771       }
772       updateMap(pageNumber,
773                 (pageNumber - (getMaxPagesPerUsagePage() * pageIndex)),
774                 mapPageBuffer, add, force);
775       getPageChannel().writePage(mapPageBuffer, mapPageNum);
776     }
777   
778     /**
779      * Create a new usage map page and update the map declaration with a
780      * pointer to it.
781      * @param pageIndex Index of the page reference within the map declaration 
782      */
783     private ByteBuffer createNewUsageMapPage(int pageIndex) throws IOException
784     {
785       ByteBuffer mapPageBuffer = allocateNewUsageMapPage(pageIndex);
786       int mapPageNum = _mapPageHolder.getPageNumber();
787       getTableBuffer().putInt(calculateMapPagePointerOffset(pageIndex),
788                               mapPageNum);
789       writeTable();
790       return mapPageBuffer;
791     }
792   
793     private int calculateMapPagePointerOffset(int pageIndex) {
794       return getRowStart() + getFormat().OFFSET_REFERENCE_MAP_PAGE_NUMBERS +
795         (pageIndex * 4);
796     }
797 
798     protected ByteBuffer allocateNewUsageMapPage(int pageIndex) 
799       throws IOException 
800     {
801       ByteBuffer mapPageBuffer = _mapPageHolder.setNewPage(getPageChannel());
802       mapPageBuffer.put(PageTypes.USAGE_MAP);
803       mapPageBuffer.put((byte) 0x01);  //Unknown
804       mapPageBuffer.putShort((short) 0); //Unknown
805       return mapPageBuffer;
806     }
807   }
808 
809   /**
810    * Modified version of a "reference" usage map used for the global usage
811    * map.  Since reference usage maps require allocating pages for their own
812    * use, we need to handle potential cycles where the PageChannel is
813    * attempting to allocate a new page (and remove it from the global usage
814    * map) and this usage map also needs to allocate a new page.  When that
815    * happens, we stash the pending information from the PageChannel and handle
816    * it after we have retrieved the new page.
817    *
818    * Note, this UsageMap does not implement all the methods "correctly".  Only
819    * addPageNumber and removePageNumber should be called by PageChannel.
820    */
821   private class GlobalReferenceHandler extends ReferenceHandler
822   {
823     private boolean _allocatingPage;
824     private Integer _pendingPage;
825 
826     private GlobalReferenceHandler() throws IOException {
827     }
828 
829     @Override
830     public boolean containsPageNumber(int pageNumber) {
831       // should never be called on global map
832       throw new UnsupportedOperationException();
833     }
834 
835     @Override
836     public void addOrRemovePageNumber(int pageNumber, boolean add,
837                                       boolean force)
838       throws IOException
839     {
840       if(_allocatingPage && !add) {
841         // we are in the midst of allocating a page for ourself, keep track of
842         // this new page so we can mark it later...
843         if(_pendingPage != null) {
844           throw new IllegalStateException("should only have single pending page");
845         }
846         _pendingPage = pageNumber;
847         return;
848       }
849 
850       super.addOrRemovePageNumber(pageNumber, add, force);
851 
852       while(_pendingPage != null) {
853         
854         // while updating our usage map, we needed to allocate a new page (and
855         // thus mark a new page as used).  we delayed that marking so that we
856         // didn't get into an infinite loop.  now that we completed the
857         // original updated, handle the new page.  (we use a loop under the
858         // off the wall chance that adding this page requires allocating a new
859         // page.  in theory, we could do this more than once, but not
860         // forever).
861         int removedPageNumber = _pendingPage;
862         _pendingPage = null;
863 
864         super.addOrRemovePageNumber(removedPageNumber, false, true);
865       } 
866     }    
867 
868     @Override
869     protected ByteBuffer allocateNewUsageMapPage(int pageIndex)
870       throws IOException 
871     {
872       try {
873         // keep track of the fact that we are actively allocating a page for our
874         // own use so that we can break the potential cycle.
875         _allocatingPage = true;
876 
877         ByteBuffer mapPageBuffer = super.allocateNewUsageMapPage(pageIndex);
878 
879         // for the global usage map, all pages are "on" by default.  so
880         // whenever we add a new backing page to the usage map, we need to
881         // turn all the pages that it represents to "on" (we essentially lazy
882         // load this map, which is fine because we should only add pages which
883         // represent the size of the database currently in use).
884         int dataStart = getFormat().OFFSET_USAGE_MAP_PAGE_DATA;
885         ByteUtil.fillRange(mapPageBuffer, dataStart, 
886                            getFormat().PAGE_SIZE - dataStart);
887 
888         int maxPagesPerUmapPage = getMaxPagesPerUsagePage();
889         int firstNewPage = (pageIndex * maxPagesPerUmapPage);
890         int lastNewPage = firstNewPage + maxPagesPerUmapPage;
891         _pageNumbers.set(firstNewPage, lastNewPage);
892 
893         return mapPageBuffer;
894 
895       } finally {
896         _allocatingPage = false;
897       }
898     }
899   }
900 
901   /**
902    * Utility class to traverse over the pages in the UsageMap.  Remains valid
903    * in the face of usage map modifications.
904    */
905   public final class PageCursor
906   {
907     /** handler for moving the page cursor forward */
908     private final DirHandler _forwardDirHandler = new ForwardDirHandler();
909     /** handler for moving the page cursor backward */
910     private final DirHandler _reverseDirHandler = new ReverseDirHandler();
911     /** the current used page number */
912     private int _curPageNumber;
913     /** the previous used page number */
914     private int _prevPageNumber;
915     /** the last read modification count on the UsageMap.  we track this so
916         that the cursor can detect updates to the usage map while traversing
917         and act accordingly */
918     private int _lastModCount;
919 
920     private PageCursor() {
921       reset();
922     }
923 
924     public UsageMap getUsageMap() {
925       return UsageMap.this;
926     }
927     
928     /**
929      * Returns the DirHandler for the given direction
930      */
931     private DirHandler getDirHandler(boolean moveForward) {
932       return (moveForward ? _forwardDirHandler : _reverseDirHandler);
933     }
934 
935     /**
936      * Returns {@code true} if this cursor is up-to-date with respect to its
937      * usage map.
938      */
939     public boolean isUpToDate() {
940       return(UsageMap.this._modCount == _lastModCount);
941     }    
942 
943     /**
944      * @return valid page number if there was another page to read,
945      *         {@link RowIdImpl#LAST_PAGE_NUMBER} otherwise
946      */
947     public int getNextPage() {
948       return getAnotherPage(CursorImpl.MOVE_FORWARD);
949     }
950 
951     /**
952      * @return valid page number if there was another page to read,
953      *         {@link RowIdImpl#FIRST_PAGE_NUMBER} otherwise
954      */
955     public int getPreviousPage() {
956       return getAnotherPage(CursorImpl.MOVE_REVERSE);
957     }
958 
959     /**
960      * Gets another page in the given direction, returning the new page.
961      */
962     private int getAnotherPage(boolean moveForward) {
963       DirHandler handler = getDirHandler(moveForward);
964       if(_curPageNumber == handler.getEndPageNumber()) {
965         if(!isUpToDate()) {
966           restorePosition(_prevPageNumber);
967           // drop through and retry moving to another page
968         } else {
969           // at end, no more
970           return _curPageNumber;
971         }
972       }
973 
974       checkForModification();
975       
976       _prevPageNumber = _curPageNumber;
977       _curPageNumber = handler.getAnotherPageNumber(_curPageNumber);
978       return _curPageNumber;
979     }
980 
981     /**
982      * After calling this method, getNextPage will return the first page in
983      * the map
984      */
985     public void reset() {
986       beforeFirst();
987     }
988 
989     /**
990      * After calling this method, {@link #getNextPage} will return the first
991      * page in the map
992      */
993     public void beforeFirst() {
994       reset(CursorImpl.MOVE_FORWARD);
995     }
996 
997     /**
998      * After calling this method, {@link #getPreviousPage} will return the
999      * last page in the map
1000      */
1001     public void afterLast() {
1002       reset(CursorImpl.MOVE_REVERSE);
1003     }
1004 
1005     /**
1006      * Resets this page cursor for traversing the given direction.
1007      */
1008     protected void reset(boolean moveForward) {
1009       _curPageNumber = getDirHandler(moveForward).getBeginningPageNumber();
1010       _prevPageNumber = _curPageNumber;
1011       _lastModCount = UsageMap.this._modCount;
1012     }
1013 
1014     /**
1015      * Restores a current position for the cursor (current position becomes
1016      * previous position).
1017      */
1018     private void restorePosition(int curPageNumber)
1019     {
1020       restorePosition(curPageNumber, _curPageNumber);
1021     }
1022     
1023     /**
1024      * Restores a current and previous position for the cursor.
1025      */
1026     protected void restorePosition(int curPageNumber, int prevPageNumber)
1027     {
1028       if((curPageNumber != _curPageNumber) ||
1029          (prevPageNumber != _prevPageNumber))
1030       {
1031         _prevPageNumber = updatePosition(prevPageNumber);
1032         _curPageNumber = updatePosition(curPageNumber);
1033         _lastModCount = UsageMap.this._modCount;
1034       } else {
1035         checkForModification();
1036       }
1037     }
1038 
1039     /**
1040      * Checks the usage map for modifications an updates state accordingly.
1041      */
1042     private void checkForModification() {
1043       if(!isUpToDate()) {
1044         _prevPageNumber = updatePosition(_prevPageNumber);
1045         _curPageNumber = updatePosition(_curPageNumber);
1046         _lastModCount = UsageMap.this._modCount;
1047       }
1048     }
1049 
1050     private int updatePosition(int pageNumber) {
1051       if(pageNumber < UsageMap.this.getFirstPageNumber()) {
1052         pageNumber = RowIdImpl.FIRST_PAGE_NUMBER;
1053       } else if(pageNumber > UsageMap.this.getLastPageNumber()) {
1054         pageNumber = RowIdImpl.LAST_PAGE_NUMBER;
1055       }
1056       return pageNumber;
1057     }
1058     
1059     @Override
1060     public String toString() {
1061       return getClass().getSimpleName() + " CurPosition " + _curPageNumber +
1062         ", PrevPosition " + _prevPageNumber;
1063     }
1064     
1065     
1066     /**
1067      * Handles moving the cursor in a given direction.  Separates cursor
1068      * logic from value storage.
1069      */
1070     private abstract class DirHandler {
1071       public abstract int getAnotherPageNumber(int curPageNumber);
1072       public abstract int getBeginningPageNumber();
1073       public abstract int getEndPageNumber();
1074     }
1075         
1076     /**
1077      * Handles moving the cursor forward.
1078      */
1079     private final class ForwardDirHandler extends DirHandler {
1080       @Override
1081       public int getAnotherPageNumber(int curPageNumber) {
1082         if(curPageNumber == getBeginningPageNumber()) {
1083           return UsageMap.this.getFirstPageNumber();
1084         }
1085         return UsageMap.this.getNextPageNumber(curPageNumber);
1086       }
1087       @Override
1088       public int getBeginningPageNumber() {
1089         return RowIdImpl.FIRST_PAGE_NUMBER;
1090       }
1091       @Override
1092       public int getEndPageNumber() {
1093         return RowIdImpl.LAST_PAGE_NUMBER;
1094       }
1095     }
1096         
1097     /**
1098      * Handles moving the cursor backward.
1099      */
1100     private final class ReverseDirHandler extends DirHandler {
1101       @Override
1102       public int getAnotherPageNumber(int curPageNumber) {
1103         if(curPageNumber == getBeginningPageNumber()) {
1104           return UsageMap.this.getLastPageNumber();
1105         }
1106         return UsageMap.this.getPrevPageNumber(curPageNumber);
1107       }
1108       @Override
1109       public int getBeginningPageNumber() {
1110         return RowIdImpl.LAST_PAGE_NUMBER;
1111       }
1112       @Override
1113       public int getEndPageNumber() {
1114         return RowIdImpl.FIRST_PAGE_NUMBER;
1115       }
1116     }
1117         
1118   }  
1119   
1120 }