001: /*
002: Copyright (c) 2006, Matthew Estes
003: All rights reserved.
004:
005: Redistribution and use in source and binary forms, with or without
006: modification, are permitted provided that the following conditions are met:
007:
008: * Redistributions of source code must retain the above copyright
009: notice, this list of conditions and the following disclaimer.
010: * Redistributions in binary form must reproduce the above copyright
011: notice, this list of conditions and the following disclaimer in the
012: documentation and/or other materials provided with the distribution.
013: * Neither the name of Metanotion Software nor the names of its
014: contributors may be used to endorse or promote products derived from this
015: software without specific prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
018: IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
019: THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
020: PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
021: CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
022: EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
023: PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
024: PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
025: LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
026: NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
027: SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
028: */
029: package net.metanotion.io.block.index;
030:
031: import java.io.IOException;
032: import java.util.HashMap;
033: import java.util.Random;
034:
035: import net.metanotion.io.RandomAccessInterface;
036: import net.metanotion.io.Serializer;
037: import net.metanotion.io.block.BlockFile;
038: import net.metanotion.util.skiplist.*;
039:
040: public class BSkipList extends SkipList {
041: public int firstSpanPage = 0;
042: public int firstLevelPage = 0;
043: public int skipPage = 0;
044: public BlockFile bf;
045:
046: public HashMap spanHash = new HashMap();
047: public HashMap levelHash = new HashMap();
048:
049: protected BSkipList() {
050: }
051:
052: public BSkipList(int spanSize, BlockFile bf, int skipPage,
053: Serializer key, Serializer val) throws IOException {
054: if (spanSize < 1) {
055: throw new Error("Span size too small");
056: }
057:
058: this .skipPage = skipPage;
059: this .bf = bf;
060:
061: BlockFile.pageSeek(bf.file, skipPage);
062: firstSpanPage = bf.file.readInt();
063: firstLevelPage = bf.file.readInt();
064: size = bf.file.readInt();
065: spans = bf.file.readInt();
066: System.out.println(size + " " + spans);
067:
068: first = new BSkipSpan(bf, this , firstSpanPage, key, val);
069: stack = new BSkipLevels(bf, firstLevelPage, this );
070: rng = new Random(System.currentTimeMillis());
071: }
072:
073: public void close() {
074: System.out.println("Closing index " + size + " and " + spans);
075: flush();
076: first = null;
077: stack = null;
078: }
079:
080: public void flush() {
081: try {
082: BlockFile.pageSeek(bf.file, skipPage);
083: bf.file.writeInt(firstSpanPage);
084: bf.file.writeInt(firstLevelPage);
085: bf.file.writeInt(size);
086: bf.file.writeInt(spans);
087:
088: } catch (IOException ioe) {
089: throw new Error();
090: }
091: }
092:
093: public void delete() throws IOException {
094: SkipLevels curLevel = stack, nextLevel;
095: while (curLevel != null) {
096: nextLevel = curLevel.levels[0];
097: curLevel.killInstance();
098: curLevel = nextLevel;
099: }
100:
101: SkipSpan curSpan = first, nextSpan;
102: while (curSpan != null) {
103: nextSpan = curSpan.next;
104: curSpan.killInstance();
105: curSpan = nextSpan;
106: }
107:
108: bf.freePage(skipPage);
109: }
110:
111: public static void init(BlockFile bf, int page, int spanSize)
112: throws IOException {
113: int firstSpan = bf.allocPage();
114: int firstLevel = bf.allocPage();
115: BlockFile.pageSeek(bf.file, page);
116: bf.file.writeInt(firstSpan);
117: bf.file.writeInt(firstLevel);
118: bf.file.writeInt(0);
119: bf.file.writeInt(1);
120: BSkipSpan.init(bf, firstSpan, spanSize);
121: BSkipLevels.init(bf, firstLevel, firstSpan, 4);
122: }
123:
124: public int maxLevels() {
125: int max = super .maxLevels();
126: int cells = (int) ((BlockFile.PAGESIZE - 8) / 4);
127: return (max > cells) ? cells : max;
128: }
129:
130: }
|