ControlRow


1   /*
2   
3      Derby - Class org.apache.derby.impl.store.access.btree.ControlRow
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 java.io.PrintStream  ;
25  
26  import org.apache.derby.iapi.services.monitor.Monitor;
27  import org.apache.derby.iapi.services.sanity.SanityManager;
28  
29  import org.apache.derby.iapi.services.io.FormatIdUtil;
30  import org.apache.derby.iapi.services.io.Storable;
31  import org.apache.derby.iapi.services.io.TypedFormat;
32  
33  import org.apache.derby.iapi.error.StandardException;
34  
35  import org.apache.derby.iapi.store.access.conglomerate.LogicalUndo;
36  
37  import org.apache.derby.iapi.store.access.Qualifier;
38  import org.apache.derby.iapi.store.access.RowUtil;
39  
40  import org.apache.derby.iapi.store.raw.AuxObject;
41  import org.apache.derby.iapi.store.raw.FetchDescriptor;
42  import org.apache.derby.iapi.store.raw.Page;
43  import org.apache.derby.iapi.store.raw.ContainerHandle;
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  import org.apache.derby.impl.store.access.StorableFormatId;
50  
51  
52  import org.apache.derby.iapi.services.io.FormatableBitSet;
53  
54  import org.apache.derby.impl.store.access.conglomerate.ConglomerateUtil;
55  
56  /**
57  
58  Base class for leaf and branch control rows.
59  <P>
60  <B>Concurrency Notes</B>
61  <P>
62  All access through control rows is serialized by an exclusive latch on 
63  the page the control row is for.  The page is latched when the control
64  row is "gotten" (ControlRow#Get), and unlatched when the control row
65  is released (ControlRow#release).
66  <P>
67  <B>To Do List</B>
68  <UL>
69  <LI> <I>[NOTE1]</I>
70  The code is arranged to fault in fields from the row as necessary.
71  many of the fields of a control row are rarely used (left sibling, parent).
72  The accessors fault in the underlying column only when
73  requested by allocating the appropriate object and calling fetchFromSlot and
74  only fetching the requested field.
75  <LI> <I>[NOTE2]</I> 
76  Currently, all the fields of the control row are stored as StorableU8s
77  for simplicity.  This is too few bits to hold the long page numbers, and
78  too many to hold the version, level, and isRoot flag.  Some consideration
79  will have to be given to the appropriate storage format for these values.
80  <LI> <I>[NOTE3]</I>
81  The implementation relies on the existance of page "auxiliary" pointers 
82  which keep Object versions of the control row.
83  <P>
84  @see ControlRow#Get
85  @see ControlRow#release
86  
87  **/
88  
89  public abstract class ControlRow implements AuxObject, TypedFormat
90  {
91      /**
92       * Version indentifier of the control row within the page.  
93       * <p>
94       * This is the format id of the control row.  The format id is currently
95       * one of either StoredFormatIds.ACCESS_BTREE_LEAFCONTROLROW_ID or
96       * StoredFormatIds.ACCESS_BTREE_BRANCHCONTROLROW_ID.
97       **/
98      private StorableFormatId    version = null;
99  
100     /**
101      * Pointer to page which is "left" at the current level.
102      * <p>
103      * Currently all pages at a level are doubly linked.  The leftmost page
104      * in a level has a leftSiblingPageNumber == 
105      * ContainerHandle.INVALID_PAGE_NUMBER.  All key values on the page which
106      * is left must precede the first key value on the current page.
107      **/
108     private SQLLongint leftSiblingPageNumber;
109 
110     /**
111      * Pointer to page which is "right" at the current level.
112      * <p>
113      * Currently all pages at a level are doubly linked.  The rightmost page
114      * in a level has a rightSiblingPageNumber == 
115      * ContainerHandle.INVALID_PAGE_NUMBER.  All key values on the page which
116      * is right of the current page must follow the last key value on the 
117      * current page.
118      **/
119     private SQLLongint rightSiblingPageNumber;
120 
121     /**
122      * The parent page of the current page.
123      * <p>
124      * For consistency checking it is useful to maintain the parentPageNumber
125      * field of the current page.  The root page has a value of 
126      * ContainerHandle.INVALID_PAGE_NUMBER in it's parentPageNumber field.
127      * <p>
128      * RESOLVE (mikem) - we need to come up with some way to not maintain these,
129      * maybe by providing a property on secondary index or a different 2nd 
130      * index.
131      *
132      **/
133     private SQLLongint parentPageNumber; // for consistency checking
134 
135 
136     /**
137      * The level of the btree.
138      * <p>
139      * The leaf level of the btree is 0.  The first branch level (parent level
140      * of the leaf), is level 1.  The height of the btree is (level + 1).
141      * <p>
142      * The smallest btree is a one page btree with only a leaf, and no branch
143      * pages. 
144      **/
145     private SQLLongint level;
146 
147     /**
148      * Is this page the root of the btree?
149      * <p>
150      * Currently "1" if the page is the root page, else "0".
151      * <p>
152      * RESOLVE (mikem) When real datatype come about, this value should 
153      * probably be just a bit in some status word.
154      **/
155     private SQLLongint isRoot = null;
156 
157     /**
158      * A copy of the Conglomerate that describes the owning conglom.
159      * <p>
160      * This information is used during logical undo to get the type information
161      * so that rows can be compared and searched for.  We may be able to get
162      * away with a subset of the information stored in the conglomerate.
163      * <p>
164      * RESOLVE (mikem) - change this to only store the info on the root page.
165      **/
166     private BTree    btree = null;
167 
168     /**
169      * The page that this control row describes.
170      **/
171     protected Page page;
172 
173     /**
174      * The page that this control row describes.
175      **/
176     protected DataValueDescriptor row[];
177 
178     /**
179      * row used to replace fetchFieldFromSlot() calls.
180      **/
181     protected DataValueDescriptor[] scratch_row;
182 
183     /**
184      * FetchDescriptor used to replace fetchFieldFromSlot() calls.
185      **/
186     protected FetchDescriptor   fetchDesc;
187 
188     /**
189      * In memory hint about whether to use the last_search_result hint during
190      * search.
191      **/
192     transient protected boolean use_last_search_result_hint = false;
193 
194     /**
195      * In memory hint about where to begin the binary search to find a key
196      * on the the current control page.
197      **/
198     transient protected int last_search_result = 0;
199 
200     /**
201      * Column number assignments for columns of the control row.
202      * <p>
203      * The control row is stored as the first row in a btree page.  The row
204      * is an array of columns.  The Control row columns are the columns numbered
205      * from ControlRow.CR_COLID_FIRST through ControlRow.CR_COLID_LAST.  The
206      * classes which implement the concrete derived classes of ControlRow may
207      * add columns to the control row, but they must be added after the 
208      * ControlRow columns.
209      **/
210     protected static final int CR_COLID_FIRST       = 0;
211     protected static final int CR_VERSION_COLID     = CR_COLID_FIRST + 0;
212     protected static final int CR_LEFTSIB_COLID     = CR_COLID_FIRST + 1;
213     protected static final int CR_RIGHTSIB_COLID    = CR_COLID_FIRST + 2;
214     protected static final int CR_PARENT_COLID      = CR_COLID_FIRST + 3;
215     protected static final int CR_LEVEL_COLID       = CR_COLID_FIRST + 4;
216     protected static final int CR_ISROOT_COLID      = CR_COLID_FIRST + 5;
217     protected static final int CR_CONGLOM_COLID     = CR_COLID_FIRST + 6;
218     protected static final int CR_COLID_LAST        = CR_CONGLOM_COLID;
219     protected static final int CR_NCOLUMNS          = CR_COLID_LAST + 1;
220 
221     /**
222      * bit sets used to fetch single columns at a time.
223      **/
224     protected static final FormatableBitSet   CR_VERSION_BITSET = 
225         new FormatableBitSet(CR_VERSION_COLID + 1);
226     protected static final FormatableBitSet   CR_LEFTSIB_BITSET = 
227         new FormatableBitSet(CR_LEFTSIB_COLID + 1);
228     protected static final FormatableBitSet   CR_RIGHTSIB_BITSET =
229         new FormatableBitSet(CR_RIGHTSIB_COLID + 1);
230     protected static final FormatableBitSet   CR_PARENT_BITSET =
231         new FormatableBitSet(CR_PARENT_COLID + 1);
232     protected static final FormatableBitSet   CR_LEVEL_BITSET =
233         new FormatableBitSet(CR_LEVEL_COLID + 1);
234     protected static final FormatableBitSet   CR_ISROOT_BITSET =
235         new FormatableBitSet(CR_ISROOT_COLID + 1);
236     protected static final FormatableBitSet   CR_CONGLOM_BITSET =
237         new FormatableBitSet(CR_CONGLOM_COLID + 1);
238 
239 
240     /**
241      * Values passed in the flag argument to splitFor.
242      **/
243     /* row causing split would be last row on leaf page */
244     public static final int SPLIT_FLAG_LAST_ON_PAGE      = 0x000000001;
245     /* row causing split would be last row in table */
246     public static final int SPLIT_FLAG_LAST_IN_TABLE     = 0x000000002;
247     /* row causing split would be first row on page */
248     public static final int SPLIT_FLAG_FIRST_ON_PAGE     = 0x000000004;
249     /* row causing split would be first row in table */
250     public static final int SPLIT_FLAG_FIRST_IN_TABLE    = 0x000000008;
251 
252     /**
253      * The slot at which all control rows reside.
254      **/
255     protected static final int CR_SLOT = 0;
256 
257     /*
258     ** Constructors of ControlRow
259     */
260 
261     static 
262     {
263         CR_VERSION_BITSET.set(CR_VERSION_COLID);
264         CR_LEFTSIB_BITSET.set(CR_LEFTSIB_COLID);
265         CR_RIGHTSIB_BITSET.set(CR_RIGHTSIB_COLID);
266         CR_PARENT_BITSET.set(CR_PARENT_COLID);
267         CR_LEVEL_BITSET.set(CR_LEVEL_COLID);
268         CR_ISROOT_BITSET.set(CR_ISROOT_COLID);
269         CR_CONGLOM_BITSET.set(CR_CONGLOM_COLID);
270     }
271 
272     /**
273      * No arg constructor.
274      * <p>
275      * GetControlRowForPage() will call this constructor when it uses the 
276      * monitor to create a control row dynamically given a given format id.
277      **/
278     protected ControlRow()
279     {
280         this.scratch_row = 
281             new DataValueDescriptor[getNumberOfControlRowColumns()];
282 
283         this.fetchDesc   = 
284             new FetchDescriptor(
285                 this.scratch_row.length, (FormatableBitSet) null, (Qualifier[][]) null);
286     }
287 
288     /**
289      * Constructor for making a new control row as part of allocating a new
290      * page.  Fills in all the fields but does not write them anywhere.
291      * <p>
292      * <P>
293      * Changes to this constructor will probably require changes to the
294      * corresponding accessor(s).
295      *
296      * @param btree      Static information about the btree.
297      * @param page       The page described by this control row.
298      * @param parent     The parent page of this page, "null" if this page is 
299      *                   root or if not maintaining parent links.
300      * @param isRoot     Is this page the root of the tree?
301      *
302      *
303      * @exception StandardException Standard exception policy.
304      **/
305     protected ControlRow(
306     OpenBTree         btree,
307     Page              page, 
308     int               level, 
309     ControlRow        parent,
310     boolean           isRoot
311     )
312         throws StandardException
313     {
314         // The caller is expected to have latched the pages.
315         if (SanityManager.DEBUG)
316         {
317             SanityManager.ASSERT(page.isLatched());
318             SanityManager.ASSERT(parent == null || parent.page.isLatched());
319         }
320 
321         // Maintain which page this control row describes.
322         this.page = page;
323 
324         // Page numbers start out "invalid".  Presumably the caller will
325         // link the page into a page chain as one of its next steps.
326         leftSiblingPageNumber  = 
327             new SQLLongint(btree.container.INVALID_PAGE_NUMBER);
328         rightSiblingPageNumber = 
329             new SQLLongint(btree.container.INVALID_PAGE_NUMBER);
330 
331         // Remember the parent if there is one and we're remembering parents.
332         parentPageNumber = new SQLLongint( 
333             (parent == null ?  
334                  btree.container.INVALID_PAGE_NUMBER : 
335                  parent.page.getPageNumber()));
336 
337         // All pages start out not being root pages.  The caller will setIsRoot
338         // if this is going to be a root page. Zero means false - see 
339         // getIsRoot/setIsRoot.
340         this.isRoot = new SQLLongint(isRoot ? 1 : 0);
341 
342         // set the rest of the state, as passed in.
343         this.level   = new SQLLongint(level);
344         this.version = new StorableFormatId(getTypeFormatId());
345 
346         // If it is a root page then store the real btree conglomerate, if it
347         // is not a root page then set up an "empty" btree conglomerate which
348         // will be stored as "null".
349         this.btree = 
350             (isRoot ? 
351              btree.getConglomerate() : 
352              (BTree) Monitor.newInstanceFromIdentifier(
353                 btree.getConglomerate().getTypeFormatId()));
354 
355         // Initialize the object array to be used for interacting with raw
356         // store to insert, fetch, and update the control row.
357         this.row = new DataValueDescriptor[getNumberOfControlRowColumns()];
358         this.row[CR_VERSION_COLID]  = this.version;
359         this.row[CR_LEFTSIB_COLID]  = this.leftSiblingPageNumber;
360         this.row[CR_RIGHTSIB_COLID] = this.rightSiblingPageNumber;
361         this.row[CR_PARENT_COLID]   = this.parentPageNumber;
362         this.row[CR_LEVEL_COLID]    = this.level;
363         this.row[CR_ISROOT_COLID]   = this.isRoot;
364         this.row[CR_CONGLOM_COLID]  = this.btree;
365 
366 
367         // Make the control row the aux object for the page so control row
368         // getters end up with the same row.
369         page.setAuxObject(this);
370     }
371 
372     /**
373      * Constructor for making a control row for an existing page.
374      * <p>
375      * Not all the fields are filled in; their values will get faulted in from 
376      * the page as necessary.
377      * <p>
378      * Classes which extend ControlRow must delegate to this constructor
379      * and may want to override it as well.
380      * Changes to this constructor will probably require changes to the
381      * corresponding accessor(s).
382      *
383      * @param container  Open container 
384      * @param page       The page described by this control row.
385      *
386      * @exception StandardException Standard exception policy.
387      **/
388     protected ControlRow(ContainerHandle container, Page page)
389         throws StandardException
390     {
391         System.out.println("ControlRow construct 2.");
392 
393         // The caller is expected to have latched the pages.
394         if (SanityManager.DEBUG)
395             SanityManager.ASSERT(page.isLatched());
396 
397         // Remember the page.
398         this.page = page;
399 
400         // The rest of the fields are left null; they'll get faulted
401         // in if/when necessary.  See the accessors.
402     }
403 
404     /* Private/Protected methods of ControlRow: */
405 
406     /**
407      * Get version of the control row.
408      * <p>
409      * Returns the version of the control row, faulting it in from the page
410      * if necessary.
411      *
412      * @return version of the control row.
413      *
414      * @exception  StandardException  Standard exception policy.
415      **/
416     protected int getVersion()
417         throws StandardException
418     {
419         if (this.version == null)
420         {
421             // Fault in the version.
422             this.version = new StorableFormatId();
423 
424             scratch_row[CR_VERSION_COLID] = this.version;
425 
426             fetchDesc.setValidColumns(CR_VERSION_BITSET);
427 
428             this.page.fetchFromSlot(
429                (RecordHandle) null, CR_SLOT, scratch_row, fetchDesc, false); 
430         }
431         return this.version.getValue();
432     }
433 
434     /**
435      * Set version of the control row.
436      * <p>
437      * Sets the version of the control row.  Updates both the in-memory 
438      * control row and the disk copy.
439      *
440      * @exception  StandardException  Standard exception policy.
441      **/
442     protected void setVersion(int version)
443         throws StandardException
444     {
445         // Store the field.
446         if (this.version == null)
447             this.version = new StorableFormatId();
448         this.version.setValue(version);
449 
450         // Write the field through to the underlying row.
451         this.page.updateFieldAtSlot(
452             CR_SLOT, CR_VERSION_COLID, this.version, null);
453     }
454 
455     /**
456      * Get the control row for this page's left sibling, or null if there is no
457      * left sibling (which probably means it's the leftmost page at its level).
458      * Since right-to-left traversal of an index level  is deadlock-prone, this 
459      * method will only get get the left sibling if it can latch it without
460      * waiting.
461      *
462      * @exception WaitError if the latch request would have had to wait.
463      *
464      * @exception StandardException Standard exception policy.
465      **/
466     public ControlRow getLeftSibling(OpenBTree btree)
467         throws StandardException, WaitError
468     {
469         ControlRow cr;
470         
471         long pageno = this.getleftSiblingPageNumber();
472 
473         // Is there a left sibling?
474         if (pageno == ContainerHandle.INVALID_PAGE_NUMBER)
475             return null;
476 
477         // Try to get the control row without waiting
478         cr = ControlRow.GetNoWait(btree, pageno);
479         if (cr == null)
480             throw new WaitError();
481 
482         return cr;
483     }
484 
485     protected void setLeftSibling(ControlRow leftsib)
486         throws StandardException
487     {
488         long left_sib_pageno = 
489             (leftsib == null ? ContainerHandle.INVALID_PAGE_NUMBER : 
490                                leftsib.page.getPageNumber());
491         
492         // Store the field.
493         if (leftSiblingPageNumber == null)
494             leftSiblingPageNumber = new SQLLongint(left_sib_pageno);
495         else
496             this.leftSiblingPageNumber.setValue(left_sib_pageno);
497 
498         // Write the field through to the underlying row
499         try
500         {
501             this.page.updateFieldAtSlot(
502                 CR_SLOT, CR_LEFTSIB_COLID, this.leftSiblingPageNumber, null);
503         }
504         catch (StandardException se)
505         {
506             // Since this is an update of a fixed length field it should 
507             // never fail, but it has happened enough that an assert helps
508             // with debugging.
509             if (SanityManager.DEBUG)
510             {
511                 SanityManager.THROWASSERT(
512                     "setLeftSibling got an exception: " + se +
513                     "control_row = " + this +
514                     "trying to update field number " + CR_LEFTSIB_COLID + 
515                     "to new value " + this.leftSiblingPageNumber);
516             }
517             throw(se);
518         }
519     }
520 
521     /**
522     Return the control row for this page's right sibling.  Unlike getting
523     the left sibling, it's ok to wait for the right sibling latch since
524     left-to-right is the deadlock-free ordering.
525 
526     @exception StandardException Standard exception policy.
527     **/
528     protected ControlRow getRightSibling(OpenBTree open_btree)
529         throws StandardException
530     {
531         long pageno = this.getrightSiblingPageNumber();
532 
533         // Return the control row for the page.
534         if (pageno == ContainerHandle.INVALID_PAGE_NUMBER)
535             return null;
536         else
537             return ControlRow.Get(open_btree, pageno);
538     }
539 
540     // This method will have to update the row.
541     protected void setRightSibling(ControlRow rightsib)
542         throws StandardException
543     {
544         long right_sib_pageno = 
545             (rightsib == null ? ContainerHandle.INVALID_PAGE_NUMBER : 
546                                 rightsib.page.getPageNumber());
547         
548         // Store the field.
549         if (rightSiblingPageNumber == null)
550             rightSiblingPageNumber = new SQLLongint(right_sib_pageno);
551         else
552             this.rightSiblingPageNumber.setValue(right_sib_pageno);
553 
554         // Write the field through to the underlying row
555         try
556         {
557         this.page.updateFieldAtSlot(
558             CR_SLOT, CR_RIGHTSIB_COLID, this.rightSiblingPageNumber, null);
559         }
560         catch (StandardException se)
561         {
562             // Since this is an update of a fixed length field it should 
563             // never fail, but it has happened enough that an assert helps
564             // with debugging.
565 
566             if (SanityManager.DEBUG)
567             {
568                 SanityManager.THROWASSERT(
569                     "setRightSibling got an exception: " + se +
570                     "control_row = " + this +
571                     "trying to update field number " + CR_RIGHTSIB_COLID + 
572                     "to new value " + this.rightSiblingPageNumber);
573             }
574             throw(se);
575         }
576     }
577 
578     /**
579     Get the page number of the left sibling. Fault it's value in if it
580     hasn't been yet.
581 
582     @exception StandardException Standard exception policy.
583     **/
584     public long getleftSiblingPageNumber()
585         throws StandardException
586     {
587         if (this.leftSiblingPageNumber == null)
588         {
589             // Fault in the page number.
590             this.leftSiblingPageNumber = new SQLLongint();
591 
592             if (SanityManager.DEBUG)
593                 SanityManager.ASSERT(scratch_row != null);
594 
595             scratch_row[CR_LEFTSIB_COLID] = this.leftSiblingPageNumber;
596 
597             fetchDesc.setValidColumns(CR_LEFTSIB_BITSET);
598             this.page.fetchFromSlot(
599                (RecordHandle) null, CR_SLOT, scratch_row, fetchDesc, false); 
600 
601         }
602 
603         return(leftSiblingPageNumber.getLong());
604     }
605 
606     /**
607     Get the page number of the right sibling. Fault it's value in if it
608     hasn't been yet.
609 
610     @exception StandardException Standard exception policy.
611     **/
612     protected long getrightSiblingPageNumber()
613         throws StandardException
614     {
615         if (this.rightSiblingPageNumber == null)
616         {
617             // Fault in the page number.
618             this.rightSiblingPageNumber = new SQLLongint();
619 
620             scratch_row[CR_RIGHTSIB_COLID] = this.rightSiblingPageNumber;
621 
622             fetchDesc.setValidColumns(CR_RIGHTSIB_BITSET);
623             this.page.fetchFromSlot(
624                (RecordHandle) null, CR_SLOT, scratch_row, fetchDesc, false); 
625         }
626 
627         return(rightSiblingPageNumber.getLong());
628     }
629 
630     /**
631     Get the page number of the parent, if it's being maintained.
632     Note that there is intentionally no way to get the control
633     row for the parent page - the b-tree code NEVER traverses
634     up the tree, even in consistency checks.
635 
636     @exception StandardException Standard exception policy.
637     **/
638     protected long getParentPageNumber()
639         throws StandardException
640     {
641         if (this.parentPageNumber == null)
642         {
643             // Fault in the page number.
644             this.parentPageNumber = new SQLLongint();
645 
646             scratch_row[CR_PARENT_COLID] = this.parentPageNumber;
647 
648             fetchDesc.setValidColumns(CR_PARENT_BITSET);
649             this.page.fetchFromSlot(
650                (RecordHandle) null, CR_SLOT, scratch_row, fetchDesc, false); 
651         }
652 
653         // See NOTE3 about converting from int to long.
654         long pageno = parentPageNumber.getLong();
655         return pageno;
656     }
657     
658     void setParent(long parent)
659         throws StandardException
660     {
661         // Store the field.
662         if (parentPageNumber == null)
663             parentPageNumber = new SQLLongint();
664         this.parentPageNumber.setValue(parent);
665 
666         // Write the field through to the underlying row
667         try
668         {
669             this.page.updateFieldAtSlot(
670                 CR_SLOT, CR_PARENT_COLID, this.parentPageNumber, null);
671         }
672         catch (StandardException se)
673         {
674             // Since this is an update of a fixed length field it should 
675             // never fail, but it has happened enough that an assert helps
676             // with debugging.
677 
678             if (SanityManager.DEBUG)
679             {
680                 SanityManager.THROWASSERT(
681                     "setParent got an exception: " + se +
682                     "control_row = " + this +
683                     "trying to update field number " + CR_PARENT_COLID + 
684                     "to new value " + this.parentPageNumber);
685             }
686             throw(se);
687         }
688 
689         return;
690     }
691 
692     protected int getLevel()
693         throws StandardException
694     {
695         if (this.level == null)
696         {
697             // Fault in the level
698             this.level = new SQLLongint();
699 
700             scratch_row[CR_LEVEL_COLID] = this.level;
701 
702             fetchDesc.setValidColumns(CR_LEVEL_BITSET);
703             this.page.fetchFromSlot(
704                (RecordHandle) null, CR_SLOT, scratch_row, fetchDesc, false); 
705         }
706 
707         return((int) this.level.getLong());
708     }
709 
710     protected void setLevel(int newlevel)
711         throws StandardException
712     {
713         // Store the field.
714         if (this.level == null)
715             this.level = new SQLLongint();
716         this.level.setValue((long) newlevel);
717 
718         // Write the field through to the underlying row.
719         this.page.updateFieldAtSlot(CR_SLOT, CR_LEVEL_COLID, this.level, null);
720     }
721 
722     protected boolean getIsRoot()
723         throws StandardException
724     {
725         // convert 1 to true, 0 to false;
726         
727         if (this.isRoot == null)
728         {
729             // Fault in the level
730             this.isRoot = new SQLLongint();
731 
732             scratch_row[CR_ISROOT_COLID] = this.isRoot;
733 
734             fetchDesc.setValidColumns(CR_ISROOT_BITSET);
735             this.page.fetchFromSlot(
736                (RecordHandle) null, CR_SLOT, scratch_row, fetchDesc, false); 
737         }
738 
739         return((this.isRoot.getLong() == 1));
740     }
741     
742     protected void setIsRoot(boolean isRoot)
743         throws StandardException
744     {
745         // RESOLVE (mmm) - need to store more efficiently //
746 
747         // Store the field.
748         if (this.isRoot == null)
749             this.isRoot = new SQLLongint();
750 
751         this.isRoot.setValue((isRoot) ? 1 : 0);
752 
753         // Write the field through to the underlying row.
754         this.page.updateFieldAtSlot(
755             CR_SLOT, CR_ISROOT_COLID, this.isRoot, null);
756     }
757 
758     /**
759      * Get format id information for row on page.
760      * <p>
761      * Returns the format id information for a row on the page. faulting it 
762      * in from the page if necessary.
763      *
764      * @return format id of a row on the page.
765      *
766      * @exception  StandardException  Standard exception policy.
767      **/
768     public BTree getConglom(int format_id)
769         throws StandardException
770     {
771 
772         if (SanityManager.DEBUG)
773         {
774             // this call is only valid on root pages.  If called on non
775             // root pages it will return a "null" conglom object.
776             SanityManager.ASSERT(
777                 (this.page.getPageNumber() == BTree.ROOTPAGEID) && getIsRoot());
778         }
779 
780         if (this.btree == null)
781         {
782             // use format id to create empty instance of Conglomerate class
783             this.btree = (BTree) Monitor.newInstanceFromIdentifier(format_id);
784 
785             scratch_row[CR_CONGLOM_COLID] = this.btree;
786 
787             fetchDesc.setValidColumns(CR_CONGLOM_BITSET);
788             this.page.fetchFromSlot(
789                (RecordHandle) null, CR_SLOT, scratch_row, fetchDesc, false); 
790         }
791         return this.btree;
792     }
793 
794     /**
795      * Set the conglomerate field in the btree.
796      * <p>
797      * Sets the btree field of the control row.  Updates just the disk copy. 
798      *
799      * @exception  StandardException  Standard exception policy.
800      **/
801     private void setConglom(BTree btree)
802         throws StandardException
803     {
804         // Store the field.  Delay faulting value into object until getConlgom()
805         // call, which in general only happens during recovery.
806 
807         // Write the field through to the underlying row.
808         this.page.updateFieldAtSlot(CR_SLOT, CR_CONGLOM_COLID, btree, null);
809     }
810 
811     /*
812     ** Methods for getting control rows from pages.
813     */
814 
815     /**
816       Get the control row from the given page in the b-tree.
817       The returned control row will be of the correct type
818       for the page (i.e., either a LeafControlRow or a
819       BranchControlRow).
820 
821     @exception StandardException Standard exception policy.
822      **/
823     public static ControlRow Get(OpenBTree open_btree, long pageNumber)
824         throws StandardException
825     {
826         return(ControlRow.Get(open_btree.container, pageNumber));
827     }
828 
829     public static ControlRow Get(ContainerHandle container, long pageNumber)
830         throws StandardException
831     {
832         if (SanityManager.DEBUG)
833         {
834             SanityManager.ASSERT(container != null, 
835                 "ControlRow.Get() is being called on a closed container.");
836         }
837 
838         // Get the page, waiting if necessary.  The page is returned latched.
839         Page page = container.getPage(pageNumber);
840 
841         if (SanityManager.DEBUG)
842         {
843             if (page == null)
844                 SanityManager.THROWASSERT(
845                     "No page at pagenumber: " + pageNumber +
846                     "; ContainerHandle = "    + container);
847         }
848 
849         // Return the corresponding control row.
850         return GetControlRowForPage(container, page);
851     }
852 
853     /**
854     Get the control row for the given page if the latch on the
855     page can be obtained without waiting, else return null.
856 
857     @exception StandardException Standard exception policy.
858     **/
859     public static ControlRow GetNoWait(
860     OpenBTree       open_btree, 
861     long            pageNumber)
862         throws StandardException
863     {
864         // Try to get the page without waiting.  If we would have
865         // to wait, return null.
866         Page page = open_btree.container.getUserPageNoWait(pageNumber);
867         if (page == null)
868             return null; 
869 
870         // Got the page without waiting.  Return the corresponding
871         // control row.
872         return GetControlRowForPage(open_btree.container, page);
873     }
874 
875     protected static ControlRow GetControlRowForPage(
876     ContainerHandle container,
877     Page            page)
878         throws StandardException
879     {
880         ControlRow cr = null;
881 
882         // See if the control row is still cached with the page
883         // If so, just use the cached control row.
884         AuxObject auxobject = page.getAuxObject();
885         if (auxobject != null)
886             return (ControlRow) auxobject;
887 
888         if (SanityManager.DEBUG)
889             SanityManager.ASSERT(page.recordCount() >= 1);
890 
891         // No cached control row, so create a new one.
892         
893         // Use the version field to determine the type of the row to
894         // create.  This routine depends on the version field being the same
895         // number column in all control rows.
896         
897         StorableFormatId version = new StorableFormatId();
898 
899         DataValueDescriptor[] version_ret = new DataValueDescriptor[1];
900         
901         version_ret[0] = version;
902 
903         // TODO (mikem) - get rid of this new.
904 
905         page.fetchFromSlot(
906            (RecordHandle) null, CR_SLOT, version_ret,
907            new FetchDescriptor(1, CR_VERSION_BITSET, (Qualifier[][]) null), 
908            false); 
909 
910         // use format id to create empty instance of right Conglomerate class
911         cr = (ControlRow) Monitor.newInstanceFromIdentifier(version.getValue());
912         cr.page = page;
913 
914         // call page specific initialization.
915         cr.ControlRowInit();
916 
917         // cache this Control row with the page in the cache.
918         page.setAuxObject(cr);
919 
920         return(cr);
921     }
922 
923     /**
924     Release this control row's resources.
925     **/
926     public void release()
927     {
928         if (SanityManager.DEBUG)
929             SanityManager.ASSERT(page != null);
930 
931         if (page != null)
932             page.unlatch();
933 
934         // It might be nice to set the page object to null, but
935         // since there might be multiple control rows on this
936         // page, we'd have to maintain a use count.  Rather than
937         // doing that we'll let the garbage collector earn its
938         // keep.  We are also expecting that the raw store will
939         // throw errors if we attempt to use an unlatched page.
940     }
941 
942     /**
943     Search this index page.
944     <P>
945     This method is very performance sensitive.  It is the intention that no
946     object allocations occur during the execution of this method.
947     <P>
948     This method performs a binary search on the page and finds the entry i on
949     the page such that entry[i] <= key < entry[i+1].  The result of the search
950     is filled into the passed in params structure.
951 
952     @param params the parameters of the search
953 
954     @exception StandardException could be thrown by underlying raw store 
955     operations.
956 
957     @see SearchParameters
958     **/
959     protected void searchForEntry(SearchParameters params)
960         throws StandardException
961     {
962         if (SanityManager.DEBUG)
963         {
964             // System.out.println("searchForEntry() enter: params:" + params);
965             // System.out.println("searchForEntry() enter: this:"   + this);
966             // System.out.println("searchForEntry() enter: this page:"   + debugPage(params.btree));
967         }
968 
969 
970         // leftrange and rightrange indicates the range of slots to search.
971         // The range starts as all the slots on the page not including slot
972         // 0 which is the control row.
973         int leftrange  = 1;
974         int rightrange = page.recordCount() - 1;
975 
976         // leftslot and rightslot if non-zero, mean that the key has been
977         // compared to the row at that slot.  If non-zero the key must be
978         // greater than the key at leftslot and the key must be lest than
979         // the key at rightslot.
980         int leftslot  = 0;
981         int rightslot = rightrange + 1;
982 
983         int midslot;
984         int compare_ret;
985 
986         // search until you either exactly find the key, or you have 
987         // compared 2 adjacent rows and found the value must exist between
988         // the 2.
989 
990 
991         if (this.use_last_search_result_hint)
992         {
993             // make sure to set midslot to point to somwhere in the legal range.
994             midslot = 
995                 ((this.last_search_result == 0) ? 1 : this.last_search_result);
996 
997             if (midslot > rightrange)
998                 midslot = rightrange;
999         }
1000        else
1001        {
1002            // if we don't think we have a good hint where to start the search
1003            // just go to the middle.
1004            midslot = (leftrange + rightrange) / 2;
1005        }
1006
1007        if (SanityManager.DEBUG)
1008        {
1009            if ((leftslot != (rightslot - 1)) &&
1010                !(midslot >= leftrange && midslot <= rightrange))
1011            {
1012                SanityManager.THROWASSERT(
1013                    "midslot = "     + midslot +
1014                    ";leftrange = "  + leftrange +
1015                    ";rightrange = " + rightrange);
1016            }
1017        }
1018
1019        
1020        while (leftslot != (rightslot - 1))
1021        {
1022            // Compare the index row to the key.
1023            compare_ret = 
1024                CompareIndexRowFromPageToKey(
1025                    this,
1026                    midslot,
1027                    params.template, params.searchKey, 
1028                    params.btree.getConglomerate().nUniqueColumns, 
1029                    params.partial_key_match_op,
1030                    params.btree.getConglomerate().ascDescInfo);
1031
1032            if (compare_ret == 0)
1033            {
1034                // Found exact match
1035                params.resultSlot = midslot;
1036                params.resultExact = true;
1037
1038                // update the hints based on result of the search.
1039                use_last_search_result_hint = 
1040                    (midslot == this.last_search_result) ? true : false;
1041                this.last_search_result = midslot;
1042
1043                return;
1044            }
1045            else if (compare_ret > 0)
1046            {
1047                // key falls to the left of midslot
1048                rightslot  = midslot;
1049                rightrange = midslot - 1;
1050            }
1051            else
1052            {
1053                // key falls to the right of midslot
1054                leftslot   = midslot;
1055                leftrange  = midslot + 1;
1056            }
1057
1058            midslot = (leftrange + rightrange) / 2;
1059            //midslot = (leftrange + rightrange) >> 1;
1060        }
1061
1062        // update the hints based on result of the search.
1063        this.use_last_search_result_hint = 
1064            (leftslot == this.last_search_result);
1065        this.last_search_result = leftslot;
1066
1067        // no exact match found, leftslot will point at the slot on the
1068        // page just before where the row should be inserted.  In the case
1069        // where the key is before rows on the page then leftslot will be
1070        // 0 (an empty page is a special case of this).
1071        if (SanityManager.DEBUG)
1072        {
1073            if (leftslot != rightslot - 1)
1074                SanityManager.THROWASSERT(
1075                    "leftslot = " + leftslot + "; rightslot = " + rightslot);
1076        }
1077
1078        params.resultSlot  = leftslot;
1079        params.resultExact = false;
1080
1081        if (SanityManager.DEBUG)
1082        {
1083            // System.out.println("searchForEntry() exit: params:" + params);
1084        }
1085
1086        return;
1087    }
1088
1089    protected void searchForEntryBackward(SearchParameters params)
1090        throws StandardException
1091    {
1092        if (SanityManager.DEBUG)
1093        {
1094            // System.out.println("searchForEntry() enter: params:" + params);
1095            // System.out.println("searchForEntry() enter: this:"   + this);
1096            // System.out.println("searchForEntry() enter: this page:"   + debugPage(params.btree));
1097        }
1098
1099
1100        // leftrange and rightrange indicates the range of slots to search.
1101        // The range starts as all the slots on the page not including slot
1102        // 0 which is the control row.
1103        int leftrange  = 1;
1104        int rightrange = page.recordCount() - 1;
1105
1106        // leftslot and rightslot if non-zero, mean that the key has been
1107        // compared to the row at that slot.  If non-zero the key must be
1108        // greater than the key at leftslot and the key must be lest than
1109        // the key at rightslot.
1110        int leftslot  = 0;
1111        int rightslot = rightrange + 1;
1112
1113        int midslot;
1114        int compare_ret;
1115
1116        // search until you either exactly find the key, or you have 
1117        // compared 2 adjacent rows and found the value must exist between
1118        // the 2.
1119
1120
1121        if (this.use_last_search_result_hint)
1122        {
1123            // make sure to set midslot to point to somwhere in the legal range.
1124            midslot = 
1125                ((this.last_search_result == 0) ? 1 : this.last_search_result);
1126
1127            if (midslot > rightrange)
1128                midslot = rightrange;
1129        }
1130        else
1131        {
1132            // if we don't think we have a good hint where to start the search
1133            // just go to the middle.
1134            midslot = (leftrange + rightrange) / 2;
1135        }
1136
1137        if (SanityManager.DEBUG)
1138        {
1139            if ((leftslot != (rightslot - 1)) &&
1140                !(midslot >= leftrange && midslot <= rightrange))
1141            {
1142                SanityManager.THROWASSERT(
1143                    "midslot = "     + midslot +
1144                    ";leftrange = "  + leftrange +
1145                    ";rightrange = " + rightrange);
1146            }
1147        }
1148
1149        
1150        while (leftslot != (rightslot - 1))
1151        {
1152            // Compare the index row to the key.
1153            compare_ret = 
1154                CompareIndexRowFromPageToKey(
1155                    this,
1156                    midslot,
1157                    params.template, params.searchKey, 
1158                    params.btree.getConglomerate().nUniqueColumns, 
1159                    params.partial_key_match_op,
1160                    params.btree.getConglomerate().ascDescInfo);
1161
1162            if (compare_ret == 0)
1163            {
1164                // Found exact match
1165                params.resultSlot = midslot;
1166                params.resultExact = true;
1167
1168                // update the hints based on result of the search.
1169                use_last_search_result_hint = 
1170                    (midslot == this.last_search_result) ? true : false;
1171                this.last_search_result = midslot;
1172
1173                return;
1174            }
1175            else if (compare_ret > 0)
1176            {
1177                // key falls to the left of midslot
1178                rightslot  = midslot;
1179                rightrange = midslot - 1;
1180            }
1181            else
1182            {
1183                // key falls to the right of midslot
1184                leftslot   = midslot;
1185                leftrange  = midslot + 1;
1186            }
1187
1188            midslot = (leftrange + rightrange) / 2;
1189            //midslot = (leftrange + rightrange) >> 1;
1190        }
1191
1192        // update the hints based on result of the search.
1193        this.use_last_search_result_hint = 
1194            (leftslot == this.last_search_result);
1195        this.last_search_result = leftslot;
1196
1197        // no exact match found, leftslot will point at the slot on the
1198        // page just before where the row should be inserted.  In the case
1199        // where the key is before rows on the page then leftslot will be
1200        // 0 (an empty page is a special case of this).
1201        if (SanityManager.DEBUG)
1202        {
1203            if (leftslot != rightslot - 1)
1204                SanityManager.THROWASSERT(
1205                    "leftslot = " + leftslot + "; rightslot = " + rightslot);
1206        }
1207
1208        params.resultSlot  = leftslot;
1209        params.resultExact = false;
1210
1211        if (SanityManager.DEBUG)
1212        {
1213            // System.out.println("searchForEntry() exit: params:" + params);
1214        }
1215
1216        return;
1217    }
1218
1219    /**
1220    Compare two orderable rows, considering nCompareCols, and return -1, 0, or 1
1221    depending on whether the first row (indexrow) is less than, equal to, or 
1222    greater than the second (key).  The key may have fewer columns present 
1223    than nCompareCols.
1224
1225    In such a case, if all the columns of the partial key match all of the 
1226    corresponding columns in the index row, then the value passed in in 
1227    partialKeyOrder is returned.  The caller should pass in partialKeyOrder=1 
1228    if the index rows which match a partial key should be considered to be 
1229    greater than the partial key, and -1 if they should be considered to be 
1230    less.
1231
1232    This routine only reads objects off the page if it needs them, so if a 
1233    multi-part key differs in the first column the subsequent columns are not
1234    read.
1235
1236    @param indexpage Controlrow of page to get target row from.
1237    @param slot      Slot to get control row from.
1238    @param indexrow template of the target row (the row in the index).
1239    @param key the (possibly partial) search key.
1240    @param nCompareCols the number of columns to compare.
1241    @param partialKeyOrder what to return on a partial key match.
1242    @param ascOrDesc column sort order information
1243    @throws StandardException if lower levels have a problem.
1244
1245    @exception StandardException Standard exception policy.
1246    **/
1247    public static int CompareIndexRowFromPageToKey(
1248    ControlRow              indexpage,
1249    int                     slot,
1250    DataValueDescriptor[]   indexrow, 
1251    DataValueDescriptor[]   key,
1252    int                     nCompareCols, 
1253    int                     partialKeyOrder,
1254    boolean[]               ascOrDesc)
1255        throws StandardException
1256    {
1257        int compare_result;
1258
1259        // Get the actual number of key columns present
1260        // in the partial key.
1261        int partialKeyCols = key.length;
1262
1263        // Fetch entire index row from page.
1264        // RESOLVE (mikem) - it may be more efficient to fetch just the
1265        // columns you need, but there is overhead currently in raw
1266        // store, since to get to the n'th column you have to walk 
1267        // through the preceding n-1 columns.
1268        indexpage.page.fetchFromSlot(
1269            (RecordHandle) null, slot, indexrow, 
1270            (FetchDescriptor) null,
1271            true);
1272
1273        // Compare corresponding columns in the index row and the key.
1274        for (int i = 0; i < nCompareCols; i++)
1275        {
1276            // See if we have run out of partial key columns.
1277            if (i >= partialKeyCols)
1278            {
1279                // All the columns of the partial key match, and 
1280                // there are more columns in the index row.  We
1281                // want to return -1 or 1, depending on whether the
1282                // caller wants to direct the search to the beginning
1283                // of this key range or the beginning of the next
1284                // one.  If the caller passes in -1, the index row
1285                // will appear less than the partial key, sending the
1286                // search to the next range ("to the right").  If the
1287                // caller passes in 1, the index row will appear
1288                // to be greater than the search key, sending the search
1289                // to the beginning of the range ("to the left").
1290                return partialKeyOrder;
1291            }
1292
1293            // Get the corresponding columns to compare
1294
1295            // Orderable indexcol = (Orderable) indexrow[i];
1296            // Orderable keycol = (Orderable) key[i];
1297
1298            // Compare them.
1299            // int r = indexcol.compare(keycol);
1300
1301            int r = indexrow[i].compare(key[i]);
1302
1303            // If the columns don't compare equal, we're done.
1304            // Return the sense of the comparison.
1305            if (r != 0)
1306            {
1307                //coulmns could have been sorted in ascending or descending
1308                //order. depending on ascending/descending order search 
1309                //direction will change.
1310
1311                if (ascOrDesc[i])  // true - Ascending order
1312                    return r;
1313                else
1314                    return -r;
1315            }
1316        }
1317
1318        // We made it through all the columns, and they must have
1319        // all compared equal.  So return that the rows compare equal.
1320        return 0;
1321    }
1322
1323    public static int CompareIndexRowToKey(
1324    DataValueDescriptor[]   indexrow, 
1325    DataValueDescriptor[]   key,
1326    int                     nCompareCols, 
1327    int                     partialKeyOrder,
1328    boolean[]               ascOrDesc)
1329        throws StandardException
1330    {
1331        // Get the actual number of key columns present
1332        // in the partial key.
1333        int partialKeyCols = key.length;
1334
1335        // Compare corresponding columns in the index row and the key.
1336        for (int i = 0; i < nCompareCols; i++)
1337        {
1338            // See if we have run out of partial key columns.
1339            if (i >= partialKeyCols)
1340            {
1341                // All the columns of the partial key match, and 
1342                // there are more columns in the index row.  We
1343                // want to return -1 or 1, depending on whether the
1344                // caller wants to direct the search to the beginning
1345                // of this key range or the beginning of the next
1346                // one.  If the caller passes in -1, the index row
1347                // will appear less than the partial key, sending the
1348                // search to the next range ("to the right").  If the
1349                // caller passes in 1, the index row will appear
1350                // to be greater than the search key, sending the search
1351                // to the beginning of the range ("to the left").
1352                return partialKeyOrder;
1353            }
1354
1355            // Get the corresponding columns to compare
1356            DataValueDescriptor indexcol = indexrow[i];
1357            DataValueDescriptor keycol = key[i];
1358
1359            // Compare them.
1360            int r = indexcol.compare(keycol);
1361
1362            // If the columns don't compare equal, we're done.
1363            // Return the sense of the comparison.
1364            if (r != 0)
1365            {
1366                if (ascOrDesc[i])  // true - column in ascending order
1367                    return r;
1368                else
1369                    return -r;
1370            }
1371        }
1372
1373        // We made it through all the columns, and they must have
1374        // all compared equal.  So return that the rows compare equal.
1375        return 0;
1376    }
1377
1378    /**
1379     ** Perform consistency checks which are common to all
1380     ** pages that derive from ControlRow (both leaf and 
1381     ** branch pages).  The checks are:
1382     ** <menu>
1383     ** <li> This page thinks the parent argument is actually
1384     **      its parent.
1385     ** <li> The level of this page is 1 less than the level of
1386     **      the parent.
1387     ** <li> All the rows on the page are in order.
1388     ** <li> Both left and right siblings, if they exist, are at
1389     **      the same level of this page.
1390     ** <li> This page is the left sibling of its right sibling,
1391     **      and it's the right sibling of its left sibling.
1392     ** <li> The last row on the left sibling is < the first
1393     **      row on this page.
1394     ** <li> The first row on the right sibling is > than the
1395     **      the last row on this page.
1396     ** </menu>
1397     ** Note that these last two are really only true if there
1398     ** are never duplicate keys.
1399
1400    @exception StandardException Standard exception policy.
1401     **/  
1402    protected void checkGeneric(
1403    OpenBTree  btree, 
1404    ControlRow parent,
1405    boolean    check_other_pages)
1406        throws StandardException
1407    {
1408        if (SanityManager.DEBUG)
1409        {
1410            SanityManager.ASSERT(this.page.recordCount() >= 1);
1411            SanityManager.ASSERT(!this.page.isDeletedAtSlot(0));
1412
1413            // Make sure that we think we're a child of the parent.
1414            if (((parent != null) &&
1415                 (parent.page.getPageNumber() != this.getParentPageNumber())))
1416                SanityManager.THROWASSERT(this + " not child of " + parent);
1417
1418            // Check this page's level.
1419            if (((parent != null) &&
1420                 (parent.getLevel() != this.getLevel() + 1)))
1421                SanityManager.THROWASSERT(this +
1422                        " at wrong level when compared to parent:" + parent);
1423            
1424            // Check rows are in order.
1425            checkRowOrder(btree, parent);
1426
1427            // Check siblings.
1428            if (check_other_pages)
1429                checkSiblings(btree);
1430        }
1431    }
1432
1433    /**
1434     ** Check that all rows on the page are in order.  This
1435     ** means that each key is > than the previous key.
1436
1437    @exception StandardException Standard exception policy.
1438     **/
1439    protected boolean checkRowOrder(OpenBTree btree, ControlRow parent)
1440        throws StandardException
1441    {
1442        if (SanityManager.DEBUG)
1443        {
1444            RecordHandle            lesser_handle   = null;
1445            RecordHandle            greater_handle  = null;
1446            DataValueDescriptor[]   lesser          = getRowTemplate(btree);
1447            DataValueDescriptor[]   greater         = getRowTemplate(btree);
1448            boolean                 is_consistent   = true;
1449           
1450            
1451            int numslots = page.recordCount();
1452            for (int i = ControlRow.CR_SLOT + 1; (i + 1) < numslots; i++)
1453            {
1454               lesser_handle = 
1455                   page.fetchFromSlot(
1456                       (RecordHandle) null, i, lesser, 
1457                       (FetchDescriptor) null, true); 
1458               greater_handle = 
1459                   page.fetchFromSlot(
1460                       (RecordHandle) null, i + 1, greater, 
1461                       (FetchDescriptor) null, true); 
1462
1463               SanityManager.ASSERT(btree.getConglomerate().nUniqueColumns <= 
1464                                    btree.getConglomerate().nKeyFields);
1465               int compare_result = 
1466                   CompareIndexRowToKey(
1467                       lesser, greater,
1468                       btree.getConglomerate().nUniqueColumns, 0,
1469                       btree.getConglomerate().ascDescInfo);
1470
1471               // >= 0 means that lesser >= greater
1472               if (compare_result >= 0)
1473               {
1474                   SanityManager.THROWASSERT(
1475                       "Bad order of rows found in conglomerate: " + btree +
1476                       "\n." +
1477                       "compare result = " + compare_result + ".  " + 
1478                       "nKeyFields = "     + btree.getConglomerate().nKeyFields +
1479                       ".\n" +  
1480                       this + " rows " + (i) + " and " + (i + 1) +
1481                       " out of order.\n" +
1482                       "row[" + i + "] + "  + RowUtil.toString(lesser) + "\n" + 
1483                       "row[" + (i + 1) + "] + "  + RowUtil.toString(greater) +
1484                       "\ndump of page = " + 
1485                           debugPage(btree) +
1486                       "\ndump of parent page = " + 
1487                           ((parent != null) ? 
1488                                parent.debugPage(btree) : "null parent") +
1489                       "\rawstore dump = " + this.page);
1490
1491                   is_consistent = false;
1492               }
1493            }
1494            return(is_consistent);
1495        }
1496        else
1497        {
1498            return(true);
1499        }
1500    }
1501
1502    protected boolean compareRowsOnSiblings(
1503        OpenBTree   btree,
1504        ControlRow  left_sib,
1505        ControlRow  right_sib)
1506            throws StandardException
1507    {
1508        if (SanityManager.DEBUG)
1509        {
1510            boolean is_consistent = true;
1511
1512            // Check that left last row is < right page's first row.
1513            if (left_sib.page.recordCount()  > 1 && 
1514                right_sib.page.recordCount() > 1)
1515            {
1516                DataValueDescriptor[] left_lastrow   = getRowTemplate(btree);
1517                DataValueDescriptor[] right_firstrow = getRowTemplate(btree);
1518
1519                RecordHandle    left_lastrow_handle   = 
1520                    left_sib.page.fetchFromSlot(
1521                        (RecordHandle) null, left_sib.page.recordCount() - 1, 
1522                        left_lastrow, 
1523                        (FetchDescriptor) null, true); 
1524
1525                RecordHandle    right_firstrow_handle  = 
1526                    right_sib.page.fetchFromSlot(
1527                        (RecordHandle) null, 1, right_firstrow, 
1528                        (FetchDescriptor) null, true); 
1529
1530                int r = 
1531                    CompareIndexRowToKey(
1532                        left_lastrow, right_firstrow,
1533                        btree.getConglomerate().nUniqueColumns,
1534                        0, btree.getConglomerate().ascDescInfo);
1535
1536                if (r >= 0)
1537                {
1538                    SanityManager.THROWASSERT(
1539                      "last row on left page " + 
1540                          left_sib.page.getPageNumber() + 
1541                      " > than first row on right page " + 
1542                          right_sib.page.getPageNumber() + "\n" + 
1543                      "left last row = " + RowUtil.toString(left_lastrow) +
1544                      "right first row = " + RowUtil.toString(right_firstrow)+
1545                      left_sib + " last > first of " + right_sib);
1546
1547                    is_consistent = false;
1548                }
1549            }
1550            return(is_consistent);
1551        }
1552        else
1553        {
1554            return(true);
1555        }
1556    }
1557
1558    /**
1559     ** Perform checks on the siblings of this page: make sure
1560     ** that they're at the same level as this page, that they're
1561     ** mutually linked together, and that the first/last keys
1562     ** on sibling pages are in order.
1563
1564    @exception StandardException Standard exception policy.
1565     **/
1566    protected void checkSiblings(OpenBTree btree)
1567        throws StandardException
1568    {
1569        if (SanityManager.DEBUG)
1570        {
1571            // Get this page's left sibling.
1572            ControlRow leftsib  = null;
1573            ControlRow rightsib = null;
1574
1575            try
1576            {
1577                try
1578                {
1579                    leftsib = this.getLeftSibling(btree);
1580                }
1581                catch (WaitError e)
1582                {
1583                    // In a normal system it may be possible to not get
1584                    // the left sibling (some other thread either user
1585                    // or daemon cache cleaner thread) may already have
1586                    // the latch on the page, and waiting on it could cause
1587                    // a latch/latch deadlock.  So for now just give up
1588                    // doing the consistency check in this case.
1589                    //
1590                    // RESOLVE (mikem) - We could do fancier things than 
1591                    // ignore this error, but the only safe way to wait for
1592                    // a right to left latch is to release current latch which
1593                    // will complicate all the code, and this is only a sanity
1594                    // check.
1595
1596                    // SanityManager.DEBUG_PRINT(
1597                    //   "ControlRow.checkSiblings",
1598                    //   this + " left sibling deadlock");
1599
1600                    // give up on checking the left sibling.
1601                    leftsib = null;
1602                }
1603
1604                // There may not be a left sibling; if there is, check it out.
1605                if (leftsib != null)
1606                {
1607                    // Check that it's at the same level as this page.
1608                    if (leftsib.getLevel() != this.getLevel())
1609                        SanityManager.THROWASSERT(
1610                            (leftsib + "not at same level as " + this));
1611
1612                    // Check that its right sibling is this page.
1613                    long hopefullythis_pageno = 
1614                        leftsib.getrightSiblingPageNumber();
1615
1616                    if (hopefullythis_pageno != this.page.getPageNumber())
1617                        SanityManager.THROWASSERT(
1618                            "right sibling of " + leftsib + " isn't "  + this);
1619
1620                    // Check that its last row is < this page's first row.
1621                    compareRowsOnSiblings(btree, leftsib, this);
1622
1623                    // Done looking at the left sibling.
1624                    leftsib.release();
1625                    leftsib = null;
1626                }
1627
1628                // Get the right sibling page.
1629                rightsib = this.getRightSibling(btree);
1630
1631                // There may not be a right sibling; if there is, check it out.
1632                if (rightsib != null)
1633                {
1634                    // Check that it's at the same level as this page.
1635                    if (rightsib.getLevel() != this.getLevel())
1636                        SanityManager.THROWASSERT(
1637                            rightsib + "not at same level as " + this);
1638
1639                    // Check that its left sibling is this page.
1640                    long hopefullythis_pageno = 
1641                        rightsib.getleftSiblingPageNumber();
1642
1643                    if (hopefullythis_pageno != this.page.getPageNumber())
1644                        SanityManager.THROWASSERT(
1645                            "left sibling of " + rightsib + " isn't "  + this);
1646
1647                    // Check that its first row is > this page's last row.
1648                    compareRowsOnSiblings(btree, this, rightsib);
1649
1650                    // Done looking at it.
1651                    rightsib.release();
1652                    rightsib = null;
1653                }
1654            }
1655            finally
1656            {
1657                if (leftsib != null)
1658                    leftsib.release();
1659                if (rightsib != null)
1660                    rightsib.release();
1661            }
1662        }
1663    }
1664
1665    /**
1666     ** Link this page to the right of the target page.
1667     ** <P>
1668     ** Upon entry, this page and the target must be
1669     ** latched.  Upon exit, this page and the target
1670     ** remain latched.
1671     ** <P>
1672     ** This method carefully acquires pages from left
1673     ** to right in order to avoid deadlocks.
1674
1675    @exception StandardException Standard exception policy.
1676     */
1677    void linkRight(OpenBTree btree, ControlRow target)
1678        throws StandardException
1679    {
1680        ControlRow rightSibling = null;
1681
1682        try
1683        {
1684            rightSibling = target.getRightSibling(btree);
1685            this.setRightSibling(rightSibling);
1686            this.setLeftSibling(target);
1687            if (rightSibling != null)
1688                rightSibling.setLeftSibling(this);
1689            target.setRightSibling(this);
1690        }
1691        finally
1692        {
1693            if (rightSibling != null)
1694                rightSibling.release();
1695        }
1696    }
1697
1698    /**
1699     ** Unlink this page from its siblings.  This method
1700     ** will give up and return false rather than run the
1701     ** risk of a deadlock.
1702     ** <P>
1703     ** On entry this page must be latched.  The siblings
1704     ** are latched and unlatched during the operation.  Upon
1705     ** exit, this page will remain latched, but unlinked from
1706     ** its siblings and deallocated from the container.
1707     ** <P>
1708     ** The seemingly odd situation that this page will be
1709     ** returned latched but deallocated is intentional.
1710     ** The container will not be able to reuse this page
1711     ** until the latch is released, and the caller may still
1712     ** need to read information out of it.
1713
1714    @exception StandardException Standard exception policy.
1715     **/
1716    boolean unlink(OpenBTree btree)
1717        throws StandardException
1718    {
1719        ControlRow leftsib  = null;
1720        ControlRow rightsib = null;
1721
1722        
1723        try 
1724        {
1725            // Try to get the left sibling, and give up if 
1726            // it can't be obtained without waiting.
1727
1728            try
1729            {
1730                leftsib = this.getLeftSibling(btree);
1731            }
1732            catch (WaitError e)
1733            {
1734                return false;
1735            }
1736
1737            // We can wait for the right sibling since it's
1738            // in the deadlock-free direction.
1739
1740            rightsib = this.getRightSibling(btree);
1741
1742            // Change the links that pointed to this page to
1743            // point to the appropriate sibling.
1744
1745            if (leftsib != null)
1746                leftsib.setRightSibling(rightsib);
1747            if (rightsib != null)
1748                rightsib.setLeftSibling(leftsib);
1749
1750            // Deallocate the page.
1751            // Would need to clear out aux object here.
1752            //
1753            // RESOLVE (mikem) - how to deallocate a page. //
1754            btree.container.removePage(this.page);
1755
1756            // After removePage call the current page is unlatched, and should
1757            // not be referenced anymore.
1758            if (SanityManager.DEBUG)
1759            {
1760                SanityManager.ASSERT(!this.page.isLatched());
1761            }
1762
1763            return true;
1764        }
1765        finally
1766        {
1767            // Unlatch the siblings.
1768            if (leftsib != null)
1769                leftsib.release();
1770            if (rightsib != null)
1771                rightsib.release();
1772        }
1773    }
1774
1775    public Page getPage()
1776    {
1777        return(page);
1778    }
1779
1780    /**
1781     * Get the row.
1782     * <p>
1783     * Return the object array that represents the control row for use
1784     * in raw store fetch, insert, and/or update.
1785     *
1786     * @return The row.
1787     *
1788     **/
1789    protected final DataValueDescriptor[] getRow()
1790    {
1791        return(row);
1792    }
1793
1794    /*
1795     * The following methods must be implemented by all
1796     * control rows.
1797     */
1798
1799    /**
1800     * Check consistency of the page and its children, returning the number of 
1801     * pages seen, and throwing errors if inconsistencies are found.
1802     * <p>
1803     *
1804     * @return The identifier to be used to open the conglomerate later.
1805     *
1806     * @param btree  The open btree to associate latches/locks with.
1807     * @param parent The parent page of this page, "null" if this page is 
1808     *               root or if not maintaining parent links.
1809     * @param check_other_pages
1810     *               Should the consistency check go to other pages (this 
1811     *               option breaks the latch protocol).
1812     *
1813     * @exception  StandardException  Standard exception policy.
1814     **/
1815    abstract protected int checkConsistency(
1816    OpenBTree  btree, 
1817    ControlRow parent,
1818    boolean    check_other_pages)
1819        throws StandardException;
1820
1821    /**
1822     * Return the left child pointer for the page.
1823     * <p>
1824     * Leaf pages don't have children, so they override this and return null.
1825     *
1826     * @return The page which is the leftmost child of this page.
1827     *
1828     * @param btree  The open btree to associate latches/locks with.
1829     *
1830     * @exception  StandardException  Standard exception policy.
1831     **/
1832    protected abstract ControlRow getLeftChild(OpenBTree btree)
1833        throws StandardException;
1834
1835    /**
1836     * Return the right child pointer for the page.
1837     * <p>
1838     * Leaf pages don't have children, so they override this and return null.
1839     *
1840     * @return The page which is the rightmost child of this page.
1841     *
1842     * @param btree  The open btree to associate latches/locks with.
1843     *
1844     * @exception  StandardException  Standard exception policy.
1845     **/
1846    protected abstract ControlRow getRightChild(OpenBTree btree)
1847        throws StandardException;
1848
1849    /**
1850     * Perform page specific initialization.
1851     * <p>
1852     *
1853     **/
1854    protected abstract void ControlRowInit();
1855
1856    /**
1857     * Is the current page the leftmost leaf of tree?
1858     * <p>
1859     *
1860     * @return true if the current page is the leftmost leaf of the tree,
1861     *              else return false.
1862     *
1863     * @exception  StandardException  Standard exception policy.
1864     **/
1865    public abstract boolean isLeftmostLeaf()
1866        throws StandardException;
1867
1868    /**
1869     * Is the current page the rightmost leaf of tree?
1870     * <p>
1871     *
1872     * @return true if the current page is the rightmost leaf of the tree,
1873     *              else return false.
1874     *
1875     * @exception  StandardException  Standard exception policy.
1876     **/
1877    public abstract boolean isRightmostLeaf()
1878        throws StandardException;
1879
1880    /**
1881     ** Perform a recursive search, ultimately returning the latched
1882     ** leaf page and row slot after which the given key belongs.
1883     ** The slot is returned in the result structure.  If the key
1884     ** exists on the page, the resultExact field will be true.  Otherwise,
1885     ** resultExact field will be false, and the row slot returned will be
1886     ** the one immediately preceding the position at which the key
1887     ** belongs.
1888
1889    @exception StandardException Standard exception policy.
1890     **/
1891    public abstract ControlRow search(
1892        SearchParameters    search_params)
1893            throws StandardException;
1894    /**
1895     * Get the number of columns in the control row.  
1896     * <p>
1897     * Control rows all share the first columns as defined by this class and
1898     * then add columns to the end of the control row.  For instance a branch
1899     * control row add a child page pointer field.
1900     * <p>
1901     *
1902     * @return The total number of columns in the control row.
1903     **/
1904    protected abstract int getNumberOfControlRowColumns();
1905    
1906    /**
1907     * Search and return the left most leaf page.
1908     * <p>
1909     * Perform a recursive search, ultimately returning the
1910     * leftmost leaf page which is the first leaf page in the
1911     * leaf sibling chain.  (This method might better be called
1912     * getFirstLeafPage()).
1913     *
1914     * @return The leftmost leaf page.
1915     *
1916     * @param btree  The open btree to associate latches/locks with.
1917     *
1918     * @exception  StandardException  Standard exception policy.
1919     **/
1920    protected abstract ControlRow searchLeft(OpenBTree btree)
1921        throws StandardException;
1922
1923    /**
1924     * Search and return the right most leaf page.
1925     * <p>
1926     * Perform a recursive search, ultimately returning the
1927     * rightmost leaf page which is the last leaf page in the
1928     * leaf sibling chain.  (This method might better be called
1929     * getLastLeafPage()).
1930     *
1931     * @return The rightmost leaf page.
1932     *
1933     * @param btree  The open btree to associate latches/locks with.
1934     *
1935     * @exception  StandardException  Standard exception policy.
1936     **/
1937    protected abstract ControlRow searchRight(OpenBTree btree)
1938        throws StandardException;
1939
1940    /**
1941     ** Perform a recursive shrink operation for the key.
1942     ** If this method returns true, the caller should
1943     ** remove the corresponding entry for the page.
1944     ** This routine is not guaranteed to successfully
1945     ** shrink anything.  The page lead to by the key might
1946     ** turn out not to be empty by the time shrink gets
1947     ** there, and shrinks will give up if there is a deadlock.
1948     ** <P>
1949     ** As currently implemented shrinkFor must be executed while holding
1950     ** an exclusive container lock on the entire table.  It is expected that
1951     ** this call is made within an internal transaction which has been called
1952     ** by a post commit thread.  Latches are released by the code.  The raw 
1953     ** store guarantees that deallocated pages are not seen by other xacts
1954     ** until the transaction has been committed.  
1955     ** <P>
1956     ** Note that a non-table level lock implementation must hold latches on
1957     ** pages affected until end transaction.
1958     ** <p>
1959     ** On entry, the current page is latched.  On exit, all pages will have
1960     ** been unlatched. 
1961     ** 
1962     ** @exception StandardException Standard exception policy.
1963     **/
1964    protected abstract boolean shrinkFor(
1965    OpenBTree               btree, 
1966    DataValueDescriptor[]   key)
1967        throws StandardException;
1968
1969    /**
1970     * Perform a top down split pass making room for the the key in "row".
1971     * <p>
1972     * Perform a split such that a subsequent call to insert
1973     * given the argument index row will likely find room for it.  Since 
1974     * latches are released the client must code for the case where another
1975     * user has grabbed the space made available by the split pass and be
1976     * ready to do another split.
1977     * <p>
1978     *
1979     * @return page number of the newly allocated leaf page created by split.
1980     *
1981     * @param open_btree The open btree to associate latches with.
1982     * @param template   A scratch area to use while searching for split pass.
1983     * @param parentpage The parent page of the current page in the split pass.
1984     *                   starts at null for root.
1985     * @param row        The key to make room for during the split pass.
1986     * @param flag       A flag used to direct where point of split should be
1987     *                   chosen.
1988     *
1989     * @exception  StandardException  Standard exception policy.
1990     **/
1991    protected abstract long splitFor(
1992    OpenBTree               open_btree, 
1993    DataValueDescriptor[]   template, 
1994    BranchControlRow        parentpage, 
1995    DataValueDescriptor[]   row,
1996    int                     flag)
1997        throws StandardException;
1998
1999    /**
2000     ** Recursively print the tree starting at current node in tree.
2001
2002    @exception StandardException Standard exception policy.
2003     **/
2004    public abstract void printTree(
2005    OpenBTree  btree) 
2006        throws StandardException;
2007    
2008
2009
2010    /*
2011    ** Methods of AuxObject
2012    */
2013
2014    /**
2015        Called when the page is being evicted from cache or when a rollback
2016        happened on the page and may possibly have changed the control row's 
2017        value
2018
2019        @see AuxObject#auxObjectInvalidated
2020    **/
2021    public void auxObjectInvalidated()
2022    {
2023        version = null;
2024        leftSiblingPageNumber = null;
2025        rightSiblingPageNumber = null;
2026        parentPageNumber = null;
2027        level = null;
2028        isRoot = null;
2029        page = null;
2030    }
2031
2032    /**
2033     * Return a new template for reading a data row from the current page.
2034     * <p>
2035     * Default implementation for rows which are the same as the conglomerates
2036     * template, sub-classes can alter if underlying template is different
2037     * (for instance branch rows add an extra field at the end).
2038     *
2039     * @return Newly allocated template.
2040     *
2041     * @exception  StandardException  Standard exception policy.
2042     **/
2043    public DataValueDescriptor[] getRowTemplate(OpenBTree    open_btree)
2044        throws StandardException
2045    {
2046        return(open_btree.getConglomerate().createTemplate());
2047    }
2048
2049
2050    /**
2051     ** Debug toString() method's.
2052     **/
2053
2054    /**
2055     * Dump complete information about control row and rows on the page.
2056     * <p>
2057     *
2058     * @return string with all info.
2059     *
2060     * @exception  StandardException  Standard exception policy.
2061     **/
2062    public String   debugPage(
2063    OpenBTree   open_btree)
2064        throws StandardException
2065    {
2066        String   ret_str;
2067
2068        if (SanityManager.DEBUG)
2069        {
2070            StringBuffer   string = new StringBuffer  (4096);
2071            string.append(this.toString());
2072            string.append("\n");
2073
2074            DataValueDescriptor[] row = getRowTemplate(open_btree);
2075
2076            string.append(
2077                ConglomerateUtil.debugPage(
2078                    page, ControlRow.CR_SLOT + 1, false, row));
2079
2080            ret_str = string.toString();
2081        }
2082        else
2083        {
2084            ret_str = null;
2085        }
2086
2087        return(ret_str);
2088    }
2089
2090    /**
2091     * The standard toString().
2092     * <p>
2093     * This is a concise print out of the info in the control row, does not
2094     * include anything the page.
2095     * <p>
2096     * 
2097     **/
2098    public String   toString()
2099    {
2100        if (SanityManager.DEBUG)
2101        {
2102            StringBuffer   string = new StringBuffer  (4096);
2103
2104            try {
2105
2106
2107                // LEAF, BRANCH, LEAF-ROOT, BRANCH-ROOT
2108                string.append((getLevel() == 0) ? "\nLEAF" : "\nBRANCH");
2109                string.append((getIsRoot())     ? "-ROOT" : "");
2110
2111                // (PAGE NUMBER)(LEVEL):num recs 
2112                //     example: (107)(lev=2):num recs = 16
2113                string.append("(");
2114                string.append(this.page.getPageNumber());
2115                string.append(")(lev=");
2116                string.append(level);
2117                string.append("): num recs = ");
2118                string.append(this.page.recordCount());
2119                string.append("\n");
2120
2121                // rest of info
2122                string.append("\t");
2123
2124                string.append("left = ");
2125                string.append(getleftSiblingPageNumber());
2126                string.append(";");
2127
2128                string.append("right = ");
2129                string.append(getrightSiblingPageNumber());
2130                string.append(";");
2131
2132                string.append("parent = ");
2133                string.append(getParentPageNumber());
2134                string.append(";");
2135
2136                string.append("isRoot = ");
2137                string.append(getIsRoot());
2138                string.append(";");
2139
2140            }
2141            catch (Throwable   t)
2142            {
2143                string.append(
2144                    "error encountered while doing ControlRow.toString()");
2145            }
2146
2147            return(string.toString());
2148        }
2149        else
2150        {
2151            return(null);
2152        }
2153    }
2154}
2155
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags