I have finished my work with the eviction code in Infinispan, here is a summary of what has happened.

From a user perspective (including API and configuration) as well as a design overview, please have a look at 

From an implementation perspective, have a look at the srcs of FIFODataContainer and LRUDataContainer.  These two classes are where everything happens.  The javadocs should explain the details, but in a nutshell you can expect constant time operations for all puts, gets, removes, iterations.  :-)  

Feedback on the impls would be handy.  :-)

Cheers

--