OSDN Git Service

Fix InternTable::Lookup()/Remove() for hash code collisions.
authorVladimir Marko <vmarko@google.com>
Thu, 22 May 2014 11:16:44 +0000 (12:16 +0100)
committerVladimir Marko <vmarko@google.com>
Thu, 22 May 2014 11:45:58 +0000 (12:45 +0100)
commit53dc70cc824fa71c237015de2bebb2da6b462b5d
treef277f20f69c25c65085af7ad2bf28268466ce6df
parent7bf9c46e93c6f7551f2645cf9bbd1ec9f797c86c
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
runtime/intern_table.cc