001: package com.quadcap.sql.index;
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: import java.io.PrintWriter;
043:
044: import java.util.HashSet;
045: import java.util.Iterator;
046: import java.util.Set;
047:
048: import com.quadcap.sql.file.BlockFile;
049:
050: import com.quadcap.util.Debug;
051: import com.quadcap.util.Util;
052:
053: /**
054: * A Btree implementation. Most of the real work happens in the Bnode
055: * class.
056: *
057: * @author Stan Bailes
058: */
059: public class Btree implements BIndex {
060: BlockFile file;
061: Comparator compare;
062: long rootBlock;
063: Bnode root;
064: Object lock;
065: byte[] tbuf = new byte[16];
066:
067: /**
068: * Open a btree index. Fetch the root block and create an empty tree if
069: * the block is zero, open the existing tree otherwise.
070: *
071: * @param file the (already opened) blockfile
072: * @param compare the compare function for key ordering
073: * @param rootBlock the block number of the root block of this tree
074: * @param create if true, initialize the rootblock to be empty.
075: *
076: * @exception IOException if an I/O error occurs opening or accessing
077: * the file.
078: */
079: public Btree(BlockFile file, Comparator compare, long rootBlock,
080: boolean create) throws IOException {
081: //#ifdef DEBUG
082: if (Trace.bit(0)) {
083: Debug.println("Btree(" + file + ", " + rootBlock + ", "
084: + create + ")");
085: }
086: //#endif
087: this .file = file;
088: this .lock = file.getLock();
089: this .compare = compare;
090: this .rootBlock = rootBlock;
091: this .root = getNode(rootBlock);
092: if (create) {
093: root.init(true);
094: } else {
095: root.checkMagic();
096: }
097: }
098:
099: /**
100: * Open a btree index. Fetch the root block and create an empty tree if
101: * the block is zero, open the existing tree otherwise.
102: *
103: * @param file the (already opened) blockfile
104: * @param rootBlock the block number of the root block of this tree
105: * @param create if true, initialize the rootblock to be empty.
106: *
107: * @exception IOException if an I/O error occurs opening or accessing
108: * the file.
109: */
110: public Btree(BlockFile file, long rootBlock, boolean create)
111: throws IOException {
112: this (file, Comparator.compare, rootBlock, create);
113: }
114:
115: public int size() throws IOException {
116: return getRoot().size();
117: }
118:
119: final private BCursor getMyCursor() throws IOException {
120: return BtreeCursor.get(this , true);
121: // *Don't* put in activeCursors
122: }
123:
124: /**
125: * Get the data bytes for the specified key. If the key is found,
126: * return the length of the data portion and place as many bytes
127: * as will fit in the data array. If the key isn't found, return
128: * -1.
129: */
130: public int get(byte[] key, int klen, byte[] data)
131: throws IOException {
132: synchronized (lock) {
133: BCursor cursor = getMyCursor();
134: try {
135: if (!cursor.seek(key))
136: return -1;
137: return cursor.getVal(data);
138: } finally {
139: cursor.release();
140: }
141: }
142: }
143:
144: public byte[] get(byte[] key) throws IOException {
145: synchronized (lock) {
146: BCursor cursor = getMyCursor();
147: try {
148: if (!cursor.seek(key, key.length))
149: return null;
150: int len = cursor.getValLen();
151: byte[] ret = new byte[len];
152: if (cursor.getVal(ret) != len) {
153: throw new IOException("What the hella?");
154: }
155: return ret;
156: } finally {
157: cursor.release();
158: }
159: }
160: }
161:
162: public boolean delete(byte[] key) throws IOException {
163: synchronized (lock) {
164: BCursor cursor = getMyCursor();
165: try {
166: boolean ret = cursor.seek(key, key.length);
167: if (ret)
168: ret = cursor.delete();
169: return ret;
170: } finally {
171: cursor.release();
172: }
173: }
174: }
175:
176: public boolean deleteObs(byte[] key) throws IOException {
177: synchronized (lock) {
178: //#ifdef DEBUG
179: if (Trace.bit(0)) {
180: Debug.println(0, "BTree[" + rootBlock + "].delete("
181: + Util.hexBytes(key) + ")");
182: }
183: //#endif
184: return getRoot().delete(key);
185: }
186: }
187:
188: public void set(byte[] key, byte[] val) throws IOException {
189: set(key, key.length, val, 0, val.length);
190: }
191:
192: public void insert(byte[] key, int klen, byte[] val, int off,
193: int len) throws IOException {
194: synchronized (lock) {
195: //#ifdef DEBUG
196: if (Trace.bit(0)) {
197: Debug.println("Btree[" + rootBlock + "].insert("
198: + Util.hexBytes(key, 0, klen) + ", "
199: + Util.hexBytes(val, off, len) + ")");
200: }
201: //#endif
202: getRoot().set(key, klen, val, off, len, true, false);
203: notifyUpdate(null);
204: }
205: }
206:
207: public void update(byte[] key, int klen, byte[] val, int off,
208: int len) throws IOException {
209: synchronized (lock) {
210: //#ifdef DEBUG
211: if (Trace.bit(0)) {
212: Debug.println("Btree[" + rootBlock + "].update("
213: + Util.hexBytes(key, 0, klen) + ", "
214: + Util.hexBytes(val, off, len) + ")");
215: }
216: //#endif
217: getRoot().set(key, klen, val, off, len, false, true);
218: notifyUpdate(null);
219: }
220: }
221:
222: public boolean set(byte[] key, int klen, byte[] val, int off,
223: int len) throws IOException {
224: synchronized (lock) {
225: //#ifdef DEBUG
226: if (Trace.bit(0)) {
227: Debug.println("Btree[" + rootBlock + "].set("
228: + Util.hexBytes(key) + ", "
229: + Util.hexBytes(val) + ")");
230: }
231: //#endif
232: boolean ret = getRoot().set(key, klen, val, off, len, true,
233: true);
234: notifyUpdate(null);
235: return ret;
236: }
237: }
238:
239: Bnode getNode(long ref) {
240: return new Bnode(this , ref);
241: }
242:
243: Bnode getRoot() {
244: return root;
245: }
246:
247: public long getRootBlock() {
248: return rootBlock;
249: }
250:
251: void setRoot(long ref) {
252: root = getNode(rootBlock = ref);
253: }
254:
255: /**
256: * Return a reference to the underlying <code>BlockFile</code.
257: */
258: public BlockFile getFile() {
259: return file;
260: }
261:
262: /**
263: * Return the comparator used to collate keys
264: */
265: public Comparator getComparator() {
266: return compare;
267: }
268:
269: /**
270: * Get a cursor
271: */
272: public BCursor getCursor() throws IOException {
273: return getCursor(false);
274: }
275:
276: Set activeCursors = new HashSet();
277:
278: /**
279: * Get a cursor
280: */
281: public BCursor getCursor(boolean skipSetup) throws IOException {
282: BCursor bc = null;
283: synchronized (lock) {
284: bc = BtreeCursor.get(this , skipSetup);
285: activeCursors.add(bc);
286: }
287: return bc;
288: }
289:
290: public void releaseCursor(BCursor c) {
291: synchronized (lock) {
292: try {
293: c.close();
294: } catch (Throwable t) {
295: }
296: activeCursors.remove(c);
297: }
298: }
299:
300: public void notifyUpdate(BCursor notMe) {
301: final Iterator iter = activeCursors.iterator();
302: while (iter.hasNext()) {
303: BtreeCursor bc = (BtreeCursor) iter.next();
304: if (bc != notMe)
305: bc.unsetup();
306: }
307: }
308:
309: /**
310: * Destroy this tree and free all of its resources
311: */
312: public void free() throws IOException {
313: //#ifdef DEBUG
314: if (activeCursors.size() > 0) {
315: final Iterator iter = activeCursors.iterator();
316: while (iter.hasNext()) {
317: BtreeCursor ac = (BtreeCursor) iter.next();
318: Debug.println("Active cursor: " + ac);
319: Debug
320: .println("Error detected at: "
321: + Util.stackTrace());
322: try {
323: ac.release();
324: } catch (Throwable t) {
325: }
326: }
327: throw new IOException(
328: "Btree.free() called with active cursors");
329: }
330: if (Trace.bit(0)) {
331: Debug.println("Btree[" + rootBlock + "].free()");
332: //Debug.println(Util.stackTrace());
333: }
334: //#endif
335: getRoot().free();
336: }
337:
338: //#ifdef DEBUG
339: public String toString() {
340: return "Btree[" + rootBlock + "]";
341: }
342:
343: public void display(PrintWriter w) throws IOException {
344: BCursor bc = getCursor(false);
345: try {
346: while (bc.next()) {
347: w.println("[" + new String(bc.getKey()) + "] = "
348: + new String(bc.getVal()));
349: }
350: } finally {
351: bc.release();
352: }
353:
354: }
355: //#endif
356: }
|