KickJava   Java API By Example, From Geeks To Geeks.

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


1 package org.netbeans.mdr.persistence.btreeimpl.btreeindex;
2
3 /*
4  * The contents of this file are subject to the terms of the Common Development
5  * and Distribution License (the License). You may not use this file except in
6  * compliance with the License.
7  *
8  * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
9  * or http://www.netbeans.org/cddl.txt.
10  *
11  * When distributing Covered Code, include this CDDL Header Notice in each file
12  * and include the License file at http://www.netbeans.org/cddl.txt.
13  * If applicable, add the following below the CDDL Header, with the fields
14  * enclosed by brackets [] replaced by your own identifying information:
15  * "Portions Copyrighted [year] [name of copyright owner]"
16  *
17  * The Original Software is NetBeans. The Initial Developer of the Original
18  * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
19  * Microsystems, Inc. All Rights Reserved.
20  */

21 import org.netbeans.mdr.persistence.*;
22 import java.util.*;
23 import java.text.*;
24
25 /**
26  * List view of the values associated with a single key in a MultivaluedBtree.
27  *
28  * @author Dana Bergen
29  * @version 1.0
30  */

31 /*
32  * Unlike BtreeIterator, we don't bother to unpin pages here. We can do this
33  * because BtreeListByKey is only used with BtreeMDRSource-based btrees,
34  * for which unpin is a no-op.
35  */

