Bnode


1   package com.quadcap.sql.index;
2   
3   /* Copyright 1997 - 2003 Quadcap Software.  All rights reserved.
4    *
5    * This software is distributed under the Quadcap Free Software License.
6    * This software may be used or modified for any purpose, personal or
7    * commercial.  Open Source redistributions are permitted.  Commercial
8    * redistribution of larger works derived from, or works which bundle
9    * this software requires a "Commercial Redistribution License"; see
10   * http://www.quadcap.com/purchase.
11   *
12   * Redistributions qualify as "Open Source" under  one of the following terms:
13   *   
14   *    Redistributions are made at no charge beyond the reasonable cost of
15   *    materials and delivery.
16   *
17   *    Redistributions are accompanied by a copy of the Source Code or by an
18   *    irrevocable offer to provide a copy of the Source Code for up to three
19   *    years at the cost of materials and delivery.  Such redistributions
20   *    must allow further use, modification, and redistribution of the Source
21   *    Code under substantially the same terms as this license.
22   *
23   * Redistributions of source code must retain the copyright notices as they
24   * appear in each source code file, these license terms, and the
25   * disclaimer/limitation of liability set forth as paragraph 6 below.
26   *
27   * Redistributions in binary form must reproduce this Copyright Notice,
28   * these license terms, and the disclaimer/limitation of liability set
29   * forth as paragraph 6 below, in the documentation and/or other materials
30   * provided with the distribution.
31   *
32   * The Software is provided on an "AS IS" basis.  No warranty is
33   * provided that the Software is free of defects, or fit for a
34   * particular purpose.  
35   *
36   * Limitation of Liability. Quadcap Software shall not be liable
37   * for any damages suffered by the Licensee or any third party resulting
38   * from use of the Software.
39   */
40  
41  import java.io.IOException  ;
42  import java.io.PrintStream  ;
43  
44  import com.quadcap.sql.file.Block;
45  import com.quadcap.sql.file.BlockFile;
46  import com.quadcap.sql.file.ByteUtil;
47  import com.quadcap.sql.file.SubPageManager;
48  
49  import com.quadcap.util.Debug;
50  import com.quadcap.util.Util;
51  
52  /**
53   * This class represents a node in the btree.
54   * <p>
55   *
56   * <b>Things to think about:</b>
57   * <p>
58   * <UL>
59   * <LI>Key Compression using dictionary?  With a large enough node, say
60   *  4 or 8 k, you could perform a block compression
61   * <LI>Key Endianness (X.500 keys are LSB, most others are MSB)
62   * <LI>Large data stored in overflow areas (blockstream)
63   * <LI>Thread-safeness
64   * <LI>Improve block garbage collection (it appears that some deleted
65   *  keys aren't properly counted as garbage!)
66   * </UL>
67   *
68   * @author Stan Bailes
69   */
70  
71  // struct node {
72  //     int      count;  /* number of items in this node */
73  //     int      dataBottom; /* data area -- grows downward */
74  //     int   flags;     /* isRoot, */
75  //     int[]    keyIndex;   /* keyrefs, grows up */
76  //     byte[]   empty;      /* ... empty in the middle ... */
77  //     byte[]   data;       /* key + data, grows down */
78  // }
79  
80  public class Bnode {
81      //#ifdef DEBUG
82      static final boolean paranoid = false;
83      //#endif
84      
85      Btree           tree;
86      BlockFile           file;
87      long            blockRef;
88  
89      /** The number of octets in the representation of a reference to
90       * a byte offset in the data area of this block.   Currently,
91       * bnode blocks can't be larger than 65536 because of the
92       * two byte ref size.
93       */
94      public static final int REF_SIZE        = 2;
95  
96      /** Number of key/data pairs in this node.  */
97      static final int        fCount          = 0;
98  
99      /** Bottom of data area -- grows downward. */
100     static final int        fDataBOS        = 4;
101 
102     /** Flags */
103     static final int        fFlags          = 8;
104     static final int            IS_LEAF         = 0x0001;
105     static final int            BNODE_MAGICF        = 0xff00;
106     static final int            BNODE_MAGICV        = 0xbd00;
107 
108     /**
109      * Amount of space that could be reclaimed by repacking the
110      * node.  When keys are deleted, we don't immediately remove
111      * the key/data pair in the data area.  Instead, we remove the
112      * pointer the pair from the key index list, and record (here)
113      * the size of the key/data pair.  Later, when the block becomes
114      * full, we reclaim this space by repacking the data area to
115      * eliminate the holes.
116      */
117     static final int        fGarbage        = 12;
118 
119     static final int        fParent         = 16;
120 
121     /** Start of key indices. */
122     static final int        fIndices        = 24;
123     
124 
125     /**
126      * Construct a node from a buffer.
127      * @param tree the Btree containing this node
128      * @param blockRef the block number in <b>file</b> of this node.
129      */
130     public Bnode(Btree tree, long blockRef) {
131     //#ifdef DEBUG
132     if (Trace.bit(2)) {
133         Debug.println("Bnode(" + blockRef + ")");
134     }
135     //#endif
136     this.tree = tree;
137     this.file = tree.file;
138     this.blockRef = blockRef;   
139     }
140 
141     /** <hr><font size =+1>Index Interface</font> <!----------------------!> */
142 
143     /**
144      * Return the number of keys in this subtree.  This implicitly only
145      * counts entries in the leaf nodes.
146      */
147     public int size() throws IOException   {
148         Block b = getBlock();
149         try {
150             return size(b);
151         } finally {
152             b.decrRefCount();
153         }
154     }
155     
156     public int size(Block b) throws IOException   {
157         int tot = 0;
158         for (int i = 0; i < getCount(b); i++) {
159             Block c = getBlock(blockRef(b, i));
160             try {
161                 if (isLeaf(c)) {
162                     tot += getCount(c);
163                 } else {
164                     tot += size(c);
165                 }
166             } finally {
167                 c.decrRefCount();
168             }
169         }
170         return tot;
171     }
172 
173     /**
174      * Implement the get operation.
175      * @param key the search key
176      * @return if the get succeeds, the data is returned as a byte array;
177      *      if the get fails, <b>null</b> is returned.
178      */
179     public final byte[] get(byte[] key, int klen) throws IOException   {
180     //#ifdef DEBUG
181     if (Trace.bit(2)) {
182         Debug.println("Bnode[" + blockRef + "] get(" +
183               Util.hexBytes(key) + ")");
184     }
185     //#endif
186     Block b = getBlock();
187     byte[] ret = null;
188     try {
189         ret = get(b, key, klen);
190     } finally {
191         b.decrRefCount();
192     }
193     return ret;
194     }
195 
196 //      /**
197 //       * Leaf level get operation
198 //       */
199 //      public final int get(byte[] key, int koff,
200 //                           byte[] data, int off, int len) throws IOException {
201 //      Block b = getBlock();
202 //          try {
203 //              return get(b, key, koff, data, off, len);
204 //          } finally {
205 //              b.decrRefCount();
206 //          }
207 //      }
208 
209     /**
210      * Implement the set operation.
211      * @param key the key
212      * @param data the data
213      */
214     public final boolean set(byte[] key, int klen,
215                              byte[] data, int doff, int dlen,
216                              boolean insOk, boolean updOk) throws IOException   {
217     //#ifdef DEBUG
218     if (Trace.bit(2)) {
219         Debug.println("[" + blockRef + "] set(" +
220               Util.hexBytes(key) + ", " +
221                           Util.hexBytes(data) + ")");
222     }
223     //#endif
224     Block b = getBlock();
225     try {
226         return set(b, key, klen, data, doff, dlen, insOk, updOk);
227     } finally {
228         b.decrRefCount();
229     }
230     }
231 
232     /**
233      * Implement the delete operation.
234      * @param key the key
235      */
236     public final boolean delete(byte[] key) throws IOException   {
237     Block b = getBlock();
238     try {
239         return delete(b, key);
240     } finally {
241         b.decrRefCount();
242     }
243     }
244 
245     /**
246      * A helper function to perform a single-level of the recursive search.
247      * @param b the block to be searched.
248      * @param key the search key
249      * @return if found, the data, else null
250      */
251     final byte[] get(Block b, byte[] key, int klen) throws IOException   {
252     byte[] ret = null;
253     int bs = bsearch(b, key, klen);
254     if (!isLeaf(b)) {
255         Block c = getSearchBlock(b, bs);
256         try {
257         ret = get(c, key, klen);
258         } finally {
259         c.decrRefCount();
260         }
261     } else if (bs >= 0) {
262             ret = dataAtPos(b, bs);
263         }
264     //#ifdef DEBUG
265     if (paranoid) { checkBlock(b); }
266     //#endif
267     return ret;
268     }
269 
270     final Block getSearchBlock(Block b, int bs) throws IOException   {
271         int index = bs < 0 ? (-1-bs) : bs;
272         if (bs < 0) {
273             index = index - 1;
274             if (index < 0) {
275                 index = 0;
276             }
277         }
278         Block c = getBlock(blockRef(b, index));
279         return c;
280     }
281 
282 //      final int get(Block b, byte[] key, int koff,
283 //                    byte[] data, int off, int len)
284 //          throws IOException
285 //      {
286 //          int ret = -1;
287 //      int bs = bsearch(b, tree.compare, key, 0, getCount(b)-1);
288 //          if (!isLeaf(b)) {
289 //          Block c = getSearchBlock(b, bs);
290 //          try {
291 //          ret = get(c, key, koff, data, off, len);
292 //          } finally {
293 //          c.decrRefCount();
294 //          }
295 //      } else {
296 //              if (bs >= 0) {
297 //                  ret = dataAtPos(b, bs, koff, data, off, len);
298 //              } else {
299 //                  ret = -1;
300 //              }
301 //          }
302 //      return ret;
303 //      }
304 
305     /**
306      * Initialize an empty <b>BNode</b>.
307      * <p><b>PRECONDITION:</b>Hold lock on <code>b</code>.
308      * @param b the block to be initialized.
309      */
310     final void init(Block b, boolean isLeaf) throws IOException    {
311     setCount(b, 0);
312     setFlags(b, (isLeaf ? IS_LEAF : 0) | BNODE_MAGICV);
313     setBos(b, file.getPageSize());
314     setGarbage(b, 0);
315     setParent(b, 0);
316     }
317 
318     final void init(boolean f) throws IOException   {
319     Block b = getBlock();
320     try {
321         init(b, f);
322     } finally {
323         b.decrRefCount();
324     }
325     }
326 
327     final void checkMagic() throws IOException   {
328     Block b = getBlock();
329     try {
330         if ((getFlags(b) & BNODE_MAGICF) != BNODE_MAGICV) {
331         throw new IOException  ("Not a valid index node: " +
332                       SubPageManager.toString(b.getPageNum()));
333         }
334     } finally {
335         b.decrRefCount();
336     }
337     }
338     
339     /**
340      * Free the resources associated with this block.  If the block is a
341      * non-leaf node, free the entire subtree.
342      */
343     public final void free() throws IOException   {
344     free(blockRef);
345     }
346     
347     /**
348      * Free the resources associated with the specified block.  If the block is a
349      * non-leaf node, free the entire subtree.
350      */
351     private final void free(long blockNum) throws IOException   {
352         //#ifdef DEBUG
353     if (blockNum == 0) {
354         Debug.println("************************** Trying to free block 0!");
355         return;
356     }
357         //#endif
358     Block b = getBlock(blockNum);
359     //#ifdef DEBUG
360     if (Trace.bit(2)) {
361         Debug.println("free(" + blockNum + ")");
362         display(b, Debug.debugStream, false);
363     }
364     //#endif
365     try {
366         if (!isLeaf(b)) {
367         for (int i = 0; i < getCount(b); i++) {
368             free(blockRef(b, i));
369         }
370         }
371         file.freePage(b.getPageNum());
372     } finally {
373         b.decrRefCount();
374     }
375     }
376 
377     /**
378      * Perform a binary search of the keys in the specified block, searching
379      * for the given key.  If the key is found in the block, return the
380      * index of the matching key.  If the key isn't
381      * found, return < 0, and for the key index which is the smallest
382      * existing key greater than the given key, return
383      * <code>0 - (index+1)</code>.
384      * @param b the block to be searched.
385      * @param key the search key
386      * @param lo index of smallest element in search region
387      * @param hi index of largest element in search region
388      * @return if found, the index of the matching key/data pair. If not
389      *      found, return the index where the data would be found
390      *      as an expression of the form:<p>
391      *      <code>0 - (index + 1)</code>
392      */
393     final static int bsearch(Block b, Comparator c, byte[] key,
394                              int klen, int lo, int hi)
395         throws IOException  
396     {
397     while (hi >= lo) {
398         int mid = (hi + lo) / 2;
399         int ret = keyCompareAtPos(c, key, klen, b, mid);
400         if (ret < 0) hi = mid-1;
401         else if (ret > 0) lo = mid+1;
402         else return mid;
403     }
404     return 0 - (hi+2);
405     }
406 
407     /**
408      * Perform a binary search of the keys in the specified block, searching
409      * for the given key.  If the key is found in the block, return the
410      * index of the matching key.  If the key isn't
411      * found, return < 0, and for the key index which is the smallest
412      * existing key greater than the given key, return
413      * <code>0 - (index+1)</code>.
414      * @param b the block to be searched.
415      * @param key the search key
416      * @return if found, the index of the matching key/data pair. If not
417      *      found, return the index where the data would be found
418      *      as an expression of the form:<p>
419      *      <code>0 - (index + 1)</code>
420      */
421     final int bsearch(Block b, byte[] key, int klen) throws IOException   {
422     return bsearch(b, tree.compare, key, klen, 0, getCount(b)-1);
423     }
424 
425     /**
426      * Return the data for a specified key as an integer
427      */
428     final static long blockRef(Block b, int index) throws IOException   {
429     return longDataAtPos(b, index);
430     }
431 
432     /**
433      * Recursive implementation of <code>set(key, data)</code>.<p>
434      * <b>Precondition</b>: The caller must already have a write-lock on
435      *  <code>b</code>.
436      * @param b the block to be searched
437      * @param key the search key
438      * @param data the data associated with the key
439      * @return true if the key already existed before the set, false otherwise.
440      */
441     final boolean set(Block b, byte[] key, int klen,
442                       byte[] data, int doff, int dlen,
443                       boolean insOk, boolean updOk) throws IOException   {
444     //#ifdef DEBUG
445     byte[] save = null;
446     if (paranoid) {
447         byte[] d = (byte[])b.getData();
448         save = new byte[d.length];
449         System.arraycopy(d, 0, save, 0, d.length);
450     }
451     //#endif
452     int bs = bsearch(b, key, klen);
453         if (bs < 0 && !insOk) {
454             throw new IOException  ("Key not found");
455         } else if (bs >= 0 && !updOk) {
456             throw new IOException  ("Key not unique"); 
457         }
458     int index = bs < 0 ? (-1-bs) : bs;
459     boolean ret = false;
460     if (isLeaf(b)) {
461         boolean replace = (bs >= 0);
462         setKey(b, index, key, klen, data, doff, dlen, replace);
463         ret = replace;
464     } else {
465         if (bs < 0) {
466         index = index - 1;
467         if (index < 0) index = 0;
468         }
469         Block c = getBlock(blockRef(b, index));
470         try {
471         ret = set(c, key, klen, data, doff, dlen, insOk, updOk);
472         } finally {
473         c.decrRefCount();
474         }
475     }
476     //#ifdef DEBUG
477     if (paranoid) {
478         try {
479         checkBlock(b);
480         } catch (RuntimeException   e) {
481         b.setData(save);
482         Debug.println("bs = " + bs);
483         Debug.println("index = " + index);
484         Debug.println("isLeaf() = " + isLeaf(b));
485         Debug.println("key = " + Util.hexBytes(key));
486         Debug.println("data = " + Util.hexBytes(data));
487         Debug.println("checkSpace = " +
488                   debugcheckSpace(b, index, klen, dlen, bs>=0));
489         Debug.println("old block:");
490         display(b, Debug.debugStream, false);
491         }
492     }
493     //#endif
494     return ret;
495     }
496 
497     /**
498      * Recursive implementation of <code>delete(key)</code>.
499      * @param b the block to be searched
500      * @param key the search key
501      * @return true if the key already existed before the delete,
502      *          false otherwise.
503      */
504     final boolean delete(Block b, byte[] key) throws IOException   {
505     boolean ret = false;
506     boolean del = false;
507     int bs = bsearch(b, key, key.length);
508     int index = bs < 0 ? (-1-bs) : bs;
509 //  Debug.println(2, "delete([" + b.getPageNum() + "] " +
510 //            keybytes(key) +
511 //            "): bs = " + bs + ", index = " + index);
512     if (isLeaf(b)) {
513         if (bs >= 0) {
514         del = deleteKeyAtPos(b, index, false);
515         ret = true;
516         }
517     } else {
518         if (bs < 0) {
519         index = index - 1;
520         if (index < 0) index = 0;
521         }
522         Block c = getBlock(blockRef(b, index));
523         try {
524         ret = delete(c, key);
525         } finally {
526         c.decrRefCount();
527         }
528     }
529     //#ifdef DEBUG
530     if (paranoid && !del) checkBlock(b);
531     //#endif
532     return ret;
533     }
534 
535     //#ifdef DEBUG
536     final void checkBlock(Block b) throws IOException   {
537     int g1 = getGarbage(b);
538     int tk = 0;
539     for (int i = 0; i < getCount(b); i++) {
540         tk += existingKeyLength(b, i);
541         if (i > 0) {
542         byte[] k1 = keyAtPos(b, i-1);
543         byte[] k2 = keyAtPos(b, i);
544         try {
545             if (tree.compare.compare(k1, 0, k1.length,
546                          k2, 0, k2.length) >= 0) {
547             try {
548                 display(b, System.out, false);
549             } catch (Exception   e) {}
550             throw new RuntimeException  ("Bad key ordering");
551             }
552         } catch (RuntimeException   e) {
553             try {
554             display(b, System.out, false);
555             } catch (Exception   ee) {
556             }
557             throw e;
558         }
559         }
560     }
561     int sk = file.getPageSize() - getBos(b);
562     if (tk + g1 != sk) {
563         try {
564         display(b, System.out, false);
565         } catch (Exception   e) {}
566         throw new RuntimeException  ("checkBlock: failure, " + (tk+g1) + " != " +
567                        sk);
568     }
569 
570     }
571     //#endif
572 
573     /**
574      * Given a block and a key index, return the data for that index as a new
575      * byte array.
576      * @param b the block on which to operate.
577      * @param index the index of the item for which the data is to be retrieved
578      * @return the data for the key at the specified position in the node.
579      */
580     final static byte[] dataAtPos(Block b, int index) {
581     int keyIndex = getKeyIndex(b, index);
582 
583     int[] start = new int[1];
584     int keylen = getKeyLen(b, keyIndex, start);
585     int keystart = start[0];
586 
587     int datastart = keystart + keylen;
588     int datalen = getKeyLen(b, datastart, start);
589     datastart = start[0];
590     byte[] data = new byte[datalen];
591     b.read(datastart, data, 0, data.length);
592     return data;
593     }
594 
595     final static int dataAtPos(Block b, int index, int koff,
596                                byte[] data, int off, int len)
597     {
598     int keyIndex = getKeyIndex(b, index);
599 
600     int[] start = new int[1];
601     int keylen = getKeyLen(b, keyIndex, start);
602     int keystart = start[0];
603 
604     int datastart = keystart + keylen;
605     datastart = start[0];
606 
607     return b.read(datastart + koff, data, off, len);
608     }
609 
610     /**
611      * Given a block and a key index, return the data for that index as
612      * a long.
613      * @param b the block on which to operate.
614      * @param index the index of the item for which the data is to be retrieved
615      * @return the data for the key at the specified position in the node.
616      */
617     final static long longDataAtPos(Block b, int index) {
618     int keyIndex = getKeyIndex(b, index);
619 
620     keyIndex = getKeyEnd(b, keyIndex);  // skip to data
621     if (b.readByte(keyIndex) != 8) {
622         throw new RuntimeException  ("not a long: " + keyIndex + ": " + b.readByte(keyIndex));
623     }
624     return b.readLong(keyIndex + 1);
625     }
626 
627     /**
628      * Compute the total length of an existing key data pair, including
629      * both key and data length fields.
630      * @param b the block on which to operate.
631      * @param index the index of the item for which the data is to be retrieved
632      * @return the total number of data area bytes consumed by this item.
633      */
634     final static int existingKeyLength(Block b, int index) {
635     int keyIndex = getKeyIndex(b, index);
636 
637     int[] start = new int[1];
638     int keylen = getKeyLen(b, keyIndex, start);
639     int keystart = start[0];
640 
641     int datastart = keystart + keylen;
642     int datalen = getKeyLen(b, datastart, start);
643     datastart = start[0];
644     int end = datastart + datalen;
645     return end - keyIndex;
646     }
647 
648     /**
649      * Given a block and a key index, return the key for that index as a new
650      * byte array.
651      * @param b the block on which to operate.
652      * @param index the index of the item for which the key is to be retrieved
653      */
654     final static byte[] keyAtPos(Block b, int index) {
655     int keyIndex = getKeyIndex(b, index);
656 
657     int[] start = new int[1];
658     int keylen = getKeyLen(b, keyIndex, start);
659     int keystart = start[0];
660 
661     byte[] key = new byte[keylen];
662     b.read(keystart, key, 0, key.length);
663     return key;
664     }
665 
666     final static int getBytes(Block b, int pos, byte[] buf, int[] lenret) {
667     int len = b.readByte(pos++) & 0xff;
668     if ((len & 0x80) != 0) {
669         int cnt = len & 0x7f;
670         len = 0;
671         while (cnt-- > 0) {
672         len <<= 8;
673                 len += (b.readByte(pos++) & 0xff);
674         }
675     }
676         lenret[0] = len;
677         if (len > buf.length) return 0 - len;
678     b.read(pos, buf, 0, len);
679         return pos + len;
680     }
681         
682     /**
683      * Given a block and a key index, return the key for that index as a new
684      * byte array.
685      * @param b the block on which to operate.
686      * @param index the index of the item for which the key is to be retrieved
687      * @param buf the buffer into which the key bytes should be places
688      * @param off the offset into the buffer
689      * @param len the maximum number of bytes to write to the buffer
690      *
691      * @return the number of bytes returned, if sucessful.  If the buffer
692      *    isn't big enough, we return a negative number '0 - k', where
693      *    'k' is the actual key length.
694      */
695     public final static boolean getKeyAndData(Block b, int index,
696                                               byte[] k, byte[] d,
697                                               int[] lengths) {
698     int pos = getKeyIndex(b, index);
699         pos = getBytes(b, pos, k, lengths);
700         int savelen = lengths[0];
701         if (pos < 0) return false;
702         pos = getBytes(b, pos, d, lengths);
703         lengths[1] = lengths[0];
704         lengths[0] = savelen;
705         if (pos < 0) return false;
706         return true;
707     }
708 
709     /**
710      * Perform a key comparison with the specified key in the block.
711      * @param c the compare function
712      * @param key the compare key
713      * @param b the block to be compared
714      * @param index the position of the key to be compared to the compare key
715      *
716      * @return the integer compare value (usu: -1, 0, 1)
717      */
718     static final int keyCompareAtPos(Comparator c, byte[] key, int klen,
719                      Block b, int index) throws IOException   {
720     int keypos = getKeyIndex(b, index);
721     int r = getKeyLen(b, keypos);
722     int start = (r >> 16) & 0xffff;
723     int len = r & 0xffff;
724     byte[] buf = (byte[])b.getData();
725     int ret = c.compare(key, 0, klen, buf, start, len);
726         return ret;
727     }
728 
729     /**
730      * Find the length of the specified key, as well as the byte offset
731      * to the start of the key.
732      *
733      * @param b the B-node
734      * @param keypos the buffer offset where the key/data pair starts.
735      * @param keystart an <b>out</b> parameter, used to return the buffer
736      *      offset where the actual key begins.
737      */
738     static final int getKeyLen(Block b, int keypos, int[] keystart) {
739     int len = b.readByte(keypos++) & 0xff;
740     if ((len & 0x80) != 0) {
741         int cnt = len & 0x7f;
742         len = 0;
743         while (cnt-- > 0) {
744         len <<= 8; len += (b.readByte(keypos++) & 0xff);
745         }
746     }
747     keystart[0] = keypos;
748     return len;
749     }
750 
751     /**
752      * Find the length of the specified key, as well as the byte offset
753      * to the start of the key.
754      *
755      * @param b the B-node
756      * @param keypos the buffer offset where the key/data pair starts.
757      * @return the key length
758      */
759     final static int getKeyLen(Block b, int keypos) {
760     int len = b.readByte(keypos++) & 0xff;
761     if ((len & 0x80) != 0) {
762         int cnt = len & 0x7f;
763         len = 0;
764         while (cnt-- > 0) {
765         len <<= 8; len += (b.readByte(keypos++) & 0xff);
766         }
767     }
768     return ((keypos & 0xffff) << 16) | (len & 0xffff);
769     }
770 
771     /**
772      * Find the length of the specified key, as well as the byte offset
773      * to the start of the key.
774      *
775      * @param b the B-node
776      * @param keypos the buffer offset where the key/data pair starts.
777      * @return two 16-bit integers {start, len} encoded in a 32 bit int.
778      */
779     static final int getKeyEnd(Block b, int keypos) {
780     int len = b.readByte(keypos++) & 0xff;
781     if ((len & 0x80) != 0) {
782         int cnt = len & 0x7f;
783         len = 0;
784         while (cnt-- > 0) {
785         len <<= 8; len += (b.readByte(keypos++) & 0xff);
786         }
787     }
788     return keypos + len;
789     }
790 
791     /**
792      * Compute the total number of bytes that will be required to store
793      * the byte array 'b' plus its length code.
794      * @param b the byte array
795      * @return the length of the byte array plus the length of the length
796      *      code.
797      */
798     final static int totalLength(int len) {
799     int lenlen = 1;
800     if (len > 0x7f) {
801         lenlen++;
802         if (len > 0xff) {
803         lenlen++;
804         if (len > 0xffff) {
805             lenlen++;
806             if (len > 0xffffff) {
807             lenlen++;
808             }
809         }
810         }
811     }
812     return len + lenlen;
813     }
814 
815     /**
816      * Insert a key/data pair at the bottom of the data area and
817      * return its offset.  This method does <b>NOT</b> check the
818      * capacity of the buffer -- it is assumed that the caller has
819      * already ensured that enough space is available.
820      * @param b the block to operate on 
821      * @param key the search key
822      * @param data the data associated with the key
823      */
824     final static int insertKeyData(Block b, byte[] key, int klen,
825                                    byte[] data, int doff, int dlen) {
826     // ---- insert the key/data pair at the bottom of the data area
827     int bos = getBos(b) - dlen;
828     b.write(bos, data, doff, dlen);
829     bos = writeLenLen(b, bos, dlen) - klen;
830     b.write(bos, key, 0, klen);
831     bos = writeLenLen(b, bos, klen);
832     setBos(b, bos);     // record the new data BOS.
833     return bos;
834     }
835 
836     /**
837      * Insert or replace a key in the specified block, which may or may
838      * not be a leaf block.  Handle split operations: if a split is required,
839      * determine which post-split block this key should be added to.
840      * Also, if the new key happens to be key zero (i.e., the lowest valued
841      * key in this block), then adjust the parent's reference to this block
842      * accordingly.  Although, maybe that can't happen?
843      *
844      * <p><b>PRECONDITION:</b> Lock/ref on block <code>b</code>
845      * <p><b>POSTCONDITION:</b> Lock/ref on block <code>b</code>
846      *
847      * @return the block into which the key was actually stored.  This
848      *      will be different from <code>b</code> if a split was
849      *      necessary.
850      */
851     final Block setKey(Block b, int index, byte[] key, int klen,
852                        byte[] data, int doff, int dlen,
853                        boolean replace)
854     throws IOException  
855     {
856     Block r = b;
857     if (index < 0) {
858         index = bsearch(b, key, klen);
859         if (index < 0) {
860         replace = false;
861         index = -1 - index;
862         }
863     }
864     // if it looks like we're inserting a key lower than the current
865     // low key, remember the old low key, we'll have to update the parent
866     // node.
867     byte[] okey = (index == 0 && getCount(b) > 0) ? keyAtPos(b, 0) : null;
868         
869     if (!setKeyAtPos(b, index, key, klen, data, doff, dlen, replace)) {
870         if (replace) {
871         if (deleteKeyAtPos(b, index, true)) {
872                     //#ifdef DEBUG
873             Debug.println("Just lost b!");
874                     //#endif
875         }
876         }
877         Block[] ba = new Block[2];
878         ba[0] = b;
879         split(ba);
880         b = ba[0];
881         Block nb = ba[1];
882             
883         try {
884         // After split, the key we were trying to add goes
885         // into one of the two split blocks.
886                 int cv = keyCompareAtPos(tree.compare, key, klen, b, 0);
887                 r = cv < 0 ? nb : b;
888 
889         try {
890             int ret = bsearch(r, key, klen);
891             if (ret >= 0) {
892                         //#ifdef DEBUG
893                         Debug.println("After a split operation, the key was " +
894                                       "found to be already present in the " +
895                                       "target block at position " + ret);
896                         Debug.println("The key: " + Util.hexBytes(key));
897                         Debug.println("cv = " + cv);
898                         Debug.println("split L: ");
899                         display(ba[0], Debug.debugStream, false);
900                         Debug.println("split R: ");
901                         display(ba[1], Debug.debugStream, false);
902                         //#endif
903             throw new RuntimeException  (
904                 "internal error in setKey: dup, key = " +
905                             Util.strBytes(key));
906             }
907             ret = -1 - ret;
908             if (!setKeyAtPos(r, ret, key, klen, data, doff, dlen, false)) {
909             throw new RuntimeException  (
910                 "com.quadcap.sql.index.Bnode: " +
911                             "internal error in setKey: no room.  " +
912                             "key length = " + key.length +
913                             ", data.length = " + data.length);
914             }
915             if (ret == 0 && getCount(r) > 1) {
916             newLow(r, keyAtPos(r, 1));
917             }
918         } finally {
919         }
920         } finally {
921         nb.decrRefCount();
922         }
923     } else {
924         if (okey != null && index == 0) {
925                 /* && (!replace || getCount(b) > 1)) */
926         newLow(b, okey);
927         }
928     }
929     return r;
930     }
931 
932     /**
933      * Split this block, by creaing a new block and moving half of this
934      * block's keys into the new block.  Then, add a new key to the parent
935      * block to reflect the new block, and adjust the parent's old reference
936      * to this block to reflect the new key distribution.
937      *
938      * <p><b>PRECONDITION:</b> We have a ref/lock on <code>ba[0]</code>
939      * <p><b>POSTCONDITION:</b> We have a ref on <code>ba[1]</code>
940      *
941      * @param ba a two-element array, with <code>ba[0]</code> being
942      *      the pre-split block, and <code>ba[1]</code> the new block
943      */
944     final void split(Block[] ba) throws IOException   {
945     Block b = ba[0];
946     long nbno = file.newPage();
947         //#ifdef DEBUG
948         if (Trace.bit(5)) {
949             Debug.println(0, "split: new block = " + nbno);
950         }
951         //#endif
952     Bnode node = this.tree.getNode(nbno);
953     node.init(isLeaf(b));
954     Block nb = null;
955         boolean gotException = true;
956         try {
957             nb = node.getBlock();   
958             ba[1] = nb;
959             splitHelp(ba, nbno);
960             gotException = false;
961         } finally {
962             if (gotException) {
963                 if (nb != null) {
964                     nb.decrRefCount();
965                     ba[1] = null;
966                 }
967                 file.freePage(nbno);
968             }
969         }
970     }
971         
972     /**
973      * Split helper:
974      * <p><b>PRECONDITION</b>: Ref/lock on both <code>ba[0], ba[1]</code>
975      */
976     final void splitHelp(Block[] ba, long nbno) throws IOException   {
977     Block b = ba[0];
978     Block nb = ba[1];
979         setParent(nb, getParent(b));
980 
981         //#ifdef DEBUG
982         if (Trace.bit(5)) {
983         Debug.println("BEFORE SPLIT: b");
984         display(b, Debug.debugStream, false);
985         Debug.println("BEFORE SPLIT: nb");
986         display(nb, Debug.debugStream, false);
987     }
988         //#endif
989     
990     int more = capacity(b);
991     int ncnt = 0;
992     for (int i = 0; capacity(nb) > more + getGarbage(b); i++) {
993         byte[] key = keyAtPos(b, i);
994         byte[] data = dataAtPos(b, i);
995         setKeyAtPos(nb, i, key, key.length, data, 0, data.length, false);
996         if (!isLeaf(nb)) {
997         Bnode child = this.tree.getNode(Util.integer(data));
998         Block cb = child.getBlock();
999         try {
1000            Bnode.setParent(cb, nbno);
1001        } finally {
1002            cb.decrRefCount();
1003        }
1004        }
1005        forgetKeyAtPos(b, i);
1006        more += REF_SIZE;
1007        ncnt++;
1008    }
1009    int cnt = getCount(b);
1010    int len = cnt - ncnt;
1011    moveKeys(b, ncnt, 0, len);
1012    setCount(b, len);
1013    gc(b);
1014    //#ifdef DEBUG
1015    if (paranoid) try { 
1016        checkBlock(b); 
1017    } catch (RuntimeException   e) {
1018        Debug.print(e);
1019    }
1020    //#endif
1021
1022    propogateSplit(ba);
1023    }
1024
1025    /**
1026     * After the split operation, propagate information up the tree to
1027     * the parent block about the newly created block and the new key
1028     * distribution.
1029     *
1030     * @param ba a two-element array, with <code>ba[0]</code> being
1031     *      the pre-split block, and <code>ba[1]</code> the new block
1032     */
1033    final void propogateSplit(Block[] ba) throws IOException   {
1034    Block b = ba[0];
1035    Block nb = ba[1];
1036    long b_blk = b.getPageNum();
1037    long parentBlock = getParent(b);
1038    Bnode pnode = null;
1039    if (parentBlock == 0) {
1040        // ---- We're splitting the root block.
1041        // ---- We'd like for block 'b', which is currently the parent,
1042        // ---- to remain so.  So we'll move the data in 'b' to 'b2',
1043        // ---- then rename 'b' to 'parent', and 'b2' to 'b'.
1044        // ---- I think.
1045        long b2 = file.newPage();
1046        Block b2b = getBlock(b2);
1047
1048        // ---- no need to synchronize here, since we already hold the
1049        // ---- lock on the parent node, and nobody else knows about
1050        // ---- b2 yet.
1051        try {
1052        b2b.takeData(b);
1053        parentBlock = b.getPageNum();
1054        setParent(b2b, parentBlock);
1055        pnode = this.tree.getNode(parentBlock);
1056        pnode.init(false);
1057        ba[0] = b = b2b;
1058        if (!isLeaf(b2b)) for (int i = 0; i < getCount(b2b); i++) {
1059                    long cref = blockRef(b2b, i);
1060            Block c = getBlock(cref);
1061            try {
1062            setParent(c, b2);
1063            } finally {
1064            c.decrRefCount();
1065            }
1066        }
1067        b_blk = b2;
1068        } finally {
1069        b2b.decrRefCount();
1070        }
1071            
1072    } else {
1073        pnode = this.tree.getNode(parentBlock);
1074    }
1075
1076    Block pb = pnode.getBlock();
1077    try {
1078        // ---- the parent currently has an entry for the old block,
1079        // ---- but with the key that is now associated with the new
1080        // ---- block.  So we replace the old key, with the new block
1081        // ---- value, and we add a new key, with the old block value.
1082
1083        // ---- replace the old key
1084        byte[] okey = keyAtPos(nb, 0);
1085        byte[] odat = Util.bytes(nb.getPageNum());
1086            Block r = setKey(pb, -1, okey, okey.length, odat, 0, odat.length,
1087                             true);
1088        try {
1089        setParent(nb, r.getPageNum());
1090
1091        // ---- add the new key
1092        byte[] nkey = keyAtPos(b, 0);
1093        byte[] ndat = Util.bytes(b.getPageNum());
1094
1095        if (r != pb) {
1096            // if the parent block was split as a result of
1097            // the previous setKey, then it is possible that
1098            // 'b' and 'nb' were on the boundary of that
1099            // split, and will now have different parent
1100            // blocks.  So we need to figure out which parent
1101            // 'b' should get...
1102
1103            throw new RuntimeException  ("internal error");
1104        }
1105        r = setKey(r, -1, nkey, nkey.length, ndat, 0, ndat.length,
1106                           false);
1107        setParent(b, r.getPageNum());
1108        } finally {
1109        }
1110        
1111    } finally {
1112        pb.decrRefCount();
1113    }
1114
1115    }
1116
1117    /**
1118     * Reclaim the data space occupied by deleted keys.
1119     */
1120    final void gc(Block b) throws IOException   {
1121    //#ifdef DEBUG
1122    byte[] saved = null;
1123    if (paranoid) {
1124        saved = new byte[file.getPageSize()];
1125        System.arraycopy((byte[])b.getData(), 0, saved, 0, saved.length);
1126    }
1127        //#endif
1128
1129    int initcap = capacity(b);
1130    int amt = getGarbage(b);
1131    int cnt = getCount(b);
1132    if (amt > 0) {
1133        int size = 0;
1134        Object  [][] pairs = new Object  [2][cnt];
1135        for (int i = 0; i < cnt; i++) {
1136        size += existingKeyLength(b, i);
1137        pairs[0][i] = keyAtPos(b, i);
1138        pairs[1][i] = dataAtPos(b, i);
1139        }
1140        setBos(b, file.getPageSize());
1141        for (int i = 0; i < cnt; i++) {
1142        byte[] key = (byte[])pairs[0][i];
1143        byte[] data = (byte[])pairs[1][i];
1144        int pos = insertKeyData(b, key, key.length,
1145                                        data, 0, data.length);
1146        setKeyIndex(b, i, pos);
1147        }
1148    }
1149    setGarbage(b, 0);
1150    }
1151
1152    /**
1153     * When an operation results in a change in the smallest key in a block,
1154     * it is necessary to inform the parent block of the change, since the
1155     * parent block key for this block is required to be the key of the
1156     * smallest item in this block.
1157     *
1158     * @param b the block containing the new lowest key
1159     * @param prevLow the key which was previously the lowest key.
1160     *
1161     * @return true if block <code>b</code> is now empty, and has been
1162     *      freed and unlinked from the tree.  Don't touch this block
1163     *      any more!   
1164     */
1165    final boolean newLow(Block b, byte[] prevLow) throws IOException   {
1166    boolean ret = false;
1167    long parentBlock = getParent(b);
1168    if (parentBlock != 0) {
1169        Bnode parent = tree.getNode(parentBlock);
1170        Block pb = parent.getBlock();
1171        try {
1172        int pos = bsearch(pb, prevLow, prevLow.length);
1173        if (pos < 0) {
1174            //#ifdef DEBUG
1175            System.out.print("b = ");
1176            display(b, System.out, false);
1177            System.out.print("pb = ");
1178            display(pb, System.out, false);
1179            Debug.println(0, "prevLow = " + keybytes(prevLow));
1180            //#endif
1181            throw new RuntimeException  (
1182            "deleteKeyAtPos: deleting " +
1183            " previous low key, not found!");
1184        }
1185        if (getCount(b) == 0) {
1186            if (deleteKeyAtPos(pb, pos, false)) {
1187                        //#ifdef DEBUG
1188            //Debug.println("Just deleted pb!");
1189                        //#endif
1190            }
1191            file.freePage(b.getPageNum());
1192            ret = true;
1193        } else {
1194                    byte[] k = keyAtPos(b, 0);
1195                    byte[] d = Util.bytes(b.getPageNum());
1196            setKey(pb, pos, k, k.length, d, 0, d.length, true);
1197            //#ifdef DEBUG
1198            if (paranoid) checkBlock(b);
1199            //#endif
1200        }
1201        } finally {
1202        pb.decrRefCount();
1203        }
1204    }
1205    return ret;
1206    }
1207
1208    /**
1209     * Helper function to move key indices around when adding or deleting
1210     * keys.
1211     */
1212    final static void moveKeys(Block b, int from, int to, int length) {
1213    if (length > 0) {
1214        byte[] buf = (byte[])b.getData();
1215        length *= REF_SIZE;
1216        int f = index(from);
1217        int t = index(to);
1218        if (f < t) {
1219        b.setDirty(true);
1220        for (int i = length-1; i >= 0; i--) {
1221            buf[t+i] = buf[f+i];
1222        }
1223        } else if (f > t) {
1224        b.setDirty(true);
1225        for (int i = 0; i < length; i++) {
1226            buf[t+i] = buf[f+i];
1227        }
1228        }
1229    }
1230    }
1231
1232    /**
1233     * Determine if there is room in the block for a new key/data pair.
1234     * @param b the block to operate on
1235     * @param index the index of the key that is being replaced,
1236     *      if <code>replace</code> is <b>true</b>.
1237     * @param klen the search key length
1238     * @param dlen the length of the data associated with the key
1239     * @param replace <b>true</b> if an existing key/data pair is to
1240     *      be replaced by the new key, <b>false</b> otherwise.
1241     *
1242     * @return negative number if there is no room for the new data.<p>
1243     *      zero if there is room for the new data.<p>
1244     *         positive number if there would be room after a garbage
1245     *      collection.  Included in this calculation is the deletion
1246     *      of the key being replaced, if <code>replace</code> is true.<p>
1247     */
1248    final int checkSpace(Block b, int index, int klen, int dlen, boolean replace) {
1249    int need = REF_SIZE + totalLength(klen) + totalLength(dlen);
1250    int total = capacity(b) + getGarbage(b);
1251    if (replace) total += REF_SIZE + existingKeyLength(b, index);
1252    int ret = 0;            // fits
1253    if (need > total) {
1254        ret = -1;           // doesn't fit
1255    } else if (need > capacity(b)) {
1256        ret = 1;            // will fit if gc
1257    }
1258    return ret;
1259    }
1260
1261    //#ifdef DEBUG
1262    final int debugcheckSpace(Block b, int index, int klen, int dlen,
1263               boolean replace) {
1264    int need = REF_SIZE + totalLength(klen) + totalLength(dlen);
1265    Debug.println(0, "keylen = " + totalLength(klen));
1266    Debug.println(0, "datalen = " + totalLength(dlen));
1267    Debug.println(0, "need = " + need);
1268    int total = capacity(b) + getGarbage(b);
1269    Debug.println(0, "capacity = " + capacity(b));
1270    Debug.println(0, "garbage = " + getGarbage(b));
1271    Debug.println(0, "total = " + total);
1272    if (replace) total += REF_SIZE + existingKeyLength(b, index);
1273    int ret = 0;            // fits
1274    if (need > total) {
1275        ret = -1;           // doesn't fit
1276    } else if (need > capacity(b)) {
1277        ret = 1;            // will fit if gc
1278    }
1279    return ret;
1280    }
1281    //#endif
1282
1283    /**
1284     * This function is scary.  It accounts for the fact that we're about
1285     * to delete a key, by including the size of the key/data in the
1286     * node's <code>garbage</code> field, but it doesn't actually delete
1287     * the key.  Be careful.
1288     */
1289    final void forgetKeyAtPos(Block b, int index) {
1290    setGarbage(b, getGarbage(b) + existingKeyLength(b, index));
1291    }
1292
1293    /**
1294     * Delete the specified key.
1295     *
1296     * @return true if the block is now empty, has been freed, and we
1297     *      should avoid touching it...
1298     */
1299    final boolean deleteKeyAtPos(Block b, int index, boolean skipNewLow)
1300    throws IOException  
1301    {
1302    boolean ret = false;
1303    int cnt = getCount(b);
1304    byte[] prevLow = index == 0 ? keyAtPos(b, 0) : null;
1305    forgetKeyAtPos(b, index);
1306    if (index < cnt-1) {
1307        moveKeys(b, index+1, index, cnt-index-1);
1308    }
1309    setCount(b, cnt-1);
1310    if (!skipNewLow && getCount(b) == 0 && getParent(b) == 0) {
1311        setLeaf(b, true);
1312    } else if (!skipNewLow && index == 0) {
1313        ret = newLow(b, prevLow);
1314    }
1315    return ret;
1316    }
1317
1318    /**
1319     * Given a block and a key position, insert a new key/data pair
1320     * immediately at the specified position, returning true if the
1321     * key/data fit in the block.  If the incoming data won't fit,
1322     * don't modify the block and return false.
1323     * @param b the block to be modified.
1324     * @param index the position in the key array
1325     * @param key the key
1326     * @param data the data
1327     * @return true if the insert was performed successfully, false
1328     *      if not because of, e.g., "wont fit".
1329     */
1330    final boolean setKeyAtPos(Block b, int index, byte[] key,
1331                              int klen, byte[] data, int doff,
1332                              int dlen, boolean replace)
1333        throws IOException  
1334    {
1335    int ret = checkSpace(b, index, klen, dlen, replace);
1336    if (ret < 0) return false;
1337    if (ret > 0) {
1338        // ---- will fit if we gc first.
1339        if (replace) {
1340        deleteKeyAtPos(b, index, true);
1341        replace = false;
1342        } 
1343        gc(b);
1344    }
1345    if (replace) forgetKeyAtPos(b, index);
1346
1347    // ---- paranoia
1348    //#ifdef DEBUG
1349    if (paranoid && checkSpace(b, index, klen, dlen, replace) != 0) {
1350        display(b, System.err, false);
1351        throw new RuntimeException  ("setKeyAtPos: no room, even after gc");
1352    }
1353    //#endif
1354
1355    // ---- insert the key/data pair at the bottom of the data area
1356    int pos = insertKeyData(b, key, klen, data, doff, dlen);
1357    if (!replace) {
1358        // ---- move the larger keys over one, then insert this one
1359        int cnt = getCount(b);      // how many existing keys?
1360            // ---- move 'cnt' keys to the right
1361            if (cnt > 0) {
1362                moveKeys(b, index, index+1, cnt-index);
1363            }
1364            setCount(b, cnt+1);         // increment the count
1365    }
1366    setKeyIndex(b, index, pos);     // insert this one
1367    return true;
1368    }
1369
1370    /**
1371     * Write a length code for the specified length, working backwards in
1372     * the data area, and returning the new bottom of the data area.
1373     */
1374    final static int writeLenLen(Block b, int bos, int len) {
1375    if (len <= 0x7f) {
1376        b.writeByte(--bos, (byte)len);
1377    } else {
1378        int lenlen = 0;
1379        while (len > 0) {
1380        b.writeByte(--bos, (byte)(len & 0xff));
1381        len >>= 8;
1382        lenlen++;
1383        }
1384        b.writeByte(--bos, (byte)(0x80 | lenlen));
1385    }
1386    return bos;
1387    }
1388
1389    /**
1390     * Return the number of available bytes in the buffer, not including
1391     * space that could be made available by performing a garbage collection.
1392     */
1393    final static int capacity(Block b) {
1394    return getBos(b) - (fIndices + (getCount(b) * REF_SIZE));
1395    }
1396
1397    final Block getBlock(long blockNum) throws IOException   {
1398    Block b = file.getBlock(blockNum);
1399    return b;
1400    }
1401    
1402    final Block getBlock() throws IOException   {
1403    return getBlock(this.blockRef);
1404    }
1405
1406    /**
1407     * Return the byte offset of the specified key/data pair.
1408     *
1409     * @param b the Bnode containing the key
1410     * @param index the index of the specified key/data pair.
1411     */
1412    final static int getKeyIndex(Block b, int index) {
1413        return b.readShort(index(index));
1414    }
1415    
1416    /**
1417     * Set the byte offset for the specified key/data pair.
1418     *
1419     * @param b the Bnode containing the key
1420     * @param index the index of the specified key/data pair.
1421     * @param val the byte offset of the specified key/data pair.
1422     */
1423    final static void setKeyIndex(Block b, int index, int val) {
1424    b.writeShort(index(index), (short)val);
1425    }
1426
1427    final static int index(int pos) { return pos * REF_SIZE + fIndices; }
1428
1429    /**
1430     * Return the value of the <b>count</b> field.
1431     */
1432    final static int getBos(Block b) { return b.readInt(fDataBOS); }
1433
1434    /**
1435     * Set the value of the <b>bos</b> field.
1436     */
1437    public final static void setBos(Block b, int bos) { b.writeInt(fDataBOS, bos); }
1438
1439    /**
1440     * Return the value of the <b>bos</b> field.
1441     */
1442    public final static int getCount(Block b) { return b.readInt(fCount); }
1443
1444    /**
1445     * Set the value of the <b>count</b> field.
1446     */
1447    public final static void setCount(Block b, int count) { b.writeInt(fCount, count); }
1448
1449    /**
1450     * Return the value of the <b>flags</b> field.
1451     */
1452    public final static int getFlags(Block b) { return b.readInt(fFlags); }
1453
1454    /**
1455     * Set the value of the <b>flags</b> field.
1456     */
1457    public final static void setFlags(Block b, int flags) { b.writeInt(fFlags, flags); }
1458
1459    /**
1460     * Return the boolean value of a specified flag.
1461     */
1462    public final static boolean getFlag(Block b, int mask) { return (getFlags(b) & mask) != 0; }
1463
1464    /**
1465     * Set a specified boolean flag.
1466     */
1467    public final static void setFlag(Block b, int mask, boolean val) {
1468    setFlags(b, val ? getFlags(b) | mask : getFlags(b) & ~mask);
1469    }
1470
1471    /**
1472     * Return the value of the <b>IS_LEAF</b> flag.
1473     */
1474    public final static boolean isLeaf(Block b) { return getFlag(b, IS_LEAF); }
1475
1476    /**
1477     * Set the value of the <b>IS_LEAF</b> flag.
1478     */
1479    public final static void setLeaf(Block b, boolean v) { setFlag(b, IS_LEAF, v); }
1480    
1481
1482    /**
1483     * Return the value of the <b>garbage</b> field.
1484     */
1485    public final static int getGarbage(Block b) { return b.readInt(fGarbage); }
1486
1487    /**
1488     * Set the value of the <b>garbage</b> field.
1489     */
1490    public final static void setGarbage(Block b, int g) {
1491    b.writeInt(fGarbage, g);
1492    }
1493
1494    /**
1495     * Return the value of the <b>parent</b> field.
1496     */
1497    public final static long getParent(Block b) { return b.readLong(fParent); }
1498
1499    /**
1500     * Set the value of the <b>parent</b> field.
1501     */
1502    public final static void setParent(Block b, long g) {
1503    b.writeLong(fParent, g);
1504    }
1505
1506    //#ifdef DEBUG
1507    /**
1508     * For debugging purposes, write a human readable version of this
1509     * <code>Bnode</code> to the specified stream.
1510     */
1511    final void display(PrintStream   os, boolean recursive) throws IOException   {
1512    display(os, os, recursive);
1513    }
1514
1515    final void display(PrintStream   os, PrintStream   er, boolean recursive)
1516    throws IOException  
1517    {
1518    Block b = getBlock();
1519    try {
1520        display(b, os, er, recursive);
1521    } finally {
1522        b.decrRefCount();
1523    }
1524    }
1525
1526    final void display(Block b, PrintStream   os, boolean recursive)
1527    throws IOException  
1528    {
1529    display(b, os, os, recursive);
1530    }
1531
1532    /**
1533     * Since this is used for displaying the key, we attempt to return the
1534     * string itself, as long as it is composed only of printable characters.
1535     * If it contains any "non-printable" characters, it is instead formatted
1536     * in hex/ascii dump form.
1537     *
1538     * @param b the bytes form of the key
1539     * @return a displayable representation of the key.
1540     */
1541    final static String   keybytes(byte[] key) {
1542    boolean printable = true;
1543    for (int i = 0; printable && i < key.length; i++) {
1544        if (key[i] < 0x20 || key[i] >= 0x7f) printable = false;
1545    }
1546    if (printable) {
1547        return new String  (key);
1548    } else {
1549        return Util.hexBytes(key) + " " +
1550                com.quadcap.sql.Key.toStringHelper(key, 0, key.length);
1551
1552    }
1553    }
1554
1555    final static String   keybytes(byte[] key, int off, int len) {
1556        return Util.hexBytes(key, off, len) + " " +
1557            com.quadcap.sql.Key.toStringHelper(key, off, len);
1558    }
1559
1560    /**
1561     * Represent strings as having a length other than 4, while representing
1562     * integers as only of length 4 bytes.
1563     *
1564     * @param b the string of bytes to convert
1565     * @return A string containing either a 4-byte integer conversion or a
1566     *          string 'keybytes' filter.
1567     */
1568    public final static String   databytes(byte[] b) {
1569        String   s = Util.hexBytes(b);
1570        if (b.length == 8) {
1571            s += " (" + SubPageManager.toString(ByteUtil.getLong(b, 0)) + ")";
1572        }
1573        return s;
1574    }
1575
1576    final void display(Block b, PrintStream   os, PrintStream   er, boolean recursive)
1577    throws IOException  
1578    {
1579    boolean leaf = isLeaf(b);
1580    int saveLevel = Debug.printLevel;
1581        Debug.printLevel = 0;
1582    int count = getCount(b);
1583    os.println("Block " + b.getPageNum() +
1584           "{" + b.getRefCount() + "}" +
1585           ", parent = " + getParent(b) +
1586           ", capacity = " + capacity(b) +
1587           ", count = " + count +
1588           ", bos = " + getBos(b) +
1589           ", garbage = " + getGarbage(b));
1590    
1591    long[] children = new long[count];
1592    for (int i = 0; i < count; i++) {
1593        int index = getKeyIndex(b, i);
1594        byte[] key = keyAtPos(b, i);
1595        byte[] data = dataAtPos(b, i);
1596            if (leaf) {
1597                os.println("[" + i + " @ " + index + "]: " +
1598                           tree.compare.toString(key, 0, key.length) + " = " +
1599                           Bnode.databytes(data));
1600            } else {
1601        children[i] = ByteUtil.getLong(data, 0);
1602                os.println("[" + i + " @ " + index + "]: " +
1603                           tree.compare.toString(key, 0, key.length) + 
1604                           SubPageManager.toString(children[i]));
1605            }
1606    }
1607    if (!leaf && recursive) {
1608        for (int i = 0; i < children.length; i++) {
1609        Block c = getBlock(children[i]);
1610        try {
1611            long p = getParent(c);
1612            if (0 != tree.compare.compare(keyAtPos(b, i),
1613                          keyAtPos(c, 0))) {
1614            Debug.println(0, "ERROR: parent {" + b.getPageNum() +
1615                   "} doesn't point to smallest key in " +
1616                   " child {" + c.getPageNum() + "}");
1617            }
1618            if (p != b.getPageNum()) {
1619            Debug.println(0, "ERROR: BROKEN PARENT LINK: Block " +
1620                   children[i] +
1621                   " has parent link of " + p +
1622                   ", but is child of " + b.getPageNum());
1623            }
1624            display(c, os, er, recursive);
1625        } finally {
1626            c.decrRefCount();
1627        }
1628        }
1629    }
1630        Debug.printLevel = saveLevel;
1631    }
1632    //#endif
1633}
1634
1635
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags