KickJava   Java API By Example, From Geeks To Geeks.

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


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
24 /**
25  * Implementation of a BtreePage with fixed length keys and fixed length data.
26  *
27  * @author Dana Bergen
28  * @version 1.0
29  */
30 public class FixedKeyPage extends BtreePage {
31
32     int keyLength; // cached here for easy access
33
34     /**
35      * Initialize a newly-instantiated or recycled FixedKeyPage. Note that the
36      * isNew parameter pertains to whether a new page is being added to the
37      * btree, not to whether this BtreePage object is new or recycled.
38      *
39      * @param btree btree to which this page belongs
40      * @param pageId page ID in byte array
41      * @param pageBuffer page buffer
42      * @param isNew is this page new to the btree
43      */
44     public void init(Btree btree, byte[] pageId, byte[] pageBuffer,
45                 boolean isNew) throws StorageException {
46
47         super.init(btree, pageId, pageBuffer, isNew);
48     keyLength = btree.keyInfo.getLength();
49     }
50
51     /**
52      * Returns the number of entries currently on this page.
53      *
54      * @return number of entries on this page
55      */
56     int numEntries() {
57         return (freeStart - headerLength)/(keyLength + dataLength);
58     }
59
60     /**
61      * Returns the offset in the page where a specified entry's key is located.
62      *
63      * @param entryNum entry number
64      *
65      * @return offset of entryNum's key
66      */
67     int keyOffset(int entryNum) {
68         return headerLength + (entryNum * (keyLength + dataLength));
69     }
70
71     /**
72      * Returns the length of a specified entry's key.
73      *
74      * @param entryNum entry number
75      *
76      * @return length of entryNum's key
77      */
78     int keyLength(int entryNum) {
79         return keyLength;
80     }
81     
82     /**
83      * Returns the data value for the specified entry.
84      *
85      * @param entryNum entry number
86      *
87      * @return new byte array containing the data at entryNum
88      */
89     byte[] getData(int entryNum) {
90         byte[] data = new byte[dataLength];
91     System.arraycopy(pageBuffer, keyOffset(entryNum) + keyLength,
92                 data, 0, dataLength);
93     return data;
94     }
95
96     /**
97      * Returns the key for the specified entry.
98      *
99      * @param entryNum entry number
100      *
101      * @return new byte array containing the key at entryNum
102      */
103     byte[] getKey(int entryNum) {
104         byte[] key = new byte[keyLength];
105     System.arraycopy(pageBuffer, keyOffset(entryNum), key, 0, keyLength);
106     return key;
107     }
108
109     /*
110      * Inserts an entry at the specified location.
111      *
112      * @param entry BtreeEntry to be inserted
113      * @param entryNum location where entry is to be inserted
114      *
115      * @return If a split occurred, an entry to be inserted in this page's
116      * parent is returned; otherwise null is returned.
117      */
118     BtreeEntry insert(BtreeEntry entry, int entryNum, SearchResult resultPosition)
119                     throws StorageException {
120
121         pageSource.dirtyPage(this);
122
123         if (btree.pageSize - freeStart >= entry.length()) {
124         insertHere(entry, entryNum, resultPosition);
125         return null;
126     } else {
127         return split(entry, entryNum, resultPosition);
128     }
129     }
130
131     /*
132      * Replaces the entry at the specified location with the passed-in entry.
133      * Since data is fixed length, we know it will fit.
134      *
135      * @param entry BtreeEntry to be inserted
136      * @param entryNum location where entry is to be inserted
137      *
138      * @return Always returns null
139      */
140     BtreeEntry replace(BtreeEntry entry, int entryNum, SearchResult resultPosition) throws StorageException {
141
142         pageSource.dirtyPage(this);
143         int offset = keyOffset(entryNum) + keyLength;
144     System.arraycopy(entry.data, 0, pageBuffer, offset, entry.data.length);
145         
146         // record position of inserted entry
147 if (resultPosition != null) {
148             resultPosition.matched = true;
149             resultPosition.skipCount = 0;
150             resultPosition.page = this;
151             resultPosition.entryNum = entryNum;
152         }
153         
154     // We didn't split so there is no parent entry to return
155 return null;
156     }
157     
158     private void insertHere(BtreeEntry entry, int entryNum, SearchResult resultPosition) {
159
160         int offset;
161
162         
163         
164     offset = keyOffset(entryNum);
165     if (offset != freeStart) {
166         /* Shift entries down to make room for this one */
167         System.arraycopy(pageBuffer, offset,
168             pageBuffer, offset + entry.length(),
169             freeStart - offset);
170     }
171     System.arraycopy(entry.key, 0, pageBuffer, offset, keyLength);
172     System.arraycopy(entry.data, 0,
173                 pageBuffer, offset+keyLength, dataLength);
174     freeStart += keyLength + dataLength;
175         
176         if (resultPosition != null) {
177             resultPosition.entryNum = entryNum;
178             resultPosition.matched = true;
179             resultPosition.page = this;
180             resultPosition.skipCount = 0;
181         }
182     }
183
184     /**
185      * Deletes an entry or range of entries from this page.
186      *
187      * @param first entry number of first entry to be deleted
188      * @param last entry number of last entry to be deleted
189      */
190     void delete(int firstEntry, int lastEntry) throws StorageException {
191
192         int startOffset, endOffset;
193     
194     pageSource.dirtyPage(this);
195     
196     startOffset = keyOffset(firstEntry);
197     endOffset = keyOffset(lastEntry+1);
198     if (freeStart != endOffset) {
199         System.arraycopy(pageBuffer, endOffset, pageBuffer, startOffset,
200                 freeStart - endOffset);
201     }
202     freeStart -= endOffset - startOffset;
203     }
204
205     /**
206      * Splits the entries on the current page between two pages, and inserts
207      * an entry into its correct location on one of those pages. The left
208      * page may be this page or it may be a different page. The right page is
209      * always a different page from this.
210      *
211      * @param left left page to move entries to (may be this page)
212      * @param right right page to move entries to
213      * @param entry BtreeEntry to be inserted
214      * @param newEntryNum insert location relative to the current page
215      *
216      * @return new byte array containing first key on right page
217      */
218     byte[] splitEntries(BtreePage left, BtreePage right, BtreeEntry entry,
219                 int entryNum, SearchResult resultPosition) {
220     
221     int entryLength;
222     int offset;
223     int midpoint;
224         int half;
225     int copyLength;
226     boolean insertLeft;
227     byte[] rightKey;
228
229     offset = keyOffset(entryNum);
230     entryLength = keyLength + dataLength;
231         half = numEntries()/2;
232     midpoint = headerLength + half*entryLength;
233     insertLeft = offset < midpoint;
234     
235     // Move second half of entries to right page.
236 if (insertLeft) {
237         copyLength = this.freeStart - midpoint;
238     } else {
239         // First just copy entries up to the insert point
240 copyLength = offset - midpoint;
241     }
242         
243         // record position of inserted entry
244 if (resultPosition != null) {
245             resultPosition.matched = true;
246             resultPosition.skipCount = 0;
247             if (insertLeft) {
248                 resultPosition.page = left;
249                 resultPosition.entryNum = entryNum;
250             } else {
251                 resultPosition.page = right;
252                 resultPosition.entryNum = entryNum - half;
253             }
254         }
255         
256     if (copyLength > 0) {
257         System.arraycopy(this.pageBuffer, midpoint, right.pageBuffer,
258             right.freeStart, copyLength);
259         right.freeStart += copyLength;
260     }
261     if (!insertLeft) {
262         System.arraycopy(entry.key, 0, right.pageBuffer, right.freeStart,
263                                     keyLength);
264         right.freeStart += keyLength;
265         System.arraycopy(entry.data, 0, right.pageBuffer, right.freeStart,
266                                     dataLength);
267         right.freeStart += dataLength;
268         if (this.freeStart != offset) {
269             System.arraycopy(this.pageBuffer, offset, right.pageBuffer,
270             right.freeStart, this.freeStart - offset);
271             right.freeStart += this.freeStart - offset;
272         }
273     }
274     
275     // Move first half of entries to left page, if left page is new.
276 // Either way, insert the new entry if it belongs here.
277 if (left != this) {
278         if (insertLeft) {
279         copyLength = offset - headerLength;
280         } else {
281         copyLength = midpoint - headerLength;
282         }
283         if (copyLength > 0) {
284             System.arraycopy(this.pageBuffer, headerLength,
285                 left.pageBuffer, left.freeStart, copyLength);
286         }
287     }
288
289     if (insertLeft) {
290         if (midpoint != offset) {
291             System.arraycopy(this.pageBuffer, offset, left.pageBuffer,
292             offset+entryLength, midpoint - offset);
293         }
294         System.arraycopy(entry.key, 0, left.pageBuffer, offset, keyLength);
295         System.arraycopy(entry.data, 0, left.pageBuffer, offset + keyLength, dataLength);
296         left.freeStart = midpoint + entryLength;
297     } else {
298         left.freeStart = midpoint;
299     }
300     if (left != this) {
301         // All entries were moved off of this page
302 this.freeStart = headerLength;
303     }
304     rightKey = new byte[keyLength];
305     System.arraycopy(right.pageBuffer, headerLength, rightKey, 0, keyLength);
306     return rightKey;
307     }
308 }
309
Popular Tags