KickJava   Java API By Example, From Geeks To Geeks.

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


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 import org.netbeans.mdr.persistence.*;
21 import java.io.*;
22
23 /**
24  * These pages contain keys which are too big to be handled normally.
25  * Each BigKeyPage contains a single key or a portion of a single key,
26  * and possibly the data associated with the key. All of the BigKeyPages
27  * are in a single chain attached to the root (i.e., root.nextPage points to
28  * the first BigKeyPage). They are maintained in key order.
29  *
30  * The first page for a given key contains the full key length in keyLength.
31  * If the key doesn't fit on a single page it is continued on subsequent pages.
32  * If the data fits completely on the same page as the last portion of the key,
33  * it is put there; otherwise, it is put on a separate page.
34  *
35  * When a big key record gets deleted, the pages are removed from the chain
36  * and the space is never reused.
37  *
38  * This is not a very efficient implementation because we don't really expect
39  * it to be used (it gets used if a key is longer than 670 bytes).
40  *
41  * @author Dana Bergen
42  * @version 1.0
43  */
44 public class BigKeyPage extends BtreePage {
45
46     private int keyLength;
47
48     public BigKeyPage() {}
49
50     /**
51      * Initialize a newly-instantiated or recycled BigKeyPage. Note that the
52      * isNew parameter pertains to whether a new page is being added to the
53      * btree, not to whether this BtreePage object is new or recycled.
54      *
55      * @param btree btree to which this page belongs
56      * @param pageId page ID in byte array
57      * @param pageBuffer page buffer
58      * @param isNew is this page new to the btree
59      */
60     public void init(Btree btree, byte[] pageId, byte[] pageBuffer,
61                     boolean isNew) throws StorageException {
62
63     if (initialized) {
64         /* This page was found in cache and doesn't need initialization */
65         return;
66     }
67
68         super.init(btree, pageId, pageBuffer, isNew);
69     if (isNew) {
70         keyLength = 0;
71         flags = 0;
72     } else {
73         /* keyLength is stored in the same slot as freeStart which
74          * is not used by BigKeyPage
75          */
76         keyLength = freeStart;
77     }
78     }
79
80     /**
81      * Write BigKeyPage header data to the page buffer.
82      */
83     public void store() {
84
85     freeStart = keyLength;
86     super.store();
87     }
88
89     /**
90      * Returns the number of entries currently on this page.
91      *
92      * @return always returns 1
93      */
94     int numEntries() {
95         return 1;
96     }
97
98     /**
99      * Returns the offset in the page where a specified entry's key is located.
100      *
101      * @param entryNum entry number
102      *
103      * @return offset of entryNum's key
104      */
105     int keyOffset(int entryNum) {
106         return headerLength;
107     }
108
109     /**
110      * Returns the length of a specified entry's key.
111      *
112      * @param entryNum entry number
113      *
114      * @return length of entryNum's key
115      */
116     int keyLength(int entryNum) {
117         return keyLength;
118     }
119
120     /**
121      * Returns the data value for the specified entry.
122      *
123      * @param entryNum entry number
124      *
125      * @return new byte array containing the data at entryNum
126      */
127     byte[] getData(int entryNum) throws StorageException {
128
129     byte[] data = new byte[dataLength];
130     int pageSpace = btree.pageSize - headerLength;
131
132     if ((keyLength + dataLength) < pageSpace) {
133         System.arraycopy(pageBuffer, headerLength + keyLength,
134                 data, 0, dataLength);
135     } else {
136         SearchResult location = getDataLocation();
137         System.arraycopy(location.page.pageBuffer, location.entryNum,
138                 data, 0, dataLength);
139         if (location.page != this) {
140         pageSource.unpinPage(location.page);
141         }
142     }
143     return data;
144     }
145
146     private SearchResult getDataLocation() throws StorageException {
147
148     BtreePage current;
149     byte[] next;
150     int left;
151     int pageSpace = btree.pageSize - headerLength;
152
153     /* Find the last page of this key */
154     current = this;
155     left = keyLength;
156     while (left > pageSpace) {
157         left -= pageSpace;
158         next = current.nextPage;
159         if (current != this) {
160         pageSource.unpinPage(current);
161         }
162         current = pageSource.getPage(next, btree);
163     }
164     if ((left + dataLength) <= pageSpace) {
165         /* The data is on the current page */
166         return new SearchResult(true, headerLength+left, current);
167     } else {
168         /* The data is on the next page */
169         next = current.nextPage;
170         if (current != this) {
171         pageSource.unpinPage(current);
172         }
173         current = pageSource.getPage(next, btree);
174         return new SearchResult(true, headerLength, current);
175     }
176     }
177     /**
178      * Returns the key for the specified entry.
179      *
180      * @param entryNum entry number
181      *
182      * @return new byte array containing the key at entryNum
183      */
184     byte[] getKey(int entryNum) throws StorageException {
185
186     byte[] next;
187     byte[] key = new byte[keyLength];
188     int pageSpace = btree.pageSize - headerLength;
189
190     if (keyLength < pageSpace) {
191         System.arraycopy(pageBuffer, headerLength,
192                 key, 0, keyLength);
193     } else {
194         BtreePage page = this;
195         int left = keyLength;
196         while (left > pageSpace) {
197             System.arraycopy(page.pageBuffer, headerLength,
198                 key, keyLength - left, pageSpace);
199             left -= pageSpace;
200         next = page.nextPage;
201         if (page != this) {
202             pageSource.unpinPage(page);
203         }
204         page = pageSource.getPage(next, btree);
205         }
206         if (left > 0) {
207             System.arraycopy(page.pageBuffer, headerLength,
208                 key, keyLength - left, left);
209         }
210         if (page != this) {
211         pageSource.unpinPage(page);
212         }
213     }
214     return key;
215     }
216
217     /**
218      * Replaces the entry at the specified location with the passed-in entry.
219      * Since data is fixed length, we know it will fit.
220      *
221      * @param entry BtreeEntry to be inserted
222      * @param entryNum location where entry is to be inserted
223      *
224      * @return Always returns null
225      */
226
227     BtreeEntry replace(BtreeEntry entry, int entryNum, SearchResult resultPosition) throws StorageException {
228
229     SearchResult location;
230
231         pageSource.dirtyPage(this);
232     location = getDataLocation();
233     if (location.page != this) {
234         pageSource.dirtyPage(location.page);
235     }
236     System.arraycopy(entry.data, 0, location.page.pageBuffer,
237              location.entryNum, entry.data.length);
238     if (location.page != this) {
239         pageSource.unpinPage(location.page);
240     }
241         
242         // record position of inserted entry
243 if (resultPosition != null) {
244             resultPosition.matched = true;
245             resultPosition.skipCount = 0;
246             resultPosition.page = this;
247             resultPosition.entryNum = entryNum;
248         }
249         
250     return null;
251     }
252
253     /*
254      * Inserts an entry at the specified location.
255      *
256      * @param entry BtreeEntry to be inserted
257      * @param entryNum 0 if entry should be inserted before this one
258      * 1 if we're pointing to the last entry, and this entry
259      * should be inserted after it
260      *
261      */
262     BtreeEntry insert(BtreeEntry entry, int entryNum, SearchResult resultPosition)
263                     throws StorageException {
264
265     BigKeyPage current, previous, newNext;
266     BtreePage newPrevious;
267     byte[] next;
268     int left;
269     int pageSpace = btree.pageSize - headerLength;
270
271     if (keyLength == 0) {
272         /* This is the first BigKeyPage and it's already linked */
273         current = this;
274         pageSource.dirtyPage(current);
275         newNext = null;
276     } else {
277         /* Create the first new page for the new entry */
278         current = pageSource.newBigKeyPage(btree);
279         if (entryNum == 0) {
280         /* Insert before this page */
281             newPrevious = pageSource.getPage(this.previousPage, btree);
282         newNext = this;
283         pageSource.dirtyPage(this);
284         } else {
285         /* Insert at end of chain */
286         newNext = null;
287         newPrevious = this;
288         next = newPrevious.nextPage;
289         while (!pageSource.isNoPage(next)) {
290             if (newPrevious != this) {
291                 pageSource.unpinPage(newPrevious);
292             }
293             newPrevious = pageSource.getPage(next, btree);
294             next = newPrevious.nextPage;
295         }
296         }
297         pageSource.dirtyPage(newPrevious);
298         linkNewPage(current, newPrevious, newNext);
299         pageSource.unpinPage(newPrevious);
300     }
301
302         // record position of inserted entry
303 if (resultPosition != null) {
304             resultPosition.matched = true;
305             resultPosition.skipCount = 0;
306             resultPosition.page = current;
307             resultPosition.entryNum = entryNum; // [PENDING]
308 }
309         
310     current.keyLength = entry.key.length;
311
312     left = entry.key.length;
313     while (left > pageSpace) {
314         System.arraycopy(entry.key, entry.key.length - left,
315                     current.pageBuffer, headerLength, pageSpace);
316         left -= pageSpace;
317         previous = current;
318         current = pageSource.newBigKeyPage(btree);
319         linkNewPage(current, previous, newNext);
320         if (previous != this) {
321         pageSource.unpinPage(previous);
322         }
323     }
324     if (left > 0) {
325         System.arraycopy(entry.key, entry.key.length - left,
326                     current.pageBuffer, headerLength, left);
327     }
328     if ((left + dataLength) > pageSpace) {
329         previous = current;
330         current = pageSource.newBigKeyPage(btree);
331         linkNewPage(current, previous, newNext);
332         if (previous != this) {
333         pageSource.unpinPage(previous);
334         }
335         left = 0;
336     }
337     System.arraycopy(entry.data, 0, current.pageBuffer, headerLength + left,
338                             dataLength);
339     if (current != this) {
340         pageSource.unpinPage(current);
341     }
342     if ((newNext != null) && (newNext != this)) {
343         pageSource.unpinPage(newNext);
344     }
345     return null;
346     }
347
348     private void linkNewPage(BtreePage newPage, BtreePage left,
349                     BtreePage right) {
350     System.arraycopy(left.pageId, 0, newPage.previousPage, 0,
351                         left.pageId.length);
352     System.arraycopy(left.nextPage, 0, newPage.nextPage, 0,
353                         left.pageId.length);
354     System.arraycopy(newPage.pageId, 0, left.nextPage, 0,
355                         newPage.pageId.length);
356     if (right != null) {
357         System.arraycopy(newPage.pageId, 0, right.previousPage, 0,
358                         newPage.pageId.length);
359     }
360     }
361
362     /**
363      * Deletes an entry or range of entries from this page.
364      *
365      * @param first ignored
366      * @param last ignored
367      */
368
369     void delete(int first, int last) throws StorageException {
370
371     BtreePage next, previous, current;
372     int pageSpace = btree.pageSize - headerLength;
373     int left = keyLength;
374
375     current = this;
376     previous = pageSource.getPage(this.previousPage, btree);
377     pageSource.dirtyPage(previous);
378     while (left > pageSpace) {
379         left -= pageSpace;
380         next = pageSource.getPage(current.nextPage, btree);
381         if (current != this) {
382         pageSource.unpinPage(current);
383         }
384         current = next;
385     }
386     if ((left + dataLength) > pageSpace) {
387         /* The data is on the next page */
388         next = pageSource.getPage(current.nextPage, btree);
389             pageSource.unpinPage(current);
390         current = next;
391     }
392     /* current is the last page to be deleted */
393     System.arraycopy(current.nextPage, 0, previous.nextPage, 0,
394                     current.nextPage.length);
395     if (!pageSource.isNoPage(current.nextPage)) {
396         next = pageSource.getPage(current.nextPage, btree);
397         pageSource.dirtyPage(next);
398         System.arraycopy(previous.pageId, 0, next.previousPage, 0,
399                     previous.pageId.length);
400         pageSource.unpinPage(next);
401     }
402     if (previous.isRoot() && pageSource.isNoPage(previous.nextPage)) {
403         btree.unsetHasBigKeys();
404     }
405     pageSource.unpinPage(previous);
406     if (current != this) {
407         pageSource.unpinPage(current);
408     }
409     }
410
411     /*
412      * Do nothing.
413      */
414     byte[] splitEntries(BtreePage leftBP, BtreePage rightBP, BtreeEntry entry,
415                 int newEntryNum, SearchResult resultPosition) throws StorageException {
416     return null;
417     }
418
419     /**
420      * Search for the key starting from this page. We do this in a very
421      * inefficient way.
422      */
423     SearchResult searchBigKeys(byte[] key) throws StorageException {
424
425     BigKeyPage current, next;
426         byte[] currentKey;
427     SearchResult result;
428     byte compare;
429
430     next = this;
431     result = null;
432     do {
433         current = next;
434         currentKey = current.getKey(0);
435         compare = btree.keyInfo.compare(key, currentKey, 0, currentKey.length);
436         if (compare == EntryTypeInfo.EQUAL) {
437             result = new SearchResult(true, 0, current);
438         } else if (compare == EntryTypeInfo.LESS) {
439             result = new SearchResult(false, 0, current);
440         } else {
441             next = current.getNextKeyStart();
442         if (current != this) {
443             pageSource.unpinPage(current);
444         }
445         }
446     } while ((result == null) && (next != null));
447
448     if (result == null) {
449         result = new SearchResult(false, 1, current);
450     }
451     return result;
452     }
453
454     /*
455      * Get the next entry, starting from the passed in result. The
456      * result is updated to point to the next entry and indicate whether
457      * it matched the key. If key is null, it is considered a match as long
458      * as any record was found.
459      *
460      * If testOnly is true, result.matched is updated but result.page and
461      * result.entry are left unchanged.
462      */
463     static void getNext(byte[] key, SearchResult result, boolean testOnly)
464                         throws StorageException {
465  
466     BigKeyPage page;
467     byte[] currentKey;
468     Btree btree = result.page.btree;
469     
470     if (result.entryNum == -1) {
471         page = (BigKeyPage)result.page;
472         if (!testOnly) {
473             result.entryNum = 0;
474         }
475     } else {
476         page = ((BigKeyPage)result.page).getNextKeyStart();
477     }
478     if (page == null) {
479         result.matched = false;
480         result.entryNum = 1;
481         return;
482     }
483     
484     if (key != null) {
485         currentKey = page.getKey(0);
486         if (btree.keyInfo.compare(key, currentKey, 0, currentKey.length)
487                 == EntryTypeInfo.EQUAL) {
488         result.matched = true;
489         } else {
490             result.matched = false;
491         }
492     } else {
493         result.matched = true;
494     }
495     if (!testOnly) {
496         result.page = page;
497     }
498     }
499
500     BigKeyPage getNextKeyStart() throws StorageException {
501
502     BigKeyPage next, currentDataPage;
503
504     currentDataPage = (BigKeyPage) getDataLocation().page;
505     if (!pageSource.isNoPage(currentDataPage.nextPage)) {
506         next = (BigKeyPage) pageSource.getPage(currentDataPage.nextPage,
507                                         btree);
508     } else {
509         next = null;
510     }
511     if (currentDataPage != this) {
512         pageSource.unpinPage(currentDataPage);
513     }
514     return next;
515     }
516
517     /*
518      * Gets the previous entry location. This only operates within the
519      * big key chain, i.e., calling getPrevious when positioned at the first
520      * big key entry will not backup to the last normal entry. Instead,
521      * it will return the location of the first big key, matched = false,
522      * and set entryNum to -1.
523      */
524     static void getPrevious(byte[] key, SearchResult result, boolean testOnly)
525                         throws StorageException {
526     BigKeyPage page;
527     byte[] currentKey;
528     Btree btree = result.page.btree;
529     
530     page = ((BigKeyPage)result.page).getPreviousKeyStart();
531     if (page == null) {
532         if (!testOnly) {
533             result.entryNum = -1;
534         }
535         result.matched = false;
536         return;
537     }
538     
539     if (key != null) {
540         currentKey = page.getKey(0);
541         if (btree.keyInfo.compare(key, currentKey, 0, currentKey.length)
542                 == EntryTypeInfo.EQUAL) {
543         result.matched = true;
544         } else {
545             result.matched = false;
546         }
547     } else {
548         result.matched = true;
549     }
550     if (!testOnly) {
551         result.page = page;
552     }
553     }
554
555     BigKeyPage getPreviousKeyStart() throws StorageException {
556
557         int currentLength = 0;
558     BtreePage current, previous;
559     
560     current = this;
561     do {
562         previous = pageSource.getPage(current.previousPage, btree);
563         if (current != this) {
564             pageSource.unpinPage(current);
565         }
566         current = previous;
567         if (!(current instanceof BigKeyPage)) {
568             /* we're back at the root */
569             pageSource.unpinPage(current);
570         current = null;
571         } else {
572             currentLength = ((BigKeyPage)current).keyLength;
573         }
574     } while ((current != null) && (currentLength == 0));
575
576     return (BigKeyPage)current;
577     }
578
579     /*
580      * Make the first BigKeyPage and link it to the root.
581      */
582     static BtreePage makeFirst(BtreePage root, BtreePageSource pageSource)
583                             throws StorageException {
584
585     BtreePage newPage;
586
587     newPage = pageSource.newBigKeyPage(root.btree);
588     System.arraycopy(newPage.pageId, 0, root.nextPage, 0,
589                         newPage.pageId.length);
590     System.arraycopy(root.pageId, 0, newPage.previousPage, 0,
591                         newPage.pageId.length);
592     root.btree.setHasBigKeys();
593     return newPage;
594     }
595     
596     void dumpLevel(PrintWriter out) throws StorageException {
597     
598         BigKeyPage current, next;
599     current = this;
600         do {
601         current.dumpPage(out);
602         next = current.getNextKeyStart();
603         if (current != this) {
604             pageSource.unpinPage(current);
605         }
606         current = next;
607     } while (current != null);
608     }
609
610     public void dumpPageHeader(PrintWriter out) {
611         super.dumpPageHeader(out);
612     out.println("Key length: " + keyLength + "\n");
613     }
614
615     public void dumpPageEntries(PrintWriter out) throws StorageException {
616
617         out.println("\nPage entries:\n\n");
618
619         out.print(btree.keyInfo.fromBuffer(getKey(0)) + ", ");
620     out.println(btree.dataInfo.fromBuffer(getData(0)));
621     }
622 }
623
Popular Tags