Java > Open Source Codes > org > netbeans > mdr > persistence > btreeimpl > btreeindex > Btree


1 /*
2  * The contents of this file are subject to the terms of the Common Development
3  * and Distribution License (the License). You may not use this file except in
4  * compliance with the License.
5  *
6  * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7  * or http://www.netbeans.org/cddl.txt.
8  *
9  * When distributing Covered Code, include this CDDL Header Notice in each file
10  * and include the License file at http://www.netbeans.org/cddl.txt.
11  * If applicable, add the following below the CDDL Header, with the fields
12  * enclosed by brackets [] replaced by your own identifying information:
13  * "Portions Copyrighted [year] [name of copyright owner]"
14  *
15  * The Original Software is NetBeans. The Initial Developer of the Original
16  * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17  * Microsystems, Inc. All Rights Reserved.
18  */
19 package org.netbeans.mdr.persistence.btreeimpl.btreeindex;
20
21 import org.netbeans.mdr.persistence.*;
22 import org.netbeans.mdr.persistence.btreeimpl.btreestorage.*; /* for BtreeMDRSource */
23 import java.util.*;
24 import java.io.*;
25 import java.text.*;
26
27 /**
28  * Btree index implementation. This is the top of the
29  * Btree hierarchy which implements the
30  * org.netbeans.mdr.persistence.Index interface hierarchy. This
31  * abstract class and its subclasses contain the persistent state
32  * of a Btree and the public interface methods for accessing it.
33  * The main logic for searching and updating a
34  * Btree is contained in the BtreePage class.
35  *
36  * <p>The btreeindex package is as much as possible independent of the
37  * btreestorage implementation. However, there are a few dependencies which
38  * would need to be addressed if this code was to be used with some other
39  * storage mechanism. The main one is the need, when instantiating a
40  * that was retrieved from the repository via Btree.read(), to instantiate the
41  * specific BtreePageSource implementation that this btree will use. The MOFID
42  * class also comes from the btreestorage package, and the Converter routines
43  * from that package are used to convert integers to byte arrays and back.
44  *
45  * @author Dana Bergen
46  * @version 1.0
47  */
48 public abstract class Btree extends Object implements Index, Streamable,
49                             StorageClient {
50
51     protected BtreePageSource pageSource;
52     protected BtreeStorage storage; /* only used for MDR based btree */
53     protected Storage.EntryType keyType;
54     protected Storage.EntryType dataType;
55     protected String name;
56
57     protected EntryTypeInfo keyInfo;
58     protected EntryTypeInfo dataInfo;
59     protected int dataLength;
60     protected int pageIdLength;
61     protected int pageSize;
62     protected byte[] rootPageId;
63
64     protected boolean uniqueKeys;
65     protected boolean uniqueValues;
66     protected boolean hasBigKeys;
67
68     /*
69      * Operation types
70      */
71     static final byte ADD = 0;
72     static final byte REPLACE = 1;
73     static final byte REPLACE_IF_EXISTS = 2;
74     /*
75      * Status of current update operation. We can get away with having these
76      * globals because updates are single-threaded.
77      */
78     boolean failed;
79     boolean replaced;
80
81     /*
82      * Synchronization (single writer, multiple readers)
83      */
84     private int activeReaders = 0;
85     private int activeWriters = 0;
86     private int waitingWriters = 0;
87     int modCount = 0;
88
89     public Btree(String name, Storage.EntryType keyType,
90                      Storage.EntryType dataType,
91                  BtreePageSource pageSource)
92                  throws StorageException {
93
94     this.keyType = keyType;
95     this.dataType = dataType;
96     this.name = name;
97     this.pageSource = pageSource;
98     pageSize = pageSource.getPageSize();
99         storage = pageSource.getStorage ();
100
101     init();
102     }
103
104     /*
105      * To be called after attributes have been populated by the
106      * constructor or read().
107      */
108     protected void init() throws StorageException {
109
110         BtreePage root;
111
112         if (keyInfo != null) {
113         /* This object was found in cache and is already initialized */
114         return;
115     }
116
117     keyInfo = EntryTypeInfo.getEntryTypeInfo(keyType, storage);
118     dataInfo = EntryTypeInfo.getEntryTypeInfo(dataType, storage);
119     if (keyInfo == null) {
120         throw new StorageBadRequestException(
121             MessageFormat.format(
122             "Invalid index key type: ",
123             new Object [] {keyType}));
124     }
125     if (dataInfo == null) {
126         throw new StorageBadRequestException(
127             MessageFormat.format(
128             "Invalid index data type: ",
129             new Object [] {dataType}));
130     }
131         
132         // this value is useless in case dataType == Storage.EntryType.STRING
133 dataLength = dataInfo.getLength();
134
135     pageIdLength = pageSource.getPageIdLength();
136
137     if (rootPageId == null) {
138         /*
139          * There are three possible scenarios: this is a new file-based
140          * btree; this is a new MDR object btree; or, this is an existing
141          * file-based btree. In the last case, getRootPage() will
142          * return the already-existing root page. In the other cases, it
143          * will return a newly-constructed page.
144          */
145         root = pageSource.getRootPage(this);
146         rootPageId = new byte[pageIdLength];
147         System.arraycopy(root.pageId, 0, rootPageId, 0, root.pageId.length);
148         root.makeRoot();
149         } else {
150         /* This is an existing MDR object btree. */
151         root = pageSource.getPage(rootPageId, this);
152     }
153
154     if (pageSource.isNoPage(root.nextPage)) {
155         hasBigKeys = false;
156     } else {
157         hasBigKeys = true;
158     }
159     pageSource.unpinPage(root);
160     }
161
162     /*
163      * Streamable Interface methods. These are only used for Btree's
164      * stored as MDR objects (when pageSource is a BtreeMDRSource).
165      */
166
167     public Btree() {
168     }
169
170     /**
171      * Write the state of this Btree to the OutputStream.
172      *
173      * @param outputStream OutputStream
174      */
175     public void write(OutputStream outputStream) throws StorageException {
176
177     /*
178      * We don't need synchronization because this will only happen
179      * at commit, or when the object is known to not be in use.
180      */
181     try {
182         DataOutputStream out = new DataOutputStream(outputStream);
183
184         byte[] n = name.getBytes();
185         out.writeShort(n.length);
186         out.write(n);
187         out.writeByte(keyType.encode());
188         out.writeByte(dataType.encode());
189         out.writeBoolean(uniqueValues);
190         out.writeInt(pageSize);
191         out.write(rootPageId);
192     } catch (IOException e) {
193         throw new StorageIOException(e);
194     }
195     }
196
197     /**
198      * Populate this Btree from the InputStream. The Storage reference will have
199      * already been set up in setStorage.
200      *
201      * @param inputStream InputStream
202      */
203     public void read(InputStream inputStream) throws StorageException {
204
205     try {
206         DataInputStream in = new DataInputStream(inputStream);
207
208         short length = in.readShort();
209         byte[] n = new byte[length];
210         in.read(n, 0, length);
211         name = new String (n).intern();
212
213         keyType = Storage.EntryType.decodeEntryType(in.readByte());
214         dataType = Storage.EntryType.decodeEntryType(in.readByte());
215         uniqueValues = in.readBoolean();
216         pageSize = in.readInt();
217
218         pageSource = new BtreeMDRSource(storage, pageSize);
219
220         rootPageId = new byte[pageSource.getPageIdLength()];
221         in.read(rootPageId, 0, rootPageId.length);
222     } catch (IOException e) {
223         throw new StorageIOException(e);
224     }
225
226     /* Now that we've read everything in, do the common initialization */
227     init();
228     }
229
230     public void setStorage(Storage storage) {
231         this.storage = (BtreeStorage) storage;
232     }
233     /*
234      *
235      * Index interface methods
236      *
237      */
238
239     /** Returns the type of keys in index.
240      * @return
241      * @throws StorageException
242      */
243     public Storage.EntryType getKeyType() {
244         return keyType;
245     }
246
247     /** Returns the type of values indexed by this index.
248      * @return
249      * @throws StorageException
250      */
251     public Storage.EntryType getValueType() {
252         return dataType;
253     }
254
255     /** Returns the unique name of the index in the Storage.
256      * @return
257      * @throws StorageException
258      */
259     public String getName() {
260         return name;
261     }
262
263     /** Returns a set view of the keys contained in this index.
264      * Returned set is read only and may not be modified.
265      * @return keys contained in this index
266      * @throws StorageException
267      */
268     public Set keySet() throws StorageException {
269         return new BtreeKeySet(this);
270     }
271
272     /**
273      * Add a new entry to the index.
274      *
275      * @param key key to insert
276      * @param data data associated with key
277      *
278      * @exception StorageBadRequestException
279      * If key or data are incorrect type, or if
280      * the insert would violate the constraints of this index
281      * @exception StorageException
282      * If a problem was encountered accessing storage
283      */
284     public void add(Object key, Object data) throws StorageException {
285         beginWrite();
286     try {
287         failed = false;
288         btreePut(key, data, ADD, 0);
289
290         if (failed) {
291         String message;
292         if (uniqueKeys) {
293             message =
294             MessageFormat.format("Key {0} already exists in index",
295                 new Object [] {key});
296         } else {
297             message =
298             MessageFormat.format(
299                 "Key-value pair {0}, {1} already exists in index",
300                 new Object [] {key, data});
301         }
302         throw new StorageBadRequestException(message);
303         }
304     } finally {
305         endWrite();
306     }
307     }
308
309     /**
310      * Remove all entries associated with the specified key.
311      *
312      * @param key key for entry to be removed
313      *
314      * @return true if a matching entry was found
315      *
316      * @exception StorageException If there was a problem reading or
317      * writing pages
318      */
319     public boolean remove(Object key) throws StorageException {
320
321         beginWrite();
322     try {
323         boolean result;
324         byte[] keyBuffer;
325
326         if ((keyBuffer = keyInfo.toBuffer(key)) == null) {
327         throw new StorageBadRequestException(
328             MessageFormat.format(
329             "Invalid key type for this index: {0} received, {1} expected",
330                 new Object [] {
331                 key.getClass().getName(),
332                 keyInfo.typeName()} ));
333         }
334         BtreePage root = pageSource.getPage(rootPageId, this);
335         result = root.remove(keyBuffer);
336         pageSource.unpinPage(root);
337         return result;
338     } finally {
339         endWrite();
340     }
341     }
342
343     /*
344      *
345      * Common support functions
346      *
347      */
348
349     /**
350      * Returns the right kind of BtreePage for this btree.
351      */
352     public BtreePage pageFactory() {
353
354         if (!dataInfo.isFixedLength())
355             return new VarRecordPage();
356     if (keyInfo.isFixedLength()) {
357             if ((keyInfo instanceof MOFIDInfo) && (dataInfo instanceof MOFIDInfo)) {
358                 return new ShrinkablePage ();
359             } else {
360                 return new FixedKeyPage();
361             }
362     } else {
363         return new VarKeyPage();
364     }
365     }
366     
367     /**
368      * Returns the tree's first record location, for initializing an Iterator.
369      *
370      * @return SearchResult pointing to first record
371      */
372     SearchResult getFirst() throws StorageException {
373         SearchResult result;
374
375         BtreePage root = pageSource.getPage(rootPageId, this);
376     result = root.getFirst();
377     if (result.page != root) {
378         pageSource.unpinPage(root);
379     }
380     return result;
381     }
382
383     /**
384      * Returns the location of the first entry for the specified key, for
385      * initializing a BtreeListbyKeyIterator.
386      *
387      * @return SearchResult pointing to first record matching key
388      */
389     SearchResult getLocation(byte[] key) throws StorageException {
390         SearchResult result;
391
392         BtreePage root = pageSource.getPage(rootPageId, this);
393     result = root.getLocation(key);
394     if (result.page != root) {
395         pageSource.unpinPage(root);
396     }
397     return result;
398     }
399
400     protected void btreePut(Object key, Object data, byte operation, int index)
401                             throws StorageException {
402
403     byte[] keyBuffer;
404     byte[] dataBuffer;
405
406     if ((keyBuffer = keyInfo.toBuffer(key)) == null) {
407         throw new StorageBadRequestException(
408             MessageFormat.format(
409         "Invalid key type for this index: {0} received, {1} expected",
410             new Object [] {
411                 key.getClass().getName(),
412                 keyInfo.typeName()} ));
413     }
414
415     if ((dataBuffer = dataInfo.toBuffer(data)) == null) {
416         throw new StorageBadRequestException(
417             MessageFormat.format(
418         "Invalid data type for this index: {0} received, {1} expected",
419             new Object [] {
420                 data.getClass().getName(),
421                 dataInfo.typeName()} ));
422     }
423
424     BtreePage root = pageSource.getPage(rootPageId, this);
425     root.put(keyBuffer, dataBuffer, operation, index);
426     pageSource.unpinPage(root);
427     }
428
429     /**
430      * Returns the number of elements in this btree
431      */
432     int countRecords() throws StorageException {
433
434         SearchResult location;
435         BtreePage savePage;
436     int count = 0;
437
438     location = getFirst();
439     if (!location.matched) {
440         return 0;
441     }
442
443     do {
444         savePage = location.page;
445         BtreePage.getNext((byte[]) null, location);
446         count++;
447         if ((savePage != null) && (savePage != location.page)) {
448             pageSource.unpinPage(savePage);
449         }
450     } while (location.matched);
451
452     if (location.page != null) {
453         pageSource.unpinPage(location.page);
454     }
455     return count;
456     }
457
458     boolean hasBigKeys() {
459     return hasBigKeys;
460     }
461
462     void setHasBigKeys() {
463         hasBigKeys = true;
464     }
465
466     void unsetHasBigKeys() {
467         hasBigKeys = false;
468     }
469
470     /*
471      * Synchronization methods
472      */
473     private boolean allowReader() {
474         return waitingWriters == 0 && activeWriters == 0;
475     }
476
477     private boolean allowWriter() {
478         return activeReaders == 0 && activeWriters == 0;
479     }
480
481     protected synchronized void beginRead() {
482     while (!allowReader()) {
483         try { wait(); } catch (InterruptedException e) {}
484     }
485     activeReaders++;
486     }
487
488     protected synchronized void endRead() {
489         activeReaders--;
490     notifyAll();
491     }
492         
493     protected synchronized void beginWrite() {
494         waitingWriters++;
495     while (!allowWriter()) {
496         try { wait(); } catch (InterruptedException e) {}
497     }
498     waitingWriters--;
499     activeWriters++;
500     }
501
502     protected synchronized void endWrite() {
503         activeWriters--;
504     modCount++;
505     notifyAll();
506     }
507
508     /*
509      * For debugging.
510      */
511     /**
512      * Print the contents of the btree for debugging purposes.
513      *
514      * @param out PrintWriter to print btree to
515      */
516     public void dumpTree(PrintWriter out) throws StorageException {
517
518     BtreePage root = pageSource.getPage(rootPageId, this);
519     root.dumpTree(out);
520     pageSource.unpinPage(root);
521     }
522
523     public TreeMetrics computeMetrics() throws StorageException {
524         BtreePage root = pageSource.getPage(rootPageId, this);
525     TreeMetrics m = root.computeMetrics();
526     pageSource.unpinPage(root);
527         return m;
528     }
529     
530     /**
531      * Check the btree for consistency, for testing and debugging.
532      *
533      * @param out PrintWriter to print results to
534      *
535      * @return number of errors encountered
536      */
537     public int consistencyCheck(PrintWriter out) throws StorageException {
538         int result;
539
540     BtreePage root = pageSource.getPage(rootPageId, this);
541     result = root.consistencyCheck(out);
542     pageSource.unpinPage(root);
543     return result;
544     }
545
546 }
547

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags