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:
033: import net.metanotion.io.RandomAccessInterface;
034: import net.metanotion.io.Serializer;
035: import net.metanotion.io.block.BlockFile;
036: import net.metanotion.io.data.NullBytes;
037: import net.metanotion.util.skiplist.SkipList;
038: import net.metanotion.util.skiplist.SkipSpan;
039:
040: public class BSkipSpan extends SkipSpan {
041:
042: protected BlockFile bf;
043: protected int page;
044: protected int overflowPage;
045:
046: protected int prevPage;
047: protected int nextPage;
048: protected Serializer keySer;
049: protected Serializer valSer;
050:
051: public static void init(BlockFile bf, int page, int spanSize)
052: throws IOException {
053: BlockFile.pageSeek(bf.file, page);
054: bf.file.writeInt(0);
055: bf.file.writeInt(0);
056: bf.file.writeInt(0);
057: bf.file.writeShort((short) spanSize);
058: bf.file.writeShort(0);
059: }
060:
061: public SkipSpan newInstance(SkipList sl) {
062: try {
063: int newPage = bf.allocPage();
064: init(bf, newPage, bf.spanSize);
065: return new BSkipSpan(bf, (BSkipList) sl, newPage, keySer,
066: valSer);
067: } catch (IOException ioe) {
068: throw new Error();
069: }
070: }
071:
072: public void killInstance() {
073: try {
074: int curPage = overflowPage;
075: int next;
076: while (curPage != 0) {
077: BlockFile.pageSeek(bf.file, curPage);
078: next = bf.file.readInt();
079: bf.freePage(curPage);
080: curPage = next;
081: }
082: bf.freePage(page);
083: } catch (IOException ioe) {
084: throw new Error();
085: }
086: }
087:
088: public void flush() {
089: try {
090: BlockFile.pageSeek(bf.file, page);
091: bf.file.writeInt(overflowPage);
092: bf.file.writeInt((prev != null) ? ((BSkipSpan) prev).page
093: : 0);
094: bf.file.writeInt((next != null) ? ((BSkipSpan) next).page
095: : 0);
096: bf.file.writeShort((short) keys.length);
097: bf.file.writeShort((short) nKeys);
098:
099: int ksz, vsz;
100: int curPage = this .page;
101: int[] curNextPage = new int[1];
102: curNextPage[0] = this .overflowPage;
103: int[] pageCounter = new int[1];
104: pageCounter[0] = 16;
105: byte[] keyData;
106: byte[] valData;
107:
108: for (int i = 0; i < nKeys; i++) {
109: if ((pageCounter[0] + 4) > BlockFile.PAGESIZE) {
110: if (curNextPage[0] == 0) {
111: curNextPage[0] = bf.allocPage();
112: BlockFile.pageSeek(bf.file, curNextPage[0]);
113: bf.file.writeInt(0);
114: BlockFile.pageSeek(bf.file, curPage);
115: bf.file.writeInt(curNextPage[0]);
116: }
117: BlockFile.pageSeek(bf.file, curNextPage[0]);
118: curPage = curNextPage[0];
119: curNextPage[0] = bf.file.readInt();
120: pageCounter[0] = 4;
121: }
122: keyData = this .keySer.getBytes(keys[i]);
123: valData = this .valSer.getBytes(vals[i]);
124: pageCounter[0] += 4;
125: bf.file.writeShort(keyData.length);
126: bf.file.writeShort(valData.length);
127: curPage = bf.writeMultiPageData(keyData, curPage,
128: pageCounter, curNextPage);
129: curPage = bf.writeMultiPageData(valData, curPage,
130: pageCounter, curNextPage);
131: }
132: BlockFile.pageSeek(bf.file, this .page);
133: this .overflowPage = bf.file.readInt();
134: } catch (IOException ioe) {
135: throw new Error();
136: }
137: }
138:
139: private static void load(BSkipSpan bss, BlockFile bf,
140: BSkipList bsl, int spanPage, Serializer key, Serializer val)
141: throws IOException {
142: bss.bf = bf;
143: bss.page = spanPage;
144: bss.keySer = key;
145: bss.valSer = val;
146:
147: bsl.spanHash.put(new Integer(spanPage), bss);
148:
149: BlockFile.pageSeek(bf.file, spanPage);
150:
151: bss.overflowPage = bf.file.readInt();
152: bss.prevPage = bf.file.readInt();
153: bss.nextPage = bf.file.readInt();
154: int sz = bf.file.readShort();
155: bss.nKeys = bf.file.readShort();
156:
157: bss.keys = new Comparable[sz];
158: bss.vals = new Object[sz];
159:
160: int ksz, vsz;
161: int curPage = spanPage;
162: int[] curNextPage = new int[1];
163: curNextPage[0] = bss.overflowPage;
164: int[] pageCounter = new int[1];
165: pageCounter[0] = 16;
166: // System.out.println("Span Load " + sz + " nKeys " + nKeys + " page " + curPage);
167: for (int i = 0; i < bss.nKeys; i++) {
168: if ((pageCounter[0] + 4) > BlockFile.PAGESIZE) {
169: BlockFile.pageSeek(bf.file, curNextPage[0]);
170: curPage = curNextPage[0];
171: curNextPage[0] = bf.file.readInt();
172: pageCounter[0] = 4;
173: }
174: ksz = bf.file.readShort();
175: vsz = bf.file.readShort();
176: pageCounter[0] += 4;
177: byte[] k = new byte[ksz];
178: byte[] v = new byte[vsz];
179: curPage = bf.readMultiPageData(k, curPage, pageCounter,
180: curNextPage);
181: curPage = bf.readMultiPageData(v, curPage, pageCounter,
182: curNextPage);
183: // System.out.println("i=" + i + ", Page " + curPage + ", offset " + pageCounter[0] + " ksz " + ksz + " vsz " + vsz);
184: bss.keys[i] = (Comparable) bss.keySer.construct(k);
185: bss.vals[i] = bss.valSer.construct(v);
186: }
187:
188: }
189:
190: protected BSkipSpan() {
191: }
192:
193: public BSkipSpan(BlockFile bf, BSkipList bsl, int spanPage,
194: Serializer key, Serializer val) throws IOException {
195: BSkipSpan.load(this , bf, bsl, spanPage, key, val);
196: this .next = null;
197: this .prev = null;
198:
199: BSkipSpan bss = this ;
200: BSkipSpan temp;
201: int np = nextPage;
202: while (np != 0) {
203: temp = (BSkipSpan) bsl.spanHash.get(new Integer(np));
204: if (temp != null) {
205: bss.next = temp;
206: break;
207: }
208: bss.next = new BSkipSpan();
209: bss.next.next = null;
210: bss.next.prev = bss;
211: bss = (BSkipSpan) bss.next;
212:
213: BSkipSpan.load(bss, bf, bsl, np, key, val);
214: np = bss.nextPage;
215: }
216:
217: bss = this ;
218: np = prevPage;
219: while (np != 0) {
220: temp = (BSkipSpan) bsl.spanHash.get(new Integer(np));
221: if (temp != null) {
222: bss.next = temp;
223: break;
224: }
225: bss.prev = new BSkipSpan();
226: bss.prev.next = bss;
227: bss.prev.prev = null;
228: bss = (BSkipSpan) bss.prev;
229:
230: BSkipSpan.load(bss, bf, bsl, np, key, val);
231: np = bss.prevPage;
232: }
233: }
234: }
|