KickJava   Java API By Example, From Geeks To Geeks.

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


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 Converter */
23 import java.io.*;
24 import org.openide.ErrorManager;
25
26 /**
27  * Implementation of a BtreePage with variable length keys and fixed length
28  * data.
29  */
30  /*The format of a page in the page buffer is as follows:
31  *
32  * The BtreePage header fields are followed by a series of 2-byte integers
33  * Each of these is the offset of an entry on the page. The entries are
34  * maintained in key order, and each entry consists of its key followed
35  * by its data value. Entries start from the end of the page and grow
36  * backwards towards the offset table.
37  *
38  * freeStart
39  * |
40  * V
41  * ------------------------------------------------------
42  * | header | offsets | free space |
43  * | | used space |
44  * ------------------------------------------------------
45  * ^ ^
46  * | |
47  * offsets[0] offsets[nextOffset]
48  * = page size
49  *
50  * The header fields and offsets are not updated in the page buffer until
51  * the page is serialized.
52  */
53 public class VarKeyPage extends BtreePage {
54
55     private int[] offsets;
56     private int nextOffset; // index into offsets array
57 private static final int SIZE_OF_OFFSET = SIZE_OF_SHORT;
58
59     /**
60      * Initialize a newly-instantiated or recycled VarKeyPage. Note that the
61      * isNew parameter pertains to whether a new page is being added to the
62      * btree, not to whether this BtreePage object is new or recycled.
63      *
64      * @param btree btree to which this page belongs
65      * @param pageId page ID in byte array
66      * @param pageBuffer page buffer
67      * @param isNew is this page new to the btree
68      */
69     public void init(Btree btree, byte[] pageId, byte[] pageBuffer,
70                     boolean isNew) throws StorageException {
71
72     int maxOffsets;
73
74     if (initialized) {
75         /* This page was found in cache and doesn't need initialization */
76         return;
77     }
78
79         super.init(btree, pageId, pageBuffer, isNew);
80
81     /* Allocate offsets table. Only the entries actually in use
82      * will be written to the page buffer, so it doesn't matter
83      * if we allocate this bigger than necessary. We don't have
84      * the information yet to do a better estimate.
85      *
86      * No need to allocate if this is a recycled page.
87      */
88     if (offsets == null) {
89         maxOffsets = (btree.pageSize - headerLength)/SIZE_OF_OFFSET;
90         offsets = new int[maxOffsets];
91     }
92     initOffsets(isNew);
93     }
94
95     private void initOffsets(boolean isNew) {
96
97     int pageOffset = headerLength;
98
99     if (isNew) {
100         nextOffset = 0;
101     } else {
102         nextOffset = (freeStart - headerLength)/SIZE_OF_OFFSET;
103         for (int i = 0; i < nextOffset; i++) {
104         offsets[i] = (int) Converter.readShort(pageBuffer,
105                             pageOffset);
106         pageOffset += 2;
107         }
108     }
109     offsets[nextOffset] = btree.pageSize;
110     }
111
112     /**
113      * Write VarKeyPage header data to the page buffer.
114      */
115     public void store() {
116
117     int pageOffset = headerLength;
118
119     super.store();
120
121     if (nextOffset > 0) {
122         for (int i = 0; i < nextOffset; i++) {
123         Converter.writeShort(pageBuffer, pageOffset, (short)offsets[i]);
124         pageOffset += 2;
125         }
126     }
127     }
128
129     /**
130      * Returns the number of entries currently on this page.
131      *
132      * @return number of entries on this page
133      */
134     int numEntries() {
135         return nextOffset;
136     }
137
138     /**
139      * Returns the offset in the page where a specified entry's key is located.
140      *
141      * @param entryNum entry number
142      *
143      * @return offset of entryNum's key
144      */
145     int keyOffset(int entryNum) {
146         return offsets[entryNum];
147     }
148
149     /**
150      * Returns the length of a specified entry's key.
151      *
152      * @param entryNum entry number
153      *
154      * @return length of entryNum's key
155      */
156     int keyLength(int entryNum) {
157         if (entryNum != nextOffset) {
158             return offsets[entryNum+1] - offsets[entryNum] - dataLength;
159     } else {
160         // this should never happen
161 return 0;
162     }
163     }
164
165     /**
166      * Returns the data value for the specified entry.
167      *
168      * @param entryNum entry number
169      *
170      * @return new byte array containing the data at entryNum
171      */
172     byte[] getData(int entryNum) {
173
174     byte[] data = new byte[dataLength];
175         try {
176             System.arraycopy(pageBuffer, offsets[entryNum+1] - dataLength,
177                             data, 0, dataLength);
178         } catch (ArrayIndexOutOfBoundsException JavaDoc e) {
179             // temporal debug message
180 String JavaDoc msg = "mdr.btreestorage.VarKeyPage.getData, ArrayIndexOutOfBoundsException occured\n" + // NOI18N
181 "buffer length: " + pageBuffer.length + ", offset: " + offsets[entryNum+1] + // NOI18N
182 ", dataLength: " + dataLength + ", data length: " + data.length; // NOI18N
183 ErrorManager.getDefault().log(ErrorManager.EXCEPTION, msg);
184             throw e;
185         }
186     return data;
187     }
188
189     /**
190      * Returns the key for the specified entry.
191      *
192      * @param entryNum entry number
193      *
194      * @return new byte array containing the key at entryNum
195      */
196     byte[] getKey(int entryNum) {
197
198     byte[] key = new byte[keyLength(entryNum)];
199     System.arraycopy(pageBuffer, offsets[entryNum], key, 0, key.length);
200     return key;
201     }
202
203     /*
204      * Replaces the entry at the specified location with the passed-in entry.
205      * Since data is fixed length, we know it will fit.
206      *
207      * @param entry BtreeEntry to be inserted
208      * @param entryNum location where entry is to be inserted
209      *
210      * @return Always returns null
211      */
212
213     BtreeEntry replace(BtreeEntry entry, int entryNum, SearchResult resultPosition) throws StorageException {
214
215         pageSource.dirtyPage(this);
216     System.arraycopy(entry.data, 0,
217              pageBuffer, offsets[entryNum+1] - entry.data.length,
218              entry.data.length);
219         
220         // record position of inserted entry
221 if (resultPosition != null) {
222             resultPosition.matched = true;
223             resultPosition.skipCount = 0;
224             resultPosition.page = this;
225             resultPosition.entryNum = entryNum;
226         }
227         
228     // We didn't split so there is no parent entry to return
229 return null;
230     }
231
232     /*
233      * Inserts an entry at the specified location.
234      *
235      * @param entry BtreeEntry to be inserted
236      * @param entryNum location where entry is to be inserted
237      *
238      * @return If a split occurred, an entry to be inserted in this page's
239      * parent is returned; otherwise null is returned.
240      */
241     BtreeEntry insert(BtreeEntry entry, int entryNum, SearchResult resultPosition)
242                     throws StorageException {
243
244     int entriesStart;
245     int entriesSplit;
246
247         pageSource.dirtyPage(this);
248
249     if (!haveSpaceForInsert(entry)) {
250         return split(entry, entryNum, resultPosition);
251     } else {
252         entriesStart = offsets[0];
253         entriesSplit = offsets[entryNum];
254         shiftOffsets(this, entryNum, entry.length());
255         if (entryNum != 0) {
256             System.arraycopy(pageBuffer, entriesStart,
257                 pageBuffer, entriesStart - entry.length(),
258                 entriesSplit - entriesStart);
259         }
260         System.arraycopy(entry.key, 0, pageBuffer, offsets[entryNum],
261                 entry.key.length);
262         System.arraycopy(entry.data, 0, pageBuffer,
263                 offsets[entryNum] + entry.key.length,
264                 entry.data.length);
265         freeStart += SIZE_OF_OFFSET;
266             
267             if (resultPosition != null) {
268                 resultPosition.entryNum = entryNum;
269                 resultPosition.matched = true;
270                 resultPosition.page = this;
271                 resultPosition.skipCount = 0;
272             }
273         return null;
274     }
275     }
276
277     /**
278      * Deletes an entry or range of entries from this page.
279      *
280      * @param first entry number of first entry to be deleted
281      * @param last entry number of last entry to be deleted
282      */
283
284     void delete(int first, int last) throws StorageException {
285
286         int startOffset, endOffset;
287     int bytesDeleted;
288     int numDeleted;
289
290     pageSource.dirtyPage(this);
291
292     startOffset = offsets[first];
293     endOffset = offsets[last+1];
294     bytesDeleted = endOffset - startOffset;
295     numDeleted = last - first + 1;
296
297     if (first != 0) {
298         System.arraycopy(pageBuffer, offsets[0],
299                  pageBuffer, offsets[0] + bytesDeleted,
300              startOffset - offsets[0]);
301     }
302     // Shift the offset entries up
303 for (int i = last + 1; i <= nextOffset; i++) {
304         offsets[i - numDeleted] = offsets[i];
305     }
306     nextOffset -= numDeleted;
307     freeStart -= numDeleted*SIZE_OF_OFFSET;
308
309     // Update the offset entries for entries that got moved down
310 if (first != 0) {
311         for (int i = 0; i < first; i++) {
312             offsets[i] += bytesDeleted;
313         }
314     }
315     }
316
317     /**
318      * Splits the entries on the current page between two pages, and inserts
319      * an entry into its correct location on one of those pages. The left
320      * page may be this page or it may be a different page. The right page is
321      * always a different page from this.
322      *
323      * @param left left page to move entries to (may be this page)
324      * @param right right page to move entries to
325      * @param entry BtreeEntry to be inserted
326      * @param newEntryNum insert location relative to the current page
327      *
328      * @return new byte array containing first key on right page
329      */
330     byte[] splitEntries(BtreePage leftBP, BtreePage rightBP, BtreeEntry entry,
331                 int newEntryNum, SearchResult resultPosition) throws StorageException {
332
333         int halfBytes;
334     int splitEntryNum;
335     int rightNewEntryNum;
336     int spaceAvailable;
337     int spaceNeeded;
338     boolean insertLeft;
339     int pageSize; // save getting this repeatedly
340 VarKeyPage left, right;
341     int rightKeyLength;
342     byte[] rightKey;
343
344     left = (VarKeyPage) leftBP;
345     right = (VarKeyPage) rightBP;
346     pageSize = btree.pageSize;
347
348     // Find the place to split at
349 spaceAvailable = pageSize - headerLength;
350     halfBytes = (spaceAvailable - nextOffset*SIZE_OF_OFFSET)/2;
351     splitEntryNum = 0;
352     while ((offsets[splitEntryNum] < halfBytes)
353             && (splitEntryNum < nextOffset)) {
354         splitEntryNum++;
355     }
356
357     // If the new entry goes on the left page, make sure it will fit there.
358 // If not, adjust the split point.
359 if (newEntryNum < splitEntryNum) {
360         do {
361             spaceNeeded = splitEntryNum*SIZE_OF_OFFSET
362                   + offsets[splitEntryNum] - offsets[0]
363               + entry.length() + SIZE_OF_OFFSET;
364         if (spaceNeeded > spaceAvailable) {
365             splitEntryNum--;
366         }
367         } while ((spaceNeeded > spaceAvailable)
368                 && (newEntryNum < splitEntryNum));
369     }
370     insertLeft = newEntryNum < splitEntryNum ? true : false;
371
372         // record position of inserted entry
373 if (resultPosition != null) {
374             resultPosition.matched = true;
375             resultPosition.skipCount = 0;
376             if (insertLeft) {
377                 resultPosition.page = left;
378                 resultPosition.entryNum = newEntryNum;
379             } else {
380                 resultPosition.page = right;
381                 resultPosition.entryNum = newEntryNum - splitEntryNum;
382             }
383         }
384         
385     if (!insertLeft) {
386         spaceNeeded = splitEntryNum*SIZE_OF_OFFSET
387                   + pageSize - offsets[splitEntryNum]
388               + entry.length() + SIZE_OF_OFFSET;
389     }
390     
391     // Move entries to right page. First copy offset table entries over,
392 // making the entry at splitEntryNum the first offset entry on the right
393 // page.
394 for (int from = splitEntryNum, to = 0; from < nextOffset;
395                             from++, to++) {
396         right.offsets[to] = this.offsets[from];
397     }
398     right.nextOffset = this.nextOffset - splitEntryNum;
399     right.offsets[right.nextOffset] = btree.pageSize;
400     right.freeStart = headerLength + right.nextOffset*SIZE_OF_OFFSET;
401
402     if (insertLeft) {
403         // Copy all the entries starting at the split point.
404 System.arraycopy(this.pageBuffer, offsets[splitEntryNum],
405                     right.pageBuffer, offsets[splitEntryNum],
406                 pageSize - offsets[splitEntryNum]);
407     } else {
408         // Adjust right page's offset table to accommodate new entry
409 rightNewEntryNum = newEntryNum - splitEntryNum;
410         shiftOffsets(right, rightNewEntryNum, entry.length());
411         right.freeStart += SIZE_OF_OFFSET;
412
413         // Copy the entries preceding the insert point
414 if (newEntryNum != splitEntryNum) {
415             System.arraycopy(this.pageBuffer, this.offsets[splitEntryNum],
416                 right.pageBuffer, right.offsets[0],
417             this.offsets[newEntryNum] - this.offsets[splitEntryNum]);
418         }
419         // Copy the new entry
420 System.arraycopy(entry.key, 0, right.pageBuffer,
421                 right.offsets[rightNewEntryNum], entry.key.length);
422         System.arraycopy(entry.data, 0, right.pageBuffer,
423                 right.offsets[rightNewEntryNum] + entry.key.length,
424                 dataLength);
425
426         // Copy the entries following the insert point
427 if (newEntryNum != nextOffset) {
428             System.arraycopy(this.pageBuffer, this.offsets[newEntryNum],
429                 right.pageBuffer, right.offsets[rightNewEntryNum + 1],
430                 pageSize - this.offsets[newEntryNum]);
431         }
432     }
433
434     // Now do the left page. Note that in the following code, "this"
435 // and "left" may or may not be the same page. If they are
436 // different, the entries are moved from this to left. Otherwise,
437 // the effect is to move the entries to their new location on the
438 // same page, being careful to move data in the right order to
439 // avoid clobbering data we still need.
440
441     // save some values in case we're overwriting this page
442 int bytesRemoved = pageSize - this.offsets[splitEntryNum];
443     int splitPoint = this.offsets[splitEntryNum];
444     int entriesStart = this.offsets[0];
445     int insertPoint = this.offsets[newEntryNum];
446
447     for (int i = 0; i < splitEntryNum; i++) {
448         left.offsets[i] = this.offsets[i] + bytesRemoved;
449     }
450     left.nextOffset = splitEntryNum;
451     left.offsets[left.nextOffset] = pageSize;
452     left.freeStart = headerLength + left.nextOffset*SIZE_OF_OFFSET;
453
454     if (!insertLeft) {
455         System.arraycopy(this.pageBuffer, entriesStart, left.pageBuffer,
456                 left.offsets[0], splitPoint - entriesStart);
457     } else {
458         // Adjust left page's offset table to accommodate new entry
459 shiftOffsets(left, newEntryNum, entry.length());
460         left.freeStart += SIZE_OF_OFFSET;
461
462         // The chunks have to be copied in this order to be sure not to
463 // overwrite existing entries before they've been copied.
464
465         // Copy the entries following the insert point
466 if (insertPoint != splitPoint) {
467             System.arraycopy(this.pageBuffer, insertPoint,
468                 left.pageBuffer, left.offsets[newEntryNum + 1],
469                 splitPoint - insertPoint);
470         }
471         // Copy the entries preceding the insert point. This chunk could
472 // get moved up or down depending on the relative sizes of
473 // bytesRemoved and the entry size.
474 if (insertPoint != entriesStart) {
475             System.arraycopy(this.pageBuffer, entriesStart,
476                 left.pageBuffer, left.offsets[0],
477             insertPoint - entriesStart);
478         }
479
480         // Copy the new entry
481 System.arraycopy(entry.key, 0, left.pageBuffer,
482                 left.offsets[newEntryNum], entry.key.length);
483         System.arraycopy(entry.data, 0, left.pageBuffer,
484                 left.offsets[newEntryNum] + entry.key.length,
485                 dataLength);
486     }
487
488     if (left != this) {
489         this.nextOffset = 0;
490         this.freeStart = headerLength;
491         this.offsets[0] = pageSize;
492     }
493
494     // Get key to insert to parent page
495 rightKeyLength = right.keyLength(0);
496     rightKey = new byte[rightKeyLength];
497     System.arraycopy(right.pageBuffer, right.offsets[0], rightKey, 0,
498                             rightKeyLength);
499     return rightKey;
500     }
501
502     private void shiftOffsets(VarKeyPage page, int entryNum, int entryLength) {
503
504     if (entryNum != page.nextOffset) {
505         // For the offsets following the entryNum, shift them all
506 // down one slot to make room for the new one.
507 for (int i = page.nextOffset; i > entryNum; i--) {
508         page.offsets[i] = page.offsets[i-1];
509         }
510     }
511     page.nextOffset++;
512     page.offsets[page.nextOffset] = btree.pageSize;
513
514     // For the offsets up to and including the one at entryNum,
515 // subtract entryLength from each offset to reflect that entry's
516 // new location on the page.
517
518     for (int i = entryNum; i >= 0; i--) {
519         page.offsets[i] -= entryLength;
520     }
521     }
522
523     boolean haveSpaceForInsert(BtreeEntry entry) {
524
525         int freeSpace = offsets[0] - freeStart;
526
527     if ((entry.length() + SIZE_OF_OFFSET) <= freeSpace) {
528         return true;
529     } else {
530         return false;
531     }
532     }
533
534     public void dumpPageHeader(PrintWriter out) {
535
536         super.dumpPageHeader(out);
537
538     out.println("\nOffsets table:\n");
539
540     for (int i = 0; i < nextOffset; i++) {
541         out.print(offsets[i] + " ");
542     }
543     out.println();
544     }
545 }
546
Popular Tags