Revert "Revert "Rewrite ImageWriter's merging of String char[]s.""

This reverts commit 4c964de8832551b701ce7b3162bc51cc6b22fc8a.

Change-Id: I940bdf48e2dbaef0f809beda32756507d18acb89

1 files changed, 55 insertions, 76 deletions

diff --git a/compiler/image_writer.cc b/compiler/image_writer.cc
index ab5c6c7..a45c2d1 100644
--- a/compiler/image_writer.cc
+++ b/compiler/image_writer.cc
@@ -480,34 +480,29 @@ class StringCollector {
 };
 
 // Compare strings based on length, used for sorting strings by length / reverse length.
-class StringLengthComparator {
+class LexicographicalStringComparator {
  public:
-  explicit StringLengthComparator(Handle<mirror::ObjectArray<mirror::String>> strings)
-      : strings_(strings) {
+  bool operator()(const mirror::HeapReference<mirror::String>& lhs,
+                  const mirror::HeapReference<mirror::String>& rhs) const
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    mirror::String* lhs_s = lhs.AsMirrorPtr();
+    mirror::String* rhs_s = rhs.AsMirrorPtr();
+    uint16_t* lhs_begin = lhs_s->GetCharArray()->GetData() + lhs_s->GetOffset();
+    uint16_t* rhs_begin = rhs_s->GetCharArray()->GetData() + rhs_s->GetOffset();
+    return std::lexicographical_compare(lhs_begin, lhs_begin + lhs_s->GetLength(),
+                                        rhs_begin, rhs_begin + rhs_s->GetLength());
   }
-  bool operator()(size_t a, size_t b) const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
-    return strings_->GetWithoutChecks(a)->GetLength() < strings_->GetWithoutChecks(b)->GetLength();
-  }
-
- private:
-  Handle<mirror::ObjectArray<mirror::String>> strings_;
 };
 
