Fix InternTable::Lookup()/Remove() for hash code collisions.

When we have a hash code collision but the string is not yet
in the intern table, the old Lookup() would iterate until
the end of the table, i.e. it was up to linear in the size
of the table rather than linear in the number of colliding
hash codes.

And though the multimap::find() is implemented in terms of
lower_bound() in the standard library we're using, this
requirement doesn't seem to be in the C++ standard. It was
therefore wrong to assume that we will iterate across all
hits when starting from the iterator returned by find().

Change-Id: Ie24aaea6e55750a7aafbed24b136878c5dba66eb

1 files changed, 4 insertions, 2 deletions

diff --git a/runtime/intern_table.cc b/runtime/intern_table.cc
index 817d104..339eb36 100644
--- a/runtime/intern_table.cc
+++ b/runtime/intern_table.cc
@@ -84,7 +84,8 @@ void InternTable::VisitRoots(RootCallback* callback, void* arg, VisitRootFlags f
 
 mirror::String* InternTable::Lookup(Table& table, mirror::String* s, int32_t hash_code) {
   Locks::intern_table_lock_->AssertHeld(Thread::Current());
-  for (auto it = table.find(hash_code), end = table.end(); it != end; ++it) {
+  for (auto it = table.lower_bound(hash_code), end = table.end();
+       it != end && it->first == hash_code; ++it) {
     mirror::String* existing_string = it->second;
     if (existing_string->Equals(s)) {
       return existing_string;
@@ -123,7 +124,8 @@ void InternTable::RemoveWeak(mirror::String* s, int32_t hash_code) {
 }
 
 void InternTable::Remove(Table& table, mirror::String* s, int32_t hash_code) {
-  for (auto it = table.find(hash_code), end = table.end(); it != end; ++it) {
+  for (auto it = table.lower_bound(hash_code), end = table.end();
+       it != end && it->first == hash_code; ++it) {
     if (it->second == s) {
       table.erase(it);
       return;