pkg://jisp2-2.5.1-2jpp.src.rpm:66980/jisp-2.5.1-source.tar.gz
info downloads
jisp-2.5.1/ 0040755 0001750 0001750 00000000000 07641723212 011546 5 ustar scott scott jisp-2.5.1/com/ 0040755 0001750 0001750 00000000000 07641722715 012333 5 ustar scott scott jisp-2.5.1/com/coyotegulch/ 0040755 0001750 0001750 00000000000 07641722716 014661 5 ustar scott scott jisp-2.5.1/com/coyotegulch/jisp/ 0040755 0001750 0001750 00000000000 07641722716 015626 5 ustar scott scott jisp-2.5.1/com/coyotegulch/jisp/BTreeException.java 0100644 0001750 0001750 00000005526 07633366244 021357 0 ustar scott scott //-----------------------------------------------------------------------
// Java Indexed Serialization Package
// ----------------------------------
// BTreeException.java
//-----------------------------------------------------------------------
//
// COPYRIGHT NOTICE, DISCLAIMER, and LICENSE:
//
// If you modify this file, you may insert additional notices
// immediately following this sentence.
//
// Copyright 1996-2003 Scott Robert Ladd.
// All rights reserved, except as noted herein.
//
// This computer program source file is supplied "AS IS". Scott Robert
// Ladd (hereinafter referred to as "Author") disclaims all warranties,
// expressed or implied, including, without limitation, the warranties
// of merchantability and of fitness for any purpose. The Author
// assumes no liability for direct, indirect, incidental, special,
// exemplary, or consequential damages, which may result from the use
// of this software, even if advised of the possibility of such damage.
//
// The Author hereby grants anyone permission to use, copy, modify, and
// distribute this source code, or portions hereof, for any legal purpose,
// without fee, subject to the following restrictions:
//
// 1. The origin of this source code must not be misrepresented.
//
// 2. Altered versions must be plainly marked as such and must not
// be misrepresented as being the original source.
//
// 3. This Copyright notice may not be removed or altered from any
// source or altered source distribution.
//
// The Author specifically permits (without fee) and encourages the use
// of this source code for entertainment, education, or decoration. If
// you use this source code in a product, acknowledgment is not required
// but would be appreciated.
//
// Acknowledgement:
// This license is based on the wonderful simple license that
// accompanies libpng.
//
//-----------------------------------------------------------------------
// For more information on this software package, please visit
// Scott's web site, Coyote Gulch Productions, at:
//
// http://www.coyotegulch.com
//-----------------------------------------------------------------------
package com.coyotegulch.jisp;
import java.io.*;
/**
* Standard exception type thrown by B-Tree index classes.
*
* @author Scott Robert Ladd
* @see com.coyotegulch.jisp.BTreeIndex
*/
public class BTreeException extends IOException
{
/**
* Constructs a new <code>BTreeException</code> with a <code>null</code> error message string.
* <p>
*/
public BTreeException()
{
super();
}
/**
* Constructs a new <code>BTreeException</code> with a specific error message string.
*
* @param message Error message string.
*/
public BTreeException(String message)
{
super(message);
}
}
jisp-2.5.1/com/coyotegulch/jisp/BTreeIndex.java 0100755 0001750 0001750 00000126360 07641135213 020460 0 ustar scott scott //-----------------------------------------------------------------------
// Java Indexed Serialization Package
// ----------------------------------
// BTreeIndex.java
//-----------------------------------------------------------------------
//
// COPYRIGHT NOTICE, DISCLAIMER, and LICENSE:
//
// If you modify this file, you may insert additional notices
// immediately following this sentence.
//
// Copyright 1996-2003 Scott Robert Ladd.
// All rights reserved, except as noted herein.
//
// This computer program source file is supplied "AS IS". Scott Robert
// Ladd (hereinafter referred to as "Author") disclaims all warranties,
// expressed or implied, including, without limitation, the warranties
// of merchantability and of fitness for any purpose. The Author
// assumes no liability for direct, indirect, incidental, special,
// exemplary, or consequential damages, which may result from the use
// of this software, even if advised of the possibility of such damage.
//
// The Author hereby grants anyone permission to use, copy, modify, and
// distribute this source code, or portions hereof, for any legal purpose,
// without fee, subject to the following restrictions:
//
// 1. The origin of this source code must not be misrepresented.
//
// 2. Altered versions must be plainly marked as such and must not
// be misrepresented as being the original source.
//
// 3. This Copyright notice may not be removed or altered from any
// source or altered source distribution.
//
// The Author specifically permits (without fee) and encourages the use
// of this source code for entertainment, education, or decoration. If
// you use this source code in a product, acknowledgment is not required
// but would be appreciated.
//
// Acknowledgement:
// This license is based on the wonderful simple license that
// accompanies libpng.
//
//-----------------------------------------------------------------------
// For more information on this software package, please visit
// Scott's web site, Coyote Gulch Productions, at:
//
// http://www.coyotegulch.com
//-----------------------------------------------------------------------
package com.coyotegulch.jisp;
import java.text.*;
import java.io.*;
import java.util.*;
/**
* Associates a <i>key</i> value with a <code>long</code> reference. In general, the
* reference is a file pointer that locates a serializable object associated with
* the key value; however, the index itself does not apply semantics to the reference.
* The user of index interprets the reference according to its design; an
* <code>IndexedObjectDatabase</code>, for example, uses the reference to record the
* file position of a <code>Serializable</code> object with a specific key.
* <p>
* Use the <code>IndexedObjectDatabase.attachIndex</code> method to attach a
* <code>BTreeIndex</code> to a database. A database updates all attached indexes
* when it writes or removes objects from its file. This is the most common use
* of <code>BTreeIndex</code>es.
* <p>
* It's important to realize that each key is associated with a <code>long</code>
* <i>reference</i> which is interpretted by the user. For example, the <code>
* IndexedObjectDatabase</code> class stores a file pointer in reference, thus
* associating a key value with a serialized object stored in the database. You can
* also use the reference as an index into an array, or in any other way appropriate
* to your application. It is even possible associate the same reference value with
* different keys.
* <p>
*
* @author Scott Robert Ladd
* @see com.coyotegulch.jisp.ObjectIndex
* @see com.coyotegulch.jisp.IndexedObjectDatabase
*/
public class BTreeIndex extends BTreePageFile implements ObjectIndex
{
// exceptions
private static final KeyNotFound err_key_not_found = new KeyNotFound("key not found in BTreeIndex");
private static final DuplicateKey err_duplicate_key = new DuplicateKey("duplicate key found in BTreeIndex");
// inner classes
private class SearchResult
{
public boolean m_found;
public Page m_page;
public int m_position;
// constructor
public SearchResult(boolean found, Page page, int position)
{
m_found = found;
m_page = page;
m_position = position;
}
}
// working storage
private Page m_root;
private IndexedObjectDatabase m_database = null;
/**
* Calculates a suggested value for a B-tree order, based on a given number of records and a maximum
* "height" for the B-tree structure.
*
* @param numRecords number of records expected in a B-tree index
* @param maxHeight maximum allowable height for the B-tree (i.e., maximum number of pages to be read
* when searching for a key)
* @return a suggested value for oder, to be used in constructing a new BTreeIndex
* @see com.coyotegulch.jisp.BTreeIndex
*/
public static int computeOrder(int numRecords, int maxHeight)
{
int result;
if ((numRecords < 1) || (maxHeight < 1))
result = 7;
else
result = (int)Math.pow((double)numRecords,1.0 / (double)(maxHeight)) + 1;
return result;
}
/**
* Opens an existing file, <code>name</code>, as a <code>BTreeIndex</code>.
*
* @param name name of the external index file to be opened.
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
*/
public BTreeIndex(String name) throws IOException, ClassNotFoundException
{
// invoke superclass constructor
super(name);
// read root page of index
m_root = readRoot();
}
/**
* Creates the specified file as a <code>BTreeIndex</code>, using the given order and
* <code>null</code> key value. The null key is a "blank" key used in padding empty
* entries in B-tree pages. Obtain a null key for any key type by either invoking the
* default constructor or calling the <code>KeyObject.makeNullKey</code> method.
*
* @param name name of the external index file to be opened.
* @param order order (page size) the the B-Tree. This should be an odd number
* greater than or equal to five (5). <code>BTreeIndex</code> will
* increment any even numbered order to the next consecutive odd number
* (if you specfy an order of 32, the index will actually have an order
* of 33). Also, an order less than 5 will be set to 5 automatically.
* @param nullKey identifies a blank table entry and provides type-checking on new
* keys added to the index. All keys added to the index must have the
* same type as <code>nullkey</code>.
* @param hasDupes Determines whether or not this index allows duplicate keys.
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @see com.coyotegulch.jisp.KeyObject
*/
public BTreeIndex(String name, int order, KeyObject nullKey, boolean hasDupes) throws IOException, ClassNotFoundException
{
// invoke superclass constructor
super(name,order,nullKey,hasDupes);
// read root page of index
m_root = readRoot();
}
/**
* Closes an open <code>BTreeIndex</code> and empties the page cache to release memory.
*/
public void close() throws IOException
{
emptyPageCache();
super.close();
}
/**
* Returns the number of keys stored in this index. It is incremented when a new
* key is added, and decremented when a key is removed.
*
* @return the number of keys stored in this index
*/
public int count()
{
return m_header.m_count;
}
/**
* Returns the number of keys added to this index since its creation. This value is
* incremented when a new key is added, but (unlike <code>count</count>, it is never
* decremented. In an index with a one-to-one correspondence between records and keys,
* this value provides a unique "record ID".
*
* @return the number of keys added to this index since its creation
*/
public long ticker()
{
return m_header.m_ticker;
}
/**
* Insert a key into the index, associating a "reference" value with the given key.
*
* @param key identifies the record to be read
* @param reference reference associated with key
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @throws DuplicateKey when inserting a duplicate key into an index that does not
* support duplicates
* @see com.coyotegulch.jisp.DuplicateKey
* @see com.coyotegulch.jisp.KeyObject
*/
public void insertKey(KeyObject key, long reference) throws IOException, ClassNotFoundException
{
// search for the key
SearchResult ins = searchInsert(m_root,key);
if (ins.m_found && !m_header.m_hasDupes)
throw err_duplicate_key;
else
{
writeKey(ins,key,reference);
++m_header.m_count;
++m_header.m_ticker;
rewriteHeader();
}
}
/**
* Replaces the reference for the given key. The method replaces the <i>first</i> occurrence
* of the key, if the index includes duplicates.
*
* @param key identifies the record being replaced
* @param reference new reference to be associated with key
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @throws KeyNotFound when the specified key can not be found in the index
* @see com.coyotegulch.jisp.DuplicateKey
* @see com.coyotegulch.jisp.KeyObject
*/
public void replaceKey(KeyObject key, long reference) throws IOException, ClassNotFoundException
{
// search for the key
SearchResult ins = search(m_root,key,false);
if (ins.m_found)
{
// store new data record pointer
ins.m_page.m_recPtr[ins.m_position] = reference;
// rewrite modified page
write(ins.m_page,false);
}
else
{
throw err_key_not_found;
}
m_root = readRoot();
}
/**
* Replaces or inserts the reference for the given key. If the key exists, the reference
* associated with that key is replaced; if the key does not exist, a new key is
* inserted into the database with the given reference. If the index supports duplicate keys,
* the first-found occurence of the key will be replaced.
*
* @param key identifies the record to be stored
* @param position reference associated with key
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @see com.coyotegulch.jisp.KeyObject
*/
public void storeKey(KeyObject key, long reference) throws IOException, ClassNotFoundException
{
// search for the key
SearchResult ins = search(m_root,key,false);
if (ins.m_found)
{
// store new data record pointer
ins.m_page.m_recPtr[ins.m_position] = reference;
// rewrite modified page
write(ins.m_page,false);
}
else
{
writeKey(ins,key,reference);
++m_header.m_count;
++m_header.m_ticker;
rewriteHeader();
}
}
/**
* Find the position of the object associated with a given key.
*
* @param key a key to be sought in the index
* @return Position of the record associated with <code>key</code>.
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @throws KeyNotFound when the specified key can not be found in the index
* @see com.coyotegulch.jisp.KeyNotFound
* @see com.coyotegulch.jisp.KeyObject
*/
public long findKey(KeyObject key) throws IOException, ClassNotFoundException
{
return findKey(key,false);
}
/**
* Find the position of an object associated with a given key, or its successor.
*
* @param key a key to be sought in the index
* @param allowNext when <code>true</code>, <code>findKey</code> will return
* the reference associated with the key greater than or
* equal to <code>key</code>
* @return The reference associated with <code>key</code>.
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @throws KeyNotFound when the specified key can not be found in the index
* @see com.coyotegulch.jisp.KeyNotFound
* @see com.coyotegulch.jisp.KeyObject
*/
public long findKey(KeyObject key, boolean allowNext) throws IOException, ClassNotFoundException
{
// search for key
SearchResult result = search(m_root,key,allowNext);
if (result.m_found)
return result.m_page.m_recPtr[result.m_position];
else
throw err_key_not_found;
}
/**
* Removes the given key from the index. If the index contains duplicates of <code>key</code>,
* the first key found will be deleted.
*
* @param key A key identifying the record to be read.
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @throws KeyNotFound when the specified key can not be found in the index
* @see com.coyotegulch.jisp.KeyNotFound
* @see com.coyotegulch.jisp.KeyObject
*/
public void removeKey(KeyObject key) throws IOException, ClassNotFoundException
{
// search for key
SearchResult del = search(m_root,key,false);
if (del.m_found == false)
throw err_key_not_found;
// is this a leaf node?
if (del.m_page.m_link[0] == NULL_PTR)
{
// remove key from leaf
--del.m_page.m_header.m_numKeys;
// slide keys left over deleted one
for (int n = del.m_position; n < del.m_page.m_header.m_numKeys; ++n)
{
del.m_page.m_key[n] = del.m_page.m_key[n + 1];
del.m_page.m_recPtr[n] = del.m_page.m_recPtr[n + 1];
}
del.m_page.m_key[del.m_page.m_header.m_numKeys] = m_header.m_nullKey.makeNullKey();
del.m_page.m_recPtr[del.m_page.m_header.m_numKeys] = NULL_PTR;
// write changed record
write(del.m_page,false);
// adjust the tree, if needed
if (del.m_page.m_header.m_numKeys < m_header.m_minKeys)
adjustTree(del.m_page);
}
else // deleting an internal page
{
// get the successor page
Page sucPage = read(del.m_page.m_link[del.m_position + 1]);
while (sucPage.m_link[0] != NULL_PTR)
sucPage = read(sucPage.m_link[0]);
// first key is the "swappee"
del.m_page.m_key[del.m_position] = sucPage.m_key[0];
del.m_page.m_recPtr[del.m_position] = sucPage.m_recPtr[0];
// delete swapped key from successor page
--sucPage.m_header.m_numKeys;
for (int n = 0; n < sucPage.m_header.m_numKeys; ++n)
{
sucPage.m_key[n] = sucPage.m_key[n + 1];
sucPage.m_recPtr[n] = sucPage.m_recPtr[n + 1];
sucPage.m_link[n + 1] = sucPage.m_link[n + 2];
}
sucPage.m_key[sucPage.m_header.m_numKeys] = m_header.m_nullKey.makeNullKey();
sucPage.m_recPtr[sucPage.m_header.m_numKeys] = NULL_PTR;
sucPage.m_link[sucPage.m_header.m_numKeys + 1] = NULL_PTR;
// write modified records
write(del.m_page,(del.m_page.m_header.m_parentPtr == NULL_PTR)); // false);
write(sucPage,false);
// adjust tree for leaf node
if (sucPage.m_header.m_numKeys < m_header.m_minKeys)
adjustTree(sucPage);
}
--m_header.m_count;
rewriteHeader();
}
// find a node
private SearchResult search(Page pg, KeyObject key, boolean allowNext) throws IOException, BTreeException, ClassNotFoundException
{
int position = 0;
// if page is empty, we didn't find the key
if (pg.m_header.m_numKeys == 0)
return new SearchResult(false,pg,position);
// loop through keys
while (true)
{
// watch for end of page
if (position == pg.m_header.m_numKeys)
break;
// compare keys
int comp = pg.m_key[position].compareTo(key);
// return result if key was found
if (comp == KeyObject.KEY_EQUAL || (allowNext && (comp == KeyObject.KEY_MORE)))
return new SearchResult(true,pg,position);
else
{
// otherwise, continue searching
if (comp == KeyObject.KEY_LESS)
++position; // this page
else
break; // search successor page
}
}
// if we're in a leaf, the key hasn't been found
if (pg.m_link[position] == NULL_PTR)
return new SearchResult(false,pg,position);
else // read and search next page
return search(read(pg.m_link[position]),key,allowNext);
}
// find a node
private SearchResult searchWithPosition(Page pg, KeyObject key, boolean allowNext) throws IOException, BTreeException, ClassNotFoundException
{
int position = 0;
// if page is empty, we didn't find the key
if (pg.m_header.m_numKeys == 0)
return new SearchResult(false,pg,position);
// loop through keys
while (true)
{
// watch for end of page
if (position == pg.m_header.m_numKeys)
break;
// compare keys
int comp = pg.m_key[position].compareTo(key);
// return result if key was found
if (comp == KeyObject.KEY_EQUAL || (allowNext && (comp == KeyObject.KEY_MORE)))
return new SearchResult(true,pg,position);
else
{
// otherwise, continue searching
if (comp == KeyObject.KEY_LESS)
++position; // this page
else
break; // search successor page
}
}
// if we're in a leaf, the key hasn't been found
if (pg.m_link[position] == NULL_PTR)
return new SearchResult(false,pg,position);
else // read and search next page
return search(read(pg.m_link[position]),key,allowNext);
}
// search for leaf node in which we insert the given key
private SearchResult searchInsert(Page pg, KeyObject key) throws IOException, BTreeException, ClassNotFoundException
{
int position = 0;
// if page is empty, we didn't find the key
if (pg.m_header.m_numKeys == 0)
return new SearchResult(false,pg,position);
// loop through keys
while (true)
{
// watch for end of page
if (position == pg.m_header.m_numKeys)
break;
// compare keys
int comp = pg.m_key[position].compareTo(key);
if (comp == KeyObject.KEY_LESS)
++position;
else
break;
}
// if we're in a leaf, the key hasn't been found
if (pg.m_link[position] == NULL_PTR)
return new SearchResult(false,pg,position);
else // read and search next page
return searchInsert(read(pg.m_link[position]),key);
}
// internal function to write keys
private void writeKey(SearchResult ins, KeyObject key, long position) throws IOException, ClassNotFoundException
{
// check to see if page is full
if (ins.m_page.m_header.m_numKeys == m_header.m_maxKeys)
{
// temporary arrays
KeyObject [] tempKeys = new KeyObject [m_header.m_maxKeys + 1];
long [] tempPtrs = new long [m_header.m_maxKeys + 1];
// store new item
tempKeys[ins.m_position] = key;
tempPtrs[ins.m_position] = position;
// copy entries from insertion page to temps
int nt = 0; // index for temp arrays
int ni = 0; // index for insertion page
while (ni < m_header.m_maxKeys)
{
// skip over inserted data
if (ni == ins.m_position)
++nt;
// copy data
tempKeys[nt] = ins.m_page.m_key[ni];
tempPtrs[nt] = ins.m_page.m_recPtr[ni];
// next one
++ni;
++nt;
}
// create a new leaf
Page sibPage = new Page(m_header);
sibPage.m_header.m_parentPtr = ins.m_page.m_header.m_parentPtr;
// clear key counts
ins.m_page.m_header.m_numKeys = 0;
sibPage.m_header.m_numKeys = 0;
// copy keys from temp to pages
for (ni = 0; ni < m_header.m_minKeys; ++ni)
{
ins.m_page.m_key[ni] = tempKeys[ni];
ins.m_page.m_recPtr[ni] = tempPtrs[ni];
++ins.m_page.m_header.m_numKeys;
}
for (ni = m_header.m_minKeys + 1; ni <= m_header.m_maxKeys; ++ni)
{
sibPage.m_key[ni - 1 - m_header.m_minKeys] = tempKeys[ni];
sibPage.m_recPtr[ni - 1 - m_header.m_minKeys] = tempPtrs[ni];
++sibPage.m_header.m_numKeys;
}
// replace remaining entries with null
for (ni = m_header.m_minKeys; ni < m_header.m_maxKeys; ++ni)
{
ins.m_page.m_key[ni] = m_header.m_nullKey.makeNullKey();
ins.m_page.m_recPtr[ni] = NULL_PTR;
}
// write pages
write(ins.m_page,false);
write(sibPage,false);
// promote key and its pointer
if (ins.m_page.m_header.m_parentPtr == NULL_PTR)
{
// creating a new m_root page
promoteRoot(tempKeys[m_header.m_minKeys],
tempPtrs[m_header.m_minKeys],
ins.m_page,
sibPage);
}
else
{
// promote key into parent page
Page parPage = read(ins.m_page.m_header.m_parentPtr);
promoteInternal(parPage,
tempKeys[m_header.m_minKeys],
tempPtrs[m_header.m_minKeys],
sibPage.m_header.m_filePtr);
}
}
else
{
// move keys to make room for new one
for (int n = ins.m_page.m_header.m_numKeys; n > ins.m_position; --n)
{
ins.m_page.m_key[n] = ins.m_page.m_key[n - 1];
ins.m_page.m_recPtr[n] = ins.m_page.m_recPtr[n - 1];
}
ins.m_page.m_key[ins.m_position] = key;
ins.m_page.m_recPtr[ins.m_position] = position;
++ins.m_page.m_header.m_numKeys;
// write updated page
write(ins.m_page,false);
}
m_root = readRoot();
}
// promote key into parent
private void promoteInternal(Page insPage, KeyObject key, long ptr, long link) throws IOException, BTreeException, ClassNotFoundException
{
if (insPage.m_header.m_numKeys == m_header.m_maxKeys)
{
// temporary array
KeyObject [] tempKeys = new KeyObject [m_header.m_maxKeys + 1];
long [] tempPtrs = new long [m_header.m_maxKeys + 1];
long [] tempLnks = new long [m_header.m_order + 1];
tempLnks[0] = insPage.m_link[0];
// copy entries from inapage to temps
int nt = 0;
int ni = 0;
int position = 0;
// find insertion point
while ((position < insPage.m_header.m_numKeys) && (insPage.m_key[position].compareTo(key) == KeyObject.KEY_LESS))
++position;
// store new info
tempKeys[position] = key;
tempPtrs[position] = ptr;
tempLnks[position + 1] = link;
// copy existing keys
while (ni < m_header.m_maxKeys)
{
if (ni == position)
++nt;
tempKeys[nt] = insPage.m_key[ni];
tempPtrs[nt] = insPage.m_recPtr[ni];
tempLnks[nt + 1] = insPage.m_link[ni + 1];
++ni;
++nt;
}
// generate a new leaf node
Page sibPage = new Page(m_header);
sibPage.m_header.m_parentPtr = insPage.m_header.m_parentPtr;
// clear key counts
insPage.m_header.m_numKeys = 0;
sibPage.m_header.m_numKeys = 0;
insPage.m_link[0] = tempLnks[0];
// copy keys from temp to pages
for (ni = 0; ni < m_header.m_minKeys; ++ni)
{
insPage.m_key[ni] = tempKeys[ni];
insPage.m_recPtr[ni] = tempPtrs[ni];
insPage.m_link[ni + 1] = tempLnks[ni + 1];
++insPage.m_header.m_numKeys;
}
sibPage.m_link[0] = tempLnks[m_header.m_minKeys + 1];
for (ni = m_header.m_minKeys + 1; ni <= m_header.m_maxKeys; ++ni)
{
sibPage.m_key[ni - 1 - m_header.m_minKeys] = tempKeys[ni];
sibPage.m_recPtr[ni - 1 - m_header.m_minKeys] = tempPtrs[ni];
sibPage.m_link[ni - m_header.m_minKeys] = tempLnks[ni + 1];
++sibPage.m_header.m_numKeys;
}
// replace remaining entries with null
for (ni = m_header.m_minKeys; ni < m_header.m_maxKeys; ++ni)
{
insPage.m_key[ni] = m_header.m_nullKey.makeNullKey();
insPage.m_recPtr[ni] = NULL_PTR;
insPage.m_link[ni + 1] = NULL_PTR;
}
// write pages
write(insPage,false);
write(sibPage,false);
// update parent links in child nodes
for (ni = 0; ni <= sibPage.m_header.m_numKeys; ++ni)
{
Page child = read(sibPage.m_link[ni]);
child.m_header.m_parentPtr = sibPage.m_header.m_filePtr;
write(child,false);
}
// promote key and pointer
if (insPage.m_header.m_parentPtr == NULL_PTR)
{
// create a new m_root
promoteRoot(tempKeys[m_header.m_minKeys],
tempPtrs[m_header.m_minKeys],
insPage,
sibPage);
}
else
{
// read parent and promote key
Page parPage = read(insPage.m_header.m_parentPtr);
promoteInternal(parPage,
tempKeys[m_header.m_minKeys],
tempPtrs[m_header.m_minKeys],
sibPage.m_header.m_filePtr);
}
}
else
{
int position = 0;
// find insertion point
while ((position < insPage.m_header.m_numKeys) && (insPage.m_key[position].compareTo(key) == KeyObject.KEY_LESS))
++position;
// shift keys right
for (int n = insPage.m_header.m_numKeys; n > position; --n)
{
insPage.m_key[n] = insPage.m_key[n - 1];
insPage.m_recPtr[n] = insPage.m_recPtr[n - 1];
insPage.m_link[n + 1] = insPage.m_link[n];
}
insPage.m_key[position] = key;
insPage.m_recPtr[position] = ptr;
insPage.m_link[position + 1] = link;
++insPage.m_header.m_numKeys;
// write updated page
write(insPage,false);
}
}
// promote key by creating new m_root
private void promoteRoot(KeyObject key, long ptr, Page lessPage, Page grtrPage) throws IOException, BTreeException, ClassNotFoundException
{
// create a new m_root page
Page newRoot = new Page(m_header);
// add key and links to m_root
newRoot.m_key[0] = key;
newRoot.m_recPtr[0] = ptr;
newRoot.m_link[0] = lessPage.m_header.m_filePtr;
newRoot.m_link[1] = grtrPage.m_header.m_filePtr;
newRoot.m_header.m_numKeys = 1;
// write new m_root to tree
write(newRoot,true);
// update children
lessPage.m_header.m_parentPtr = newRoot.m_header.m_filePtr;
grtrPage.m_header.m_parentPtr = newRoot.m_header.m_filePtr;
write(lessPage,false);
write(grtrPage,false);
}
// adjust tree if page is too small
private void adjustTree(Page pg) throws IOException, BTreeException, ClassNotFoundException
{
// check for root
if (pg.m_header.m_parentPtr == NULL_PTR)
return;
// get parent page
Page parPage = read(pg.m_header.m_parentPtr);
// find pointer to pg
int n = 0;
while (parPage.m_link[n] != pg.m_header.m_filePtr)
++n;
// read sibling pages
Page sibMore = null;
Page sibLess = null;
if (n < parPage.m_header.m_numKeys)
sibMore = read(parPage.m_link[n+1]);
if (n > 0)
sibLess = read(parPage.m_link[n-1]);
// figure out what to do
if (sibLess != null)
{
--n;
if (sibLess.m_header.m_numKeys > m_header.m_minKeys)
redistribute(n,sibLess,parPage,pg);
else
concatenate(n,sibLess,parPage,pg);
}
else
{
if (sibMore != null)
{
if (sibMore.m_header.m_numKeys > m_header.m_minKeys)
redistribute(n,pg,parPage,sibMore);
else
concatenate(n,pg,parPage,sibMore);
}
else
throw new BTreeException("This should never happen!");
}
}
// redistribute keys among siblings and parent
private void redistribute(int position, Page lessPage, Page parPage, Page morePage) throws IOException, BTreeException, ClassNotFoundException
{
// check for leaf page
if (lessPage.m_link[0] == NULL_PTR)
{
if (lessPage.m_header.m_numKeys > morePage.m_header.m_numKeys)
{
// move a key from lessPage to morePage
for (int n = morePage.m_header.m_numKeys; n > 0; --n)
{
morePage.m_key[n] = morePage.m_key[n - 1];
morePage.m_recPtr[n] = morePage.m_recPtr[n - 1];
}
// store parent separator in morePage
morePage.m_key[0] = parPage.m_key[position];
morePage.m_recPtr[0] = parPage.m_recPtr[position];
// increment morePage key count
++morePage.m_header.m_numKeys;
// decrement lessPage key count
--lessPage.m_header.m_numKeys;
// move last key in lessPage to parPage as separator
parPage.m_key[position] = lessPage.m_key[lessPage.m_header.m_numKeys];
parPage.m_recPtr[position] = lessPage.m_recPtr[lessPage.m_header.m_numKeys];
// clear last key in lessPage
lessPage.m_key[lessPage.m_header.m_numKeys] = m_header.m_nullKey.makeNullKey();
lessPage.m_recPtr[lessPage.m_header.m_numKeys] = NULL_PTR;
}
else
{
// add parent key to lesser page
lessPage.m_key[lessPage.m_header.m_numKeys] = parPage.m_key[position];
lessPage.m_recPtr[lessPage.m_header.m_numKeys] = parPage.m_recPtr[position];
// increment lessPage key count
++lessPage.m_header.m_numKeys;
// move first key in morePage to parPage as separator
parPage.m_key[position] = morePage.m_key[0];
parPage.m_recPtr[position] = morePage.m_recPtr[0];
// decrement morePage key count
--morePage.m_header.m_numKeys;
// move a key from morePage to lessPage
int n;
for (n = 0; n < morePage.m_header.m_numKeys; ++n)
{
morePage.m_key[n] = morePage.m_key[n + 1];
morePage.m_recPtr[n] = morePage.m_recPtr[n + 1];
}
// clear last key in morePage
morePage.m_key[n] = m_header.m_nullKey.makeNullKey();
morePage.m_recPtr[n] = NULL_PTR;
}
}
else
{
if (lessPage.m_header.m_numKeys > morePage.m_header.m_numKeys)
{
// move a key from lessPage to morePage
for (int n = morePage.m_header.m_numKeys; n > 0; --n)
{
morePage.m_key[n] = morePage.m_key[n - 1];
morePage.m_recPtr[n] = morePage.m_recPtr[n - 1];
morePage.m_link[n + 1] = morePage.m_link[n];
}
morePage.m_link[1] = morePage.m_link[0];
// store parPage separator key in morePage
morePage.m_key[0] = parPage.m_key[position];
morePage.m_recPtr[0] = parPage.m_recPtr[position];
morePage.m_link[0] = lessPage.m_link[lessPage.m_header.m_numKeys];
// update child link
Page child = read(morePage.m_link[0]);
child.m_header.m_parentPtr = morePage.m_header.m_filePtr;
write(child,false);
// increment morePage key count
++morePage.m_header.m_numKeys;
// decrement lessPage key count
--lessPage.m_header.m_numKeys;
// move last key in lessPage to parPage as separator
parPage.m_key[position] = lessPage.m_key[lessPage.m_header.m_numKeys];
parPage.m_recPtr[position] = lessPage.m_recPtr[lessPage.m_header.m_numKeys];
// clear last key in lessPage
lessPage.m_key[lessPage.m_header.m_numKeys] = m_header.m_nullKey.makeNullKey();
lessPage.m_recPtr[lessPage.m_header.m_numKeys] = NULL_PTR;
lessPage.m_link[lessPage.m_header.m_numKeys + 1] = NULL_PTR;
}
else
{
// store parPage separator key in lessPage
lessPage.m_key[lessPage.m_header.m_numKeys] = parPage.m_key[position];
lessPage.m_recPtr[lessPage.m_header.m_numKeys] = parPage.m_recPtr[position];
lessPage.m_link[lessPage.m_header.m_numKeys + 1] = morePage.m_link[0];
// update child link
Page child = read(morePage.m_link[0]);
child.m_header.m_parentPtr = lessPage.m_header.m_filePtr;
write(child,false);
// increment lessPage key count
++lessPage.m_header.m_numKeys;
// move last key in morePage to parPage as separator
parPage.m_key[position] = morePage.m_key[0];
parPage.m_recPtr[position] = morePage.m_recPtr[0];
// decrement morePage key count
--morePage.m_header.m_numKeys;
// move a key from morePage to lessPage
int n;
for (n = 0; n < morePage.m_header.m_numKeys; ++n)
{
morePage.m_key[n] = morePage.m_key[n + 1];
morePage.m_recPtr[n] = morePage.m_recPtr[n + 1];
morePage.m_link[n] = morePage.m_link[n + 1];
}
morePage.m_link[n] = morePage.m_link[n + 1];
// clear last key in morePage
morePage.m_key[n] = m_header.m_nullKey.makeNullKey();
morePage.m_recPtr[n] = NULL_PTR;
morePage.m_link[n + 1] = NULL_PTR;
}
}
// write updated pages
write(lessPage,false);
write(parPage,false);
write(morePage,false);
// update cached m_root if necessary
if (parPage.m_header.m_parentPtr == NULL_PTR)
m_root = parPage;
}
// concatenate sibling pages
private void concatenate(int position, Page lessPage, Page parPage, Page morePage) throws IOException, BTreeException, ClassNotFoundException
{
// move separator key from parPage into lessPage
lessPage.m_key[lessPage.m_header.m_numKeys] = parPage.m_key[position];
lessPage.m_recPtr[lessPage.m_header.m_numKeys] = parPage.m_recPtr[position];
lessPage.m_link[lessPage.m_header.m_numKeys + 1] = morePage.m_link[0];
// increment lessPage key count
++lessPage.m_header.m_numKeys;
// delete separator from parPage
--parPage.m_header.m_numKeys;
int n;
for (n = position; n < parPage.m_header.m_numKeys; ++n)
{
parPage.m_key[n] = parPage.m_key[n + 1];
parPage.m_recPtr[n] = parPage.m_recPtr[n + 1];
parPage.m_link[n + 1] = parPage.m_link[n + 2];
}
// clear unsused key from parent
parPage.m_key[n] = m_header.m_nullKey.makeNullKey();
parPage.m_recPtr[n] = NULL_PTR;
parPage.m_link[n + 1] = NULL_PTR;
// copy keys from morePage to lessPage
int ng = 0;
n = lessPage.m_header.m_numKeys;
// combine pages
while (ng < morePage.m_header.m_numKeys)
{
++lessPage.m_header.m_numKeys;
lessPage.m_key[n] = morePage.m_key[ng];
lessPage.m_recPtr[n] = morePage.m_recPtr[ng];
lessPage.m_link[n + 1] = morePage.m_link[ng + 1];
++ng;
++n;
}
// delete morePage
delete(morePage);
// is this a leaf?
if (lessPage.m_link[0] != NULL_PTR)
{
// adjust child pointers
for (n = 0; n <= lessPage.m_header.m_numKeys; ++n)
{
Page child = read(lessPage.m_link[n]);
child.m_header.m_parentPtr = lessPage.m_header.m_filePtr;
write(child,false);
}
}
// write lessPage and parent
if (parPage.m_header.m_numKeys == 0)
{
delete(parPage);
lessPage.m_header.m_parentPtr = NULL_PTR;
write(lessPage,true);
m_root = lessPage;
}
else
{
write(parPage,false);
write(lessPage,false);
// reset cached m_root page if needed
if (parPage.m_header.m_parentPtr == NULL_PTR)
m_root = parPage;
// if parent is too small, adjust
if (parPage.m_header.m_numKeys < m_header.m_minKeys)
adjustTree(parPage);
}
}
/**
* Empty the page cache.
*/
public void emptyPageCache()
{
m_pageCache = new HashMap();
}
/**
* Get the size of the page cache, in number of B-tree pages stored in memory.
*/
public int getPageCacheSize()
{
return m_pageCache.size();
}
/**
* Dumps the entire B-Tree to <code>System.out</code> for analysis. For diagnostic purposes only.
*
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @throws DuplicateKey when inserting a duplicate key into an index that does not
* support duplicates
*/
public void dumpTree(PrintStream output) throws IOException, DuplicateKey, ClassNotFoundException
{
// recursively dump from the root
output.println("ROOT: " + m_root.m_header.m_filePtr);
dumpTreeRecursive(m_root,output);
}
private void dumpTreeRecursive(Page pg, PrintStream output) throws IOException, DuplicateKey, ClassNotFoundException
{
// create a formatter for numbers
DecimalFormat numform1 = new DecimalFormat("#######0");
DecimalFormat numform2 = new DecimalFormat("000");
output.println();
output.println("PAGE:" + numform1.format(pg.m_header.m_filePtr));
for (int k = 0; k < pg.m_header.m_numKeys; ++k)
{
output.println("" + numform2.format(k) + ": " + numform1.format(pg.m_link[k]));
output.println(" " + pg.m_key[k].toString().trim());
}
// display last link
output.println("" + numform2.format(pg.m_header.m_numKeys) + ": " + numform1.format(pg.m_link[pg.m_header.m_numKeys]));
for (int n = 0; n < pg.m_header.m_numKeys + 1; ++n)
{
if (pg.m_link[n] >= 0)
dumpTreeRecursive(read(pg.m_link[n]),output);
}
}
}
jisp-2.5.1/com/coyotegulch/jisp/BTreeIterator.java 0100644 0001750 0001750 00000041462 07641135213 021176 0 ustar scott scott //-----------------------------------------------------------------------
// Java Indexed Serialization Package
// ----------------------------------
// BTreeIterator.java
//-----------------------------------------------------------------------
//
// COPYRIGHT NOTICE, DISCLAIMER, and LICENSE:
//
// If you modify this file, you may insert additional notices
// immediately following this sentence.
//
// Copyright 1996-2003 Scott Robert Ladd.
// All rights reserved, except as noted herein.
//
// This computer program source file is supplied "AS IS". Scott Robert
// Ladd (hereinafter referred to as "Author") disclaims all warranties,
// expressed or implied, including, without limitation, the warranties
// of merchantability and of fitness for any purpose. The Author
// assumes no liability for direct, indirect, incidental, special,
// exemplary, or consequential damages, which may result from the use
// of this software, even if advised of the possibility of such damage.
//
// The Author hereby grants anyone permission to use, copy, modify, and
// distribute this source code, or portions hereof, for any legal purpose,
// without fee, subject to the following restrictions:
//
// 1. The origin of this source code must not be misrepresented.
//
// 2. Altered versions must be plainly marked as such and must not
// be misrepresented as being the original source.
//
// 3. This Copyright notice may not be removed or altered from any
// source or altered source distribution.
//
// The Author specifically permits (without fee) and encourages the use
// of this source code for entertainment, education, or decoration. If
// you use this source code in a product, acknowledgment is not required
// but would be appreciated.
//
// Acknowledgement:
// This license is based on the wonderful simple license that
// accompanies libpng.
//
//-----------------------------------------------------------------------
// For more information on this software package, please visit
// Scott's web site, Coyote Gulch Productions, at:
//
// http://www.coyotegulch.com
//-----------------------------------------------------------------------
package com.coyotegulch.jisp;
import java.io.IOException;
import java.util.Stack;
/**
* <code>BTreeIterator</code> defines an object that references a specific object relative to other
* objects in an <code>ObjectIndex</code>. In many ways, a <code>BTreeIterator</code> is analogous
* to the "cursors" found in SQL-type databases; it is essentially a movable reference to elements
* in an index, and it can be moved forward and backward through the list of keys.
* <p>
* @author Scott Robert Ladd
* @see com.coyotegulch.jisp.ObjectIndex
* @see com.coyotegulch.jisp.IndexedObjectDatabase
*/
public class BTreeIterator implements IndexIterator
{
private class PagePointer
{
public Page m_page;
public int m_index;
public PagePointer(Page pg, int index)
{
m_page = pg;
m_index = index;
}
}
private boolean m_valid = true;
private BTreeIndex m_index;
private Stack m_pageStack;
private Page m_currentPage;
private int m_currentIndex;
/**
* Creates a new <code>BTreeIterator</code> for a given index and database.
*
* @param index the index to which this iterator is attached.
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @see com.coyotegulch.jisp.BTreeIndex
*/
public BTreeIterator(BTreeIndex index) throws IOException, ClassNotFoundException
{
// save reference to the tree file
m_index = index;
// create page stack for recursion
m_pageStack = new Stack();
// read the root page
m_currentPage = m_index.readRoot();
m_currentIndex = -1;
if (m_currentPage.m_header.m_numKeys < 1)
m_valid = false;
else
m_valid = moveNext();
}
/**
* Creates a new <code>BTreeIterator</code> that points to the same location as an existing
* <code>BtreeIterator</code>.
*
* @param iterator the iterator to be copied.
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @see com.coyotegulch.jisp.BTreeIndex
*/
public BTreeIterator(BTreeIterator iterator) throws IOException, ClassNotFoundException
{
// save reference to the tree file
m_index = iterator.m_index;
// create page stack for recursion
m_pageStack = (Stack)iterator.m_pageStack.clone();
// read the root page
m_currentPage = m_index.readRoot();
m_currentIndex = iterator.m_currentIndex;
}
/**
* Returns the reference (usually a file pointer) currently associated with this iterator.
*
* @return the record <code>Object</code> currently referenced by this iterator, or -1 if the iterator is invalid
*/
public long getRecPtr() throws IOException
{
long result = -1;
if (m_valid)
result = m_currentPage.m_recPtr[m_currentIndex];
return result;
}
/**
* Returns the key <code>Object</code> currently associated with this iterator.
*
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @return the key <code>Object</code> currently referenced by this iterator, or null if the iterator is invalid
*/
public Object getKey() throws IOException
{
Object result = null;
if (m_valid)
{
// read the object
try
{
result = m_currentPage.m_key[m_currentIndex];
}
catch (Exception ex)
{
ex.printStackTrace();
}
}
return result;
}
/**
* Moves this iterator to the next key and reference in sequence.
*
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @return <code>true</code> if the operation was successful; <code>false</code> otherwise.
*/
public boolean moveNext() throws IOException, ClassNotFoundException
{
if (!m_valid)
return false;
// next entry
++m_currentIndex;
boolean popped = false;
// have we passed the end of this page?
if (m_currentIndex == m_currentPage.m_header.m_numKeys)
{
if (m_currentPage.m_link[m_currentIndex] != BTreePageFile.NULL_PTR)
{
// save the current page
m_pageStack.push(new PagePointer(m_currentPage,m_currentIndex));
// move to the child page
m_currentPage = m_index.read(m_currentPage.m_link[m_currentIndex]);
m_currentIndex = 0;
}
}
while (m_currentIndex >= m_currentPage.m_header.m_numKeys)
{
if (m_pageStack.empty())
{
// we're done
return false;
}
else
{
// go back to previous page and continue with next entry
PagePointer temp = (PagePointer)m_pageStack.pop();
m_currentPage = temp.m_page;
m_currentIndex = temp.m_index;
popped = true;
}
}
try
{
// go to first entry in child, if it exists
if (!popped)
{
while (m_currentPage.m_link[m_currentIndex] != Page.NULL_PTR)
{
// save the current page
m_pageStack.push(new PagePointer(m_currentPage,m_currentIndex));
// move to the child page
m_currentPage = m_index.read(m_currentPage.m_link[m_currentIndex]);
m_currentIndex = 0;
}
}
}
catch (Exception ex)
{
ex.printStackTrace();
return false;
}
return true;
}
/**
* Moves this iterator to the previous key and reference in sequence.
*
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @throws BTreeException when an error occurs during B-Tree processing
* @return <code>true</code> if the operation was successful; <code>false</code> otherwise.
*/
public boolean movePrevious() throws IOException, ClassNotFoundException
{
if (!m_valid)
return false;
boolean popped = false;
// are we at the beginning of the page?
while (m_currentIndex == 0)
{
// are we done yet?
if (m_pageStack.empty())
return false;
// go back to previous page and continue with next entry
PagePointer temp = (PagePointer)m_pageStack.pop();
m_currentPage = temp.m_page;
m_currentIndex = temp.m_index;
popped = true;
}
// previous entry
--m_currentIndex;
if (m_currentPage.m_link[m_currentIndex] != BTreePageFile.NULL_PTR)
{
// save the current page
m_pageStack.push(new PagePointer(m_currentPage,m_currentIndex));
// move to the child page
m_currentPage = m_index.read(m_currentPage.m_link[m_currentIndex]);
m_currentIndex = m_currentPage.m_header.m_numKeys - 1;
}
return true;
}
/**
* Moves this iterator to the first key and reference in sequence.
*
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @throws BTreeException when an error occurs during B-Tree processing
* @return <code>true</code> if the operation was successful; <code>false</code> otherwise.
*/
public boolean moveFirst() throws IOException, ClassNotFoundException
{
// verify validity
if (!m_valid)
return false;
// create page stack for recursion
m_pageStack = new Stack();
// read the root page
m_currentPage = m_index.readRoot();
m_currentIndex = -1;
moveNext();
return true;
}
/**
* Moves this iterator to the last key and reference in sequence.
*
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @throws BTreeException when an error occurs during B-Tree processing
* @return <code>true</code> if the operation was successful; <code>false</code> otherwise.
*/
public boolean moveLast() throws IOException, ClassNotFoundException
{
// verify validity
if (!m_valid)
return false;
// create page stack for recursion
m_pageStack = new Stack();
// read the root page
m_currentPage = m_index.readRoot();
m_currentIndex = -1;
while (moveNext())
{
// just loop 'til we find the end
// not efficient, but works right now when I'm testing
}
return true;
}
/**
* Moves this iterator to point to the given <code>key</code>.
*
* @param key key identifier to find
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @throws BTreeException when an error occurs during B-Tree processing
* @return <code>true</code> if the operation was successful; <code>false</code> otherwise.
*/
public boolean moveTo(KeyObject key) throws IOException, ClassNotFoundException
{
return moveTo(key,false);
}
/**
* Moves this iterator to point to the given <code>key</code>.
*
* @param key key identifier to find
* @param acceptNext when true, allows the search to return the next record in sequence
* if an exact match is not found
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @throws BTreeException when an error occurs during B-Tree processing
* @return <code>true</code> if the operation was successful; <code>false</code> otherwise.
*/
public boolean moveTo(KeyObject key, boolean acceptNext) throws IOException, ClassNotFoundException
{
// verify validity
if (!m_valid)
return false;
// create page stack for recursion
m_pageStack = new Stack();
// read the root page
m_currentPage = m_index.readRoot();
m_currentIndex = -1;
return search(key,m_currentPage,acceptNext);
}
private boolean search(KeyObject key, Page pg, boolean acceptNext) throws IOException, ClassNotFoundException
{
int pos = 0;
if (pg.m_header.m_numKeys == 0)
return false;
int comp = KeyObject.KEY_ERROR;
while (true)
{
if (pos == pg.m_header.m_numKeys)
break;
comp = pg.m_key[pos].compareTo(key);
if (comp == KeyObject.KEY_EQUAL)
{
m_currentPage = pg;
m_currentIndex = pos;
return true;
}
else
{
if (comp == KeyObject.KEY_LESS)
++pos;
else
break;
}
}
if (pg.m_link[pos] == BTreeIndex.NULL_PTR)
{
if (acceptNext)
{
if (comp == KeyObject.KEY_MORE)
{
m_currentPage = pg;
m_currentIndex = pos;
return true;
}
else
return false;
}
else
return false;
}
else
{
// save the current page
m_pageStack.push(new PagePointer(pg,pos));
return search(key,m_index.read(pg.m_link[pos]),acceptNext);
}
}
/**
* Checks to see if this iterator is valid.
*
* @return <code>true</code> if the iterator is valid; <code>false</code> if it is invalid.
*/
public boolean isValid()
{
return m_valid;
}
/**
* Sets this iterator's state to invalid.
*/
public void invalidate()
{
m_valid = false;
}
}
jisp-2.5.1/com/coyotegulch/jisp/BTreePageFile.java 0100644 0001750 0001750 00000016057 07640741260 021067 0 ustar scott scott //-----------------------------------------------------------------------
// Java Indexed Serialization Package
// ----------------------------------
// BTreePageFile.java
//-----------------------------------------------------------------------
//
// COPYRIGHT NOTICE, DISCLAIMER, and LICENSE:
//
// If you modify this file, you may insert additional notices
// immediately following this sentence.
//
// Copyright 1996-2003 Scott Robert Ladd.
// All rights reserved, except as noted herein.
//
// This computer program source file is supplied "AS IS". Scott Robert
// Ladd (hereinafter referred to as "Author") disclaims all warranties,
// expressed or implied, including, without limitation, the warranties
// of merchantability and of fitness for any purpose. The Author
// assumes no liability for direct, indirect, incidental, special,
// exemplary, or consequential damages, which may result from the use
// of this software, even if advised of the possibility of such damage.
//
// The Author hereby grants anyone permission to use, copy, modify, and
// distribute this source code, or portions hereof, for any legal purpose,
// without fee, subject to the following restrictions:
//
// 1. The origin of this source code must not be misrepresented.
//
// 2. Altered versions must be plainly marked as such and must not
// be misrepresented as being the original source.
//
// 3. This Copyright notice may not be removed or altered from any
// source or altered source distribution.
//
// The Author specifically permits (without fee) and encourages the use
// of this source code for entertainment, education, or decoration. If
// you use this source code in a product, acknowledgment is not required
// but would be appreciated.
//
// Acknowledgement:
// This license is based on the wonderful simple license that
// accompanies libpng.
//
//-----------------------------------------------------------------------
// For more information on this software package, please visit
// Scott's web site, Coyote Gulch Productions, at:
//
// http://www.coyotegulch.com
//-----------------------------------------------------------------------
package com.coyotegulch.jisp;
import java.io.*;
import java.util.*;
class BTreePageFile extends BTreeShared
{
// class constants
private static final int MINIMUM_ORDER = 5;
/**
* Header data for a file containing B-Tree pages.
*/
protected PageFileHeader m_header;
private PageDatabaseFile m_datafile;
/**
* A cache of pages that have already been loaded into memory. As each page is read
*/
protected HashMap m_pageCache;
// constructors
BTreePageFile(String name) throws IOException, ClassNotFoundException
{
m_datafile = new PageDatabaseFile(name);
// read existing m_header
m_datafile.rewind();
m_header = (PageFileHeader)m_datafile.readObject();
m_pageCache = new HashMap();
}
BTreePageFile(String name, int order, KeyObject nullKey, boolean hasDupes) throws IOException, ClassNotFoundException
{
// delete any existing files
File killthis = new File(name);
killthis.delete();
m_datafile = new PageDatabaseFile(name);
m_pageCache = new HashMap();
constructorHelper(order,nullKey,hasDupes);
}
private void constructorHelper(int order, KeyObject nullKey, boolean hasDupes) throws IOException, ClassNotFoundException
{
// adjust order to fit requirements
if (order < MINIMUM_ORDER)
order = MINIMUM_ORDER;
else
{
// make certain order is odd
if ((order & 1) != 1)
++order;
}
// new file, new m_header
m_header = new PageFileHeader();
m_header.m_order = order;
m_header.m_maxKeys = order - 1;
m_header.m_minKeys = order / 2;
m_header.m_count = 0;
m_header.m_ticker = 0;
m_header.m_rootPtr = NULL_PTR;
m_header.m_hasDupes = hasDupes;
m_header.m_nullKey = nullKey;
// write m_header to file
m_datafile.writeObject(m_header);
// create a new root
Page root = new Page(m_header);
// store root and update m_header
root.m_header.m_filePtr = m_datafile.getNextOpen();
m_header.m_rootPtr = m_datafile.writeObject(root);
// update m_header
m_datafile.rewind();
m_datafile.rewriteObject(m_header);
}
// methods
void write(Page pg, boolean root) throws IOException
{
// if new page, find a place to write it
if (pg.m_header.m_filePtr == NULL_PTR)
{
pg.m_header.m_filePtr = m_datafile.getNextOpen();
// add page to cache
Long cacheKey = new Long(pg.m_header.m_filePtr);
m_pageCache.put(cacheKey,pg);
// write the new page
m_datafile.writeObject(pg);
}
else // write in old position
{
m_datafile.seek(pg.m_header.m_filePtr);
m_datafile.rewriteObject(pg);
}
// if root, change root pointer
if (root)
{
m_header.m_rootPtr = pg.m_header.m_filePtr;
// update m_header
m_datafile.rewind();
m_datafile.rewriteObject(m_header);
}
}
void rewriteHeader() throws IOException
{
m_datafile.rewind();
m_datafile.rewriteObject(m_header);
}
Page read(long pos) throws IOException, ClassNotFoundException
{
Page result = null;
Long cacheKey = new Long(pos);
// System.err.print("--- Reading page from position " + pos);
// see if page is already in cache
if (m_pageCache.containsKey(cacheKey))
{
// System.err.println(" from cache");
result = (Page)m_pageCache.get(cacheKey);
}
else
{
// System.err.println(" from file");
// move to specified position in data file
m_datafile.seek(pos);
// read and return a Page
result = (Page)m_datafile.readObject();
// add new page to cache
m_pageCache.put(cacheKey,result);
}
return result;
}
Page readRoot() throws IOException, ClassNotFoundException
{
return read(m_header.m_rootPtr);
}
void delete(Page pg) throws IOException
{
// remove page from cache if it is in there
Long cacheKey = new Long(pg.m_header.m_filePtr);
if (m_pageCache.containsKey(cacheKey))
m_pageCache.remove(cacheKey);
// move to specified position in data file
m_datafile.seek(pg.m_header.m_filePtr);
// delete this record
m_datafile.delete();
}
HashMap getPageCache()
{
return m_pageCache;
}
public void close() throws IOException
{
if (m_datafile != null)
{
m_datafile.close();
m_datafile = null;
}
}
}
jisp-2.5.1/com/coyotegulch/jisp/BTreeShared.java 0100644 0001750 0001750 00000005223 07633366244 020621 0 ustar scott scott //-----------------------------------------------------------------------
// Java Indexed Serialization Package
// ----------------------------------
// BTreeShared.java
//-----------------------------------------------------------------------
//
// COPYRIGHT NOTICE, DISCLAIMER, and LICENSE:
//
// If you modify this file, you may insert additional notices
// immediately following this sentence.
//
// Copyright 1996-2003 Scott Robert Ladd.
// All rights reserved, except as noted herein.
//
// This computer program source file is supplied "AS IS". Scott Robert
// Ladd (hereinafter referred to as "Author") disclaims all warranties,
// expressed or implied, including, without limitation, the warranties
// of merchantability and of fitness for any purpose. The Author
// assumes no liability for direct, indirect, incidental, special,
// exemplary, or consequential damages, which may result from the use
// of this software, even if advised of the possibility of such damage.
//
// The Author hereby grants anyone permission to use, copy, modify, and
// distribute this source code, or portions hereof, for any legal purpose,
// without fee, subject to the following restrictions:
//
// 1. The origin of this source code must not be misrepresented.
//
// 2. Altered versions must be plainly marked as such and must not
// be misrepresented as being the original source.
//
// 3. This Copyright notice may not be removed or altered from any
// source or altered source distribution.
//
// The Author specifically permits (without fee) and encourages the use
// of this source code for entertainment, education, or decoration. If
// you use this source code in a product, acknowledgment is not required
// but would be appreciated.
//
// Acknowledgement:
// This license is based on the wonderful simple license that
// accompanies libpng.
//
//-----------------------------------------------------------------------
// For more information on this software package, please visit
// Scott's web site, Coyote Gulch Productions, at:
//
// http://www.coyotegulch.com
//-----------------------------------------------------------------------
package com.coyotegulch.jisp;
class BTreeShared
{
static final long NULL_PTR = -1;
static final BTreeException err_inv_order = new BTreeException("invalid BTree order");
static final BTreeException err_inv_keylen = new BTreeException("invalid BTree key length");
static final BTreeException err_inv_page = new BTreeException("invalid BTree page");
static final BTreeException err_corrupt_page = new BTreeException("corrupt BTree page");
}
jisp-2.5.1/com/coyotegulch/jisp/DatabaseException.java 0100644 0001750 0001750 00000005601 07633366244 022054 0 ustar scott scott //-----------------------------------------------------------------------
// Java Indexed Serialization Package
// ----------------------------------
// DatabaseException.java
//-----------------------------------------------------------------------
//
// COPYRIGHT NOTICE, DISCLAIMER, and LICENSE:
//
// If you modify this file, you may insert additional notices
// immediately following this sentence.
//
// Copyright 1996-2003 Scott Robert Ladd.
// All rights reserved, except as noted herein.
//
// This computer program source file is supplied "AS IS". Scott Robert
// Ladd (hereinafter referred to as "Author") disclaims all warranties,
// expressed or implied, including, without limitation, the warranties
// of merchantability and of fitness for any purpose. The Author
// assumes no liability for direct, indirect, incidental, special,
// exemplary, or consequential damages, which may result from the use
// of this software, even if advised of the possibility of such damage.
//
// The Author hereby grants anyone permission to use, copy, modify, and
// distribute this source code, or portions hereof, for any legal purpose,
// without fee, subject to the following restrictions:
//
// 1. The origin of this source code must not be misrepresented.
//
// 2. Altered versions must be plainly marked as such and must not
// be misrepresented as being the original source.
//
// 3. This Copyright notice may not be removed or altered from any
// source or altered source distribution.
//
// The Author specifically permits (without fee) and encourages the use
// of this source code for entertainment, education, or decoration. If
// you use this source code in a product, acknowledgment is not required
// but would be appreciated.
//
// Acknowledgement:
// This license is based on the wonderful simple license that
// accompanies libpng.
//
//-----------------------------------------------------------------------
// For more information on this software package, please visit
// Scott's web site, Coyote Gulch Productions, at:
//
// http://www.coyotegulch.com
//-----------------------------------------------------------------------
package com.coyotegulch.jisp;
import java.io.*;
/**
* Standard exception type thrown by the object database classes.
*
* @author Scott Robert Ladd
* @see com.coyotegulch.jisp.IndexedObjectDatabase
*/
public class DatabaseException extends IOException
{
/**
* Constructs a new <code>DatabaseException</code> with null as its error message string.
*/
public DatabaseException()
{
super();
}
/**
* Constructs a new <code>DatabaseException</code> with <code>message</code> as its error
* message string.
* <p>
* @param message Error message string.
*/
public DatabaseException(String message)
{
super(message);
}
}
jisp-2.5.1/com/coyotegulch/jisp/DuplicateKey.java 0100644 0001750 0001750 00000006616 07633366244 021063 0 ustar scott scott //-----------------------------------------------------------------------
// Java Indexed Serialization Package
// ----------------------------------
// DuplicateKey.java
//-----------------------------------------------------------------------
//
// COPYRIGHT NOTICE, DISCLAIMER, and LICENSE:
//
// If you modify this file, you may insert additional notices
// immediately following this sentence.
//
// Copyright 1996-2003 Scott Robert Ladd.
// All rights reserved, except as noted herein.
//
// This computer program source file is supplied "AS IS". Scott Robert
// Ladd (hereinafter referred to as "Author") disclaims all warranties,
// expressed or implied, including, without limitation, the warranties
// of merchantability and of fitness for any purpose. The Author
// assumes no liability for direct, indirect, incidental, special,
// exemplary, or consequential damages, which may result from the use
// of this software, even if advised of the possibility of such damage.
//
// The Author hereby grants anyone permission to use, copy, modify, and
// distribute this source code, or portions hereof, for any legal purpose,
// without fee, subject to the following restrictions:
//
// 1. The origin of this source code must not be misrepresented.
//
// 2. Altered versions must be plainly marked as such and must not
// be misrepresented as being the original source.
//
// 3. This Copyright notice may not be removed or altered from any
// source or altered source distribution.
//
// The Author specifically permits (without fee) and encourages the use
// of this source code for entertainment, education, or decoration. If
// you use this source code in a product, acknowledgment is not required
// but would be appreciated.
//
// Acknowledgement:
// This license is based on the wonderful simple license that
// accompanies libpng.
//
//-----------------------------------------------------------------------
// For more information on this software package, please visit
// Scott's web site, Coyote Gulch Productions, at:
//
// http://www.coyotegulch.com
//-----------------------------------------------------------------------
package com.coyotegulch.jisp;
/**
* A <code>ObjectIndex</code> throws a <code>DuplicateKey</code> when a key being added to the
* index is identical to a key already stored there. Each concrete index class
* determines the circumstances under which this exception is thrown. For example,
* a <code>BTreeIndex</code> will throw <code>DuplicateKey</code>
* when a call to the <code>insertKey</code> method finds an existing key that
* matches the insertion key; however, the <code>BTreeIndex.writeKey</code> method
* does not throw an exception for a duplicate key, instead replacing the record
* position associated with the extant key.
* <p>
* @author Scott Robert Ladd
* @see com.coyotegulch.jisp.ObjectIndex
* @see com.coyotegulch.jisp.BTreeIndex
*/
public class DuplicateKey extends DatabaseException
{
/**
* Constructs a new <code>DuplicateKey</code> with null as its error message string.
*/
public DuplicateKey()
{
super();
}
/**
* Constructs a new <code>DuplicateKey</code> with <code>message</code> as its error message string.
*
* @param message Error message string.
*/
public DuplicateKey(String message)
{
super(message);
}
}
jisp-2.5.1/com/coyotegulch/jisp/HashIndex.java 0100644 0001750 0001750 00000045147 07641135213 020342 0 ustar scott scott //-----------------------------------------------------------------------
// Java Indexed Serialization Package
// ----------------------------------
// HashIndex.java
//-----------------------------------------------------------------------
//
// COPYRIGHT NOTICE, DISCLAIMER, and LICENSE:
//
// If you modify this file, you may insert additional notices
// immediately following this sentence.
//
// Copyright 1996-2003 Scott Robert Ladd.
// All rights reserved, except as noted herein.
//
// This computer program source file is supplied "AS IS". Scott Robert
// Ladd (hereinafter referred to as "Author") disclaims all warranties,
// expressed or implied, including, without limitation, the warranties
// of merchantability and of fitness for any purpose. The Author
// assumes no liability for direct, indirect, incidental, special,
// exemplary, or consequential damages, which may result from the use
// of this software, even if advised of the possibility of such damage.
//
// The Author hereby grants anyone permission to use, copy, modify, and
// distribute this source code, or portions hereof, for any legal purpose,
// without fee, subject to the following restrictions:
//
// 1. The origin of this source code must not be misrepresented.
//
// 2. Altered versions must be plainly marked as such and must not
// be misrepresented as being the original source.
//
// 3. This Copyright notice may not be removed or altered from any
// source or altered source distribution.
//
// The Author specifically permits (without fee) and encourages the use
// of this source code for entertainment, education, or decoration. If
// you use this source code in a product, acknowledgment is not required
// but would be appreciated.
//
// Acknowledgement:
// This license is based on the wonderful simple license that
// accompanies libpng.
//
//-----------------------------------------------------------------------
// For more information on this software package, please visit
// Scott's web site, Coyote Gulch Productions, at:
//
// http://www.coyotegulch.com
//-----------------------------------------------------------------------
package com.coyotegulch.jisp;
import java.io.*;
/**
* <code>HashIndex</code> associates a <code>key</code> value with a reference to persistent data,
* using a disk-based hash table. The index assumes that the <code>position</code> of a serializable
* object is constant, regardless of the actual meaning of the <code>long</code> position. In
* general, the position represents the location (file pointer) of a <code>Serializable</code>
* object in an <code>IndexedObjectDatabase</code>.
* <p>
* Use the <code>IndexedObjectDatabase.attachIndex</code> method to attach a <code>BTreeIndex</code>
* to a database. A database updates all attached indexes when it writes or removes objects
* from its file.
* <p>
* <b>This class should not be used in new code.</b> It was originally design to illustrate
* algorithms, and it suffers from a number of performance problems. A better, more efficient
* hash-bvased index will be introduced in version 3.0 of Jisp.
*
* @deprecated As of Jisp versioon 2.5.0, the HashIndex class is deprecated; it will be replaced in
* Jisp 3.0 by a more efficient and simpler hash-based index.
* @author Scott Robert Ladd
* @see com.coyotegulch.jisp.ObjectIndex
*/
public class HashIndex implements ObjectIndex
{
// class storage
private static final long NULL_POS = -1L;
// working storage
private String m_name;
private ObjectDatabaseFile m_file;
private HashIndexHeader m_header;
//
// constructors
//
/**
* Creates the file as a <code>HashIndex</code>. The initial length of each list is
* based on <code>numBuckets</code> and <code>macRecords</code>. The null key is a "blank" key; obtain
* a null key for any <code>KeyObject</code> type by calling the <code>KeyObject.makeNullKey</code>
* method.
* <p>
* @param name The name of the external index file to be opened.
* @param numBuckets The number of lists in the hash table; this is also known as the "hash factor."
* Use prime numbers to limit the number of collisions and increase the
* efficiency of the index.
* @param maxRecords The expected number of records to be indexed. This is <code>not</code> a limit
* on the index size; the index will expand to handle up to 2 billion records.
* However, the best performance is obtained by setting <code>maxRecords</code>
* to a value that reflects the expected size of the database.
* @param nullKey The null key serves two purposes: to identify a blank table entry,
* and to perform type-checking on new keys added to the index. All
* keys added to the index must have the same type as <code>nullkey</code>.
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @see com.coyotegulch.jisp.KeyObject
*/
public HashIndex(String name, int numBuckets, int maxRecords, KeyObject nullKey) throws IOException, ClassNotFoundException
{
// superclass constructor
m_name = new String(name);
m_file = new ObjectDatabaseFile(name,true);
// generate header
m_header = new HashIndexHeader();
if (numBuckets > 0)
m_header.m_nBuckets = numBuckets;
else
m_header.m_nBuckets = 101;
m_header.m_bucketPos = new long [m_header.m_nBuckets];
for (int n = 0; n < m_header.m_nBuckets; ++n)
m_header.m_bucketPos[n] = NULL_POS;
m_header.m_nullKey = nullKey.makeNullKey();
m_header.m_padding = maxRecords / numBuckets + 1;
if (m_header.m_padding < 10)
m_header.m_padding = 10;
// write header
m_file.rewind();
m_file.writeObject(m_header);
}
/**
* Opens a file as a <code>HashIndex</code>.
* <p>
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @param name The name of the external index file to be opened.
*/
public HashIndex(String name) throws IOException, ClassNotFoundException
{
// superclass constructor
m_file = new ObjectDatabaseFile(name,false);
// read header
m_file.rewind();
m_header = (HashIndexHeader)m_file.readObject();
}
//
// methods
//
/**
* Insert a key into the database, associating a record position with the given key.
*
* @param key A key identifying the record to be read.
* @param pos File position of record associated with key
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @throws DuplicateKey when inserting a duplicate key into an index that does not
* support duplicates
* @see com.coyotegulch.jisp.DuplicateKey
* @see com.coyotegulch.jisp.KeyObject
*/
public void insertKey(KeyObject key, long pos) throws IOException, DuplicateKey, ClassNotFoundException
{
// calculate bucket
int n = key.hashCode() % m_header.m_nBuckets;
HashIndexBucket bucket = null;
boolean new_bucket;
// does this bucket exist?
if (m_header.m_bucketPos[n] == NULL_POS)
{
// create a new bucket record
bucket = new HashIndexBucket();
bucket.m_key = new KeyObject [m_header.m_padding];
bucket.m_pos = new long [m_header.m_padding];
for (int i = 0; i < m_header.m_padding; ++i)
{
bucket.m_key[i] = m_header.m_nullKey.makeNullKey();
bucket.m_pos[i] = NULL_POS;
}
bucket.m_empty = m_header.m_padding;
new_bucket = true;
}
else
{
// read existing bucket
m_file.seek(m_header.m_bucketPos[n]);
bucket = (HashIndexBucket)m_file.readObject();
new_bucket = false;
}
// do we need to extend the bucket's size?
int where;
if (bucket.m_empty == 0)
{
int new_len = bucket.m_key.length + m_header.m_padding;
KeyObject [] new_key = new KeyObject [new_len];
long [] new_pos = new long [new_len];
for (int i = 0; i < new_len; ++i)
{
if (i >= bucket.m_key.length)
{
new_key[i] = m_header.m_nullKey.makeNullKey();
new_pos[i] = NULL_POS;
}
else
{
new_key[i] = bucket.m_key[i];
new_pos[i] = bucket.m_pos[i];
}
}
// location of new entry
where = bucket.m_key.length;
// assign expanded arrays to bucket
bucket.m_key = new_key;
bucket.m_pos = new_pos;
bucket.m_empty = m_header.m_padding - 1;
// add new entry
bucket.m_key[where] = key;
bucket.m_pos[where] = pos;
// delete existing bucket
m_file.seek(m_header.m_bucketPos[n]);
m_file.delete();
// write new bucket & store position in header
m_header.m_bucketPos[n] = m_file.writeObject(bucket);
// rewrite header
m_file.rewind();
m_file.rewriteObject(m_header);
}
else
{
for (where = 0; bucket.m_pos[where] != NULL_POS; ++where)
;
// add new entry
bucket.m_key[where] = key;
bucket.m_pos[where] = pos;
--bucket.m_empty;
// rewrite bucket
if (new_bucket)
{
// write new bucket & store position in header
m_header.m_bucketPos[n] = m_file.writeObject(bucket);
// rewrite header
m_file.rewind();
m_file.rewriteObject(m_header);
}
else
{
m_file.seek(m_header.m_bucketPos[n]);
m_file.rewriteObject(bucket);
}
}
}
/**
* Replace the reference pos for the given key.
*
* @param key A key identifying the record to be read.
* @param pos File position of record associated with key
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @throws KeyNotFound when the specified key can not be found in the index
* @see com.coyotegulch.jisp.KeyNotFound
* @see com.coyotegulch.jisp.KeyObject
*/
public void replaceKey(KeyObject key, long pos) throws IOException, ClassNotFoundException
{
try
{
removeKey(key);
}
catch (KeyNotFound ex)
{
// ignore it
}
insertKey(key,pos);
}
/**
* If the key already exists, replace the reference pos for the given key. Otherwise, insert
* a key into the database, associating a record position with the given key.
*
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @param key A key identifying the record to be read.
* @param pos File position of record associated with key
* @see com.coyotegulch.jisp.KeyObject
*/
public void storeKey(KeyObject key, long pos) throws IOException, ClassNotFoundException
{
replaceKey(key,pos);
}
/**
* Find the position of the object associated with a given key.
*
* @param key A key identifying the record to be read.
* @return The position of the record associated with <code>key</code>.
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @throws KeyNotFound when the specified key can not be found in the index
* @see com.coyotegulch.jisp.KeyNotFound
* @see com.coyotegulch.jisp.KeyObject
*/
public long findKey(KeyObject key) throws KeyNotFound, IOException, ClassNotFoundException
{
// calculate bucket
int n = key.hashCode() % m_header.m_nBuckets;
HashIndexBucket bucket = null;
// does this bucket exist?
if (m_header.m_bucketPos[n] == NULL_POS)
throw new KeyNotFound();
// read bucket
m_file.seek(m_header.m_bucketPos[n]);
bucket = (HashIndexBucket)m_file.readObject();
// search for key
boolean found = false;
int i;
for (i = 0; i < bucket.m_key.length; ++i)
{
if ((bucket.m_key[i] != null) && (key.compareTo(bucket.m_key[i]) == KeyObject.KEY_EQUAL))
{
found = true;
break;
}
}
if (!found)
throw new KeyNotFound();
// return the associated record position
return bucket.m_pos[i];
}
/**
* Removes the given key from the index.
*
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException for a casting error, usually when a persistent object or index does
* match the expected type
* @throws KeyNotFound when the specified key can not be found in the index
* @param key A key identifying the record to be read.
* @see com.coyotegulch.jisp.KeyNotFound
* @see com.coyotegulch.jisp.KeyObject
*/
public void removeKey(KeyObject key) throws IOException, ClassNotFoundException
{
// calculate bucket
int n = key.hashCode() % m_header.m_nBuckets;
HashIndexBucket bucket = null;
// does this bucket exist?
if (m_header.m_bucketPos[n] == NULL_POS)
throw new KeyNotFound();
// read bucket
m_file.seek(m_header.m_bucketPos[n]);
bucket = (HashIndexBucket)m_file.readObject();
// search for key
boolean found = false;
int i;
for (i = 0; i < bucket.m_key.length; ++i)
{
if ((bucket.m_key[i] != null) && (key.compareTo(bucket.m_key[i]) == KeyObject.KEY_EQUAL))
{
found = true;
break;
}
}
if (!found)
throw new KeyNotFound();
// remove key
bucket.m_key[i] = m_header.m_nullKey.makeNullKey();
bucket.m_pos[i] = NULL_POS;
++bucket.m_empty;
// delete existing bucket
m_file.seek(m_header.m_bucketPos[n]);
m_file.delete();
// write new bucket & store position in header
m_header.m_bucketPos[n] = m_file.writeObject(bucket);
// rewrite header
m_file.rewind();
m_file.rewriteObject(m_header);
}
/**
* Improves the performance of this <code>HashIndex</code> by optimizing the
* index contents.
*
*/
public void optimize() throws IOException, ClassNotFoundException
{
// create new file
String temp_name = "" + System.currentTimeMillis() + ".tmp";
ObjectDatabaseFile new_file = new ObjectDatabaseFile(temp_name,true);
// create a new header
HashIndexHeader new_header = new HashIndexHeader();
new_header.m_nBuckets = m_header.m_nBuckets;
new_header.m_nullKey = m_header.m_nullKey.makeNullKey();
new_header.m_padding = m_header.m_padding;
new_header.m_bucketPos = (long [])m_header.m_bucketPos.clone();
// rewrite header
new_file.rewind();
new_file.writeObject(new_header);
// copy records
for (int n = 0; n < m_header.m_nBuckets; ++n)
{
// read old record
if (m_header.m_bucketPos[n] != NULL_POS)
{
m_file.seek(m_header.m_bucketPos[n]);
HashIndexBucket bucket = (HashIndexBucket)m_file.readObject();
// update header
new_header.m_bucketPos[n] = new_file.writeObject(bucket);
}
}
// rewrite header
new_file.rewind();
new_file.rewriteObject(new_header);
// close new file
new_file.close();
// delete old file
m_file.close();
m_file = null;
File f_old = new File(m_name);
f_old.delete();
// rename new file
File f_new = new File(temp_name);
f_new.renameTo(f_old);
// reopen new file as current file
m_file = new ObjectDatabaseFile(m_name,false);
// use new header
m_header = new_header;
}
public void close() throws IOException
{
if (m_file != null)
{
m_file.close();
m_file = null;
}
}
}
jisp-2.5.1/com/coyotegulch/jisp/HashIndexBucket.java 0100644 0001750 0001750 00000004651 07633366244 021506 0 ustar scott scott //-----------------------------------------------------------------------
// Java Indexed Serialization Package
// ----------------------------------
// HashIndexBucket.java
//-----------------------------------------------------------------------
//
// COPYRIGHT NOTICE, DISCLAIMER, and LICENSE:
//
// If you modify this file, you may insert additional notices
// immediately following this sentence.
//
// Copyright 1996-2003 Scott Robert Ladd.
// All rights reserved, except as noted herein.
//
// This computer program source file is supplied "AS IS". Scott Robert
// Ladd (hereinafter referred to as "Author") disclaims all warranties,
// expressed or implied, including, without limitation, the warranties
// of merchantability and of fitness for any purpose. The Author
// assumes no liability for direct, indirect, incidental, special,
// exemplary, or consequential damages, which may result from the use
// of this software, even if advised of the possibility of such damage.
//
// The Author hereby grants anyone permission to use, copy, modify, and
// distribute this source code, or portions hereof, for any legal purpose,
// without fee, subject to the following restrictions:
//
// 1. The origin of this source code must not be misrepresented.
//
// 2. Altered versions must be plainly marked as such and must not
// be misrepresented as being the original source.
//
// 3. This Copyright notice may not be removed or altered from any
// source or altered source distribution.
//
// The Author specifically permits (without fee) and encourages the use
// of this source code for entertainment, education, or decoration. If
// you use this source code in a product, acknowledgment is not required
// but would be appreciated.
//
// Acknowledgement:
// This license is based on the wonderful simple license that
// accompanies libpng.
//
//-----------------------------------------------------------------------
// For more information on this software package, please visit
// Scott's web site, Coyote Gulch Productions, at:
//
// http://www.coyotegulch.com
//-----------------------------------------------------------------------
package com.coyotegulch.jisp;
import java.io.*;
class HashIndexBucket implements Serializable
{
//
// fields
//
public KeyObject [] m_key = null;
public long [] m_pos = null;
public int m_empty = 0;
}
jisp-2.5.1/com/coyotegulch/jisp/HashIndexHeader.java 0100644 0001750 0001750 00000004714 07633366244 021461 0 ustar scott scott //-----------------------------------------------------------------------
// Java Indexed Serialization Package
// ----------------------------------
// HashIndexHeader.java
//-----------------------------------------------------------------------
//
// COPYRIGHT NOTICE, DISCLAIMER, and LICENSE:
//
// If you modify this file, you may insert additional notices
// immediately following this sentence.
//
// Copyright 1996-2003 Scott Robert Ladd.
// All rights reserved, except as noted herein.
//
// This computer program source file is supplied "AS IS". Scott Robert
// Ladd (hereinafter referred to as "Author") disclaims all warranties,
// expressed or implied, including, without limitation, the warranties
// of merchantability and of fitness for any purpose. The Author
// assumes no liability for direct, indirect, incidental, special,
// exemplary, or consequential damages, which may result from the use
// of this software, even if advised of the possibility of such damage.
//
// The Author hereby grants anyone permission to use, copy, modify, and
// distribute this source code, or portions hereof, for any legal purpose,
// without fee, subject to the following restrictions:
//
// 1. The origin of this source code must not be misrepresented.
//
// 2. Altered versions must be plainly marked as such and must not
// be misrepresented as being the original source.
//
// 3. This Copyright notice may not be removed or altered from any
// source or altered source distribution.
//
// The Author specifically permits (without fee) and encourages the use
// of this source code for entertainment, education, or decoration. If
// you use this source code in a product, acknowledgment is not required
// but would be appreciated.
//
// Acknowledgement:
// This license is based on the wonderful simple license that
// accompanies libpng.
//
//-----------------------------------------------------------------------
// For more information on this software package, please visit
// Scott's web site, Coyote Gulch Productions, at:
//
// http://www.coyotegulch.com
//-----------------------------------------------------------------------
package com.coyotegulch.jisp;
import java.io.*;
class HashIndexHeader implements Serializable
{
// fields
public int m_nBuckets = 0;
public int m_padding = 0;
public long [] m_bucketPos = null;
public KeyObject m_nullKey = null;
}
jisp-2.5.1/com/coyotegulch/jisp/Huffman.java 0100644 0001750 0001750 00000034107 07633366244 020060 0 ustar scott scott //-----------------------------------------------------------------------
// Java Indexed Serialization Package
// ----------------------------------
// Huffman.java
//-----------------------------------------------------------------------
//
// COPYRIGHT NOTICE, DISCLAIMER, and LICENSE:
//
// If you modify this file, you may insert additional notices
// immediately following this sentence.
//
// Copyright 1996-2003 Scott Robert Ladd.
// All rights reserved, except as noted herein.
//
// This computer program source file is supplied "AS IS". Scott Robert
// Ladd (hereinafter referred to as "Author") disclaims all warranties,
// expressed or implied, including, without limitation, the warranties
// of merchantability and of fitness for any purpose. The Author
// assumes no liability for direct, indirect, incidental, special,
// exemplary, or consequential damages, which may result from the use
// of this software, even if advised of the possibility of such damage.
//
// The Author hereby grants anyone permission to use, copy, modify, and
// distribute this source code, or portions hereof, for any legal purpose,
// without fee, subject to the following restrictions:
//
// 1. The origin of this source code must not be misrepresented.
//
// 2. Altered versions must be plainly marked as such and must not
// be misrepresented as being the original source.
//
// 3. This Copyright notice may not be removed or altered from any
// source or altered source distribution.
//
// The Author specifically permits (without fee) and encourages the use
// of this source code for entertainment, education, or decoration. If
// you use this source code in a product, acknowledgment is not required
// but would be appreciated.
//
// Acknowledgement:
// This license is based on the wonderful simple license that
// accompanies libpng.
//
//-----------------------------------------------------------------------
// For more information on this software package, please visit
// Scott's web site, Coyote Gulch Productions, at:
//
// http://www.coyotegulch.com
//-----------------------------------------------------------------------
package com.coyotegulch.jisp;
import java.io.*;
/**
* Compresses and decompresses objects using the Huffman algorithm. Huffman
* encoding creates a set of codes for which the shortest code represents the
* most common piece of data. Codes created by the Huffman algorithm require
* a file to be analyzed, counting bytes to determine their frequency. From
* the frequencies, the Huffman algorithm builds a table of codes used to
* compress the information. Including the table of codes with the compressed
* data allows the original file to be reconstructed.
* <p>
* To be most effective, Huffman encoding uses a variable length code, where
* no code is a prefix of another, which makes decompression easier by allowing
* the extraction of the file bit-by-bit. The shortest codes are assigned to
* the most common characters, with infrequent characters receiving longer codes.
* <p>
* Objects to be compressed must be Serializable.
*
* @author Scott Robert Ladd
* @see com.coyotegulch.jisp.HuffmanEncoded
*/
public class Huffman
{
/**
* Encodes an object using Huffman compression.
*
* @param obj serializable object to be compressed
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @return a new <code>HuffmanEncoded</code> object containing the compressed
* object and its encoding table
* @see HuffmanEncoded
*/
public static HuffmanEncoded encode(Object obj) throws IOException
{
// serialize object
if ((obj instanceof Serializable) || (obj instanceof Externalizable))
{
// create an output byte array
ByteArrayOutputStream raw = new ByteArrayOutputStream();
// create an object Output stream
ObjectOutputStream out = new ObjectOutputStream(raw);
// write object to output stream
out.writeObject(obj);
out.flush();
// encode bytes
return compress(raw.toByteArray());
}
else
throw new HuffmanException("can't encode non-serializable object");
}
/**
* Decodes a compressed object using the Huffman algorithm.
*
* @param enc object to be decompressed
* @throws IOException when an I/O exception is thrown by an underlying java.io.* class
* @throws ClassNotFoundException when an explicit cast fails
* @return the decompressed <code>Object</code>
* @see HuffmanEncoded
*/
public static Object decode(HuffmanEncoded enc) throws IOException, ClassNotFoundException
{
// decode compressed data
byte [] decoded = decompress(enc);
// create byte input stream from decoded bytes
ByteArrayInputStream raw = new ByteArrayInputStream(decoded);
// create an object input stream
ObjectInputStream in = new ObjectInputStream(raw);
// return the object
return in.readObject();
}
private static void heapAdjust(int [] freq, int [] heap, int n, int k)
{
// this function compares the values in the array
// 'freq' to order the elements of 'heap' according
// in an inverse heap.
int j;
int v = heap[k - 1];
while (k <= (n / 2))
{
j = k + k;
if ((j < n) && (freq[heap[j - 1]] > freq[heap[j]]))
++j;
if (freq[v] < freq[heap[j - 1]])
break;
heap[k - 1] = heap[j - 1];
k = j;
}
heap[k - 1] = v;
}
// Huffman compression function
private static HuffmanEncoded compress(byte [] info)
{
// get length of info
int bytes = info.length;
// allocate data space
byte [] edata = new byte [bytes + 1];
// allocate frequency table
int [] freq = new int [512];
// allocate heap
int [] heap = new int [256];
// allocate link array
int [] link = new int [512];
// create work area
HuffmanEncoded encoded = new HuffmanEncoded();
int [] code = encoded.m_header.m_code;
short [] clen = encoded.m_header.m_codeLength;
// count frequencies
int i;
byte a = -1;
for (i = 0; i < bytes; ++i)
++freq[info[i] < 0 ? 256 + info[i] : info[i]];
// create indirect heap based on frequencies
int n = 0;
for (i = 0; i < 256; ++i)
{
if (freq[i] != 0)
{
heap[n] = i;
++n;
}
}
for (i = n; i > 0; --i)
heapAdjust(freq,heap,n,i);
// generate a trie from heap
int temp;
// at this point, n contains the number of characters
// that occur in the info array
while (n > 1)
{
// take first item from top of heap
--n;
temp = heap[0];
heap[0] = heap[n];
// adjust the heap to maintain properties
heapAdjust(freq,heap,n,1);
// in upper half of freq array, store sums of
// the two smallest frequencies from the heap
freq[256 + n] = freq[heap[0]] + freq[temp];
link[temp] = 256 + n; // parent
link[heap[0]] = -256 - n; // left child
heap[0] = 256 + n; // right child
// adjust the heap again
heapAdjust(freq,heap,n,1);
}
link[256 + n] = 0;
// generate codes
int j, k, x, maxx = 0, maxi = 0;
int l;
for (k = 0; k < 256; ++k)
{
if (freq[k] == 0) // character does not occur
{
code[k] = 0;
clen[k] = 0;
}
else
{
i = 0; // length of current code
j = 1; // bit being set in code
x = 0; // code being built
l = link[k]; // link in trie
while (l != 0) // while not at end of trie
{
if (l < 0) // left link (negative)
{
x += j; // insert 1 into code
l = -l; // reverse sign
}
l = link[l]; // move to next link
j <<= 1; // next bit to be set
++i; // increment code length
}
code[k] = x; // save code
clen[k] = (short)i; // save code len
// keep track of biggest key
if (x > maxx)
maxx = x;
// keep track of longest key
if (i > maxi)
maxi = i;
}
}
// make sure longest codes fit in unsigned long-bits
if (maxi > 32)
throw new HuffmanException("code size overflow");
// encode data
int mask; // mask for extracting bits
int nout = 0; // number of bytes output
byte bout = 0; // byte of encoded data
int bit = -1; // count of bits stored in bout
// watch for one-value file!
if (maxx == 0)
{
edata[0] = (byte)info[0];
nout = 1;
encoded.m_header.m_oneValue = true;
}
else
{
for (j = 0; j < bytes; ++j)
{
int ibyte = info[j] < 0 ? 256 + info[j] : info[j];
// start copying at first bit of code
mask = 1 << (clen[ibyte] - 1);
// copy code bits
for (i = 0; i < clen[ibyte]; ++i)
{
if (bit == 7)
{
// store full output byte
edata[nout] = bout;
++nout;
// check for overflow
if (nout == bytes)
throw new HuffmanException("compression overflow");
bit = 0;
bout = 0;
}
else
{
// move to next bit
++bit;
bout <<= 1;
}
if ((code[ibyte] & mask) != 0)
bout |= 1;
mask >>>= 1;
}
}
// o 