KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > derby > impl > store > access > btree > BranchControlRow


1 /*
2
3    Derby - Class org.apache.derby.impl.store.access.btree.BranchControlRow
4
5    Licensed to the Apache Software Foundation (ASF) under one or more
6    contributor license agreements. See the NOTICE file distributed with
7    this work for additional information regarding copyright ownership.
8    The ASF licenses this file to you under the Apache License, Version 2.0
9    (the "License"); you may not use this file except in compliance with
10    the License. You may obtain a copy of the License at
11
12       http://www.apache.org/licenses/LICENSE-2.0
13
14    Unless required by applicable law or agreed to in writing, software
15    distributed under the License is distributed on an "AS IS" BASIS,
16    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17    See the License for the specific language governing permissions and
18    limitations under the License.
19
20  */
21
22 package org.apache.derby.impl.store.access.btree;
23
24 import org.apache.derby.iapi.reference.SQLState;
25
26 import org.apache.derby.iapi.services.io.FormatIdUtil;
27 import org.apache.derby.iapi.services.io.Storable;
28 import org.apache.derby.iapi.services.io.StoredFormatIds;
29
30 import org.apache.derby.iapi.services.sanity.SanityManager;
31
32 import org.apache.derby.iapi.error.StandardException;
33
34 import org.apache.derby.iapi.store.access.conglomerate.LogicalUndo;
35
36 import org.apache.derby.iapi.store.access.AccessFactoryGlobals;
37 import org.apache.derby.iapi.store.access.Qualifier;
38 import org.apache.derby.iapi.store.access.RowUtil;
39 import org.apache.derby.iapi.store.access.ScanController;
40
41 import org.apache.derby.iapi.store.raw.ContainerHandle;
42 import org.apache.derby.iapi.store.raw.FetchDescriptor;
43 import org.apache.derby.iapi.store.raw.Page;
44 import org.apache.derby.iapi.store.raw.RecordHandle;
45
46 import org.apache.derby.iapi.types.DataValueDescriptor;
47
48 import org.apache.derby.iapi.types.SQLLongint;
49
50 import org.apache.derby.iapi.services.io.FormatableBitSet;
51
52 /**
53  * @format_id ACCESS_BTREE_BRANCHCONTROLROW_V1_ID
54  *
55  * @purpose Btree pages all have a control row at the front of every page.
56  * To determine the type of row, read the first column which is a
57  * format id and it tells what kind of control row it is.
58  *
59  * @upgrade RESOLVE.
60  *
61  * @disk_layout
62  * column 1 - control row type : StorableFormatId
63  * column 2 - left sibling page number : SQLLongint
64  * column 3 - right sibling page number: SQLLongint
65  * column 4 - parent page number : SQLLongint
66  * column 5 - level number (0 is leaf) : SQLLongint
67  * column 6 - isRoot : SQLLongint
68  * column 7 - Conglomerate object : null unless it is root else
69  * a Conglomerate object, matching
70  * that of current table.
71  * Currently this field
72  * is only used by logical undo and
73  * the type of object is inferred by
74  * the logical undo code.
75  * column 8 - left child page number : SQLLongint
76  **/
77
78 /**
79 A branch row contains key fields and the pointer to the child page.
80 **/
81 public class BranchControlRow extends ControlRow
82 {
83     protected SQLLongint left_child_page = null;
84
85
86     /**
87      * Only allocate one child_pageno_buf to read the page pointer field into,
88      * then cache to "empty" object for reuse by the page itself.
89      **/
90     transient SQLLongint child_pageno_buf = null;
91
92     /* Column assignments */
93     private static final int CR_LEFTCHILD = ControlRow.CR_COLID_LAST + 1;
94     private static final int CR_COLID_LAST = CR_LEFTCHILD;
95     private static final int CR_NCOLUMNS = CR_COLID_LAST + 1;
96
97     /**
98      * bit sets used to fetch single columns at a time.
99      **/
100     protected static final FormatableBitSet CR_LEFTCHILD_BITMAP =
101         new FormatableBitSet(CR_LEFTCHILD + 1);
102
103     /*
104     ** Constructors of BranchControlRow
105     */
106
107     static
108     {
109         CR_LEFTCHILD_BITMAP.set(CR_LEFTCHILD);
110     }
111
112     /**
113      * No arg constructor.
114      * <p>
115      * Public no arg constructor is for the monitor to call for format
116      * id implementation, it should not be called for any other reason.
117      **/
118     public BranchControlRow()
119     {
120     }
121
122     public BranchControlRow(
123     OpenBTree open_btree,
124     Page page,
125     int level,
126     ControlRow parent,
127     boolean isRoot,
128     long left_child)
129         throws StandardException
130     {
131         super(open_btree, page,
132               level, parent, isRoot);
133
134         this.left_child_page = new SQLLongint(left_child);
135
136         // finish initializing the row to be used for interacting with
137 // raw store to insert, fetch, and update the control row on the page.
138 this.row[CR_LEFTCHILD] = left_child_page;
139
140         // set up buffer to read a branch row's page number into.
141 child_pageno_buf = new SQLLongint();
142     }
143
144     /*
145     ** Non - Debug/consistency check Methods of ControlRow:
146     */
147
148     /**
149      * Perform page specific initialization.
150      * <p>
151      **/
152     protected final void ControlRowInit()
153     {
154         child_pageno_buf = new SQLLongint();
155     }
156
157     /**
158      * Is the current page the leftmost leaf of tree?
159      * <p>
160      *
161      * @return true if the current page is the leftmost leaf of the tree,
162      * else return false.
163      *
164      * @exception StandardException Standard exception policy.
165      **/
166     public boolean isLeftmostLeaf()
167         throws StandardException
168     {
169         return(false);
170     }
171
172     /**
173      * Is the current page the rightmost leaf of tree?
174      * <p>
175      *
176      * @return true if the current page is the rightmost leaf of the tree,
177      * else return false.
178      *
179      * @exception StandardException Standard exception policy.
180      **/
181     public boolean isRightmostLeaf()
182         throws StandardException
183     {
184         return(false);
185     }
186
187     /**
188      * Get the number of columns in the control row.
189      * <p>
190      * Control rows all share the first columns as defined by this class and
191      * then add columns to the end of the control row. For instance a branch
192      * control row add a child page pointer field.
193      * <p>
194      *
195      * @return The total number of columns in the control row.
196      **/
197     protected final int getNumberOfControlRowColumns()
198     {
199         return(this.CR_NCOLUMNS);
200     }
201
202     public static long restartSplitFor(
203     OpenBTree open_btree,
204     DataValueDescriptor[] template,
205     BranchControlRow parent,
206     ControlRow child,
207     DataValueDescriptor[] newbranchrow,
208     DataValueDescriptor[] splitrow,
209     int flag)
210         throws StandardException
211     {
212         // release parent and current latch
213 parent.release();
214         child.release();
215         parent = null;
216         child = null;
217
218         // Get the root page back, and perform a split following the
219 // branch row which would not fit.
220 ControlRow root = ControlRow.Get(open_btree, BTree.ROOTPAGEID);
221
222         if (SanityManager.DEBUG)
223             SanityManager.ASSERT(root.page.isLatched());
224
225         return(root.splitFor(open_btree, template, null, newbranchrow, flag));
226     }
227
228
229     /**
230      ** Perform a recursive search, ultimately returning the latched
231      ** leaf page and row slot after which the given key belongs.
232      ** The slot is returned in the result structure. If the key
233      ** exists on the page, the result.exact will be true. Otherwise,
234      ** result.exact will be false, and the row slot returned will be
235      ** the one immediately preceding the position at which the key
236      ** belongs.
237      **
238      ** @exception StandardException Standard exception policy.
239      **/
240     public ControlRow search(SearchParameters sp)
241         throws StandardException
242     {
243         ControlRow childpage = null;
244         long childpageid;
245         boolean got_error = true;
246
247         try
248         {
249             searchForEntry(sp);
250
251             if (sp.searchForOptimizer)
252             {
253                 // Update left_fraction to be used to esitimate the number of
254 // rows left of the current search key.
255
256                 // Some search results leave the search positioned on the 0th
257 // slot which is a control row, in branch pages this results
258 // in following the left page pointer, there is no key
259 // associated with this slot. Set left_rows to be the number
260 // of leaf page pointers on the page which are left
261 // of the current slot.
262 float left_rows = sp.resultSlot;
263
264                 // include the control row count here, as it accounts for the
265 // left page pointer which has no associated key.
266 int row_count = this.page.recordCount();
267
268                 if (this.getIsRoot())
269                 {
270                     sp.current_fraction = 1;
271                     sp.left_fraction = 0;
272                 }
273
274                 // calculate the fraction of rows in the table which are left
275 // of the current slot in the search. This number represents
276 // the fraction of rows in the sub-tree which includes all
277 // rows left of rows pointed at by the sub-tree to be followed
278 // by the code below which descends the child page pointer.
279 // After the search is
280 // completed (sp.left_fraction * number of rows), is the
281 // estimated number of rows to the left of the current row.
282 sp.left_fraction +=
283                     (sp.current_fraction) * (left_rows / row_count);
284
285                 sp.current_fraction =
286                     (sp.current_fraction) * (((float) 1) / row_count);
287             }
288
289             childpage =
290                 this.getChildPageAtSlot(sp.btree, sp.resultSlot);
291
292             this.release();
293
294             got_error = false;
295
296             return childpage.search(sp);
297         }
298         finally
299         {
300             if (got_error)
301             {
302                 if (childpage != null)
303                     childpage.release();
304                 if (this.page.isLatched())
305                     this.release();
306             }
307         }
308     }
309
310     /**
311      * Search and return the left most leaf page.
312      * <p>
313      * Perform a recursive search, ultimately returning the
314      * leftmost leaf page which is the first leaf page in the
315      * leaf sibling chain. (This method might better be called
316      * getFirstLeafPage()).
317      *
318      * @return The leftmost leaf page.
319      *
320      * @param btree The open btree to associate latches/locks with.
321      *
322      * @exception StandardException Standard exception policy.
323      **/
324     protected ControlRow searchLeft(OpenBTree btree)
325         throws StandardException
326     {
327         ControlRow childpage = null;
328         boolean got_error = true;
329
330         try
331         {
332             childpage = this.getLeftChild(btree);
333             this.release();
334
335             got_error = false;
336             return childpage.searchLeft(btree);
337         }
338         finally
339         {
340             if (got_error)
341             {
342                 if (childpage != null)
343                     childpage.release();
344                 if (this.page.isLatched())
345                     this.release();
346             }
347         }
348     }
349
350     /**
351      * Search and return the right most leaf page.
352      * <p>
353      * Perform a recursive search, ultimately returning the
354      * rightmost leaf page which is the last leaf page in the
355      * leaf sibling chain. (This method might better be called
356      * getLastLeafPage()).
357      *
358      * @return The rightmost leaf page.
359      *
360      * @param btree The open btree to associate latches/locks with.
361      *
362      * @exception StandardException Standard exception policy.
363      **/
364     protected ControlRow searchRight(OpenBTree btree)
365         throws StandardException
366     {
367         ControlRow childpage = null;
368         boolean got_error = true;
369
370         try
371         {
372             childpage = this.getRightChild(btree);
373             this.release();
374
375             got_error = false;
376             return(childpage.searchRight(btree));
377         }
378         finally
379         {
380             if (got_error)
381             {
382                 if (childpage != null)
383                     childpage.release();
384                 if (this.page.isLatched())
385                     this.release();
386             }
387         }
388     }
389
390
391     /**
392      ** Perform a recursive shrink operation for the key.
393      ** If this method returns true, the caller should
394      ** remove the corresponding entry for the page.
395      ** This routine is not guaranteed to successfully
396      ** shrink anything. The page lead to by the key might
397      ** turn out not to be empty by the time shrink gets
398      ** there, and shrinks will give up if there is a deadlock.
399      ** <P>
400      ** The receiver page must be latched on entry and is
401      ** returned latched.
402      **
403      ** @exception StandardException Standard exception policy.
404      **/
405     protected boolean shrinkFor(
406     OpenBTree open_btree,
407     DataValueDescriptor[] shrink_key)
408         throws StandardException
409     {
410         ControlRow childpage = null;
411         boolean shrinkme = false;
412
413         try
414         {
415             if (SanityManager.DEBUG)
416                 SanityManager.ASSERT(this.page.isLatched());
417
418             // Find the child page for the shrink key.
419
420             BranchRow branch_template =
421                 BranchRow.createEmptyTemplate(open_btree.getConglomerate());
422             SearchParameters sp = new SearchParameters(
423                 shrink_key,
424                 SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH,
425                 branch_template.getRow(), open_btree, false);
426
427             this.searchForEntry(sp);
428             childpage = this.getChildPageAtSlot(sp.btree, sp.resultSlot);
429
430             // Recursively shrink the child. If this call returns
431 // true, then the child page has been deleted from its
432 // sibling chain, and we have to delete the entry for it
433 // in this page.
434
435             if (childpage.shrinkFor(open_btree, shrink_key))
436             {
437                 // Child was deallocated.
438 if (sp.resultSlot != 0)
439                 {
440                     // Remove the corresponding branch row. This call assumes
441 // that raw store will shift all higher slots down to fill
442 // the purged slot.
443 this.page.purgeAtSlot(sp.resultSlot, 1, true);
444                 }
445                 else
446                 {
447                     // Shrunk slot is zero, which means the left child page was
448 // deallocated. If the current page is empty, then
449 // we have to deallocate it. Otherwise, we "slide" the rows
450 // down, making the first index row into the left child,
451 // and the second index row into the first, etc.
452
453                     if (this.page.recordCount() > 1)
454                     {
455                         // There is a branch row on this page (besides the
456 // control row). Make the first branch row into the
457 // left child.
458
459                         long leftchildpageid =
460                             getChildPageIdAtSlot(open_btree, 1);
461
462                         this.setLeftChildPageno(leftchildpageid);
463
464                         // purge the row we just made the "left child", this
465 // will automatically shifta all other rows "left" in
466 // the tree.
467 this.page.purgeAtSlot(1, 1, true);
468                     }
469                     else
470                     {
471                         // We shrunk the left child which was the last child on
472 // the page. This means that this entire subtree is
473 // empty. Again, there are two cases: root vs.
474 // non-root. Because this method waits till pages are
475 // completely empty before deallocating them from the
476 // index, an empty root page means an empty index.
477 // If this page is not the root, then simply
478 // deallocate it and return that fact to the caller.
479
480                         if (this.getIsRoot())
481                         {
482                             // The root page has become empty. If the root page
483 // is empty, then the index is empty. What has to
484 // happen here is that this page has to be
485 // converted back to an empty leaf page.
486
487                             // With the current interface, after this page has
488 // been converted to a leaf, the caller will be
489 // left with a branch control row object, although
490 // the page is a leaf page. This same problem was
491 // addressed in splitFor by adjusting the interface
492 // - the two routines should at least have the same
493 // interface style.
494
495                             if (SanityManager.DEBUG)
496                             {
497                                 SanityManager.ASSERT(
498                                     this.page.recordCount() == 1);
499                             }
500
501                             LeafControlRow newleafroot = new LeafControlRow(
502                                 open_btree, this.page, null, true);
503
504                             newleafroot.page.updateAtSlot(
505                                 0, newleafroot.getRow(),
506                                 (FormatableBitSet) null);
507
508                             newleafroot.release();
509
510                             shrinkme = true;
511                         }
512                         else
513                         {
514                             // This page is empty, but it's not the root. We
515 // have to unlink this page from its siblings, and
516 // return to the parent branch page that its
517 // branch row should be removed.
518
519                             // Unlink this page from its siblings.
520 if (this.unlink(open_btree))
521                             {
522                                 // Tell the caller to remove entry.
523 shrinkme = true;
524                             }
525                         }
526                     }
527                 }
528             }
529         }
530         finally
531         {
532             // If shrinkme then the page has been unlatched either by
533 // page.removePage(), or by the process of changing the root branch
534 // page to a root leaf page.
535 if (!shrinkme)
536                 this.release();
537         }
538
539         return(shrinkme);
540     }
541
542     /**
543      * Perform a top down split pass making room for the the key in "row".
544      * <p>
545      * Perform a split such that a subsequent call to insert
546      * given the argument index row will likely find room for it. Since
547      * latches are released the client must code for the case where another
548      * user has grabbed the space made available by the split pass and be
549      * ready to do another split.
550      * <p>
551      * Latches:
552      * o PARENT : is latched on entry (unless the split is the root then
553      * there is no parent.
554      * o THISBRANCH: the current page is latched on entry.
555      * o CHILD : latch the child page which will be pointed at by the
556      * left child pointer of the new page.
557      * RESOLVE (mikem) -see comments below
558      * o NEWPAGE : Allocate and latch new page.
559      * o CHILD : release. (RESOLVE)
560      * o fixparents: latch pages and reset their parent pointers.
561      * Conditionally fix up the parent links on the pages
562      * pointed at by the newly allocated page. First get latch
563      * and release on the left child page and then loop through
564      * slots on NEWPAGE, from left to right getting and
565      * releasing latches.
566      *
567      *
568      * @return page number of the newly allocated leaf page created by split.
569      *
570      * @param open_btree The open btree to associate latches with.
571      * @param template A scratch area to use while searching for split pass.
572      * @param parent The parent page of the current page in the split pass.
573      * starts at null for root.
574      * @param splitrow The key to make room for during the split pass.
575      * @param flag A flag used to direct where point of split should be
576      * chosen.
577      *
578      * @exception StandardException Standard exception policy.
579      **/
580     protected long splitFor(
581     OpenBTree open_btree,
582     DataValueDescriptor[] template,
583     BranchControlRow parent,
584     DataValueDescriptor[] splitrow,
585     int flag)
586         throws StandardException
587     {
588         int childpageid;
589         ControlRow childpage;
590
591         // On entry, the parent page is either latched by the caller,
592 // or it's null (which implies that this object is the root).
593
594         if (SanityManager.DEBUG)
595         {
596             SanityManager.ASSERT(parent != null || this.getIsRoot());
597
598             SanityManager.ASSERT(
599                 parent == null || parent.page.isLatched(),
600                 "parent page is not latched");
601
602             SanityManager.ASSERT(this.page.isLatched(),
603                 "page is not latched:");
604         }
605
606         if ((this.page.recordCount() - 1 >=
607                 open_btree.getConglomerate().maxRowsPerPage) ||
608             (!this.page.spaceForInsert(splitrow, (FormatableBitSet) null,
609                 AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD)))
610         {
611
612             if (this.page.recordCount() == 1)
613             {
614                 // RESOLVE (mikem) long row issue. For now it makes no sense
615 // to split if there are no rows. So if spaceForRecord() fails
616 // on empty page, we throw exception.
617 throw StandardException.newException(
618                         SQLState.BTREE_NO_SPACE_FOR_KEY);
619             }
620
621             // Track.BranchSplit++;
622
623             if (this.getIsRoot())
624             {
625                 // Track.BranchSplitRoot++;
626 growRoot(open_btree, template, this);
627
628                 parent = (BranchControlRow)
629                     ControlRow.Get(open_btree, BTree.ROOTPAGEID);
630
631
632                 return(parent.splitFor(
633                         open_btree, template, null, splitrow, flag));
634             }
635
636             // At this point we know that this page has to be split and
637 // that it isn't a root page.
638 if (SanityManager.DEBUG)
639             {
640                 SanityManager.ASSERT(!this.getIsRoot());
641                 SanityManager.ASSERT(parent != null);
642             }
643
644             int splitpoint = (this.page.recordCount() - 1) / 2 + 1;
645
646             if ((flag & ControlRow.SPLIT_FLAG_FIRST_ON_PAGE) != 0)
647             {
648                 // move all the row to the new page
649 splitpoint = 1;
650             }
651             else if ((flag & ControlRow.SPLIT_FLAG_LAST_ON_PAGE) != 0)
652             {
653                 // This is not optimal as we would rather move no rows to the
654 // next page, but what should we use as a discriminator?
655 splitpoint = this.page.recordCount() - 1;
656             }
657
658             if (SanityManager.DEBUG)
659             {
660                 if (splitpoint <= 0)
661                     SanityManager.THROWASSERT(this + "yikes! splitpoint of 0!");
662             }
663
664
665             // Before any logged operation is done in the current internal
666 // xact, make sure that there is room in the parent to insert
667 // the new branch row.
668 //
669 // Create a new branch row which points to the new page,
670 // and insert it on parent page.
671
672             // Read in the branch row which is at the split point.
673 BranchRow split_branch_row =
674                 BranchRow.createEmptyTemplate(open_btree.getConglomerate());
675
676             this.page.fetchFromSlot(
677                 (RecordHandle) null, splitpoint, split_branch_row.getRow(),
678                 (FetchDescriptor) null, true);
679
680             // Create the branch row to insert onto the parent page. For now
681 // use a fake page number because we don't know the real page
682 // number until the allocate is done, but want to delay the
683 // allocate until we know the insert will succeed.
684 BranchRow newbranchrow =
685                 split_branch_row.createBranchRowFromOldBranchRow(
686                         BranchRow.DUMMY_PAGE_NUMBER);
687
688             // At this point we have guaranteed there is space in the parent
689 // page for splitrow, but it could be the case that the new
690 // "newbranchrow" does not fit on the parent page.
691 if (!parent.page.spaceForInsert(
692                     newbranchrow.getRow(), (FormatableBitSet) null,
693                     AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD))
694             {
695                 // There is no room on the parent page to complete a split at
696 // the current level, so restart the split at top with the
697 // branchrow that did not fit. On return from this routine
698 // there is no way to know the state of the tree, so the
699 // current split pass recursion must end.
700 return(
701                     parent.restartSplitFor(
702                         open_btree, template, parent, this,
703                         newbranchrow.getRow(), splitrow, flag));
704             }
705
706             // Get the child page for the index row at the split point
707 // This will be the left child for the new page. We're
708 // getting the page because BranchControlRow.Allocate
709 // sets the left child pointer from a BranchControlRow.
710 // If there were a version which just took the pageid,
711 // we wouldn't have to get the page (the latch on this
712 // page is enough to ensure that the child page won't
713 // disappear).
714
715             childpage = this.getChildPageAtSlot(open_btree, splitpoint);
716
717             // Allocate a new branch page and link it to the
718 // right of the current page.
719 BranchControlRow newbranch =
720                 BranchControlRow.Allocate(open_btree, childpage,
721                     this.getLevel(), parent);
722             newbranch.linkRight(open_btree, this);
723
724
725             // Test fail after allocation
726 if (SanityManager.DEBUG)
727             {
728                 if (SanityManager.DEBUG_ON("branch_split_abort1"))
729                 {
730                     throw StandardException.newException(
731                             SQLState.BTREE_ABORT_THROUGH_TRACE);
732                 }
733             }
734
735             // Done with the child page.
736 childpage.release();
737
738             // Now that we know the page number of the new child page update
739 // the branch row to be inserted with the correct value.
740 newbranchrow.setPageNumber(newbranch.page.getPageNumber());
741
742             BranchRow branch_template =
743                 BranchRow.createEmptyTemplate(open_btree.getConglomerate());
744             SearchParameters sp = new SearchParameters(
745                 newbranchrow.getRow(),
746                 SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH,
747                 branch_template.getRow(),
748                 open_btree, false);
749
750             parent.searchForEntry(sp);
751
752             byte insertFlag = Page.INSERT_INITIAL;
753             insertFlag |= Page.INSERT_DEFAULT;
754             insertFlag |= Page.INSERT_UNDO_WITH_PURGE;
755             if (parent.page.insertAtSlot(
756                     sp.resultSlot + 1,
757                     newbranchrow.getRow(),
758                     (FormatableBitSet) null,
759                     (LogicalUndo)null,
760                     insertFlag, AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD)
761                     == null)
762             {
763                 throw StandardException.newException(
764                             SQLState.BTREE_NO_SPACE_FOR_KEY);
765             }
766
767
768             // Test fail after of row onto parent page.
769 if (SanityManager.DEBUG)
770             {
771                 if (SanityManager.DEBUG_ON("branch_split_abort2"))
772                 {
773                     throw StandardException.newException(
774                             SQLState.BTREE_ABORT_THROUGH_TRACE);
775                 }
776             }
777
778             // newbranchrow only valid while contents of split_branch_row
779 // remain unchanged.
780 newbranchrow = null;
781
782             // Copy the rows from the split point, but not including it (since
783 // the split point is turning into the left child of the new
784 // branch), onto the new page. Purge the rows including the split
785 // point from the current page.
786 int num_rows_to_move = this.page.recordCount() - (splitpoint + 1);
787
788             if (num_rows_to_move > 0)
789             {
790                 this.page.copyAndPurge(
791                     newbranch.page, splitpoint + 1, num_rows_to_move, 1);
792             }
793
794             // remove the splitpoint row, we didn't copy it because it became
795 // the "left child", but we do need to get rid of it.
796 this.page.purgeAtSlot(splitpoint, 1, true);
797
798             // Test fail after of copy of rows to new page.
799 if (SanityManager.DEBUG)
800             {
801                 if (SanityManager.DEBUG_ON("branch_split_abort3"))
802                 {
803                     throw StandardException.newException(
804                             SQLState.BTREE_ABORT_THROUGH_TRACE);
805                 }
806             }
807
808             // Test fail after purge of rows on old page.
809 if (SanityManager.DEBUG)
810             {
811                 if (SanityManager.DEBUG_ON("branch_split_abort4"))
812                 {
813                     throw StandardException.newException(
814                             SQLState.BTREE_ABORT_THROUGH_TRACE);
815                 }
816             }
817
818             // Check pages that have been altered by above split
819 if (SanityManager.DEBUG)
820             {
821                 if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck"))
822                 {
823                     parent.checkConsistency(open_btree, null, false);
824                     newbranch.checkConsistency(open_btree, parent, false);
825                     this.checkConsistency(open_btree, parent, false);
826                 }
827             }
828
829             // Fix up the parent links on the pages for the rows that moved to
830 // the new branch.
831 newbranch.fixChildrensParents(open_btree, null);
832
833             // At this point a unit of work in the split down the tree has
834 // been performed in an internal transaction (ie. writes have been
835 // done to latched pages), and the resulting
836 // tree is logically consistent, thus the work can be committed.
837 // This work must be committed before any latches are released.
838 open_btree.getXactMgr().commit();
839
840             // Decide whether we're following the current page or the new page.
841 BranchControlRow pagetofollow;
842
843             if (CompareIndexRowToKey(
844                     splitrow,
845                     split_branch_row.getRow(),
846                     split_branch_row.getRow().length - 1, 0,
847                     open_btree.getConglomerate().ascDescInfo) >= 0)
848             {
849                 // Follow the new branch
850 pagetofollow = newbranch;
851                 this.release();
852             }
853             else
854             {
855                 // Follow the current branch
856 pagetofollow = this;
857                 newbranch.release();
858             }
859
860             // At this point we hold latches on the parent, and the current
861 // child of the page that we are following. Note that committing
862 // the internal transaction did not release the latches.
863 if (SanityManager.DEBUG)
864             {
865                 SanityManager.ASSERT(parent != null);
866                 SanityManager.ASSERT(parent.page.isLatched());
867                 SanityManager.ASSERT(
868                         pagetofollow.page.isLatched());
869             }
870
871             // Recurse down the tree splitting if necessary.
872 return(
873                 pagetofollow.splitFor(
874                     open_btree, template, parent, splitrow, flag));
875         }
876
877         if (SanityManager.DEBUG)
878         {
879             if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck"))
880             {
881                 this.checkConsistency(open_btree, parent, false);
882             }
883         }
884
885         // Don't need the parent any more.
886 if (parent != null)
887             parent.release();
888
889         // RESOLVE (mikem) - should this be passed in?
890 BranchRow branch_template =
891             BranchRow.createEmptyTemplate(open_btree.getConglomerate());
892         SearchParameters sp = new SearchParameters(
893             splitrow,
894             SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH,
895             branch_template.getRow(),
896             open_btree, false);
897
898         searchForEntry(sp);
899
900         childpage = this.getChildPageAtSlot(open_btree, sp.resultSlot);
901
902         return(childpage.splitFor(open_btree, template, this, splitrow, flag));
903     }
904
905     /*
906     ** Debug/consistency check Methods of ControlRow:
907     */
908
909
910     /**
911      ** Perform consistency checks for a branch page. The checks
912      ** specific to a branch page are:
913      ** <menu>
914      ** <li> The rows on the page are indeed branch rows, and
915      ** they all have the correct number of fields (which
916      ** is the b-tree's key fields plus one for the child
917      ** page number.
918      ** <li> The child pages pointed to by the left child pointer
919      ** and the index rows are linked together in the same
920      ** order that they appear on the page.
921      ** <li> The child pages themselves are all consistent.
922      ** </menu>
923      ** This method also performs the consistency checks that
924      ** are common to both leaf and branch pages (see
925      ** ControlRow.checkGeneric).
926      **
927      ** @exception StandardException Standard exception policy.
928      **/
929     public int checkConsistency(
930     OpenBTree btree,
931     ControlRow parent,
932     boolean check_other_pages)
933         throws StandardException
934     {
935         // Do the consistency checks that are common to all
936 // types of pages.
937 checkGeneric(btree, parent, check_other_pages);
938
939         // Branch specific Control Row checks.
940 if (SanityManager.DEBUG)
941         {
942             SanityManager.ASSERT(
943                 this.getLevel() > 0, "branch not above level 0");
944
945             // RESOLVE (mikem) - how to check right version?
946 /*
947             if (this.getVersion() != CURRENT_BRANCH_VERSION)
948                 SanityManager.THROWASSERT(
949                     "Expected branch version:(" + CURRENT_BRANCH_VERSION +
950                     ") but got (" + this.getVersion());
951             */
952             SanityManager.ASSERT(
953                 this.page.fetchNumFieldsAtSlot(CR_SLOT) ==
954                 BranchControlRow.CR_NCOLUMNS);
955             SanityManager.ASSERT(getLeftChildPageno() !=
956                                  ContainerHandle.INVALID_PAGE_NUMBER);
957
958             // RESOLVE (mikem) - this makes an assumption about page numbering,
959 // that may not be always valid in all implementations but has
960 // been useful in finding bugs with uninitialized fields.
961 SanityManager.ASSERT(getLeftChildPageno() >= BTree.ROOTPAGEID);
962         }
963
964         // The remaining checks are specific to branch pages.
965 if (SanityManager.DEBUG)
966         {
967
968             // Check that all the branch rows are branch rows
969 // (we'll get a case error otherwise), and have the right
970 // number of columns. Every branch row should have the
971 // btree's key columns plus one for the child link.
972 int numslots = this.page.recordCount();
973             for (int slot = 1; slot < numslots; slot++)
974             {
975                 if ((this.page.fetchNumFieldsAtSlot(slot) !=
976                      (btree.getConglomerate().nKeyFields + 1)))
977                     SanityManager.THROWASSERT(
978                         "row[" + slot + "]"
979                         + " has " + this.page.fetchNumFieldsAtSlot(slot)
980                         + " columns, should have at least " +
981                         (btree.getConglomerate().nKeyFields + 1));
982
983                 SanityManager.ASSERT(this.getChildPageIdAtSlot(btree, slot) !=
984                         ContainerHandle.INVALID_PAGE_NUMBER);
985
986                 // Rows on branch pages are never deleted, they are only purged.
987 SanityManager.ASSERT(!this.page.isDeletedAtSlot(slot));
988
989                 // RESOLVE (mikem) - this makes an assumption about page
990 // numbering, that may not be always valid in all
991 // implementations but has been useful in finding bugs with
992 // uninitialized fields.
993 SanityManager.ASSERT(getLeftChildPageno() >= BTree.ROOTPAGEID);
994             }
995         }
996
997         // Check that the linkage of the children is in the
998 // same order as the branch rows.
999 // RESOLVE (mikem) enable when multiple latches work.
1000 if (check_other_pages)
1001            checkChildOrderAgainstRowOrder(btree);
1002
1003        // Check the children.
1004 int nchildren = 0;
1005
1006        // RESOLVE (mikem) enable when multiple latches work.
1007 if (check_other_pages)
1008            nchildren = checkChildren(btree);
1009
1010        // Return the number of children visited plus one for this page.
1011 return nchildren + 1;
1012    }
1013
1014    private int checkChildren(OpenBTree btree)
1015        throws StandardException
1016    {
1017        int nchildren = 0;
1018        ControlRow childpage = null;
1019
1020        try
1021        {
1022            // Check the left child.
1023 childpage = this.getLeftChild(btree);
1024            nchildren += childpage.checkConsistency(btree, this, true);
1025            childpage.release();
1026            childpage = null;
1027
1028            // Check children from each index row.
1029 int numslots = this.page.recordCount();
1030            for (int slot = 1; slot < numslots; slot++)
1031            {
1032                childpage = this.getChildPageAtSlot(btree, slot);
1033                nchildren += childpage.checkConsistency(btree, this, true);
1034                childpage.release();
1035                childpage = null;
1036            }
1037
1038            return(nchildren);
1039        }
1040        finally
1041        {
1042            if (childpage != null)
1043                childpage.release();
1044        }
1045    }
1046
1047    private void checkChildOrderAgainstRowOrder(OpenBTree btree)
1048        throws StandardException
1049    {
1050        ControlRow cur = null;
1051        ControlRow prev = null;
1052
1053        try
1054        {
1055            prev = this.getLeftChild(btree);
1056
1057            int numslots = this.page.recordCount();
1058            for (int slot = 1; slot < numslots; slot++)
1059            {
1060                cur = this.getChildPageAtSlot(btree, slot);
1061
1062                long shouldbecur_pageno = prev.getrightSiblingPageNumber();
1063                if (SanityManager.DEBUG)
1064                {
1065                    if (shouldbecur_pageno != cur.page.getPageNumber())
1066                        SanityManager.THROWASSERT(
1067                            "child linkage error going right.\n" +
1068                            "cur page control row = " + cur + "\n" +
1069                            "prev page control row = " + prev + "\n");
1070                }
1071
1072                long shouldbeprev_pageno = cur.getleftSiblingPageNumber();
1073
1074                if (SanityManager.DEBUG)
1075                {
1076                    SanityManager.ASSERT(
1077                        shouldbeprev_pageno == prev.page.getPageNumber(),
1078                        "child linkeage error going left");
1079                }
1080
1081                prev.release();
1082                prev = cur;
1083                cur = null;
1084            }
1085
1086            prev.release();
1087            prev = null;
1088        }
1089        finally
1090        {
1091            if (prev != null)
1092                prev.release();
1093            if (cur != null)
1094                cur.release();
1095        }
1096
1097        return;
1098    }
1099
1100    /**
1101     * Recursively print the tree starting at current node in tree.
1102     *
1103     * @param btree the open btree to print.
1104     *
1105     * @exception StandardException Standard exception policy.
1106     **/
1107    public void printTree(
1108    OpenBTree btree)
1109        throws StandardException
1110    {
1111        if (SanityManager.DEBUG)
1112        {
1113            SanityManager.DEBUG_PRINT("p_tree", this.debugPage(btree));
1114
1115            ControlRow child = null;
1116
1117            try
1118            {
1119                child = this.getLeftChild(btree);
1120
1121                child.printTree(btree);
1122                child.release();
1123                child = null;
1124
1125                int numslots = this.page.recordCount();
1126                for (int slot = 1; slot < numslots; slot++)
1127                {
1128                    child = this.getChildPageAtSlot(btree, slot);
1129                    child.printTree(btree);
1130                    child.release();
1131                    child = null;
1132                }
1133            }
1134            finally
1135            {
1136                if (child != null)
1137                    child.release();
1138            }
1139
1140            return;
1141        }
1142    }
1143
1144    /*
1145     * Private methods of BranchControlRow
1146     */
1147
1148    /**
1149     ** Add a level to the tree by moving the current branch-root page up
1150     ** one level and adding a new page as it's left child. On exit the
1151     ** current root page remains the root of the tree.
1152     ** <P>
1153     ** On entry, the current branch root page is expected to be latched.
1154     ** On exit, all latches will have been released.
1155     ** <P>
1156     ** Latch order:
1157     ** o ROOT: on entry current root is latched.
1158     ** No other latches should be held.
1159     ** o ROOT_OLDCHILD: Get and Latch root's left child page.
1160     ** o ROOT_NEWCHILD: Allocate a new branch page with latch.
1161     ** o Conditionally fix up the parent links on the pages pointed at
1162     ** by the newly allocated page. Loop through slots on ROOT_NEWCHILD,
1163     ** from left to right getting and releasing latches. Note that
1164     ** fixChildrensParents() must not latch the leftchild as ROOT_OLDCHILD
1165     ** is already latched.
1166     ** RESOLVE: (mikem) does order of release matter.
1167     ** o ROOT : released.
1168     ** o ROOT_NEWCHILD: released.
1169     ** o ROOT_OLDCHILD: released.
1170     **/
1171    private static void growRoot(
1172    OpenBTree open_btree,
1173    DataValueDescriptor[] template,
1174    BranchControlRow root)
1175        throws StandardException
1176    {
1177        ControlRow leftchild = null;
1178        BranchControlRow branch = null;
1179
1180        try
1181        {
1182            if (SanityManager.DEBUG)
1183            {
1184                SanityManager.ASSERT(root.page.isLatched());
1185                SanityManager.ASSERT(root.getIsRoot());
1186            }
1187
1188            // System.out.println("Growing root: control row = " + root);
1189 // System.out.println("Growing root: page = " + root.page);
1190
1191            // Get and latch the current root's left child. This will become
1192 // the left child on the new branch page (and the new
1193 // branch will become the left child of the root).
1194 leftchild = root.getLeftChild(open_btree);
1195
1196            // Allocate a new branch page. This one will take the
1197 // rows from the root, and remain at the old root's level.
1198 // Its parent is the root.
1199 branch =
1200                BranchControlRow.Allocate(
1201                    open_btree, leftchild, root.getLevel(), root);
1202
1203            // Copy all the index rows from the root to the new branch.
1204 // Purge the index rows from the root now that they're safely on the
1205 // new branch page. Leave the branch control row on the page.
1206 root.page.copyAndPurge(branch.page, 1, root.page.recordCount() - 1, 1);
1207
1208            // Set the root's left child to be the new branch.
1209 root.setLeftChild(branch);
1210
1211            // Move the root up a level
1212 root.setLevel(root.getLevel() + 1);
1213
1214            // The parent of the old root's children has changed.
1215 // It used to be page 0 (the old root, but now it's
1216 // the new branch page. Fix this up.
1217 branch.fixChildrensParents(open_btree, leftchild);
1218
1219            if (SanityManager.DEBUG)
1220            {
1221                if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck"))
1222                {
1223                    root.checkConsistency(open_btree, null, false);
1224                    branch.checkConsistency(open_btree, root, false);
1225                    leftchild.checkConsistency(open_btree, branch, false);
1226                }
1227            }
1228
1229            // At this point a unit of work in the split down the tree has
1230 // been performed in an internal transaction. This work must
1231 // be committed before any latches are released.
1232 open_btree.getXactMgr().commit();
1233
1234        }
1235        finally
1236        {
1237            // At the end of a growRoot() no latches are held, the caller must
1238 // restart at the root.
1239 //
1240 root.release();
1241            if (branch != null)
1242                branch.release();
1243            if (leftchild != null)
1244                leftchild.release();
1245        }
1246        return;
1247    }
1248    /**
1249     * Allocate a new leaf page to the conglomerate.
1250     *
1251     * @exception StandardException Standard exception policy.
1252     */
1253    private static BranchControlRow Allocate(
1254    OpenBTree open_btree,
1255    ControlRow leftchild,
1256    int level,
1257    ControlRow parent)
1258        throws StandardException
1259    {
1260        Page page = open_btree.container.addPage();
1261
1262        // Create a control row for the new page.
1263 BranchControlRow control_row =
1264            new BranchControlRow(
1265                open_btree, page, level,
1266                parent, false, leftchild.page.getPageNumber());
1267
1268        // Insert the control row on the page.
1269 byte insertFlag = Page.INSERT_INITIAL;
1270        insertFlag |= Page.INSERT_DEFAULT;
1271        page.insertAtSlot(
1272            Page.FIRST_SLOT_NUMBER,
1273            control_row.getRow(),
1274            (FormatableBitSet) null,
1275            (LogicalUndo)null,
1276            insertFlag, AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD);
1277
1278        // Page is returned latched.
1279 return(control_row);
1280    }
1281
1282    protected void setLeftChildPageno(long leftchild_pageno)
1283        throws StandardException
1284    {
1285        // Store the field.
1286 if (left_child_page == null)
1287            left_child_page = new SQLLongint(leftchild_pageno);
1288        else
1289            this.left_child_page.setValue(leftchild_pageno);
1290
1291        // Write the field through to the underlying row
1292 this.page.updateFieldAtSlot(
1293            CR_SLOT, CR_LEFTCHILD, this.left_child_page, null);
1294    }
1295
1296    protected void setLeftChild(ControlRow leftchild)
1297        throws StandardException
1298    {
1299        this.setLeftChildPageno(leftchild.page.getPageNumber());
1300    }
1301
1302    /**
1303     ** A branch page that has just been allocated as part
1304     ** of a split has index rows and a left child pointer
1305     ** that were copied from another page. The parent
1306     ** link on the corresponding pages will still point to
1307     ** the original page. This method fixes their parent
1308     ** pointers so that they point to the curren page like
1309     ** they're supposed to.
1310     ** <P>
1311     ** Note that maintaining the parent link is kind of a
1312     ** pain, and will slow down applications. It's only
1313     ** needed for consistency checks, so we may want to
1314     ** have implementations that don't bother to maintain it.
1315     ** <P)
1316     ** This
1317     **/
1318    private void fixChildrensParents(
1319    OpenBTree btree,
1320    ControlRow leftchild)
1321        throws StandardException
1322    {
1323        ControlRow child = null;
1324
1325        try
1326        {
1327            if (leftchild == null)
1328            {
1329                child = this.getLeftChild(btree);
1330                child.setParent(this.page.getPageNumber());
1331
1332                if (SanityManager.DEBUG)
1333                {
1334                    if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck"))
1335                    {
1336                        child.checkConsistency(btree, this, false);
1337                    }
1338                }
1339
1340                child.release();
1341                child = null;
1342            }
1343            else
1344            {
1345                leftchild.setParent(this.page.getPageNumber());
1346
1347                if (SanityManager.DEBUG)
1348                {
1349                    if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck"))
1350                    {
1351                        leftchild.checkConsistency(btree, this, false);
1352                    }
1353                }
1354            }
1355
1356            int numslots = this.page.recordCount();
1357            for (int slot = 1; slot < numslots; slot++)
1358            {
1359                child = getChildPageAtSlot(btree, slot);
1360                child.setParent(this.page.getPageNumber());
1361                if (SanityManager.DEBUG)
1362                {
1363                    if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck"))
1364                    {
1365                        child.checkConsistency(btree, this, false);
1366                    }
1367                }
1368
1369                child.release();
1370                child = null;
1371            }
1372        }
1373        finally
1374        {
1375            if (child != null)
1376                child.release();
1377        }
1378    }
1379
1380    private long getChildPageIdAtSlot(
1381    OpenBTree btree,
1382    int slot)
1383        throws StandardException
1384    {
1385        long child_page_id;
1386
1387        if (slot == 0)
1388        {
1389            child_page_id = this.getLeftChildPageno();
1390        }
1391        else
1392        {
1393            this.page.fetchFieldFromSlot(
1394                slot, btree.getConglomerate().nKeyFields, child_pageno_buf);
1395            child_page_id = child_pageno_buf.getLong();
1396        }
1397
1398        return(child_page_id);
1399    }
1400
1401    protected ControlRow getChildPageAtSlot(
1402    OpenBTree open_btree,
1403    int slot)
1404        throws StandardException
1405    {
1406        ControlRow child_control_row;
1407
1408        if (slot == 0)
1409        {
1410            child_control_row = this.getLeftChild(open_btree);
1411        }
1412        else
1413        {
1414            this.page.fetchFieldFromSlot(
1415                slot, open_btree.getConglomerate().nKeyFields,
1416                child_pageno_buf);
1417
1418            child_control_row =
1419                ControlRow.Get(open_btree, child_pageno_buf.getLong());
1420        }
1421
1422        return(child_control_row);
1423    }
1424
1425    /**
1426     * Return the left child pointer for the page.
1427     * <p>
1428     * Leaf pages don't have children, so they override this and return null.
1429     *
1430     * @return The page which is the leftmost child of this page.
1431     *
1432     * @param open_btree The open btree to associate latches/locks with.
1433     *
1434     * @exception StandardException Standard exception policy.
1435     **/
1436    public ControlRow getLeftChild(OpenBTree open_btree)
1437            throws StandardException
1438    {
1439         return(ControlRow.Get(open_btree, this.getLeftChildPageno()));
1440    }
1441
1442    /**
1443     * Return the right child pointer for the page.
1444     * <p>
1445     * Leaf pages don't have children, so they override this and return null.
1446     *
1447     * @return The page which is the rightmost child of this page.
1448     *
1449     * @param open_btree The open btree to associate latches/locks with.
1450     *
1451     * @exception StandardException Standard exception policy.
1452     **/
1453    protected ControlRow getRightChild(OpenBTree open_btree)
1454        throws StandardException
1455    {
1456        ControlRow right_child;
1457        int num_slots = this.page.recordCount();
1458
1459        // if num_slots is 1 then there are no branch rows, so just follow
1460 // the left page pointer, else if num_slots is > 1 then follow the
1461 // last branch row to find the rightmost child.
1462 right_child =
1463            (num_slots == 1 ?
1464                ControlRow.Get(open_btree, this.getLeftChildPageno()) :
1465                getChildPageAtSlot(open_btree, (num_slots - 1)));
1466
1467        return(right_child);
1468    }
1469
1470    /**
1471     ** Return the left child page number for the page. Leaf pages
1472     ** don't have left children, so they override this and return
1473     ** null.
1474     **/
1475    long getLeftChildPageno()
1476        throws StandardException
1477    {
1478        if (this.left_child_page == null)
1479        {
1480            this.left_child_page = new SQLLongint();
1481
1482            scratch_row[CR_LEFTCHILD] = this.left_child_page;
1483
1484            fetchDesc.setValidColumns(CR_LEFTCHILD_BITMAP);
1485            this.page.fetchFromSlot(
1486               (RecordHandle) null, CR_SLOT, scratch_row, fetchDesc, false);
1487        }
1488        return(left_child_page.getLong());
1489    }
1490
1491    /*
1492     * TypedFormat:
1493     */
1494
1495
1496    /**
1497        Return my format identifier.
1498
1499        @see org.apache.derby.iapi.services.io.TypedFormat#getTypeFormatId
1500    */
1501    public int getTypeFormatId()
1502    {
1503        return StoredFormatIds.ACCESS_BTREE_BRANCHCONTROLROW_V1_ID;
1504    }
1505
1506    /**
1507     * Return a new template for reading a data row from the current page.
1508     * <p>
1509     * Default implementation for rows which are the same as the conglomerates
1510     * template, sub-classes can alter if underlying template is different
1511     * (for instance branch rows add an extra field at the end).
1512     *
1513     * @return Newly allocated template.
1514     *
1515     * @exception StandardException Standard exception policy.
1516     **/
1517    public DataValueDescriptor[] getRowTemplate(OpenBTree open_btree)
1518        throws StandardException
1519    {
1520        return(BranchRow.createEmptyTemplate(
1521                    open_btree.getConglomerate()).getRow());
1522    }
1523
1524    /**
1525     ** The standard toString.
1526     **/
1527    public String JavaDoc toString()
1528    {
1529        if (SanityManager.DEBUG)
1530        {
1531            String JavaDoc string = super.toString();
1532
1533            try
1534            {
1535                string += "left child page = " + getLeftChildPageno() + ";";
1536                
1537            }
1538            catch (Throwable JavaDoc t)
1539            {
1540                string += "error encountered while doing ControlRow.toString()";
1541            }
1542
1543            return(string);
1544        }
1545        else
1546        {
1547            return(null);
1548        }
1549    }
1550}
1551
Popular Tags