-// Normal string < comparison through the chars_ array.
-class SubstringComparator {
- public:
-  explicit SubstringComparator(const std::vector<uint16_t>* const chars) : chars_(chars) {
-  }
-  bool operator()(const std::pair<size_t, size_t>& a, const std::pair<size_t, size_t>& b) {
-    return std::lexicographical_compare(chars_->begin() + a.first,
-                                        chars_->begin() + a.first + a.second,
-                                        chars_->begin() + b.first,
-                                        chars_->begin() + b.first + b.second);
+static bool IsPrefix(mirror::String* pref, mirror::String* full)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  if (pref->GetLength() > full->GetLength()) {
+    return false;
   }
-
- private:
-  const std::vector<uint16_t>* const chars_;
-};
+  uint16_t* pref_begin = pref->GetCharArray()->GetData() + pref->GetOffset();
+  uint16_t* full_begin = full->GetCharArray()->GetData() + full->GetOffset();
+  return std::equal(pref_begin, pref_begin + pref->GetLength(), full_begin);
+}
 
 void ImageWriter::ProcessStrings() {
   size_t total_strings = 0;
@@ -529,67 +524,51 @@ void ImageWriter::ProcessStrings() {
   // Some strings could have gotten freed if AllocStringArray caused a GC.
   CHECK_LE(string_collector.GetIndex(), total_strings);
   total_strings = string_collector.GetIndex();
-  size_t total_length = 0;
-  std::vector<size_t> reverse_sorted_strings;
-  for (size_t i = 0; i < total_strings; ++i) {
-    mirror::String* s = strings->GetWithoutChecks(i);
-    // Look up the string in the array.
-    total_length += s->GetLength();
-    reverse_sorted_strings.push_back(i);
-  }
-  // Sort by reverse length.
-  StringLengthComparator comparator(strings);
-  std::sort(reverse_sorted_strings.rbegin(), reverse_sorted_strings.rend(), comparator);
-  // Deduplicate prefixes and add strings to the char array.
-  std::vector<uint16_t> combined_chars(total_length, 0U);
-  size_t num_chars = 0;
+  auto* strings_begin = reinterpret_cast<mirror::HeapReference<mirror::String>*>(
+          strings->GetRawData(sizeof(mirror::HeapReference<mirror::String>), 0));
+  std::sort(strings_begin, strings_begin + total_strings, LexicographicalStringComparator());
   // Characters of strings which are non equal prefix of another string (not the same string).
   // We don't count the savings from equal strings since these would get interned later anyways.
   size_t prefix_saved_chars = 0;
-  std::set<std::pair<size_t, size_t>, SubstringComparator> existing_strings((
-      SubstringComparator(&combined_chars)));
-  for (size_t i = 0; i < total_strings; ++i) {
-    mirror::String* s = strings->GetWithoutChecks(reverse_sorted_strings[i]);
-    // Add the string to the end of the char array.
+  // Count characters needed for the strings.
+  size_t num_chars = 0u;
+  mirror::String* prev_s = nullptr;
+  for (size_t idx = 0; idx != total_strings; ++idx) {
+    mirror::String* s = strings->GetWithoutChecks(idx);
     size_t length = s->GetLength();
-    for (size_t j = 0; j < length; ++j) {
-      combined_chars[num_chars++] = s->CharAt(j);
-    }
-    // Try to see if the string exists as a prefix of an existing string.
-    size_t new_offset = 0;
-    std::pair<size_t, size_t> new_string(num_chars - length, length);
-    auto it = existing_strings.lower_bound(new_string);
-    bool is_prefix = false;
-    if (it != existing_strings.end()) {
-      CHECK_LE(length, it->second);
-      is_prefix = std::equal(combined_chars.begin() + new_string.first,
-                             combined_chars.begin() + new_string.first + new_string.second,
-                             combined_chars.begin() + it->first);
-    }
-    if (is_prefix) {
-      // Shares a prefix, set the offset to where the new offset will be.
-      new_offset = it->first;
-      // Remove the added chars.
-      num_chars -= length;
-      if (it->second != length) {
-        prefix_saved_chars += length;
+    num_chars += length;
+    if (prev_s != nullptr && IsPrefix(prev_s, s)) {
+      size_t prev_length = prev_s->GetLength();
+      num_chars -= prev_length;
+      if (prev_length != length) {
+        prefix_saved_chars += prev_length;
       }
-    } else {
-      new_offset = new_string.first;
-      existing_strings.insert(new_string);
     }
-    s->SetOffset(new_offset);
-  }
-  // Allocate and update the char arrays.
-  auto* array = mirror::CharArray::Alloc(self, num_chars);
-  for (size_t i = 0; i < num_chars; ++i) {
-    array->SetWithoutChecks<false>(i, combined_chars[i]);
-  }
-  for (size_t i = 0; i < total_strings; ++i) {
-    strings->GetWithoutChecks(i)->SetArray(array);
+    prev_s = s;
+  }
+  // Create character array, copy characters and point the strings there.
+  mirror::CharArray* array = mirror::CharArray::Alloc(self, num_chars);
+  uint16_t* array_data = array->GetData();
+  size_t pos = 0u;
+  prev_s = nullptr;
+  for (size_t idx = 0; idx != total_strings; ++idx) {
+    mirror::String* s = strings->GetWithoutChecks(idx);
+    uint16_t* s_data = s->GetCharArray()->GetData() + s->GetOffset();
+    int32_t s_length = s->GetLength();
+    int32_t prefix_length = 0u;
+    if (idx != 0u && IsPrefix(prev_s, s)) {
+      prefix_length = prev_s->GetLength();
+    }
+    memcpy(array_data + pos, s_data + prefix_length, (s_length - prefix_length) * sizeof(*s_data));
+    s->SetOffset(pos - prefix_length);
+    s->SetArray(array);
+    pos += s_length - prefix_length;
+    prev_s = s;
   }
+  CHECK_EQ(pos, num_chars);
+
   LOG(INFO) << "Total # image strings=" << total_strings << " combined length="
-      << total_length << " prefix saved chars=" << prefix_saved_chars;
+      << num_chars << " prefix saved chars=" << prefix_saved_chars;
   ComputeEagerResolvedStrings();
 }