|
What this is
Other links
The source code/* * Sun Public License Notice * * The contents of this file are subject to the Sun Public License * Version 1.0 (the "License"). You may not use this file except in * compliance with the License. A copy of the License is available at * http://www.sun.com/ * * The Original Code is NetBeans. The Initial Developer of the Original * Code is Sun Microsystems, Inc. Portions Copyright 1997-2001 Sun * Microsystems, Inc. All Rights Reserved. */ package org.netbeans.mdr.persistence.btreeimpl.btreeindex; import org.netbeans.mdr.persistence.*; import java.io.*; /** * These pages contain keys which are too big to be handled normally. * Each BigKeyPage contains a single key or a portion of a single key, * and possibly the data associated with the key. All of the BigKeyPages * are in a single chain attached to the root (i.e., root.nextPage points to * the first BigKeyPage). They are maintained in key order. * * The first page for a given key contains the full key length in keyLength. * If the key doesn't fit on a single page it is continued on subsequent pages. * If the data fits completely on the same page as the last portion of the key, * it is put there; otherwise, it is put on a separate page. * * When a big key record gets deleted, the pages are removed from the chain * and the space is never reused. * * This is not a very efficient implementation because we don't really expect * it to be used (it gets used if a key is longer than 670 bytes). * * @author Dana Bergen * @version 1.0 */ public class BigKeyPage extends BtreePage { private int keyLength; public BigKeyPage() {} /** * Initialize a newly-instantiated or recycled BigKeyPage. Note that the * isNew parameter pertains to whether a new page is being added to the * btree, not to whether this BtreePage object is new or recycled. * * @param btree btree to which this page belongs * @param pageId page ID in byte array * @param pageBuffer page buffer * @param isNew is this page new to the btree */ public void init(Btree btree, byte[] pageId, byte[] pageBuffer, boolean isNew) throws StorageException { if (initialized) { /* This page was found in cache and doesn't need initialization */ return; } super.init(btree, pageId, pageBuffer, isNew); if (isNew) { keyLength = 0; flags = 0; } else { /* keyLength is stored in the same slot as freeStart which * is not used by BigKeyPage */ keyLength = freeStart; } } /** * Write BigKeyPage header data to the page buffer. */ public void store() { freeStart = keyLength; super.store(); } /** * Returns the number of entries currently on this page. * * @return always returns 1 */ int numEntries() { return 1; } /** * Returns the offset in the page where a specified entry's key is located. * * @param entryNum entry number * * @return offset of entryNum's key */ int keyOffset(int entryNum) { return headerLength; } /** * Returns the length of a specified entry's key. * * @param entryNum entry number * * @return length of entryNum's key */ int keyLength(int entryNum) { return keyLength; } /** * Returns the data value for the specified entry. * * @param entryNum entry number * * @return new byte array containing the data at entryNum */ byte[] getData(int entryNum) throws StorageException { byte[] data = new byte[dataLength]; int pageSpace = btree.pageSize - headerLength; if ((keyLength + dataLength) < pageSpace) { System.arraycopy(pageBuffer, headerLength + keyLength, data, 0, dataLength); } else { SearchResult location = getDataLocation(); System.arraycopy(location.page.pageBuffer, location.entryNum, data, 0, dataLength); if (location.page != this) { pageSource.unpinPage(location.page); } } return data; } private SearchResult getDataLocation() throws StorageException { BtreePage current; byte[] next; int left; int pageSpace = btree.pageSize - headerLength; /* Find the last page of this key */ current = this; left = keyLength; while (left > pageSpace) { left -= pageSpace; next = current.nextPage; if (current != this) { pageSource.unpinPage(current); } current = pageSource.getPage(next, btree); } if ((left + dataLength) <= pageSpace) { /* The data is on the current page */ return new SearchResult(true, headerLength+left, current); } else { /* The data is on the next page */ next = current.nextPage; if (current != this) { pageSource.unpinPage(current); } current = pageSource.getPage(next, btree); return new SearchResult(true, headerLength, current); } } /** * Returns the key for the specified entry. * * @param entryNum entry number * * @return new byte array containing the key at entryNum */ byte[] getKey(int entryNum) throws StorageException { byte[] next; byte[] key = new byte[keyLength]; int pageSpace = btree.pageSize - headerLength; if (keyLength < pageSpace) { System.arraycopy(pageBuffer, headerLength, key, 0, keyLength); } else { BtreePage page = this; int left = keyLength; while (left > pageSpace) { System.arraycopy(page.pageBuffer, headerLength, key, keyLength - left, pageSpace); left -= pageSpace; next = page.nextPage; if (page != this) { pageSource.unpinPage(page); } page = pageSource.getPage(next, btree); } if (left > 0) { System.arraycopy(page.pageBuffer, headerLength, key, keyLength - left, left); } if (page != this) { pageSource.unpinPage(page); } } return key; } /** * Replaces the entry at the specified location with the passed-in entry. * Since data is fixed length, we know it will fit. * * @param entry BtreeEntry to be inserted * @param entryNum location where entry is to be inserted * * @return Always returns null */ BtreeEntry replace(BtreeEntry entry, int entryNum, SearchResult resultPosition) throws StorageException { SearchResult location; pageSource.dirtyPage(this); location = getDataLocation(); if (location.page != this) { pageSource.dirtyPage(location.page); } System.arraycopy(entry.data, 0, location.page.pageBuffer, location.entryNum, entry.data.length); if (location.page != this) { pageSource.unpinPage(location.page); } // record position of inserted entry if (resultPosition != null) { resultPosition.matched = true; resultPosition.skipCount = 0; resultPosition.page = this; resultPosition.entryNum = entryNum; } return null; } /* * Inserts an entry at the specified location. * * @param entry BtreeEntry to be inserted * @param entryNum 0 if entry should be inserted before this one * 1 if we're pointing to the last entry, and this entry * should be inserted after it * */ BtreeEntry insert(BtreeEntry entry, int entryNum, SearchResult resultPosition) throws StorageException { BigKeyPage current, previous, newNext; BtreePage newPrevious; byte[] next; int left; int pageSpace = btree.pageSize - headerLength; if (keyLength == 0) { /* This is the first BigKeyPage and it's already linked */ current = this; pageSource.dirtyPage(current); newNext = null; } else { /* Create the first new page for the new entry */ current = pageSource.newBigKeyPage(btree); if (entryNum == 0) { /* Insert before this page */ newPrevious = pageSource.getPage(this.previousPage, btree); newNext = this; pageSource.dirtyPage(this); } else { /* Insert at end of chain */ newNext = null; newPrevious = this; next = newPrevious.nextPage; while (!pageSource.isNoPage(next)) { if (newPrevious != this) { pageSource.unpinPage(newPrevious); } newPrevious = pageSource.getPage(next, btree); next = newPrevious.nextPage; } } pageSource.dirtyPage(newPrevious); linkNewPage(current, newPrevious, newNext); pageSource.unpinPage(newPrevious); } // record position of inserted entry if (resultPosition != null) { resultPosition.matched = true; resultPosition.skipCount = 0; resultPosition.page = current; resultPosition.entryNum = entryNum; // [PENDING] } current.keyLength = entry.key.length; left = entry.key.length; while (left > pageSpace) { System.arraycopy(entry.key, entry.key.length - left, current.pageBuffer, headerLength, pageSpace); left -= pageSpace; previous = current; current = pageSource.newBigKeyPage(btree); linkNewPage(current, previous, newNext); if (previous != this) { pageSource.unpinPage(previous); } } if (left > 0) { System.arraycopy(entry.key, entry.key.length - left, current.pageBuffer, headerLength, left); } if ((left + dataLength) > pageSpace) { previous = current; current = pageSource.newBigKeyPage(btree); linkNewPage(current, previous, newNext); if (previous != this) { pageSource.unpinPage(previous); } left = 0; } System.arraycopy(entry.data, 0, current.pageBuffer, headerLength + left, dataLength); if (current != this) { pageSource.unpinPage(current); } if ((newNext != null) && (newNext != this)) { pageSource.unpinPage(newNext); } return null; } private void linkNewPage(BtreePage newPage, BtreePage left, BtreePage right) { System.arraycopy(left.pageId, 0, newPage.previousPage, 0, left.pageId.length); System.arraycopy(left.nextPage, 0, newPage.nextPage, 0, left.pageId.length); System.arraycopy(newPage.pageId, 0, left.nextPage, 0, newPage.pageId.length); if (right != null) { System.arraycopy(newPage.pageId, 0, right.previousPage, 0, newPage.pageId.length); } } /** * Deletes an entry or range of entries from this page. * * @param first ignored * @param last ignored */ void delete(int first, int last) throws StorageException { BtreePage next, previous, current; int pageSpace = btree.pageSize - headerLength; int left = keyLength; current = this; previous = pageSource.getPage(this.previousPage, btree); pageSource.dirtyPage(previous); while (left > pageSpace) { left -= pageSpace; next = pageSource.getPage(current.nextPage, btree); if (current != this) { pageSource.unpinPage(current); } current = next; } if ((left + dataLength) > pageSpace) { /* The data is on the next page */ next = pageSource.getPage(current.nextPage, btree); pageSource.unpinPage(current); current = next; } /* current is the last page to be deleted */ System.arraycopy(current.nextPage, 0, previous.nextPage, 0, current.nextPage.length); if (!pageSource.isNoPage(current.nextPage)) { next = pageSource.getPage(current.nextPage, btree); pageSource.dirtyPage(next); System.arraycopy(previous.pageId, 0, next.previousPage, 0, previous.pageId.length); pageSource.unpinPage(next); } if (previous.isRoot() && pageSource.isNoPage(previous.nextPage)) { btree.unsetHasBigKeys(); } pageSource.unpinPage(previous); if (current != this) { pageSource.unpinPage(current); } } /* * Do nothing. */ byte[] splitEntries(BtreePage leftBP, BtreePage rightBP, BtreeEntry entry, int newEntryNum, SearchResult resultPosition) throws StorageException { return null; } /** * Search for the key starting from this page. We do this in a very * inefficient way. */ SearchResult searchBigKeys(byte[] key) throws StorageException { BigKeyPage current, next; byte[] currentKey; SearchResult result; byte compare; next = this; result = null; do { current = next; currentKey = current.getKey(0); compare = btree.keyInfo.compare(key, currentKey, 0, currentKey.length); if (compare == EntryTypeInfo.EQUAL) { result = new SearchResult(true, 0, current); } else if (compare == EntryTypeInfo.LESS) { result = new SearchResult(false, 0, current); } else { next = current.getNextKeyStart(); if (current != this) { pageSource.unpinPage(current); } } } while ((result == null) && (next != null)); if (result == null) { result = new SearchResult(false, 1, current); } return result; } /* * Get the next entry, starting from the passed in result. The * result is updated to point to the next entry and indicate whether * it matched the key. If key is null, it is considered a match as long * as any record was found. * * If testOnly is true, result.matched is updated but result.page and * result.entry are left unchanged. */ static void getNext(byte[] key, SearchResult result, boolean testOnly) throws StorageException { BigKeyPage page; byte[] currentKey; Btree btree = result.page.btree; if (result.entryNum == -1) { page = (BigKeyPage)result.page; if (!testOnly) { result.entryNum = 0; } } else { page = ((BigKeyPage)result.page).getNextKeyStart(); } if (page == null) { result.matched = false; result.entryNum = 1; return; } if (key != null) { currentKey = page.getKey(0); if (btree.keyInfo.compare(key, currentKey, 0, currentKey.length) == EntryTypeInfo.EQUAL) { result.matched = true; } else { result.matched = false; } } else { result.matched = true; } if (!testOnly) { result.page = page; } } BigKeyPage getNextKeyStart() throws StorageException { BigKeyPage next, currentDataPage; currentDataPage = (BigKeyPage) getDataLocation().page; if (!pageSource.isNoPage(currentDataPage.nextPage)) { next = (BigKeyPage) pageSource.getPage(currentDataPage.nextPage, btree); } else { next = null; } if (currentDataPage != this) { pageSource.unpinPage(currentDataPage); } return next; } /* * Gets the previous entry location. This only operates within the * big key chain, i.e., calling getPrevious when positioned at the first * big key entry will not backup to the last normal entry. Instead, * it will return the location of the first big key, matched = false, * and set entryNum to -1. */ static void getPrevious(byte[] key, SearchResult result, boolean testOnly) throws StorageException { BigKeyPage page; byte[] currentKey; Btree btree = result.page.btree; page = ((BigKeyPage)result.page).getPreviousKeyStart(); if (page == null) { if (!testOnly) { result.entryNum = -1; } result.matched = false; return; } if (key != null) { currentKey = page.getKey(0); if (btree.keyInfo.compare(key, currentKey, 0, currentKey.length) == EntryTypeInfo.EQUAL) { result.matched = true; } else { result.matched = false; } } else { result.matched = true; } if (!testOnly) { result.page = page; } } BigKeyPage getPreviousKeyStart() throws StorageException { int currentLength = 0; BtreePage current, previous; current = this; do { previous = pageSource.getPage(current.previousPage, btree); if (current != this) { pageSource.unpinPage(current); } current = previous; if (!(current instanceof BigKeyPage)) { /* we're back at the root */ pageSource.unpinPage(current); current = null; } else { currentLength = ((BigKeyPage)current).keyLength; } } while ((current != null) && (currentLength == 0)); return (BigKeyPage)current; } /* * Make the first BigKeyPage and link it to the root. */ static BtreePage makeFirst(BtreePage root, BtreePageSource pageSource) throws StorageException { BtreePage newPage; newPage = pageSource.newBigKeyPage(root.btree); System.arraycopy(newPage.pageId, 0, root.nextPage, 0, newPage.pageId.length); System.arraycopy(root.pageId, 0, newPage.previousPage, 0, newPage.pageId.length); root.btree.setHasBigKeys(); return newPage; } void dumpLevel(PrintWriter out) throws StorageException { BigKeyPage current, next; current = this; do { current.dumpPage(out); next = current.getNextKeyStart(); if (current != this) { pageSource.unpinPage(current); } current = next; } while (current != null); } public void dumpPageHeader(PrintWriter out) { super.dumpPageHeader(out); out.println("Key length: " + keyLength + "\n"); } public void dumpPageEntries(PrintWriter out) throws StorageException { out.println("\nPage entries:\n\n"); out.print(btree.keyInfo.fromBuffer(getKey(0)) + ", "); out.println(btree.dataInfo.fromBuffer(getData(0))); } } |
... this post is sponsored by my books ... | |
#1 New Release! |
FP Best Seller |
Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.
A percentage of advertising revenue from
pages under the /java/jwarehouse
URI on this website is
paid back to open source projects.