001: package com.quadcap.sql.file;
002:
003: /* Copyright 1997 - 2003 Quadcap Software. All rights reserved.
004: *
005: * This software is distributed under the Quadcap Free Software License.
006: * This software may be used or modified for any purpose, personal or
007: * commercial. Open Source redistributions are permitted. Commercial
008: * redistribution of larger works derived from, or works which bundle
009: * this software requires a "Commercial Redistribution License"; see
010: * http://www.quadcap.com/purchase.
011: *
012: * Redistributions qualify as "Open Source" under one of the following terms:
013: *
014: * Redistributions are made at no charge beyond the reasonable cost of
015: * materials and delivery.
016: *
017: * Redistributions are accompanied by a copy of the Source Code or by an
018: * irrevocable offer to provide a copy of the Source Code for up to three
019: * years at the cost of materials and delivery. Such redistributions
020: * must allow further use, modification, and redistribution of the Source
021: * Code under substantially the same terms as this license.
022: *
023: * Redistributions of source code must retain the copyright notices as they
024: * appear in each source code file, these license terms, and the
025: * disclaimer/limitation of liability set forth as paragraph 6 below.
026: *
027: * Redistributions in binary form must reproduce this Copyright Notice,
028: * these license terms, and the disclaimer/limitation of liability set
029: * forth as paragraph 6 below, in the documentation and/or other materials
030: * provided with the distribution.
031: *
032: * The Software is provided on an "AS IS" basis. No warranty is
033: * provided that the Software is free of defects, or fit for a
034: * particular purpose.
035: *
036: * Limitation of Liability. Quadcap Software shall not be liable
037: * for any damages suffered by the Licensee or any third party resulting
038: * from use of the Software.
039: */
040:
041: import java.io.IOException;
042:
043: import com.quadcap.util.ConfigNumber;
044: import com.quadcap.util.Debug;
045: import com.quadcap.util.Util;
046:
047: /**
048: * This class implements a randomly accessible, growable region within
049: * a <b>BlockFile</b> object. The region is defined by a root block,
050: * which either contains the entire data for the region (if it will fit),
051: * or contains a set of references to secondary blocks which contain the
052: * actual data. If the region is large enough, those secondary blocks
053: * themselves may be references, and so on.
054: *
055: * @author Stan Bailes
056: */
057:
058: public class BlockAccess extends RandomAccess {
059: static final int HEADER_SIZE = 8; // size of 'header' in bytes
060: static final int REF_SIZE = 8; // size of a ref, in bytes
061:
062: /**
063: * The underlying store.
064: */
065: PageManager file;
066:
067: /**
068: * The 'root' block of this data area.
069: * The format of this block is as follows:
070: * <p>Bytes 0-3: The size of this data area, in bytes.
071: */
072: long rootBlock;
073: long size;
074:
075: /**
076: * A vector of <b>depth</b> elements, indicating the size of
077: * the recursive sub-block at each level.
078: */
079: int[] radices = null;
080:
081: byte[] b1 = new byte[1];
082:
083: /**
084: * Depth of this data area. A depth of zero indicates
085: * that the actual data area is entirely contained within the
086: * root block. A depth of one indicates that the data is contained
087: * in sub-blocks, and the root block contains the block numbers of
088: * the sub-blocks. Larger depths indicate that the sub-blocks
089: * contain pointers to other sub-blocks, etc.
090: */
091: int depth = 0;
092:
093: /**
094: * Path from root to leaf blocks
095: */
096: BlockPath path = null;
097:
098: /**
099: * The file lock
100: */
101: Object fileLock = null;
102:
103: /**
104: * Default public constructor
105: */
106: public BlockAccess() {
107: }
108:
109: /**
110: * Construct a new <tt>BlockAccess</tt> attached to the specified
111: * block.
112: */
113: public BlockAccess(PageManager file, long rootBlock)
114: throws IOException {
115: init(file, rootBlock);
116: }
117:
118: public void init(PageManager file, long rootBlock)
119: throws IOException {
120: this .file = file;
121: this .fileLock = file.getLock();
122: this .rootBlock = rootBlock;
123: this .path = null;
124:
125: synchronized (fileLock) {
126: Page root = file.getPage(rootBlock);
127: try {
128: this .size = root.readLong(0);
129: //#ifdef DEBUG
130: if (Trace.bit(3)) {
131: Debug.println("INIT: " + this );
132: }
133: //#endif
134: } finally {
135: root.decrRefCount();
136: }
137: }
138: this .depth = depthForSize(this .size);
139: this .radices = radicesForDepth(this .depth);
140: }
141:
142: /**
143: * Return the size of this region
144: */
145: public long size() {
146: return this .size;
147: }
148:
149: /**
150: * Resize the region.
151: */
152: public void resize(long newSize) throws IOException {
153: //#ifdef DEBUG
154: if (Trace.bit(2)) {
155: Debug.println("BlockAccess[" + toString(rootBlock) + ":"
156: + size + "] resize(" + newSize + ")");
157: }
158: //#endif
159: synchronized (fileLock) {
160: Page root = file.getPage(rootBlock);
161: try {
162: long curSize = root.readLong(0);
163: byte[] bufx = new byte[bufLen()];
164: int rsize = bufx.length - HEADER_SIZE;
165: this .size = newSize;
166:
167: int newDepth = depthForSize(newSize);
168: while (newDepth > depth) {
169: // ---- growing
170: long newPage = file.newPage();
171: Page b = file.getPage(newPage);
172: try {
173: root.read(HEADER_SIZE, bufx, 0, rsize);
174: root.clear();
175: b.write(0, bufx, 0, rsize);
176: setBlockRef(root, 0, newPage, true);
177: radices = radicesForDepth(++depth);
178: } finally {
179: b.decrRefCount();
180: }
181: }
182:
183: while (newDepth < depth) {
184: // ---- shrinking
185: for (int i = 1; i < refsForLevel(0); i++) {
186: long blk = getBlockRef(root, i, true);
187: if (blk != 0) {
188: file.freePage(blk);
189: setBlockRef(root, i, 0, true);
190: }
191: }
192: long freePage = getBlockRef(root, 0, true);
193: Page b = file.getPage(freePage);
194: try {
195: b.read(0, bufx, 0, rsize);
196: root.write(HEADER_SIZE, bufx, 0, rsize);
197: radices = radicesForDepth(--depth);
198: } finally {
199: b.decrRefCount();
200: }
201: file.freePage(freePage);
202: }
203: root.writeLong(0, newSize);
204: } finally {
205: root.decrRefCount();
206: }
207: }
208: }
209:
210: /**
211: * Write into the data region.
212: *
213: * @param pos the starting position to write
214: * @param buf the buffer containing the data to write
215: * @param offset the position of the first byte in the buffer
216: * @param len the number of bytes to write
217: */
218: public void write(long pos, byte[] buf, int offset, int len)
219: throws IOException {
220: synchronized (fileLock) {
221: //#ifdef DEBUG
222: if (Trace.bit(2)) {
223: Debug.println("[" + toString(rootBlock) + ":" + size
224: + "] write(" + pos + ", "
225: + Util.strBytes(buf, offset, len) + ")");
226: }
227: //#endif
228: Page root = file.getPage(rootBlock);
229: try {
230: BlockPath p = getPath(pos);
231: int hdr = (depth >= 1) ? 0 : HEADER_SIZE;
232: while (len > 0) {
233: int bufloc = p.getBufPos();
234: int amt = Math.min(len, (bufLen() - hdr) - bufloc);
235: Page b = p.getLeafBlock();
236: try {
237: b.write(bufloc + hdr, buf, offset, amt);
238: } finally {
239: b.decrRefCount();
240: }
241: len -= amt;
242: offset += amt;
243: //pos += amt; // pos used only for debug
244: //Debug.println("Before incr: " + this);
245: if (len > 0)
246: p.incr(amt);
247: }
248: } finally {
249: root.decrRefCount();
250: }
251: }
252: }
253:
254: /**
255: * Read from the data region.
256: */
257: public void read(long pos, byte[] buf, int offset, int len)
258: throws IOException {
259: //#ifdef DEBUG
260: if (pos + len > size) {
261: throw new IOException("BlockAccess.read() out of bounds: "
262: + "pos = " + pos + ", len = " + len + ", size = "
263: + size());
264: }
265: long save_pos = pos;
266: int save_offset = offset;
267: int save_len = len;
268: //#endif
269:
270: synchronized (fileLock) {
271: Page root = file.getPage(rootBlock);
272: try {
273: BlockPath p = getPath(pos);
274: int hdr = (depth >= 1) ? 0 : HEADER_SIZE;
275: while (len > 0) {
276: int bufloc = p.getBufPos();
277: int amt = Math.min(len, (bufLen() - hdr) - bufloc);
278: //#ifdef DEBUG
279: if (amt <= 0) {
280: Debug.println("pos = " + pos + ", offset = "
281: + offset + ", len = " + len
282: + ", bufloc = " + bufloc
283: + ", bufLen() = " + bufLen());
284: Debug.println("save_pos = " + save_pos
285: + ", save_offset = " + save_offset
286: + ", save_len = " + save_len);
287: Debug.println("p = " + p);
288: Debug.println("size = " + size);
289: Debug.println("depth = " + depth);
290: for (int i = 0; i < radices.length; i++) {
291: Debug.println("radix[" + i + "] = "
292: + radices[i]);
293: }
294: throw new RuntimeException(
295: "Internal error: amt: " + amt);
296: }
297: //#endif
298: Page b = p.getLeafBlock();
299: try {
300: b.read(bufloc + hdr, buf, offset, amt);
301: } finally {
302: b.decrRefCount();
303: }
304: len -= amt;
305: offset += amt;
306: //pos += amt;
307: if (len > 0)
308: p.incr(amt);
309: }
310: } finally {
311: root.decrRefCount();
312: }
313: }
314: }
315:
316: /**
317: * Finalization: We're done with this region.
318: */
319: public void close() {
320: }
321:
322: public void flush() {
323: }
324:
325: private final BlockPath getPath(long pos) throws IOException {
326: if (path == null || depth != path.getDepth()) {
327: path = new BlockPath(this , pos);
328: } else {
329: path.setPos(pos);
330: }
331: return path;
332: }
333:
334: /**
335: * Build the radices array for a region of the specified depth.
336: */
337: final int[] radicesForDepth(int depth) {
338: int[] v = new int[depth];
339: int r = bufLen();
340: for (int i = depth - 1; i >= 0; i--) {
341: v[i] = r;
342: r *= refsForLevel(i);
343: }
344: return v;
345: }
346:
347: /**
348: * Return the specified block reference. This method treats the data
349: * portion of the block as an array of integer blockrefs.
350: *
351: * @param b the block containing the array of blockrefs
352: * @param pos the location in the blockref array of the block number
353: * to fetch.
354: */
355: final long getBlockRef(Page b, int pos, boolean isRoot)
356: throws IOException {
357: int offset = pos * REF_SIZE + (isRoot ? HEADER_SIZE : 0);
358: long ref = b.readLong(offset);
359: return ref;
360: }
361:
362: /**
363: * Return the specified block reference. This method treats the data
364: * portion of the block as an array of long blockrefs. If the
365: * selected blockref is zero, this routine will allocate a new
366: * block and return the blockref of the newly created block, as well
367: * as update <tt>b</tt>'s blockref array with the new blockref.
368: *
369: * @param b the block containing the array of blockrefs
370: * @param pos the location in the blockref array of the block number
371: * to fetch.
372: */
373: final long makeBlockRef(Page b, int pos, boolean isRoot)
374: throws IOException {
375: int offset = pos * REF_SIZE + (isRoot ? HEADER_SIZE : 0);
376: long ref = b.readLong(offset);
377: if (ref == 0) {
378: ref = file.newPage();
379: b.writeLong(offset, ref);
380: }
381: return ref;
382: }
383:
384: /**
385: * Set the specified block reference.
386: *
387: * @param b the block containing the array of blockrefs
388: * @param pos the (zero-offset) index of the blockref within the array
389: * @param val the value to store in the array
390: */
391: final void setBlockRef(Page b, int pos, long val, boolean isRoot) {
392: int offset = pos * REF_SIZE + (isRoot ? HEADER_SIZE : 0);
393: b.writeLong(offset, val);
394: }
395:
396: /**
397: * Return the number of blockrefs that will fit in a block.
398: */
399: final int refsForLevel(int level) {
400: return (bufLen() - (level == 0 ? HEADER_SIZE : 0)) / REF_SIZE;
401: }
402:
403: /**
404: * Return the size of the data portion of the block.
405: */
406: final int bufLen() {
407: return file.getPageSize();
408: }
409:
410: /**
411: * Return the maximum size for a region of the specified depth.
412: */
413: private final long maxSizeForDepth(int level) {
414: if (level == 0) {
415: return bufLen() - HEADER_SIZE;
416: }
417: long ret = bufLen();
418: for (int i = 0; i < level; i++) {
419: ret *= refsForLevel(i);
420: }
421: return ret;
422: }
423:
424: /**
425: * Return the depth necessary to represent a region of the specified size
426: *
427: * @param size the size of the region
428: */
429: private final int depthForSize(long size) {
430: if (size <= bufLen() - HEADER_SIZE)
431: return 0;
432:
433: int ret = 1;
434: long max = bufLen() * refsForLevel(0);
435:
436: while (size > max) {
437: max *= refsForLevel(++ret);
438: }
439: return ret;
440: }
441:
442: //#ifdef DEBUG
443: final String toString(long page) {
444: return SubPageManager.toString(page);
445: }
446:
447: public String toString() {
448: StringBuffer sb = new StringBuffer("BlockAccess(");
449: sb.append("root=");
450: sb.append(SubPageManager.toString(rootBlock));
451: sb.append(" size=");
452: sb.append(size);
453: if (radices != null) {
454: sb.append(" radices=");
455: for (int i = 0; i < radices.length; i++) {
456: if (i > 0)
457: sb.append(',');
458: sb.append(radices[i]);
459: }
460: }
461: sb.append(" depth=");
462: sb.append(depth);
463: sb.append(" path=");
464: sb.append(path);
465: sb.append(")");
466: return sb.toString();
467: }
468: //#endif
469: }
|