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 java.util.ArrayList;
import java.util.NoSuchElementException;
/**
* <code>FieldIndexTable</code> provides a simplified index table whose key is
* a fixed or variable length {@link IndexField} which consists of a concatenation of
* the index field value and associated primary table key.
*/
public class FieldIndexTable extends IndexTable {
private static final Field[] fields = {};
private static final String[] fieldNames = {};
private final IndexField indexKeyType;
/**
* Construct a new secondary index which is based upon a specific field column within the
* primary table.
* @param primaryTable primary table
* @param colIndex field column index
* @throws IOException thrown if IO error occurs
*/
FieldIndexTable(Table primaryTable, int colIndex) throws IOException {
this(primaryTable, primaryTable.getDBHandle()
.getMasterTable()
.createTableRecord(
primaryTable.getName(), getIndexTableSchema(primaryTable, colIndex), colIndex));
}
/**
* 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 an IO error occurs
*/
FieldIndexTable(Table primaryTable, TableRecord indexTableRecord) throws IOException {
super(primaryTable, indexTableRecord);
indexKeyType = (IndexField) indexTable.getSchema().getKeyFieldType();
}
/**
* Generate index table schema for specified primaryTable and index column
* @param primaryTable primary table
* @param colIndex index column
* @return index table schema
*/
private static Schema getIndexTableSchema(Table primaryTable, int colIndex) {
Schema primarySchema = primaryTable.getSchema();
Field indexedField = primarySchema.getField(colIndex);
Field primaryKeyType = primarySchema.getKeyFieldType();
IndexField indexKeyField = new IndexField(indexedField, primaryKeyType);
return new Schema(0, indexKeyField, "IndexKey", fields, fieldNames);
}
@Override
Field[] findPrimaryKeys(Field indexValue) throws IOException {
IndexField indexField =
indexKeyType.newIndexField(indexValue, getPrimaryTableKeyType().getMinValue());
DBFieldIterator iter = indexTable.fieldKeyIterator(indexField);
ArrayList<IndexField> list = new ArrayList<>(20);
while (iter.hasNext()) {
IndexField f = (IndexField) iter.next();
if (!f.hasSameIndexValue(indexField)) {
break;
}
if (indexField.usesTruncatedFieldValue()) {
// Must check actual record if index value was truncated
DBRecord rec = primaryTable.getRecord(f.getPrimaryKey());
Field val = rec.getField(indexColumn);
if (!indexValue.equals(val)) {
continue;
}
}
list.add(f);
}
Field[] keys = new Field[list.size()];
for (int i = 0; i < keys.length; i++) {
IndexField f = list.get(i);
keys[i] = f.getPrimaryKey();
}
return keys;
}
@Override
int getKeyCount(Field indexValue) throws IOException {
return findPrimaryKeys(indexValue).length;
}
@Override
void addEntry(DBRecord record) throws IOException {
Field indexedField = record.getField(indexColumn);
if (isSparseIndex && indexedField.isNull()) {
return;
}
IndexField f = indexKeyType.newIndexField(indexedField, record.getKeyField());
DBRecord rec = indexTable.getSchema().createRecord(f);
indexTable.putRecord(rec);
}
@Override
void deleteEntry(DBRecord record) throws IOException {
Field indexedField = record.getField(indexColumn);
if (isSparseIndex && indexedField.isNull()) {
return;
}
IndexField f = indexKeyType.newIndexField(indexedField, record.getKeyField());
indexTable.deleteRecord(f);
}
@Override
DBFieldIterator indexIterator() throws IOException {
return new IndexFieldIterator();
}
@Override
DBFieldIterator indexIterator(Field minField, Field maxField, boolean before)
throws IOException {
return new IndexFieldIterator(minField, maxField, before);
}
@Override
DBFieldIterator indexIterator(Field minField, Field maxField, Field startField, boolean before)
throws IOException {
return new IndexFieldIterator(minField, maxField, startField, before);
}
/**
* Iterates over index field values within a specified range.
* NOTE: Index fields which have been truncated may be returned out of order.
*/
class IndexFieldIterator implements DBFieldIterator {
private IndexField min;
private IndexField max;
private IndexField lastKey;
private IndexField indexKey;
private DBFieldIterator indexIterator;
private boolean hasNext = false;
private boolean hasPrev = false;
/**
* Construct an index field iterator starting with the minimum index value.
* @throws IOException an IO error occurred
*/
IndexFieldIterator() throws IOException {
this(null, null, true);
}
/**
* Construct an index field iterator.
* @param minValue minimum index value or null if no minimum
* @param maxValue maximum index value or null if no maximum
* @param before if true initial position is before minValue, else position
* after maxValue
* @throws IOException an IO error occurred
*/
IndexFieldIterator(Field minValue, Field maxValue, boolean before) throws IOException {
if (primaryTable.getSchema().getField(indexColumn).isVariableLength()) {
throw new UnsupportedOperationException(
"Due to potential truncation issues, operation not permitted on variable length fields");
}
Field primaryKeyType = getPrimaryTableKeyType();
min = minValue != null
? indexKeyType.newIndexField(minValue, primaryKeyType.getMinValue())
: null;
max = maxValue != null
? indexKeyType.newIndexField(maxValue, primaryKeyType.getMaxValue())
: null;
IndexField start = null;
if (before && minValue != null) {
start = min;
}
else if (!before && maxValue != null) {
start = max;
}
if (start != null) {
indexIterator = indexTable.fieldKeyIterator(min, max, start);
}
else {
indexIterator = indexTable.fieldKeyIterator(min, max, before);
}
if (indexIterator.hasNext()) {
indexIterator.next();
if (before) {
indexIterator.previous();
}
}
}
/**
* Construct an index field iterator. The iterator is positioned at index
* value identified by startValue.
* @param minValue minimum index value or null if no minimum
* @param maxValue maximum index value or null if no maximum
* @param startValue initial index value position
* @param before if true initial position is before minValue, else position
* after maxValue
* @throws IOException an IO error occurred
*/
IndexFieldIterator(Field minValue, Field maxValue, Field startValue, boolean before)
throws IOException {
if (primaryTable.getSchema().getField(indexColumn).isVariableLength()) {
throw new UnsupportedOperationException(
"Due to potential truncation issues, operation not permitted on variable length fields");
}
if (startValue == null) {
throw new IllegalArgumentException("starting index value required");
}
Field primaryKeyType = getPrimaryTableKeyType();
min = minValue != null
? indexKeyType.newIndexField(minValue, primaryKeyType.getMinValue())
: null;
max = maxValue != null
? indexKeyType.newIndexField(maxValue, primaryKeyType.getMaxValue())
: null;
IndexField start = indexKeyType.newIndexField(startValue,
before ? primaryKeyType.getMinValue() : primaryKeyType.getMaxValue());
indexIterator = indexTable.fieldKeyIterator(min, max, start);
if (indexIterator.hasNext()) {
IndexField f = (IndexField) indexIterator.next();
if (before || !f.getIndexedField().equals(startValue)) {
indexIterator.previous();
}
}
}
@Override
public boolean hasNext() throws IOException {
if (hasNext) {
return true;
}
hasPrev = false; // TODO ???
indexKey = (IndexField) indexIterator.next();
int skipCnt = 0;
while (indexKey != null && indexKey.hasSameIndexValue(lastKey)) {
if (++skipCnt > 10) {
// Reinit iterator to skip large number of same index value
indexIterator =
indexTable.fieldKeyIterator(min, max, indexKeyType.newIndexField(
indexKey.getIndexedField(), getPrimaryTableKeyType().getMaxValue()));
skipCnt = 0;
}
indexKey = (IndexField) indexIterator.next();
}
if (indexKey == null) {
return false;
}
hasNext = true;
return true;
}
@Override
public boolean hasPrevious() throws IOException {
if (hasPrev) {
return true;
}
hasNext = false; // TODO ???
indexKey = (IndexField) indexIterator.previous();
int skipCnt = 0;
while (indexKey != null && indexKey.hasSameIndexValue(lastKey)) {
if (++skipCnt > 10) {
// Reinit iterator to skip large number of same index value
indexIterator =
indexTable.fieldKeyIterator(min, max, indexKeyType.newIndexField(
indexKey.getIndexedField(), getPrimaryTableKeyType().getMinValue()));
skipCnt = 0;
}
indexKey = (IndexField) indexIterator.previous();
}
if (indexKey == null) {
return false;
}
hasPrev = true;
return true;
}
@Override
public Field next() throws IOException {
if (hasNext || hasNext()) {
hasNext = false;
hasPrev = true;
lastKey = indexKey;
return indexKey.getIndexedField();
}
return null;
}
@Override
public Field previous() throws IOException {
if (hasPrev || hasPrevious()) {
hasNext = true;
hasPrev = false;
lastKey = indexKey;
return indexKey.getIndexedField();
}
return null;
}
/**
* Delete all primary records which have the current
* index value (lastKey).
* @see db.DBFieldIterator#delete()
*/
@Override
public boolean delete() throws IOException {
if (lastKey == null) {
return false;
}
synchronized (db) {
Field[] keys = findPrimaryKeys(lastKey.getIndexedField());
for (Field key : keys) {
primaryTable.deleteRecord(key);
}
lastKey = null;
return true;
}
}
}
@Override
boolean hasRecord(Field field) throws IOException {
IndexField indexField =
indexKeyType.newIndexField(field, getPrimaryTableKeyType().getMinValue());
DBFieldIterator iter = indexTable.fieldKeyIterator(indexField);
while (iter.hasNext()) {
IndexField f = (IndexField) iter.next();
if (!f.hasSameIndexValue(indexField)) {
return false;
}
if (indexField.usesTruncatedFieldValue()) {
// Must check actual record if index value was truncated
DBRecord rec = primaryTable.getRecord(f.getPrimaryKey());
Field val = rec.getField(indexColumn);
if (!field.equals(val)) {
continue; // skip
}
}
return true;
}
return false;
}
@Override
DBFieldIterator keyIterator() throws IOException {
return new PrimaryKeyIterator();
}
@Override
DBFieldIterator keyIteratorBefore(Field startField) throws IOException {
return new PrimaryKeyIterator(startField, false);
}
@Override
DBFieldIterator keyIteratorAfter(Field startField) throws IOException {
return new PrimaryKeyIterator(startField, true);
}
@Override
DBFieldIterator keyIteratorBefore(Field startField, Field primaryKey) throws IOException {
return new PrimaryKeyIterator(null, null, startField, primaryKey, false);
}
@Override
DBFieldIterator keyIteratorAfter(Field startField, Field primaryKey) throws IOException {
return new PrimaryKeyIterator(null, null, startField, primaryKey, true);
}
@Override
DBFieldIterator keyIterator(Field startField, Field endField, boolean atStart)
throws IOException {
return new PrimaryKeyIterator(startField, endField, atStart ? startField : endField,
atStart ? getPrimaryTableKeyType().getMinValue()
: getPrimaryTableKeyType().getMaxValue(),
!atStart);
}
@Override
DBFieldIterator keyIterator(Field minField, Field maxField, Field startField, boolean before)
throws IOException {
return new PrimaryKeyIterator(minField, maxField, startField,
before ? getPrimaryTableKeyType().getMinValue()
: getPrimaryTableKeyType().getMaxValue(),
!before);
}
/**
* Iterates over primary keys which correspond to index field values within a specified range.
* NOTE: Primary keys corresponding to index fields which have been truncated may be returned out of order.
*/
private class PrimaryKeyIterator implements DBFieldIterator {
private IndexField min;
private IndexField max;
private DBFieldIterator indexIterator;
private boolean hasNext = false;
private boolean hasPrev = false;
private IndexField key;
private IndexField lastKey;
/**
* Construct a key iterator starting with the minimum secondary key.
* @throws IOException thrown if IO error occurs
*/
PrimaryKeyIterator() throws IOException {
indexIterator = indexTable.fieldKeyIterator();
}
/**
* Construct a key iterator. The iterator is positioned immediately before
* the key associated with the first occurance of the startValue.
* @param startValue indexed field value.
* @param after if true the iterator is positioned immediately after
* the last occurance of the specified startValue position.
* @throws IOException thrown if IO error occurs
*/
PrimaryKeyIterator(Field startValue, boolean after) throws IOException {
this(null, null, startValue, after ? getPrimaryTableKeyType().getMaxValue()
: getPrimaryTableKeyType().getMinValue(),
after);
}
/**
* Construct a key iterator. The iterator is positioned immediately before
* or after the key associated with the specified startValue/primaryKey.
* @param minValue minimum index value or null if no minimum
* @param maxValue maximum index value or null if no maximum
* @param startValue starting index value.
* @param primaryKey starting primary key value (ignored if startValue is null).
* @param after if true iterator is positioned immediately after
* the startValue/primaryKey,
* otherwise immediately before.
* @throws IOException thrown if IO error occurs
*/
PrimaryKeyIterator(Field minValue, Field maxValue, Field startValue, Field primaryKey,
boolean after) throws IOException {
Field primaryKeyType = getPrimaryTableKeyType();
min = minValue != null
? indexKeyType.newIndexField(minValue, primaryKeyType.getMinValue())
: null;
max = maxValue != null
? indexKeyType.newIndexField(maxValue, primaryKeyType.getMaxValue())
: null;
IndexField start = null;
if (after && startValue == null && maxValue == null) {
indexIterator = indexTable.fieldKeyIterator(min, max, !after);
if (indexIterator.hasNext()) {
indexIterator.next(); // must step beyond max indexed value
}
}
else {
start =
startValue != null ? indexKeyType.newIndexField(startValue, primaryKey) : null;
indexIterator = indexTable.fieldKeyIterator(min, max, start);
if (indexIterator.hasNext()) {
Field f = indexIterator.next();
if (!after || !f.equals(start)) {
indexIterator.previous();
}
}
}
}
/**
* If min or max index values was truncated, a comparison of the actual
* indexed field value (i.e., primary table value) is done with the min and/or max values.
* @param f index field from index table iterator
* @return true if field value corresponding to f is outside the min/max range.
* It is assumed that the underlying table iterator will not return index values
* out of range which do not have the same truncated index value.
* @throws IOException thrown if IO error occurs
*/
private boolean indexValueOutOfRange(IndexField f) throws IOException {
Field val = null;
if (min != null && min.usesTruncatedFieldValue() && min.hasSameIndexValue(f)) {
DBRecord rec = primaryTable.getRecord(f.getPrimaryKey());
val = rec.getField(indexColumn);
if (val.compareTo(min.getNonTruncatedIndexField()) < 0) {
return true;
}
}
if (max != null && max.usesTruncatedFieldValue() && max.hasSameIndexValue(f)) {
if (val == null) {
DBRecord rec = primaryTable.getRecord(f.getPrimaryKey());
val = rec.getField(indexColumn);
}
if (val.compareTo(max.getNonTruncatedIndexField()) > 0) {
return true;
}
}
return false;
}
@Override
public boolean hasNext() throws IOException {
if (hasNext) {
return true;
}
while (indexIterator.hasNext()) {
hasPrev = false;
key = (IndexField) indexIterator.next();
if (!indexValueOutOfRange(key)) {
hasNext = true;
break;
}
}
return hasNext;
}
@Override
public boolean hasPrevious() throws IOException {
if (hasPrev) {
return true;
}
while (indexIterator.hasPrevious()) {
hasNext = false;
key = (IndexField) indexIterator.previous();
if (!indexValueOutOfRange(key)) {
hasPrev = true;
break;
}
}
return hasPrev;
}
@Override
public Field next() throws IOException {
if (hasNext()) {
lastKey = key;
hasNext = false;
return key.getPrimaryKey();
}
throw new NoSuchElementException();
}
@Override
public Field previous() throws IOException {
if (hasPrevious()) {
lastKey = key;
hasPrev = false;
return key.getPrimaryKey();
}
throw new NoSuchElementException();
}
@Override
public boolean delete() throws IOException {
if (lastKey != null) {
Field primaryKey = lastKey.getPrimaryKey();
lastKey = null;
return primaryTable.deleteRecord(primaryKey);
}
return false;
}
}
}