File	Doc	Category	Size	Date	Package
Cache.java	API Doc	Android 1.5 API	13629	Wed May 06 22:41:06 BST 2009	org.apache.harmony.security.provider.cert

Cache

• java.lang.Object

Fields Summary
private static final long	HASH_MASK
private static final long	PREFIX_HASH_MASK
private static final int	INDEX_MASK
private final int	cache_size
private final int	prefix_size
private final long[]	hashes
private final byte[]	encodings
private final Object[]	cache
private final long[]	hashes_idx
private int	last_cached
private boolean	cache_is_full

Constructors Summary
public Cache(int pref_size, int size) Creates the Cache object. param pref_size specifies how many leading/trailing bytes of object's encoded form will be used for hash computation param size capacity of the cache to be created. cache_size = size; prefix_size = pref_size; hashes = new long[cache_size]; hashes_idx = new long[cache_size]; encodings = new byte[cache_size][]; cache = new Object[cache_size];
public Cache(int pref_size) Creates the Cache object of size of 9. param pref_size specifies how many leading/trailing bytes of object's encoded form will be used for hash computation this(pref_size, 9);
public Cache() Creates the Cache object of size of 9. this(28, 9);

Methods Summary
public boolean	contains(long prefix_hash) Checks if there are any object in the cache generated on the base of encoding with prefix corresponding to the specified hash code. param prefix_hash the hash code for the prefix of the encoding (retrieved by method getHash(byte[])) return false if there were not any object generated on the base of encoding with specified hash code, true otherwise. int idx = -1*Arrays.binarySearch(hashes_idx, prefix_hash)-1; if (idx == cache_size) { return false; } else { return (hashes_idx[idx] & PREFIX_HASH_MASK) == prefix_hash; }
public java.lang.Object	get(long hash, byte[] encoding) Returns the object built on the base on the specified encoded form if it is contained in the cache and null otherwise. This method is computationally expensive and should be called only if the method contains(long) for the hash code returned true. param hash the hash code for the prefix of the encoding (retrieved by method getHash(byte[])) param encoding encoded form of the required object. return the object corresponding to specified encoding or null if there is no such correspondence. hash |= getSuffHash(encoding); int idx = -1*Arrays.binarySearch(hashes_idx, hash)-1; if (idx == cache_size) { return null; } while ((hashes_idx[idx] & HASH_MASK) == hash) { int i = (int) (hashes_idx[idx] & INDEX_MASK) - 1; if (Arrays.equals(encoding, encodings[i])) { return cache[i]; } idx++; if (idx == cache_size) { return null; } } return null;
public long	getHash(byte[] arr) Returns the hash code for the array. This code is used to predetermine whether the object was built on the base of the similar encoding or not (by means of contains(long) method), to exactly determine whether object is contained in the cache or not, and to put the object in the cache. Note: parameter array should be of length not less than specified by prefix_size (default 28) param arr the byte array containing at least prefix_size leading bytes of the encoding. return hash code for specified encoding prefix long hash = 0; for (int i=1; i<prefix_size; i++) { hash += (arr[i] & 0xFF); } // it takes about 2 bytes for prefix_size == 28 // shift to the correct place hash = hash << 32; return hash;
private long	getSuffHash(byte[] arr) long hash_addon = 0; for (int i=arr.length-1; i>arr.length - prefix_size; i--) { hash_addon += (arr[i] & 0xFF); } return hash_addon << 16;
public void	put(long hash, byte[] encoding, java.lang.Object object) Puts the object into the cache. param hash hash code for the prefix of the encoding param encoding the encoded form of the object param object the object to be saved in the cache // check for empty space in the cache if (last_cached == cache_size) { // so cache is full, will erase the first entry in the // cache (oldest entry). it could be better to throw out // rarely used value instead of oldest one.. last_cached = 0; cache_is_full = true; } // index pointing to the item of the table to be overwritten int index = last_cached++; // improve the hash value with info from the tail of encoding hash |= getSuffHash(encoding); if (cache_is_full) { // indexing hash value to be overwritten: long idx_hash = (hashes[index] | (index+1)); int idx = Arrays.binarySearch(hashes_idx, idx_hash); if (idx < 0) { // it will never happen because we use saved hash value // (hashes[index]) System.out.println("WARNING! "+idx); //$NON-NLS-1$ idx = -(idx + 1); } long new_hash_idx = (hash | (index + 1)); int new_idx = Arrays.binarySearch(hashes_idx, new_hash_idx); if (new_idx >= 0) { // it's possible when we write the same hash in the same cell if (idx != new_idx) { // it will never happen because we use the same // hash and the same index in hash table System.out.println("WARNING: "); //$NON-NLS-1$ System.out.println(">> idx: "+idx+" new_idx: "+new_idx); //$NON-NLS-1$ //$NON-NLS-2$ } } else { new_idx = -(new_idx + 1); // replace in sorted array if (new_idx > idx) { System.arraycopy(hashes_idx, idx+1, hashes_idx, idx, new_idx - idx - 1); hashes_idx[new_idx-1] = new_hash_idx; } else if (idx > new_idx) { System.arraycopy(hashes_idx, new_idx, hashes_idx, new_idx+1, idx - new_idx); hashes_idx[new_idx] = new_hash_idx; } else { // idx == new_idx hashes_idx[new_idx] = new_hash_idx; } } } else { long idx_hash = (hash | (index + 1)); int idx = Arrays.binarySearch(hashes_idx, idx_hash); if (idx < 0) { // it will always be true because idx_hash depends on index idx = -(idx + 1); } idx = idx - 1; if (idx != cache_size - index - 1) { // if not in the cell containing 0 (free cell), do copy: System.arraycopy(hashes_idx, cache_size - index, hashes_idx, cache_size - index - 1, idx - (cache_size - index) + 1); } hashes_idx[idx] = idx_hash; } // overwrite the values in the tables: hashes[index] = hash; encodings[index] = encoding; cache[index] = object;