001    /**
002     * JDBM LICENSE v1.00
003     *
004     * Redistribution and use of this software and associated documentation
005     * ("Software"), with or without modification, are permitted provided
006     * that the following conditions are met:
007     *
008     * 1. Redistributions of source code must retain copyright
009     *    statements and notices.  Redistributions must also contain a
010     *    copy of this document.
011     *
012     * 2. Redistributions in binary form must reproduce the
013     *    above copyright notice, this list of conditions and the
014     *    following disclaimer in the documentation and/or other
015     *    materials provided with the distribution.
016     *
017     * 3. The name "JDBM" must not be used to endorse or promote
018     *    products derived from this Software without prior written
019     *    permission of Cees de Groot.  For written permission,
020     *    please contact cg@cdegroot.com.
021     *
022     * 4. Products derived from this Software may not be called "JDBM"
023     *    nor may "JDBM" appear in their names without prior written
024     *    permission of Cees de Groot.
025     *
026     * 5. Due credit should be given to the JDBM Project
027     *    (http://jdbm.sourceforge.net/).
028     *
029     * THIS SOFTWARE IS PROVIDED BY THE JDBM PROJECT AND CONTRIBUTORS
030     * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
031     * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
032     * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
033     * CEES DE GROOT OR ANY CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
034     * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
035     * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
036     * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
037     * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
038     * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
039     * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
040     * OF THE POSSIBILITY OF SUCH DAMAGE.
041     *
042     * Copyright 2001 (C) Alex Boisvert. All Rights Reserved.
043     * Contributions are Copyright (C) 2001 by their associated contributors.
044     *
045     */
046    
047    package jdbm.btree;
048    
049    
050    import jdbm.helper.Serializer;
051    import jdbm.helper.Tuple;
052    import jdbm.helper.TupleBrowser;
053    
054    import java.io.IOException;
055    import java.io.ByteArrayOutputStream;
056    import java.io.ByteArrayInputStream;
057    import java.io.ObjectInput;
058    import java.io.ObjectOutput;
059    import java.io.ObjectInputStream;
060    import java.io.ObjectOutputStream;
061    
062    import org.apache.directory.server.i18n.I18n;
063    
064    
065    /**
066     * Page of a Btree.
067     * <p>
068     * The page contains a number of key-value pairs.  Keys are ordered to allow
069     * dichotomic search.
070     * <p>
071     * If the page is a leaf page, the keys and values are user-defined and
072     * represent entries inserted by the user.
073     * <p>
074     * If the page is non-leaf, each key represents the greatest key in the
075     * underlying BPages and the values are recids pointing to the children BPages.
076     * The only exception is the rightmost BPage, which is considered to have an
077     * "infinite" key value, meaning that any insert will be to the left of this
078     * pseudo-key
079     *
080     * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
081     * @version $Id: BPage.java,v 1.6 2003/09/21 15:46:59 boisvert Exp $
082     */
083    public final class BPage implements Serializer
084    {
085    
086        private static final boolean DEBUG = false;
087    
088        /**
089         * Version id for serialization.
090         */
091        final static long serialVersionUID = 1L;
092    
093        /**
094         * Parent B+Tree.
095         */
096        transient BTree _btree;
097    
098        /**
099         * This BPage's record ID in the PageManager.
100         */
101        protected transient long _recid;
102    
103        /**
104         * Flag indicating if this is a leaf BPage.
105         */
106        protected boolean _isLeaf;
107    
108        /**
109         * Keys of children nodes
110         */
111        protected Object[] _keys;
112    
113        /**
114         * Values associated with keys.  (Only valid if leaf BPage)
115         */
116        protected Object[] _values;
117    
118        /**
119         * Children pages (recids) associated with keys.  (Only valid if non-leaf BPage)
120         */
121        protected long[] _children;
122    
123        /**
124         * Index of first used item at the page
125         */
126        protected int _first;
127    
128        /**
129         * Previous leaf BPage (only if this BPage is a leaf)
130         */
131        protected long _previous;
132    
133        /**
134         * Next leaf BPage (only if this BPage is a leaf)
135         */
136        protected long _next;
137    
138    
139        /**
140         * No-argument constructor used by serialization.
141         */
142        public BPage()
143        {
144            // empty
145        }
146    
147    
148        /**
149         * Root page overflow constructor
150         */
151        BPage( BTree btree, BPage root, BPage overflow ) throws IOException
152        {
153            _btree = btree;
154    
155            _isLeaf = false;
156    
157            _first = _btree._pageSize - 2;
158    
159            _keys = new Object[_btree._pageSize];
160            _keys[_btree._pageSize - 2] = overflow.getLargestKey();
161            _keys[_btree._pageSize - 1] = root.getLargestKey();
162    
163            _children = new long[_btree._pageSize];
164            _children[_btree._pageSize - 2] = overflow._recid;
165            _children[_btree._pageSize - 1] = root._recid;
166    
167            _recid = _btree._recman.insert( this, this );
168        }
169    
170    
171        /**
172         * Root page (first insert) constructor.
173         */
174        BPage( BTree btree, Object key, Object value ) throws IOException
175        {
176            _btree = btree;
177    
178            _isLeaf = true;
179    
180            _first = btree._pageSize - 2;
181    
182            _keys = new Object[_btree._pageSize];
183            _keys[_btree._pageSize - 2] = key;
184            _keys[_btree._pageSize - 1] = null; // I am the root BPage for now
185    
186            _values = new Object[_btree._pageSize];
187            _values[_btree._pageSize - 2] = value;
188            _values[_btree._pageSize - 1] = null; // I am the root BPage for now
189    
190            _recid = _btree._recman.insert( this, this );
191        }
192    
193    
194        /**
195         * Overflow page constructor.  Creates an empty BPage.
196         */
197        BPage( BTree btree, boolean isLeaf ) throws IOException
198        {
199            _btree = btree;
200    
201            _isLeaf = isLeaf;
202    
203            // page will initially be half-full
204            _first = _btree._pageSize / 2;
205    
206            _keys = new Object[_btree._pageSize];
207            if ( isLeaf )
208            {
209                _values = new Object[_btree._pageSize];
210            }
211            else
212            {
213                _children = new long[_btree._pageSize];
214            }
215    
216            _recid = _btree._recman.insert( this, this );
217        }
218    
219    
220        /**
221         * Get largest key under this BPage.  Null is considered to be the
222         * greatest possible key.
223         */
224        Object getLargestKey()
225        {
226            return _keys[_btree._pageSize - 1];
227        }
228    
229    
230        /**
231         * Return true if BPage is empty.
232         */
233        boolean isEmpty()
234        {
235            if ( _isLeaf )
236            {
237                return ( _first == _values.length - 1 );
238            }
239            else
240            {
241                return ( _first == _children.length - 1 );
242            }
243        }
244    
245    
246        /**
247         * Return true if BPage is full.
248         */
249        boolean isFull()
250        {
251            return ( _first == 0 );
252        }
253    
254    
255        /**
256         * Find the object associated with the given key.
257         *
258         * @param height Height of the current BPage (zero is leaf page)
259         * @param key The key
260         * @return TupleBrowser positionned just before the given key, or before
261         *                      next greater key if key isn't found.
262         */
263        TupleBrowser find( int height, Object key ) throws IOException
264        {
265            int index = findChildren( key );
266    
267            /*
268            if ( DEBUG ) {
269                System.out.println( "BPage.find() current: " + this
270                                    + " height: " + height);
271            }
272            */
273    
274            height -= 1;
275    
276            if ( height == 0 )
277            {
278                // leaf BPage
279                return new Browser( this, index );
280            }
281            else
282            {
283                // non-leaf BPage
284                BPage child = childBPage( index );
285                return child.find( height, key );
286            }
287        }
288    
289    
290        /**
291         * Find first entry and return a browser positioned before it.
292         *
293         * @return TupleBrowser positionned just before the first entry.
294         */
295        TupleBrowser findFirst() throws IOException
296        {
297            if ( _isLeaf )
298            {
299                return new Browser( this, _first );
300            }
301            else
302            {
303                BPage child = childBPage( _first );
304                return child.findFirst();
305            }
306        }
307    
308    
309        /**
310         * Insert the given key and value.
311         * <p>
312         * Since the Btree does not support duplicate entries, the caller must
313         * specify whether to replace the existing value.
314         *
315         * @param height Height of the current BPage (zero is leaf page)
316         * @param key Insert key
317         * @param value Insert value
318         * @param replace Set to true to replace the existing value, if one exists.
319         * @return Insertion result containing existing value OR a BPage if the key
320         *         was inserted and provoked a BPage overflow.
321         */
322        InsertResult insert( int height, Object key, Object value, boolean replace ) throws IOException
323        {
324            InsertResult result;
325            long overflow;
326    
327            int index = findChildren( key );
328    
329            height -= 1;
330            if ( height == 0 )
331            {
332    
333                result = new InsertResult();
334    
335                // inserting on a leaf BPage
336                overflow = -1;
337                if ( DEBUG )
338                {
339                    System.out.println( "Bpage.insert() Insert on leaf Bpage key=" + key + " value=" + value + " index="
340                        + index );
341                }
342                if ( compare( key, _keys[index] ) == 0 )
343                {
344                    // key already exists
345                    if ( DEBUG )
346                    {
347                        System.out.println( "Bpage.insert() Key already exists." );
348                    }
349                    result._existing = _values[index];
350                    if ( replace )
351                    {
352                        _values[index] = value;
353                        _btree._recman.update( _recid, this, this );
354                    }
355                    // return the existing key
356                    return result;
357                }
358            }
359            else
360            {
361                // non-leaf BPage
362                BPage child = childBPage( index );
363                result = child.insert( height, key, value, replace );
364    
365                if ( result._existing != null )
366                {
367                    // return existing key, if any.
368                    return result;
369                }
370    
371                if ( result._overflow == null )
372                {
373                    // no overflow means we're done with insertion
374                    return result;
375                }
376    
377                // there was an overflow, we need to insert the overflow page
378                // on this BPage
379                if ( DEBUG )
380                {
381                    System.out.println( "BPage.insert() Overflow page: " + result._overflow._recid );
382                }
383                key = result._overflow.getLargestKey();
384                overflow = result._overflow._recid;
385    
386                // update child's largest key
387                _keys[index] = child.getLargestKey();
388    
389                // clean result so we can reuse it
390                result._overflow = null;
391            }
392    
393            // if we get here, we need to insert a new entry on the BPage
394            // before _children[ index ]
395            if ( !isFull() )
396            {
397                if ( height == 0 )
398                {
399                    insertEntry( this, index - 1, key, value );
400                }
401                else
402                {
403                    insertChild( this, index - 1, key, overflow );
404                }
405                _btree._recman.update( _recid, this, this );
406                return result;
407            }
408    
409            // page is full, we must divide the page
410            int half = _btree._pageSize >> 1;
411            BPage newPage = new BPage( _btree, _isLeaf );
412            if ( index < half )
413            {
414                // move lower-half of entries to overflow BPage,
415                // including new entry
416                if ( DEBUG )
417                {
418                    System.out
419                        .println( "Bpage.insert() move lower-half of entries to overflow BPage, including new entry." );
420                }
421                if ( height == 0 )
422                {
423                    copyEntries( this, 0, newPage, half, index );
424                    setEntry( newPage, half + index, key, value );
425                    copyEntries( this, index, newPage, half + index + 1, half - index - 1 );
426                }
427                else
428                {
429                    copyChildren( this, 0, newPage, half, index );
430                    setChild( newPage, half + index, key, overflow );
431                    copyChildren( this, index, newPage, half + index + 1, half - index - 1 );
432                }
433            }
434            else
435            {
436                // move lower-half of entries to overflow BPage,
437                // new entry stays on this BPage
438                if ( DEBUG )
439                {
440                    System.out.println( "Bpage.insert() move lower-half of entries to overflow BPage. New entry stays" );
441                }
442                if ( height == 0 )
443                {
444                    copyEntries( this, 0, newPage, half, half );
445                    copyEntries( this, half, this, half - 1, index - half );
446                    setEntry( this, index - 1, key, value );
447                }
448                else
449                {
450                    copyChildren( this, 0, newPage, half, half );
451                    copyChildren( this, half, this, half - 1, index - half );
452                    setChild( this, index - 1, key, overflow );
453                }
454            }
455    
456            _first = half - 1;
457    
458            // nullify lower half of entries
459            for ( int i = 0; i < _first; i++ )
460            {
461                if ( height == 0 )
462                {
463                    setEntry( this, i, null, null );
464                }
465                else
466                {
467                    setChild( this, i, null, -1 );
468                }
469            }
470    
471            if ( _isLeaf )
472            {
473                // link newly created BPage
474                newPage._previous = _previous;
475                newPage._next = _recid;
476                if ( _previous != 0 )
477                {
478                    BPage previous = loadBPage( _previous );
479                    previous._next = newPage._recid;
480                    _btree._recman.update( _previous, previous, this );
481                }
482                _previous = newPage._recid;
483            }
484    
485            _btree._recman.update( _recid, this, this );
486            _btree._recman.update( newPage._recid, newPage, this );
487    
488            result._overflow = newPage;
489            return result;
490        }
491    
492    
493        /**
494         * Remove the entry associated with the given key.
495         *
496         * @param height Height of the current BPage (zero is leaf page)
497         * @param key Removal key
498         * @return Remove result object
499         */
500        RemoveResult remove( int height, Object key ) throws IOException
501        {
502            RemoveResult result;
503    
504            int half = _btree._pageSize / 2;
505            int index = findChildren( key );
506    
507            height -= 1;
508            if ( height == 0 )
509            {
510                // remove leaf entry
511                if ( compare( _keys[index], key ) != 0 )
512                {
513                    throw new IllegalArgumentException( I18n.err( I18n.ERR_514, key ) );
514                }
515                result = new RemoveResult();
516                result._value = _values[index];
517                removeEntry( this, index );
518    
519                // update this BPage
520                _btree._recman.update( _recid, this, this );
521    
522            }
523            else
524            {
525                // recurse into Btree to remove entry on a children page
526                BPage child = childBPage( index );
527                result = child.remove( height, key );
528    
529                // update children
530                _keys[index] = child.getLargestKey();
531                _btree._recman.update( _recid, this, this );
532    
533                if ( result._underflow )
534                {
535                    // underflow occured
536                    if ( child._first != half + 1 )
537                    {
538                        throw new IllegalStateException( I18n.err( I18n.ERR_513, "1" ) );
539                    }
540                    if ( index < _children.length - 1 )
541                    {
542                        // exists greater brother page
543                        BPage brother = childBPage( index + 1 );
544                        int bfirst = brother._first;
545                        if ( bfirst < half )
546                        {
547                            // steal entries from "brother" page
548                            int steal = ( half - bfirst + 1 ) / 2;
549                            brother._first += steal;
550                            child._first -= steal;
551                            if ( child._isLeaf )
552                            {
553                                copyEntries( child, half + 1, child, half + 1 - steal, half - 1 );
554                                copyEntries( brother, bfirst, child, 2 * half - steal, steal );
555                            }
556                            else
557                            {
558                                copyChildren( child, half + 1, child, half + 1 - steal, half - 1 );
559                                copyChildren( brother, bfirst, child, 2 * half - steal, steal );
560                            }
561    
562                            for ( int i = bfirst; i < bfirst + steal; i++ )
563                            {
564                                if ( brother._isLeaf )
565                                {
566                                    setEntry( brother, i, null, null );
567                                }
568                                else
569                                {
570                                    setChild( brother, i, null, -1 );
571                                }
572                            }
573    
574                            // update child's largest key
575                            _keys[index] = child.getLargestKey();
576    
577                            // no change in previous/next BPage
578    
579                            // update BPages
580                            _btree._recman.update( _recid, this, this );
581                            _btree._recman.update( brother._recid, brother, this );
582                            _btree._recman.update( child._recid, child, this );
583    
584                        }
585                        else
586                        {
587                            // move all entries from page "child" to "brother"
588                            if ( brother._first != half )
589                            {
590                                throw new IllegalStateException( I18n.err( I18n.ERR_513, "2" ) );
591                            }
592    
593                            brother._first = 1;
594                            if ( child._isLeaf )
595                            {
596                                copyEntries( child, half + 1, brother, 1, half - 1 );
597                            }
598                            else
599                            {
600                                copyChildren( child, half + 1, brother, 1, half - 1 );
601                            }
602                            _btree._recman.update( brother._recid, brother, this );
603    
604                            // remove "child" from current BPage
605                            if ( _isLeaf )
606                            {
607                                copyEntries( this, _first, this, _first + 1, index - _first );
608                                setEntry( this, _first, null, null );
609                            }
610                            else
611                            {
612                                copyChildren( this, _first, this, _first + 1, index - _first );
613                                setChild( this, _first, null, -1 );
614                            }
615                            _first += 1;
616                            _btree._recman.update( _recid, this, this );
617    
618                            // re-link previous and next BPages
619                            if ( child._previous != 0 )
620                            {
621                                BPage prev = loadBPage( child._previous );
622                                prev._next = child._next;
623                                _btree._recman.update( prev._recid, prev, this );
624                            }
625                            if ( child._next != 0 )
626                            {
627                                BPage next = loadBPage( child._next );
628                                next._previous = child._previous;
629                                _btree._recman.update( next._recid, next, this );
630                            }
631    
632                            // delete "child" BPage
633                            _btree._recman.delete( child._recid );
634                        }
635                    }
636                    else
637                    {
638                        // page "brother" is before "child"
639                        BPage brother = childBPage( index - 1 );
640                        int bfirst = brother._first;
641                        if ( bfirst < half )
642                        {
643                            // steal entries from "brother" page
644                            int steal = ( half - bfirst + 1 ) / 2;
645                            brother._first += steal;
646                            child._first -= steal;
647                            if ( child._isLeaf )
648                            {
649                                copyEntries( brother, 2 * half - steal, child, half + 1 - steal, steal );
650                                copyEntries( brother, bfirst, brother, bfirst + steal, 2 * half - bfirst - steal );
651                            }
652                            else
653                            {
654                                copyChildren( brother, 2 * half - steal, child, half + 1 - steal, steal );
655                                copyChildren( brother, bfirst, brother, bfirst + steal, 2 * half - bfirst - steal );
656                            }
657    
658                            for ( int i = bfirst; i < bfirst + steal; i++ )
659                            {
660                                if ( brother._isLeaf )
661                                {
662                                    setEntry( brother, i, null, null );
663                                }
664                                else
665                                {
666                                    setChild( brother, i, null, -1 );
667                                }
668                            }
669    
670                            // update brother's largest key
671                            _keys[index - 1] = brother.getLargestKey();
672    
673                            // no change in previous/next BPage
674    
675                            // update BPages
676                            _btree._recman.update( _recid, this, this );
677                            _btree._recman.update( brother._recid, brother, this );
678                            _btree._recman.update( child._recid, child, this );
679    
680                        }
681                        else
682                        {
683                            // move all entries from page "brother" to "child"
684                            if ( brother._first != half )
685                            {
686                                throw new IllegalStateException( I18n.err( I18n.ERR_513, "3" ) );
687                            }
688    
689                            child._first = 1;
690                            if ( child._isLeaf )
691                            {
692                                copyEntries( brother, half, child, 1, half );
693                            }
694                            else
695                            {
696                                copyChildren( brother, half, child, 1, half );
697                            }
698                            _btree._recman.update( child._recid, child, this );
699    
700                            // remove "brother" from current BPage
701                            if ( _isLeaf )
702                            {
703                                copyEntries( this, _first, this, _first + 1, index - 1 - _first );
704                                setEntry( this, _first, null, null );
705                            }
706                            else
707                            {
708                                copyChildren( this, _first, this, _first + 1, index - 1 - _first );
709                                setChild( this, _first, null, -1 );
710                            }
711                            _first += 1;
712                            _btree._recman.update( _recid, this, this );
713    
714                            // re-link previous and next BPages
715                            if ( brother._previous != 0 )
716                            {
717                                BPage prev = loadBPage( brother._previous );
718                                prev._next = brother._next;
719                                _btree._recman.update( prev._recid, prev, this );
720                            }
721                            if ( brother._next != 0 )
722                            {
723                                BPage next = loadBPage( brother._next );
724                                next._previous = brother._previous;
725                                _btree._recman.update( next._recid, next, this );
726                            }
727    
728                            // delete "brother" BPage
729                            _btree._recman.delete( brother._recid );
730                        }
731                    }
732                }
733            }
734    
735            // underflow if page is more than half-empty
736            result._underflow = _first > half;
737    
738            return result;
739        }
740    
741    
742        /**
743         * Find the first children node with a key equal or greater than the given
744         * key.
745         *
746         * @return index of first children with equal or greater key.
747         */
748        private int findChildren( Object key )
749        {
750            int left = _first;
751            int right = _btree._pageSize - 1;
752    
753            // binary search
754            while ( left < right )
755            {
756                int middle = ( left + right ) / 2;
757                if ( compare( _keys[middle], key ) < 0 )
758                {
759                    left = middle + 1;
760                }
761                else
762                {
763                    right = middle;
764                }
765            }
766            return right;
767        }
768    
769    
770        /**
771         * Insert entry at given position.
772         */
773        private static void insertEntry( BPage page, int index, Object key, Object value )
774        {
775            Object[] keys = page._keys;
776            Object[] values = page._values;
777            int start = page._first;
778            int count = index - page._first + 1;
779    
780            // shift entries to the left
781            System.arraycopy( keys, start, keys, start - 1, count );
782            System.arraycopy( values, start, values, start - 1, count );
783            page._first -= 1;
784            keys[index] = key;
785            values[index] = value;
786        }
787    
788    
789        /**
790         * Insert child at given position.
791         */
792        private static void insertChild( BPage page, int index, Object key, long child )
793        {
794            Object[] keys = page._keys;
795            long[] children = page._children;
796            int start = page._first;
797            int count = index - page._first + 1;
798    
799            // shift entries to the left
800            System.arraycopy( keys, start, keys, start - 1, count );
801            System.arraycopy( children, start, children, start - 1, count );
802            page._first -= 1;
803            keys[index] = key;
804            children[index] = child;
805        }
806    
807    
808        /**
809         * Remove entry at given position.
810         */
811        private static void removeEntry( BPage page, int index )
812        {
813            Object[] keys = page._keys;
814            Object[] values = page._values;
815            int start = page._first;
816            int count = index - page._first;
817    
818            System.arraycopy( keys, start, keys, start + 1, count );
819            keys[start] = null;
820            System.arraycopy( values, start, values, start + 1, count );
821            values[start] = null;
822            page._first++;
823        }
824    
825    
826        /**
827         * Remove child at given position.
828         */
829        /*    
830            private static void removeChild( BPage page, int index )
831            {
832                Object[] keys = page._keys;
833                long[] children = page._children;
834                int start = page._first;
835                int count = index-page._first;
836    
837                System.arraycopy( keys, start, keys, start+1, count );
838                keys[ start ] = null;
839                System.arraycopy( children, start, children, start+1, count );
840                children[ start ] = (long) -1;
841                page._first++;
842            }
843        */
844    
845        /**
846         * Set the entry at the given index.
847         */
848        private static void setEntry( BPage page, int index, Object key, Object value )
849        {
850            page._keys[index] = key;
851            page._values[index] = value;
852        }
853    
854    
855        /**
856         * Set the child BPage recid at the given index.
857         */
858        private static void setChild( BPage page, int index, Object key, long recid )
859        {
860            page._keys[index] = key;
861            page._children[index] = recid;
862        }
863    
864    
865        /**
866         * Copy entries between two BPages
867         */
868        private static void copyEntries( BPage source, int indexSource, BPage dest, int indexDest, int count )
869        {
870            System.arraycopy( source._keys, indexSource, dest._keys, indexDest, count );
871            System.arraycopy( source._values, indexSource, dest._values, indexDest, count );
872        }
873    
874    
875        /**
876         * Copy child BPage recids between two BPages
877         */
878        private static void copyChildren( BPage source, int indexSource, BPage dest, int indexDest, int count )
879        {
880            System.arraycopy( source._keys, indexSource, dest._keys, indexDest, count );
881            System.arraycopy( source._children, indexSource, dest._children, indexDest, count );
882        }
883    
884    
885        /**
886         * Return the child BPage at given index.
887         */
888        BPage childBPage( int index ) throws IOException
889        {
890            return loadBPage( _children[index] );
891        }
892    
893    
894        /**
895         * Load the BPage at the given recid.
896         */
897        private BPage loadBPage( long recid ) throws IOException
898        {
899            BPage child = ( BPage ) _btree._recman.fetch( recid, this );
900            child._recid = recid;
901            child._btree = _btree;
902            return child;
903        }
904    
905    
906        private final int compare( Object value1, Object value2 )
907        {
908            if ( value1 == null )
909            {
910                return 1;
911            }
912            if ( value2 == null )
913            {
914                return -1;
915            }
916            return _btree._comparator.compare( value1, value2 );
917        }
918    
919    
920        static byte[] readByteArray( ObjectInput in ) throws IOException
921        {
922            int len = in.readInt();
923            if ( len < 0 )
924            {
925                return null;
926            }
927            byte[] buf = new byte[len];
928            in.readFully( buf );
929            return buf;
930        }
931    
932    
933        static void writeByteArray( ObjectOutput out, byte[] buf ) throws IOException
934        {
935            if ( buf == null )
936            {
937                out.writeInt( -1 );
938            }
939            else
940            {
941                out.writeInt( buf.length );
942                out.write( buf );
943            }
944        }
945    
946    
947        /**
948         * Dump the structure of the tree on the screen.  This is used for debugging
949         * purposes only.
950         */
951        private void dump( int height )
952        {
953            String prefix = "";
954            for ( int i = 0; i < height; i++ )
955            {
956                prefix += "    ";
957            }
958            System.out.println( prefix + "-------------------------------------- BPage recid=" + _recid );
959            System.out.println( prefix + "first=" + _first );
960            for ( int i = 0; i < _btree._pageSize; i++ )
961            {
962                if ( _isLeaf )
963                {
964                    System.out.println( prefix + "BPage [" + i + "] " + _keys[i] + " " + _values[i] );
965                }
966                else
967                {
968                    System.out.println( prefix + "BPage [" + i + "] " + _keys[i] + " " + _children[i] );
969                }
970            }
971            System.out.println( prefix + "--------------------------------------" );
972        }
973    
974    
975        /**
976         * Recursively dump the state of the BTree on screen.  This is used for
977         * debugging purposes only.
978         */
979        void dumpRecursive( int height, int level ) throws IOException
980        {
981            height -= 1;
982            level += 1;
983            if ( height > 0 )
984            {
985                for ( int i = _first; i < _btree._pageSize; i++ )
986                {
987                    if ( _keys[i] == null )
988                        break;
989                    BPage child = childBPage( i );
990                    child.dump( level );
991                    child.dumpRecursive( height, level );
992                }
993            }
994        }
995    
996    
997        /**
998         * Assert the ordering of the keys on the BPage.  This is used for testing
999         * purposes only.
1000         */
1001        private void assertConsistency()
1002        {
1003            for ( int i = _first; i < _btree._pageSize - 1; i++ )
1004            {
1005                if ( compare( ( byte[] ) _keys[i], ( byte[] ) _keys[i + 1] ) >= 0 )
1006                {
1007                    dump( 0 );
1008                    throw new Error( I18n.err( I18n.ERR_515 ) );
1009                }
1010            }
1011        }
1012    
1013    
1014        /**
1015         * Recursively assert the ordering of the BPage entries on this page
1016         * and sub-pages.  This is used for testing purposes only.
1017         */
1018        void assertConsistencyRecursive( int height ) throws IOException
1019        {
1020            assertConsistency();
1021            if ( --height > 0 )
1022            {
1023                for ( int i = _first; i < _btree._pageSize; i++ )
1024                {
1025                    if ( _keys[i] == null )
1026                        break;
1027                    BPage child = childBPage( i );
1028                    if ( compare( ( byte[] ) _keys[i], child.getLargestKey() ) != 0 )
1029                    {
1030                        dump( 0 );
1031                        child.dump( 0 );
1032                        throw new Error( I18n.err( I18n.ERR_516 ) );
1033                    }
1034                    child.assertConsistencyRecursive( height );
1035                }
1036            }
1037        }
1038    
1039    
1040        /**
1041         * Deserialize the content of an object from a byte array.
1042         *
1043         * @param serialized Byte array representation of the object
1044         * @return deserialized object
1045         *
1046         */
1047        public Object deserialize( byte[] serialized ) throws IOException
1048        {
1049            ByteArrayInputStream bais;
1050            ObjectInputStream ois;
1051            BPage bpage;
1052    
1053            bpage = new BPage();
1054            bais = new ByteArrayInputStream( serialized );
1055            ois = new ObjectInputStream( bais );
1056    
1057            bpage._isLeaf = ois.readBoolean();
1058            if ( bpage._isLeaf )
1059            {
1060                bpage._previous = ois.readLong();
1061                bpage._next = ois.readLong();
1062            }
1063    
1064            bpage._first = ois.readInt();
1065    
1066            bpage._keys = new Object[_btree._pageSize];
1067            try
1068            {
1069                for ( int i = bpage._first; i < _btree._pageSize; i++ )
1070                {
1071                    if ( _btree._keySerializer == null )
1072                    {
1073                        bpage._keys[i] = ois.readObject();
1074                    }
1075                    else
1076                    {
1077                        serialized = readByteArray( ois );
1078                        if ( serialized != null )
1079                        {
1080                            bpage._keys[i] = _btree._keySerializer.deserialize( serialized );
1081                        }
1082                    }
1083                }
1084            }
1085            catch ( ClassNotFoundException except )
1086            {
1087                throw new IOException( except.getLocalizedMessage() );
1088            }
1089    
1090            if ( bpage._isLeaf )
1091            {
1092                bpage._values = new Object[_btree._pageSize];
1093                try
1094                {
1095                    for ( int i = bpage._first; i < _btree._pageSize; i++ )
1096                    {
1097                        if ( _btree._valueSerializer == null )
1098                        {
1099                            bpage._values[i] = ois.readObject();
1100                        }
1101                        else
1102                        {
1103                            serialized = readByteArray( ois );
1104                            if ( serialized != null )
1105                            {
1106                                bpage._values[i] = _btree._valueSerializer.deserialize( serialized );
1107                            }
1108                        }
1109                    }
1110                }
1111                catch ( ClassNotFoundException except )
1112                {
1113                    throw new IOException( except.getLocalizedMessage() );
1114                }
1115            }
1116            else
1117            {
1118                bpage._children = new long[_btree._pageSize];
1119                for ( int i = bpage._first; i < _btree._pageSize; i++ )
1120                {
1121                    bpage._children[i] = ois.readLong();
1122                }
1123            }
1124            ois.close();
1125            bais.close();
1126    
1127            return bpage;
1128        }
1129    
1130    
1131        /** 
1132         * Serialize the content of an object into a byte array.
1133         *
1134         * @param obj Object to serialize
1135         * @return a byte array representing the object's state
1136         *
1137         */
1138        public byte[] serialize( Object obj ) throws IOException
1139        {
1140            byte[] serialized;
1141            ByteArrayOutputStream baos;
1142            ObjectOutputStream oos;
1143            BPage bpage;
1144            byte[] data;
1145    
1146            // note:  It is assumed that BPage instance doing the serialization is the parent
1147            // of the BPage object being serialized.
1148    
1149            bpage = ( BPage ) obj;
1150            baos = new ByteArrayOutputStream();
1151            oos = new ObjectOutputStream( baos );
1152    
1153            oos.writeBoolean( bpage._isLeaf );
1154            if ( bpage._isLeaf )
1155            {
1156                oos.writeLong( bpage._previous );
1157                oos.writeLong( bpage._next );
1158            }
1159    
1160            oos.writeInt( bpage._first );
1161    
1162            for ( int i = bpage._first; i < _btree._pageSize; i++ )
1163            {
1164                if ( _btree._keySerializer == null )
1165                {
1166                    oos.writeObject( bpage._keys[i] );
1167                }
1168                else
1169                {
1170                    if ( bpage._keys[i] != null )
1171                    {
1172                        serialized = _btree._keySerializer.serialize( bpage._keys[i] );
1173                        writeByteArray( oos, serialized );
1174                    }
1175                    else
1176                    {
1177                        writeByteArray( oos, null );
1178                    }
1179                }
1180            }
1181    
1182            if ( bpage._isLeaf )
1183            {
1184                for ( int i = bpage._first; i < _btree._pageSize; i++ )
1185                {
1186                    if ( _btree._valueSerializer == null )
1187                    {
1188                        oos.writeObject( bpage._values[i] );
1189                    }
1190                    else
1191                    {
1192                        if ( bpage._values[i] != null )
1193                        {
1194                            serialized = _btree._valueSerializer.serialize( bpage._values[i] );
1195                            writeByteArray( oos, serialized );
1196                        }
1197                        else
1198                        {
1199                            writeByteArray( oos, null );
1200                        }
1201                    }
1202                }
1203            }
1204            else
1205            {
1206                for ( int i = bpage._first; i < _btree._pageSize; i++ )
1207                {
1208                    oos.writeLong( bpage._children[i] );
1209                }
1210            }
1211    
1212            oos.flush();
1213            data = baos.toByteArray();
1214            oos.close();
1215            baos.close();
1216            return data;
1217        }
1218    
1219        /** STATIC INNER CLASS
1220         *  Result from insert() method call
1221         */
1222        static class InsertResult
1223        {
1224    
1225            /**
1226             * Overflow page.
1227             */
1228            BPage _overflow;
1229    
1230            /**
1231             * Existing value for the insertion key.
1232             */
1233            Object _existing;
1234    
1235        }
1236    
1237        /** STATIC INNER CLASS
1238         *  Result from remove() method call
1239         */
1240        static class RemoveResult
1241        {
1242    
1243            /**
1244             * Set to true if underlying pages underflowed
1245             */
1246            boolean _underflow;
1247    
1248            /**
1249             * Removed entry value
1250             */
1251            Object _value;
1252        }
1253    
1254        /** PRIVATE INNER CLASS
1255         * Browser to traverse leaf BPages.
1256         */
1257        static class Browser extends TupleBrowser
1258        {
1259    
1260            /**
1261             * Current page.
1262             */
1263            private BPage _page;
1264    
1265            /**
1266             * Current index in the page.  The index positionned on the next
1267             * tuple to return.
1268             */
1269            private int _index;
1270    
1271    
1272            /**
1273             * Create a browser.
1274             *
1275             * @param page Current page
1276             * @param index Position of the next tuple to return.
1277             */
1278            Browser( BPage page, int index )
1279            {
1280                _page = page;
1281                _index = index;
1282            }
1283    
1284    
1285            public boolean getNext( Tuple tuple ) throws IOException
1286            {
1287                if ( _index < _page._btree._pageSize )
1288                {
1289                    if ( _page._keys[_index] == null )
1290                    {
1291                        // reached end of the tree.
1292                        return false;
1293                    }
1294                }
1295                else if ( _page._next != 0 )
1296                {
1297                    // move to next page
1298                    _page = _page.loadBPage( _page._next );
1299                    _index = _page._first;
1300                }
1301                tuple.setKey( _page._keys[_index] );
1302                tuple.setValue( _page._values[_index] );
1303                _index++;
1304                return true;
1305            }
1306    
1307    
1308            public boolean getPrevious( Tuple tuple ) throws IOException
1309            {
1310                if ( _index == _page._first )
1311                {
1312    
1313                    if ( _page._previous != 0 )
1314                    {
1315                        _page = _page.loadBPage( _page._previous );
1316                        _index = _page._btree._pageSize;
1317                    }
1318                    else
1319                    {
1320                        // reached beginning of the tree
1321                        return false;
1322                    }
1323                }
1324                _index--;
1325                tuple.setKey( _page._keys[_index] );
1326                tuple.setValue( _page._values[_index] );
1327                return true;
1328    
1329            }
1330        }
1331    
1332    }