0001: /**
0002: * com.mckoi.store.AbstractStore 30 Aug 2002
0003: *
0004: * Mckoi SQL Database ( http://www.mckoi.com/database )
0005: * Copyright (C) 2000, 2001, 2002 Diehl and Associates, Inc.
0006: *
0007: * This program is free software; you can redistribute it and/or
0008: * modify it under the terms of the GNU General Public License
0009: * Version 2 as published by the Free Software Foundation.
0010: *
0011: * This program is distributed in the hope that it will be useful,
0012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
0013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
0014: * GNU General Public License Version 2 for more details.
0015: *
0016: * You should have received a copy of the GNU General Public License
0017: * Version 2 along with this program; if not, write to the Free Software
0018: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
0019: *
0020: * Change Log:
0021: *
0022: *
0023: */package com.mckoi.store;
0024:
0025: import java.util.Arrays;
0026: import java.util.Collections;
0027: import java.util.List;
0028: import java.util.ArrayList;
0029: import java.util.HashMap;
0030: import java.io.*;
0031: import com.mckoi.util.ByteArrayUtil;
0032: import com.mckoi.util.UserTerminal;
0033:
0034: /**
0035: * Provides an abstract implementation of Store. This implements a bin based
0036: * best-fit recycling algorithm. The store manages a structure that points to
0037: * bins of freed space of specific sizes. When an allocation is requested the
0038: * structure is searched for the first bin that contains an area that best fits
0039: * the size requested.
0040: * <p>
0041: * Provided the derived class supports safe atomic IO operations, this store
0042: * is designed for robustness to the level that at no point is the store left
0043: * in a unworkable (corrupt) state.
0044: *
0045: * @author Tobias Downer
0046: */
0047:
0048: public abstract class AbstractStore implements Store {
0049:
0050: /**
0051: * The free bin list contains 128 entries pointing to the first available
0052: * block in the bin. If the list item contains -1 then there are no free
0053: * blocks in the bin.
0054: */
0055: protected long[] free_bin_list;
0056:
0057: /**
0058: * A pointer to the wilderness area (the last deleted area in the store),
0059: * or -1 if there is no wilderness area.
0060: */
0061: protected long wilderness_pointer;
0062:
0063: /**
0064: * True if this is read-only.
0065: */
0066: protected boolean read_only;
0067:
0068: /**
0069: * The total amount of allocated space within this store since the store
0070: * was openned. Note that this could be a negative amount if more space
0071: * was freed than allocated.
0072: */
0073: protected long total_allocated_space;
0074:
0075: /**
0076: * True if the store was opened dirtily (was not previously closed cleanly).
0077: */
0078: private boolean dirty_open;
0079:
0080: // ---------- Statics ----------
0081:
0082: /**
0083: * The offset into the file that the data areas start.
0084: */
0085: protected static final long DATA_AREA_OFFSET = 256 + 1024 + 32;
0086:
0087: /**
0088: * The offset into the file of the 64 byte fixed area.
0089: */
0090: protected static final long FIXED_AREA_OFFSET = 128;
0091:
0092: /**
0093: * The offset into the file that the bin area starts.
0094: */
0095: protected static final long BIN_AREA_OFFSET = 256;
0096:
0097: /**
0098: * The magic value.
0099: */
0100: protected static final int MAGIC = 0x0AEAE91;
0101:
0102: /**
0103: * Constructs the store.
0104: */
0105: protected AbstractStore(boolean read_only) {
0106: free_bin_list = new long[BIN_ENTRIES + 1];
0107: for (int i = 0; i < BIN_ENTRIES + 1; ++i) {
0108: free_bin_list[i] = (long) -1;
0109: }
0110: wilderness_pointer = -1;
0111: this .read_only = read_only;
0112: }
0113:
0114: /**
0115: * Initializes the store to an empty state.
0116: */
0117: private synchronized void initializeToEmpty() throws IOException {
0118: setDataAreaSize(DATA_AREA_OFFSET);
0119: // New file so write out the initial file area,
0120: ByteArrayOutputStream bout = new ByteArrayOutputStream(
0121: (int) BIN_AREA_OFFSET);
0122: DataOutputStream out = new DataOutputStream(bout);
0123: // The file MAGIC
0124: out.writeInt(MAGIC); // 0
0125: // The file version
0126: out.writeInt(1); // 4
0127: // The number of areas (chunks) in the file (currently unused)
0128: out.writeLong(-1); // 8
0129: // File open/close status byte
0130: out.writeByte(0); // 16
0131:
0132: out.flush();
0133: byte[] buf = new byte[(int) DATA_AREA_OFFSET];
0134: byte[] buf2 = bout.toByteArray();
0135: System.arraycopy(buf2, 0, buf, 0, buf2.length);
0136: ;
0137: for (int i = (int) BIN_AREA_OFFSET; i < (int) DATA_AREA_OFFSET; ++i) {
0138: buf[i] = (byte) 255;
0139: }
0140:
0141: writeByteArrayToPT(0, buf, 0, buf.length);
0142: }
0143:
0144: /**
0145: * Opens the data store. Returns true if the store did not close cleanly.
0146: */
0147: public synchronized boolean open() throws IOException {
0148: internalOpen(read_only);
0149:
0150: // If it's small, initialize to empty
0151: if (endOfDataAreaPointer() < DATA_AREA_OFFSET) {
0152: initializeToEmpty();
0153: }
0154:
0155: byte[] read_buf = new byte[(int) BIN_AREA_OFFSET];
0156: readByteArrayFrom(0, read_buf, 0, read_buf.length);
0157: ByteArrayInputStream b_in = new ByteArrayInputStream(read_buf);
0158: DataInputStream din = new DataInputStream(b_in);
0159:
0160: int magic = din.readInt();
0161: if (magic != MAGIC) {
0162: throw new IOException(
0163: "Format invalid: Magic value is not as expected.");
0164: }
0165: int version = din.readInt();
0166: if (version != 1) {
0167: throw new IOException(
0168: "Format invalid: unrecognised version.");
0169: }
0170: din.readLong(); // ignore
0171: byte status = din.readByte();
0172: dirty_open = false;
0173: if (status == 1) {
0174: // This means the store wasn't closed cleanly.
0175: dirty_open = true;
0176: }
0177:
0178: // Read the bins
0179: readBins();
0180:
0181: // Mark the file as open
0182: if (!read_only) {
0183: writeByteToPT(16, 1);
0184: }
0185:
0186: long file_length = endOfDataAreaPointer();
0187: if (file_length <= 8) {
0188: throw new IOException(
0189: "Format invalid: File size is too small.");
0190: }
0191:
0192: // Set the wilderness pointer.
0193: if (file_length == DATA_AREA_OFFSET) {
0194: wilderness_pointer = -1;
0195: } else {
0196: readByteArrayFrom(file_length - 8, read_buf, 0, 8);
0197: long last_boundary = ByteArrayUtil.getLong(read_buf, 0);
0198: long last_area_pointer = file_length - last_boundary;
0199:
0200: if (last_area_pointer < DATA_AREA_OFFSET) {
0201: System.out.println("last_boundary = " + last_boundary);
0202: System.out.println("last_area_pointer = "
0203: + last_area_pointer);
0204: throw new IOException(
0205: "File corrupt: last_area_pointer is before data part of file.");
0206: }
0207: if (last_area_pointer > file_length - 8) {
0208: throw new IOException(
0209: "File corrupt: last_area_pointer at the end of the file.");
0210: }
0211:
0212: readByteArrayFrom(last_area_pointer, read_buf, 0, 8);
0213: long last_area_header = ByteArrayUtil.getLong(read_buf, 0);
0214: // If this is a freed block, then set this are the wilderness pointer.
0215: if ((last_area_header & 0x08000000000000000L) != 0) {
0216: wilderness_pointer = last_area_pointer;
0217: } else {
0218: wilderness_pointer = -1;
0219: }
0220: }
0221:
0222: return dirty_open;
0223: }
0224:
0225: /**
0226: * Closes the store.
0227: */
0228: public synchronized void close() throws IOException {
0229:
0230: // Mark the file as closed
0231: if (!read_only) {
0232: writeByteToPT(16, 0);
0233: }
0234:
0235: internalClose();
0236: }
0237:
0238: /**
0239: * Returns true if the given area size is valid. Currently the criteria
0240: * for a valid boundary size is (size >= 24) and (size % 8 == 0) and
0241: * (size < 200 gigabytes)
0242: */
0243: protected static boolean isValidBoundarySize(long size) {
0244: long MAX_AREA_SIZE = (long) Integer.MAX_VALUE * 200;
0245: size = size & 0x07FFFFFFFFFFFFFFFL;
0246: return ((size < MAX_AREA_SIZE) && (size >= 24) && ((size & 0x07) == 0));
0247: }
0248:
0249: /**
0250: * Reads an 8 byte long at the given position in the data area.
0251: */
0252: private byte[] buf = new byte[8];
0253:
0254: private long readLongAt(long position) throws IOException {
0255: readByteArrayFrom(position, buf, 0, 8);
0256: return ByteArrayUtil.getLong(buf, 0);
0257: }
0258:
0259: /**
0260: * Performs a repair scan from the given pointer. This is a recursive
0261: * algorithm that looks for at most 'n' number of repairs before giving
0262: * up. Returns false if a repair path could not be found.
0263: */
0264: private boolean repairScan(final ArrayList areas_to_fix,
0265: final long pointer, final long end_pointer,
0266: final boolean scan_forward, final int max_repairs)
0267: throws IOException {
0268: // Recurse end conditions;
0269: // If the end is reached, success!
0270: if (pointer == end_pointer) {
0271: return true;
0272: }
0273: // If max repairs exhausted, failure!
0274: if (pointer > end_pointer || max_repairs <= 0) {
0275: return false;
0276: }
0277:
0278: long pointer_to_head = scan_forward ? pointer : end_pointer - 8;
0279:
0280: // Does the pointer at least look right?
0281: long first_header = readLongAt(pointer_to_head) & 0x07FFFFFFFFFFFFFFFL;
0282: // If it's a valid boundary size, and the header points inside the
0283: // end boundary
0284: long max_bound_size = end_pointer - pointer;
0285: if (isValidBoundarySize(first_header)
0286: && first_header <= max_bound_size) {
0287:
0288: long pointer_to_tail = scan_forward ? (pointer + first_header) - 8
0289: : end_pointer - first_header;
0290:
0291: // If the end doesn't look okay,
0292: long end_area_pointer = pointer_to_tail;
0293: long end_header = readLongAt(end_area_pointer) & 0x07FFFFFFFFFFFFFFFL;
0294: boolean valid_end_header = (first_header == end_header);
0295:
0296: long scan_area_p1 = scan_forward ? (pointer + first_header)
0297: : pointer;
0298: long scan_area_p2 = scan_forward ? end_pointer
0299: : (end_pointer - first_header);
0300:
0301: if (!valid_end_header) {
0302: // First and ends are invalid, so lets first assume we make the end
0303: // valid and recurse,
0304: long area_p = scan_forward ? pointer_to_head
0305: : pointer_to_tail;
0306: areas_to_fix.add(new Long(area_p));
0307: areas_to_fix.add(new Long(first_header));
0308:
0309: boolean b = repairScan(areas_to_fix, scan_area_p1,
0310: scan_area_p2, true, max_repairs - 1);
0311: // If success
0312: if (b) {
0313: return true;
0314: }
0315:
0316: // If failure, take that repair off the top
0317: areas_to_fix.remove(areas_to_fix.size() - 1);
0318: areas_to_fix.remove(areas_to_fix.size() - 1);
0319: // And keep searching
0320: } else {
0321: // Looks okay, so keep going,
0322:
0323: // This really does the same thing as recursing through the scan area
0324: // however, we have to reduce the stack usage for large files which
0325: // makes this iterative solution necessary. Basically, this looks for
0326: // the first broken area and reverts back to applying the recursive
0327: // algorithm on it.
0328: boolean something_broken = false;
0329: long previous1_scan_area_p1 = scan_area_p1;
0330: long previous2_scan_area_p1 = scan_area_p1;
0331: long previous3_scan_area_p1 = scan_area_p1;
0332:
0333: while (scan_area_p1 < scan_area_p2 && !something_broken) {
0334: // Assume something broken,
0335: something_broken = true;
0336:
0337: // Does the pointer at least look right?
0338: long scanning_header = readLongAt(scan_area_p1) & 0x07FFFFFFFFFFFFFFFL;
0339: long scan_max_bound_size = scan_area_p2
0340: - scan_area_p1;
0341: if (isValidBoundarySize(scanning_header)
0342: && scanning_header <= scan_max_bound_size) {
0343: long scan_end_header = readLongAt((scan_area_p1 + scanning_header) - 8) & 0x07FFFFFFFFFFFFFFFL;
0344: if (scan_end_header == scanning_header) {
0345: // Cycle the scanned areas
0346: previous3_scan_area_p1 = previous2_scan_area_p1;
0347: previous2_scan_area_p1 = previous1_scan_area_p1;
0348: previous1_scan_area_p1 = scan_area_p1;
0349:
0350: scan_area_p1 = (scan_area_p1 + scanning_header);
0351: // Enough evidence that area is not broken, so continue scan
0352: something_broken = false;
0353: }
0354: }
0355: }
0356: if (something_broken) {
0357: // Back track to the last 3 scanned areas and perform a repair on
0358: // this area. This allows for the scan to have more choices on
0359: // repair paths.
0360: scan_area_p1 = previous3_scan_area_p1;
0361: }
0362:
0363: // The recursive scan on the (potentially) broken area.
0364: boolean b = repairScan(areas_to_fix, scan_area_p1,
0365: scan_area_p2, true, max_repairs);
0366: if (b) {
0367: // Repair succeeded!
0368: return b;
0369: }
0370:
0371: // Repair didn't succeed so keep searching.
0372: }
0373: }
0374:
0375: // Try reversing the scan and see if that comes up with something valid.
0376: if (scan_forward) {
0377: boolean b = repairScan(areas_to_fix, pointer, end_pointer,
0378: false, max_repairs);
0379: // Success
0380: if (b) {
0381: return b;
0382: }
0383:
0384: } else {
0385: return false;
0386: }
0387:
0388: // We guarenteed to be scan forward if we get here....
0389:
0390: // Facts: we know that the start and end pointers are invalid....
0391:
0392: // Search forward for something that looks like a boundary. If we don't
0393: // find it, search backwards for something that looks like a boundary.
0394:
0395: final long max_size = end_pointer - pointer;
0396: for (long i = 16; i < max_size; i += 8) {
0397:
0398: long v = readLongAt(pointer + i) & 0x07FFFFFFFFFFFFFFFL;
0399: if (v == i + 8) {
0400: // This looks like a boundary, so try this...
0401: areas_to_fix.add(new Long(pointer));
0402: areas_to_fix.add(new Long(i + 8));
0403: boolean b = repairScan(areas_to_fix, pointer + i + 8,
0404: end_pointer, true, max_repairs - 1);
0405: if (b) {
0406: return true;
0407: }
0408: areas_to_fix.remove(areas_to_fix.size() - 1);
0409: areas_to_fix.remove(areas_to_fix.size() - 1);
0410: }
0411:
0412: }
0413:
0414: // Scan backwards....
0415: for (long i = max_size - 8 - 16; i >= 0; i -= 8) {
0416:
0417: long v = readLongAt(pointer + i) & 0x07FFFFFFFFFFFFFFFL;
0418: if (v == (max_size - i)) {
0419: // This looks like a boundary, so try this...
0420: areas_to_fix.add(new Long(pointer + i));
0421: areas_to_fix.add(new Long((max_size - i)));
0422: boolean b = repairScan(areas_to_fix, pointer, pointer
0423: + i, true, max_repairs - 1);
0424: if (b) {
0425: return true;
0426: }
0427: areas_to_fix.remove(areas_to_fix.size() - 1);
0428: areas_to_fix.remove(areas_to_fix.size() - 1);
0429: }
0430:
0431: }
0432:
0433: // No luck, so simply set this as a final big area and return true.
0434: // NOTE: There are other tests possible here but I think what we have will
0435: // find fixes for 99% of corruption cases.
0436: areas_to_fix.add(new Long(pointer));
0437: areas_to_fix.add(new Long(end_pointer - pointer));
0438:
0439: return true;
0440:
0441: }
0442:
0443: /**
0444: * Opens/scans the store looking for any errors with the layout. If a
0445: * problem with the store is detected, it attempts to fix it.
0446: */
0447: public synchronized void openScanAndFix(UserTerminal terminal)
0448: throws IOException {
0449:
0450: internalOpen(read_only);
0451:
0452: terminal.println("- Store: " + toString());
0453:
0454: // If it's small, initialize to empty
0455: if (endOfDataAreaPointer() < DATA_AREA_OFFSET) {
0456: terminal
0457: .println("+ Store too small - initializing to empty.");
0458: initializeToEmpty();
0459: return;
0460: }
0461:
0462: byte[] read_buf = new byte[(int) BIN_AREA_OFFSET];
0463: readByteArrayFrom(0, read_buf, 0, read_buf.length);
0464: ByteArrayInputStream b_in = new ByteArrayInputStream(read_buf);
0465: DataInputStream din = new DataInputStream(b_in);
0466:
0467: int magic = din.readInt();
0468: if (magic != MAGIC) {
0469: terminal
0470: .println("! Store magic value not present - not fixable.");
0471: return;
0472: }
0473: int version = din.readInt();
0474: if (version != 1) {
0475: terminal
0476: .println("! Store version is invalid - not fixable.");
0477: return;
0478: }
0479:
0480: // Check the size
0481: long end_of_data_area = endOfDataAreaPointer();
0482: if (end_of_data_area < DATA_AREA_OFFSET + 16) {
0483: // Store size is too small. There's nothing to be lost be simply
0484: // reinitializing it to a blank state.
0485: terminal
0486: .println("! Store is too small, reinitializing store to blank state.");
0487: initializeToEmpty();
0488: return;
0489: }
0490:
0491: // Do a recursive scan over the store.
0492: ArrayList repairs = new ArrayList();
0493: boolean b = repairScan(repairs, DATA_AREA_OFFSET,
0494: endOfDataAreaPointer(), true, 20);
0495:
0496: if (b) {
0497: if (repairs.size() == 0) {
0498: terminal.println("- Store areas are intact.");
0499: } else {
0500: terminal.println("+ " + (repairs.size() / 2)
0501: + " area repairs:");
0502: for (int i = 0; i < repairs.size(); i += 2) {
0503: terminal.println(" Area pointer: "
0504: + repairs.get(i));
0505: terminal.println(" Area size: "
0506: + repairs.get(i + 1));
0507: long pointer = ((Long) repairs.get(i)).longValue();
0508: long size = ((Long) repairs.get(i + 1)).longValue();
0509: coalescArea(pointer, size);
0510: }
0511: }
0512: } else {
0513: terminal.println("- Store is not repairable!");
0514: }
0515:
0516: // Rebuild the free bins,
0517: free_bin_list = new long[BIN_ENTRIES + 1];
0518: for (int i = 0; i < BIN_ENTRIES + 1; ++i) {
0519: free_bin_list[i] = (long) -1;
0520: }
0521:
0522: terminal.println("+ Rebuilding free bins.");
0523: long[] header = new long[2];
0524: // Scan for all free areas in the store.
0525: long pointer = DATA_AREA_OFFSET;
0526: while (pointer < end_of_data_area) {
0527: getAreaHeader(pointer, header);
0528: long area_size = (header[0] & 0x07FFFFFFFFFFFFFFFL);
0529: boolean is_free = ((header[0] & 0x08000000000000000L) != 0);
0530:
0531: if (is_free) {
0532: addToBinChain(pointer, area_size);
0533: }
0534:
0535: pointer += area_size;
0536: }
0537:
0538: // Update all the bins
0539: writeAllBins();
0540:
0541: terminal.println("- Store repair complete.");
0542:
0543: // Open the store for real,
0544: open();
0545:
0546: }
0547:
0548: /**
0549: * Performs an extensive lookup on all the tables in this store and sets a
0550: * number of properties in the given HashMap
0551: * (property name(String) -> property description(Object)). This should be
0552: * used for store diagnostics.
0553: * <p>
0554: * Assume the store is open.
0555: */
0556: public synchronized void statsScan(HashMap properties)
0557: throws IOException {
0558:
0559: long free_areas = 0;
0560: long free_total = 0;
0561: long allocated_areas = 0;
0562: long allocated_total = 0;
0563:
0564: final long end_of_data_area = endOfDataAreaPointer();
0565:
0566: long[] header = new long[2];
0567: // The first header
0568: long pointer = DATA_AREA_OFFSET;
0569: while (pointer < end_of_data_area) {
0570: getAreaHeader(pointer, header);
0571: long area_size = (header[0] & 0x07FFFFFFFFFFFFFFFL);
0572:
0573: if ((header[0] & 0x08000000000000000L) != 0) {
0574: ++free_areas;
0575: free_total += area_size;
0576: } else {
0577: ++allocated_areas;
0578: allocated_total += area_size;
0579: }
0580:
0581: pointer += area_size;
0582: }
0583:
0584: if (wilderness_pointer != -1) {
0585: getAreaHeader(wilderness_pointer, header);
0586: long wilderness_size = (header[0] & 0x07FFFFFFFFFFFFFFFL);
0587: properties.put("AbstractStore.wilderness_size", new Long(
0588: wilderness_size));
0589: }
0590:
0591: properties.put("AbstractStore.end_of_data_area", new Long(
0592: end_of_data_area));
0593: properties
0594: .put("AbstractStore.free_areas", new Long(free_areas));
0595: properties
0596: .put("AbstractStore.free_total", new Long(free_total));
0597: properties.put("AbstractStore.allocated_areas", new Long(
0598: allocated_areas));
0599: properties.put("AbstractStore.allocated_total", new Long(
0600: allocated_total));
0601:
0602: }
0603:
0604: /**
0605: * Returns a List of Long objects that contain a complete list of all areas
0606: * in the store. This is useful for checking if a given pointer is valid
0607: * or not. The returned list is sorted from start area to end area.
0608: */
0609: public List getAllAreas() throws IOException {
0610: ArrayList list = new ArrayList();
0611: final long end_of_data_area = endOfDataAreaPointer();
0612: long[] header = new long[2];
0613: // The first header
0614: long pointer = DATA_AREA_OFFSET;
0615: while (pointer < end_of_data_area) {
0616: getAreaHeader(pointer, header);
0617: long area_size = (header[0] & 0x07FFFFFFFFFFFFFFFL);
0618: if ((header[0] & 0x08000000000000000L) == 0) {
0619: list.add(new Long(pointer));
0620: }
0621: pointer += area_size;
0622: }
0623: return list;
0624: }
0625:
0626: /**
0627: * Scans the area list, and any areas that aren't deleted and aren't found
0628: * in the given ArrayList are returned as leaked areas. This is a useful
0629: * method for finding any leaks in the store.
0630: */
0631: public ArrayList findAllocatedAreasNotIn(ArrayList list)
0632: throws IOException {
0633:
0634: // Sort the list
0635: Collections.sort(list);
0636:
0637: // The list of leaked areas
0638: ArrayList leaked_areas = new ArrayList();
0639:
0640: int list_index = 0;
0641:
0642: // What area are we looking for?
0643: long looking_for = Long.MAX_VALUE;
0644: if (list_index < list.size()) {
0645: looking_for = ((Long) list.get(list_index)).longValue();
0646: ++list_index;
0647: }
0648:
0649: final long end_of_data_area = endOfDataAreaPointer();
0650: long[] header = new long[2];
0651:
0652: long pointer = DATA_AREA_OFFSET;
0653: while (pointer < end_of_data_area) {
0654: getAreaHeader(pointer, header);
0655: long area_size = (header[0] & 0x07FFFFFFFFFFFFFFFL);
0656: boolean area_free = (header[0] & 0x08000000000000000L) != 0;
0657:
0658: if (pointer == looking_for) {
0659: if (area_free) {
0660: throw new IOException("Area (pointer = " + pointer
0661: + ") is not allocated!");
0662: }
0663: // Update the 'looking_for' pointer
0664: if (list_index < list.size()) {
0665: looking_for = ((Long) list.get(list_index))
0666: .longValue();
0667: ++list_index;
0668: } else {
0669: looking_for = Long.MAX_VALUE;
0670: }
0671: } else if (pointer > looking_for) {
0672: throw new IOException("Area (pointer = " + looking_for
0673: + ") wasn't found in store!");
0674: } else {
0675: // An area that isn't in the list
0676: if (!area_free) {
0677: // This is a leaked area.
0678: // It isn't free and it isn't in the list
0679: leaked_areas.add(new Long(pointer));
0680: }
0681: }
0682:
0683: pointer += area_size;
0684: }
0685:
0686: return leaked_areas;
0687:
0688: }
0689:
0690: /**
0691: * Returns the total allocated space since the file was openned.
0692: */
0693: public synchronized long totalAllocatedSinceStart() {
0694: return total_allocated_space;
0695: }
0696:
0697: /**
0698: * Returns the bin index that would be the minimum size to store the given
0699: * object.
0700: */
0701: private int minimumBinSizeIndex(long size) {
0702: int i = Arrays.binarySearch(BIN_SIZES, (int) size);
0703: if (i < 0) {
0704: i = -(i + 1);
0705: }
0706: return i;
0707: }
0708:
0709: /**
0710: * Internally opens the backing area. If 'read_only' is true then the
0711: * store is openned in read only mode.
0712: */
0713: protected abstract void internalOpen(boolean read_only)
0714: throws IOException;
0715:
0716: /**
0717: * Internally closes the backing area.
0718: */
0719: protected abstract void internalClose() throws IOException;
0720:
0721: /**
0722: * Reads a byte from the given position in the file.
0723: */
0724: protected abstract int readByteFrom(long position)
0725: throws IOException;
0726:
0727: /**
0728: * Reads a byte array from the given position in the file. Returns the
0729: * number of bytes read.
0730: */
0731: protected abstract int readByteArrayFrom(long position, byte[] buf,
0732: int off, int len) throws IOException;
0733:
0734: /**
0735: * Writes a byte to the given position in the file.
0736: */
0737: protected abstract void writeByteTo(long position, int b)
0738: throws IOException;
0739:
0740: /**
0741: * Writes a byte array to the given position in the file.
0742: */
0743: protected abstract void writeByteArrayTo(long position, byte[] buf,
0744: int off, int len) throws IOException;
0745:
0746: /**
0747: * Returns a pointer to the end of the current data area.
0748: */
0749: protected abstract long endOfDataAreaPointer() throws IOException;
0750:
0751: /**
0752: * Sets the size of the data area.
0753: */
0754: protected abstract void setDataAreaSize(long length)
0755: throws IOException;
0756:
0757: /**
0758: * WriteByteTo pass-through method.
0759: */
0760: private final void writeByteToPT(long position, int b)
0761: throws IOException {
0762: writeByteTo(position, b);
0763: }
0764:
0765: /**
0766: * WriteByteArrayTo pass-through method.
0767: */
0768: private final void writeByteArrayToPT(long position, byte[] buf,
0769: int off, int len) throws IOException {
0770: writeByteArrayTo(position, buf, off, len);
0771: }
0772:
0773: // ----------
0774:
0775: /**
0776: * Checks the pointer is valid.
0777: */
0778: protected void checkPointer(long pointer) throws IOException {
0779: if (pointer < DATA_AREA_OFFSET
0780: || pointer >= endOfDataAreaPointer()) {
0781: throw new IOException("Pointer out of range: "
0782: + DATA_AREA_OFFSET + " > " + pointer + " > "
0783: + endOfDataAreaPointer());
0784: }
0785: }
0786:
0787: /**
0788: * A buffered work area we work with when reading/writing bin pointers from
0789: * the file header.
0790: */
0791: private final byte[] bin_area = new byte[128 * 8];
0792:
0793: /**
0794: * Reads the bins from the header information in the file.
0795: */
0796: protected void readBins() throws IOException {
0797: readByteArrayFrom(BIN_AREA_OFFSET, bin_area, 0, 128 * 8);
0798: ByteArrayInputStream bin = new ByteArrayInputStream(bin_area);
0799: DataInputStream in = new DataInputStream(bin);
0800: for (int i = 0; i < 128; ++i) {
0801: free_bin_list[i] = in.readLong();
0802: }
0803: }
0804:
0805: /**
0806: * Updates all bins to the data area header area.
0807: */
0808: protected void writeAllBins() throws IOException {
0809: int p = 0;
0810: for (int i = 0; i < 128; ++i, p += 8) {
0811: long val = free_bin_list[i];
0812: ByteArrayUtil.setLong(val, bin_area, p);
0813: }
0814: writeByteArrayToPT(BIN_AREA_OFFSET, bin_area, 0, 128 * 8);
0815: }
0816:
0817: /**
0818: * Updates the given bin index to the data area header area.
0819: */
0820: protected void writeBinIndex(int index) throws IOException {
0821: int p = index * 8;
0822: long val = free_bin_list[index];
0823: ByteArrayUtil.setLong(val, bin_area, p);
0824: writeByteArrayToPT(BIN_AREA_OFFSET + p, bin_area, p, 8);
0825: }
0826:
0827: protected final byte[] header_buf = new byte[16];
0828:
0829: /**
0830: * Sets the 'header' array with information from the header of the given
0831: * pointer.
0832: */
0833: protected void getAreaHeader(long pointer, long[] header)
0834: throws IOException {
0835: readByteArrayFrom(pointer, header_buf, 0, 16);
0836: header[0] = ByteArrayUtil.getLong(header_buf, 0);
0837: header[1] = ByteArrayUtil.getLong(header_buf, 8);
0838: }
0839:
0840: /**
0841: * Sets the 'header' array with information from the previous header to the
0842: * given pointer, and returns a pointer to the previous area.
0843: */
0844: protected long getPreviousAreaHeader(long pointer, long[] header)
0845: throws IOException {
0846: // If the pointer is the start of the file area
0847: if (pointer == DATA_AREA_OFFSET) {
0848: // Return a 0 sized block
0849: header[0] = 0;
0850: return -1;
0851: } else {
0852: readByteArrayFrom(pointer - 8, header_buf, 0, 8);
0853: long sz = ByteArrayUtil.getLong(header_buf, 0);
0854: sz = sz & 0x07FFFFFFFFFFFFFFFL;
0855: long previous_pointer = pointer - sz;
0856: readByteArrayFrom(previous_pointer, header_buf, 0, 8);
0857: header[0] = ByteArrayUtil.getLong(header_buf, 0);
0858: return previous_pointer;
0859: }
0860: }
0861:
0862: /**
0863: * Sets the 'header' array with information from the next header to the
0864: * given pointer, and returns a pointer to the next area.
0865: */
0866: protected long getNextAreaHeader(long pointer, long[] header)
0867: throws IOException {
0868: readByteArrayFrom(pointer, header_buf, 0, 8);
0869: long sz = ByteArrayUtil.getLong(header_buf, 0);
0870: sz = sz & 0x07FFFFFFFFFFFFFFFL;
0871: long next_pointer = pointer + sz;
0872:
0873: if (next_pointer >= endOfDataAreaPointer()) {
0874: // Return a 0 sized block
0875: header[0] = 0;
0876: return -1;
0877: }
0878:
0879: readByteArrayFrom(next_pointer, header_buf, 0, 8);
0880: header[0] = ByteArrayUtil.getLong(header_buf, 0);
0881: return next_pointer;
0882: }
0883:
0884: /**
0885: * Rebounds the given area with the given header information. If
0886: * 'write_headers' is true, the header (header[0]) is changed. Note that this
0887: * shouldn't be used to change the size of a chunk.
0888: */
0889: protected void reboundArea(long pointer, long[] header,
0890: boolean write_headers) throws IOException {
0891: if (write_headers) {
0892: ByteArrayUtil.setLong(header[0], header_buf, 0);
0893: ByteArrayUtil.setLong(header[1], header_buf, 8);
0894: writeByteArrayToPT(pointer, header_buf, 0, 16);
0895: } else {
0896: ByteArrayUtil.setLong(header[1], header_buf, 8);
0897: writeByteArrayToPT(pointer + 8, header_buf, 8, 8);
0898: }
0899: }
0900:
0901: /**
0902: * Coalesc one or more areas into a larger area. This alters the boundary
0903: * of the area to encompass the given size.
0904: */
0905: protected void coalescArea(long pointer, long size)
0906: throws IOException {
0907:
0908: ByteArrayUtil.setLong(size, header_buf, 0);
0909:
0910: // ISSUE: Boundary alteration is a moment when corruption could occur.
0911: // There are two seeks and writes here and when we are setting the
0912: // end points, there is a risk of failure.
0913:
0914: writeByteArrayToPT(pointer, header_buf, 0, 8);
0915: writeByteArrayToPT((pointer + size) - 8, header_buf, 0, 8);
0916: }
0917:
0918: /**
0919: * Expands the data area by at least the minimum size given. Returns the
0920: * actual size the data area was expanded by.
0921: */
0922: protected long expandDataArea(long minimum_size) throws IOException {
0923: long end_of_data_area = endOfDataAreaPointer();
0924:
0925: // Round all sizes up to the nearest 8
0926: // We grow only by a small amount if the area is small, and a large amount
0927: // if the area is large.
0928: long over_grow = end_of_data_area / 64;
0929: long d = (over_grow & 0x07L);
0930: if (d != 0) {
0931: over_grow = over_grow + (8 - d);
0932: }
0933: over_grow = Math.min(over_grow, 262144L);
0934: if (over_grow < 1024) {
0935: over_grow = 1024;
0936: }
0937:
0938: long grow_by = minimum_size + over_grow;
0939: long new_file_length = end_of_data_area + grow_by;
0940: setDataAreaSize(new_file_length);
0941: return grow_by;
0942: }
0943:
0944: /**
0945: * Splits an area pointed to by 'pointer' at a new boundary point.
0946: */
0947: protected void splitArea(long pointer, long new_boundary)
0948: throws IOException {
0949: // Split the area pointed to by the pointer.
0950: readByteArrayFrom(pointer, header_buf, 0, 8);
0951: long cur_size = ByteArrayUtil.getLong(header_buf, 0) & 0x07FFFFFFFFFFFFFFFL;
0952: long left_size = new_boundary;
0953: long right_size = cur_size - new_boundary;
0954:
0955: if (right_size < 0) {
0956: throw new Error("right_size < 0");
0957: }
0958:
0959: ByteArrayUtil.setLong(left_size, header_buf, 0);
0960: ByteArrayUtil.setLong(right_size, header_buf, 8);
0961:
0962: // ISSUE: Boundary alteration is a moment when corruption could occur.
0963: // There are three seeks and writes here and when we are setting the
0964: // end points, there is a risk of failure.
0965:
0966: // First set the boundary
0967: writeByteArrayToPT((pointer + new_boundary) - 8, header_buf, 0,
0968: 16);
0969: // Now set the end points
0970: writeByteArrayToPT(pointer, header_buf, 0, 8);
0971: writeByteArrayToPT((pointer + cur_size) - 8, header_buf, 8, 8);
0972: }
0973:
0974: private long[] header_info = new long[2];
0975: private long[] header_info2 = new long[2];
0976:
0977: /**
0978: * Adds the given area to the bin represented by the bin_chain_index.
0979: */
0980: private void addToBinChain(long pointer, long size)
0981: throws IOException {
0982:
0983: checkPointer(pointer);
0984:
0985: // What bin would this area fit into?
0986: int bin_chain_index = minimumBinSizeIndex(size);
0987:
0988: // System.out.println("+ Adding to bin chain: " + pointer + " size: " + size);
0989: // System.out.println("+ Adding to index: " + bin_chain_index);
0990:
0991: long cur_pointer = free_bin_list[bin_chain_index];
0992: if (cur_pointer == -1) {
0993: // If the bin chain has no elements,
0994: header_info[0] = (size | 0x08000000000000000L);
0995: header_info[1] = -1;
0996: reboundArea(pointer, header_info, true);
0997: free_bin_list[bin_chain_index] = pointer;
0998: writeBinIndex(bin_chain_index);
0999: } else {
1000: boolean inserted = false;
1001: long last_pointer = -1;
1002: int searches = 0;
1003: while (cur_pointer != -1 && inserted == false) {
1004: // Get the current pointer
1005: getAreaHeader(cur_pointer, header_info);
1006:
1007: long header = header_info[0];
1008: long next = header_info[1];
1009: // Assert - the header must have deleted flag
1010: if ((header & 0x08000000000000000L) == 0) {
1011: throw new Error(
1012: "Assert failed - area not marked as deleted. "
1013: + "pos = " + cur_pointer
1014: + " this = " + toString());
1015: }
1016: long area_size = header ^ 0x08000000000000000L;
1017: if (area_size >= size || searches >= 12) {
1018: // Insert if the area size is >= than the size we are adding.
1019: // Set the previous header to point to this
1020: long previous = last_pointer;
1021:
1022: // Set up the deleted area
1023: header_info[0] = (size | 0x08000000000000000L);
1024: header_info[1] = cur_pointer;
1025: reboundArea(pointer, header_info, true);
1026:
1027: if (last_pointer != -1) {
1028: // Set the previous in the chain to point to the deleted area
1029: getAreaHeader(previous, header_info);
1030: header_info[1] = pointer;
1031: reboundArea(previous, header_info, false);
1032: } else {
1033: // Otherwise set the head bin item
1034: free_bin_list[bin_chain_index] = pointer;
1035: writeBinIndex(bin_chain_index);
1036: }
1037:
1038: inserted = true;
1039: }
1040: last_pointer = cur_pointer;
1041: cur_pointer = next;
1042: ++searches;
1043: }
1044:
1045: // If we reach the end and we haven't inserted,
1046: if (!inserted) {
1047: // Set the new deleted area.
1048: header_info[0] = (size | 0x08000000000000000L);
1049: header_info[1] = -1;
1050: reboundArea(pointer, header_info, true);
1051:
1052: // Set the previous entry to this
1053: getAreaHeader(last_pointer, header_info);
1054: header_info[1] = pointer;
1055: reboundArea(last_pointer, header_info, false);
1056:
1057: }
1058:
1059: }
1060:
1061: }
1062:
1063: /**
1064: * Removes the given area from the bin chain. This requires a search of the
1065: * bin chain for the given size.
1066: */
1067: private void removeFromBinChain(long pointer, long size)
1068: throws IOException {
1069: // What bin index should we be looking in?
1070: int bin_chain_index = minimumBinSizeIndex(size);
1071:
1072: // System.out.println("- Removing from bin chain " + pointer + " size " + size);
1073: // System.out.println("- Removing from index " + bin_chain_index);
1074:
1075: long previous_pointer = -1;
1076: long cur_pointer = free_bin_list[bin_chain_index];
1077: // Search this bin for the pointer
1078: // NOTE: This is an iterative search through the bin chain
1079: while (pointer != cur_pointer) {
1080: if (cur_pointer == -1) {
1081: throw new IOException("Area not found in bin chain! "
1082: + "pos = " + pointer + " store = " + toString());
1083: }
1084: // Move to the next in the chain
1085: getAreaHeader(cur_pointer, header_info);
1086: previous_pointer = cur_pointer;
1087: cur_pointer = header_info[1];
1088: }
1089:
1090: // Found the pointer, so remove it,
1091: if (previous_pointer == -1) {
1092: getAreaHeader(pointer, header_info);
1093: free_bin_list[bin_chain_index] = header_info[1];
1094: writeBinIndex(bin_chain_index);
1095: } else {
1096: getAreaHeader(previous_pointer, header_info2);
1097: getAreaHeader(pointer, header_info);
1098: header_info2[1] = header_info[1];
1099: reboundArea(previous_pointer, header_info2, false);
1100: }
1101:
1102: }
1103:
1104: /**
1105: * Crops the area to the given size. This is used after an area is pulled
1106: * from a bin. This method decides if it's worth reusing any space left over
1107: * and the end of the area.
1108: */
1109: private void cropArea(long pointer, long allocated_size)
1110: throws IOException {
1111: // Get the header info
1112: getAreaHeader(pointer, header_info);
1113: long header = header_info[0];
1114: // Can we recycle the difference in area size?
1115: final long free_area_size = header;
1116: // The difference between the size of the free area and the size
1117: // of the allocated area?
1118: final long size_difference = free_area_size - allocated_size;
1119: // If the difference is greater than 512 bytes, add the excess space to
1120: // a free bin.
1121: boolean is_wilderness = (pointer == wilderness_pointer);
1122: if ((is_wilderness && size_difference >= 32)
1123: || size_difference >= 512) {
1124: // Split the area into two areas.
1125: splitArea(pointer, allocated_size);
1126:
1127: long left_over_pointer = pointer + allocated_size;
1128: // Add this area to the bin chain
1129: addToBinChain(left_over_pointer, size_difference);
1130:
1131: // If pointer is the wilderness area, set this as the new wilderness
1132: if (is_wilderness
1133: || (left_over_pointer + size_difference) >= endOfDataAreaPointer()) {
1134: wilderness_pointer = left_over_pointer;
1135: }
1136:
1137: } else {
1138: // If pointer is the wilderness area, set wilderness to -1
1139: if (is_wilderness) {
1140: wilderness_pointer = -1;
1141: }
1142: }
1143: }
1144:
1145: /**
1146: * Allocates a block of memory from the backing area of the given size and
1147: * returns a pointer to that area.
1148: */
1149: private long alloc(long size) throws IOException {
1150:
1151: // Negative allocations are not allowed
1152: if (size < 0) {
1153: throw new IOException("Negative size allocation");
1154: }
1155:
1156: // Add 16 bytes for headers
1157: size = size + 16;
1158: // If size < 32, make size = 32
1159: if (size < 32) {
1160: size = 32;
1161: }
1162:
1163: // Round all sizes up to the nearest 8
1164: long d = size & 0x07L;
1165: if (d != 0) {
1166: size = size + (8 - d);
1167: }
1168:
1169: final long real_alloc_size = size;
1170:
1171: // Search the free bin list for the first bin that matches the given size.
1172: int bin_chain_index;
1173: if (size > MAX_BIN_SIZE) {
1174: bin_chain_index = BIN_ENTRIES;
1175: } else {
1176: int i = minimumBinSizeIndex(size);
1177: bin_chain_index = i;
1178: }
1179:
1180: // Search the bins until we find the first area that is the nearest fit to
1181: // the size requested.
1182: int found_bin_index = -1;
1183: long previous_pointer = -1;
1184: boolean first = true;
1185: for (int i = bin_chain_index; i < BIN_ENTRIES + 1
1186: && found_bin_index == -1; ++i) {
1187: long cur_pointer = free_bin_list[i];
1188: if (cur_pointer != -1) {
1189: if (!first) {
1190: // Pick this..
1191: found_bin_index = i;
1192: previous_pointer = -1;
1193: }
1194: // Search this bin for the first that's big enough.
1195: // We only search the first 12 entries in the bin before giving up.
1196: else {
1197: long last_pointer = -1;
1198: int searches = 0;
1199: while (cur_pointer != -1 && found_bin_index == -1
1200: && searches < 12) {
1201: getAreaHeader(cur_pointer, header_info);
1202: long area_size = (header_info[0] & 0x07FFFFFFFFFFFFFFFL);
1203: // Is this area is greater or equal than the required size
1204: // and is not the wilderness area, pick it.
1205: if (cur_pointer != wilderness_pointer
1206: && area_size >= size) {
1207: found_bin_index = i;
1208: previous_pointer = last_pointer;
1209: }
1210: // Go to next in chain.
1211: last_pointer = cur_pointer;
1212: cur_pointer = header_info[1];
1213: ++searches;
1214: }
1215: }
1216:
1217: }
1218: first = false;
1219: }
1220:
1221: // If no area can be recycled,
1222: if (found_bin_index == -1) {
1223:
1224: // Allocate a new area of the given size.
1225: // If there is a wilderness, grow the wilderness area to the new size,
1226: long working_pointer;
1227: long size_to_grow;
1228: long current_area_size;
1229: if (wilderness_pointer != -1) {
1230: working_pointer = wilderness_pointer;
1231: getAreaHeader(wilderness_pointer, header_info);
1232: long wilderness_size = (header_info[0] & 0x07FFFFFFFFFFFFFFFL);
1233: // Remove this from the bins
1234: removeFromBinChain(working_pointer, wilderness_size);
1235: // For safety, we set wilderness_pointer to -1
1236: wilderness_pointer = -1;
1237: size_to_grow = size - wilderness_size;
1238: current_area_size = wilderness_size;
1239: } else {
1240: // wilderness_pointer == -1 so add to the end of the data area.
1241: working_pointer = endOfDataAreaPointer();
1242: size_to_grow = size;
1243: current_area_size = 0;
1244: }
1245:
1246: long expanded_size = 0;
1247: if (size_to_grow > 0) {
1248: // Expand the data area to the new size.
1249: expanded_size = expandDataArea(size_to_grow);
1250: }
1251: // Coalesc the new area to the given size
1252: coalescArea(working_pointer, current_area_size
1253: + expanded_size);
1254: // crop the area
1255: cropArea(working_pointer, size);
1256:
1257: // Add to the total allocated space
1258: total_allocated_space += real_alloc_size;
1259:
1260: return working_pointer;
1261: } else {
1262:
1263: // An area is taken from the bins,
1264: long free_area_pointer;
1265: // Remove this area from the bin chain and possibly add any excess space
1266: // left over to a new bin.
1267: if (previous_pointer == -1) {
1268: free_area_pointer = free_bin_list[found_bin_index];
1269: getAreaHeader(free_area_pointer, header_info);
1270: free_bin_list[found_bin_index] = header_info[1];
1271: writeBinIndex(found_bin_index);
1272: } else {
1273: getAreaHeader(previous_pointer, header_info2);
1274: free_area_pointer = header_info2[1];
1275: getAreaHeader(free_area_pointer, header_info);
1276: header_info2[1] = header_info[1];
1277: reboundArea(previous_pointer, header_info2, false);
1278: }
1279:
1280: // Reset the header of the recycled area.
1281: header_info[0] = (header_info[0] & 0x07FFFFFFFFFFFFFFFL);
1282: reboundArea(free_area_pointer, header_info, true);
1283:
1284: // Crop the area to the given size.
1285: cropArea(free_area_pointer, size);
1286:
1287: // Add to the total allocated space
1288: total_allocated_space += real_alloc_size;
1289:
1290: return free_area_pointer;
1291: }
1292:
1293: }
1294:
1295: /**
1296: * Frees a previously allocated area in the store.
1297: */
1298: private void free(long pointer) throws IOException {
1299:
1300: // Get the area header
1301: getAreaHeader(pointer, header_info);
1302:
1303: if ((header_info[0] & 0x08000000000000000L) != 0) {
1304: throw new IOException("Area already marked as unallocated.");
1305: }
1306:
1307: // If (pointer + size) reaches the end of the header area, set this as the
1308: // wilderness.
1309: boolean set_as_wilderness = ((pointer + header_info[0]) >= endOfDataAreaPointer());
1310:
1311: long r_pointer = pointer;
1312: final long freeing_area_size = header_info[0];
1313: long r_size = freeing_area_size;
1314:
1315: // Can this area coalesc?
1316: long left_pointer = getPreviousAreaHeader(pointer, header_info2);
1317: boolean coalesc = false;
1318: if ((header_info2[0] & 0x08000000000000000L) != 0) {
1319: // Yes, we can coalesc left
1320: long area_size = (header_info2[0] & 0x07FFFFFFFFFFFFFFFL);
1321:
1322: r_pointer = left_pointer;
1323: r_size = r_size + area_size;
1324: // Remove left area from the bin
1325: removeFromBinChain(left_pointer, area_size);
1326: coalesc = true;
1327:
1328: }
1329:
1330: if (!set_as_wilderness) {
1331: long right_pointer = getNextAreaHeader(pointer,
1332: header_info2);
1333: if ((header_info2[0] & 0x08000000000000000L) != 0) {
1334: // Yes, we can coalesc right
1335: long area_size = (header_info2[0] & 0x07FFFFFFFFFFFFFFFL);
1336:
1337: r_size = r_size + area_size;
1338: // Remove right from the bin
1339: removeFromBinChain(right_pointer, area_size);
1340: set_as_wilderness = (right_pointer == wilderness_pointer);
1341: coalesc = true;
1342:
1343: }
1344: }
1345:
1346: // If we are coalescing parent areas
1347: if (coalesc) {
1348: coalescArea(r_pointer, r_size);
1349: }
1350:
1351: // Add this new area to the bin chain,
1352: addToBinChain(r_pointer, r_size);
1353:
1354: // Do we set this as the wilderness?
1355: if (set_as_wilderness) {
1356: wilderness_pointer = r_pointer;
1357: }
1358:
1359: total_allocated_space -= freeing_area_size;
1360:
1361: }
1362:
1363: /**
1364: * Convenience for finding the size of an area. If the area is deleted
1365: * throws an exception.
1366: */
1367: private long getAreaSize(final long pointer) throws IOException {
1368: final byte[] buf = new byte[8];
1369: readByteArrayFrom(pointer, buf, 0, 8);
1370: final long v = ByteArrayUtil.getLong(buf, 0);
1371: if ((v & 0x08000000000000000L) != 0) {
1372: throw new IOException("Area is deleted.");
1373: }
1374: return v - 16;
1375: }
1376:
1377: // ---------- Implemented from Store ----------
1378:
1379: public synchronized AreaWriter createArea(long size)
1380: throws IOException {
1381: long pointer = alloc(size);
1382: return new StoreAreaWriter(pointer, size);
1383: }
1384:
1385: public synchronized void deleteArea(long id) throws IOException {
1386: free(id);
1387: }
1388:
1389: public InputStream getAreaInputStream(long id) throws IOException {
1390: if (id == -1) {
1391: return new StoreAreaInputStream(FIXED_AREA_OFFSET, 64);
1392: } else {
1393: return new StoreAreaInputStream(id + 8, getAreaSize(id));
1394: }
1395: }
1396:
1397: public Area getArea(long id) throws IOException {
1398: // If this is the fixed area
1399: if (id == -1) {
1400: return new StoreArea(id, FIXED_AREA_OFFSET, 64);
1401: }
1402: // Otherwise must be a regular area
1403: else {
1404: return new StoreArea(id, id);
1405: }
1406: }
1407:
1408: public MutableArea getMutableArea(long id) throws IOException {
1409: // If this is the fixed area
1410: if (id == -1) {
1411: return new StoreMutableArea(id, FIXED_AREA_OFFSET, 64);
1412: }
1413: // Otherwise must be a regular area
1414: else {
1415: return new StoreMutableArea(id, id);
1416: }
1417: }
1418:
1419: public boolean lastCloseClean() {
1420: return !dirty_open;
1421: }
1422:
1423: // ---------- Inner classes ----------
1424:
1425: private class StoreAreaInputStream extends InputStream {
1426:
1427: private long pointer;
1428: private long end_pointer;
1429: private long mark;
1430:
1431: public StoreAreaInputStream(long pointer, long max_size) {
1432: this .pointer = pointer;
1433: this .end_pointer = pointer + max_size;
1434: this .mark = -1;
1435: }
1436:
1437: public int read() throws IOException {
1438: if (pointer >= end_pointer) {
1439: return -1;
1440: }
1441: int b = readByteFrom(pointer);
1442: ++pointer;
1443: return b;
1444: }
1445:
1446: public int read(byte[] buf) throws IOException {
1447: return read(buf, 0, buf.length);
1448: }
1449:
1450: public int read(byte[] buf, int off, int len)
1451: throws IOException {
1452: // Is the end of the stream reached?
1453: if (pointer >= end_pointer) {
1454: return -1;
1455: }
1456: // How much can we read?
1457: int read_count = Math.min(len,
1458: (int) (end_pointer - pointer));
1459: int act_read_count;
1460: act_read_count = readByteArrayFrom(pointer, buf, off,
1461: read_count);
1462: if (act_read_count != read_count) {
1463: throw new IOException("act_read_count != read_count");
1464: }
1465: pointer += read_count;
1466: return read_count;
1467: }
1468:
1469: public long skip(long skip) throws IOException {
1470: long to_skip = Math.min(end_pointer - pointer, skip);
1471: pointer += to_skip;
1472: return to_skip;
1473: }
1474:
1475: public int available() throws IOException {
1476: return (int) (end_pointer - pointer);
1477: }
1478:
1479: public void close() throws IOException {
1480: // Do nothing
1481: }
1482:
1483: public void mark(int read_limit) {
1484: mark = pointer;
1485: }
1486:
1487: public void reset() throws IOException {
1488: pointer = mark;
1489: }
1490:
1491: public boolean markSupported() {
1492: return true;
1493: }
1494:
1495: }
1496:
1497: private class StoreArea implements Area {
1498:
1499: protected static final int BUFFER_SIZE = 8;
1500:
1501: protected final long id;
1502: protected final long start_pointer;
1503: protected final long end_pointer;
1504: protected long position;
1505: // A small buffer used when accessing the underlying data
1506: protected final byte[] buffer = new byte[BUFFER_SIZE];
1507:
1508: public StoreArea(final long id, final long pointer)
1509: throws IOException {
1510: // Check the pointer is within the bounds of the data area of the file
1511: checkPointer(pointer);
1512:
1513: readByteArrayFrom(pointer, buffer, 0, 8);
1514: final long v = ByteArrayUtil.getLong(buffer, 0);
1515: if ((v & 0x08000000000000000L) != 0) {
1516: throw new IOException(
1517: "Store being constructed on deleted area.");
1518: }
1519:
1520: final long max_size = v - 16;
1521: this .id = id;
1522: this .start_pointer = pointer + 8;
1523: this .position = start_pointer;
1524: this .end_pointer = start_pointer + max_size;
1525: }
1526:
1527: public StoreArea(final long id, final long pointer,
1528: final long fixed_size) throws IOException {
1529: // Check the pointer is valid
1530: if (pointer != FIXED_AREA_OFFSET) {
1531: checkPointer(pointer);
1532: }
1533:
1534: this .id = id;
1535: this .start_pointer = pointer;
1536: this .position = start_pointer;
1537: this .end_pointer = start_pointer + fixed_size;
1538: }
1539:
1540: protected long checkPositionBounds(int diff) throws IOException {
1541: long new_pos = position + diff;
1542: if (new_pos > end_pointer) {
1543: throw new IOException("Position out of bounds. "
1544: + " start=" + start_pointer + " end="
1545: + end_pointer + " pos=" + position
1546: + " new_pos=" + new_pos);
1547: }
1548: long old_pos = position;
1549: position = new_pos;
1550: return old_pos;
1551: }
1552:
1553: public long getID() {
1554: return id;
1555: }
1556:
1557: public int position() {
1558: return (int) (position - start_pointer);
1559: }
1560:
1561: public int capacity() {
1562: return (int) (end_pointer - start_pointer);
1563: }
1564:
1565: public void position(int position) throws IOException {
1566: long act_position = start_pointer + position;
1567: if (act_position >= 0 && act_position < end_pointer) {
1568: this .position = act_position;
1569: return;
1570: }
1571: throw new IOException("Moved position out of bounds.");
1572: }
1573:
1574: public void copyTo(AreaWriter destination_writer, int size)
1575: throws IOException {
1576: // NOTE: Assuming 'destination' is a StoreArea, the temporary buffer
1577: // could be optimized away to a direct System.arraycopy. However, this
1578: // function would need to be written as a lower level IO function.
1579: final int BUFFER_SIZE = 2048;
1580: byte[] buf = new byte[BUFFER_SIZE];
1581: int to_copy = Math.min(size, BUFFER_SIZE);
1582:
1583: while (to_copy > 0) {
1584: get(buf, 0, to_copy);
1585: destination_writer.put(buf, 0, to_copy);
1586: size -= to_copy;
1587: to_copy = Math.min(size, BUFFER_SIZE);
1588: }
1589: }
1590:
1591: public byte get() throws IOException {
1592: return (byte) readByteFrom(checkPositionBounds(1));
1593: }
1594:
1595: public void get(byte[] buf, int off, int len)
1596: throws IOException {
1597: readByteArrayFrom(checkPositionBounds(len), buf, off, len);
1598: }
1599:
1600: public short getShort() throws IOException {
1601: readByteArrayFrom(checkPositionBounds(2), buffer, 0, 2);
1602: return ByteArrayUtil.getShort(buffer, 0);
1603: }
1604:
1605: public int getInt() throws IOException {
1606: readByteArrayFrom(checkPositionBounds(4), buffer, 0, 4);
1607: return ByteArrayUtil.getInt(buffer, 0);
1608: }
1609:
1610: public long getLong() throws IOException {
1611: readByteArrayFrom(checkPositionBounds(8), buffer, 0, 8);
1612: return ByteArrayUtil.getLong(buffer, 0);
1613: }
1614:
1615: public char getChar() throws IOException {
1616: readByteArrayFrom(checkPositionBounds(2), buffer, 0, 2);
1617: return ByteArrayUtil.getChar(buffer, 0);
1618: }
1619:
1620: public String toString() {
1621: return "[Area start_pointer=" + start_pointer
1622: + " end_pointer=" + end_pointer + " position="
1623: + position + "]";
1624: }
1625:
1626: }
1627:
1628: private class StoreMutableArea extends StoreArea implements
1629: MutableArea {
1630:
1631: public StoreMutableArea(final long id, final long pointer)
1632: throws IOException {
1633: super (id, pointer);
1634: }
1635:
1636: public StoreMutableArea(final long id, final long pointer,
1637: final long fixed_size) throws IOException {
1638: super (id, pointer, fixed_size);
1639: }
1640:
1641: public void checkOut() throws IOException {
1642: // Currently, no-op
1643: }
1644:
1645: public void put(byte b) throws IOException {
1646: writeByteToPT(checkPositionBounds(1), b);
1647: }
1648:
1649: public void put(byte[] buf, int off, int len)
1650: throws IOException {
1651: writeByteArrayToPT(checkPositionBounds(len), buf, off, len);
1652: }
1653:
1654: public void put(byte[] buf) throws IOException {
1655: put(buf, 0, buf.length);
1656: }
1657:
1658: public void putShort(short s) throws IOException {
1659: ByteArrayUtil.setShort(s, buffer, 0);
1660: writeByteArrayToPT(checkPositionBounds(2), buffer, 0, 2);
1661: }
1662:
1663: public void putInt(int i) throws IOException {
1664: ByteArrayUtil.setInt(i, buffer, 0);
1665: writeByteArrayToPT(checkPositionBounds(4), buffer, 0, 4);
1666: }
1667:
1668: public void putLong(long l) throws IOException {
1669: ByteArrayUtil.setLong(l, buffer, 0);
1670: writeByteArrayToPT(checkPositionBounds(8), buffer, 0, 8);
1671: }
1672:
1673: public void putChar(char c) throws IOException {
1674: ByteArrayUtil.setChar(c, buffer, 0);
1675: writeByteArrayToPT(checkPositionBounds(2), buffer, 0, 2);
1676: }
1677:
1678: public String toString() {
1679: return "[MutableArea start_pointer=" + start_pointer
1680: + " end_pointer=" + end_pointer + " position="
1681: + position + "]";
1682: }
1683:
1684: }
1685:
1686: /**
1687: * A simple OutputStream implementation that is on top of an AreaWriter
1688: * object.
1689: */
1690: static class AreaOutputStream extends OutputStream {
1691:
1692: private final AreaWriter writer;
1693:
1694: public AreaOutputStream(AreaWriter writer) {
1695: this .writer = writer;
1696: }
1697:
1698: public void write(int b) throws IOException {
1699: writer.put((byte) b);
1700: }
1701:
1702: public void write(byte[] buf) throws IOException {
1703: writer.put(buf, 0, buf.length);
1704: }
1705:
1706: public void write(byte[] buf, int off, int len)
1707: throws IOException {
1708: writer.put(buf, off, len);
1709: }
1710:
1711: public void flush() throws IOException {
1712: // do nothing
1713: }
1714:
1715: public void close() throws IOException {
1716: // do nothing
1717: }
1718:
1719: }
1720:
1721: private class StoreAreaWriter extends StoreMutableArea implements
1722: AreaWriter {
1723:
1724: public StoreAreaWriter(final long pointer, final long fixed_size)
1725: throws IOException {
1726: super (pointer, pointer + 8, fixed_size);
1727: }
1728:
1729: public OutputStream getOutputStream() {
1730: return new AreaOutputStream(this );
1731: }
1732:
1733: public void finish() throws IOException {
1734: // Currently, no-op
1735: }
1736:
1737: }
1738:
1739: // ---------- Static methods ----------
1740:
1741: /**
1742: * The default bin sizes in bytes. The minimum size of a bin is 32 and the
1743: * maximum size is 2252832.
1744: */
1745: private final static int[] BIN_SIZES = { 32, 64, 96, 128, 160, 192,
1746: 224, 256, 288, 320, 352, 384, 416, 448, 480, 512, 544, 576,
1747: 608, 640, 672, 704, 736, 768, 800, 832, 864, 896, 928, 960,
1748: 992, 1024, 1056, 1088, 1120, 1152, 1184, 1216, 1248, 1280,
1749: 1312, 1344, 1376, 1408, 1440, 1472, 1504, 1536, 1568, 1600,
1750: 1632, 1664, 1696, 1728, 1760, 1792, 1824, 1856, 1888, 1920,
1751: 1952, 1984, 2016, 2048, 2080, 2144, 2208, 2272, 2336, 2400,
1752: 2464, 2528, 2592, 2656, 2720, 2784, 2848, 2912, 2976, 3040,
1753: 3104, 3168, 3232, 3296, 3360, 3424, 3488, 3552, 3616, 3680,
1754: 3744, 3808, 3872, 3936, 4000, 4064, 4128, 4384, 4640, 4896,
1755: 5152, 5408, 5664, 5920, 6176, 6432, 6688, 6944, 7200, 7456,
1756: 7712, 7968, 8224, 10272, 12320, 14368, 16416, 18464, 20512,
1757: 22560, 24608, 57376, 90144, 122912, 155680, 1204256,
1758: 2252832 };
1759:
1760: protected final static int BIN_ENTRIES = BIN_SIZES.length;
1761: private final static int MAX_BIN_SIZE = BIN_SIZES[BIN_ENTRIES - 1];
1762:
1763: }
|