/*
Derby - Class org.apache.derby.iapi.store.access.DiskHashtable
Licensed to the Apache Software Foundation (ASF) under one or more
contributor license agreements. See the NOTICE file distributed with
this work for additional information regarding copyright ownership.
The ASF licenses this file to you under the Apache License, Version 2.0
(the "License"); you may not use this file except in compliance with
the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
package org.apache.derby.iapi.store.access;
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Properties;
import org.apache.derby.shared.common.reference.SQLState;
import org.apache.derby.iapi.error.StandardException;
import org.apache.derby.iapi.types.DataValueDescriptor;
import org.apache.derby.iapi.types.SQLInteger;
import org.apache.derby.iapi.types.RowLocation;
import org.apache.derby.iapi.types.StringDataValue;
import org.apache.derby.iapi.services.context.ContextService;
import org.apache.derby.iapi.services.io.FormatableBitSet;
import org.apache.derby.shared.common.sanity.SanityManager;
import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
/**
* This class is used by BackingStoreHashtable when the BackingStoreHashtable
* must spill to disk. It implements the methods of a hash table: put, get,
* remove, elements, however it is not implemented as a hash table. In order to
* minimize the amount of unique code it is implemented using a Btree and a
* heap conglomerate. The Btree indexes the hash code of the row key. The
* actual key may be too long for our Btree implementation.
*
* Created: Fri Jan 28 13:58:03 2005
*
* @version 1.0
*/
public class DiskHashtable
{
private final long rowConglomerateId;
private ConglomerateController rowConglomerate;
private final long btreeConglomerateId;
private ConglomerateController btreeConglomerate;
private final DataValueDescriptor[] btreeRow;
private final int[] key_column_numbers;
private final boolean remove_duplicates;
private final TransactionController tc;
private final DataValueDescriptor[] row;
private final DataValueDescriptor[] scanKey = { new SQLInteger()};
private int size;
private boolean keepStatistics;
private final boolean keepAfterCommit;
/**
* Creates a new DiskHashtable instance.
*
* @param tc
* @param template An array of DataValueDescriptors that
* serves as a template for the rows.
* @param key_column_numbers The indexes of the key columns (0 based)
* @param remove_duplicates If true then rows with duplicate keys are
* removed.
* @param keepAfterCommit If true then the hash table is kept after
* a commit
*/
public DiskHashtable(
TransactionController tc,
DataValueDescriptor[] template,
int[] collation_ids,
int[] key_column_numbers,
boolean remove_duplicates,
boolean keepAfterCommit)
throws StandardException
{
this.tc = tc;
this.key_column_numbers = key_column_numbers;
this.remove_duplicates = remove_duplicates;
this.keepAfterCommit = keepAfterCommit;
LanguageConnectionContext lcc = (LanguageConnectionContext)
ContextService.getContextOrNull(
LanguageConnectionContext.CONTEXT_ID);
keepStatistics = (lcc != null) && lcc.getRunTimeStatisticsMode();
// Create template row used for creating the conglomerate and
// fetching rows.
row = new DataValueDescriptor[template.length];
for( int i = 0; i < row.length; i++)
{
row[i] = template[i].getNewNull();
if (SanityManager.DEBUG)
{
// must have an object template for all cols in hash overflow.
SanityManager.ASSERT(
row[i] != null,
"Template for the hash table must have non-null object");
}
}
int tempFlags =
keepAfterCommit ?
(TransactionController.IS_TEMPORARY |
TransactionController.IS_KEPT) :
TransactionController.IS_TEMPORARY;
// create the "base" table of the hash overflow.
rowConglomerateId =
tc.createConglomerate(
"heap",
template,
(ColumnOrdering[]) null,
collation_ids,
(Properties) null,
tempFlags);
// open the "base" table of the hash overflow.
rowConglomerate =
tc.openConglomerate(
rowConglomerateId,
keepAfterCommit,
TransactionController.OPENMODE_FORUPDATE,
TransactionController.MODE_TABLE,
TransactionController.ISOLATION_NOLOCK/* Single thread only */);
// create the index on the "hash" base table. The key of the index
// is the hash code of the row key. The second column is the
// RowLocation of the row in the "base" table of the hash overflow.
btreeRow =
new DataValueDescriptor[]
{ new SQLInteger(), rowConglomerate.newRowLocationTemplate()};
Properties btreeProps = new Properties();
btreeProps.put("baseConglomerateId",
String.valueOf(rowConglomerateId));
btreeProps.put("rowLocationColumn",
"1");
btreeProps.put("allowDuplicates",
"false"); // Because the row location is part of the key
btreeProps.put("nKeyFields",
"2"); // Include the row location column
btreeProps.put("nUniqueColumns",
"2"); // Include the row location column
btreeProps.put("maintainParentLinks",
"false");
// default collation is used for hash code and row location
int[] index_collation_ids =
{StringDataValue.COLLATION_TYPE_UCS_BASIC,
StringDataValue.COLLATION_TYPE_UCS_BASIC};
btreeConglomerateId =
tc.createConglomerate(
"BTREE",
btreeRow,
(ColumnOrdering[]) null,
index_collation_ids,
btreeProps,
tempFlags);
// open the "index" of the hash overflow.
btreeConglomerate =
tc.openConglomerate(
btreeConglomerateId,
keepAfterCommit,
TransactionController.OPENMODE_FORUPDATE,
TransactionController.MODE_TABLE,
TransactionController.ISOLATION_NOLOCK /*Single thread only*/ );
} // end of constructor
public void close() throws StandardException
{
btreeConglomerate.close();
rowConglomerate.close();
tc.dropConglomerate( btreeConglomerateId);
tc.dropConglomerate( rowConglomerateId);
} // end of close
/**
* Put a new row in the overflow structure.
*
* @param row The row to be inserted.
*
* @return true if the row was added,
* false if it was not added (because it was a duplicate and we
* are eliminating duplicates).
*
* @exception StandardException standard error policy
*/
public boolean put(Object key, Object[] row)
throws StandardException
{
boolean isDuplicate = false;
if (remove_duplicates || keepStatistics)
{
// Go to the work of finding out whether it is a duplicate
isDuplicate = (getRemove(key, false, true) != null);
if (remove_duplicates && isDuplicate)
return false;
}
// insert the row into the "base" conglomerate.
rowConglomerate.insertAndFetchLocation(
(DataValueDescriptor[]) row, (RowLocation) btreeRow[1]);
// create index row from hashcode and rowlocation just inserted, and
// insert index row into index.
btreeRow[0].setValue( key.hashCode());
btreeConglomerate.insert( btreeRow);
if (keepStatistics && !isDuplicate)
size++;
return true;
} // end of put
/**
* Get a row from the overflow structure.
*
* @param key If the rows only have one key column then the key value.
* If there is more than one key column then a KeyHasher
*
* @return null if there is no corresponding row,
* the row (DataValueDescriptor[]) if there is exactly one row
* with the key, or
* a Vector of all the rows with the key if there is more than one.
*
* @exception StandardException
*/
public Object get(Object key)
throws StandardException
{
return getRemove(key, false, false);
}
private Object getRemove(Object key, boolean remove, boolean existenceOnly)
throws StandardException
{
int hashCode = key.hashCode();
int rowCount = 0;
DataValueDescriptor[] firstRow = null;
List allRows = null;
scanKey[0].setValue( hashCode);
ScanController scan =
tc.openScan(
btreeConglomerateId,
false, // do not hold
remove ? TransactionController.OPENMODE_FORUPDATE : 0,
TransactionController.MODE_TABLE,
TransactionController.ISOLATION_READ_UNCOMMITTED,
null, // Scan all the columns
scanKey,
ScanController.GE,
(Qualifier[][]) null,
scanKey,
ScanController.GT);
try
{
while (scan.fetchNext(btreeRow))
{
if (rowConglomerate.fetch(
(RowLocation) btreeRow[1],
row,
(FormatableBitSet) null /* all columns */)
&& rowMatches( row, key))
{
if( existenceOnly)
return this;
DataValueDescriptor[] clonedRow =
BackingStoreHashtable.shallowCloneRow(row);
rowCount++;
if( rowCount == 1)
{
// if there is only one matching row just return row.
firstRow = clonedRow;
}
else
{
// If there is more than one row, return a list of
// the rows.
//
if (allRows == null)
{
// convert the "single" row retrieved from the
// first trip in the loop, to a vector with the
// first two rows.
allRows = new ArrayList(2);
allRows.add(firstRow);
}
allRows.add(clonedRow);
}
if( remove)
{
rowConglomerate.delete( (RowLocation) btreeRow[1]);
scan.delete();
size--;
}
if( remove_duplicates)
// This must be the only row with the key
return clonedRow;
}
}
}
finally
{
scan.close();
}
if (allRows == null) {
// No duplicates. Return the single row, or null if no row was
// found for the given key.
return firstRow;
} else {
// Return list of all duplicate values.
return allRows;
}
} // end of getRemove
private boolean rowMatches(
DataValueDescriptor[] row,
Object key)
{
if( key_column_numbers.length == 1)
return row[ key_column_numbers[0]].equals( key);
KeyHasher kh = (KeyHasher) key;
for( int i = 0; i < key_column_numbers.length; i++)
{
if( ! row[ key_column_numbers[i]].equals( kh.getObject(i)))
return false;
}
return true;
} // end of rowMatches
/**
* remove all rows with a given key from the hash table.
*
* @param key The key of the rows to remove.
*
* @return The removed row(s).
*
* @exception StandardException Standard exception policy.
**/
public Object remove( Object key)
throws StandardException
{
return getRemove( key, true, false);
} // end of remove
/**
* @return The number of rows in the hash table
*/
public int size()
{
return size;
}
/**
* Return an Enumeration that can be used to scan entire table.
*
* RESOLVE - is it worth it to support this routine?
*
* @return The Enumeration.
*
* @exception StandardException Standard exception policy.
**/
public Enumeration
Ads help maintain this website.