Add TextLayout Cache
- use GenerationCache for caching
- move GenerationCache.h from libs/hwui/utils to include/utils
- add #define for cache activation / deactivation
Change-Id: Ifaf519f0b5e33b087a453e4aa6430162d8438f20
diff --git a/libs/hwui/utils/GenerationCache.h b/GenerationCache.h
similarity index 100%
rename from libs/hwui/utils/GenerationCache.h
rename to GenerationCache.h
diff --git a/core/jni/Android.mk b/core/jni/Android.mk
index 41baca2..12eda8e 100644
--- a/core/jni/Android.mk
+++ b/core/jni/Android.mk
@@ -112,6 +112,7 @@
android/graphics/Shader.cpp \
android/graphics/SurfaceTexture.cpp \
android/graphics/TextLayout.cpp \
+ android/graphics/TextLayoutCache.cpp \
android/graphics/Typeface.cpp \
android/graphics/Utils.cpp \
android/graphics/Xfermode.cpp \
diff --git a/core/jni/android/graphics/RtlProperties.h b/core/jni/android/graphics/RtlProperties.h
new file mode 100644
index 0000000..6d8ba91
--- /dev/null
+++ b/core/jni/android/graphics/RtlProperties.h
@@ -0,0 +1,49 @@
+/*
+ * Copyright (C) 2011 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.
+ */
+
+#ifndef ANDROID_RTL_PROPERTIES_H
+#define ANDROID_RTL_PROPERTIES_H
+
+#include <cutils/properties.h>
+#include <stdlib.h>
+
+namespace android {
+
+/**
+ * Debug level for app developers.
+ */
+#define RTL_PROPERTY_DEBUG "rtl.debug_level"
+
+/**
+ * Debug levels. Debug levels are used as flags.
+ */
+enum RtlDebugLevel {
+ kRtlDebugDisabled = 0,
+ kRtlDebugMemory = 1,
+ kRtlDebugCaches = 2,
+ kRtlDebugAllocations = 3
+};
+
+static RtlDebugLevel readRtlDebugLevel() {
+ char property[PROPERTY_VALUE_MAX];
+ if (property_get(RTL_PROPERTY_DEBUG, property, NULL) > 0) {
+ return (RtlDebugLevel) atoi(property);
+ }
+ return kRtlDebugDisabled;
+}
+
+} // namespace android
+#endif // ANDROID_RTL_PROPERTIES_H
diff --git a/core/jni/android/graphics/TextLayout.cpp b/core/jni/android/graphics/TextLayout.cpp
index e957635..f1bb696 100644
--- a/core/jni/android/graphics/TextLayout.cpp
+++ b/core/jni/android/graphics/TextLayout.cpp
@@ -15,6 +15,7 @@
*/
#include "TextLayout.h"
+#include "TextLayoutCache.h"
#include <android_runtime/AndroidRuntime.h>
@@ -23,10 +24,12 @@
#include "unicode/ushape.h"
#include <utils/Log.h>
-// Log debug messages from RTL related allocations
-#define DEBUG_RTL_ALLOCATIONS 0
-
namespace android {
+
+#if USE_TEXT_LAYOUT_CACHE
+TextLayoutCache TextLayout::mCache;
+#endif
+
// Returns true if we might need layout. If bidiFlags force LTR, assume no layout, if
// bidiFlags indicate there probably is RTL, assume we do, otherwise scan the text
// looking for a character >= the first RTL character in unicode and assume we do if
@@ -60,14 +63,10 @@
* @return the length of the shaped text, or -1 if error
*/
int TextLayout::shapeRtlText(const jchar* context, jsize start, jsize count, jsize contextCount,
- jchar* shaped, UErrorCode &status) {
+ jchar* shaped, UErrorCode& status) {
SkAutoSTMalloc<CHAR_BUFFER_SIZE, jchar> tempBuffer(contextCount);
jchar* buffer = tempBuffer.get();
-#if DEBUG_RTL_ALLOCATIONS
- LOGD("TextLayout::shapeRtlText - allocated buffer with size: %d", contextCount);
-#endif
-
// Use fixed length since we need to keep start and count valid
u_shapeArabic(context, contextCount, buffer, contextCount,
U_SHAPE_LENGTH_FIXED_SPACES_NEAR |
@@ -105,8 +104,8 @@
* @flags line bidi flags
* @return the length of the reordered, shaped line, or -1 if error
*/
-jint TextLayout::layoutLine(const jchar* text, jint len, jint flags, int &dir, jchar* buffer,
- UErrorCode &status) {
+jint TextLayout::layoutLine(const jchar* text, jint len, jint flags, int& dir, jchar* buffer,
+ UErrorCode& status) {
static const int RTL_OPTS = UBIDI_DO_MIRRORING | UBIDI_KEEP_BASE_COMBINING |
UBIDI_REMOVE_BIDI_CONTROLS | UBIDI_OUTPUT_REVERSE;
@@ -156,7 +155,7 @@
return result;
}
-bool TextLayout::prepareText(SkPaint *paint, const jchar* text, jsize len, jint bidiFlags,
+bool TextLayout::prepareText(SkPaint* paint, const jchar* text, jsize len, jint bidiFlags,
const jchar** outText, int32_t* outBytes, jchar** outBuffer) {
const jchar *workText = text;
jchar *buffer = NULL;
@@ -166,11 +165,6 @@
if (!buffer) {
return false;
}
-
-#if DEBUG_RTL_ALLOCATIONS
- LOGD("TextLayout::prepareText - allocated buffer with size: %d", len);
-#endif
-
UErrorCode status = U_ZERO_ERROR;
len = layoutLine(text, len, bidiFlags, dir, buffer, status); // might change len, dir
if (!U_SUCCESS(status)) {
@@ -178,7 +172,6 @@
free(buffer);
return false; // can't render
}
-
workText = buffer; // use the shaped text
}
@@ -262,74 +255,24 @@
}
}
-void TextLayout::getTextRunAdvances(SkPaint *paint, const jchar *chars, jint start,
+void TextLayout::getTextRunAdvances(SkPaint* paint, const jchar* chars, jint start,
jint count, jint contextCount, jint dirFlags,
- jfloat *resultAdvances, jfloat &resultTotalAdvance) {
- resultTotalAdvance = 0;
-
- SkAutoSTMalloc<CHAR_BUFFER_SIZE, jchar> tempBuffer(contextCount);
- jchar* buffer = tempBuffer.get();
-
-#if DEBUG_RTL_ALLOCATIONS
- LOGD("TextLayout::getTextRunAdvances - allocated buffer with size: %d", contextCount);
+ jfloat* resultAdvances, jfloat& resultTotalAdvance) {
+#if USE_TEXT_LAYOUT_CACHE
+ // Return advances from the cache. Compute them if needed
+ mCache.getRunAdvances(paint, chars, start, count, contextCount,
+ dirFlags, resultAdvances, &resultTotalAdvance);
+#else
+ // Compute advances and return them
+ RunAdvanceDescription::computeAdvances(paint, chars, start, count, contextCount, dirFlags,
+ resultAdvances, &resultTotalAdvance);
#endif
-
- SkScalar* scalarArray = (SkScalar*)resultAdvances;
-
- // this is where we'd call harfbuzz
- // for now we just use ushape.c
-
- int widths;
- const jchar* text;
- if (dirFlags & 0x1) { // rtl, call arabic shaping in case
- UErrorCode status = U_ZERO_ERROR;
- // Use fixed length since we need to keep start and count valid
- u_shapeArabic(chars, contextCount, buffer, contextCount,
- U_SHAPE_LENGTH_FIXED_SPACES_NEAR |
- U_SHAPE_TEXT_DIRECTION_LOGICAL | U_SHAPE_LETTERS_SHAPE |
- U_SHAPE_X_LAMALEF_SUB_ALTERNATE, &status);
- // we shouldn't fail unless there's an out of memory condition,
- // in which case we're hosed anyway
- for (int i = start, e = i + count; i < e; ++i) {
- if (buffer[i] == UNICODE_NOT_A_CHAR) {
- buffer[i] = UNICODE_ZWSP; // zero-width-space for skia
- }
- }
- text = buffer + start;
- widths = paint->getTextWidths(text, count << 1, scalarArray);
- } else {
- text = chars + start;
- widths = paint->getTextWidths(text, count << 1, scalarArray);
- }
-
- if (widths < count) {
- // Skia operates on code points, not code units, so surrogate pairs return only
- // one value. Expand the result so we have one value per UTF-16 code unit.
-
- // Note, skia's getTextWidth gets confused if it encounters a surrogate pair,
- // leaving the remaining widths zero. Not nice.
- for (int i = 0, p = 0; i < widths; ++i) {
- resultTotalAdvance += resultAdvances[p++] = SkScalarToFloat(scalarArray[i]);
- if (p < count &&
- text[p] >= UNICODE_FIRST_LOW_SURROGATE &&
- text[p] < UNICODE_FIRST_PRIVATE_USE &&
- text[p-1] >= UNICODE_FIRST_HIGH_SURROGATE &&
- text[p-1] < UNICODE_FIRST_LOW_SURROGATE) {
- resultAdvances[p++] = 0;
- }
- }
- } else {
- for (int i = 0; i < count; i++) {
- resultTotalAdvance += resultAdvances[i] = SkScalarToFloat(scalarArray[i]);
- }
- }
}
// Draws a paragraph of text on a single line, running bidi and shaping
void TextLayout::drawText(SkPaint* paint, const jchar* text, jsize len,
int bidiFlags, jfloat x, jfloat y, SkCanvas* canvas) {
-
handleText(paint, text, len, bidiFlags, x, y, canvas, NULL);
}
@@ -353,10 +296,6 @@
SkAutoSTMalloc<CHAR_BUFFER_SIZE, jchar> buffer(count);
-#if DEBUG_RTL_ALLOCATIONS
- LOGD("TextLayout::drawTextOnPath - allocated buffer with size: %d", count);
-#endif
-
int dir = kDirection_LTR;
UErrorCode status = U_ZERO_ERROR;
count = layoutLine(text, count, bidiFlags, dir, buffer.get(), status);
diff --git a/core/jni/android/graphics/TextLayout.h b/core/jni/android/graphics/TextLayout.h
index c98f745..a950d13 100644
--- a/core/jni/android/graphics/TextLayout.h
+++ b/core/jni/android/graphics/TextLayout.h
@@ -20,6 +20,8 @@
#include "SkPaint.h"
#include "unicode/utypes.h"
+#include "TextLayoutCache.h"
+
namespace android {
#define UNICODE_NOT_A_CHAR 0xffff
@@ -34,6 +36,11 @@
*/
#define CHAR_BUFFER_SIZE 80
+/**
+ * Turn on for using the Cache
+ */
+#define USE_TEXT_LAYOUT_CACHE 1
+
class TextLayout {
public:
@@ -62,22 +69,23 @@
jint start, jint count, jint contextCount,
int dirFlags, jfloat x, jfloat y, SkCanvas* canvas);
- static void getTextRunAdvances(SkPaint *paint, const jchar *chars, jint start,
+ static void getTextRunAdvances(SkPaint* paint, const jchar* chars, jint start,
jint count, jint contextCount, jint dirFlags,
- jfloat *resultAdvances, jfloat &resultTotalAdvance);
+ jfloat* resultAdvances, jfloat& resultTotalAdvance);
static void drawText(SkPaint* paint, const jchar* text, jsize len,
jint bidiFlags, jfloat x, jfloat y, SkCanvas* canvas);
- static void getTextPath(SkPaint *paint, const jchar *text, jsize len,
- jint bidiFlags, jfloat x, jfloat y, SkPath *path);
+ static void getTextPath(SkPaint* paint, const jchar* text, jsize len,
+ jint bidiFlags, jfloat x, jfloat y, SkPath* path);
static void drawTextOnPath(SkPaint* paint, const jchar* text, jsize len,
int bidiFlags, jfloat hOffset, jfloat vOffset,
SkPath* path, SkCanvas* canvas);
- static bool prepareText(SkPaint *paint, const jchar* text, jsize len, jint bidiFlags,
+ static bool prepareText(SkPaint* paint, const jchar* text, jsize len, jint bidiFlags,
const jchar** outText, int32_t* outBytes, jchar** outBuffer);
+
static bool prepareRtlTextRun(const jchar* context, jsize start, jsize& count,
jsize contextCount, jchar* shaped);
@@ -85,11 +93,15 @@
private:
static bool needsLayout(const jchar* text, jint len, jint bidiFlags);
static int shapeRtlText(const jchar* context, jsize start, jsize count, jsize contextCount,
- jchar* shaped, UErrorCode &status);
+ jchar* shaped, UErrorCode& status);
static jint layoutLine(const jchar* text, jint len, jint flags, int &dir, jchar* buffer,
UErrorCode &status);
- static void handleText(SkPaint *paint, const jchar* text, jsize len,
- int bidiFlags, jfloat x, jfloat y,SkCanvas *canvas, SkPath *path);
+ static void handleText(SkPaint* paint, const jchar* text, jsize len,
+ int bidiFlags, jfloat x, jfloat y, SkCanvas* canvas, SkPath* path);
+
+#if USE_TEXT_LAYOUT_CACHE
+ static TextLayoutCache mCache;
+#endif
};
}
diff --git a/core/jni/android/graphics/TextLayoutCache.cpp b/core/jni/android/graphics/TextLayoutCache.cpp
new file mode 100644
index 0000000..7888769
--- /dev/null
+++ b/core/jni/android/graphics/TextLayoutCache.cpp
@@ -0,0 +1,210 @@
+/*
+ * Copyright (C) 2011 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.
+ */
+
+#include "TextLayoutCache.h"
+
+namespace android {
+
+TextLayoutCache::TextLayoutCache():
+ mCache(GenerationCache<TextLayoutCacheKey, RunAdvanceDescription*>::kUnlimitedCapacity),
+ mSize(0), mMaxSize(MB(DEFAULT_TEXT_LAYOUT_CACHE_SIZE_IN_MB)),
+ mCacheHitCount(0), mNanosecondsSaved(0) {
+ init();
+}
+
+TextLayoutCache::TextLayoutCache(uint32_t max):
+ mCache(GenerationCache<TextLayoutCacheKey, RunAdvanceDescription*>::kUnlimitedCapacity),
+ mSize(0), mMaxSize(max),
+ mCacheHitCount(0), mNanosecondsSaved(0) {
+ init();
+}
+
+TextLayoutCache::~TextLayoutCache() {
+ mCache.clear();
+}
+
+void TextLayoutCache::init() {
+ mCache.setOnEntryRemovedListener(this);
+
+ mDebugLevel = readRtlDebugLevel();
+ mDebugEnabled = mDebugLevel & kRtlDebugCaches;
+ LOGD("Using TextLayoutCache debug level: %d - Debug Enabled: %d", mDebugLevel, mDebugEnabled);
+
+ mCacheStartTime = systemTime(SYSTEM_TIME_MONOTONIC);
+ if (mDebugEnabled) {
+ LOGD("TextLayoutCache start time: %lld", mCacheStartTime);
+ }
+
+ mInitialized = true;
+ if (mDebugEnabled) {
+ LOGD("TextLayoutCache initialization is done");
+ }
+}
+
+/*
+ * Size management
+ */
+
+uint32_t TextLayoutCache::getSize() {
+ return mSize;
+}
+
+uint32_t TextLayoutCache::getMaxSize() {
+ return mMaxSize;
+}
+
+void TextLayoutCache::setMaxSize(uint32_t maxSize) {
+ mMaxSize = maxSize;
+ removeOldests();
+}
+
+void TextLayoutCache::removeOldests() {
+ while (mSize > mMaxSize) {
+ mCache.removeOldest();
+ }
+}
+
+/**
+ * Callbacks
+ */
+void TextLayoutCache::operator()(TextLayoutCacheKey& text, RunAdvanceDescription*& desc) {
+ if (desc) {
+ size_t totalSizeToDelete = text.getSize() + desc->getSize();
+ mSize -= totalSizeToDelete;
+ if (mDebugEnabled) {
+ LOGD("RunAdvance description deleted, size = %d", totalSizeToDelete);
+ }
+ delete desc;
+ }
+}
+
+/*
+ * Cache clearing
+ */
+void TextLayoutCache::clear() {
+ mCache.clear();
+}
+
+/*
+ * Caching
+ */
+void TextLayoutCache::getRunAdvances(SkPaint* paint, const jchar* text,
+ jint start, jint count, jint contextCount, jint dirFlags,
+ jfloat* outAdvances, jfloat* outTotalAdvance) {
+
+ AutoMutex _l(mLock);
+
+ nsecs_t startTime = 0;
+ if (mDebugEnabled) {
+ startTime = systemTime(SYSTEM_TIME_MONOTONIC);
+ }
+
+ TextLayoutCacheKey entry(paint, text, start, count, contextCount, dirFlags);
+
+ // Get entry for cache if possible
+ RunAdvanceDescription* desc = mCache.get(entry);
+
+ // Value not found for the entry, we need to add a new value in the cache
+ if (!desc) {
+ desc = new RunAdvanceDescription();
+
+ // Compute advances and store them
+ desc->computeAdvances(paint, text, start, count, contextCount, dirFlags);
+ desc->copyResult(outAdvances, outTotalAdvance);
+
+ // Don't bother to add in the cache if the entry is too big
+ size_t size = entry.getSize() + desc->getSize();
+ if (size <= mMaxSize) {
+ // Cleanup to make some room if needed
+ if (mSize + size > mMaxSize) {
+ if (mDebugEnabled) {
+ LOGD("TextLayoutCache: need to clean some entries "
+ "for making some room for a new entry");
+ }
+ while (mSize + size > mMaxSize) {
+ // This will call the callback
+ mCache.removeOldest();
+ }
+ }
+
+ // Update current cache size
+ mSize += size;
+
+ // Copy the text when we insert the new entry
+ entry.internalTextCopy();
+ mCache.put(entry, desc);
+
+ if (mDebugEnabled) {
+ // Update timing information for statistics.
+ desc->setElapsedTime(systemTime(SYSTEM_TIME_MONOTONIC) - startTime);
+
+ LOGD("CACHE MISS: Added entry for text='%s' with start=%d, count=%d, "
+ "contextCount=%d, entry size %d bytes, remaining space %d bytes"
+ " - Compute time in nanos: %d",
+ String8(text, contextCount).string(), start, count, contextCount,
+ size, mMaxSize - mSize, desc->getElapsedTime());
+ }
+ } else {
+ if (mDebugEnabled) {
+ LOGD("CACHE MISS: Calculated but not storing entry because it is too big "
+ "for text='%s' with start=%d, count=%d, contextCount=%d, "
+ "entry size %d bytes, remaining space %d bytes"
+ " - Compute time in nanos: %d",
+ String8(text, contextCount).string(), start, count, contextCount,
+ size, mMaxSize - mSize, desc->getElapsedTime());
+ }
+ delete desc;
+ }
+ } else {
+ // This is a cache hit, just copy the pre-computed results
+ desc->copyResult(outAdvances, outTotalAdvance);
+ if (mDebugEnabled) {
+ nsecs_t elapsedTimeThruCacheGet = systemTime(SYSTEM_TIME_MONOTONIC) - startTime;
+ mNanosecondsSaved += (desc->getElapsedTime() - elapsedTimeThruCacheGet);
+ ++mCacheHitCount;
+
+ if (desc->getElapsedTime() > 0) {
+ float deltaPercent = 100 * ((desc->getElapsedTime() - elapsedTimeThruCacheGet)
+ / ((float)desc->getElapsedTime()));
+ LOGD("CACHE HIT #%d for text='%s' with start=%d, count=%d, contextCount=%d "
+ "- Compute time in nanos: %d - "
+ "Cache get time in nanos: %lld - Gain in percent: %2.2f",
+ mCacheHitCount, String8(text, contextCount).string(), start, count,
+ contextCount,
+ desc->getElapsedTime(), elapsedTimeThruCacheGet, deltaPercent);
+ }
+ if (mCacheHitCount % DEFAULT_DUMP_STATS_CACHE_HIT_INTERVAL == 0) {
+ dumpCacheStats();
+ }
+ }
+ }
+}
+
+void TextLayoutCache::dumpCacheStats() {
+ float remainingPercent = 100 * ((mMaxSize - mSize) / ((float)mMaxSize));
+ float timeRunningInSec = (systemTime(SYSTEM_TIME_MONOTONIC) - mCacheStartTime) / 1000000000;
+ LOGD("------------------------------------------------");
+ LOGD("TextLayoutCache stats");
+ LOGD("------------------------------------------------");
+ LOGD("running : %.0f seconds", timeRunningInSec);
+ LOGD("size : %d bytes", mMaxSize);
+ LOGD("remaining : %d bytes or %2.2f percent", mMaxSize - mSize, remainingPercent);
+ LOGD("hits : %d", mCacheHitCount);
+ LOGD("saved : %lld milliseconds", mNanosecondsSaved / 1000000);
+ LOGD("------------------------------------------------");
+}
+
+} // namespace android
diff --git a/core/jni/android/graphics/TextLayoutCache.h b/core/jni/android/graphics/TextLayoutCache.h
new file mode 100644
index 0000000..9d55918
--- /dev/null
+++ b/core/jni/android/graphics/TextLayoutCache.h
@@ -0,0 +1,314 @@
+/*
+ * Copyright (C) 2011 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.
+ */
+
+#ifndef ANDROID_TEXT_LAYOUT_CACHE_H
+#define ANDROID_TEXT_LAYOUT_CACHE_H
+
+#include "RtlProperties.h"
+
+#include "stddef.h"
+#include <utils/threads.h>
+#include <utils/String16.h>
+#include "utils/GenerationCache.h"
+#include "utils/Compare.h"
+
+#include "SkPaint.h"
+#include "SkTemplates.h"
+
+#include "unicode/ubidi.h"
+#include "unicode/ushape.h"
+
+#include <android_runtime/AndroidRuntime.h>
+
+#define UNICODE_NOT_A_CHAR 0xffff
+#define UNICODE_ZWSP 0x200b
+#define UNICODE_FIRST_LOW_SURROGATE 0xdc00
+#define UNICODE_FIRST_HIGH_SURROGATE 0xd800
+#define UNICODE_FIRST_PRIVATE_USE 0xe000
+#define UNICODE_FIRST_RTL_CHAR 0x0590
+
+// Temporary buffer size
+#define CHAR_BUFFER_SIZE 80
+
+// Converts a number of mega-bytes into bytes
+#define MB(s) s * 1024 * 1024
+
+// Define the default cache size in Mb
+#define DEFAULT_TEXT_LAYOUT_CACHE_SIZE_IN_MB 0.125f
+
+// Define the interval in number of cache hits between two statistics dump
+#define DEFAULT_DUMP_STATS_CACHE_HIT_INTERVAL 100
+
+namespace android {
+
+/**
+ * TextLayoutCacheKey is the Cache key
+ */
+class TextLayoutCacheKey {
+public:
+ TextLayoutCacheKey() : text(NULL), start(0), count(0), contextCount(0),
+ dirFlags(0), textSize(0), typeface(NULL), textSkewX(0), fakeBoldText(false) {
+ }
+
+ TextLayoutCacheKey(const SkPaint* paint,
+ const UChar* text, size_t start, size_t count,
+ size_t contextCount, int dirFlags) :
+ text(text), start(start), count(count), contextCount(contextCount),
+ dirFlags(dirFlags) {
+ textSize = paint->getTextSize();
+ typeface = paint->getTypeface();
+ textSkewX = paint->getTextSkewX();
+ fakeBoldText = paint->isFakeBoldText();
+ }
+
+ bool operator<(const TextLayoutCacheKey& rhs) const {
+ LTE_INT(count) {
+ LTE_INT(contextCount) {
+ LTE_INT(start) {
+ LTE_FLOAT(textSize) {
+ LTE_INT(typeface) {
+ LTE_INT(textSkewX) {
+ LTE_INT(fakeBoldText) {
+ LTE_INT(dirFlags) {
+ return strncmp16(text, rhs.text, contextCount) < 0;
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ return false;
+ }
+
+ // We need to copy the text when we insert the key into the cache itself.
+ // We don't need to copy the text when we are only comparing keys.
+ void internalTextCopy() {
+ textCopy.setTo(text, contextCount);
+ text = textCopy.string();
+ }
+
+ /**
+ * Get the size of the Cache key.
+ */
+ size_t getSize() {
+ return sizeof(TextLayoutCacheKey) + sizeof(UChar) * contextCount;
+ }
+
+private:
+ const UChar* text;
+ String16 textCopy;
+ size_t start;
+ size_t count;
+ size_t contextCount;
+ int dirFlags;
+ float textSize;
+ SkTypeface* typeface;
+ float textSkewX;
+ bool fakeBoldText;
+}; // TextLayoutCacheKey
+
+/*
+ * RunAdvanceDescription is the Cache entry
+ */
+class RunAdvanceDescription {
+public:
+ RunAdvanceDescription() {
+ advances = NULL;
+ totalAdvance = 0;
+ }
+
+ ~RunAdvanceDescription() {
+ delete[] advances;
+ }
+
+ void setElapsedTime(uint32_t time) {
+ elapsedTime = time;
+ }
+
+ uint32_t getElapsedTime() {
+ return elapsedTime;
+ }
+
+ void computeAdvances(SkPaint* paint, const UChar* chars, size_t start, size_t count,
+ size_t contextCount, int dirFlags) {
+ advances = new float[count];
+ this->count = count;
+
+ computeAdvances(paint, chars, start, count, contextCount, dirFlags,
+ advances, &totalAdvance);
+ }
+
+ void copyResult(jfloat* outAdvances, jfloat* outTotalAdvance) {
+ memcpy(outAdvances, advances, count * sizeof(jfloat));
+ *outTotalAdvance = totalAdvance;
+ }
+
+ /**
+ * Get the size of the Cache entry
+ */
+ size_t getSize() {
+ return sizeof(RunAdvanceDescription) + sizeof(jfloat) * count;
+ }
+
+ static void computeAdvances(SkPaint* paint, const UChar* chars, size_t start, size_t count,
+ size_t contextCount, int dirFlags, jfloat* outAdvances, jfloat* outTotalAdvance) {
+ SkAutoSTMalloc<CHAR_BUFFER_SIZE, jchar> tempBuffer(contextCount);
+ jchar* buffer = tempBuffer.get();
+
+ SkScalar* scalarArray = (SkScalar*)outAdvances;
+
+ // this is where we'd call harfbuzz
+ // for now we just use ushape.c
+ size_t widths;
+ const jchar* text;
+ if (dirFlags & 0x1) { // rtl, call arabic shaping in case
+ UErrorCode status = U_ZERO_ERROR;
+ // Use fixed length since we need to keep start and count valid
+ u_shapeArabic(chars, contextCount, buffer, contextCount,
+ U_SHAPE_LENGTH_FIXED_SPACES_NEAR |
+ U_SHAPE_TEXT_DIRECTION_LOGICAL | U_SHAPE_LETTERS_SHAPE |
+ U_SHAPE_X_LAMALEF_SUB_ALTERNATE, &status);
+ // we shouldn't fail unless there's an out of memory condition,
+ // in which case we're hosed anyway
+ for (int i = start, e = i + count; i < e; ++i) {
+ if (buffer[i] == UNICODE_NOT_A_CHAR) {
+ buffer[i] = UNICODE_ZWSP; // zero-width-space for skia
+ }
+ }
+ text = buffer + start;
+ widths = paint->getTextWidths(text, count << 1, scalarArray);
+ } else {
+ text = chars + start;
+ widths = paint->getTextWidths(text, count << 1, scalarArray);
+ }
+
+ jfloat totalAdvance = 0;
+ if (widths < count) {
+ // Skia operates on code points, not code units, so surrogate pairs return only
+ // one value. Expand the result so we have one value per UTF-16 code unit.
+
+ // Note, skia's getTextWidth gets confused if it encounters a surrogate pair,
+ // leaving the remaining widths zero. Not nice.
+ for (size_t i = 0, p = 0; i < widths; ++i) {
+ totalAdvance += outAdvances[p++] = SkScalarToFloat(scalarArray[i]);
+ if (p < count &&
+ text[p] >= UNICODE_FIRST_LOW_SURROGATE &&
+ text[p] < UNICODE_FIRST_PRIVATE_USE &&
+ text[p-1] >= UNICODE_FIRST_HIGH_SURROGATE &&
+ text[p-1] < UNICODE_FIRST_LOW_SURROGATE) {
+ outAdvances[p++] = 0;
+ }
+ }
+ } else {
+ for (size_t i = 0; i < count; i++) {
+ totalAdvance += outAdvances[i] = SkScalarToFloat(scalarArray[i]);
+ }
+ }
+ *outTotalAdvance = totalAdvance;
+ }
+
+private:
+ jfloat* advances;
+ jfloat totalAdvance;
+ size_t count;
+
+ uint32_t elapsedTime;
+}; // RunAdvanceDescription
+
+
+class TextLayoutCache: public OnEntryRemoved<TextLayoutCacheKey, RunAdvanceDescription*>
+{
+public:
+ TextLayoutCache();
+ TextLayoutCache(uint32_t maxByteSize);
+
+ virtual ~TextLayoutCache();
+
+ bool isInitialized() {
+ return mInitialized;
+ }
+
+ /**
+ * Used as a callback when an entry is removed from the cache.
+ * Do not invoke directly.
+ */
+ void operator()(TextLayoutCacheKey& text, RunAdvanceDescription*& desc);
+
+ /**
+ * Get cache entries
+ */
+ void getRunAdvances(SkPaint* paint, const jchar* text,
+ jint start, jint count, jint contextCount, jint dirFlags,
+ jfloat* outAdvances, jfloat* outTotalAdvance);
+
+ /**
+ * Clear the cache
+ */
+ void clear();
+
+ /**
+ * Sets the maximum size of the cache in bytes.
+ */
+ void setMaxSize(uint32_t maxSize);
+
+ /**
+ * Returns the maximum size of the cache in bytes.
+ */
+ uint32_t getMaxSize();
+
+ /**
+ * Returns the current size of the cache in bytes.
+ */
+ uint32_t getSize();
+
+private:
+ Mutex mLock;
+ bool mInitialized;
+
+ GenerationCache<TextLayoutCacheKey, RunAdvanceDescription*> mCache;
+
+ uint32_t mSize;
+ uint32_t mMaxSize;
+
+ uint32_t mCacheHitCount;
+ uint64_t mNanosecondsSaved;
+
+ uint64_t mCacheStartTime;
+
+ RtlDebugLevel mDebugLevel;
+ bool mDebugEnabled;
+
+ /*
+ * Class initialization
+ */
+ void init();
+
+ /**
+ * Remove oldest entries until we are having enough space
+ */
+ void removeOldests();
+
+ /**
+ * Dump Cache statistics
+ */
+ void dumpCacheStats();
+}; // TextLayoutCache
+
+} // namespace android
+#endif /* ANDROID_TEXT_LAYOUT_CACHE_H */
+
diff --git a/include/utils/GenerationCache.h b/include/utils/GenerationCache.h
new file mode 100644
index 0000000..bb9ddd6
--- /dev/null
+++ b/include/utils/GenerationCache.h
@@ -0,0 +1,255 @@
+/*
+ * 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.
+ */
+
+#ifndef ANDROID_UTILS_GENERATION_CACHE_H
+#define ANDROID_UTILS_GENERATION_CACHE_H
+
+#include <utils/KeyedVector.h>
+#include <utils/RefBase.h>
+
+namespace android {
+
+/**
+ * GenerationCache callback used when an item is removed
+ */
+template<typename EntryKey, typename EntryValue>
+class OnEntryRemoved {
+public:
+ virtual ~OnEntryRemoved() { };
+ virtual void operator()(EntryKey& key, EntryValue& value) = 0;
+}; // class OnEntryRemoved
+
+template<typename EntryKey, typename EntryValue>
+struct Entry: public LightRefBase<Entry<EntryKey, EntryValue> > {
+ Entry() { }
+ Entry(const Entry<EntryKey, EntryValue>& e):
+ key(e.key), value(e.value), parent(e.parent), child(e.child) { }
+ Entry(sp<Entry<EntryKey, EntryValue> > e):
+ key(e->key), value(e->value), parent(e->parent), child(e->child) { }
+
+ EntryKey key;
+ EntryValue value;
+
+ sp<Entry<EntryKey, EntryValue> > parent;
+ sp<Entry<EntryKey, EntryValue> > child;
+}; // struct Entry
+
+/**
+ * A LRU type cache
+ */
+template<typename K, typename V>
+class GenerationCache {
+public:
+ GenerationCache(uint32_t maxCapacity);
+ virtual ~GenerationCache();
+
+ enum Capacity {
+ kUnlimitedCapacity,
+ };
+
+ void setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener);
+
+ void clear();
+
+ bool contains(K key) const;
+ V get(K key);
+ K getKeyAt(uint32_t index) const;
+ bool put(K key, V value);
+ V remove(K key);
+ V removeOldest();
+ V getValueAt(uint32_t index) const;
+
+ uint32_t size() const;
+
+ void addToCache(sp<Entry<K, V> > entry, K key, V value);
+ void attachToCache(sp<Entry<K, V> > entry);
+ void detachFromCache(sp<Entry<K, V> > entry);
+
+ V removeAt(ssize_t index);
+
+private:
+ KeyedVector<K, sp<Entry<K, V> > > mCache;
+ uint32_t mMaxCapacity;
+
+ OnEntryRemoved<K, V>* mListener;
+
+ sp<Entry<K, V> > mOldest;
+ sp<Entry<K, V> > mYoungest;
+}; // class GenerationCache
+
+template<typename K, typename V>
+GenerationCache<K, V>::GenerationCache(uint32_t maxCapacity): mMaxCapacity(maxCapacity),
+ mListener(NULL) {
+};
+
+template<typename K, typename V>
+GenerationCache<K, V>::~GenerationCache() {
+ clear();
+};
+
+template<typename K, typename V>
+uint32_t GenerationCache<K, V>::size() const {
+ return mCache.size();
+}
+
+/**
+ * Should be set by the user of the Cache so that the callback is called whenever an item is
+ * removed from the cache
+ */
+template<typename K, typename V>
+void GenerationCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
+ mListener = listener;
+}
+
+template<typename K, typename V>
+void GenerationCache<K, V>::clear() {
+ if (mListener) {
+ for (uint32_t i = 0; i < mCache.size(); i++) {
+ sp<Entry<K, V> > entry = mCache.valueAt(i);
+ if (mListener) {
+ (*mListener)(entry->key, entry->value);
+ }
+ }
+ }
+ mCache.clear();
+ mYoungest.clear();
+ mOldest.clear();
+}
+
+template<typename K, typename V>
+bool GenerationCache<K, V>::contains(K key) const {
+ return mCache.indexOfKey(key) >= 0;
+}
+
+template<typename K, typename V>
+K GenerationCache<K, V>::getKeyAt(uint32_t index) const {
+ return mCache.keyAt(index);
+}
+
+template<typename K, typename V>
+V GenerationCache<K, V>::getValueAt(uint32_t index) const {
+ return mCache.valueAt(index)->value;
+}
+
+template<typename K, typename V>
+V GenerationCache<K, V>::get(K key) {
+ ssize_t index = mCache.indexOfKey(key);
+ if (index >= 0) {
+ sp<Entry<K, V> > entry = mCache.valueAt(index);
+ if (entry.get()) {
+ detachFromCache(entry);
+ attachToCache(entry);
+ return entry->value;
+ }
+ }
+
+ return NULL;
+}
+
+template<typename K, typename V>
+bool GenerationCache<K, V>::put(K key, V value) {
+ if (mMaxCapacity != kUnlimitedCapacity && mCache.size() >= mMaxCapacity) {
+ removeOldest();
+ }
+
+ ssize_t index = mCache.indexOfKey(key);
+ if (index < 0) {
+ sp<Entry<K, V> > entry = new Entry<K, V>;
+ addToCache(entry, key, value);
+ return true;
+ }
+
+ return false;
+}
+
+template<typename K, typename V>
+void GenerationCache<K, V>::addToCache(sp<Entry<K, V> > entry, K key, V value) {
+ entry->key = key;
+ entry->value = value;
+ mCache.add(key, entry);
+ attachToCache(entry);
+}
+
+template<typename K, typename V>
+V GenerationCache<K, V>::remove(K key) {
+ ssize_t index = mCache.indexOfKey(key);
+ if (index >= 0) {
+ return removeAt(index);
+ }
+
+ return NULL;
+}
+
+template<typename K, typename V>
+V GenerationCache<K, V>::removeAt(ssize_t index) {
+ sp<Entry<K, V> > entry = mCache.valueAt(index);
+ if (mListener) {
+ (*mListener)(entry->key, entry->value);
+ }
+ mCache.removeItemsAt(index, 1);
+ detachFromCache(entry);
+
+ return entry->value;
+}
+
+template<typename K, typename V>
+V GenerationCache<K, V>::removeOldest() {
+ if (mOldest.get()) {
+ ssize_t index = mCache.indexOfKey(mOldest->key);
+ if (index >= 0) {
+ return removeAt(index);
+ }
+ }
+
+ return NULL;
+}
+
+template<typename K, typename V>
+void GenerationCache<K, V>::attachToCache(sp<Entry<K, V> > entry) {
+ if (!mYoungest.get()) {
+ mYoungest = mOldest = entry;
+ } else {
+ entry->parent = mYoungest;
+ mYoungest->child = entry;
+ mYoungest = entry;
+ }
+}
+
+template<typename K, typename V>
+void GenerationCache<K, V>::detachFromCache(sp<Entry<K, V> > entry) {
+ if (entry->parent.get()) {
+ entry->parent->child = entry->child;
+ }
+
+ if (entry->child.get()) {
+ entry->child->parent = entry->parent;
+ }
+
+ if (mOldest == entry) {
+ mOldest = entry->child;
+ }
+
+ if (mYoungest == entry) {
+ mYoungest = entry->parent;
+ }
+
+ entry->parent.clear();
+ entry->child.clear();
+}
+
+}; // namespace android
+
+#endif // ANDROID_UTILS_GENERATION_CACHE_H