alluxio.client.file.cache.cuckoofilter

Class SimpleCuckooTable

java.lang.Object

alluxio.client.file.cache.cuckoofilter.SimpleCuckooTable

All Implemented Interfaces:

CuckooTable

public class SimpleCuckooTable
extends java.lang.Object
implements CuckooTable

A simple cuckoo table.

Constructor Summary

Constructors

Constructor and Description
SimpleCuckooTable(BitSet bitSet, int numBuckets, int tagsPerBucket, int bitsPerTag) Create a single cuckoo table on given bit set.

Method Summary

Modifier and Type	Method and Description
TagPosition	deleteTag(int bucketIndex, int tag) Delete a tag in specified bucket and return its position.
TagPosition	findTag(int bucketIndex, int tag) Find a tag in specified bucket and return its position.
TagPosition	findTag(int bucketIndex1, int bucketIndex2, int tag) Find a tag in specified two buckets and return its position.
int	getBitsPerTag()
int	getNumBuckets()
int	getNumTagsPerBuckets()
int	getSizeInBytes()
int	getSizeInTags()
int	insertOrKickTag(int bucketIndex, int tag) Insert a tag into specified bucket.
int	readTag(int bucketIndex, int slotIndex) Reads the value of tag in specified position.
void	writeTag(int bucketIndex, int slotIndex, int tag) Set the value of tag in specified position.

Methods inherited from class java.lang.Object

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

Constructor Detail

SimpleCuckooTable

public SimpleCuckooTable(BitSet bitSet,
                         int numBuckets,
                         int tagsPerBucket,
                         int bitsPerTag)

Create a single cuckoo table on given bit set.

Parameters:

bitSet - the bit set will be used as the underlying storage

numBuckets - the number of buckets this table has

tagsPerBucket - the number of slots each bucket has

bitsPerTag - the number of bits each slot has

Method Detail

readTag

public int readTag(int bucketIndex,
                   int slotIndex)

Description copied from interface: CuckooTable

Reads the value of tag in specified position.

Specified by:

readTag in interface CuckooTable

Parameters:

bucketIndex - the bucket index

slotIndex - the slot in bucket

Returns:

the tag value to read

writeTag

public void writeTag(int bucketIndex,
                     int slotIndex,
                     int tag)

Description copied from interface: CuckooTable

Set the value of tag in specified position.

Specified by:

writeTag in interface CuckooTable

Parameters:

bucketIndex - the bucket index

slotIndex - the slot in bucket

tag - the tag value to write

findTag

public TagPosition findTag(int bucketIndex,
                           int tag)

Description copied from interface: CuckooTable

Find a tag in specified bucket and return its position.

Specified by:

findTag in interface CuckooTable

Parameters:

bucketIndex - the bucket index

tag - the tag value to find

Returns:

the valid position of this tag if it is found; otherwise an invalid position indicates that tag is not found

findTag

public TagPosition findTag(int bucketIndex1,
                           int bucketIndex2,
                           int tag)

Description copied from interface: CuckooTable

Find a tag in specified two buckets and return its position.

Specified by:

findTag in interface CuckooTable

Parameters:

bucketIndex1 - the first bucket index

bucketIndex2 - the second bucket index

tag - the tag value to find

Returns:

the valid position of this tag if it is found; otherwise an invalid position indicates that tag is not found

deleteTag

public TagPosition deleteTag(int bucketIndex,
                             int tag)

Description copied from interface: CuckooTable

Delete a tag in specified bucket and return its position.

Specified by:

deleteTag in interface CuckooTable

Parameters:

bucketIndex - the bucket to delete from

tag - the tag value to find

Returns:

the valid position of this tag if it is found and deleted; otherwise an invalid position indicates that tag is not found

insertOrKickTag

public int insertOrKickTag(int bucketIndex,
                           int tag)

Description copied from interface: CuckooTable

Insert a tag into specified bucket. If no empty slot found, it will kickout one randomly and return the victim's tag value.

Specified by:

insertOrKickTag in interface CuckooTable

Parameters:

bucketIndex - the bucket index

tag - the tag value to find

Returns:

the tag value kicked out

getNumTagsPerBuckets

public int getNumTagsPerBuckets()

Specified by:

getNumTagsPerBuckets in interface CuckooTable

Returns:

the number of tags per bucket

getNumBuckets

public int getNumBuckets()

Specified by:

getNumBuckets in interface CuckooTable

Returns:

the number of buckets

getBitsPerTag

public int getBitsPerTag()

Specified by:

getBitsPerTag in interface CuckooTable

Returns:

the number of bits per tag

getSizeInBytes

public int getSizeInBytes()

Specified by:

getSizeInBytes in interface CuckooTable

Returns:

the number of bytes

getSizeInTags

public int getSizeInTags()

Specified by:

getSizeInTags in interface CuckooTable

Returns:

the number of tags