org.supermind.crawl
Class ChainedScatterTable

java.lang.Object
  extended by org.supermind.crawl.util.ChainedScatterTable

public class ChainedScatterTable
extends java.lang.Object

A fixed-size chained scatter table that implements the clock/second-chance algorithm for purging entries.

Implemented for storing longs. The 16 most significant bits are used as the hashkey, whilst the 48 least significant bits are used as the value.


Nested Class Summary
static class ChainedScatterTable.Entry
           
 
Field Summary
protected  ChainedScatterTable.Entry[] array
           
protected  int clockIndex
           
protected  int count
           
protected static java.util.logging.Logger LOG
          Logger.
protected  ScatterPurger purger
           
 
Constructor Summary
ChainedScatterTable(ScatterPurger purger)
           
 
Method Summary
 void clear()
           
 boolean contains(long chksm)
           
 int find(long obj)
           
protected  int getAddressToEvict()
          This method has side-effect of incrementing clockIndex.
protected  int hash(long obj)
          Use 32 most sig.
 int insert(long value)
           
 long reconstitute(int idx, long value)
          Reconstitute the full long given an index.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

array

protected ChainedScatterTable.Entry[] array

clockIndex

protected int clockIndex

count

protected int count

LOG

protected static java.util.logging.Logger LOG
Logger.


purger

protected ScatterPurger purger
Constructor Detail

ChainedScatterTable

public ChainedScatterTable(ScatterPurger purger)
Method Detail

clear

public void clear()

contains

public boolean contains(long chksm)

find

public int find(long obj)

getAddressToEvict

protected int getAddressToEvict()
This method has side-effect of incrementing clockIndex.

Returns:

hash

protected int hash(long obj)
Use 32 most sig. bits as hash. Lampson's abbreviated keys technique.

Parameters:
obj -
Returns:

insert

public int insert(long value)

reconstitute

public long reconstitute(int idx,
                         long value)
Reconstitute the full long given an index.

Parameters:
idx -
Returns: