Btree


1   package com.quadcap.sql.index;
2   
3   /* Copyright 1997 - 2003 Quadcap Software.  All rights reserved.
4    *
5    * This software is distributed under the Quadcap Free Software License.
6    * This software may be used or modified for any purpose, personal or
7    * commercial.  Open Source redistributions are permitted.  Commercial
8    * redistribution of larger works derived from, or works which bundle
9    * this software requires a "Commercial Redistribution License"; see
10   * http://www.quadcap.com/purchase.
11   *
12   * Redistributions qualify as "Open Source" under  one of the following terms:
13   *   
14   *    Redistributions are made at no charge beyond the reasonable cost of
15   *    materials and delivery.
16   *
17   *    Redistributions are accompanied by a copy of the Source Code or by an
18   *    irrevocable offer to provide a copy of the Source Code for up to three
19   *    years at the cost of materials and delivery.  Such redistributions
20   *    must allow further use, modification, and redistribution of the Source
21   *    Code under substantially the same terms as this license.
22   *
23   * Redistributions of source code must retain the copyright notices as they
24   * appear in each source code file, these license terms, and the
25   * disclaimer/limitation of liability set forth as paragraph 6 below.
26   *
27   * Redistributions in binary form must reproduce this Copyright Notice,
28   * these license terms, and the disclaimer/limitation of liability set
29   * forth as paragraph 6 below, in the documentation and/or other materials
30   * provided with the distribution.
31   *
32   * The Software is provided on an "AS IS" basis.  No warranty is
33   * provided that the Software is free of defects, or fit for a
34   * particular purpose.  
35   *
36   * Limitation of Liability. Quadcap Software shall not be liable
37   * for any damages suffered by the Licensee or any third party resulting
38   * from use of the Software.
39   */
40  
41  import java.io.IOException  ;
42  import java.io.PrintWriter  ;
43  
44  import java.util.HashSet  ;
45  import java.util.Iterator  ;
46  import java.util.Set  ;
47  
48  import com.quadcap.sql.file.BlockFile;
49  
50  import com.quadcap.util.Debug;
51  import com.quadcap.util.Util;
52  
53  /**
54   * A Btree implementation.  Most of the real work happens in the Bnode
55   * class.
56   *
57   * @author Stan Bailes
58   */
59  public class Btree implements BIndex {
60      BlockFile       file;
61      Comparator      compare;
62      long        rootBlock;
63      Bnode       root;
64      Object                lock;
65      byte[]              tbuf = new byte[16];
66  
67      /**
68       * Open a btree index.  Fetch the root block and create an empty tree if
69       * the block is zero, open the existing tree otherwise.
70       *
71       * @param file the (already opened) blockfile
72       * @param compare the compare function for key ordering
73       * @param rootBlock the block number of the root block of this tree
74       * @param create if true, initialize the rootblock to be empty.
75       *          
76       * @exception IOException if an I/O error occurs opening or accessing
77       *          the file.
78       */
79      public Btree(BlockFile file, Comparator compare,
80           long rootBlock, boolean create)
81      throws IOException  
82      {
83      //#ifdef DEBUG
84      if (Trace.bit(0)) {
85          Debug.println("Btree(" + file + ", " + rootBlock + ", " +
86                create + ")");
87      }
88      //#endif
89      this.file = file;
90          this.lock = file.getLock();
91      this.compare = compare;
92      this.rootBlock = rootBlock;
93      this.root = getNode(rootBlock);
94      if (create) {
95          root.init(true);
96      } else {
97          root.checkMagic();
98      }
99      }
100 
101     /**
102      * Open a btree index.  Fetch the root block and create an empty tree if
103      * the block is zero, open the existing tree otherwise.
104      *
105      * @param file the (already opened) blockfile
106      * @param rootBlock the block number of the root block of this tree
107      * @param create if true, initialize the rootblock to be empty.
108      *          
109      * @exception IOException if an I/O error occurs opening or accessing
110      *          the file.
111      */
112     public Btree(BlockFile file, long rootBlock, boolean create)
113     throws IOException  
114     {
115     this(file, Comparator.compare, rootBlock, create);
116     }
117 
118     public int size() throws IOException   {
119         return getRoot().size();
120     }
121 
122     final private BCursor getMyCursor() throws IOException   {
123         return BtreeCursor.get(this, true);
124         // *Don't* put in activeCursors
125     }
126     
127     /**
128      * Get the data bytes for the specified key.  If the key is found,
129      * return the length of the data portion and place as many bytes
130      * as will fit in the data array.  If the key isn't found, return
131      * -1.
132      */
133     public int get(byte[] key, int klen, byte[] data) throws IOException   {
134         synchronized (lock) {
135             BCursor cursor = getMyCursor();
136             try {
137                 if (!cursor.seek(key)) return -1;
138                 return cursor.getVal(data);
139             } finally {
140                 cursor.release();
141             }
142         }
143     }
144 
145     public byte[] get(byte[] key) throws IOException   {
146         synchronized (lock) {
147             BCursor cursor = getMyCursor();
148             try {
149                 if (!cursor.seek(key, key.length)) 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) ret = cursor.delete();
168                 return ret;
169             } finally {
170                 cursor.release();
171             }
172         }
173     }
174 
175     public boolean deleteObs(byte[] key) throws IOException   {
176         synchronized (lock) {
177             //#ifdef DEBUG
178             if (Trace.bit(0)) {
179                 Debug.println(0, "BTree[" + rootBlock + "].delete(" +
180                               Util.hexBytes(key) + ")");
181             }
182             //#endif
183             return getRoot().delete(key);
184         }
185     }
186 
187     public void set(byte[] key, byte[] val) throws IOException   {
188         set(key, key.length, val, 0, val.length);
189     }
190 
191     public void insert(byte[] key, int klen,
192                        byte[] val, int off, int len) throws IOException   {
193         synchronized (lock) {
194             //#ifdef DEBUG
195             if (Trace.bit(0)) {
196                 Debug.println("Btree[" + rootBlock + "].insert(" +
197                               Util.hexBytes(key, 0, klen) + ", " +
198                               Util.hexBytes(val, off, len) + ")");
199             }
200             //#endif
201             getRoot().set(key, klen, val, off, len, true, false);
202             notifyUpdate(null);
203         }
204     }
205     
206     public void update(byte[] key, int klen,
207                        byte[] val, int off, int len) throws IOException   {
208         synchronized (lock) {
209             //#ifdef DEBUG
210             if (Trace.bit(0)) {
211                 Debug.println("Btree[" + rootBlock + "].update(" +
212                               Util.hexBytes(key, 0, klen) + ", " +
213                               Util.hexBytes(val, off, len) + ")");
214             }
215             //#endif
216             getRoot().set(key, klen, val, off, len, false, true);
217             notifyUpdate(null);
218         }
219     }
220     
221     public boolean set(byte[] key, int klen,
222                        byte[] val, int off, int len) throws IOException   {
223         synchronized (lock) {
224             //#ifdef DEBUG
225             if (Trace.bit(0)) {
226                 Debug.println("Btree[" + rootBlock + "].set(" +
227                               Util.hexBytes(key) + ", " +
228                               Util.hexBytes(val) + ")");
229             }
230             //#endif
231             boolean ret = getRoot().set(key, klen, val, off, len, true, true);
232             notifyUpdate(null);
233             return ret;
234         }
235     }
236     
237     Bnode getNode(long ref) {
238     return new Bnode(this, ref);
239     }
240 
241     Bnode getRoot() { return root; }
242 
243     public long getRootBlock() {
244     return rootBlock;
245     }
246 
247     void setRoot(long ref) {
248     root = getNode(rootBlock = ref);
249     }
250 
251     /**
252      * Return a reference to the underlying <code>BlockFile</code.
253      */
254     public BlockFile getFile() { return file; }
255 
256     /**
257      * Return the comparator used to collate keys
258      */
259     public Comparator getComparator() {
260     return compare;
261     }
262 
263     /**
264      * Get a cursor
265      */
266     public BCursor getCursor() throws IOException   {
267         return getCursor(false);
268     }
269 
270     Set   activeCursors = new HashSet  ();
271     
272     /**
273      * Get a cursor
274      */
275     public BCursor getCursor(boolean skipSetup) throws IOException   {
276         BCursor bc = null;
277         synchronized (lock) {
278             bc = BtreeCursor.get(this, skipSetup);
279             activeCursors.add(bc);
280         }
281         return bc;
282     }
283 
284     public void releaseCursor(BCursor c) {
285         synchronized (lock) {
286             try {
287                 c.close();
288             } catch (Throwable   t) {}
289             activeCursors.remove(c);
290         }
291     }
292 
293     public void notifyUpdate(BCursor notMe) {
294         final Iterator   iter = activeCursors.iterator();
295         while (iter.hasNext()) {
296             BtreeCursor bc = (BtreeCursor)iter.next();
297             if (bc != notMe) bc.unsetup();
298         }
299     }
300     
301     /**
302      * Destroy this tree and free all of its resources
303      */
304     public void free() throws IOException   {
305     //#ifdef DEBUG
306         if (activeCursors.size() > 0) {
307             final Iterator   iter = activeCursors.iterator();
308             while (iter.hasNext()) {
309                 BtreeCursor ac = (BtreeCursor)iter.next();
310                 Debug.println("Active cursor: " + ac);
311                 Debug.println("Error detected at: " + Util.stackTrace());
312                 try {
313                     ac.release();
314                 } catch (Throwable   t) {
315                 }
316             }
317             throw new IOException  ("Btree.free() called with active cursors");
318         }
319     if (Trace.bit(0)) {
320         Debug.println("Btree[" + rootBlock + "].free()");
321         //Debug.println(Util.stackTrace());
322     }
323     //#endif
324     getRoot().free();
325     }
326 
327     //#ifdef DEBUG
328     public String   toString() {
329         return "Btree[" + rootBlock + "]";
330     }
331 
332     public void display(PrintWriter   w) throws IOException   {
333         BCursor bc = getCursor(false);
334         try {
335             while (bc.next()) {
336                 w.println("[" + new String  (bc.getKey()) + "] = " +
337                           new String  (bc.getVal()));
338             }
339         } finally {
340             bc.release();
341         }
342         
343     }
344     //#endif
345 }
346 
347
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags