org.mmtk.utility

Class SimpleHashtable

java.lang.Object

org.mmtk.utility.SimpleHashtable

Direct Known Subclasses:

SanityDataTable

public abstract class SimpleHashtable
extends Object

This class implements a simple hashtable. It is intended for use in sanity checking or debugging, not high-performance algorithms.

This class is not thread safe.

Field Summary

Fields

Modifier and Type	Field and Description
private Address	base The start address of the data table
private static Offset	DATA_OFFSET Offset to the data
private Extent	entrySize The size of each entry in the table
private static int	HASH_SHIFT The number of low order bits to ignore
private static Offset	KEY_OFFSET Offset to the key
private Word	mask The mask to use to get the hash code
private Extent	size The full size of the table
private RawPageSpace	space The space to use for allocating the data structure
private boolean	valid Is this table valid (created)

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	SimpleHashtable(RawPageSpace rps, int logSize, Extent es) Create a new data table of a specified size.

Method Summary

Modifier and Type	Method and Description
void	acquireTable() Create a (zeroed) table.
private int	computeHash(Word key) Compute the hashtable index for a given object.
boolean	contains(Word key) Does the passed object have an entry in the table?
private Address	getEntry(int index) Return the address of a specified entry in the table.
Address	getEntry(Word key, boolean create) Retrieve a pointer to the entry for the given object, or zero if one does not exist, unless create is passed.
Address	getFirst()
static Word	getKey(Address entry) Return the key for a given entry.
Address	getNext(Address curr) The next element in the table after the passed entry, or null if it is the last entry.
static Address	getPayloadAddress(Address entry) Given an address of an entry, return a pointer to the payload.
Address	getPayloadAddress(Word key) Given a key, return a pointer to the payload.
boolean	isValid()
void	releaseTable() Drop the table (after collection).
static void	replaceKey(Address entry, Word key) Update the key for a given entry.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

HASH_SHIFT

private static final int HASH_SHIFT

The number of low order bits to ignore

See Also:

Constant Field Values

KEY_OFFSET

private static final Offset KEY_OFFSET

Offset to the key

DATA_OFFSET

private static final Offset DATA_OFFSET

Offset to the data

entrySize

private final Extent entrySize

The size of each entry in the table

mask

private final Word mask

The mask to use to get the hash code

base

private Address base

The start address of the data table

size

private final Extent size

The full size of the table

space

private final RawPageSpace space

The space to use for allocating the data structure

valid

private boolean valid

Is this table valid (created)

Constructor Detail

SimpleHashtable

protected SimpleHashtable(RawPageSpace rps,
                          int logSize,
                          Extent es)

Create a new data table of a specified size.

Parameters:

rps - The space to acquire the data structure from.

logSize - The log of the number of table entries.

es - The size of each entry.

Method Detail

acquireTable

public final void acquireTable()

Create a (zeroed) table.

releaseTable

public final void releaseTable()

Drop the table (after collection).

isValid

public final boolean isValid()

Returns:

True if this table has backing data and is ready for use.

getEntry

public final Address getEntry(Word key,
                              boolean create)

Retrieve a pointer to the entry for the given object, or zero if one does not exist, unless create is passed.

If create is true, the return is guaranteed to be non-null.

Parameters:

key - The key used to lookup.

create - Create a new entry if not found.

Returns:

A pointer to the reference or null.

computeHash

private int computeHash(Word key)

Compute the hashtable index for a given object.

Parameters:

key - The key.

Returns:

The index.

getEntry

private Address getEntry(int index)

Return the address of a specified entry in the table.

Parameters:

index - The index of the entry.

Returns:

An address to the entry.

contains

public final boolean contains(Word key)

Does the passed object have an entry in the table?

Parameters:

key - The key to find an entry for

Returns:

True if there is an entry for that object.

getFirst

public final Address getFirst()

Returns:

The first non-zero element in the table, or null if the table is empty.

getNext

public final Address getNext(Address curr)

The next element in the table after the passed entry, or null if it is the last entry.

Parameters:

curr - The object to look for the next entry from.

Returns:

The next entry or null.

getPayloadAddress

public static Address getPayloadAddress(Address entry)

Given an address of an entry, return a pointer to the payload.

Parameters:

entry - The entry

Returns:

The object reference.

getPayloadAddress

public final Address getPayloadAddress(Word key)

Given a key, return a pointer to the payload.

Parameters:

key - The key

Returns:

The object reference.

getKey

public static Word getKey(Address entry)

Return the key for a given entry.

Parameters:

entry - The entry.

Returns:

The key.

replaceKey

public static void replaceKey(Address entry,
                              Word key)

Update the key for a given entry. This operation is not safe without rehashing

Parameters:

entry - The entry to update.

key - The new key.