Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD

org.mmtk.utility
Class SimpleHashtable

java.lang.Object
  extended by org.mmtk.utility.SimpleHashtable
All Implemented Interfaces:
Constants
Direct Known Subclasses:
SanityDataTable
public abstract class SimpleHashtable
extends Object
implements Constants

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
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)
 
Fields inherited from interface org.mmtk.utility.Constants
ALIGNMENT_VALUE, ARRAY_ELEMENT, BITS_IN_ADDRESS, BITS_IN_BYTE, BITS_IN_CHAR, BITS_IN_INT, BITS_IN_PAGE, BITS_IN_SHORT, BITS_IN_WORD, BYTES_IN_ADDRESS, BYTES_IN_BYTE, BYTES_IN_CHAR, BYTES_IN_INT, BYTES_IN_KBYTE, BYTES_IN_MBYTE, BYTES_IN_PAGE, BYTES_IN_SHORT, BYTES_IN_WORD, CARD_MASK, CARD_META_PAGES_PER_REGION, INSTANCE_FIELD, LOG_BITS_IN_ADDRESS, LOG_BITS_IN_BYTE, LOG_BITS_IN_CHAR, LOG_BITS_IN_INT, LOG_BITS_IN_PAGE, LOG_BITS_IN_SHORT, LOG_BITS_IN_WORD, LOG_BYTES_IN_ADDRESS, LOG_BYTES_IN_ADDRESS_SPACE, LOG_BYTES_IN_BYTE, LOG_BYTES_IN_CHAR, LOG_BYTES_IN_INT, LOG_BYTES_IN_KBYTE, LOG_BYTES_IN_MBYTE, LOG_BYTES_IN_PAGE, LOG_BYTES_IN_SHORT, LOG_BYTES_IN_WORD, LOG_CARD_BYTES, LOG_CARD_GRAIN, LOG_CARD_META_BYTES, LOG_CARD_META_PAGES, LOG_CARD_META_SIZE, LOG_CARD_UNITS, LOG_MIN_ALIGNMENT, MAX_ALIGNMENT, MAX_BYTES_PADDING, MAX_INT, MIN_ALIGNMENT, MIN_INT, SUPPORT_CARD_SCANNING
 
Constructor Summary
protected SimpleHashtable(RawPageSpace rps, int logSize, Extent es)
          Create a new data table of a specified size.
 
Method Summary
 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.
Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD