hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/util/TestLightWeightCache.java - hadoop - Git at Google

 /**
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 package org.apache.hadoop.util;

 import java.util.Collection;
 import java.util.Date;
 import java.util.Iterator;
 import java.util.Random;

 import org.junit.Assert;
 import org.junit.Test;

 /** Testing {@link LightWeightCache} */
 public class TestLightWeightCache {
   private static final long starttime = Time.now();
   private static final long seed = starttime;
   private static final Random ran = new Random(seed);
   static {
     println("Start time = " + new Date(starttime) + ", seed=" +  seed);
   }

   private static void print(Object s) {
     System.out.print(s);
     System.out.flush();
   }

   private static void println(Object s) {
     System.out.println(s);
   }

   @Test
   public void testLightWeightCache() {
     // test randomized creation expiration with zero access expiration
     {
       final long creationExpiration = ran.nextInt(1024) + 1;
       check(1, creationExpiration, 0L, 1 << 10, 65537);
       check(17, creationExpiration, 0L, 1 << 16, 17);
       check(255, creationExpiration, 0L, 1 << 16, 65537);
     }

     // test randomized creation/access expiration periods
     for(int i = 0; i < 3; i++) {
       final long creationExpiration = ran.nextInt(1024) + 1;
       final long accessExpiration = ran.nextInt(1024) + 1;

       check(1, creationExpiration, accessExpiration, 1 << 10, 65537);
       check(17, creationExpiration, accessExpiration, 1 << 16, 17);
       check(255, creationExpiration, accessExpiration, 1 << 16, 65537);
     }

     // test size limit
     final int dataSize = 1 << 16;
     for(int i = 0; i < 10; i++) {
       final int modulus = ran.nextInt(1024) + 1;
       final int sizeLimit = ran.nextInt(modulus) + 1;
       checkSizeLimit(sizeLimit, dataSize, modulus);
     }
   }

   private static void checkSizeLimit(final int sizeLimit, final int datasize,
       final int modulus) {
     final LightWeightCacheTestCase test = new LightWeightCacheTestCase(
         sizeLimit, sizeLimit, 1L << 32, 1L << 32, datasize, modulus);

     // keep putting entries and check size limit
     print("  check size ................. ");
     for(int i = 0; i < test.data.size(); i++) {
       test.cache.put(test.data.get(i));
       Assert.assertTrue(test.cache.size() <= sizeLimit);
     }
     println("DONE " + test.stat());
   }

   /**
    * Test various createionExpirationPeriod and accessExpirationPeriod.
    * It runs ~2 minutes. If you are changing the implementation,
    * please un-comment the following line in order to run the test.
    */
 //  @Test
   public void testExpirationPeriods() {
     for(int k = -4; k < 10; k += 4) {
       final long accessExpirationPeriod = k < 0? 0L: (1L << k);
       for(int j = 0; j < 10; j += 4) {
         final long creationExpirationPeriod = 1L << j;
         runTests(1, creationExpirationPeriod, accessExpirationPeriod);
         for(int i = 1; i < Integer.SIZE - 1; i += 8) {
           runTests((1 << i) + 1, creationExpirationPeriod, accessExpirationPeriod);
         }
       }
     }
   }

   /** Run tests with various table lengths. */
   private static void runTests(final int modulus,
       final long creationExpirationPeriod,
       final long accessExpirationPeriod) {
     println("\n\n\n*** runTest: modulus=" + modulus
         + ", creationExpirationPeriod=" + creationExpirationPeriod
         + ", accessExpirationPeriod=" + accessExpirationPeriod);
     for(int i = 0; i <= 16; i += 4) {
       final int tablelength = (1 << i);

       final int upper = i + 2;
       final int steps = Math.max(1, upper/3);

       for(int j = upper; j > 0; j -= steps) {
         final int datasize = 1 << j;
         check(tablelength, creationExpirationPeriod, accessExpirationPeriod,
             datasize, modulus);
       }
     }
   }

   private static void check(int tablelength, long creationExpirationPeriod,
       long accessExpirationPeriod, int datasize, int modulus) {
     check(new LightWeightCacheTestCase(tablelength, -1,
         creationExpirationPeriod, accessExpirationPeriod, datasize, modulus));
   }

   /**
    * check the following operations
    * (1) put
    * (2) remove & put
    * (3) remove
    * (4) remove & put again
    */
   private static void check(final LightWeightCacheTestCase test) {
     //check put
     print("  check put .................. ");
     for(int i = 0; i < test.data.size()/2; i++) {
       test.put(test.data.get(i));
     }
     for(int i = 0; i < test.data.size(); i++) {
       test.put(test.data.get(i));
     }
     println("DONE " + test.stat());

     //check remove and put
     print("  check remove & put ......... ");
     for(int j = 0; j < 10; j++) {
       for(int i = 0; i < test.data.size()/2; i++) {
         final int r = ran.nextInt(test.data.size());
         test.remove(test.data.get(r));
       }
       for(int i = 0; i < test.data.size()/2; i++) {
         final int r = ran.nextInt(test.data.size());
         test.put(test.data.get(r));
       }
     }
     println("DONE " + test.stat());

     //check remove
     print("  check remove ............... ");
     for(int i = 0; i < test.data.size(); i++) {
       test.remove(test.data.get(i));
     }
     Assert.assertEquals(0, test.cache.size());
     println("DONE " + test.stat());

     //check remove and put again
     print("  check remove & put again ... ");
     for(int j = 0; j < 10; j++) {
       for(int i = 0; i < test.data.size()/2; i++) {
         final int r = ran.nextInt(test.data.size());
         test.remove(test.data.get(r));
       }
       for(int i = 0; i < test.data.size()/2; i++) {
         final int r = ran.nextInt(test.data.size());
         test.put(test.data.get(r));
       }
     }
     println("DONE " + test.stat());

     final long s = (Time.now() - starttime)/1000L;
     println("total time elapsed=" + s + "s\n");
   }

   /**
    * The test case contains two data structures, a cache and a hashMap.
    * The hashMap is used to verify the correctness of the cache.  Note that
    * no automatic eviction is performed in the hashMap.  Thus, we have
    * (1) If an entry exists in cache, it MUST exist in the hashMap.
    * (2) If an entry does not exist in the cache, it may or may not exist in the
    *     hashMap.  If it exists, it must be expired.
    */
   private static class LightWeightCacheTestCase implements GSet<IntEntry, IntEntry> {
     /** hashMap will not evict entries automatically. */
     final GSet<IntEntry, IntEntry> hashMap
         = new GSetByHashMap<IntEntry, IntEntry>(1024, 0.75f);

     final LightWeightCache<IntEntry, IntEntry> cache;
     final IntData data;

     final String info;
     final long starttime = Time.now();
     /** Determine the probability in {@link #check()}. */
     final int denominator;
     int iterate_count = 0;
     int contain_count = 0;

     private FakeTimer fakeTimer = new FakeTimer();

     LightWeightCacheTestCase(int tablelength, int sizeLimit,
         long creationExpirationPeriod, long accessExpirationPeriod,
         int datasize, int modulus) {
       denominator = Math.min((datasize >> 7) + 1, 1 << 16);
       info = getClass().getSimpleName() + "(" + new Date(starttime)
           + "): tablelength=" + tablelength
           + ", creationExpirationPeriod=" + creationExpirationPeriod
           + ", accessExpirationPeriod=" + accessExpirationPeriod
           + ", datasize=" + datasize
           + ", modulus=" + modulus
           + ", denominator=" + denominator;
       println(info);

       data = new IntData(datasize, modulus);
       cache = new LightWeightCache<IntEntry, IntEntry>(tablelength, sizeLimit,
           creationExpirationPeriod, 0, fakeTimer);

       Assert.assertEquals(0, cache.size());
     }

     private boolean containsTest(IntEntry key) {
       final boolean c = cache.contains(key);
       if (c) {
         Assert.assertTrue(hashMap.contains(key));
       } else {
         final IntEntry h = hashMap.remove(key);
         if (h != null) {
           Assert.assertTrue(cache.isExpired(h, fakeTimer.monotonicNowNanos()));
         }
       }
       return c;
     }
     @Override
     public boolean contains(IntEntry key) {
       final boolean e = containsTest(key);
       check();
       return e;
     }

     private IntEntry getTest(IntEntry key) {
       final IntEntry c = cache.get(key);
       if (c != null) {
         Assert.assertEquals(hashMap.get(key).id, c.id);
       } else {
         final IntEntry h = hashMap.remove(key);
         if (h != null) {
           Assert.assertTrue(cache.isExpired(h, fakeTimer.monotonicNowNanos()));
         }
       }
       return c;
     }
     @Override
     public IntEntry get(IntEntry key) {
       final IntEntry e = getTest(key);
       check();
       return e;
     }

     private IntEntry putTest(IntEntry entry) {
       final IntEntry c = cache.put(entry);
       if (c != null) {
         Assert.assertEquals(hashMap.put(entry).id, c.id);
       } else {
         final IntEntry h = hashMap.put(entry);
         if (h != null && h != entry) {
           // if h == entry, its expiration time is already updated
           Assert.assertTrue(cache.isExpired(h, fakeTimer.monotonicNowNanos()));
         }
       }
       return c;
     }
     @Override
     public IntEntry put(IntEntry entry) {
       final IntEntry e = putTest(entry);
       check();
       return e;
     }

     private IntEntry removeTest(IntEntry key) {
       final IntEntry c = cache.remove(key);
       if (c != null) {
         Assert.assertEquals(c.id, hashMap.remove(key).id);
       } else {
         final IntEntry h = hashMap.remove(key);
         if (h != null) {
           Assert.assertTrue(cache.isExpired(h, fakeTimer.monotonicNowNanos()));
         }
       }
       return c;
     }
     @Override
     public IntEntry remove(IntEntry key) {
       final IntEntry e = removeTest(key);
       check();
       return e;
     }

     private int sizeTest() {
       final int c = cache.size();
       Assert.assertTrue(hashMap.size() >= c);
       return c;
     }
     @Override
     public int size() {
       final int s = sizeTest();
       check();
       return s;
     }

     @Override
     public Iterator<IntEntry> iterator() {
       throw new UnsupportedOperationException();
     }

     boolean tossCoin() {
       return ran.nextInt(denominator) == 0;
     }

     void check() {
       fakeTimer.advanceNanos(ran.nextInt() & 0x3);

       //test size
       sizeTest();

       if (tossCoin()) {
         //test get(..), check content and test iterator
         iterate_count++;
         for(IntEntry i : cache) {
           getTest(i);
         }
       }

       if (tossCoin()) {
         //test contains(..)
         contain_count++;
         final int count = Math.min(data.size(), 1000);
         if (count == data.size()) {
           for(IntEntry i : data.integers) {
             containsTest(i);
           }
         } else {
           for(int j = 0; j < count; j++) {
             containsTest(data.get(ran.nextInt(data.size())));
           }
         }
       }
     }

     String stat() {
       final long t = Time.now() - starttime;
       return String.format(" iterate=%5d, contain=%5d, time elapsed=%5d.%03ds",
           iterate_count, contain_count, t/1000, t%1000);
     }

     @Override
     public void clear() {
       hashMap.clear();
       cache.clear();
       Assert.assertEquals(0, size());
     }

     @Override
     public Collection<IntEntry> values() {
       throw new UnsupportedOperationException();
     }
   }

   private static class IntData {
     final IntEntry[] integers;

     IntData(int size, int modulus) {
       integers = new IntEntry[size];
       for(int i = 0; i < integers.length; i++) {
         integers[i] = new IntEntry(i, ran.nextInt(modulus));
       }
     }

     IntEntry get(int i) {
       return integers[i];
     }

     int size() {
       return integers.length;
     }
   }

   /** Entries of {@link LightWeightCache} in this test */
   private static class IntEntry implements LightWeightCache.Entry,
       Comparable<IntEntry> {
     private LightWeightGSet.LinkedElement next;
     final int id;
     final int value;
     private long expirationTime = 0;

     IntEntry(int id, int value) {
       this.id = id;
       this.value = value;
     }

     @Override
     public boolean equals(Object obj) {
       return obj != null && obj instanceof IntEntry
           && value == ((IntEntry)obj).value;
     }

     @Override
     public int hashCode() {
       return value;
     }

     @Override
     public int compareTo(IntEntry that) {
       return value - that.value;
     }

     @Override
     public String toString() {
       return id + "#" + value + ",expirationTime=" + expirationTime;
     }

     @Override
     public LightWeightGSet.LinkedElement getNext() {
       return next;
     }

     @Override
     public void setNext(LightWeightGSet.LinkedElement e) {
       next = e;
     }

     @Override
     public void setExpirationTime(long timeNano) {
       this.expirationTime = timeNano;
     }

     @Override
     public long getExpirationTime() {
       return expirationTime;
     }
   }
 }
	/**
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the
	* "License"); you may not use this file except in compliance
	* with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	package org.apache.hadoop.util;

	import java.util.Collection;
	import java.util.Date;
	import java.util.Iterator;
	import java.util.Random;

	import org.junit.Assert;
	import org.junit.Test;

	/** Testing {@link LightWeightCache} */
	public class TestLightWeightCache {
	private static final long starttime = Time.now();
	private static final long seed = starttime;
	private static final Random ran = new Random(seed);
	static {
	println("Start time = " + new Date(starttime) + ", seed=" + seed);
	}

	private static void print(Object s) {
	System.out.print(s);
	System.out.flush();
	}

	private static void println(Object s) {
	System.out.println(s);
	}

	@Test
	public void testLightWeightCache() {
	// test randomized creation expiration with zero access expiration
	{
	final long creationExpiration = ran.nextInt(1024) + 1;
	check(1, creationExpiration, 0L, 1 << 10, 65537);
	check(17, creationExpiration, 0L, 1 << 16, 17);
	check(255, creationExpiration, 0L, 1 << 16, 65537);
	}

	// test randomized creation/access expiration periods
	for(int i = 0; i < 3; i++) {
	final long creationExpiration = ran.nextInt(1024) + 1;
	final long accessExpiration = ran.nextInt(1024) + 1;

	check(1, creationExpiration, accessExpiration, 1 << 10, 65537);
	check(17, creationExpiration, accessExpiration, 1 << 16, 17);
	check(255, creationExpiration, accessExpiration, 1 << 16, 65537);
	}

	// test size limit
	final int dataSize = 1 << 16;
	for(int i = 0; i < 10; i++) {
	final int modulus = ran.nextInt(1024) + 1;
	final int sizeLimit = ran.nextInt(modulus) + 1;
	checkSizeLimit(sizeLimit, dataSize, modulus);
	}
	}

	private static void checkSizeLimit(final int sizeLimit, final int datasize,
	final int modulus) {
	final LightWeightCacheTestCase test = new LightWeightCacheTestCase(
	sizeLimit, sizeLimit, 1L << 32, 1L << 32, datasize, modulus);

	// keep putting entries and check size limit
	print(" check size ................. ");
	for(int i = 0; i < test.data.size(); i++) {
	test.cache.put(test.data.get(i));
	Assert.assertTrue(test.cache.size() <= sizeLimit);
	}
	println("DONE " + test.stat());
	}

	/**
	* Test various createionExpirationPeriod and accessExpirationPeriod.
	* It runs ~2 minutes. If you are changing the implementation,
	* please un-comment the following line in order to run the test.
	*/
	// @Test
	public void testExpirationPeriods() {
	for(int k = -4; k < 10; k += 4) {
	final long accessExpirationPeriod = k < 0? 0L: (1L << k);
	for(int j = 0; j < 10; j += 4) {
	final long creationExpirationPeriod = 1L << j;
	runTests(1, creationExpirationPeriod, accessExpirationPeriod);
	for(int i = 1; i < Integer.SIZE - 1; i += 8) {
	runTests((1 << i) + 1, creationExpirationPeriod, accessExpirationPeriod);
	}
	}
	}
	}

	/** Run tests with various table lengths. */
	private static void runTests(final int modulus,
	final long creationExpirationPeriod,
	final long accessExpirationPeriod) {
	println("\n\n\n*** runTest: modulus=" + modulus
	+ ", creationExpirationPeriod=" + creationExpirationPeriod
	+ ", accessExpirationPeriod=" + accessExpirationPeriod);
	for(int i = 0; i <= 16; i += 4) {
	final int tablelength = (1 << i);

	final int upper = i + 2;
	final int steps = Math.max(1, upper/3);

	for(int j = upper; j > 0; j -= steps) {
	final int datasize = 1 << j;
	check(tablelength, creationExpirationPeriod, accessExpirationPeriod,
	datasize, modulus);
	}
	}
	}

	private static void check(int tablelength, long creationExpirationPeriod,
	long accessExpirationPeriod, int datasize, int modulus) {
	check(new LightWeightCacheTestCase(tablelength, -1,
	creationExpirationPeriod, accessExpirationPeriod, datasize, modulus));
	}

	/**
	* check the following operations
	* (1) put
	* (2) remove & put
	* (3) remove
	* (4) remove & put again
	*/
	private static void check(final LightWeightCacheTestCase test) {
	//check put
	print(" check put .................. ");
	for(int i = 0; i < test.data.size()/2; i++) {
	test.put(test.data.get(i));
	}
	for(int i = 0; i < test.data.size(); i++) {
	test.put(test.data.get(i));
	}
	println("DONE " + test.stat());

	//check remove and put
	print(" check remove & put ......... ");
	for(int j = 0; j < 10; j++) {
	for(int i = 0; i < test.data.size()/2; i++) {
	final int r = ran.nextInt(test.data.size());
	test.remove(test.data.get(r));
	}
	for(int i = 0; i < test.data.size()/2; i++) {
	final int r = ran.nextInt(test.data.size());
	test.put(test.data.get(r));
	}
	}
	println("DONE " + test.stat());

	//check remove
	print(" check remove ............... ");
	for(int i = 0; i < test.data.size(); i++) {
	test.remove(test.data.get(i));
	}
	Assert.assertEquals(0, test.cache.size());
	println("DONE " + test.stat());

	//check remove and put again
	print(" check remove & put again ... ");
	for(int j = 0; j < 10; j++) {
	for(int i = 0; i < test.data.size()/2; i++) {
	final int r = ran.nextInt(test.data.size());
	test.remove(test.data.get(r));
	}
	for(int i = 0; i < test.data.size()/2; i++) {
	final int r = ran.nextInt(test.data.size());
	test.put(test.data.get(r));
	}
	}
	println("DONE " + test.stat());

	final long s = (Time.now() - starttime)/1000L;
	println("total time elapsed=" + s + "s\n");
	}

	/**
	* The test case contains two data structures, a cache and a hashMap.
	* The hashMap is used to verify the correctness of the cache. Note that
	* no automatic eviction is performed in the hashMap. Thus, we have
	* (1) If an entry exists in cache, it MUST exist in the hashMap.
	* (2) If an entry does not exist in the cache, it may or may not exist in the
	* hashMap. If it exists, it must be expired.
	*/
	private static class LightWeightCacheTestCase implements GSet<IntEntry, IntEntry> {
	/** hashMap will not evict entries automatically. */
	final GSet<IntEntry, IntEntry> hashMap
	= new GSetByHashMap<IntEntry, IntEntry>(1024, 0.75f);

	final LightWeightCache<IntEntry, IntEntry> cache;
	final IntData data;

	final String info;
	final long starttime = Time.now();
	/** Determine the probability in {@link #check()}. */
	final int denominator;
	int iterate_count = 0;
	int contain_count = 0;

	private FakeTimer fakeTimer = new FakeTimer();

	LightWeightCacheTestCase(int tablelength, int sizeLimit,
	long creationExpirationPeriod, long accessExpirationPeriod,
	int datasize, int modulus) {
	denominator = Math.min((datasize >> 7) + 1, 1 << 16);
	info = getClass().getSimpleName() + "(" + new Date(starttime)
	+ "): tablelength=" + tablelength
	+ ", creationExpirationPeriod=" + creationExpirationPeriod
	+ ", accessExpirationPeriod=" + accessExpirationPeriod
	+ ", datasize=" + datasize
	+ ", modulus=" + modulus
	+ ", denominator=" + denominator;
	println(info);

	data = new IntData(datasize, modulus);
	cache = new LightWeightCache<IntEntry, IntEntry>(tablelength, sizeLimit,
	creationExpirationPeriod, 0, fakeTimer);

	Assert.assertEquals(0, cache.size());
	}

	private boolean containsTest(IntEntry key) {
	final boolean c = cache.contains(key);
	if (c) {
	Assert.assertTrue(hashMap.contains(key));
	} else {
	final IntEntry h = hashMap.remove(key);
	if (h != null) {
	Assert.assertTrue(cache.isExpired(h, fakeTimer.monotonicNowNanos()));
	}
	}
	return c;
	}
	@Override
	public boolean contains(IntEntry key) {
	final boolean e = containsTest(key);
	check();
	return e;
	}

	private IntEntry getTest(IntEntry key) {
	final IntEntry c = cache.get(key);
	if (c != null) {
	Assert.assertEquals(hashMap.get(key).id, c.id);
	} else {
	final IntEntry h = hashMap.remove(key);
	if (h != null) {
	Assert.assertTrue(cache.isExpired(h, fakeTimer.monotonicNowNanos()));
	}
	}
	return c;
	}
	@Override
	public IntEntry get(IntEntry key) {
	final IntEntry e = getTest(key);
	check();
	return e;
	}

	private IntEntry putTest(IntEntry entry) {
	final IntEntry c = cache.put(entry);
	if (c != null) {
	Assert.assertEquals(hashMap.put(entry).id, c.id);
	} else {
	final IntEntry h = hashMap.put(entry);
	if (h != null && h != entry) {
	// if h == entry, its expiration time is already updated
	Assert.assertTrue(cache.isExpired(h, fakeTimer.monotonicNowNanos()));
	}
	}
	return c;
	}
	@Override
	public IntEntry put(IntEntry entry) {
	final IntEntry e = putTest(entry);
	check();
	return e;
	}

	private IntEntry removeTest(IntEntry key) {
	final IntEntry c = cache.remove(key);
	if (c != null) {
	Assert.assertEquals(c.id, hashMap.remove(key).id);
	} else {
	final IntEntry h = hashMap.remove(key);
	if (h != null) {
	Assert.assertTrue(cache.isExpired(h, fakeTimer.monotonicNowNanos()));
	}
	}
	return c;
	}
	@Override
	public IntEntry remove(IntEntry key) {
	final IntEntry e = removeTest(key);
	check();
	return e;
	}

	private int sizeTest() {
	final int c = cache.size();
	Assert.assertTrue(hashMap.size() >= c);
	return c;
	}
	@Override
	public int size() {
	final int s = sizeTest();
	check();
	return s;
	}

	@Override
	public Iterator<IntEntry> iterator() {
	throw new UnsupportedOperationException();
	}

	boolean tossCoin() {
	return ran.nextInt(denominator) == 0;
	}

	void check() {
	fakeTimer.advanceNanos(ran.nextInt() & 0x3);

	//test size
	sizeTest();

	if (tossCoin()) {
	//test get(..), check content and test iterator
	iterate_count++;
	for(IntEntry i : cache) {
	getTest(i);
	}
	}

	if (tossCoin()) {
	//test contains(..)
	contain_count++;
	final int count = Math.min(data.size(), 1000);
	if (count == data.size()) {
	for(IntEntry i : data.integers) {
	containsTest(i);
	}
	} else {
	for(int j = 0; j < count; j++) {
	containsTest(data.get(ran.nextInt(data.size())));
	}
	}
	}
	}

	String stat() {
	final long t = Time.now() - starttime;
	return String.format(" iterate=%5d, contain=%5d, time elapsed=%5d.%03ds",
	iterate_count, contain_count, t/1000, t%1000);
	}

	@Override
	public void clear() {
	hashMap.clear();
	cache.clear();
	Assert.assertEquals(0, size());
	}

	@Override
	public Collection<IntEntry> values() {
	throw new UnsupportedOperationException();
	}
	}

	private static class IntData {
	final IntEntry[] integers;

	IntData(int size, int modulus) {
	integers = new IntEntry[size];
	for(int i = 0; i < integers.length; i++) {
	integers[i] = new IntEntry(i, ran.nextInt(modulus));
	}
	}

	IntEntry get(int i) {
	return integers[i];
	}

	int size() {
	return integers.length;
	}
	}

	/** Entries of {@link LightWeightCache} in this test */
	private static class IntEntry implements LightWeightCache.Entry,
	Comparable<IntEntry> {
	private LightWeightGSet.LinkedElement next;
	final int id;
	final int value;
	private long expirationTime = 0;

	IntEntry(int id, int value) {
	this.id = id;
	this.value = value;
	}

	@Override
	public boolean equals(Object obj) {
	return obj != null && obj instanceof IntEntry
	&& value == ((IntEntry)obj).value;
	}

	@Override
	public int hashCode() {
	return value;
	}

	@Override
	public int compareTo(IntEntry that) {
	return value - that.value;
	}

	@Override
	public String toString() {
	return id + "#" + value + ",expirationTime=" + expirationTime;
	}

	@Override
	public LightWeightGSet.LinkedElement getNext() {
	return next;
	}

	@Override
	public void setNext(LightWeightGSet.LinkedElement e) {
	next = e;
	}

	@Override
	public void setExpirationTime(long timeNano) {
	this.expirationTime = timeNano;
	}

	@Override
	public long getExpirationTime() {
	return expirationTime;
	}
	}
	}