KickJava   Java API By Example, From Geeks To Geeks.

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


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