org.erights.e.elib.tables
Class KeyColumn

java.lang.Object
  |
  +--org.erights.e.elib.tables.Column
        |
        +--org.erights.e.elib.tables.KeyColumn

All Implemented Interfaces:

Cloneable

Direct Known Subclasses:

EqualityKeyColumn, IdentityKeyColumn, SamenessKeyColumn

abstract class KeyColumn

extends Column

Based on the GenericHashtable in the vat by Dan Bornstein

Author:

Mark S. Miller

Field Summary

(package private) static int	KEY_DELETED A value in myPos2Rank indicating that this position used to be occupied since the last rehash, but no longer is.
(package private) static int	KEY_UNUSED A value in myPos2Rank indicating that this position has never been occupied since the last rehash.
(package private) Object[]	myKeys The sparse array of keys by position.
(package private) int	myNumDeleted The number of keys currently marked deleted in the column.
(package private) int	myNumTaken The number of key currently in the column.
(package private) int[]	myPos2Rank A sparse array parallel to myKeys.
(package private) int[]	myRank2Pos A dense array, listing positions in their enumeration order.
static int	POSITIVE_MASK Used to ensure ints are positive
private static int[]	possibleSizes Little sorted array of primes for use to size key columns.

Constructor Summary

(package private)	KeyColumn(Class memberType, int capacity) Construct a new, empty KeyColumn, with the specified parameters.
(package private)	KeyColumn(Object[] keys, int[] pos2Rank, int[] rank2Pos, int numTaken, int numDeleted)

Method Summary

(package private) int	capacity()
protected Object	clone() Argument defaults to memberType()
protected abstract Column	diverge(Class membType) A shallow copy of the column.
(package private) abstract int	findPosOf(Object key) Returns the pos at which key resides, or -1 if the key is absent from the map.
private static int	firstSize(int candidate) Returns the first good size for a key column that's no less than candidate.
(package private) Object	get(int pos)
(package private) boolean	isPosTaken(int pos) Given a pos, say whether this pos contains a valid key.
(package private) static KeyColumn	make(Class memberType, int capacity) Makes a key column that's equivalent to a SamenessKeyColumn(memberType, capacity), but may select a more efficient implementation based on how instances of memberType compare for sameness.
(package private) Class	memberType() All the members of the column must conform to this type
(package private) abstract Column	newVacant(int capacity) Makes a new column just like this one, except of the specified size and without any members.
(package private) int	numTaken() Get the number of keys in the column
(package private) int	occupy(int pos, Object key)
(package private) void	put(int pos, Object value)
(package private) int[]	rank2Pos() Caller should only read, and only between 0..!numTaken()
(package private) static int	skip(int hash, int len)
(package private) abstract int	store(Object key) Put the given key into the map, and return its pos.
(package private) void	vacate(int pos) cause pos not to contain a valid key
static Column	values(Class memberType, int capacity) Make a value-column that can only hold values that conform to 'memberType' and has 'capacity' positions.
static Column	values(int capacity) memberType defaults to Object

Methods inherited from class java.lang.Object

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

Field Detail

POSITIVE_MASK

public static final int POSITIVE_MASK

Used to ensure ints are positive

myKeys

final Object[] myKeys

The sparse array of keys by position. null is a valid entry. The value of an entry is only valid if indicated by the corresponding myPos2Rank entry.

myPos2Rank

final int[] myPos2Rank

A sparse array parallel to myKeys. Each element contains either KEY_UNUSED, KEY_DELETED, or an index into myRank2Pos indicating where the association at this position fits into the ordering.

KEY_UNUSED

static final int KEY_UNUSED

A value in myPos2Rank indicating that this position has never been occupied since the last rehash. Note that KEY_UNUSED is negative, so it can't conflict with an array index.

KEY_DELETED

static final int KEY_DELETED

A value in myPos2Rank indicating that this position used to be occupied since the last rehash, but no longer is. Note that KEY_DELETED is negative, so it can't conflict with an array index.

myRank2Pos

final int[] myRank2Pos

A dense array, listing positions in their enumeration order. The allocated size of myRank2Pos is actually the same as the sparse arrays, but it's dense in 0..!myNumTaken, and unused after that.

myNumTaken

int myNumTaken

The number of key currently in the column.

myNumDeleted

int myNumDeleted

The number of keys currently marked deleted in the column.

possibleSizes

private static final int[] possibleSizes

Little sorted array of primes for use to size key columns. The elements grow exponentially at somewhat less than 2x.

Constructor Detail

KeyColumn

KeyColumn(Object[] keys,
          int[] pos2Rank,
          int[] rank2Pos,
          int numTaken,
          int numDeleted)

KeyColumn

KeyColumn(Class memberType,
          int capacity)

Construct a new, empty KeyColumn, with the specified parameters.

Parameters:

memberType - All keys will be (implicitly) checked for conformance to this type.

capacity - The column will hold at least this number of positions. To find out the actual number, call capacity() on the constructed column.

Method Detail

make

static KeyColumn make(Class memberType,
                      int capacity)

Makes a key column that's equivalent to a SamenessKeyColumn(memberType, capacity), but may select a more efficient implementation based on how instances of memberType compare for sameness.

findPosOf

abstract int findPosOf(Object key)

Returns the pos at which key resides, or -1 if the key is absent from the map.

firstSize

private static int firstSize(int candidate)

Returns the first good size for a key column that's no less than candidate. This will be a prime number so that we get better distribution of elements through the map.

get

Object get(int pos)

Specified by:

get in class Column

isPosTaken

boolean isPosTaken(int pos)

Given a pos, say whether this pos contains a valid key.

memberType

Class memberType()

Description copied from class: Column

All the members of the column must conform to this type

Specified by:

memberType in class Column

capacity

int capacity()

Specified by:

capacity in class Column

numTaken

int numTaken()

Get the number of keys in the column

rank2Pos

int[] rank2Pos()

Caller should only read, and only between 0..!numTaken()

put

void put(int pos,
         Object value)

Specified by:

put in class Column

skip

static int skip(int hash,
                int len)

store

abstract int store(Object key)

Put the given key into the map, and return its pos. If the key is equivalent (according to the concrete column's equality function) to a key already in the map, that pos is returned. If the key is novel but the map is too small to add it, a -1 is returned.

If the key already exists, no ordering information is affected. If a novel key is inserted, it's position gets the next rank.

Parameters:

key - the key to place in the map

Returns:

the pos at which the key now resides in the map, or -1 if we need more room.

occupy

int occupy(int pos,
           Object key)

vacate

void vacate(int pos)

cause pos not to contain a valid key

Specified by:

vacate in class Column

diverge

protected abstract Column diverge(Class membType)

A shallow copy of the column. The members are shared, not copied. The new Column is restricted to only holding members of type membType.

clone

protected Object clone()

Argument defaults to memberType()

Overrides:

clone in class Object

Returns:

a clone of this instance.

See Also:

java.lang.Cloneable

newVacant

abstract Column newVacant(int capacity)

Makes a new column just like this one, except of the specified size and without any members.

values

public static Column values(int capacity)

memberType defaults to Object

values

public static Column values(Class memberType,
                            int capacity)

Make a value-column that can only hold values that conform to 'memberType' and has 'capacity' positions. If the memberType is a scalar type, the column will represent these values unboxed.