net.captp.tables
Class CommTable

java.lang.Object
  |
  +--net.captp.tables.CommTable

Direct Known Subclasses:

AnswersTable, ExportsTable, ImportsTable, QuestionsTable

public abstract class CommTable

extends Object

Untamed: Just some common mechanism made available to the CommTable implementations.

CommTables are defined in terms of indices (always positive), not position. At a higher level, positions use positive or negative to encode choice of table (questions vs imports, answers vs exports). This can be a bit confusing because CommTable internally uses negated indices for free list entries, and these two uses of negation are completely independent. The rest of CapTP depends on the tables, but for the sake of unit testing, each table stands alone to the greatest reasonable degree. Since AnswersTable adds almost nothing to CommTable, you can unit test CommTable by testing AnswersTable.

Author:

Mark Miller

Field Summary

private static int	GROWTH_FACTOR
private static int	INIT_CAPACITY Default initial capacity
(package private) int	myCapacity What is the size of my parallel arrays?
private int	myFreeHead Let first = -myFreeHead; If first >= 1, it's the index of the first free entry in myFreeList.
private int[]	myFreeList Keeps track of the allocation of my indices.
private int	mySize How many allocated entries do I have?
(package private) Object[]	myStuff The actual contents of the table.
private static Object	ThePumpkin Used to indicate the absence of any other object

Constructor Summary

CommTable()
Enabled: Starts will all inidices free.

Method Summary

void	__printOn(TextWriter out) Enabled:
private void	alloc(int index) Allocate a particular index.
private int	bigEnough(int index) What the next capacity big enough to represent index?
int	bind(Object value) Enabled: Allocates a free index, put value there, and returns that index.
boolean	decr(int index, int delta) Enabled: Decrement index's allocation count delta, and free it if it reaches zero.
void	free(int index) Enabled: Deallocates an allocated index.
Object	get(int index) Enabled: Gets the object at the allocated index.
private static Object	grow(Object array, int capacity) Returns array or a copy of array sized to capacity.
private void	growToHold(int index) Become big enough to hold index.
void	incr(int index) Enabled: Increment index's allocation count.
(package private) boolean	isFree(int index) Is this index free? If it's past the end, yes.
void	mustBeAlloced(int index) Enabled: Complain if not allocated
void	mustBeFree(int index) Enabled: Complain if not free
void	put(int index, Object value) Enabled:
void	put(int index, Object value, boolean strict) Enabled:
int	size() Enabled: How many allocated entries?
void	smash(Throwable problem) Enabled: Drop all state and make sure nothing ever works again.

Methods inherited from class java.lang.Object

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

Field Detail

ThePumpkin

private static final Object ThePumpkin

Used to indicate the absence of any other object

INIT_CAPACITY

private static final int INIT_CAPACITY

Default initial capacity

GROWTH_FACTOR

private static final int GROWTH_FACTOR

mySize

private int mySize

How many allocated entries do I have?

myCapacity

int myCapacity

What is the size of my parallel arrays?

myFreeList

private int[] myFreeList

Keeps track of the allocation of my indices.

myFreeList[0] is unused and always has the value 0. For all i >= 1, if myFreeList[i] >= 1, it's an allocation count. Otherwise, let next := -myFreeList[i]. If next >= 1, it's the index of the next free entry in myFreeList. If next == 0, we're at the end of the list.

myFreeHead

private int myFreeHead

Let first = -myFreeHead; If first >= 1, it's the index of the first free entry in myFreeList. If first == 0, the list is empty.

myStuff

Object[] myStuff

The actual contents of the table.

Constructor Detail

CommTable

public CommTable()

Enabled: Starts will all inidices free.

Method Detail

smash

public void smash(Throwable problem)

Enabled: Drop all state and make sure nothing ever works again.

size

public int size()

Enabled: How many allocated entries?

isFree

boolean isFree(int index)

Is this index free? If it's past the end, yes. If it's before the beginning, it's not valid, so no.

mustBeFree

public void mustBeFree(int index)

Enabled: Complain if not free

mustBeAlloced

public void mustBeAlloced(int index)

Enabled: Complain if not allocated

bigEnough

private int bigEnough(int index)

What the next capacity big enough to represent index?

grow

private static Object grow(Object array,
                           int capacity)

Returns array or a copy of array sized to capacity.

growToHold

private void growToHold(int index)

Become big enough to hold index.

Newly added elements are on the (newly grown) free list.

free

public void free(int index)

Enabled: Deallocates an allocated index.

Subclasses may override and send-super in order to clear their parallel arrays.

incr

public void incr(int index)

Enabled: Increment index's allocation count.

index must already be allocated

decr

public boolean decr(int index,
                    int delta)

Enabled: Decrement index's allocation count delta, and free it if it reaches zero.

On entry, index must be allocated.

Returns:

whether the entry got freed

alloc

private void alloc(int index)

Allocate a particular index.

On entry, index must be free.

Since the free list is singly linked, we can't generally do this in constant time. However, by far the typical case is for the requested index to be the same as the one that zero-argument alloc would have allocated, so we need merely assure that this case is constant time.

get

public Object get(int index)

Enabled: Gets the object at the allocated index.

put

public void put(int index,
                Object value)

Enabled:

put

public void put(int index,
                Object value,
                boolean strict)

Enabled:

bind

public int bind(Object value)

Enabled: Allocates a free index, put value there, and returns that index.

Subclasses may override and send-super to initialize their parallel arrays.

__printOn

public void __printOn(TextWriter out)
               throws IOException

Enabled:

IOException