BlobCache
提到此算法，就是想到上一篇LruCache算法 ，BlobCache 算法与LruCache算法都是图片缓存算法，在安卓中使用到源码：
仅利用三个文件：Index文件，Active文件和Unactive文件。通过FileInputStream().getChannel().map()把索引文件直接映射到内存中，通过索引偏移来读取文件中的图片缓存。清除旧图片的方法就是seek到文件头部，覆盖写入处理。为了最小的磁盘I/O代价完成磁盘缓存。
【BlobCache算法】当然谷歌建议把从内存淘汰的图片降低压缩比存储到本地中，最大限度地降低以后备用的解码开销。
/*
* Copyright (C) 2010 The Android Open Source Project
*
* Licensed 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.
*/// This is an on-disk cache which maps a 64-bits key to a byte array.
//
// It consists of three files: one index file and two data files. One of the
// data files is "active", and the other is "inactive". New entries are
// appended into the active region until it reaches the size limit. At that
// point the active file and the inactive file are swapped, and the new active
// file is truncated to empty (and the index for that file is also cleared).
// The index is a hash table with linear probing. When the load factor reaches
// 0.5, it does the same thing like when the size limit is reached.
//
// The index file format: (all numbers are stored in little-endian)
// [0]Magic number: 0xB3273030
// [4]MaxEntries: Max number of hash entries per region.
// [8]MaxBytes: Max number of data bytes per region (including header).
// [12] ActiveRegion: The active growing region: 0 or 1.
// [16] ActiveEntries: The number of hash entries used in the active region.
// [20] ActiveBytes: The number of data bytes used in the active region.
// [24] Version number.
// [28] Checksum of [0..28).
// [32] Hash entries for region 0. The size is X = (12 * MaxEntries bytes).
// [32 + X] Hash entries for region 1. The size is also X.
//
// Each hash entry is 12 bytes: 8 bytes key and 4 bytes offset into the data
// file. The offset is 0 when the slot is free. Note that 0 is a valid value
// for key. The keys are used directly as index into a hash table, so they
// should be suitably distributed.
//
// Each data file stores data for one region. The data file is concatenated
// blobs followed by the magic number 0xBD248510.
//
// The blob format:
// [0]Key of this blob
// [8]Checksum of this blob
// [12] Offset of this blob
// [16] Length of this blob (not including header)
// [20] Blob
//
// Below are the interface for BlobCache. The instance of this class does not
// support concurrent use by multiple threads.
//
// public BlobCache(String path, int maxEntries, int maxBytes, boolean reset) throws IOException;
// public void insert(long key, byte[] data) throws IOException;
// public byte[] lookup(long key) throws IOException;
// public void lookup(LookupRequest req) throws IOException;
// public void close();
// public void syncIndex();
// public void syncAll();
// public static void deleteFiles(String path);
//
...import android.util.Log;
import java.io.Closeable;
import java.io.File;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.nio.ByteOrder;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.util.Arrays;
import java.util.zip.Adler32;
public class BlobCache implements Closeable {
private static final String TAG = "BlobCache";
private static final int MAGIC_INDEX_FILE = 0xB3273030;
private static final int MAGIC_DATA_FILE = 0xBD248510;
// index header offset
private static final int IH_MAGIC = 0;
private static final int IH_MAX_ENTRIES = 4;
private static final int IH_MAX_BYTES = 8;
private static final int IH_ACTIVE_REGION = 12;
private static final int IH_ACTIVE_ENTRIES = 16;
private static final int IH_ACTIVE_BYTES = 20;
private static final int IH_VERSION = 24;
private static final int IH_CHECKSUM = 28;
private static final int INDEX_HEADER_SIZE = 32;
private static final int DATA_HEADER_SIZE = 4;
// blob header offset
private static final int BH_KEY = 0;
private static final int BH_CHECKSUM = 8;
private static final int BH_OFFSET = 12;
private static final int BH_LENGTH = 16;
private static final int BLOB_HEADER_SIZE = 20;
private RandomAccessFile mIndexFile;
private RandomAccessFile mDataFile0;
private RandomAccessFile mDataFile1;
private FileChannel mIndexChannel;
private MappedByteBuffer mIndexBuffer;
private int mMaxEntries;
private int mMaxBytes;
private int mActiveRegion;
private int mActiveEntries;
private int mActiveBytes;
private int mVersion;
private RandomAccessFile mActiveDataFile;
private RandomAccessFile mInactiveDataFile;
private int mActiveHashStart;
private int mInactiveHashStart;
private byte[] mIndexHeader = new byte[INDEX_HEADER_SIZE];
private byte[] mBlobHeader = new byte[BLOB_HEADER_SIZE];
private Adler32 mAdler32 = new Adler32();
// Creates the cache. Three files will be created:
// path + ".idx", path + ".0", and path + ".1"
// The ".0" file and the ".1" file each stores data for a region. Each of
// them can grow to the size specified by maxBytes. The maxEntries parameter
// specifies the maximum number of entries each region can have. If the
// "reset" parameter is true, the cache will be cleared before use.
public BlobCache(String path, int maxEntries, int maxBytes, boolean reset)
throws IOException {
this(path, maxEntries, maxBytes, reset, 0);
}public BlobCache(String path, int maxEntries, int maxBytes, boolean reset,
int version) throws IOException {
mIndexFile = new RandomAccessFile(path + ".idx", "rw");
mDataFile0 = new RandomAccessFile(path + ".0", "rw");
mDataFile1 = new RandomAccessFile(path + ".1", "rw");
mVersion = version;
if (!reset && loadIndex()) {
return;
}resetCache(maxEntries, maxBytes);
if (!loadIndex()) {
closeAll();
throw new IOException("unable to load index");
}
}// Delete the files associated with the given path previously created
// by the BlobCache constructor.
public static void deleteFiles(String path) {
deleteFileSilently(path + ".idx");
deleteFileSilently(path + ".0");
deleteFileSilently(path + ".1");
}private static void deleteFileSilently(String path) {
try {
new File(path).delete();
} catch (Throwable t) {
// ignore;
}
}// Close the cache. All resources are released. No other method should be
// called after this is called.
@Override
public void close() {
syncAll();
closeAll();
}private void closeAll() {
closeSilently(mIndexChannel);
closeSilently(mIndexFile);
closeSilently(mDataFile0);
closeSilently(mDataFile1);
}// Returns true if loading index is successful. After this method is called,
// mIndexHeader and index header in file should be kept sync.
private boolean loadIndex() {
try {
mIndexFile.seek(0);
mDataFile0.seek(0);
mDataFile1.seek(0);
byte[] buf = mIndexHeader;
if (mIndexFile.read(buf) != INDEX_HEADER_SIZE) {
Log.w(TAG, "cannot read header");
return false;
}if (readInt(buf, IH_MAGIC) != MAGIC_INDEX_FILE) {
Log.w(TAG, "cannot read header magic");
return false;
}if (readInt(buf, IH_VERSION) != mVersion) {
Log.w(TAG, "version mismatch");
return false;
}mMaxEntries = readInt(buf, IH_MAX_ENTRIES);
mMaxBytes = readInt(buf, IH_MAX_BYTES);
mActiveRegion = readInt(buf, IH_ACTIVE_REGION);
mActiveEntries = readInt(buf, IH_ACTIVE_ENTRIES);
mActiveBytes = readInt(buf, IH_ACTIVE_BYTES);
int sum = readInt(buf, IH_CHECKSUM);
if (checkSum(buf, 0, IH_CHECKSUM) != sum) {
Log.w(TAG, "header checksum does not match");
return false;
}// Sanity check
if (mMaxEntries <= 0) {
Log.w(TAG, "invalid max entries");
return false;
}
if (mMaxBytes <= 0) {
Log.w(TAG, "invalid max bytes");
return false;
}
if (mActiveRegion != 0 && mActiveRegion != 1) {
Log.w(TAG, "invalid active region");
return false;
}
if (mActiveEntries < 0 || mActiveEntries > mMaxEntries) {
Log.w(TAG, "invalid active entries");
return false;
}
if (mActiveBytes < DATA_HEADER_SIZE || mActiveBytes > mMaxBytes) {
Log.w(TAG, "invalid active bytes");
return false;
}
if (mIndexFile.length() !=
INDEX_HEADER_SIZE + mMaxEntries * 12 * 2) {
Log.w(TAG, "invalid index file length");
return false;
}// Make sure data file has magic
byte[] magic = new byte[4];
if (mDataFile0.read(magic) != 4) {
Log.w(TAG, "cannot read data file magic");
return false;
}
if (readInt(magic, 0) != MAGIC_DATA_FILE) {
Log.w(TAG, "invalid data file magic");
return false;
}
if (mDataFile1.read(magic) != 4) {
Log.w(TAG, "cannot read data file magic");
return false;
}
if (readInt(magic, 0) != MAGIC_DATA_FILE) {
Log.w(TAG, "invalid data file magic");
return false;
}// Map index file to memory
mIndexChannel = mIndexFile.getChannel();
mIndexBuffer = mIndexChannel.map(FileChannel.MapMode.READ_WRITE,
0, mIndexFile.length());
mIndexBuffer.order(ByteOrder.LITTLE_ENDIAN);
setActiveVariables();
return true;
} catch (IOException ex) {
Log.e(TAG, "loadIndex failed.", ex);
return false;
}
}private void setActiveVariables() throws IOException {
mActiveDataFile = (mActiveRegion == 0) ? mDataFile0 : mDataFile1;
mInactiveDataFile = (mActiveRegion == 1) ? mDataFile0 : mDataFile1;
mActiveDataFile.setLength(mActiveBytes);
mActiveDataFile.seek(mActiveBytes);
mActiveHashStart = INDEX_HEADER_SIZE;
mInactiveHashStart = INDEX_HEADER_SIZE;
if (mActiveRegion == 0) {
mInactiveHashStart += mMaxEntries * 12;
} else {
mActiveHashStart += mMaxEntries * 12;
}
}private void resetCache(int maxEntries, int maxBytes) throws IOException {
mIndexFile.setLength(0);
// truncate to zero the index
mIndexFile.setLength(INDEX_HEADER_SIZE + maxEntries * 12 * 2);
mIndexFile.seek(0);
byte[] buf = mIndexHeader;
writeInt(buf, IH_MAGIC, MAGIC_INDEX_FILE);
writeInt(buf, IH_MAX_ENTRIES, maxEntries);
writeInt(buf, IH_MAX_BYTES, maxBytes);
writeInt(buf, IH_ACTIVE_REGION, 0);
writeInt(buf, IH_ACTIVE_ENTRIES, 0);
writeInt(buf, IH_ACTIVE_BYTES, DATA_HEADER_SIZE);
writeInt(buf, IH_VERSION, mVersion);
writeInt(buf, IH_CHECKSUM, checkSum(buf, 0, IH_CHECKSUM));
mIndexFile.write(buf);
// This is only needed if setLength does not zero the extended part.
// writeZero(mIndexFile, maxEntries * 12 * 2);
mDataFile0.setLength(0);
mDataFile1.setLength(0);
mDataFile0.seek(0);
mDataFile1.seek(0);
writeInt(buf, 0, MAGIC_DATA_FILE);
mDataFile0.write(buf, 0, 4);
mDataFile1.write(buf, 0, 4);
}// Flip the active region and the inactive region.
private void flipRegion() throws IOException {
mActiveRegion = 1 - mActiveRegion;
mActiveEntries = 0;
mActiveBytes = DATA_HEADER_SIZE;
writeInt(mIndexHeader, IH_ACTIVE_REGION, mActiveRegion);
writeInt(mIndexHeader, IH_ACTIVE_ENTRIES, mActiveEntries);
writeInt(mIndexHeader, IH_ACTIVE_BYTES, mActiveBytes);
updateIndexHeader();
setActiveVariables();
clearHash(mActiveHashStart);
syncIndex();
}// Sync mIndexHeader to the index file.
private void updateIndexHeader() {
writeInt(mIndexHeader, IH_CHECKSUM,
checkSum(mIndexHeader, 0, IH_CHECKSUM));
mIndexBuffer.position(0);
mIndexBuffer.put(mIndexHeader);
}// Clear the hash table starting from the specified offset.
private void clearHash(int hashStart) {
byte[] zero = new byte[1024];
mIndexBuffer.position(hashStart);
for (int count = mMaxEntries * 12;
count > 0;
) {
int todo = Math.min(count, 1024);
mIndexBuffer.put(zero, 0, todo);
count -= todo;
}
}// Inserts a (key, data) pair into the cache.
public void insert(long key, byte[] data) throws IOException {
if (DATA_HEADER_SIZE + BLOB_HEADER_SIZE + data.length > mMaxBytes) {
throw new RuntimeException("blob is too large!");
}if (mActiveBytes + BLOB_HEADER_SIZE + data.length > mMaxBytes
|| mActiveEntries * 2 >= mMaxEntries) {
flipRegion();
}if (!lookupInternal(key, mActiveHashStart)) {
// If we don't have an existing entry with the same key, increase
// the entry count.
mActiveEntries++;
writeInt(mIndexHeader, IH_ACTIVE_ENTRIES, mActiveEntries);
}insertInternal(key, data, data.length);
updateIndexHeader();
}public void clearEntry(long key) throws IOException {
if (!lookupInternal(key, mActiveHashStart)) {
return;
// Nothing to clear
}
byte[] header = mBlobHeader;
Arrays.fill(header, (byte) 0);
mActiveDataFile.seek(mFileOffset);
mActiveDataFile.write(header);
}// Appends the data to the active file. It also updates the hash entry.
// The proper hash entry (suitable for insertion or replacement) must be
// pointed by mSlotOffset.
private void insertInternal(long key, byte[] data, int length)
throws IOException {
byte[] header = mBlobHeader;
int sum = checkSum(data);
writeLong(header, BH_KEY, key);
writeInt(header, BH_CHECKSUM, sum);
writeInt(header, BH_OFFSET, mActiveBytes);
writeInt(header, BH_LENGTH, length);
mActiveDataFile.write(header);
mActiveDataFile.write(data, 0, length);
mIndexBuffer.putLong(mSlotOffset, key);
mIndexBuffer.putInt(mSlotOffset + 8, mActiveBytes);
mActiveBytes += BLOB_HEADER_SIZE + length;
writeInt(mIndexHeader, IH_ACTIVE_BYTES, mActiveBytes);
}public static class LookupRequest {
public long key;
// input: the key to find
public byte[] buffer;
// input/output: the buffer to store the blob
public int length;
// output: the length of the blob
}// This method is for one-off lookup. For repeated lookup, use the version
// accepting LookupRequest to avoid repeated memory allocation.
private LookupRequest mLookupRequest = new LookupRequest();
public byte[] lookup(long key) throws IOException {
mLookupRequest.key = key;
mLookupRequest.buffer = null;
if (lookup(mLookupRequest)) {
return mLookupRequest.buffer;
} else {
return null;
}
}// Returns true if the associated blob for the given key is available.
// The blob is stored in the buffer pointed by req.buffer, and the length
// is in stored in the req.length variable.
//
// The user can input a non-null value in req.buffer, and this method will
// try to use that buffer. If that buffer is not large enough, this method
// will allocate a new buffer and assign it to req.buffer.
//
// This method tries not to throw IOException even if the data file is
// corrupted, but it can still throw IOException if things get strange.
public boolean lookup(LookupRequest req) throws IOException {
// Look up in the active region first.
if (lookupInternal(req.key, mActiveHashStart)) {
if (getBlob(mActiveDataFile, mFileOffset, req)) {
return true;
}
}// We want to copy the data from the inactive file to the active file
// if it's available. So we keep the offset of the hash entry so we can
// avoid looking it up again.
int insertOffset = mSlotOffset;
// Look up in the inactive region.
if (lookupInternal(req.key, mInactiveHashStart)) {
if (getBlob(mInactiveDataFile, mFileOffset, req)) {
// If we don't have enough space to insert this blob into
// the active file, just return it.
if (mActiveBytes + BLOB_HEADER_SIZE + req.length > mMaxBytes
|| mActiveEntries * 2 >= mMaxEntries) {
return true;
}
// Otherwise copy it over.
mSlotOffset = insertOffset;
try {
insertInternal(req.key, req.buffer, req.length);
mActiveEntries++;
writeInt(mIndexHeader, IH_ACTIVE_ENTRIES, mActiveEntries);
updateIndexHeader();
} catch (Throwable t) {
Log.e(TAG, "cannot copy over");
}
return true;
}
}return false;
}// Copies the blob for the specified offset in the specified file to
// req.buffer. If req.buffer is null or too small, allocate a buffer and
// assign it to req.buffer.
// Returns false if the blob is not available (either the index file is
// not sync with the data file, or one of them is corrupted). The length
// of the blob is stored in the req.length variable.
private boolean getBlob(RandomAccessFile file, int offset,
LookupRequest req) throws IOException {
byte[] header = mBlobHeader;
long oldPosition = file.getFilePointer();
try {
file.seek(offset);
if (file.read(header) != BLOB_HEADER_SIZE) {
Log.w(TAG, "cannot read blob header");
return false;
}
long blobKey = readLong(header, BH_KEY);
if (blobKey == 0) {
return false;
// This entry has been cleared.
}
if (blobKey != req.key) {
Log.w(TAG, "blob key does not match: " + blobKey);
return false;
}
int sum = readInt(header, BH_CHECKSUM);
int blobOffset = readInt(header, BH_OFFSET);
if (blobOffset != offset) {
Log.w(TAG, "blob offset does not match: " + blobOffset);
return false;
}
int length = readInt(header, BH_LENGTH);
if (length < 0 || length > mMaxBytes - offset - BLOB_HEADER_SIZE) {
Log.w(TAG, "invalid blob length: " + length);
return false;
}
if (req.buffer == null || req.buffer.length < length) {
req.buffer = new byte[length];
}byte[] blob = req.buffer;
req.length = length;
if (file.read(blob, 0, length) != length) {
Log.w(TAG, "cannot read blob data");
return false;
}
if (checkSum(blob, 0, length) != sum) {
Log.w(TAG, "blob checksum does not match: " + sum);
return false;
}
return true;
} catch (Throwable t){
Log.e(TAG, "getBlob failed.", t);
return false;
} finally {
file.seek(oldPosition);
}
}// Tries to look up a key in the specified hash region.
// Returns true if the lookup is successful.
// The slot offset in the index file is saved in mSlotOffset. If the lookup
// is successful, it's the slot found. Otherwise it's the slot suitable for
// insertion.
// If the lookup is successful, the file offset is also saved in
// mFileOffset.
private int mSlotOffset;
private int mFileOffset;
private boolean lookupInternal(long key, int hashStart) {
int slot = (int) (key % mMaxEntries);
if (slot < 0) slot += mMaxEntries;
int slotBegin = slot;
while (true) {
int offset = hashStart + slot * 12;
long candidateKey = mIndexBuffer.getLong(offset);
int candidateOffset = mIndexBuffer.getInt(offset + 8);
if (candidateOffset == 0) {
mSlotOffset = offset;
return false;
} else if (candidateKey == key) {
mSlotOffset = offset;
mFileOffset = candidateOffset;
return true;
} else {
if (++slot >= mMaxEntries) {
slot = 0;
}
if (slot == slotBegin) {
Log.w(TAG, "corrupted index: clear the slot.");
mIndexBuffer.putInt(hashStart + slot * 12 + 8, 0);
}
}
}
}public void syncIndex() {
try {
mIndexBuffer.force();
} catch (Throwable t) {
Log.w(TAG, "sync index failed", t);
}
}public void syncAll() {
syncIndex();
try {
mDataFile0.getFD().sync();
} catch (Throwable t) {
Log.w(TAG, "sync data file 0 failed", t);
}
try {
mDataFile1.getFD().sync();
} catch (Throwable t) {
Log.w(TAG, "sync data file 1 failed", t);
}
}// This is for testing only.
//
// Returns the active count (mActiveEntries). This also verifies that
// the active count matches matches what's inside the hash region.
int getActiveCount() {
int count = 0;
for (int i = 0;
i < mMaxEntries;
i++) {
int offset = mActiveHashStart + i * 12;
long candidateKey = mIndexBuffer.getLong(offset);
int candidateOffset = mIndexBuffer.getInt(offset + 8);
if (candidateOffset != 0) ++count;
}
if (count == mActiveEntries) {
return count;
} else {
Log.e(TAG, "wrong active count: " + mActiveEntries + " vs " + count);
return -1;
// signal failure.
}
}int checkSum(byte[] data) {
mAdler32.reset();
mAdler32.update(data);
return (int) mAdler32.getValue();
}int checkSum(byte[] data, int offset, int nbytes) {
mAdler32.reset();
mAdler32.update(data, offset, nbytes);
return (int) mAdler32.getValue();
}static void closeSilently(Closeable c) {
if (c == null) return;
try {
c.close();
} catch (Throwable t) {
// do nothing
}
}static int readInt(byte[] buf, int offset) {
return (buf[offset] & 0xff)
| ((buf[offset + 1] & 0xff) << 8)
| ((buf[offset + 2] & 0xff) << 16)
| ((buf[offset + 3] & 0xff) << 24);
}static long readLong(byte[] buf, int offset) {
long result = buf[offset + 7] & 0xff;
for (int i = 6;
i >= 0;
i--) {
result = (result << 8) | (buf[offset + i] & 0xff);
}
return result;
}static void writeInt(byte[] buf, int offset, int value) {
for (int i = 0;
i < 4;
i++) {
buf[offset + i] = (byte) (value & 0xff);
value >>= 8;
}
}static void writeLong(byte[] buf, int offset, long value) {
for (int i = 0;
i < 8;
i++) {
buf[offset + i] = (byte) (value & 0xff);
value >>= 8;
}
}
}
