LCOV - code coverage report
Current view: top level - src - identity-map.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 145 145 100.0 %
Date: 2017-04-26 Functions: 17 18 94.4 %

          Line data    Source code
       1             : // Copyright 2015 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #include "src/identity-map.h"
       6             : 
       7             : #include "src/base/functional.h"
       8             : #include "src/heap/heap-inl.h"
       9             : 
      10             : namespace v8 {
      11             : namespace internal {
      12             : 
      13             : static const int kInitialIdentityMapSize = 4;
      14             : static const int kResizeFactor = 4;
      15             : 
      16      545700 : IdentityMapBase::~IdentityMapBase() {
      17             :   // Clear must be called by the subclass to avoid calling the virtual
      18             :   // DeleteArray function from the destructor.
      19             :   DCHECK_NULL(keys_);
      20      545700 : }
      21             : 
      22      664299 : void IdentityMapBase::Clear() {
      23      664299 :   if (keys_) {
      24             :     DCHECK(!is_iterable());
      25      400863 :     heap_->UnregisterStrongRoots(keys_);
      26      400864 :     DeleteArray(keys_);
      27      400864 :     DeleteArray(values_);
      28      400864 :     keys_ = nullptr;
      29      400864 :     values_ = nullptr;
      30      400864 :     size_ = 0;
      31      400864 :     capacity_ = 0;
      32      400864 :     mask_ = 0;
      33             :   }
      34      664300 : }
      35             : 
      36         154 : void IdentityMapBase::EnableIteration() {
      37         154 :   CHECK(!is_iterable());
      38         154 :   is_iterable_ = true;
      39         154 : }
      40             : 
      41         154 : void IdentityMapBase::DisableIteration() {
      42         154 :   CHECK(is_iterable());
      43         154 :   is_iterable_ = false;
      44         154 : }
      45             : 
      46    25970439 : int IdentityMapBase::ScanKeysFor(Object* address) const {
      47    25970439 :   int start = Hash(address) & mask_;
      48    25970347 :   Object* not_mapped = heap_->not_mapped_symbol();
      49    82247229 :   for (int index = start; index < capacity_; index++) {
      50    80936762 :     if (keys_[index] == address) return index;  // Found.
      51    69802378 :     if (keys_[index] == not_mapped) return -1;  // Not found.
      52             :   }
      53     5908412 :   for (int index = 0; index < start; index++) {
      54     7114693 :     if (keys_[index] == address) return index;  // Found.
      55     6888508 :     if (keys_[index] == not_mapped) return -1;  // Not found.
      56             :   }
      57             :   return -1;
      58             : }
      59             : 
      60    23342517 : int IdentityMapBase::InsertKey(Object* address) {
      61    23342517 :   Object* not_mapped = heap_->not_mapped_symbol();
      62             :   while (true) {
      63    24159071 :     int start = Hash(address) & mask_;
      64    24159104 :     int limit = capacity_ / 2;
      65             :     // Search up to {limit} entries.
      66    70991085 :     for (int index = start; --limit > 0; index = (index + 1) & mask_) {
      67    70174531 :       if (keys_[index] == address) return index;  // Found.
      68    70174478 :       if (keys_[index] == not_mapped) {           // Free entry.
      69    23342497 :         keys_[index] = address;
      70    23342497 :         return index;
      71             :       }
      72             :     }
      73             :     // Should only have to resize once, since we grow 4x.
      74      816554 :     Resize(capacity_ * kResizeFactor);
      75             :   }
      76             :   UNREACHABLE();
      77      816554 :   return -1;
      78             : }
      79             : 
      80       14469 : void* IdentityMapBase::DeleteIndex(int index) {
      81       14469 :   void* ret_value = values_[index];
      82       14469 :   Object* not_mapped = heap_->not_mapped_symbol();
      83             :   DCHECK_NE(keys_[index], not_mapped);
      84       14469 :   keys_[index] = not_mapped;
      85       14469 :   values_[index] = nullptr;
      86       14469 :   size_--;
      87             :   DCHECK_GE(size_, 0);
      88             : 
      89       14469 :   if (size_ * kResizeFactor < capacity_ / kResizeFactor) {
      90         129 :     Resize(capacity_ / kResizeFactor);
      91         129 :     return ret_value;  // No need to fix collisions as resize reinserts keys.
      92             :   }
      93             : 
      94             :   // Move any collisions to their new correct location.
      95             :   int next_index = index;
      96             :   for (;;) {
      97       57285 :     next_index = (next_index + 1) & mask_;
      98       57285 :     Object* key = keys_[next_index];
      99       57285 :     if (key == not_mapped) break;
     100             : 
     101       42945 :     int expected_index = Hash(key) & mask_;
     102       42945 :     if (index < next_index) {
     103       41923 :       if (index < expected_index && expected_index <= next_index) continue;
     104             :     } else {
     105             :       DCHECK_GT(index, next_index);
     106        1022 :       if (index < expected_index || expected_index <= next_index) continue;
     107             :     }
     108             : 
     109             :     DCHECK_EQ(not_mapped, keys_[index]);
     110             :     DCHECK_NULL(values_[index]);
     111        8379 :     std::swap(keys_[index], keys_[next_index]);
     112        8379 :     std::swap(values_[index], values_[next_index]);
     113             :     index = next_index;
     114             :   }
     115             : 
     116             :   return ret_value;
     117             : }
     118             : 
     119      203412 : int IdentityMapBase::Lookup(Object* key) const {
     120      203412 :   int index = ScanKeysFor(key);
     121      272190 :   if (index < 0 && gc_counter_ != heap_->gc_count()) {
     122             :     // Miss; rehash if there was a GC, then lookup again.
     123          63 :     const_cast<IdentityMapBase*>(this)->Rehash();
     124          63 :     index = ScanKeysFor(key);
     125             :   }
     126      203412 :   return index;
     127             : }
     128             : 
     129    25766972 : int IdentityMapBase::LookupOrInsert(Object* key) {
     130             :   // Perform an optimistic lookup.
     131    25766972 :   int index = ScanKeysFor(key);
     132    25766949 :   if (index < 0) {
     133             :     // Miss; rehash if there was a GC, then insert.
     134    29082076 :     if (gc_counter_ != heap_->gc_count()) Rehash();
     135    14541038 :     index = InsertKey(key);
     136    14541014 :     size_++;
     137             :     DCHECK_LE(size_, capacity_);
     138             :   }
     139             :   DCHECK_GE(index, 0);
     140    25766925 :   return index;
     141             : }
     142             : 
     143    50187154 : int IdentityMapBase::Hash(Object* address) const {
     144    50187154 :   CHECK_NE(address, heap_->not_mapped_symbol());
     145    50187154 :   uintptr_t raw_address = reinterpret_cast<uintptr_t>(address);
     146    50187151 :   return static_cast<int>(hasher_(raw_address));
     147             : }
     148             : 
     149             : // Searches this map for the given key using the object's address
     150             : // as the identity, returning:
     151             : //    found => a pointer to the storage location for the value
     152             : //    not found => a pointer to a new storage location for the value
     153    25766972 : IdentityMapBase::RawEntry IdentityMapBase::GetEntry(Object* key) {
     154    25766972 :   CHECK(!is_iterable());  // Don't allow insertion while iterable.
     155    25766972 :   if (capacity_ == 0) {
     156             :     // Allocate the initial storage for keys and values.
     157      400864 :     capacity_ = kInitialIdentityMapSize;
     158      400864 :     mask_ = kInitialIdentityMapSize - 1;
     159     1202592 :     gc_counter_ = heap_->gc_count();
     160             : 
     161      400864 :     keys_ = reinterpret_cast<Object**>(NewPointerArray(capacity_));
     162      400864 :     Object* not_mapped = heap_->not_mapped_symbol();
     163      400864 :     for (int i = 0; i < capacity_; i++) keys_[i] = not_mapped;
     164      400864 :     values_ = NewPointerArray(capacity_);
     165      400864 :     memset(values_, 0, sizeof(void*) * capacity_);
     166             : 
     167      400864 :     heap_->RegisterStrongRoots(keys_, keys_ + capacity_);
     168             :   }
     169    25766972 :   int index = LookupOrInsert(key);
     170    25766866 :   return &values_[index];
     171             : }
     172             : 
     173             : // Searches this map for the given key using the object's address
     174             : // as the identity, returning:
     175             : //    found => a pointer to the storage location for the value
     176             : //    not found => {nullptr}
     177      199000 : IdentityMapBase::RawEntry IdentityMapBase::FindEntry(Object* key) const {
     178             :   // Don't allow find by key while iterable (might rehash).
     179      199000 :   CHECK(!is_iterable());
     180      199000 :   if (size_ == 0) return nullptr;
     181             :   // Remove constness since lookup might have to rehash.
     182      188942 :   int index = Lookup(key);
     183      188942 :   return index >= 0 ? &values_[index] : nullptr;
     184             : }
     185             : 
     186             : // Deletes the given key from the map using the object's address as the
     187             : // identity, returning:
     188             : //    found => the value
     189             : //    not found => {nullptr}
     190       15876 : void* IdentityMapBase::DeleteEntry(Object* key) {
     191       15876 :   CHECK(!is_iterable());  // Don't allow deletion by key while iterable.
     192       15876 :   if (size_ == 0) return nullptr;
     193       14470 :   int index = Lookup(key);
     194       14470 :   if (index < 0) return nullptr;  // No entry found.
     195       14469 :   return DeleteIndex(index);
     196             : }
     197             : 
     198       16170 : IdentityMapBase::RawEntry IdentityMapBase::EntryAtIndex(int index) const {
     199             :   DCHECK_LE(0, index);
     200             :   DCHECK_LT(index, capacity_);
     201             :   DCHECK_NE(keys_[index], heap_->not_mapped_symbol());
     202       16170 :   CHECK(is_iterable());  // Must be iterable to access by index;
     203       16170 :   return &values_[index];
     204             : }
     205             : 
     206        8239 : int IdentityMapBase::NextIndex(int index) const {
     207             :   DCHECK_LE(-1, index);
     208             :   DCHECK_LE(index, capacity_);
     209        8239 :   CHECK(is_iterable());  // Must be iterable to access by index;
     210        8239 :   Object* not_mapped = heap_->not_mapped_symbol();
     211       19754 :   for (++index; index < capacity_; ++index) {
     212       19600 :     if (keys_[index] != not_mapped) {
     213             :       return index;
     214             :     }
     215             :   }
     216             :   return capacity_;
     217             : }
     218             : 
     219         118 : void IdentityMapBase::Rehash() {
     220         118 :   CHECK(!is_iterable());  // Can't rehash while iterating.
     221             :   // Record the current GC counter.
     222         354 :   gc_counter_ = heap_->gc_count();
     223             :   // Assume that most objects won't be moved.
     224             :   std::vector<std::pair<Object*, void*>> reinsert;
     225             :   // Search the table looking for keys that wouldn't be found with their
     226             :   // current hashcode and evacuate them.
     227             :   int last_empty = -1;
     228             :   Object* not_mapped = heap_->not_mapped_symbol();
     229       24998 :   for (int i = 0; i < capacity_; i++) {
     230       28432 :     if (keys_[i] == not_mapped) {
     231             :       last_empty = i;
     232             :     } else {
     233       14959 :       int pos = Hash(keys_[i]) & mask_;
     234       14959 :       if (pos <= last_empty || pos > i) {
     235             :         // Evacuate an entry that is in the wrong place.
     236        7104 :         reinsert.push_back(std::pair<Object*, void*>(keys_[i], values_[i]));
     237        3552 :         keys_[i] = not_mapped;
     238        3552 :         values_[i] = nullptr;
     239             :         last_empty = i;
     240             :       }
     241             :     }
     242             :   }
     243             :   // Reinsert all the key/value pairs that were in the wrong place.
     244        3788 :   for (auto pair : reinsert) {
     245        3552 :     int index = InsertKey(pair.first);
     246             :     DCHECK_GE(index, 0);
     247        3552 :     values_[index] = pair.second;
     248             :   }
     249         118 : }
     250             : 
     251      816711 : void IdentityMapBase::Resize(int new_capacity) {
     252      816711 :   CHECK(!is_iterable());  // Can't resize while iterating.
     253             :   // Resize the internal storage and reinsert all the key/value pairs.
     254             :   DCHECK_GT(new_capacity, size_);
     255      816711 :   int old_capacity = capacity_;
     256      816711 :   Object** old_keys = keys_;
     257      816711 :   void** old_values = values_;
     258             : 
     259      816711 :   capacity_ = new_capacity;
     260      816711 :   mask_ = capacity_ - 1;
     261     2450133 :   gc_counter_ = heap_->gc_count();
     262             : 
     263      816711 :   keys_ = reinterpret_cast<Object**>(NewPointerArray(capacity_));
     264      816711 :   Object* not_mapped = heap_->not_mapped_symbol();
     265      816711 :   for (int i = 0; i < capacity_; i++) keys_[i] = not_mapped;
     266      816711 :   values_ = NewPointerArray(capacity_);
     267      816711 :   memset(values_, 0, sizeof(void*) * capacity_);
     268             : 
     269    11478884 :   for (int i = 0; i < old_capacity; i++) {
     270    10662173 :     if (old_keys[i] == not_mapped) continue;
     271     8797965 :     int index = InsertKey(old_keys[i]);
     272             :     DCHECK_GE(index, 0);
     273     8797965 :     values_[index] = old_values[i];
     274             :   }
     275             : 
     276             :   // Unregister old keys and register new keys.
     277      816711 :   heap_->UnregisterStrongRoots(old_keys);
     278      816711 :   heap_->RegisterStrongRoots(keys_, keys_ + capacity_);
     279             : 
     280             :   // Delete old storage;
     281      816711 :   DeleteArray(old_keys);
     282      816711 :   DeleteArray(old_values);
     283      816711 : }
     284             : 
     285             : }  // namespace internal
     286             : }  // namespace v8

Generated by: LCOV version 1.10