36 public class BtreeListByKey extends AbstractSequentialList {
37
38     private MultivaluedBtree btree;
39     private byte[] key;
40     private Object JavaDoc objectKey;
41     private int listModCounter = 0;
42     
43     BtreeListByKey(MultivaluedBtree btree, Object JavaDoc key) throws StorageException {
44
45         this.btree = btree;
46         this.objectKey = key;
47         this.key = btree.keyInfo.toBuffer(key);
48     if (this.key == null) {
49         throw new StorageBadRequestException(
50             MessageFormat.format(
51         "Invalid key type for this index: {0} received, {1} expected",
52             new Object JavaDoc[] {
53                 key.getClass().getName(),
54                 btree.keyInfo.typeName()} ));
55     }
56     }
57     
58     public int size() {
59         BtreeListByKeyIterator iterator = new BtreeListByKeyIterator(0, null);
60         while (iterator.moveForward()) {}
61     return iterator.previousIndex();
62     }
63     
64     public boolean isEmpty() {
65         return !listIterator(0).hasNext();
66     }
67     
68     public boolean add(Object JavaDoc o) {
69         ListIterator it = listIterator();
70         while (it.hasNext()) it.next();
71         it.add(o);
72         return true;
73     }
74     
75     public boolean addAll(Collection c) {
76         boolean result = false;
77         ListIterator it = listIterator();
78         Iterator cit;
79         while (it.hasNext()) it.next();
80         for (cit = c.iterator(); cit.hasNext();) {
81             try {
82                 it.add(cit.next());
83                 result = true;
84             } catch (RuntimeStorageException e) {
85             }
86         }
87         return result;
88     }
89
90     public void increaseModCount () {
91         listModCounter++;
92     }
93
94     public int hashCode() {
95         return objectKey.hashCode();
96     }
97
98     public boolean equals(Object JavaDoc o) {
99         if (o instanceof BtreeListByKey)
100             return ((BtreeListByKey) o).objectKey.equals(objectKey);
101         if (o instanceof Key)
102             return ((Key) o).objectKey.equals(objectKey);
103         return false;
104     }
105     
106     public ListIterator listIterator(int index) {
107         return new BtreeListByKeyIterator(index, null);
108     }
109     
110     ListIterator listIterator (int index, SinglevaluedIndex repos) {
111         return new BtreeListByKeyIterator(index, repos);
112     }
113     
114     // Iterator ..................................................................
115

116     public class BtreeListByKeyIterator extends Object JavaDoc
117                         implements ListIterator {
118
119         /* [TODO] Performance of next/previous operations should be improved by
120          * implementing live scan position holder that reflects all changes done over
121          * the index (for now, scan position relocations are required if the index is
122          * modifed outside the iterator and btree pages storing data related to the
123          * iterator are affected).
124          */

125                                                 
126     /* Btree scan position */
127     private SearchResult current;
128         /* Btree scan position of the leftmost entry matching the key */
129         private SearchResult first;
130     /* Index of the last item returned */
131     private int index;
132     private boolean empty;
133     private int modCount;
134         private SinglevaluedIndex repos;
135         private boolean itemAvailable = false;
136         /* true if the available item has been retrieved by next operation */
137         private boolean retrievedByNext = false;
138     
139     BtreeListByKeyIterator(int startIndex, SinglevaluedIndex repos)
140                     throws IndexOutOfBoundsException JavaDoc {
141         try {
142                 this.repos = repos;
143         btree.beginRead();
144         modCount = listModCounter;
145         index = -1;
146         current = btree.getLocation(key);
147                 first = new SearchResult (current);
148         current.entryNum--;
149         if (!current.matched) {
150             empty = true;
151         }
152                 
153                 if (startIndex < 0) throw new IndexOutOfBoundsException JavaDoc();
154
155         for (int i = 0; i < startIndex; i++) {
156                 if (!moveForward()) {
157                     throw new IndexOutOfBoundsException JavaDoc();
158                 }
159         }
160
161         } catch (StorageException e) {
162             throw new RuntimeStorageException(e);
163         } finally {
164             btree.endRead();
165         }
166     }
167
168     public Object JavaDoc next() throws NoSuchElementException {
169         if (!moveForward()) {
170             throw new NoSuchElementException();
171         }
172             itemAvailable = true;
173             retrievedByNext = true;
174         return getCurrentItem();
175     }
176
177     public Object JavaDoc previous() throws NoSuchElementException {
178
179         Object JavaDoc item;
180
181         if (index == -1) {
182             throw new NoSuchElementException();
183         }
184         item = getCurrentItem();
185         moveBackward();
186             itemAvailable = true;
187             retrievedByNext = false;
188         return item;
189     }
190
191     public boolean hasNext() {
192         try {
193             btree.beginRead();
194         checkModCount();
195                 locateCurrentItem();
196             return BtreePage.hasNext(key, current);
197         } catch (StorageException e) {
198             throw new RuntimeStorageException(e);
199         } finally {
200             btree.endRead();
201         }
202     }
203
204     public boolean hasPrevious() {
205         return (index >= 0);
206     }
207
208     private boolean moveForward() {
209
210         try {
211             btree.beginRead();
212         checkModCount();
213                 locateCurrentItem();
214             BtreePage.getNext(key, current);
215             index++;
216         return current.matched;
217         } catch (StorageException e) {
218                 
219                 e.printStackTrace ();
220                 
221             throw new RuntimeStorageException(e);
222         } finally {
223             btree.endRead();
224         }
225     }
226
227     private void moveBackward() {
228         try {
229             btree.beginRead();
230         checkModCount();
231                 locateCurrentItem();
232                 int tempEntryNum = current.entryNum;
233             BtreePage.getPrevious(key, current);
234                 if (!current.matched && (current.entryNum == tempEntryNum))
235                     current.entryNum--;
236             index--;
237         } catch (StorageException e) {
238             throw new RuntimeStorageException(e);
239         } finally {
240             btree.endRead();
241         }
242     }
243
244     private Object JavaDoc getCurrentItem() {
245         Object JavaDoc result;
246
247         try {
248         btree.beginRead();
249         checkModCount();
250                 locateCurrentItem();
251                 if (repos != null) {
252                     result = btree.dataInfo.objectFromBuffer(
253                             current.page.getData(current.entryNum), repos);
254                 }
255                 else {
256             result = btree.dataInfo.fromBuffer(
257                             current.page.getData(current.entryNum));
258                 }
259         return result;
260         } catch (StorageException e) {
261             throw new RuntimeStorageException(e);
262         } finally {
263             btree.endRead();
264         }
265     }
266         
267     public int nextIndex() {
268         return index + 1;
269     }
270
271     public int previousIndex() {
272         return index;
273     }
274
275     private void checkModCount() {
276         if (listModCounter != modCount) {
277             throw new ConcurrentModificationException("Index "
278             + btree.getName()
279                         + ", key "
280                         + objectKey
281             + " has been modified since iterator was created.");
282         }
283     }
284                 
285     public void remove() {
286             if (!itemAvailable)
287                 throw new IllegalStateException JavaDoc ();
288             checkModCount ();
289         removeItem ();
290             itemAvailable = false;
291             if (retrievedByNext)
292                 index--;
293             listModCounter++;
294             modCount = listModCounter;
295     }
296
297     public void set(Object JavaDoc o) {
298             if (!itemAvailable)
299                 throw new IllegalStateException JavaDoc ();
300             checkModCount ();
301             setItem (o);
302             listModCounter++;
303             modCount = listModCounter;
304     }
305
306     public void add(Object JavaDoc o) {
307             checkModCount ();
308         addItem (o);
309             itemAvailable = false;
310             index++;
311             listModCounter++;
312             modCount = listModCounter;
313     }
314         
315         private void setItem(Object JavaDoc o) {
316         try {
317         btree.beginWrite();
318                 locateCurrentItem();
319                 BtreePage.BtreeEntry entry = new BtreePage.BtreeEntry (key, btree.dataInfo.toBuffer (o));
320                 if (current.page instanceof ShrinkablePage) {
321                     BtreePage root = btree.pageSource.getPage(btree.rootPageId, btree);
322                     root.put(key, btree.dataInfo.toBuffer (o), Btree.REPLACE, index, current);
323                     btree.pageSource.unpinPage(root);
324                 } else {
325                     // we can call replace directly on a page (instead of tree) to achieve a better performance
326
current.page.replace(entry, current.entryNum, null);
327                 }
328         } catch (StorageException e) {
329             throw new RuntimeStorageException(e);
330         } finally {
331             btree.endWrite();
332         }
333     }
334         
335         private void removeItem() {
336         try {
337         btree.beginWrite();
338                 locateCurrentItem();
339                 SearchResult temp = new SearchResult (current);
340                 if (retrievedByNext) {
341                     BtreePage.getPrevious(key, current);
342                     if (!current.matched && (current.entryNum == temp.entryNum))
343                         current.entryNum--;
344                 } else {
345                     BtreePage.getNext(key, temp);
346                 }
347                 // delete does not merge pages, thus we can perform it directly on the page
348
temp.page.delete(temp.entryNum, temp.entryNum);
349                 if ((retrievedByNext && (index == 0)) || (!retrievedByNext && (index == -1))) {
350                     first = new SearchResult(current);
351                     BtreePage.getNext(key, first);
352                 }
353         } catch (StorageException e) {
354             throw new RuntimeStorageException(e);
355         } finally {
356             btree.endWrite();
357         }
358     }
359         
360         private void addItem(Object JavaDoc o) {
361         try {
362         btree.beginWrite();
363                 locateCurrentItem();
364                 BtreePage root = btree.pageSource.getPage(btree.rootPageId, btree);
365                 root.put(key, btree.dataInfo.toBuffer (o), Btree.ADD, index + 1, current);
366                 btree.pageSource.unpinPage(root);
367                 if (index == -1) {
368                     first = new SearchResult(current);
369                 }
370             // BtreePage.getNext(key, current);
371
} catch (StorageException e) {
372             throw new RuntimeStorageException(e);
373         } finally {
374             btree.endWrite();
375         }
376     }
377         
378         private void locateCurrentItem() throws StorageException {
379             SearchResult res = first.page.searchPage(key, first.entryNum);
380             if ((first.entryNum != res.entryNum) || (first.page != res.page)) {
381                 first = res;
382                 current = new SearchResult (first);
383                 if (index == -1) {
384                     current.entryNum--;
385                 } else {
386                     first.page.findNth(current, key, index, false);
387                 }
388             } else {
389                 if ((index > -1) && (current.page.compare(key, current.entryNum) != EntryTypeInfo.EQUAL)) {
390                     current = new SearchResult (first);
391                     first.page.findNth(current, key, index, false);
392                 }
393             }
394         }
395         
396     } // BtreeListByKeyIterator class
397

398     /**
399      * This class is used to query for BtreeListByKey instances in hashtables.
400      */

401     static class Key {
402         
403         private Object JavaDoc objectKey;
404         
405         Key (Object JavaDoc key) {
406             objectKey = key;
407         }
408         
409         public int hashCode() {
410             return objectKey.hashCode();
411         }
412
413         public boolean equals(Object JavaDoc o) {
414             if (o instanceof BtreeListByKey)
415                 return ((BtreeListByKey) o).objectKey.equals(objectKey);
416             if (o instanceof Key)
417                 return ((Key) o).objectKey.equals(objectKey);
418             return false;
419         }
420         
421     } // Key class
422

423 }
424
Popular Tags