Package it.unimi.di.law.bubing.util

Class FastApproximateByteArrayCache

java.lang.Object

it.unimi.di.law.bubing.util.FastApproximateByteArrayCache

public class FastApproximateByteArrayCache
extends java.lang.Object

A fast, concurrent approximate cache for byte arrays.

This cache stores 128-bit MurmurHash3 fingerprints of byte arrays. Fingerprints are stored in a number of stripes whose access is synchronized. Each stripe is an open-address linked hash table similar to a LongLinkedOpenHashSet.

Fingerprints are evicted using a standard LRU strategy. Since we store fingerprints, it is in principle possible to get false positives (i.e., add(byte[]) might return false even if the argument was never added to the cache).

The number of objects created by this map is very small, and depends only on the number of stripes, not on the size of the cache.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	FastApproximateByteArrayCache.Stripe	A class containing a stripe of the cache.

Constructor Summary

Constructors

Constructor	Description
FastApproximateByteArrayCache(long byteSize)	Creates a new cache with specified size and concurrency level equal to Runtime.availableProcessors().
FastApproximateByteArrayCache(long byteSize, int concurrencyLevel)	Creates a new cache with specified size.

Method Summary

Modifier and Type	Method	Description
boolean	add(byte[] key)
boolean	add(byte[] key, int offset, int length)
boolean	add(ByteArrayList key)
long	hits()	Returns the number of cache hits.
long	misses()	Returns the number of cache misses.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

FastApproximateByteArrayCache

public FastApproximateByteArrayCache(long byteSize)

Creates a new cache with specified size and concurrency level equal to Runtime.availableProcessors().

Parameters:

byteSize - the approximate size of the cache in bytes.

FastApproximateByteArrayCache

public FastApproximateByteArrayCache(long byteSize,
                                     int concurrencyLevel)

Creates a new cache with specified size.

Parameters:

byteSize - the approximate size of the cache in bytes.

concurrencyLevel - the number of stripes (it will be forced to be a power of two).

Method Detail

add

public boolean add(byte[] key)

add

public boolean add(ByteArrayList key)

add

public boolean add(byte[] key,
                   int offset,
                   int length)

hits

public long hits()

Returns the number of cache hits.

Returns:

the number of cache hits.

misses

public long misses()

Returns the number of cache misses.

Returns:

the number of cache misses.