BlockAccess


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.ConfigNumber;
44  import com.quadcap.util.Debug;
45  import com.quadcap.util.Util;
46  
47  /**
48   * This class implements a randomly accessible, growable region within
49   * a <b>BlockFile</b> object.  The region is defined by a root block,
50   * which either contains the entire data for the region (if it will fit),
51   * or contains a set of references to secondary blocks which contain the
52   * actual data.  If the region is large enough, those secondary blocks
53   * themselves may be references, and so on.
54   *
55   * @author Stan Bailes
56   */
57  
58  public class BlockAccess extends RandomAccess {
59      static final int HEADER_SIZE    = 8;    // size of 'header' in bytes
60      static final int REF_SIZE       = 8;    // size of a ref, in bytes
61  
62      /**
63       * The underlying store.
64       */
65      PageManager     file;
66      
67      /**
68       * The 'root' block of this data area.
69       * The format of this block is as follows:
70       * <p>Bytes 0-3: The size of this data area, in bytes.
71       */
72      long                rootBlock;
73      long                size;
74  
75      /**
76       * A vector of <b>depth</b> elements, indicating the size of
77       * the recursive sub-block at each level.
78       */
79      int[]               radices         = null;
80  
81      byte[]              b1              = new byte[1];
82  
83      /**
84       * Depth of this data area.  A depth of zero indicates
85       * that the actual data area is entirely contained within the
86       * root block.  A depth of one indicates that the data is contained
87       * in sub-blocks, and the root block contains the block numbers of
88       * the sub-blocks.  Larger depths indicate that the sub-blocks
89       * contain pointers to other sub-blocks, etc.
90       */
91      int                 depth           = 0;
92  
93      /**
94       * Path from root to leaf blocks
95       */
96      BlockPath           path            = null;
97  
98      /**
99       * The file lock
100      */
101     Object                fileLock        = null;
102 
103     /**
104      * Default public constructor
105      */
106     public BlockAccess() {}
107     
108     /**
109      * Construct a new <tt>BlockAccess</tt> attached to the specified
110      * block.
111      */
112     public BlockAccess(PageManager file, long rootBlock) throws IOException   {
113         init(file, rootBlock);
114     }
115 
116     public void init(PageManager file, long rootBlock) throws IOException   {
117     this.file = file;
118         this.fileLock = file.getLock();
119         this.rootBlock = rootBlock;
120         this.path = null;
121 
122         synchronized (fileLock) {
123             Page root = file.getPage(rootBlock);
124             try {
125                 this.size = root.readLong(0);
126                 //#ifdef DEBUG
127                 if (Trace.bit(3)) {
128                     Debug.println("INIT: " + this);
129                 }
130                 //#endif
131             } finally {
132                 root.decrRefCount();
133             }
134         }
135     this.depth = depthForSize(this.size);
136     this.radices = radicesForDepth(this.depth);
137     }
138 
139     /**
140      * Return the size of this region
141      */
142     public long size() {
143         return this.size;
144     }
145 
146     /**
147      * Resize the region.
148      */
149     public void resize(long newSize) throws IOException   {
150     //#ifdef DEBUG
151     if (Trace.bit(2)) {
152         Debug.println("BlockAccess[" + toString(rootBlock) + ":" + size + 
153               "] resize(" + newSize + ")");
154     }
155     //#endif
156         synchronized (fileLock) {
157             Page root = file.getPage(rootBlock);
158             try {
159                 long curSize = root.readLong(0);
160                 byte[] bufx = new byte[bufLen()];
161                 int rsize = bufx.length - HEADER_SIZE;
162                 this.size = newSize;
163     
164                 int newDepth = depthForSize(newSize);
165                 while (newDepth > depth) {      
166                     // ---- growing
167                     long newPage = file.newPage();
168                     Page b = file.getPage(newPage);
169                     try {
170                         root.read(HEADER_SIZE, bufx, 0, rsize);
171                         root.clear();
172                         b.write(0, bufx, 0, rsize);
173                         setBlockRef(root, 0, newPage, true);
174                         radices = radicesForDepth(++depth);
175                     } finally {
176                         b.decrRefCount();
177                     }
178                 }
179     
180                 while (newDepth < depth) {
181                     // ---- shrinking
182                     for (int i = 1; i < refsForLevel(0); i++) {
183                         long blk = getBlockRef(root, i, true);
184                         if (blk != 0) {
185                             file.freePage(blk);
186                             setBlockRef(root, i, 0, true);
187                         }
188                     }
189                     long freePage = getBlockRef(root, 0, true);
190                     Page b = file.getPage(freePage);
191                     try {
192                         b.read(0, bufx, 0, rsize);
193                         root.write(HEADER_SIZE, bufx, 0, rsize);
194                         radices = radicesForDepth(--depth);
195                     } finally {
196                         b.decrRefCount();
197                     }
198                     file.freePage(freePage);
199                 }
200                 root.writeLong(0, newSize);
201             } finally {
202                 root.decrRefCount();
203             }
204         }
205     }
206 
207     /**
208      * Write into the data region.
209      *
210      * @param pos the starting position to write
211      * @param buf the buffer containing the data to write
212      * @param offset the position of the first byte in the buffer
213      * @param len the number of bytes to write
214      */
215     public void write(long pos, byte[] buf, int offset, int len)
216     throws IOException  
217     {
218         synchronized (fileLock) {
219             //#ifdef DEBUG
220             if (Trace.bit(2)) {
221                 Debug.println("[" + toString(rootBlock) + ":" + size + 
222                               "] write(" + 
223                               pos + ", " + Util.strBytes(buf, offset, len) + ")");
224             }
225             //#endif
226             Page root = file.getPage(rootBlock);
227             try {
228                 BlockPath p = getPath(pos);
229                 int hdr = (depth >= 1) ? 0 : HEADER_SIZE;
230                 while (len > 0) {
231                     int bufloc = p.getBufPos();
232                     int amt = Math.min(len, (bufLen() - hdr) - bufloc);
233                     Page b = p.getLeafBlock();
234                     try {
235                         b.write(bufloc + hdr, buf, offset, amt);
236                     } finally {
237                         b.decrRefCount();
238                     }
239                     len -= amt;
240                     offset += amt;
241                     //pos += amt;   // pos used only for debug
242                     //Debug.println("Before incr: " + this);
243                     if (len > 0) p.incr(amt);
244                 }
245             } finally {
246                 root.decrRefCount();
247             }
248         }
249     }
250 
251     /**
252      * Read from the data region.
253      */
254     public void read(long pos, byte[] buf, int offset, int len)
255     throws IOException  
256     {
257         //#ifdef DEBUG
258         if (pos + len > size) {
259             throw new IOException  ("BlockAccess.read() out of bounds: " +
260                                   "pos = " + pos +
261                                   ", len = " + len +
262                                   ", size = " + size());
263         }
264         long save_pos = pos;
265         int save_offset = offset;
266         int save_len = len;
267         //#endif
268 
269         synchronized (fileLock) {
270             Page root = file.getPage(rootBlock);
271             try {
272                 BlockPath p = getPath(pos);
273                 int hdr = (depth >= 1) ? 0 : HEADER_SIZE;
274                 while (len > 0) {
275                     int bufloc = p.getBufPos();
276                     int amt = Math.min(len, (bufLen() - hdr) - bufloc);
277                     //#ifdef DEBUG
278                     if (amt <= 0) {
279                         Debug.println("pos = " + pos + ", offset = " + offset +
280                                       ", len = " + len + ", bufloc = " + bufloc +
281                                       ", bufLen() = " + bufLen());
282                         Debug.println("save_pos = " + save_pos +
283                                       ", save_offset = " + save_offset +
284                                       ", save_len = " + save_len);
285                         Debug.println("p = " + p);
286                         Debug.println("size = " + size);
287                         Debug.println("depth = " + depth);
288                         for (int i = 0; i < radices.length; i++) {
289                             Debug.println("radix[" + i + "] = " + radices[i]);
290                         }
291                         throw new RuntimeException  ("Internal error: amt: " + amt);
292                     }
293                     //#endif
294                     Page b = p.getLeafBlock();
295                     try {
296                         b.read(bufloc + hdr, buf, offset, amt);
297                     } finally {
298                         b.decrRefCount();
299                     }
300                     len -= amt;
301                     offset += amt;
302                     //pos += amt;
303                     if (len > 0) p.incr(amt);
304                 }
305             } finally {
306                 root.decrRefCount();
307             }
308         }
309     }
310 
311     /**
312      * Finalization: We're done with this region.
313      */
314     public void close() {
315     }
316 
317     public void flush() {
318     }
319 
320     private final BlockPath getPath(long pos) throws IOException   {
321         if (path == null || depth != path.getDepth()) {
322             path = new BlockPath(this, pos);
323         } else {
324             path.setPos(pos);
325         }
326         return path;
327     }
328 
329     /**
330      * Build the radices array for a region of the specified depth.
331      */
332     final int[] radicesForDepth(int depth) {
333         int[] v = new int[depth];
334         int r = bufLen();
335         for (int i = depth-1; i >= 0; i--) {
336             v[i] = r;
337             r *= refsForLevel(i);
338         }
339     return v;
340     }
341 
342     /**
343      * Return the specified block reference.  This method treats the data
344      * portion of the block as an array of integer blockrefs.
345      *
346      * @param b the block containing the array of blockrefs
347      * @param pos the location in the blockref array of the block number
348      *  to fetch.
349      */
350     final long getBlockRef(Page b, int pos, boolean isRoot)
351         throws IOException  
352     {
353     int offset = pos * REF_SIZE + (isRoot ? HEADER_SIZE : 0);
354     long ref = b.readLong(offset);
355     return ref;
356     }
357 
358     /**
359      * Return the specified block reference.  This method treats the data
360      * portion of the block as an array of long blockrefs.  If the
361      * selected blockref is zero, this routine will allocate a new
362      * block and return the blockref of the newly created block, as well
363      * as update <tt>b</tt>'s blockref array with the new blockref.
364      *
365      * @param b the block containing the array of blockrefs
366      * @param pos the location in the blockref array of the block number
367      *  to fetch.
368      */
369     final long makeBlockRef(Page b, int pos, boolean isRoot)
370         throws IOException  
371     {
372     int offset = pos * REF_SIZE + (isRoot ? HEADER_SIZE : 0);
373         long ref = b.readLong(offset);
374     if (ref == 0) {
375         ref = file.newPage();
376         b.writeLong(offset, ref);
377     }
378     return ref;
379     }
380 
381     /**
382      * Set the specified block reference.
383      *
384      * @param b the block containing the array of blockrefs
385      * @param pos the (zero-offset) index of the blockref within the array
386      * @param val the value to store in the array
387      */
388     final void setBlockRef(Page b, int pos, long val, boolean isRoot) {
389     int offset = pos * REF_SIZE + (isRoot ? HEADER_SIZE : 0);
390     b.writeLong(offset, val);
391     }
392     
393     /**
394      * Return the number of blockrefs that will fit in a block.
395      */
396     final int refsForLevel(int level) {
397         return (bufLen() - (level == 0 ? HEADER_SIZE : 0)) / REF_SIZE;
398     }
399 
400     /**
401      * Return the size of the data portion of the block.
402      */
403     final int bufLen() {
404         return file.getPageSize();
405     }
406 
407     /**
408      * Return the maximum size for a region of the specified depth.
409      */
410     private final long maxSizeForDepth(int level) {
411         if (level == 0) {
412             return bufLen() - HEADER_SIZE;
413         }
414         long ret = bufLen();
415         for (int i = 0; i < level; i++) {
416             ret *= refsForLevel(i);
417         }
418         return ret;
419     }
420 
421     /**
422      * Return the depth necessary to represent a region of the specified size
423      *
424      * @param size the size of the region
425      */
426     private final int depthForSize(long size) {
427         if (size <= bufLen() - HEADER_SIZE) return 0;
428 
429         int ret = 1;
430     long max = bufLen() * refsForLevel(0);
431 
432     while (size > max) {
433             max *= refsForLevel(++ret);
434     }
435     return ret;
436     }
437 
438     //#ifdef DEBUG
439     final String   toString(long page) {
440     return SubPageManager.toString(page);
441     }
442 
443     public String   toString() {
444         StringBuffer   sb = new StringBuffer  ("BlockAccess(");
445         sb.append("root=");
446         sb.append(SubPageManager.toString(rootBlock));
447         sb.append("  size=");
448         sb.append(size);
449         if (radices != null) {
450             sb.append("  radices=");
451             for (int i = 0; i < radices.length; i++) {
452                 if (i>0) sb.append(',');
453                 sb.append(radices[i]);
454             }
455         }
456         sb.append("  depth=");
457         sb.append(depth);
458         sb.append("  path=");
459         sb.append(path);
460         sb.append(")");
461         return sb.toString();
462     }
463     //#endif
464 }
465
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags