Lightweight Bartering Grid

lbg.protocol.data
Class Cache<K extends java.lang.Comparable<? extends K>>

java.lang.Object
  extended by lbg.protocol.data.Cache<K>
Type Parameters:
K - The type of the keys for the entries
Direct Known Subclasses:
SlottedLRUCache, UnlimitedCache

public abstract class Cache<K extends java.lang.Comparable<? extends K>>
extends java.lang.Object

An abstract cache.

A Cache does not actually store entries. Rather, it stores identifiers for these entries along with Metadata that could be useful for implementing classes. In the following, we will consider that the identifiers are the actual entries (and they could be, depending on what you store).

Additionnally, a Cache can have a veto on a set of entries, which means that, no matter what, they will never me removed from the cache (and never be candidate for removal). The veto, however, does not guarantee that the entries are present in cache, just that if they were present when the veto was set, or were added after it was set, they are still there. Consequently, there is no bound on the veto size.

Author:
Xavier Dalem

Field Summary
protected  java.util.Map<K,Metadata<K>> entries
          All entries know by this cache, including veto'ed ones
protected  java.util.Set<K> veto
          A list of veto'ed entries
 
Constructor Summary
Cache()
           
 
Method Summary
abstract  Metadata<K> add(K entry, Metadata<K> meta)
          Adds an entry to the cache.
abstract  boolean canAdd(Metadata<K>[] entries, boolean mindVeto)
          Checks if the cache can hold all entries.
 float getCacheHit(K[] entries)
          Get the cache hit that inserting a set of entries would yield.
 Metadata<K> getMetadata(K entry)
           
 K[] getVeto(K[] a)
           
 boolean has(K entry)
           
 boolean hasVetoOn(K candidate)
          Is this entry veto'ed ?
 boolean isEmpty()
           
abstract  boolean isFull()
           
 Metadata<K> remove(K entry)
          Removes an entry from the cache.
abstract  K selectForRemoval()
          Selects an entry that could be removed, but doesn't remove it yet.
 void setVeto(K[] veto)
          Sets a set of entries as non-removable.
 int size()
          Returns the number of entries currently known by this cache.
 int vetoSize()
          Returns the number of elements in the veto.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

veto

protected java.util.Set<K extends java.lang.Comparable<? extends K>> veto
A list of veto'ed entries


entries

protected java.util.Map<K extends java.lang.Comparable<? extends K>,Metadata<K extends java.lang.Comparable<? extends K>>> entries
All entries know by this cache, including veto'ed ones

Constructor Detail

Cache

public Cache()
Method Detail

setVeto

public final void setVeto(K[] veto)
Sets a set of entries as non-removable. Veto'ed data do not have to be present in the cache. They could be added later. Furthermore, the veto could be larger than the cache. See the definition of the veto for more details.

Parameters:
veto - The new veto set (null to clear current veto)

getVeto

public final K[] getVeto(K[] a)

hasVetoOn

public final boolean hasVetoOn(K candidate)
Is this entry veto'ed ?

Parameters:
candidate - The entry to check
Returns:
true if the entry is veto'ed, false in all other cases, including when the entry isn't even in cache.

vetoSize

public final int vetoSize()
Returns the number of elements in the veto. This method should be significantly faster than checking the size of the array returned by getVeto(Comparable[])


add

public abstract Metadata<K> add(K entry,
                                Metadata<K> meta)
                                                                   throws VetoException
Adds an entry to the cache. Setting meta data for an existing entry doesn't replace the existing metadata. Either getMetadata(Comparable) and modify it or remove(Comparable) then add it back.

Parameters:
entry - The entry to add
meta - Metadata concerning this entry
Returns:
The metadata for the entry that was removed, if the cache implementation has a finite capacity and had to make room.
Throws:
VetoException - If the Veto prevents adding this entry in any way

canAdd

public abstract boolean canAdd(Metadata<K>[] entries,
                               boolean mindVeto)
Checks if the cache can hold all entries. The check is based on the current veto, as this method returns true if all entries not in the veto can be stored in the remaining space.

Parameters:
entries - The entries that would be added
mindVeto - true if the current veto should be taken into account. If false, it will be considered that the veto could be removed before actually inserting the data. In the latter case, adding without clearing the veto could fail even if the method returns true
Returns:
true if all entries can potentially be added.

remove

public Metadata<K> remove(K entry)
                                                             throws VetoException
Removes an entry from the cache.

Parameters:
entry - The entry to remove
Returns:
true if the entry was in the cache
Throws:
VetoException - if the entry is veto'ed

selectForRemoval

public abstract K selectForRemoval()
                                                                      throws VetoException
Selects an entry that could be removed, but doesn't remove it yet.

Returns:
The entry that could be removed, or null if none can be removed but this is normal (e.g. because the cache has no limit or is empty)
Throws:
VetoException - If the veto prevents removal of any entry

isFull

public abstract boolean isFull()

isEmpty

public final boolean isEmpty()

has

public final boolean has(K entry)

getMetadata

public final Metadata<K> getMetadata(K entry)

getCacheHit

public final float getCacheHit(K[] entries)
Get the cache hit that inserting a set of entries would yield.

The cache hit is defined by (number of candidate entries already in the cache) / (total number of candidate entries). It is thus comprised between 0 and 1 inclusive.

Parameters:
entries - The entries that would be inserted.
Returns:
The cache hit ratio

size

public final int size()
Returns the number of entries currently known by this cache.

This is not linked to any metric that could be used in a subclass to bound the cache.


Lightweight Bartering Grid

Copyright (c) 2005-2008, Cyril Briquet, parts Xavier Dalem.