BlockPath


1   package com.quadcap.sql.file;
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  
43  import com.quadcap.util.Debug;
44  
45  /**
46   * This class is used to locate a specified offset within a randomly
47   * accessible <code>BlockAccess</code> object.  The path has two
48   * components, a logical component, <b>p</b> which specifies the offsets of the
49   * block references needed to locate the block and position corresponding
50   * to the selected byte, and a physical component <b>r</b> which contains
51   * the block references of the blocks needed to locate the actual byte.
52   *
53   * @author Stan Bailes
54   */
55  
56  class BlockPath {
57      /** The actual bytes */
58      BlockAccess     a;
59      /** Depth of this path */
60      int                 depth;
61      /** Byte offset info 'a' */
62      long        pos;
63      /** Logical path */
64      int[]       p;
65      /** Block refs */
66      long[]      r;
67      /** A temporary (logical) path */
68      int[]               tp;
69  
70      /**
71       * Construct a new BlockPath to represent the specified byte in the
72       * specified region.
73       *
74       * @param a the region into which the index is made
75       * @param pos the byte offset in the region
76       */
77      public BlockPath(BlockAccess a, long pos) throws IOException   {
78      this.a = a;
79      this.pos = pos;
80  
81          depth = a.depth;
82          
83      p = new int[depth + 1];
84      r = new long[depth + 1];
85      tp = new int[depth + 1];
86  
87      getPath(pos, p);
88      getRefs();
89      }
90  
91      /**
92       * Return the block which actually contains the data.  This is the
93       * final block in the path.
94       * <p>
95       * <B>NOTE</b>: This block needs to have its reference count decremented
96       * when you're done with it!!
97       */
98      public final Page getLeafBlock() throws IOException   {
99      return a.file.getPage(r[r.length-1]);
100     }
101 
102     /**
103      * Return the byte offset within the leaf block where the designated
104      * byte can be found.
105      */
106     public final int getBufPos() {
107     return p[p.length-1];
108     }
109 
110     /**
111      * Return the depth of this path
112      */
113     public final int getDepth() { return depth; }
114 
115     /**
116      * Return the current position referred to by this path
117      */
118     public final long getPos() { return pos; }
119 
120 
121     /**
122      * Return the current position referred to by this path
123      */
124     public final void setPos(long newpos) throws IOException   {
125         if (newpos != pos) {
126             getPath(newpos, tp);
127             updatePath(tp);
128             pos = newpos;
129         }
130     }
131 
132     /**
133      * Adjust this BlockPath to point to a new location, with a minimum
134      * number of block accesses.
135      *
136      * @param cnt  The offset from the current location
137      */
138     public final void incr(long offset) throws IOException   {
139     setPos(pos + offset);
140     }
141 
142     /**
143      * Build the (logical) path vector for a specified byte in the region.
144      */
145     private final void getPath(long pos, int[] path) {
146         //Debug.println("getPath(" + pos + ")");
147     int len = a.radices.length;
148         for (int i = 0; i < len; i++) {
149             path[i] = (int)(pos / a.radices[i]);
150             pos %= a.radices[i];
151             //Debug.println("   " + i + ": " + path[i] + " (" + a.radices[i] +
152             //              ", pos = " + pos + ")");
153         }
154         path[len] = (int)pos;
155         //Debug.println(" * " + len + ": " + path[len]);
156     }
157 
158     /**
159      * Find the actual block refs, given the logical path vector.
160      */
161     private final void getRefs() throws IOException   {
162     r[0] = a.rootBlock;
163     for (int i = 1; i < r.length; i++) {
164             try {
165                 Page b = a.file.getPage(r[i-1]);
166                 try {
167                     r[i] = a.makeBlockRef(b, p[i-1], i==1);
168                 } finally {
169                     b.decrRefCount();
170                 }
171             } catch (IOException   ex) {
172                 Debug.println("getRefs, i = " + i +
173                               ", r[" + i + "]=" +
174                               SubPageManager.toString(r[i-1]));
175                 Debug.println("this = " + this);
176                 throw ex;
177             } catch (RuntimeException   ex) {
178                 Debug.println("getRefs, i = " + i +
179                               ", r[" + i + "]=" +
180                               SubPageManager.toString(r[i-1]));
181                 Debug.println("this = " + this);
182                 throw ex;
183             }
184     }
185     }
186 
187     /**
188      * Update the block refs, given a new logical path, attempting
189      * to minimize the number of block accesses.
190      */
191     private final void updatePath(int[] path) throws IOException   {
192         if (true) {
193             this.p = path;
194             getRefs();
195         } else {
196             boolean update = false;
197             for (int i = 1; i < r.length; i++) {
198                 update |= (p[i-1] != path[i-1]);
199                 p[i-1] = path[i-1];
200                 if (update) {
201                     Page b = a.file.getPage(r[i-1]);
202                     try {
203                         r[i] = a.makeBlockRef(b, path[i-1], i==1);
204                     } finally {
205                         b.decrRefCount();
206                     }
207                 }
208             }
209             p[r.length-1] = path[r.length-1];
210         }
211     }
212 
213     //#ifdef DEBUG
214     /**
215      * For debugging, return a displayable representation of this BlockPath.
216      */
217     public String   toString() {
218     StringBuffer   sb = new StringBuffer  ();
219     sb.append("Path[" + pos + "] p(");
220     for (int i = 0; i < p.length; i++) {
221         if (i > 0) sb.append(", ");
222         sb.append("" + p[i]);
223     }
224     sb.append(") r(");
225     for (int i = 0; i < r.length; i++) {
226         if (i > 0) sb.append(", ");
227         sb.append("" + SubPageManager.toString(r[i]));
228     }
229     sb.append(")");
230     return sb.toString();
231     }
232     //#endif
233 
234 }
235
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags