Ghidra is a software reverse engineering (SRE) framework
/* ###
* IP: GHIDRA
*
* Licensed 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 db;
import java.io.IOException;
import ghidra.util.exception.AssertException;
import ghidra.util.exception.CancelledException;
import ghidra.util.task.TaskMonitor;
/**
* <code>IndexTable</code> maintains a secondary index within a private Table instance.
* This index facilitates the indexing of non-unique secondary keys within a
* user Table.
*/
abstract class IndexTable {
protected static final Field[] emptyKeyArray = Field.EMPTY_ARRAY;
/**
* Database Handle
*/
protected final DBHandle db;
/**
* Master table record for this index table.
*/
protected final TableRecord indexTableRecord;
/**
* Primary table
*/
protected Table primaryTable;
/**
* Underlying table which contains secondary index data.
*/
protected Table indexTable;
/**
* Indexed column within primary table schema.
*/
protected final int indexColumn;
protected final boolean isSparseIndex;
/**
* Construct a new or existing secondary index. An existing index must have
* its root ID specified within the tableRecord.
* @param primaryTable primary table.
* @param indexTableRecord specifies the index parameters.
* @throws IOException thrown if IO error occurs
*/
IndexTable(Table primaryTable, TableRecord indexTableRecord) throws IOException {
if (!primaryTable.useLongKeys() && !primaryTable.useFixedKeys()) {
throw new AssertException("Only fixed-length key tables may be indexed");
}
this.db = primaryTable.getDBHandle();
this.primaryTable = primaryTable;
this.indexTableRecord = indexTableRecord;
this.indexTable = new Table(primaryTable.getDBHandle(), indexTableRecord);
this.indexColumn = indexTableRecord.getIndexedColumn();
this.isSparseIndex = primaryTable.getSchema().isSparseColumn(indexColumn);
primaryTable.addIndex(this);
}
/**
* Get the index table for a specified index TableRecord.
* @param db database handle
* @param indexTableRecord master table record for an index table
* @return IndexTable index table
* @throws IOException thrown if IO error occurs
*/
static IndexTable getIndexTable(DBHandle db, TableRecord indexTableRecord) throws IOException {
String name = indexTableRecord.getName();
Table primaryTable = db.getTable(name);
if (primaryTable == null) {
throw new AssertException("Table not found: " + name);
}
Field keyFieldType = indexTableRecord.getSchema().getKeyFieldType();
if (keyFieldType instanceof IndexField) {
return new FieldIndexTable(primaryTable, indexTableRecord);
}
throw new AssertException(
"Unexpected index field type: " + keyFieldType.getClass().getName());
}
/**
* Create a new index table for an empty primary table.
* @param primaryTable primary table to be indexed
* @param indexColumn primary table column to be indexed
* @return IndexTable new index table
* @throws IOException thrown if IO error occurs
*/
static IndexTable createIndexTable(Table primaryTable, int indexColumn) throws IOException {
if (primaryTable.getRecordCount() != 0) {
throw new AssertException();
}
return new FieldIndexTable(primaryTable, indexColumn);
}
/**
* Check the consistency of this index table.
* @param monitor task monitor
* @return true if consistency check passed, else false
* @throws IOException if IO error occurs
* @throws CancelledException if task cancelled
*/
boolean isConsistent(TaskMonitor monitor) throws IOException, CancelledException {
return indexTable.isConsistent(primaryTable.getSchema().getFieldNames()[indexColumn],
monitor);
}
/**
* Get the primary table key type
* @return primary table key type
*/
Field getPrimaryTableKeyType() {
return primaryTable.getSchema().getKeyFieldType();
}
/**
* Get the table number associated with the underlying index table.
* @return table number
*/
long getTableNum() {
return indexTable.getTableNum();
}
/**
* Get the indexed column within the primary table schema.
* @return indexed column number
*/
int getColumnIndex() {
return indexColumn;
}
/**
* Get index table statistics
* @return statistics data
* @throws IOException thrown if IO error occurs
*/
TableStatistics getStatistics() throws IOException {
TableStatistics stats = indexTable.getStatistics();
stats.indexColumn = indexColumn;
return stats;
}
/**
* Determine if there is an occurance of the specified index key value.
* @param field index key value
* @return true if an index key value equal to field exists.
* @throws IOException if IO error occurs
*/
boolean hasRecord(Field field) throws IOException {
return indexTable.hasRecord(field);
}
/**
* Find all primary keys which correspond to the specified indexed field
* value.
* @param indexValue the field value to search for.
* @return list of primary keys
* @throws IOException if IO error occurs
*/
abstract Field[] findPrimaryKeys(Field indexValue) throws IOException;
/**
* Get the number of primary keys which correspond to the specified indexed field
* value.
* @param indexValue the field value to search for.
* @return key count
* @throws IOException if IO error occurs
*/
abstract int getKeyCount(Field indexValue) throws IOException;
/**
* Add an entry to this index. Caller is responsible for ensuring that this
* is not a duplicate entry.
* @param record new record
* @throws IOException if IO error occurs
*/
abstract void addEntry(DBRecord record) throws IOException;
/**
* Delete an entry from this index.
* @param oldRecord deleted record
* @throws IOException if IO error occurs
*/
abstract void deleteEntry(DBRecord oldRecord) throws IOException;
/**
* Delete all records within this index table.
* @throws IOException if IO error occurs
*/
void deleteAll() throws IOException {
indexTable.deleteAll();
}
/**
* Iterate over all index keys. Index keys are sorted in ascending order.
* @return index key iterator
* @throws IOException thrown if IO error occurs
*/
abstract DBFieldIterator indexIterator() throws IOException;
/**
* Iterate over all the unique index field values within the specified range identified
* by minField and maxField. Index values are returned in an ascending sorted order.
* @param minField minimum index column value, if null absolute minimum is used
* @param maxField maximum index column value, if null absolute maximum is used
* @param before if true initial position is before minField, else position
* is after endField
* @return index field iterator.
* @throws IOException if IO error occurs
*/
abstract DBFieldIterator indexIterator(Field minField, Field maxField, boolean before)
throws IOException;
/**
* Iterate over all the unique index field values within the specified range identified
* by minField and maxField. Index values are returned in an ascending sorted order with the
* initial iterator position corresponding to the startField.
* @param minField minimum index column value, if null absolute minimum is used
* @param maxField maximum index column value, if null absolute maximum is used
* @param startField index column value corresponding to initial position of iterator
* @param before if true initial position is before startField value, else position
* is after startField value
* @return index field iterator.
* @throws IOException if IO error occurs
*/
abstract DBFieldIterator indexIterator(Field minField, Field maxField, Field startField,
boolean before) throws IOException;
/**
* Iterate over all primary keys sorted based upon the associated index key.
* @return primary key iterator
* @throws IOException thrown if IO error occurs
*/
abstract DBFieldIterator keyIterator() throws IOException;
/**
* Iterate over all primary keys sorted based upon the associated index key.
* The iterator is initially positioned before the first index buffer whose index key
* is greater than or equal to the specified startField value.
* @param startField index key value which determines initial position of iterator
* @return primary key iterator
* @throws IOException thrown if IO error occurs
*/
abstract DBFieldIterator keyIteratorBefore(Field startField) throws IOException;
/**
* Iterate over all primary keys sorted based upon the associated index key.
* The iterator is initially positioned after the index buffer whose index key
* is equal to the specified startField value or immediately before the first
* index buffer whose index key is greater than the specified startField value.
* @param startField index key value which determines initial position of iterator
* @return primary key iterator
* @throws IOException thrown if IO error occurs
*/
abstract DBFieldIterator keyIteratorAfter(Field startField) throws IOException;
/**
* Iterate over all primary keys sorted based upon the associated index key.
* The iterator is initially positioned before the primaryKey within the index buffer
* whose index key is equal to the specified startField value or immediately before the first
* index buffer whose index key is greater than the specified startField value.
* @param startField index key value which determines initial position of iterator
* @param primaryKey initial position within index buffer if index key matches startField value.
* @return primary key iterator
* @throws IOException thrown if IO error occurs
*/
abstract DBFieldIterator keyIteratorBefore(Field startField, Field primaryKey)
throws IOException;
/**
* Iterate over all primary keys sorted based upon the associated index key.
* The iterator is initially positioned after the primaryKey within the index buffer
* whose index key is equal to the specified startField value or immediately before the first
* index buffer whose index key is greater than the specified startField value.
* @param startField index key value which determines initial position of iterator
* @param primaryKey initial position within index buffer if index key matches startField value.
* @return primary key iterator
* @throws IOException thrown if IO error occurs
*/
abstract DBFieldIterator keyIteratorAfter(Field startField, Field primaryKey)
throws IOException;
/**
* Iterate over all primary keys sorted based upon the associated index key.
* The iterator is limited to range of index keys of minField through maxField, inclusive.
* If before is true, the iterator is initially positioned before the first index
* buffer whose index key is greater than or equal to the specified minField value.
* If before is false, the iterator is initially positioned after the first index
* buffer whose index key is less than or equal to the specified maxField value.
* @param minField minimum index key value
* @param maxField maximum index key value
* @param before if true, position iterator before minField value,
* Otherwise, position iterator after maxField value.
* @return primary key iterator
* @throws IOException thrown if IO error occurs
*/
abstract DBFieldIterator keyIterator(Field minField, Field maxField, boolean before)
throws IOException;
/**
* Iterate over all primary keys sorted based upon the associated index key.
* The iterator is limited to range of index keys of minField through maxField, inclusive.
* The iterator is initially positioned before or after the specified startField index value.
* @param minField minimum index key value
* @param maxField maximum index key value
* @param startField starting indexed value position
* @param before if true positioned before startField value, else positioned after maxField value
* @return primary key iterator
* @throws IOException thrown if IO error occurs
*/
abstract DBFieldIterator keyIterator(Field minField, Field maxField, Field startField,
boolean before) throws IOException;
}