ariba.util.core
Class LRUHashtable

java.lang.Object
  ariba.util.core.LRUHashtable

Direct Known Subclasses:

EqLRUHashtable, LinearLRUHashtable

public class LRUHashtable
extends java.lang.Object

A hashtable that tracks the age of entries. Adding and entry makes the entry the newest. Putting an entry in again will make the entry newest again.

Tables always grow in size by doubling. The index computation depends on the table size being a power of two. This is a tiny performance hack, and could easily be removed.

The table grows up to a given target size of elements, after which it start purging items from the table.

We don't want to purge the table on every insert, so when we purge, we purge a bunch. If we fail to purge as much as we want to -- probably a very bad sign for our client -- we increase the purgeTrigger.

We always try to purge to the targetSize. After a purge, we set the purgeTrigger to be "purgeMargin" more than the current size.

We only attempt to purge at the point at which we would have to grow the table. This might be well after we have reached the purgeTrigger number of entries.

The point of the purge margin is to make sure we bundle together purges. If you pick an bad targetEntries and purgeMargin, then the purges can run more frequently than you might expect. To avoid this, targetEntries+purgeMargin should be just less than maxLoad*maxSize, where maxSize is allocation size (in number of entries) that you expect to run with. Then the point at which the table fills up will be just beyond the purgeTrigger, so you'll always purge before trying to grow beyond your target size. As long as the purges reduce the table entries to the target, purges will only be triggered after having done at least purgeTrigger adds to the table. If a purge does not yield enough, then the trigger will be pushed up over the permitted number of entries for the table size, and the table will grow the next time it fills up.

For example: new LRUHashtable(name, 16, 140, 50, .75, removeListener) Allocates a table of 16 entries (which can hold 16*.75=12 entries before growing). The table will grow to size 256 (which can hold 192 entries). When the table fills up, and is about to grow, a purge will be triggered -- because the trigger is 140+50=190.

name is used to label debugging output.

Supplying a removeListener gives the creator of the LRUHashtable veto power on the removal of objects from the table. When the LRUHashtable scans to purge old entries, it calls removeListener.okToRemove(object) on each object that is old enough to be removed. If okToRemove returns false, the object is not removed. It is possible for a table to grow beyond its specified limits because nothing can be removed.

A removeListener of null is the same as a removeListener with an okToRemove() method that always returns true.

Synchronization: This class is NOT thread safe. The caller is repsonsible to ensure thread-safe access if needed.

Field Summary

int	inUse Number of entries currently occupied
java.lang.Object	lock

Constructor Summary

LRUHashtable(java.lang.String name, int initialEntries, int targetEntries, int purgeMargin, double maxLoad, LRURemoveListener removeListener)
Initial entries should be a power of 2.

Method Summary

void	addKeysTo(java.util.List v)
void	addValuesTo(java.util.List v)
java.lang.Object[]	allKeys()
java.lang.Object[]	allValues()
void	clear() Clears the entire hashtable.
void	dump(Logger log) Print every slot in the table, even slots not currently occupied, to the log.
void	dumpInOrder(Logger log, int limit) Print the first LIMIT entries in the table from newest to oldest.
void	dumpLRUStats(Logger log) Write LRU statistics.
void	dumpSummary(Logger log) Write a summary of the table's key attributes.
LRUEntry[]	entries()
java.lang.Object	get(java.lang.Object key) Return the value associated with 'key', or null if not found.
int	getHits()
int	getLookups()
java.lang.Object	getOldestKey() Return the oldest object in the LRU
int	getTotalInUseEntries()
java.lang.Object	peek(java.lang.Object key) Like get, but does not promote the found item.
java.util.List	purgeOldestEntries(int totalOldestEntries)
boolean	put(java.lang.Object key, java.lang.Object value)
java.lang.Object	remove(java.lang.Object key)
java.lang.Object	removeOldest()
void	sane(Logger log) Perform a simple-minded check that the LRU state is consistent.

Methods inherited from class java.lang.Object

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

Field Detail

lock

public final java.lang.Object lock

inUse

public int inUse

Number of entries currently occupied

Constructor Detail

LRUHashtable

public LRUHashtable(java.lang.String name,
                    int initialEntries,
                    int targetEntries,
                    int purgeMargin,
                    double maxLoad,
                    LRURemoveListener removeListener)

Initial entries should be a power of 2.

Method Detail

getLookups

public int getLookups()

getHits

public int getHits()

put

public final boolean put(java.lang.Object key,
                         java.lang.Object value)

get

public final java.lang.Object get(java.lang.Object key)

Return the value associated with 'key', or null if not found. Make the entry found newest.

peek

public final java.lang.Object peek(java.lang.Object key)

Like get, but does not promote the found item. For printing to the log, for example.

getOldestKey

public final java.lang.Object getOldestKey()

Return the oldest object in the LRU

removeOldest

public final java.lang.Object removeOldest()

remove

public final java.lang.Object remove(java.lang.Object key)

clear

public final void clear()

Clears the entire hashtable. SHOULD BE USED WITH EXTREME CARE.

getTotalInUseEntries

public int getTotalInUseEntries()

purgeOldestEntries

public java.util.List purgeOldestEntries(int totalOldestEntries)

allKeys

public final java.lang.Object[] allKeys()

allValues

public final java.lang.Object[] allValues()

entries

public final LRUEntry[] entries()

addKeysTo

public final void addKeysTo(java.util.List v)

addValuesTo

public final void addValuesTo(java.util.List v)

dumpSummary

public final void dumpSummary(Logger log)

Write a summary of the table's key attributes.

dumpLRUStats

public final void dumpLRUStats(Logger log)

Write LRU statistics.

dump

public final void dump(Logger log)

Print every slot in the table, even slots not currently occupied, to the log.

dumpInOrder

public final void dumpInOrder(Logger log,
                              int limit)

Print the first LIMIT entries in the table from newest to oldest.

sane

public final void sane(Logger log)

Perform a simple-minded check that the LRU state is consistent. Start at newest and scan toward oldest. For a table with N entries in use, after scanning N entries, we should be looking at the oldest entry. If not, something is wrong.