BtreePage


1   /*
2    * The contents of this file are subject to the terms of the Common Development
3    * and Distribution License (the License). You may not use this file except in
4    * compliance with the License.
5    *
6    * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7    * or http://www.netbeans.org/cddl.txt.
8    *
9    * When distributing Covered Code, include this CDDL Header Notice in each file
10   * and include the License file at http://www.netbeans.org/cddl.txt.
11   * If applicable, add the following below the CDDL Header, with the fields
12   * enclosed by brackets [] replaced by your own identifying information:
13   * "Portions Copyrighted [year] [name of copyright owner]"
14   *
15   * The Original Software is NetBeans. The Initial Developer of the Original
16   * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17   * Microsystems, Inc. All Rights Reserved.
18   */
19  package org.netbeans.mdr.persistence.btreeimpl.btreeindex;
20  
21  import org.netbeans.mdr.persistence.*;
22  import org.netbeans.mdr.persistence.btreeimpl.btreestorage.*;    /* for Converter */
23  import java.io.*;
24  
25  /**
26   * Abstract class containing the main logic for searching and updating a Btree.
27   * It searches and updates the structure of the pages that make up the tree.
28   * Pages are obtained by calls on the associated BtreePageSource.
29   * Searching and updating of the entries on a given page is handled by the
30   * subclass for the specific page format.
31   *
32   * <p>There are two types of normal pages: FixedKeyPage and VarKeyPage.  A
33   * given btree will have either all FixedKeyPages or all VarKeyPages,
34   * depending on the key type.  These are kept in a tree structure where
35   * leaf pages contain the actual data and intermediate pages contain
36   * pageIds of the pages on the level below. 
37   *
38   * <p>The exception to this is BigKeyPages, which may coexist with VarKeyPages
39   * in the same btree.  These are used when a key is encountered whose length is
40   * such that the key plus its data would take up more than one-third the
41   * available space on a page (for a btree with MOFID data items this would
42   * be a key longer than 670 bytes).   All BigKeyPages are kept on a single chain
43   * attached to the root on the right.
44   *
45   * @author  Dana Bergen
46   * @version 1.0
47   */
48  public abstract class BtreePage extends Object   implements Streamable {
49  
50      Btree   btree;      /* Btree to which this page belongs*/
51      BtreePageSource pageSource; /* obtained from Btree */
52      /*
53       * The pageBuffer contains all the entries for this page.  The first
54       * headerLength bytes of the pageBuffer are reserved for the header fields.
55       * The header fields are read from the pageBuffer when it is instantiated
56       * and written to the pageBuffer when it is about to be stored persistently.
57       * During the life of an instantiated BtreePage object, header data is
58       * only updated in the object members, not in the PageBuffer.
59       */
60      public byte[] pageBuffer;   
61  
62      /* Persistently stored page header fields */
63  
64      public byte[]   pageId;     /* this page's ID */
65      byte[]  nextPage;       /* right sibling */
66      byte[]  previousPage;       /* left sibling */
67      short   flags; 
68      int     freeStart;      /* start of free space in page buffer */
69   
70      /* flag values */
71      static final short BTREE_LEAF_PAGE = 0x01;
72      static final short BTREE_ROOT_PAGE = 0x02;
73  
74      static final int    SIZE_OF_SHORT = 2;
75  
76      int     dataLength; /* length of a data entry on this page */
77      int     headerLength;   /* depends on type of page and type of tree */
78      boolean initialized = false;
79  
80      /* Object for passing around btree entries */
81      static class BtreeEntry extends Object   {
82  
83      byte[] key;
84      byte[] data;
85  
86      BtreeEntry(byte[] key, byte[] data) {
87          this.key = key;
88          this.data = data;            
89      }
90  
91      BtreeEntry() {}
92  
93      int length() {
94          return key.length + data.length;
95      }
96      }
97      private static class ParentEntry extends BtreeEntry {
98  
99          int skipCount;
100 
101     ParentEntry(BtreeEntry entry, int skipCount) {
102         key = entry.key;
103         data = entry.data;
104         this.skipCount = skipCount;
105     }
106     }
107 
108     /*
109      * @param resultPosition if this parameter is not null, a new location of the inserted 
110      * entry is recorded here
111      */
112     abstract BtreeEntry insert(BtreeEntry entry, int entryNum, SearchResult resultPosition) 
113                             throws StorageException;
114     abstract BtreeEntry replace(BtreeEntry entry, int entryNum, SearchResult resultPosition)
115                             throws StorageException;
116     abstract void delete(int first, int last) throws StorageException;
117     abstract byte[] getData(int entryNum) throws StorageException;
118     abstract byte[] getKey(int entryNum) throws StorageException;
119     abstract int numEntries();
120     abstract int keyOffset(int entryNum);
121     abstract int keyLength(int entryNum);
122     abstract byte[] splitEntries(BtreePage left, BtreePage right, 
123                      BtreeEntry entry, int entryNum, SearchResult resultPosition)
124                             throws StorageException;
125 
126     /**
127      * Construct an empty BtreePage. All the real work is done in init().
128      */
129     public BtreePage() {
130     }
131 
132     /**
133      * Initialize a newly-instantiated or recycled BtreePage. Note that the
134      * isNew parameter pertains to whether a new page is being added to the
135      * btree, not to whether this BtreePage object is new or recycled.
136      *
137      * @param   btree       Btree to which this page belongs
138      * @param   pageId      page ID in byte array
139      * @param   pageBuffer  page buffer
140      * @param   isNew       is this page new to the btree
141      */
142     public void init(Btree btree, byte[] pageId, byte[] pageBuffer, 
143                 boolean isNew) throws StorageException {
144 
145     if (initialized) {
146         /* This page was found in cache and doesn't need initialization */
147         return;
148     }
149 
150     this.btree = btree;
151     this.pageSource = btree.pageSource;
152     headerLength = btree.pageIdLength*2 + SIZE_OF_SHORT*2;
153 
154     /* If this is a recycled page we don't need to allocate the pageId's */
155     if (this.pageId == null) {
156             this.pageId = new byte[btree.pageIdLength];
157             nextPage = new byte[btree.pageIdLength];
158             previousPage = new byte[btree.pageIdLength];
159     }
160         System.arraycopy(pageId, 0, this.pageId, 0, pageId.length);
161 
162     if (pageBuffer == null) {
163         throw new StoragePersistentDataException("Received null page buffer");
164     } else if (pageBuffer.length != btree.pageSize) {
165         throw new StoragePersistentDataException(
166             "Page buffer size " + pageBuffer.length + 
167         " doesn't match expected page size " + btree.pageSize);
168     }
169     this.pageBuffer = pageBuffer;
170 
171     if (isNew) {
172         pageSource.setNoPage(nextPage);
173         pageSource.setNoPage(previousPage);
174         freeStart = headerLength;
175         makeLeaf();
176     } else {
177         readHeader(pageBuffer);
178     } 
179     initialized = true;
180     }
181     
182     /*
183      * Initialize the BtreePage's attributes using the values in the
184      * header portion of the page buffer.
185      */ 
186     private void readHeader(byte[] pageBuffer) {
187 
188     int pageIdLength;
189     int offset = 0;
190 
191     pageIdLength = pageId.length;
192 
193     for (int i=0; i < pageIdLength; i++) {
194         nextPage[i] = Converter.readByte(pageBuffer, offset++);
195     }
196     for (int i=0; i < pageIdLength; i++) {
197         previousPage[i] = Converter.readByte(pageBuffer, offset++);
198     }
199     flags = Converter.readShort(pageBuffer, offset);
200     offset += 2;
201     freeStart = (int) Converter.readShort(pageBuffer, offset);
202 
203     if (isLeaf()) {
204         makeLeaf();
205     } else {
206         makeInternal();
207     }
208     }   
209 
210     /**
211      * Write BtreePage header data to the page buffer.
212      */
213     public void store() {
214 
215     /*
216      * We don't need synchronization because this will only happen
217      * at commit, or when the object is known to not be in use.
218      */
219     int pageIdLength = pageId.length;
220     int offset = 0;
221 
222     System.arraycopy(nextPage, 0, pageBuffer, offset, pageIdLength);
223     offset += pageIdLength;
224     System.arraycopy(previousPage, 0, pageBuffer, offset, pageIdLength);
225     offset += pageIdLength;
226 
227     Converter.writeShort(pageBuffer, offset, flags);
228     offset += 2;
229     short shortFreeStart = (short) freeStart;
230     Converter.writeShort(pageBuffer, offset, shortFreeStart);
231     }
232 
233     /**
234      * (Streamable Interface) Populate the pageBuffer from the InputStream.  
235      * The page is not usable until init() has also been called. This is
236      * done in pageSource.getPage because it requires a reference to the Btree.
237      *
238      * @param   in  InputStream to read from
239      */
240     public void read(InputStream in) throws StorageException {
241         
242     try {
243         pageBuffer = new byte[in.available()];
244         in.read(pageBuffer);
245     } catch (IOException e) {
246         throw new StorageIOException(e);
247     }
248     }
249 
250     /**
251      * (Streamable Interface) Write this page to the OutputStream.
252      *
253      * @param   out OutputStream to write page to
254      */
255     public void write(OutputStream out) throws StorageException {
256         
257     /*
258      * We don't need synchronization because this will only happen
259      * at commit, or when the object is known to not be in use.
260      */
261     store();
262     try {
263         out.write(pageBuffer);
264     } catch (IOException e) {
265         throw new StorageIOException(e);
266     }
267     }
268 
269     public void uninit() {
270         initialized = false;
271     }
272     
273     /**
274      * Add an entry to the btree, navigating down from this page.  
275      *
276      * @param   key byte array containing key
277      * @param   data    byte array containing data
278      */
279     public void put(byte[] key, byte[] data, byte operation, int index)
280                     throws StorageException {
281     
282     if (!isBigKey(key)) {
283         put(new BtreeEntry(key, data), operation, index, null);
284         } else {
285             putBigKey(new BtreeEntry(key, data), operation, index, null);
286     }
287     }    
288     
289     /**
290      * Add an entry to the btree, navigating down from this page.  
291      *
292      * @param   key byte array containing key
293      * @param   data    byte array containing data
294      * @param   resultPosition location of inserted element is recorded in case this parameter is not null
295      *          and the oparation to perform is insert (add).
296      */
297     public void put(byte[] key, byte[] data, byte operation, int index, SearchResult resultPosition)
298                     throws StorageException {
299     
300     if (!isBigKey(key)) {
301         put(new BtreeEntry(key, data), operation, index, resultPosition);
302         } else {
303             putBigKey(new BtreeEntry(key, data), operation, index, resultPosition);
304     }
305     }
306 
307     /**
308      * Add an entry to the btree, navigating down from this page.  put()
309      * recursively calls itself on its children until a leaf page is reached.
310      * The entry is then inserted.  Page splits may result, in which case put()
311      * may return a BtreeEntry to be inserted to its parent.
312      *
313      * @param entry BtreeEntry to be inserted
314      *
315      * @return      ParentEntry to be inserted to this page's parent 
316      *          due to a page split
317      */
318     ParentEntry put(BtreeEntry entry, byte operation, int index, SearchResult resultPosition) 
319                         throws StorageException {
320 
321     SearchResult    searchResult;
322     ParentEntry     parentEntry;
323 
324     searchResult = searchPage(entry.key);
325 
326     if (isLeaf()) {
327         BtreePage page = searchResult.page;
328         parentEntry = page.putHere(operation, searchResult, entry, index, resultPosition);
329         if (searchResult.page != page) {
330             pageSource.unpinPage(searchResult.page);
331         }
332         if (page != this) {
333             pageSource.unpinPage(page);
334         }
335     } else {
336 
337         BtreePage   child;
338         ParentEntry myEntry;
339 
340         child = searchResult.page.getChild(searchResult);
341         myEntry = child.put(entry, operation, index, resultPosition);
342         pageSource.unpinPage(child);
343         if (myEntry == null) {
344             parentEntry = null;
345         } else {
346             parentEntry = insertParentEntry(myEntry, searchResult);
347         }
348     }
349     return parentEntry;
350     }
351     
352     /*
353      * After a split, insert an entry in the appropriate parent page pointing
354      * to the newly created page. In a MultivaluedOrderedBtree, when doing an
355      * indexed insert we may have traversed sibling pages, so the original
356      * parent location may not be the correct place for this insert.  In that
357      * case we need to move forward one entry at this level for each page 
358      * that was traversed at the child level.
359      */
360     private ParentEntry insertParentEntry(ParentEntry entry, 
361                     SearchResult location) throws StorageException {
362     
363     ParentEntry newParentEntry = null;
364     BtreeEntry splitEntry = null;
365 
366     /*
367      * entry.skipCount is the number of entries to skip at this level.
368      * If there was an exact match at this level, add 1 to skip past
369      * the original leftmost entry for this key.
370      */
371     if (location.matched) {
372         entry.skipCount++;
373     }
374     if (entry.skipCount > 0) {
375             findNth(location, null, entry.skipCount, true);
376     }
377     /*
378      * Don't add a new page entry 0 here,
379      * or the parent key pointing to this page may
380      * become incorrect.  Make it the last entry
381      * of the previous page instead.
382      */
383     if (location.entryNum == 0) {
384         getPrevious(entry.key, location);
385         location.entryNum++;
386     }
387     splitEntry = location.page.insert(entry, location.entryNum, null);
388     /*
389      * location.skipCount now contains the number of entries to be skipped
390      * at our parent's level.
391      */
392     if (splitEntry != null) {
393         newParentEntry = new ParentEntry(splitEntry, location.skipCount);
394     }
395     return newParentEntry;
396     }
397 
398     private ParentEntry putHere(byte operation, SearchResult location,
399             BtreeEntry entry, int index, SearchResult resultPosition) throws StorageException {
400 
401     ParentEntry parentEntry = null;
402     BtreeEntry splitEntry;
403     SearchResult testLocation;
404 
405     switch (operation) {
406 
407         case Btree.ADD:
408             if (location.matched && btree.uniqueKeys) {
409                     
410             btree.failed = true;
411         } else {
412             if (location.matched && btree.uniqueValues) {
413                 testLocation = new SearchResult(location.matched, 
414                     location.entryNum, location.page);
415                 btree.failed = findMatchingData(testLocation, entry.key,
416                                     entry.data);
417                         
418             if ((testLocation.page != location.page)
419                 && (testLocation.page != this)) {
420                 pageSource.unpinPage(testLocation.page);
421             }
422             }
423             if (!btree.failed && (index > 0)) {
424                 btree.failed = !findNth(location, entry.key, 
425                             index, true);
426             }
427             if (!btree.failed) {
428                 splitEntry = location.page.insert(entry, 
429                                 location.entryNum, resultPosition);
430             if (splitEntry != null) {
431                 parentEntry = new ParentEntry(splitEntry, 
432                                 location.skipCount);
433             }
434             }
435         }
436         break;
437 
438         case Btree.REPLACE:
439             if (!location.matched) {
440             btree.failed = true;
441         } else {
442             if (index > 0) {
443                 btree.failed = !findNth(location, entry.key, 
444                             index, false);
445             }
446             if (!btree.failed) {
447                 splitEntry = location.page.replace(entry, 
448                             location.entryNum, resultPosition);
449             if (splitEntry != null) {
450                 parentEntry = new ParentEntry(splitEntry, 
451                                 location.skipCount);
452             }
453             }
454         }
455         break;
456 
457         case Btree.REPLACE_IF_EXISTS:
458             if (!location.matched) {
459                 splitEntry = insert(entry, location.entryNum, resultPosition);
460         } else {
461                 splitEntry = replace(entry, location.entryNum, resultPosition);
462             btree.replaced = true;
463         }
464         if (splitEntry != null) {
465             parentEntry = new ParentEntry(splitEntry, 0);
466         }
467         break;
468     }
469     return parentEntry;
470     }
471 
472     /*
473      * Find the nth (starting from 0) entry matching the key, or the first
474      * entry that doesn't match.
475      *
476      * Returns true if searchResult now points to the nth entry and it
477      * matched. Returns false if the nth entry is not a match, with the
478      * following exceptions:
479      *
480      * If n is Integer.MAX_VALUE, we're adding a new last entry. Or,
481      * if the target entry is the first non-matching entry and this is an
482      * add operation, we're also adding a new last entry.  In either case,
483      * set searchResult to point to the correct insert location and return true.
484      */
485     boolean findNth(SearchResult searchResult, byte[] key,
486                 int target, boolean adding) throws StorageException {
487     BtreePage page;
488 
489     /* 
490      * If we're adding at the end and the list is empty, we're
491      * already correctly positioned, so just return.
492      */
493     if ((target == Integer.MAX_VALUE) && !searchResult.matched) {
494         return true;
495     }
496 
497     /* We already have entry 0, so start counting from 1. */
498     for (int i = 1; i <= target; i++) {
499         page = searchResult.page;
500         getNext(key, searchResult, false);
501         if ((searchResult.page != page) && (page != this)) {
502             pageSource.unpinPage(page);
503         }
504         if (!searchResult.matched) {
505             if (adding && 
506           ((i == target) || (target == Integer.MAX_VALUE))) {
507             /* We're adding a new last entry for this key. Don't
508              * add a new page entry 0 that doesn't match the key of
509              * the existing entry 0, or the parent key pointing to
510              * this page will be incorrect.  Make it the last entry
511              * of the previous page instead.
512              */
513             if ((searchResult.entryNum == 0) && !isBigKey(key)) {
514                 getPrevious(key, searchResult);
515             searchResult.entryNum++;
516             }
517                 return true;
518         } else {
519             return false;
520         }
521         }
522     }
523         return true;
524     }
525 
526     /*
527      * Search for a key/value pair matching the parameters passed in.
528      * The searchResult is presumed to already point to the first entry 
529      * matching the key.  If a match is found, on return searchResult points 
530      * to the matching entry.
531      */
532     private boolean findMatchingData(SearchResult searchResult, 
533         byte[] key, byte[] value) throws StorageException {
534 
535     boolean found;
536     BtreePage page;
537 
538     do {
539         found = (searchResult.page.compareData(
540         value, searchResult.entryNum) == EntryTypeInfo.EQUAL);
541         if (!found) {
542             page = searchResult.page;
543             getNext(key, searchResult, false);
544             if ((searchResult.page != page) && (page != this)) {
545                 pageSource.unpinPage(page);
546             searchResult.skipCount++;
547             }
548         }
549     } while (!found && searchResult.matched);
550 
551     return found;
552     }
553 
554     /**
555      * Retrieves the value associated with the given key.
556      *
557      * @param key   key to find the entry for
558      *
559      * @return      the data associated with the passed-in key, or null
560      *          if it was not found.
561      */
562     public byte[] get(byte[] key) throws StorageException {
563 
564         SearchResult    searchResult;
565     BtreePage   page;
566     byte[]      data;
567 
568         searchResult = getLocation(key);
569     page = searchResult.page;
570 
571     if (searchResult.matched) {
572         data = page.getData(searchResult.entryNum);
573     } else {
574         data = null;
575     }
576     if (page != this) {
577         pageSource.unpinPage(page);
578     }
579     return data;
580     }
581 
582     /**
583      * Finds the first entry associated with the given key, navigating down 
584      * the btree from this page.  
585      * Recursively calls itself on its children until a leaf page is reached.
586      *
587      * @param key   key to find the entry for
588      *
589      * @return      SearchResult pointing to the entry. If no match was
590      *          found, SearchResult.matched will be false.
591      */
592     public SearchResult getLocation(byte[] key) throws StorageException {
593 
594     SearchResult    searchResult;
595 
596     if (isBigKey(key)) {
597         return searchBigKeys(key);
598     }
599 
600     searchResult = searchPage(key);
601 
602     if (isLeaf()) {
603         return searchResult;
604     } else {
605         BtreePage   child;
606 
607         child = searchResult.page.getChild(searchResult);
608         searchResult = child.getLocation(key);
609         if (searchResult.page != child) {
610             pageSource.unpinPage(child);
611         }
612     }
613     return searchResult;
614     }
615 
616     /**
617      * Return the first entry in the btree.  This method is 
618      * called on the root page.
619      */
620     SearchResult getFirst() throws StorageException {
621 
622     SearchResult location;
623     BtreePage parent;
624     
625     location = new SearchResult(false, 0, this);
626     while (!location.page.isLeaf()) {
627         parent = location.page;
628         location.page = location.page.getChild(location);
629         if (parent != location.page) {
630             pageSource.unpinPage(parent);
631         }
632     }
633     /* We now have the first leaf page. Get the first real entry. */
634     location.entryNum = -1;
635         getNext(null, location);
636     if ((!location.matched) && (btree.hasBigKeys())) {
637         getFirstBigKey(location, false);
638     }
639     return location;
640     }
641 
642     /**
643      * Remove all entries from the btree that match the given key.
644      *
645      * @param key   the key to be matched
646      *
647      * @return      boolean indicating whether a match was found
648      */
649     public boolean remove(byte[] key) throws StorageException {
650 
651     SearchResult    result;
652     BtreePage   page = null;
653     int     first, last;
654     boolean     found;
655 
656     result = getLocation(key);
657 
658     if (!result.matched) {
659         found = false;
660     } else {
661         found = true;
662         if (btree.uniqueKeys) {
663         result.page.delete(result.entryNum, result.entryNum);
664         } else {
665         // Call delete() on each page that has matching entries
666         page = result.page;
667         while (result.matched) {
668             page = result.page;
669             first = result.entryNum;
670             last = result.entryNum;
671             // Find the last matching entry on this page
672             while (result.matched && (result.page == page)) {
673             last = result.entryNum;
674             getNext(key, result);
675             }
676             page.delete(first, last);
677             if (page != this) {
678             pageSource.unpinPage(page);
679             }
680         }
681         }
682     }
683     if ((result.page != this) && (result.page != page)) {
684         pageSource.unpinPage(result.page);
685     }
686     return found;
687     }
688 
689     /**
690      * Remove the first entry encountered that matches the key/value pair.
691      *
692      * @param key   the key to be matched
693      * @param data  the data value to be matched
694      *
695      * @return      boolean indicating whether a match was found
696      */
697     public boolean remove(byte[] key, byte[] data) throws StorageException {
698 
699     SearchResult    result;
700     BtreePage   page;
701     boolean     found;
702 
703     result = getLocation(key);
704 
705     if (!result.matched) {
706         found = false;
707     } else {
708         page = result.page;
709         if (page.findMatchingData(result, key, data)) {
710         found = true;
711         result.page.delete(result.entryNum, result.entryNum);
712         } else {
713         found = false;
714         }
715         if ((page != this) && (page != result.page)) {
716         pageSource.unpinPage(page);
717         }
718     }
719     if (result.page != this) {
720         pageSource.unpinPage(result.page);
721     }
722     return found;
723     }
724 
725     /**
726      * Remove the item matching the key at the indexed position.
727      *
728      * @param key   the key to be matched
729      * @param index position within key's entries of the target entry
730      *
731      * @return      boolean indicating whether a match was found
732      */
733     public boolean remove(byte[] key, int index) throws StorageException {
734 
735     SearchResult    result;
736     BtreePage   page;
737     boolean     found;
738 
739     result = getLocation(key);
740 
741     if (!result.matched) {
742         found = false;
743     } else {
744         page = result.page;
745         if (page.findNth(result, key, index, false)) {
746         found = true;
747         result.page.delete(result.entryNum, result.entryNum);
748         } else {
749         found = false;
750         }
751         if ((page != this) && (page != result.page)) {
752         pageSource.unpinPage(page);
753         }
754     }
755     if (result.page != this) {
756         pageSource.unpinPage(result.page);
757     }
758     return found;
759     }
760 
761     /*
762      * Get the child page pointed to by the given searchResult.
763      * A SearchResult points to the first entry >= the search key. So, if
764      * it wasn't an exact match, we need to back up one entry to find the
765      * correct child page.
766      */
767     private BtreePage getChild(SearchResult searchResult) 
768                 throws StorageException {
769 
770         int childEntry;
771 
772     if (searchResult.matched || searchResult.entryNum == 0) {
773         childEntry = searchResult.entryNum;
774     } else {
775         childEntry = searchResult.entryNum - 1;
776     }
777     return pageSource.getPage(getData(childEntry), btree);
778     }
779     
780     /*
781      * Search the page for an entry matching the specified key.  The leftmost
782      * matching entry is returned, which may or may not be on this page.  If
783      * no match was found, the location where this key would be inserted is
784      * returned.
785      */
786     private SearchResult searchPage(byte[] key) throws StorageException {
787         int base;
788         int limit;
789         int midpoint;
790         byte compare;
791         SearchResult test, result;
792         
793         // Binary search the entries on this page
794         base = 0;
795         result = null;
796         if (numEntries() > 0) {
797             for (base = 0, limit = numEntries(); limit > 0; limit = limit/2) {
798                 
799                 midpoint = base + limit/2;
800                 
801                 if ((compare = compare(key, midpoint)) == EntryTypeInfo.EQUAL) {
802                     result = new SearchResult(true, midpoint, this);
803                     if (btree.uniqueKeys) break;
804                 } else if (compare == EntryTypeInfo.GREATER) {
805                     base = midpoint + 1;
806                     limit--;
807                 }
808             }
809         }
810         
811         if (result == null) {
812             result = new SearchResult(false, base, this);
813         }
814         
815         // If this is a non-unique index, we're not done.
816         if (!btree.uniqueKeys) {
817             
818             test = new SearchResult(result);
819             
820             if (!result.matched && isLeaf()) {
821                 // If there was no match, and this is a leaf page,
822                 // there could be a match on an adjoining page (this
823                 // could happen if there were duplicate entries
824                 // on this page that were deleted).
825                 if (result.entryNum == 0) {
826                     getPrevious(key, test);
827                     if (test.matched) {
828                         //System.err.println("matching on previous page");
829                         test.copy(result);
830                     }
831                 }
832                 if (!result.matched &&
833                         result.entryNum == numEntries()) {
834                     //System.err.println("matching on next page");
835                     result.copy(test);
836                     getNext(key, test);
837                     if (test.matched) {
838                         test.copy(result);
839                     }
840                 }
841             }
842             // Get the leftmost match
843             if (result.matched) {
844                 result.copy(test);
845                 do {
846                     // XXX waaay to slow to linearly traverse them.
847                     getPrevious(key, test);
848                     if (test.matched) {
849                         if ((test.page != result.page) && (result.page != this)) {
850                             pageSource.unpinPage(result.page);
851                         }
852                         if (test.page != result.page) { // moved across page
853                             // find the leftmost page
854                             SearchResult test2 = new SearchResult(test);
855                             do {
856                                 test2.copy(test);
857                                 test2.entryNum = 0;
858                                 getPrevious(key, test2); // try previous page
859                             } while (test2.matched);
860                             // test contains the leftmost page now
861                             result = test.page.searchPage(key);
862                             result.skipCount = -1;
863                             return result;
864                         }
865                         test.copy(result);
866                     }
867                 } while (test.matched);
868             }
869         }
870         return result;
871     }
872     
873     /*
874      * Search the page for an entry matching the specified key.  The leftmost
875      * matching entry is returned, which may or may not be on this page.  If
876      * no match was found, the location where this key would be inserted is
877      * returned.
878      *
879      * This methods first of all checks if the leftmost matching entry is on the
880      * specified position. If not, standard search page method is called.
881      */
882     
883     SearchResult searchPage(byte[] key, int position) throws StorageException {
884         if (isLeaf() && (position < numEntries()) && (compare(key, position) == EntryTypeInfo.EQUAL)) {
885             SearchResult result = new SearchResult(true, position, this);
886             if (position > 0) {
887                 if (compare(key, position - 1) != EntryTypeInfo.EQUAL)
888                     return result;
889             } else {
890                 getPrevious(key, result);
891                 if (!result.matched) {
892                     result.matched = true;
893                     result.entryNum = position;
894                     result.page = this;
895                     return result;
896                 }
897             }
898         }
899         return getLocation(key);
900     }
901     
902     /*
903      * Get the previous entry, starting from the passed in result.  The
904      * result is updated to point to the previous entry and indicate whether
905      * it matched the key. If key is null, it is considered a match as long
906      * as any record was found.
907      *
908      * Only empty pages get unpinned here.  Any other page fetched here
909      * will be returned in a SearchResult and must be unpinned by the caller.
910      */
911     static void getPrevious(byte[] key, SearchResult result) 
912                 throws StorageException {
913 
914     BtreePage   page, newPage;
915     int     entry;
916     boolean     endOfChain;
917     Btree       btree;
918     BtreePageSource pageSource;
919     int     traversed = 0;
920         
921     entry = result.entryNum;
922     page = result.page;
923     endOfChain = false;
924     btree = page.btree;
925     pageSource = btree.pageSource;
926     
927     if (page instanceof BigKeyPage) {
928         BigKeyPage.getPrevious(key, result);
929         return;
930     }
931 
932     // Get previous page if necessary, skipping over empty pages
933     while (!(endOfChain = pageSource.isNoPage(page.previousPage))
934          && (entry == 0)) {
935             newPage = pageSource.getPage(page.previousPage, btree);
936         traversed++;
937         if ((page.numEntries() == 0) && (page != result.page)) {
938             pageSource.unpinPage(page);
939         }
940         page = newPage;
941         entry = page.numEntries();
942     }
943 
944     if (endOfChain && (entry == 0)) {
945         result.matched = false;
946     } else {
947             entry--;
948         if ((key == null) ||
949             (page.compare(key, entry) == EntryTypeInfo.EQUAL)) {
950             result.matched = true;
951         } else {
952             result.matched = false;
953         }
954         result.entryNum = entry;
955         result.page = page;
956         result.skipCount -= traversed;
957     }
958     }
959 
960     static boolean hasNext(byte[] key, SearchResult result) 
961                             throws StorageException {
962 
963         getNext(key, result, true);
964     return result.matched;
965     }
966 
967     static void getNext(byte[] key, SearchResult result) 
968                             throws StorageException {
969 
970         getNext(key, result, false);
971     }
972 
973     /*
974      * Get the next entry, starting from the passed in result.  The
975      * result is updated to point to the next entry and indicate whether
976      * it matched the key. If key is null, it is considered a match as long
977      * as any record was found.
978      *
979      * If testOnly is true, result.matched is updated but result.page and
980      * result.entry are left unchanged.
981      *
982      * Empty pages fetched here are unpinned here.  Normally a non-empty page 
983      * fetched here will be returned in the SearchResult and must be unpinned 
984      * by the caller. However if testOnly is true, a non-empty page fetched
985      * here is unpinned here since it will not be returned.
986      */
987     static void getNext(byte[] key, SearchResult result,
988                     boolean testOnly) 
989                 throws StorageException {
990 
991     BtreePage   page, newPage;
992     int     entry;
993     boolean     endOfChain;
994     Btree       btree;
995     BtreePageSource pageSource;
996     int     traversed = 0;
997         
998     page = result.page;
999     btree = page.btree;
1000    pageSource = btree.pageSource;
1001    endOfChain = false;
1002
1003    if (page instanceof BigKeyPage) {
1004        BigKeyPage.getNext(key, result, testOnly);
1005        return;
1006    }
1007
1008    if (page.numEntries() > 0) {
1009        entry = result.entryNum;
1010    } else {
1011        entry = -1;
1012    }
1013    
1014    // Get next page if necessary, skipping over empty pages
1015    while (!(endOfChain = 
1016        (page.isRoot() || pageSource.isNoPage(page.nextPage)))
1017         && (entry >= page.numEntries() - 1)) {
1018            newPage = pageSource.getPage(page.nextPage, btree);
1019        traversed++;
1020        if ((page.numEntries() == 0) && (page != result.page)) {
1021            /*
1022         * This would be a good place to optionally trace
1023         * empty pages in the tree.
1024         */
1025            pageSource.unpinPage(page);
1026        }
1027        page = newPage;
1028        entry = -1;
1029    }
1030
1031    entry++;
1032    if (endOfChain && (entry >= page.numEntries())) {
1033        if ((key == null) && page.isLeaf() && btree.hasBigKeys()) {
1034            getFirstBigKey(result, testOnly);
1035            return;
1036        }
1037        result.matched = false;
1038    } else {
1039        if ((key == null) ||
1040            (page.compare(key, entry) == EntryTypeInfo.EQUAL)) {
1041            result.matched = true;
1042        } else {
1043            result.matched = false;
1044        }
1045    }
1046    if (!testOnly) {
1047        result.entryNum = entry;
1048        result.page = page;
1049        result.skipCount += traversed;
1050    } else if (page != result.page) {
1051        pageSource.unpinPage(page);
1052    }
1053    }
1054
1055    /*
1056     * Splits this page, inserting the new entry in its correct location.
1057     * This method allocates a new page and links it in to the tree.  It
1058     * then calls splitEntries() which moves the entries around
1059     * and does the insert.
1060     *
1061     * @param resultPosition if this parameter is not null, a new location of the inserted 
1062     * entry is recorded here
1063     */
1064    protected BtreeEntry split(BtreeEntry entry, int entryNum, SearchResult resultPosition) 
1065                throws StorageException {
1066
1067        BtreePage right, oldRight;
1068    byte[] rightKey, rightId;
1069
1070        pageSource.dirtyPage(this);
1071
1072    if (isRoot()) {
1073        splitRoot(entry, entryNum, resultPosition);
1074        return null;
1075    } else {
1076        right = pageSource.newPage(btree);
1077        if (isLeaf()) {
1078        right.makeLeaf();
1079        } else {
1080        right.makeInternal();
1081        }
1082        if (!pageSource.isNoPage(nextPage)) {
1083        oldRight = pageSource.getPage(nextPage, btree);
1084        pageSource.dirtyPage(oldRight);
1085        System.arraycopy(right.pageId, 0, oldRight.previousPage, 0,
1086                            right.pageId.length);
1087        pageSource.unpinPage(oldRight);
1088        }
1089        System.arraycopy(this.pageId, 0, right.previousPage, 0,
1090                        this.pageId.length);
1091        System.arraycopy(this.nextPage, 0, right.nextPage, 0,
1092                        this.pageId.length);
1093        System.arraycopy(right.pageId, 0, this.nextPage, 0,
1094                        right.pageId.length);
1095        /*
1096         * Now split the entries between the two pages.  If we're adding 
1097         * a new last record, it may be the case that sequential inserts
1098         * are being done.  If so, it's much more efficient to just move
1099         * the new insert onto the new page instead of splitting in the 
1100         * middle which would just waste space.  If not, no harm done 
1101         * by doing this.
1102         */
1103        if (pageSource.isNoPage(right.nextPage) && (entryNum == numEntries())) {
1104        right.insert(entry, 0, resultPosition);
1105        rightKey = entry.key;
1106        } else {
1107            rightKey = splitEntries(this, right, entry, entryNum, resultPosition);
1108        }
1109        rightId = new byte[right.pageId.length];
1110        System.arraycopy(right.pageId, 0, rightId, 0, right.pageId.length);
1111        pageSource.unpinPage(right);
1112        
1113        return new BtreeEntry(rightKey, rightId);
1114    }
1115    }
1116
1117    /*
1118     * Splits a root page, which is a special case of splitting a page, and
1119     * inserts the entry in the correct location.
1120     */
1121    private void splitRoot(BtreeEntry entry, int entryNum, SearchResult resultPosition) 
1122                throws StorageException {
1123
1124        BtreePage right;
1125    BtreePage left;
1126    byte[] rightKey;
1127    byte[] leftKey;
1128
1129        pageSource.dirtyPage(this);
1130
1131    // Make two new pages
1132    left = pageSource.newPage(btree);
1133    right = pageSource.newPage(btree);
1134    System.arraycopy(right.pageId, 0, left.nextPage, 0, 
1135                        right.pageId.length);
1136    System.arraycopy(left.pageId, 0, right.previousPage, 0, 
1137                        left.pageId.length);
1138    if (this.isLeaf()) {
1139        left.makeLeaf();
1140        right.makeLeaf();
1141    } else {
1142        left.makeInternal();
1143        right.makeInternal();
1144    }
1145    
1146    // Move the entries to the new child pages, clear them from the
1147    // current page, and insert the entry that caused the split.
1148    rightKey = splitEntries(left, right, entry, entryNum, resultPosition);
1149    
1150    // The leftmost key will never be used, so just put a placeholder there.
1151    // See compare() below for explanation.
1152    leftKey = new byte[rightKey.length];
1153
1154    if (isLeaf()) {
1155        makeInternal();
1156    }
1157    insert(new BtreeEntry(leftKey, left.pageId), 0, null);
1158    insert(new BtreeEntry(rightKey, right.pageId), 1, null);
1159    pageSource.unpinPage(right);
1160    pageSource.unpinPage(left);
1161    }
1162    
1163    /**
1164     * Compares the key with that of the specified entry.  Just handles one
1165     * special case and then calls btree.keyInfo.compare().
1166     *
1167     * @param key search key
1168     * @param entryNum entry number of target entry
1169     * @return EntryTypeInfo.EQUAL  if the two keys are equal
1170     *         EntryTypeInfo.GREATER    if search key is greater than entry's key
1171     *         EntryTypeInfo.LESS   if search key is less than entry's key
1172     */
1173    protected byte compare(byte[] key, int entryNum) {
1174
1175    // The leftmost key on the leftmost page at a non-leaf level
1176    // is forced to compare as less than any search key. This avoids
1177    // having to update the leftmost key on internal pages  when
1178    // a key gets inserted that is smaller than anything previously
1179    // inserted.
1180
1181    if (!isLeaf() && (entryNum == 0) 
1182        && pageSource.isNoPage(previousPage)) {
1183        return EntryTypeInfo.GREATER;
1184    } else {                                    
1185        return btree.keyInfo.compare(key, pageBuffer,
1186                            keyOffset(entryNum),
1187                                keyLength(entryNum));
1188        }
1189    }
1190
1191    protected byte compareData(byte[] data, int entryNum) {
1192
1193    return btree.dataInfo.compare(data, pageBuffer,
1194            keyOffset(entryNum) + keyLength(entryNum), data.length);
1195    }
1196
1197    private void makeLeaf() {
1198        flags |= BTREE_LEAF_PAGE;
1199    dataLength = btree.dataLength;
1200    }
1201
1202    private void makeInternal() {
1203        flags &= ~BTREE_LEAF_PAGE;
1204    dataLength = btree.pageIdLength;
1205    }
1206
1207    public void makeRoot() {
1208        flags |= BTREE_ROOT_PAGE;
1209    }
1210
1211    boolean isLeaf() {
1212        return (flags == (flags | BTREE_LEAF_PAGE));
1213    }
1214
1215    boolean isRoot() {
1216        return (flags == (flags | BTREE_ROOT_PAGE));
1217    }
1218
1219    /* 
1220     * BigKey handling methods.  Except for isBigKey(), these are all called
1221     * on the root page.  Once we have a BigKeyPage to work with, a
1222     * BigKeyPage method is invoked.
1223     */
1224
1225    boolean isBigKey(byte[] key) {
1226        return (key.length + btree.dataLength) 
1227        > ((btree.pageSize - headerLength - 4) / 3);
1228    }
1229
1230    void putBigKey(BtreeEntry entry, byte operation, int index, SearchResult resultPosition) 
1231                    throws StorageException {
1232
1233        SearchResult    location;
1234    BtreePage   firstBig;
1235
1236    location = searchBigKeys(entry.key);
1237    if (location.page == this) {
1238        /* There are no big key pages yet */
1239        if (operation == Btree.REPLACE) {
1240            btree.failed = true;
1241        return;
1242        }
1243        firstBig = BigKeyPage.makeFirst(this, pageSource);
1244        location.page = firstBig;
1245        location.entryNum = 0;
1246    }
1247    putHere(operation, location, entry, index, resultPosition);
1248    }
1249
1250    SearchResult searchBigKeys(byte[] key) throws StorageException {
1251
1252    BtreePage page;
1253    SearchResult location;
1254
1255    if (!btree.hasBigKeys()) {
1256        return new SearchResult(false, 0, this);
1257    } else {
1258        page = pageSource.getPage(nextPage, btree);
1259        location = page.searchBigKeys(key);
1260        if (location.page != page) {
1261            pageSource.unpinPage(page);
1262        }
1263        return location;
1264    }
1265    }
1266
1267    static void getFirstBigKey(SearchResult result, boolean testOnly) 
1268                        throws StorageException {
1269
1270        Btree btree = result.page.btree;
1271    BtreePageSource pageSource = btree.pageSource;
1272
1273    BtreePage root = pageSource.getPage(btree.rootPageId, btree);
1274    if (pageSource.isNoPage(root.nextPage)) {
1275        result.matched = false;
1276    } else {
1277        result.matched = true;
1278        if (!testOnly) {
1279            result.page = pageSource.getPage(root.nextPage, btree);
1280        }
1281    }
1282    pageSource.unpinPage(root);
1283    }
1284
1285    /* ******************************************************************
1286     *
1287     * Debugging methods
1288     *
1289     * *****************************************************************/
1290
1291    public TreeMetrics computeMetrics() throws StorageException {
1292        int totalBytes = pageBuffer.length - headerLength;
1293        int usedBytes = freeStart - headerLength;
1294        int num = numEntries();
1295        if (!isLeaf()) {
1296            TreeMetrics[] m = new TreeMetrics[num];
1297            for (int x = 0; x < num; x++) {
1298                BtreePage page = pageSource.getPage(getData(x), btree);
1299                m[x] = page.computeMetrics();
1300            }
1301            return TreeMetrics.computeParent(m, totalBytes, usedBytes, num);
1302        } else {
1303            return new TreeMetrics(1, 1, totalBytes, usedBytes, num, num);
1304        }
1305    }
1306    
1307    /**
1308     * Print BtreePage contents for debugging.
1309     *
1310     * @param   out PrintWriter to print to
1311     */
1312    public void dumpPage(PrintWriter out) throws StorageException {
1313
1314        dumpPageHeader(out);
1315    dumpPageEntries(out);
1316    }
1317
1318    /**
1319     * Print BtreePage header for debugging.
1320     *
1321     * @param   out PrintWriter to print to
1322     */
1323    public void dumpPageHeader(PrintWriter out) {
1324
1325    out.println("\n");
1326
1327    out.println("Page ID: " + pageSource.getPageIdInfo().fromBuffer(pageId) + "\n");
1328    out.println("Next page: " + pageSource.getPageIdInfo().fromBuffer(nextPage) + "\n");
1329    out.println("Previous page: " + pageSource.getPageIdInfo().fromBuffer(previousPage) + "\n");
1330    out.println("Flags: " + flags + "\n");
1331    out.println("Free start: " + freeStart + "\n");
1332    }
1333
1334    /**
1335     * Print BtreePage entries for debugging.
1336     *
1337     * @param   out PrintWriter to print to
1338     */
1339    public void dumpPageEntries(PrintWriter out) throws StorageException {
1340
1341    EntryTypeInfo pageIdInfo = pageSource.getPageIdInfo();
1342
1343        out.println("\nPage entries:\n\n");
1344
1345    for (int i = 0; i < numEntries(); i++) {
1346
1347        out.print(i + ": "); 
1348        // could change these to not allocate
1349        out.print(btree.keyInfo.fromBuffer(getKey(i)) + ", ");
1350        if (isLeaf()) {
1351            out.println(btree.dataInfo.fromBuffer(getData(i)));
1352        } else {
1353            out.println(pageIdInfo.fromBuffer(getData(i)));
1354        }
1355    }
1356    }
1357
1358    /**
1359     * Print raw page buffer contents for debugging.
1360     *
1361     * @param   out PrintWriter to print to
1362     */
1363    public void dumpPageBuffer(PrintWriter out) {
1364
1365        DataInputStream in = new DataInputStream
1366                (new ByteArrayInputStream(pageBuffer));
1367    out.println("\nPage buffer contents:");
1368    try {
1369        int count = 0;
1370        while (true) {
1371        if (count%8== 0) {
1372            out.println();
1373        }
1374            out.print(Integer.toHexString(in.readInt()));
1375            out.print(" ");
1376        count++;
1377        }
1378    } catch (Exception   e) {}
1379    out.println();
1380    }
1381    /**
1382     * Print tree starting from this page for debugging. 
1383     *
1384     * @param   out PrintWriter to print to
1385     */
1386    public void dumpTree(PrintWriter out) throws StorageException {
1387
1388        out.println("\n Dumping Btree:");
1389
1390    BtreePage current = this;
1391    BtreePage old;
1392    int level = 1;
1393    SearchResult leftEntry = new SearchResult(true, 0, this);
1394    while (!current.isLeaf()) {
1395        out.println("\n Level " + level);
1396        current.dumpLevel(out);
1397        level++;
1398        old = current;
1399        current = current.getChild(leftEntry);
1400        if (old != this) {
1401            pageSource.unpinPage(old);
1402        }
1403    }
1404    out.println("\n Leaf Level " + level);
1405    current.dumpLevel(out);
1406    if (current != this) {
1407        pageSource.unpinPage(current);
1408    }
1409    }
1410
1411    void dumpLevel(PrintWriter out) 
1412                throws StorageException {
1413
1414        BtreePage current = this;
1415    byte[] next;
1416
1417    do {
1418        if (current instanceof BigKeyPage) {
1419            current.dumpLevel(out);
1420        return;
1421        }
1422        current.dumpPage(out);
1423        next = current.nextPage;
1424        if (current != this) {
1425            pageSource.unpinPage(current);
1426        }
1427    } while (!pageSource.isNoPage(next) &&
1428        (current = pageSource.getPage(next, btree)) != null);
1429    }
1430
1431    public int consistencyCheck(PrintWriter out) throws StorageException {
1432
1433    BtreePage leftPage = this;
1434    BtreePage old;
1435    int level = 1;
1436    SearchResult leftEntry = new SearchResult(true, 0, this);
1437    SearchResult current = new SearchResult(true, 0, this);
1438    boolean done = false;
1439    int errors = 0;
1440    byte[] previous;
1441    EntryTypeInfo pageIdInfo = pageSource.getPageIdInfo();
1442
1443        out.println("\nBtree Consistency Check:\n");
1444
1445    /* Check consistency of each level */
1446    while (!done) {
1447        current.entryNum = 0;
1448        current.page = leftPage;
1449        current.matched = true;
1450        getNext(null, current);
1451        /* Check that keys on this level are in correct order.  At the
1452         * leaf level, also verify that each record can be navigated
1453         * to correctly by its key.
1454         */
1455        while (current.matched) {
1456            previous = current.page.getKey(current.entryNum);
1457        if (current.page.isLeaf() && btree instanceof SinglevaluedBtree
1458            && (((SinglevaluedBtree)btree).getIfExists(
1459                    btree.keyInfo.fromBuffer(previous)) == null)) {
1460                out.println("Record with key "
1461                + btree.keyInfo.fromBuffer(previous)
1462                + " exists at page "
1463                    + pageIdInfo.fromBuffer(current.page.pageId)
1464                + " , entry " + current.entryNum
1465                + " but cannot be reached.");
1466        } 
1467        old = current.page;
1468            getNext(null, current);
1469        if ((current.page != old) && (old != leftPage)) {
1470            pageSource.unpinPage(old);
1471        }
1472        if (current.matched && !(current.page instanceof BigKeyPage)
1473            && (current.page.compare(previous, current.entryNum)
1474                == EntryTypeInfo.GREATER)) {
1475            errors++;
1476            out.println("Key is less than previous key: page "
1477                    + pageIdInfo.fromBuffer(current.page.pageId)
1478                + " , entry " + current.entryNum
1479                + " , level " + level);
1480        }
1481        }
1482        if (current.page != this) {
1483            pageSource.unpinPage(current.page);
1484        }
1485        /* Go to the beginning of the next level */
1486        level++;
1487        old = leftPage;
1488        if (!(done = leftPage.isLeaf())) {
1489            leftPage = leftPage.getChild(leftEntry);
1490        }
1491        if (old != this) {
1492        pageSource.unpinPage(old);
1493        }
1494    }
1495
1496        out.println("\nBtree Consistency Check Completed\n");
1497    out.flush();
1498    return errors;
1499    }
1500}
1501
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags