//
#include "StringPool.h"
+#include "ResourceTable.h"
#include <utils/ByteOrder.h>
+#include <utils/SortedVector.h>
+#include <cutils/qsort_r_compat.h>
+
+#if HAVE_PRINTF_ZD
+# define ZD "%zd"
+# define ZD_TYPE ssize_t
+#else
+# define ZD "%ld"
+# define ZD_TYPE long
+#endif
#define NOISY(x) //x
void printStringPool(const ResStringPool* pool)
{
+ SortedVector<const void*> uniqueStrings;
+ const size_t N = pool->size();
+ for (size_t i=0; i<N; i++) {
+ size_t len;
+ if (pool->isUTF8()) {
+ uniqueStrings.add(pool->string8At(i, &len));
+ } else {
+ uniqueStrings.add(pool->stringAt(i, &len));
+ }
+ }
+
+ printf("String pool of " ZD " unique %s %s strings, " ZD " entries and "
+ ZD " styles using " ZD " bytes:\n",
+ (ZD_TYPE)uniqueStrings.size(), pool->isUTF8() ? "UTF-8" : "UTF-16",
+ pool->isSorted() ? "sorted" : "non-sorted",
+ (ZD_TYPE)N, (ZD_TYPE)pool->styleCount(), (ZD_TYPE)pool->bytes());
+
const size_t NS = pool->size();
for (size_t s=0; s<NS; s++) {
- size_t len;
- printf("String #%d: %s\n", s,
- String8(pool->stringAt(s, &len)).string());
+ String8 str = pool->string8ObjectAt(s);
+ printf("String #" ZD ": %s\n", (ZD_TYPE) s, str.string());
}
}
-StringPool::StringPool(bool sorted)
- : mSorted(sorted), mValues(-1), mIdents(-1)
-{
+String8 StringPool::entry::makeConfigsString() const {
+ String8 configStr(configTypeName);
+ if (configStr.size() > 0) configStr.append(" ");
+ if (configs.size() > 0) {
+ for (size_t j=0; j<configs.size(); j++) {
+ if (j > 0) configStr.append(", ");
+ configStr.append(configs[j].toString());
+ }
+ } else {
+ configStr = "(none)";
+ }
+ return configStr;
+}
+
+int StringPool::entry::compare(const entry& o) const {
+ // Strings with styles go first, to reduce the size of the styles array.
+ // We don't care about the relative order of these strings.
+ if (hasStyles) {
+ return o.hasStyles ? 0 : -1;
+ }
+ if (o.hasStyles) {
+ return 1;
+ }
+
+ // Sort unstyled strings by type, then by logical configuration.
+ int comp = configTypeName.compare(o.configTypeName);
+ if (comp != 0) {
+ return comp;
+ }
+ const size_t LHN = configs.size();
+ const size_t RHN = o.configs.size();
+ size_t i=0;
+ while (i < LHN && i < RHN) {
+ comp = configs[i].compareLogical(o.configs[i]);
+ if (comp != 0) {
+ return comp;
+ }
+ i++;
+ }
+ if (LHN < RHN) return -1;
+ else if (LHN > RHN) return 1;
+ return 0;
}
-ssize_t StringPool::add(const String16& value, bool mergeDuplicates)
+StringPool::StringPool(bool utf8) :
+ mUTF8(utf8), mValues(-1)
{
- return add(String16(), value, mergeDuplicates);
}
-ssize_t StringPool::add(const String16& value, const Vector<entry_style_span>& spans)
+ssize_t StringPool::add(const String16& value, const Vector<entry_style_span>& spans,
+ const String8* configTypeName, const ResTable_config* config)
{
- ssize_t res = add(String16(), value, false);
+ ssize_t res = add(value, false, configTypeName, config);
if (res >= 0) {
addStyleSpans(res, spans);
}
return res;
}
-ssize_t StringPool::add(const String16& ident, const String16& value,
- bool mergeDuplicates)
+ssize_t StringPool::add(const String16& value,
+ bool mergeDuplicates, const String8* configTypeName, const ResTable_config* config)
{
- if (ident.size() > 0) {
- ssize_t idx = mIdents.valueFor(ident);
- if (idx >= 0) {
- fprintf(stderr, "ERROR: Duplicate string identifier %s\n",
- String8(mEntries[idx].value).string());
- return UNKNOWN_ERROR;
- }
- }
-
ssize_t vidx = mValues.indexOfKey(value);
ssize_t pos = vidx >= 0 ? mValues.valueAt(vidx) : -1;
ssize_t eidx = pos >= 0 ? mEntryArray.itemAt(pos) : -1;
}
}
- const bool first = vidx < 0;
- if (first || !mergeDuplicates) {
- pos = mEntryArray.add(eidx);
- if (first) {
- vidx = mValues.add(value, pos);
- const size_t N = mEntryArrayToValues.size();
- for (size_t i=0; i<N; i++) {
- size_t& e = mEntryArrayToValues.editItemAt(i);
- if ((ssize_t)e >= vidx) {
- e++;
+ if (configTypeName != NULL) {
+ entry& ent = mEntries.editItemAt(eidx);
+ NOISY(printf("*** adding config type name %s, was %s\n",
+ configTypeName->string(), ent.configTypeName.string()));
+ if (ent.configTypeName.size() <= 0) {
+ ent.configTypeName = *configTypeName;
+ } else if (ent.configTypeName != *configTypeName) {
+ ent.configTypeName = " ";
+ }
+ }
+
+ if (config != NULL) {
+ // Add this to the set of configs associated with the string.
+ entry& ent = mEntries.editItemAt(eidx);
+ size_t addPos;
+ for (addPos=0; addPos<ent.configs.size(); addPos++) {
+ int cmp = ent.configs.itemAt(addPos).compareLogical(*config);
+ if (cmp >= 0) {
+ if (cmp > 0) {
+ NOISY(printf("*** inserting config: %s\n", config->toString().string()));
+ ent.configs.insertAt(*config, addPos);
}
+ break;
}
}
- mEntryArrayToValues.add(vidx);
- if (!mSorted) {
- entry& ent = mEntries.editItemAt(eidx);
- ent.indices.add(pos);
+ if (addPos >= ent.configs.size()) {
+ NOISY(printf("*** adding config: %s\n", config->toString().string()));
+ ent.configs.add(*config);
}
}
- if (ident.size() > 0) {
- mIdents.add(ident, vidx);
+ const bool first = vidx < 0;
+ const bool styled = (pos >= 0 && (size_t)pos < mEntryStyleArray.size()) ?
+ mEntryStyleArray[pos].spans.size() : 0;
+ if (first || styled || !mergeDuplicates) {
+ pos = mEntryArray.add(eidx);
+ if (first) {
+ vidx = mValues.add(value, pos);
+ }
+ entry& ent = mEntries.editItemAt(eidx);
+ ent.indices.add(pos);
}
NOISY(printf("Adding string %s to pool: pos=%d eidx=%d vidx=%d\n",
status_t StringPool::addStyleSpan(size_t idx, const entry_style_span& span)
{
- LOG_ALWAYS_FATAL_IF(mSorted, "Can't use styles with sorted string pools.");
-
// Place blank entries in the span array up to this index.
while (mEntryStyleArray.size() <= idx) {
mEntryStyleArray.add();
entry_style& style = mEntryStyleArray.editItemAt(idx);
style.spans.add(span);
+ mEntries.editItemAt(mEntryArray[idx]).hasStyles = true;
return NO_ERROR;
}
-size_t StringPool::size() const
+int StringPool::config_sort(void* state, const void* lhs, const void* rhs)
{
- return mSorted ? mValues.size() : mEntryArray.size();
+ StringPool* pool = (StringPool*)state;
+ const entry& lhe = pool->mEntries[pool->mEntryArray[*static_cast<const size_t*>(lhs)]];
+ const entry& rhe = pool->mEntries[pool->mEntryArray[*static_cast<const size_t*>(rhs)]];
+ return lhe.compare(rhe);
}
-const StringPool::entry& StringPool::entryAt(size_t idx) const
+void StringPool::sortByConfig()
{
- if (!mSorted) {
- return mEntries[mEntryArray[idx]];
- } else {
- return mEntries[mEntryArray[mValues.valueAt(idx)]];
+ LOG_ALWAYS_FATAL_IF(mOriginalPosToNewPos.size() > 0, "Can't sort string pool after already sorted.");
+
+ const size_t N = mEntryArray.size();
+
+ // This is a vector that starts out with a 1:1 mapping to entries
+ // in the array, which we will sort to come up with the desired order.
+ // At that point it maps from the new position in the array to the
+ // original position the entry appeared.
+ Vector<size_t> newPosToOriginalPos;
+ newPosToOriginalPos.setCapacity(N);
+ for (size_t i=0; i < N; i++) {
+ newPosToOriginalPos.add(i);
}
-}
-size_t StringPool::countIdentifiers() const
-{
- return mIdents.size();
+ // Sort the array.
+ NOISY(printf("SORTING STRINGS BY CONFIGURATION...\n"));
+ // Vector::sort uses insertion sort, which is very slow for this data set.
+ // Use quicksort instead because we don't need a stable sort here.
+ qsort_r_compat(newPosToOriginalPos.editArray(), N, sizeof(size_t), this, config_sort);
+ //newPosToOriginalPos.sort(config_sort, this);
+ NOISY(printf("DONE SORTING STRINGS BY CONFIGURATION.\n"));
+
+ // Create the reverse mapping from the original position in the array
+ // to the new position where it appears in the sorted array. This is
+ // so that clients can re-map any positions they had previously stored.
+ mOriginalPosToNewPos = newPosToOriginalPos;
+ for (size_t i=0; i<N; i++) {
+ mOriginalPosToNewPos.editItemAt(newPosToOriginalPos[i]) = i;
+ }
+
+#if 0
+ SortedVector<entry> entries;
+
+ for (size_t i=0; i<N; i++) {
+ printf("#%d was %d: %s\n", i, newPosToOriginalPos[i],
+ mEntries[mEntryArray[newPosToOriginalPos[i]]].makeConfigsString().string());
+ entries.add(mEntries[mEntryArray[i]]);
+ }
+
+ for (size_t i=0; i<entries.size(); i++) {
+ printf("Sorted config #%d: %s\n", i,
+ entries[i].makeConfigsString().string());
+ }
+#endif
+
+ // Now we rebuild the arrays.
+ Vector<entry> newEntries;
+ Vector<size_t> newEntryArray;
+ Vector<entry_style> newEntryStyleArray;
+ DefaultKeyedVector<size_t, size_t> origOffsetToNewOffset;
+
+ for (size_t i=0; i<N; i++) {
+ // We are filling in new offset 'i'; oldI is where we can find it
+ // in the original data structure.
+ size_t oldI = newPosToOriginalPos[i];
+ // This is the actual entry associated with the old offset.
+ const entry& oldEnt = mEntries[mEntryArray[oldI]];
+ // This is the same entry the last time we added it to the
+ // new entry array, if any.
+ ssize_t newIndexOfOffset = origOffsetToNewOffset.indexOfKey(oldI);
+ size_t newOffset;
+ if (newIndexOfOffset < 0) {
+ // This is the first time we have seen the entry, so add
+ // it.
+ newOffset = newEntries.add(oldEnt);
+ newEntries.editItemAt(newOffset).indices.clear();
+ } else {
+ // We have seen this entry before, use the existing one
+ // instead of adding it again.
+ newOffset = origOffsetToNewOffset.valueAt(newIndexOfOffset);
+ }
+ // Update the indices to include this new position.
+ newEntries.editItemAt(newOffset).indices.add(i);
+ // And add the offset of the entry to the new entry array.
+ newEntryArray.add(newOffset);
+ // Add any old style to the new style array.
+ if (mEntryStyleArray.size() > 0) {
+ if (oldI < mEntryStyleArray.size()) {
+ newEntryStyleArray.add(mEntryStyleArray[oldI]);
+ } else {
+ newEntryStyleArray.add(entry_style());
+ }
+ }
+ }
+
+ // Now trim any entries at the end of the new style array that are
+ // not needed.
+ for (ssize_t i=newEntryStyleArray.size()-1; i>=0; i--) {
+ const entry_style& style = newEntryStyleArray[i];
+ if (style.spans.size() > 0) {
+ // That's it.
+ break;
+ }
+ // This one is not needed; remove.
+ newEntryStyleArray.removeAt(i);
+ }
+
+ // All done, install the new data structures and upate mValues with
+ // the new positions.
+ mEntries = newEntries;
+ mEntryArray = newEntryArray;
+ mEntryStyleArray = newEntryStyleArray;
+ mValues.clear();
+ for (size_t i=0; i<mEntries.size(); i++) {
+ const entry& ent = mEntries[i];
+ mValues.add(ent.value, ent.indices[0]);
+ }
+
+#if 0
+ printf("FINAL SORTED STRING CONFIGS:\n");
+ for (size_t i=0; i<mEntries.size(); i++) {
+ const entry& ent = mEntries[i];
+ printf("#" ZD " %s: %s\n", (ZD_TYPE)i, ent.makeConfigsString().string(),
+ String8(ent.value).string());
+ }
+#endif
}
sp<AaptFile> StringPool::createStringBlock()
return err == NO_ERROR ? pool : NULL;
}
+#define ENCODE_LENGTH(str, chrsz, strSize) \
+{ \
+ size_t maxMask = 1 << ((chrsz*8)-1); \
+ size_t maxSize = maxMask-1; \
+ if (strSize > maxSize) { \
+ *str++ = maxMask | ((strSize>>(chrsz*8))&maxSize); \
+ } \
+ *str++ = strSize; \
+}
+
status_t StringPool::writeStringBlock(const sp<AaptFile>& pool)
{
// Allow appending. Sorry this is a little wacky.
}
}
- const size_t ENTRIES = size();
+ const size_t ENTRIES = mEntryArray.size();
// Now build the pool of unique strings.
return NO_MEMORY;
}
+ const size_t charSize = mUTF8 ? sizeof(uint8_t) : sizeof(char16_t);
+
size_t strPos = 0;
for (i=0; i<STRINGS; i++) {
entry& ent = mEntries.editItemAt(i);
const size_t strSize = (ent.value.size());
- const size_t lenSize = strSize > 0x7fff ? sizeof(uint32_t) : sizeof(uint16_t);
- const size_t totalSize = lenSize + ((strSize+1)*sizeof(uint16_t));
+ const size_t lenSize = strSize > (size_t)(1<<((charSize*8)-1))-1 ?
+ charSize*2 : charSize;
+
+ String8 encStr;
+ if (mUTF8) {
+ encStr = String8(ent.value);
+ }
+
+ const size_t encSize = mUTF8 ? encStr.size() : 0;
+ const size_t encLenSize = mUTF8 ?
+ (encSize > (size_t)(1<<((charSize*8)-1))-1 ?
+ charSize*2 : charSize) : 0;
ent.offset = strPos;
- uint16_t* dat = (uint16_t*)pool->editData(preSize + strPos + totalSize);
+
+ const size_t totalSize = lenSize + encLenSize +
+ ((mUTF8 ? encSize : strSize)+1)*charSize;
+
+ void* dat = (void*)pool->editData(preSize + strPos + totalSize);
if (dat == NULL) {
fprintf(stderr, "ERROR: Out of memory for string pool\n");
return NO_MEMORY;
}
- dat += (preSize+strPos)/sizeof(uint16_t);
- if (lenSize > sizeof(uint16_t)) {
- *dat = htods(0x8000 | ((strSize>>16)&0x7fff));
- dat++;
+ dat = (uint8_t*)dat + preSize + strPos;
+ if (mUTF8) {
+ uint8_t* strings = (uint8_t*)dat;
+
+ ENCODE_LENGTH(strings, sizeof(uint8_t), strSize)
+
+ ENCODE_LENGTH(strings, sizeof(uint8_t), encSize)
+
+ strncpy((char*)strings, encStr, encSize+1);
+ } else {
+ uint16_t* strings = (uint16_t*)dat;
+
+ ENCODE_LENGTH(strings, sizeof(uint16_t), strSize)
+
+ strcpy16_htod(strings, ent.value);
}
- *dat++ = htods(strSize);
- strcpy16_htod(dat, ent.value);
- strPos += lenSize + (strSize+1)*sizeof(uint16_t);
+ strPos += totalSize;
}
// Pad ending string position up to a uint32_t boundary.
header->header.size = htodl(pool->getSize());
header->stringCount = htodl(ENTRIES);
header->styleCount = htodl(STYLES);
- if (mSorted) {
- header->flags |= htodl(ResStringPool_header::SORTED_FLAG);
+ if (mUTF8) {
+ header->flags |= htodl(ResStringPool_header::UTF8_FLAG);
}
header->stringsStart = htodl(preSize);
header->stylesStart = htodl(STYLES > 0 ? (preSize+strPos) : 0);
// Write string index array.
uint32_t* index = (uint32_t*)(header+1);
- if (mSorted) {
- for (i=0; i<ENTRIES; i++) {
- entry& ent = const_cast<entry&>(entryAt(i));
- ent.indices.clear();
- ent.indices.add(i);
- *index++ = htodl(ent.offset);
- }
- } else {
- for (i=0; i<ENTRIES; i++) {
- entry& ent = mEntries.editItemAt(mEntryArray[i]);
- *index++ = htodl(ent.offset);
- NOISY(printf("Writing entry #%d: \"%s\" ent=%d off=%d\n", i,
- String8(ent.value).string(),
- mEntryArray[i], ent.offset));
- }
+ for (i=0; i<ENTRIES; i++) {
+ entry& ent = mEntries.editItemAt(mEntryArray[i]);
+ *index++ = htodl(ent.offset);
+ NOISY(printf("Writing entry #%d: \"%s\" ent=%d off=%d\n", i,
+ String8(ent.value).string(),
+ mEntryArray[i], ent.offset));
}
// Write style index array.
- if (mSorted) {
- for (i=0; i<STYLES; i++) {
- LOG_ALWAYS_FATAL("Shouldn't be here!");
- }
- } else {
- for (i=0; i<STYLES; i++) {
- *index++ = htodl(mEntryStyleArray[i].offset);
- }
+ for (i=0; i<STYLES; i++) {
+ *index++ = htodl(mEntryStyleArray[i].offset);
}
return NO_ERROR;
projects / android / aapt.git / blobdiff