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     UsageMapkcess/impl/UsageMap.html#UsageMap">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 static int toValidStartPage(int startPage) {
449     // start page must be a multiple of 8
450     return ((startPage / 8) * 8);
451   }
452 
453   private abstract class Handler
454   {
455     protected Handler() {
456     }
457 
458     public boolean containsPageNumber(int pageNumber) {
459       return(isPageWithinRange(pageNumber) &&
460              getPageNumbers().get(pageNumberToBitIndex(pageNumber)));
461     }
462 
463     /**
464      * @param pageNumber Page number to add or remove from this map
465      * @param add True to add it, false to remove it
466      * @param force true to force add/remove and ignore certain inconsistencies
467      */
468     public abstract void addOrRemovePageNumber(int pageNumber, boolean add,
469                                                boolean force)
470       throws IOException;
471   }
472 
473   /**
474    * Usage map whose map is written inline in the same page.  For Jet4, this
475    * type of map can usually contains a maximum of 512 pages.  Free space maps
476    * are always inline, used space maps may be inline or reference.  It has a
477    * start page, which all page numbers in its map are calculated as starting
478    * from.
479    * @author Tim McCune
480    */
481   private class InlineHandler extends Handler
482   {
483     private final int _maxInlinePages;
484 
485     protected InlineHandler() throws IOException
486     {
487       _maxInlinePages = (getInlineDataEnd() - getInlineDataStart()) * 8;
488       int startPage = getTableBuffer().getInt(getRowStart() + 1);
489       setInlinePageRange(startPage);
490       processMap(getTableBuffer(), 0);
491     }
492 
493     protected final int getMaxInlinePages() {
494       return _maxInlinePages;
495     }
496 
497     protected final int getInlineDataStart() {
498       return getRowStart() + getFormat().OFFSET_USAGE_MAP_START;
499     }
500 
501     protected final int getInlineDataEnd() {
502       return getRowEnd();
503     }
504 
505     /**
506      * Sets the page range for an inline usage map starting from the given
507      * page.
508      */
509     private void setInlinePageRange(int startPage) {
510       setPageRange(startPage, startPage + getMaxInlinePages());
511     }
512 
513     @Override
514     public void addOrRemovePageNumber(int pageNumber, boolean add,
515                                       boolean force)
516       throws IOException
517     {
518       if(isPageWithinRange(pageNumber)) {
519 
520         // easy enough, just update the inline data
521         int bufferRelativePageNumber = pageNumberToBitIndex(pageNumber);
522         updateMap(pageNumber, bufferRelativePageNumber, getTableBuffer(), add,
523                   force);
524         // Write the updated map back to disk
525         writeTable();
526 
527       } else {
528 
529         // uh-oh, we've split our britches.  what now?
530         addOrRemovePageNumberOutsideRange(pageNumber, add, force);
531       }
532     }
533 
534     protected void addOrRemovePageNumberOutsideRange(
535         int pageNumber, boolean add, boolean force)
536       throws IOException
537     {
538       // determine what our status is before taking action
539 
540       if(add) {
541 
542         int firstPage = getFirstPageNumber();
543         int lastPage = getLastPageNumber();
544 
545         // we are adding, can we shift the bits and stay inline?
546         if(firstPage <= PageChannel.INVALID_PAGE_NUMBER) {
547           // no pages currently
548           firstPage = pageNumber;
549           lastPage = pageNumber;
550         } else if(pageNumber > lastPage) {
551           lastPage = pageNumber;
552         } else {
553           firstPage = pageNumber;
554         }
555 
556         firstPage = toValidStartPage(firstPage);
557 
558         if((lastPage - firstPage + 1) < getMaxInlinePages()) {
559 
560           // we can still fit within an inline map
561           moveToNewStartPage(firstPage, pageNumber);
562 
563         } else {
564           // not going to happen, need to promote the usage map to a
565           // reference map
566           promoteInlineHandlerToReferenceHandler(pageNumber);
567         }
568 
569       } else {
570 
571         // we are removing, what does that mean?
572         if(!force) {
573 
574           // this should not happen, we are removing a page which is not in
575           // the map
576           throw new IOException("Page number " + pageNumber +
577                                 " already removed from usage map" +
578                                 ", expected range " +
579                                 _startPage + " to " + _endPage);
580         }
581       }
582     }
583 
584     /**
585      * Shifts the inline usage map so that it now starts with the given page.
586      * @param newStartPage new page at which to start
587      * @param newPageNumber optional page number to add once the map has been
588      *                      shifted to the new start page
589      */
590     protected final void moveToNewStartPage(int newStartPage, int newPageNumber)
591       throws IOException
592     {
593       int oldStartPage = getStartPage();
594       BitSet oldPageNumbers = (BitSet)getPageNumbers().clone();
595 
596       // clear out the main table (inline usage map data and start page)
597       clearTableAndPages();
598 
599       // write new start page
600       ByteBuffer tableBuffer = getTableBuffer();
601       tableBuffer.position(getRowStart() + 1);
602       tableBuffer.putInt(newStartPage);
603 
604       // write the new table data
605       writeTable();
606 
607       // set new page range
608       setInlinePageRange(newStartPage);
609 
610       // put the pages back in
611       reAddPages(oldStartPage, oldPageNumbers, newPageNumber);
612     }
613   }
614 
615   /**
616    * Modified version of an "inline" usage map used for the global usage map.
617    * When an inline usage map is used for the global usage map, we assume
618    * out-of-range bits are on.  We never promote the global usage map to a
619    * reference usage map (although ms access may).
620    *
621    * Note, this UsageMap does not implement all the methods "correctly".  Only
622    * addPageNumber and removePageNumber should be called by PageChannel.
623    */
624   private class GlobalInlineHandler extends InlineHandler
625   {
626     private GlobalInlineHandler() throws IOException {
627     }
628 
629     @Override
630     public boolean containsPageNumber(int pageNumber) {
631       // should never be called on global map
632       throw new UnsupportedOperationException();
633     }
634 
635     @Override
636     protected void addOrRemovePageNumberOutsideRange(
637         int pageNumber, boolean add, boolean force)
638       throws IOException
639     {
640       // determine what our status is
641 
642       // for the global usage map, we can ignore out-of-range page addition
643       // since we assuming out-of-range bits are "on".  Note, we are leaving
644       // small holes in the database here (leaving behind some free pages),
645       // but it's not the end of the world.
646 
647       if(!add) {
648 
649         int firstPage = getFirstPageNumber();
650         int lastPage = getLastPageNumber();
651 
652         // we are using an inline map and assuming that anything not
653         // within the current range is "on".  so, if we attempt to set a
654         // bit which is before the current page, ignore it, we are not
655         // going back for it.
656         if((firstPage <= PageChannel.INVALID_PAGE_NUMBER) ||
657            (pageNumber > lastPage)) {
658 
659           // move to new start page, filling in as we move
660           moveToNewStartPageForRemove(firstPage, pageNumber);
661         }
662       }
663     }
664 
665     /**
666      * Shifts the inline usage map so that it now starts with the given
667      * firstPage (if valid), otherwise the newPageNumber.  Any page numbers
668      * added to the end of the usage map are set to "on".
669      * @param firstPage current first used page
670      * @param newPageNumber page number to remove once the map has been
671      *                      shifted to the new start page
672      */
673     private void moveToNewStartPageForRemove(int firstPage, int newPageNumber)
674       throws IOException
675     {
676       int oldEndPage = getEndPage();
677       int newStartPage =
678         toValidStartPage(
679             ((firstPage <= PageChannel.INVALID_PAGE_NUMBER) ? newPageNumber :
680              // just shift a little and discard any initial unused pages.
681              (newPageNumber - (getMaxInlinePages() / 2))));
682 
683       // move the current data
684       moveToNewStartPage(newStartPage, PageChannel.INVALID_PAGE_NUMBER);
685 
686       if(firstPage <= PageChannel.INVALID_PAGE_NUMBER) {
687 
688         // this is the common case where we left everything behind
689         ByteUtil.fillRange(_tableBuffer, getInlineDataStart(),
690                            getInlineDataEnd());
691 
692         // write out the updated table
693         writeTable();
694 
695         // "add" all the page numbers
696         getPageNumbers().set(0, getMaxInlinePages());
697 
698       } else {
699 
700         // add every new page manually
701         for(int i = oldEndPage; i < getEndPage(); ++i) {
702           addPageNumber(i);
703         }
704       }
705 
706       // lastly, remove the new page
707       removePageNumber(newPageNumber, false);
708     }
709   }
710 
711   /**
712    * Usage map whose map is written across one or more entire separate pages
713    * of page type USAGE_MAP.  For Jet4, this type of map can contain 32736
714    * pages per reference page, and a maximum of 17 reference map pages for a
715    * total maximum of 556512 pages (2 GB).
716    * @author Tim McCune
717    */
718   private class ReferenceHandler extends Handler
719   {
720     /** Buffer that contains the current reference map page */
721     private final TempPageHolder _mapPageHolder =
722       TempPageHolder.newHolder(TempBufferHolder.Type.SOFT);
723     private final int _maxPagesPerUsageMapPage;
724 
725     private ReferenceHandler() throws IOException
726     {
727       _maxPagesPerUsageMapPage = ((getFormat().PAGE_SIZE -
728                                    getFormat().OFFSET_USAGE_MAP_PAGE_DATA) * 8);
729       int numUsagePages = (getRowEnd() - getRowStart() - 1) / 4;
730       setStartOffset(getFormat().OFFSET_USAGE_MAP_PAGE_DATA);
731       setPageRange(0, (numUsagePages * _maxPagesPerUsageMapPage));
732 
733       // there is no "start page" for a reference usage map, so we get an
734       // extra page reference on top of the number of page references that fit
735       // in the table
736       for (int i = 0; i < numUsagePages; i++) {
737         int mapPageNum = getTableBuffer().getInt(
738             calculateMapPagePointerOffset(i));
739         if (mapPageNum > 0) {
740           ByteBuffer mapPageBuffer =
741             _mapPageHolder.setPage(getPageChannel(), mapPageNum);
742           byte pageType = mapPageBuffer.get();
743           if (pageType != PageTypes.USAGE_MAP) {
744             throw new IOException("Looking for usage map at page " +
745                                   mapPageNum + ", but page type is " +
746                                   pageType);
747           }
748           mapPageBuffer.position(getFormat().OFFSET_USAGE_MAP_PAGE_DATA);
749           processMap(mapPageBuffer, (_maxPagesPerUsageMapPage * i));
750         }
751       }
752     }
753 
754     protected final int getMaxPagesPerUsagePage() {
755       return _maxPagesPerUsageMapPage;
756     }
757 
758     @Override
759     public void addOrRemovePageNumber(int pageNumber, boolean add,
760                                       boolean force)
761       throws IOException
762     {
763       if(!isPageWithinRange(pageNumber)) {
764         if(force) {
765           return;
766         }
767         throw new IOException("Page number " + pageNumber +
768                               " is out of supported range");
769       }
770       int pageIndex = (pageNumber / getMaxPagesPerUsagePage());
771       int mapPageNum = getTableBuffer().getInt(
772           calculateMapPagePointerOffset(pageIndex));
773       ByteBuffer mapPageBuffer = null;
774       if(mapPageNum > 0) {
775         mapPageBuffer = _mapPageHolder.setPage(getPageChannel(), mapPageNum);
776       } else {
777         // Need to create a new usage map page
778         mapPageBuffer = createNewUsageMapPage(pageIndex);
779         mapPageNum = _mapPageHolder.getPageNumber();
780       }
781       updateMap(pageNumber,
782                 (pageNumber - (getMaxPagesPerUsagePage() * pageIndex)),
783                 mapPageBuffer, add, force);
784       getPageChannel().writePage(mapPageBuffer, mapPageNum);
785     }
786 
787     /**
788      * Create a new usage map page and update the map declaration with a
789      * pointer to it.
790      * @param pageIndex Index of the page reference within the map declaration
791      */
792     private ByteBuffer createNewUsageMapPage(int pageIndex) throws IOException
793     {
794       ByteBuffer mapPageBuffer = allocateNewUsageMapPage(pageIndex);
795       int mapPageNum = _mapPageHolder.getPageNumber();
796       getTableBuffer().putInt(calculateMapPagePointerOffset(pageIndex),
797                               mapPageNum);
798       writeTable();
799       return mapPageBuffer;
800     }
801 
802     private int calculateMapPagePointerOffset(int pageIndex) {
803       return getRowStart() + getFormat().OFFSET_REFERENCE_MAP_PAGE_NUMBERS +
804         (pageIndex * 4);
805     }
806 
807     protected ByteBuffer allocateNewUsageMapPage(int pageIndex)
808       throws IOException
809     {
810       ByteBuffer mapPageBuffer = _mapPageHolder.setNewPage(getPageChannel());
811       mapPageBuffer.put(PageTypes.USAGE_MAP);
812       mapPageBuffer.put((byte) 0x01);  //Unknown
813       mapPageBuffer.putShort((short) 0); //Unknown
814       return mapPageBuffer;
815     }
816   }
817 
818   /**
819    * Modified version of a "reference" usage map used for the global usage
820    * map.  Since reference usage maps require allocating pages for their own
821    * use, we need to handle potential cycles where the PageChannel is
822    * attempting to allocate a new page (and remove it from the global usage
823    * map) and this usage map also needs to allocate a new page.  When that
824    * happens, we stash the pending information from the PageChannel and handle
825    * it after we have retrieved the new page.
826    *
827    * Note, this UsageMap does not implement all the methods "correctly".  Only
828    * addPageNumber and removePageNumber should be called by PageChannel.
829    */
830   private class GlobalReferenceHandler extends ReferenceHandler
831   {
832     private boolean _allocatingPage;
833     private Integer _pendingPage;
834 
835     private GlobalReferenceHandler() throws IOException {
836     }
837 
838     @Override
839     public boolean containsPageNumber(int pageNumber) {
840       // should never be called on global map
841       throw new UnsupportedOperationException();
842     }
843 
844     @Override
845     public void addOrRemovePageNumber(int pageNumber, boolean add,
846                                       boolean force)
847       throws IOException
848     {
849       if(_allocatingPage && !add) {
850         // we are in the midst of allocating a page for ourself, keep track of
851         // this new page so we can mark it later...
852         if(_pendingPage != null) {
853           throw new IllegalStateException("should only have single pending page");
854         }
855         _pendingPage = pageNumber;
856         return;
857       }
858 
859       super.addOrRemovePageNumber(pageNumber, add, force);
860 
861       while(_pendingPage != null) {
862 
863         // while updating our usage map, we needed to allocate a new page (and
864         // thus mark a new page as used).  we delayed that marking so that we
865         // didn't get into an infinite loop.  now that we completed the
866         // original updated, handle the new page.  (we use a loop under the
867         // off the wall chance that adding this page requires allocating a new
868         // page.  in theory, we could do this more than once, but not
869         // forever).
870         int removedPageNumber = _pendingPage;
871         _pendingPage = null;
872 
873         super.addOrRemovePageNumber(removedPageNumber, false, true);
874       }
875     }
876 
877     @Override
878     protected ByteBuffer allocateNewUsageMapPage(int pageIndex)
879       throws IOException
880     {
881       try {
882         // keep track of the fact that we are actively allocating a page for our
883         // own use so that we can break the potential cycle.
884         _allocatingPage = true;
885 
886         ByteBuffer mapPageBuffer = super.allocateNewUsageMapPage(pageIndex);
887 
888         // for the global usage map, all pages are "on" by default.  so
889         // whenever we add a new backing page to the usage map, we need to
890         // turn all the pages that it represents to "on" (we essentially lazy
891         // load this map, which is fine because we should only add pages which
892         // represent the size of the database currently in use).
893         int dataStart = getFormat().OFFSET_USAGE_MAP_PAGE_DATA;
894         ByteUtil.fillRange(mapPageBuffer, dataStart,
895                            getFormat().PAGE_SIZE - dataStart);
896 
897         int maxPagesPerUmapPage = getMaxPagesPerUsagePage();
898         int firstNewPage = (pageIndex * maxPagesPerUmapPage);
899         int lastNewPage = firstNewPage + maxPagesPerUmapPage;
900         _pageNumbers.set(firstNewPage, lastNewPage);
901 
902         return mapPageBuffer;
903 
904       } finally {
905         _allocatingPage = false;
906       }
907     }
908   }
909 
910   /**
911    * Utility class to traverse over the pages in the UsageMap.  Remains valid
912    * in the face of usage map modifications.
913    */
914   public final class PageCursor
915   {
916     /** handler for moving the page cursor forward */
917     private final DirHandler _forwardDirHandler = new ForwardDirHandler();
918     /** handler for moving the page cursor backward */
919     private final DirHandler _reverseDirHandler = new ReverseDirHandler();
920     /** the current used page number */
921     private int _curPageNumber;
922     /** the previous used page number */
923     private int _prevPageNumber;
924     /** the last read modification count on the UsageMap.  we track this so
925         that the cursor can detect updates to the usage map while traversing
926         and act accordingly */
927     private int _lastModCount;
928 
929     private PageCursor() {
930       reset();
931     }
932 
933     public UsageMap getUsageMap() {
934       return UsageMap.this;
935     }
936 
937     /**
938      * Returns the DirHandler for the given direction
939      */
940     private DirHandler getDirHandler(boolean moveForward) {
941       return (moveForward ? _forwardDirHandler : _reverseDirHandler);
942     }
943 
944     /**
945      * Returns {@code true} if this cursor is up-to-date with respect to its
946      * usage map.
947      */
948     public boolean isUpToDate() {
949       return(UsageMap.this._modCount == _lastModCount);
950     }
951 
952     /**
953      * @return valid page number if there was another page to read,
954      *         {@link RowIdImpl#LAST_PAGE_NUMBER} otherwise
955      */
956     public int getNextPage() {
957       return getAnotherPage(CursorImpl.MOVE_FORWARD);
958     }
959 
960     /**
961      * @return valid page number if there was another page to read,
962      *         {@link RowIdImpl#FIRST_PAGE_NUMBER} otherwise
963      */
964     public int getPreviousPage() {
965       return getAnotherPage(CursorImpl.MOVE_REVERSE);
966     }
967 
968     /**
969      * Gets another page in the given direction, returning the new page.
970      */
971     private int getAnotherPage(boolean moveForward) {
972       DirHandler handler = getDirHandler(moveForward);
973       if(_curPageNumber == handler.getEndPageNumber()) {
974         if(!isUpToDate()) {
975           restorePosition(_prevPageNumber);
976           // drop through and retry moving to another page
977         } else {
978           // at end, no more
979           return _curPageNumber;
980         }
981       }
982 
983       checkForModification();
984 
985       _prevPageNumber = _curPageNumber;
986       _curPageNumber = handler.getAnotherPageNumber(_curPageNumber);
987       return _curPageNumber;
988     }
989 
990     /**
991      * After calling this method, getNextPage will return the first page in
992      * the map
993      */
994     public void reset() {
995       beforeFirst();
996     }
997 
998     /**
999      * After calling this method, {@link #getNextPage} will return the first
1000      * page in the map
1001      */
1002     public void beforeFirst() {
1003       reset(CursorImpl.MOVE_FORWARD);
1004     }
1005 
1006     /**
1007      * After calling this method, {@link #getPreviousPage} will return the
1008      * last page in the map
1009      */
1010     public void afterLast() {
1011       reset(CursorImpl.MOVE_REVERSE);
1012     }
1013 
1014     /**
1015      * Resets this page cursor for traversing the given direction.
1016      */
1017     protected void reset(boolean moveForward) {
1018       _curPageNumber = getDirHandler(moveForward).getBeginningPageNumber();
1019       _prevPageNumber = _curPageNumber;
1020       _lastModCount = UsageMap.this._modCount;
1021     }
1022 
1023     /**
1024      * Restores a current position for the cursor (current position becomes
1025      * previous position).
1026      */
1027     private void restorePosition(int curPageNumber)
1028     {
1029       restorePosition(curPageNumber, _curPageNumber);
1030     }
1031 
1032     /**
1033      * Restores a current and previous position for the cursor.
1034      */
1035     protected void restorePosition(int curPageNumber, int prevPageNumber)
1036     {
1037       if((curPageNumber != _curPageNumber) ||
1038          (prevPageNumber != _prevPageNumber))
1039       {
1040         _prevPageNumber = updatePosition(prevPageNumber);
1041         _curPageNumber = updatePosition(curPageNumber);
1042         _lastModCount = UsageMap.this._modCount;
1043       } else {
1044         checkForModification();
1045       }
1046     }
1047 
1048     /**
1049      * Checks the usage map for modifications an updates state accordingly.
1050      */
1051     private void checkForModification() {
1052       if(!isUpToDate()) {
1053         _prevPageNumber = updatePosition(_prevPageNumber);
1054         _curPageNumber = updatePosition(_curPageNumber);
1055         _lastModCount = UsageMap.this._modCount;
1056       }
1057     }
1058 
1059     private int updatePosition(int pageNumber) {
1060       if(pageNumber < UsageMap.this.getFirstPageNumber()) {
1061         pageNumber = RowIdImpl.FIRST_PAGE_NUMBER;
1062       } else if(pageNumber > UsageMap.this.getLastPageNumber()) {
1063         pageNumber = RowIdImpl.LAST_PAGE_NUMBER;
1064       }
1065       return pageNumber;
1066     }
1067 
1068     @Override
1069     public String toString() {
1070       return getClass().getSimpleName() + " CurPosition " + _curPageNumber +
1071         ", PrevPosition " + _prevPageNumber;
1072     }
1073 
1074 
1075     /**
1076      * Handles moving the cursor in a given direction.  Separates cursor
1077      * logic from value storage.
1078      */
1079     private abstract class DirHandler {
1080       public abstract int getAnotherPageNumber(int curPageNumber);
1081       public abstract int getBeginningPageNumber();
1082       public abstract int getEndPageNumber();
1083     }
1084 
1085     /**
1086      * Handles moving the cursor forward.
1087      */
1088     private final class ForwardDirHandler extends DirHandler {
1089       @Override
1090       public int getAnotherPageNumber(int curPageNumber) {
1091         if(curPageNumber == getBeginningPageNumber()) {
1092           return UsageMap.this.getFirstPageNumber();
1093         }
1094         return UsageMap.this.getNextPageNumber(curPageNumber);
1095       }
1096       @Override
1097       public int getBeginningPageNumber() {
1098         return RowIdImpl.FIRST_PAGE_NUMBER;
1099       }
1100       @Override
1101       public int getEndPageNumber() {
1102         return RowIdImpl.LAST_PAGE_NUMBER;
1103       }
1104     }
1105 
1106     /**
1107      * Handles moving the cursor backward.
1108      */
1109     private final class ReverseDirHandler extends DirHandler {
1110       @Override
1111       public int getAnotherPageNumber(int curPageNumber) {
1112         if(curPageNumber == getBeginningPageNumber()) {
1113           return UsageMap.this.getLastPageNumber();
1114         }
1115         return UsageMap.this.getPrevPageNumber(curPageNumber);
1116       }
1117       @Override
1118       public int getBeginningPageNumber() {
1119         return RowIdImpl.LAST_PAGE_NUMBER;
1120       }
1121       @Override
1122       public int getEndPageNumber() {
1123         return RowIdImpl.FIRST_PAGE_NUMBER;
1124       }
1125     }
1126 
1127   }
1128 
1129 }