KickJava   Java API By Example, From Geeks To Geeks.

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


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 java.io.*;
23 import java.util.Arrays JavaDoc;
24
25 /**
26  * Implementation of a BtreePage with fixed key length and fixed data length that
27  * are stored in compressed form if all the stored keys or data prefixes are
28  * strings of zeros (these prefixes are excluded then).
29  */
30 public class ShrinkablePage extends BtreePage {
31
32     private static boolean debug = false;
33
34     private static final byte KEYS_SHRINKED_MASK = 1;
35     private static final byte DATA_SHRINKED_MASK = 2;
36     
37     // length of the key prefix relavant to the page compression
38 static final int KEY_ZERO_PREFIX_LENGTH = MOFID.LENGTH / 2;
39     // length of the data prefix relavant to the page compression
40 static final int DATA_ZERO_PREFIX_LENGTH = MOFID.LENGTH / 2;
41     
42     // length of the key - determined by key info
43 int keyLengthX;
44     // length of data - determined by data info
45 int dataLengthX;
46     
47     // flag indicating if the keys are stored in the compressed form
48 boolean keysShrinked;
49     // flag indicating if the data are stored in the compressed form
50 boolean dataShrinked;
51     // true if keys are shrinkable
52 boolean keysShrinkable;
53     // true if data are shrinkable
54 boolean dataShrinkable;
55     
56     // number of bytes currently used to store a key
57 int currentKeyLength;
58     // number of bytes currently used to store data
59 int currentDataLength;
60     
61     /*
62     // number of keys with non-zero prefix stored in the page
63     int longKeysCount;
64     // number of data with non-zero prefix stored in the page
65     int longDataCount;
66      */
67     
68     // flag indicating if an operation requires key parts of entries to expanded (from shrinked form)
69 boolean expandKeys;
70     // flag indicating if an operation requires data parts of entries to expanded (from shrinked form)
71 boolean expandData;
72     
73     /**
74      * Initialize a newly-instantiated or recycled ShrinkablePage. Note that the
75      * isNew parameter pertains to whether a new page is being added to the
76      * btree, not to whether this BtreePage object is new or recycled.
77      *
78      * @param btree btree to which this page belongs
79      * @param pageId page ID in byte array
80      * @param pageBuffer page buffer
81      * @param isNew is this page new to the btree
82      */
83     public void init(Btree btree, byte[] pageId, byte[] pageBuffer,
84                 boolean isNew) throws StorageException {
85
86         if (initialized) {
87             /* This page was found in cache and doesn't need initialization */
88             return;
89         }
90         
91         super.init(btree, pageId, pageBuffer, isNew);
92         
93         headerLength++;
94         
95     keyLengthX = btree.keyInfo.getLength();
96         dataLengthX = btree.dataInfo.getLength();
97         
98         keysShrinkable = btree.keyInfo instanceof MOFIDInfo;
99         dataShrinkable = btree.dataInfo instanceof MOFIDInfo;
100                         
101         if (isNew) {
102             keysShrinked = keysShrinkable;
103             dataShrinked = dataShrinkable;
104             freeStart++;
105         } else {
106             keysShrinked = (pageBuffer [headerLength - 1] & KEYS_SHRINKED_MASK) > 0;
107             dataShrinked = (pageBuffer [headerLength - 1] & DATA_SHRINKED_MASK) > 0;
108         }
109         
110         currentKeyLength = keysShrinked ? MOFID.LENGTH / 2 : keyLengthX;
111         currentDataLength = dataShrinked ? MOFID.LENGTH / 2 : dataLengthX;
112         
113         /*
114         longKeysCount = 0;
115         longDataCount = 0;
116          */
117     }
118
119     /**
120      * Returns the number of entries currently on this page.
121      *
122      * @return number of entries on this page
123      */
124     int numEntries() {
125         return (freeStart - headerLength)/(currentKeyLength + currentDataLength);
126     }
127
128     /**
129      * Returns the offset in the page where a specified entry's key is located.
130      *
131      * @param entryNum entry number
132      *
133      * @return offset of entryNum's key
134      */
135     int keyOffset(int entryNum) {
136         return headerLength + (entryNum * (currentKeyLength + currentDataLength));
137     }
138
139     /**
140      * Returns the length of a specified entry's key.
141      *
142      * @param entryNum entry number
143      *
144      * @return length of entryNum's key
145      */
146     int keyLength(int entryNum) {
147         return keyLengthX;
148     }
149     
150     /**
151      * Returns the data value for the specified entry.
152      *
153      * @param entryNum entry number
154      *
155      * @return new byte array containing the data at entryNum
156      */
157     byte[] getData(int entryNum) {
158         byte[] data = new byte[dataLengthX];
159         if (dataShrinked) {
160             System.arraycopy(pageBuffer, keyOffset(entryNum) + currentKeyLength,
161                 data, DATA_ZERO_PREFIX_LENGTH, currentDataLength);
162         } else {
163             System.arraycopy(pageBuffer, keyOffset(entryNum) + currentKeyLength,
164                 data, 0, currentDataLength);
165         }
166         
167         if (debug) {
168             System.out.println("getData called: " + entryNum);
169         }
170         
171     return data;
172     }
173
174     /**
175      * Returns the key for the specified entry.
176      *
177      * @param entryNum entry number
178      *
179      * @return new byte array containing the key at entryNum
180      */
181     byte[] getKey(int entryNum) {
182         byte[] key = new byte[keyLengthX];
183         if (keysShrinked) {
184             System.arraycopy(pageBuffer, keyOffset(entryNum), key,
185                     KEY_ZERO_PREFIX_LENGTH, currentKeyLength);
186         } else {
187             System.arraycopy(pageBuffer, keyOffset(entryNum), key, 0, currentKeyLength);
188         }
189         
190         if (debug) {
191             System.out.print("getKey: ");
192             for (int x = 0; x < key.length; x++)
193                 System.out.print(key[x] + ":");
194             System.out.println("");
195         }
196     return key;
197     }
198
199     protected byte compare(byte[] key, int entryNum) {
200
201         if (!isLeaf() && (entryNum == 0)
202         && pageSource.isNoPage(previousPage)) {
203         return EntryTypeInfo.GREATER;
204     }
205         
206         int index = 0;
207     byte k,p;
208         if (keysShrinkable && keysShrinked) {
209             for (; index < KEY_ZERO_PREFIX_LENGTH; index++) {
210         k = key[index];
211                 if (k < 0) {
212                     return EntryTypeInfo.LESS;
213                 } else if (k > 0) {
214                     return EntryTypeInfo.GREATER;
215                 }
216             } // for
217 } // if
218 int offset = keyOffset (entryNum);
219     for (; index < key.length; index++, offset++) {
220         k = key[index];
221         p = pageBuffer[offset];
222         if (k < p) {
223             return EntryTypeInfo.LESS;
224         } else if (k > p) {
225             return EntryTypeInfo.GREATER;
226         }
227         }
228         return EntryTypeInfo.EQUAL;
229     }
230     
231     protected byte compareData(byte[] data, int entryNum) {
232
233     int index = 0;
234     byte d,p;
235         if (dataShrinkable && dataShrinked) {
236             for (; index < DATA_ZERO_PREFIX_LENGTH; index++) {
237         d = data[index];
238                 if (d < 0) {
239                     return EntryTypeInfo.LESS;
240                 } else if (d > 0) {
241                     return EntryTypeInfo.GREATER;
242                 }
243             } // for
244 } // if
245 int offset = keyOffset (entryNum) + currentKeyLength;
246     for (; index < data.length; index++, offset++) {
247         d = data[index];
248         p = pageBuffer[offset];
249         if (d < p) {
250             return EntryTypeInfo.LESS;
251         } else if (d > p) {
252             return EntryTypeInfo.GREATER;
253         }
254         }
255         return EntryTypeInfo.EQUAL;
256     }
257     
258     /*
259      * Inserts an entry at the specified location.
260      *
261      * @param entry BtreeEntry to be inserted
262      * @param entryNum location where entry is to be inserted
263      *
264      * @return If a split occurred, an entry to be inserted in this page's
265      * parent is returned; otherwise null is returned.
266      */
267     BtreeEntry insert(BtreeEntry entry, int entryNum, SearchResult resultPosition)
268                     throws StorageException {
269                                         
270         if (debug) {
271             System.out.print("insert called: ");
272             for (int x = 0; x < entry.key.length; x++) {
273                 System.out.print(entry.key [x]);
274             }
275             System.out.println("");
276         }
277         
278         if (debug) {
279             for (int x = 0; x < entry.key.length; x++)
280                 System.out.print(entry.key[x] + ":");
281             System.out.print(" ");
282             for (int x = 0; x < entry.data.length; x++)
283                 System.out.print(entry.data[x] + ":");
284             System.out.println();
285         }
286                                     
287         int space = 0;
288         
289         expandKeys = false;
290         expandData = false;
291
292         pageSource.dirtyPage(this);
293
294         if (keysShrinked && hasLongKey (entry)) {
295             expandKeys = true;
296             space += numEntries () * KEY_ZERO_PREFIX_LENGTH + entry.key.length;
297         }
298         if (dataShrinked && hasLongData (entry)) {
299             expandData = true;
300             space += numEntries () * DATA_ZERO_PREFIX_LENGTH + entry.data.length;
301         }
302         if (!expandKeys)
303             space += currentKeyLength;
304         if (!expandData)
305             space += currentDataLength;
306
307         if (btree.pageSize - freeStart - keyLengthX - dataLengthX >= space) {
308         insertHere(entry, entryNum, resultPosition);
309         return null;
310     } else {
311         BtreeEntry result = split(entry, entryNum, resultPosition);
312             return result;
313     }
314     }
315
316     /*
317      * Replaces the entry at the specified location with the passed-in entry.
318      *
319      * @param entry BtreeEntry to be inserted
320      * @param entryNum location where entry is to be inserted
321      *
322      * @return
323      */
324     BtreeEntry replace(BtreeEntry entry, int entryNum, SearchResult position) throws StorageException {
325
326         if (debug) {
327             System.out.println("replace called");
328         }
329         
330         pageSource.dirtyPage(this);
331
332         if (dataShrinked && hasLongData (entry)) {
333             int space = numEntries () * (currentKeyLength + dataLengthX);
334             if (btree.pageSize - freeStart - keyLengthX - dataLengthX < space) {
335                 delete (entryNum, entryNum);
336                 return insert (entry, entryNum, position);
337             } else {
338                 expandData ();
339             }
340         }
341         
342         int offset = keyOffset(entryNum) + currentKeyLength;
343         int dataStart = dataShrinked ? DATA_ZERO_PREFIX_LENGTH : 0;
344     System.arraycopy(entry.data, dataStart, pageBuffer, offset, currentDataLength);
345         
346     return null;
347     }
348     
349     private void insertHere(BtreeEntry entry, int entryNum, SearchResult resultPosition) {
350
351         if (debug) {
352             //if (expandKeys || expandData) {
353 dump ();
354                 dumpBuffer ();
355             //}
356 }
357         
358         int offset;
359         if (expandKeys)
360             expandKeys ();
361         if (expandData)
362             expandData ();
363         
364     offset = keyOffset(entryNum);
365     if (offset != freeStart) {
366         /* Shift entries down to make room for this one */
367         System.arraycopy(pageBuffer, offset,
368             pageBuffer, offset + (currentKeyLength + currentDataLength),
369             freeStart - offset);
370     }
371         copyEntry (offset, entry);
372     freeStart += currentKeyLength + currentDataLength;
373         
374         if (resultPosition != null) {
375             resultPosition.entryNum = entryNum;
376             resultPosition.matched = true;
377             resultPosition.page = this;
378             resultPosition.skipCount = 0;
379         }
380
381         if (debug) {
382             //if ((expandKeys || expandData)) {
383 //System.out.print("insert called: ");
384 for (int x = 0; x < entry.key.length; x++) {
385                     System.out.print(entry.key [x]);
386                 }
387                 System.out.println("");
388                 dump ();
389                 dumpBuffer ();
390             //}
391 }
392         
393     }
394
395     /**
396      * Deletes an entry or range of entries from this page.
397      *
398      * @param first entry number of first entry to be deleted
399      * @param last entry number of last entry to be deleted
400      */
401     void delete(int firstEntry, int lastEntry) throws StorageException {
402         int startOffset, endOffset;
403
404         if (debug) {
405             System.out.println("delete called: " + firstEntry + " " + lastEntry);
406         }
407         
408     pageSource.dirtyPage(this);
409
410     startOffset = keyOffset(firstEntry);
411     endOffset = keyOffset(lastEntry+1);
412     if (freeStart != endOffset) {
413         System.arraycopy(pageBuffer, endOffset, pageBuffer, startOffset,
414                 freeStart - endOffset);
415     }
416     freeStart -= endOffset - startOffset;
417     }
418
419     /**
420      * Splits the entries on the current page between two pages, and inserts
421      * an entry into its correct location on one of those pages. The left
422      * page may be this page or it may be a different page. The right page is
423      * always a different page from this.
424      *
425      * @param left left page to move entries to (may be this page)
426      * @param right right page to move entries to
427      * @param entry BtreeEntry to be inserted
428      * @param newEntryNum insert location relative to the current page
429      *
430      * @return new byte array containing first key on right page
431      */
432     byte[] splitEntries(BtreePage leftPage, BtreePage rightPage, BtreeEntry entry,
433                 int entryNum, SearchResult resultPosition) {
434     
435     int entryLength;
436     int offset;
437     int midpoint;
438         int half;
439     int copyLength;
440     boolean insertLeft;
441     
442         if (debug) {
443             System.out.println("Split entries called.");
444         }
445         
446         ShrinkablePage left = (ShrinkablePage) leftPage;
447         ShrinkablePage right = (ShrinkablePage) rightPage;
448         
449         copyState (right);
450         if (left != this)
451             copyState (left);
452         
453     offset = keyOffset(entryNum);
454     entryLength = currentKeyLength + currentDataLength;
455         half = numEntries()/2;
456     midpoint = headerLength + half*entryLength;
457     insertLeft = offset < midpoint;
458
459     // Move second half of entries to right page.
460 if (insertLeft) {
461         copyLength = this.freeStart - midpoint;
462     } else {
463         // First just copy entries up to the insert point
464 copyLength = offset - midpoint;
465     }
466         
467         // record position of inserted entry
468 if (resultPosition != null) {
469             resultPosition.matched = true;
470             resultPosition.skipCount = 0;
471             if (insertLeft) {
472                 resultPosition.page = left;
473                 resultPosition.entryNum = entryNum;
474             } else {
475                 resultPosition.page = right;
476                 resultPosition.entryNum = entryNum - half;
477             }
478         }
479         
480     if (copyLength > 0) {
481         System.arraycopy(this.pageBuffer, midpoint, right.pageBuffer,
482             right.freeStart, copyLength);
483         right.freeStart += copyLength;
484     }
485     if (!insertLeft) {
486         // System.arraycopy(entry.key, 0, right.pageBuffer, right.freeStart, currentKeyLength);
487 right.freeStart += currentKeyLength;
488         // System.arraycopy(entry.data, 0, right.pageBuffer, right.freeStart, currentDataLength);
489 right.freeStart += currentDataLength;
490         if (this.freeStart != offset) {
491             System.arraycopy(this.pageBuffer, offset, right.pageBuffer,
492             right.freeStart, this.freeStart - offset);
493             right.freeStart += this.freeStart - offset;
494         }
495             if (expandKeys)
496                 right.expandKeys ();
497             if (expandData)
498                 right.expandData ();
499             right.copyEntry (right.keyOffset (entryNum - half), entry);
500     }
501     
502     // Move first half of entries to left page, if left page is new.
503 // Either way, insert the new entry if it belongs here.
504 if (left != this) {
505         if (insertLeft) {
506         copyLength = offset - headerLength;
507         } else {
508         copyLength = midpoint - headerLength;
509         }
510         if (copyLength > 0) {
511             System.arraycopy(this.pageBuffer, headerLength,
512                 left.pageBuffer, left.freeStart, copyLength);
513         }
514     }
515
516     if (insertLeft) {
517         if (midpoint != offset) {
518             System.arraycopy(this.pageBuffer, offset, left.pageBuffer,
519             offset+entryLength, midpoint - offset);
520         }
521             left.freeStart = midpoint + entryLength;
522             if (expandKeys)
523                 left.expandKeys ();
524             if (expandData)
525                 left.expandData ();
526             left.copyEntry (keyOffset (entryNum), entry);
527         // System.arraycopy(entry.key, 0, left.pageBuffer, offset, keyLength);
528 // System.arraycopy(entry.data, 0, left.pageBuffer, offset + keyLength, dataLength);
529 } else {
530         left.freeStart = midpoint;
531     }
532     if (left != this) {
533         // All entries were moved off of this page
534 this.freeStart = headerLength;
535     }
536         /*
537     rightKey = new byte[keyLength];
538     System.arraycopy(right.pageBuffer, headerLength, rightKey, 0, keyLength);
539     return rightKey;
540          */
541         
542         /*
543         try {
544             System.out.println("============");
545             for (int x = 0; x < entry.key.length; x++)
546                 System.out.print(entry.key[x]);
547             System.out.print(" ");
548             for (int x = 0; x < entry.data.length; x++)
549                 System.out.print(entry.data[x]);
550             System.out.println();
551             
552             pg.getKey (entNum);
553             pg.getData (entNum);
554             System.out.println("============");
555         } catch (Exception e) {
556         }
557         */
558         
559         // System.out.println("split done: " + left.numEntries () + " " + right.numEntries ());
560
561         return right.getKey (0);
562     }
563     
564     public void store() {
565
566     super.store();
567
568         byte val = 0;
569         if (keysShrinked) {
570             val += KEYS_SHRINKED_MASK;
571         }
572         if (dataShrinked) {
573             val += DATA_SHRINKED_MASK;
574         }
575         pageBuffer [headerLength - 1] = val;
576     }
577     
578     // helper methods ...........................................................
579
580     /**
581      * @return true if the entry's key prefix does not consist of 0's
582      */
583     private boolean hasLongKey (BtreeEntry entry) {
584         for (int x = 0; x < KEY_ZERO_PREFIX_LENGTH; x++) {
585             if (entry.key [x] != 0)
586                 return true;
587         } // for
588 return false;
589     }
590     
591     /**
592      * @return true if the entry's data prefix does not consist of 0's
593      */
594     private boolean hasLongData (BtreeEntry entry) {
595         for (int x = 0; x < KEY_ZERO_PREFIX_LENGTH; x++) {
596             if (entry.data [x] != 0)
597                 return true;
598         } // for
599 return false;
600     }
601     
602     void expandKeys () {
603         if (debug) {
604             System.out.println("expand keys called");
605             dump ();
606         }
607         
608         int numEntries = numEntries ();
609         int length = numEntries * (currentKeyLength + currentDataLength);
610         byte [] tempBuffer = new byte [length];
611         System.arraycopy (pageBuffer, headerLength, tempBuffer, 0, length);
612         for (int i = 0; i < numEntries; i++) {
613             int index = headerLength + i*(keyLengthX + currentDataLength);
614             Arrays.fill (pageBuffer, index,
615                 index + KEY_ZERO_PREFIX_LENGTH, (byte) 0);
616             System.arraycopy (tempBuffer, i*(currentKeyLength + currentDataLength), pageBuffer,
617                 KEY_ZERO_PREFIX_LENGTH + index,
618                 currentKeyLength + currentDataLength);
619         }
620         freeStart += numEntries * KEY_ZERO_PREFIX_LENGTH;
621         currentKeyLength = keyLengthX;
622         keysShrinked = false;
623         
624         if (debug) {
625             dump ();
626         }
627     }
628     
629     void expandData () {
630         if (debug) {
631             System.out.println("expand data called");
632         }
633         
634         int numEntries = numEntries ();
635         int length = numEntries * (currentKeyLength + currentDataLength);
636         byte [] tempBuffer = new byte [length];
637         System.arraycopy (pageBuffer, headerLength, tempBuffer, 0, length);
638         for (int i = 0; i < numEntries; i++) {
639             int index = headerLength + currentKeyLength + i*(currentKeyLength + dataLengthX);
640             System.arraycopy (tempBuffer,
641                 i*(currentKeyLength + currentDataLength),
642                 pageBuffer,
643                 headerLength + i*(keyLengthX + currentDataLength), currentKeyLength);
644             Arrays.fill (pageBuffer,
645                 index,
646                 index + DATA_ZERO_PREFIX_LENGTH, (byte) 0);
647             System.arraycopy (tempBuffer,
648                 currentKeyLength + i*(currentKeyLength + currentDataLength),
649                 pageBuffer,
650                 headerLength + currentKeyLength + DATA_ZERO_PREFIX_LENGTH + i*(keyLengthX + currentDataLength),
651                 currentDataLength);
652         }
653         freeStart += numEntries * DATA_ZERO_PREFIX_LENGTH;
654         currentDataLength = dataLengthX;
655         dataShrinked = false;
656     }
657     
658     void copyEntry (int offset, BtreeEntry entry) {
659         int keyStart = keysShrinked ? KEY_ZERO_PREFIX_LENGTH : 0;
660         int dataStart = dataShrinked ? DATA_ZERO_PREFIX_LENGTH : 0;
661         System.arraycopy(entry.key, keyStart, pageBuffer, offset, currentKeyLength);
662     System.arraycopy(entry.data, dataStart, pageBuffer,
663             offset + currentKeyLength, currentDataLength);
664     }
665     
666     private void copyState (ShrinkablePage page) {
667         page.keysShrinked = keysShrinked;
668         page.dataShrinked = dataShrinked;
669         page.currentKeyLength = currentKeyLength;
670         page.currentDataLength = currentDataLength;
671     }
672     
673     public void dump () {
674         System.out.println("# entries: " + numEntries () + " ------------------");
675         for (int i = 0; i < numEntries (); i++) {
676             boolean temp = debug;
677             debug = true;
678             getKey (i);
679             System.out.print(" ");
680             getData (i);
681             debug = temp;
682         }
683         System.out.println("----------------------------------");
684     }
685     
686     public void dumpBuffer () {
687         System.out.print("buff: ");
688         for (int x = headerLength; x < freeStart; x++) {
689             System.out.print(pageBuffer[x] + ".");
690         }
691         System.out.println("");
692     }
693     
694 }
695
Popular Tags