OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 1 // Copyright 2014 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/compiler/node-cache.h" | 5 #include "src/compiler/node-cache.h" |
6 | 6 |
7 #include <cstring> | 7 #include <cstring> |
8 | 8 |
9 #include "src/zone.h" | 9 #include "src/zone.h" |
10 #include "src/zone-containers.h" | 10 #include "src/zone-containers.h" |
(...skipping 18 matching lines...) Expand all Loading... |
29 | 29 |
30 template <typename Key, typename Hash, typename Pred> | 30 template <typename Key, typename Hash, typename Pred> |
31 bool NodeCache<Key, Hash, Pred>::Resize(Zone* zone) { | 31 bool NodeCache<Key, Hash, Pred>::Resize(Zone* zone) { |
32 if (size_ >= max_) return false; // Don't grow past the maximum size. | 32 if (size_ >= max_) return false; // Don't grow past the maximum size. |
33 | 33 |
34 // Allocate a new block of entries 4x the size. | 34 // Allocate a new block of entries 4x the size. |
35 Entry* old_entries = entries_; | 35 Entry* old_entries = entries_; |
36 size_t old_size = size_ + kLinearProbe; | 36 size_t old_size = size_ + kLinearProbe; |
37 size_ *= 4; | 37 size_ *= 4; |
38 size_t num_entries = size_ + kLinearProbe; | 38 size_t num_entries = size_ + kLinearProbe; |
39 entries_ = zone->NewArray<Entry>(static_cast<int>(num_entries)); | 39 entries_ = zone->NewArray<Entry>(num_entries); |
40 memset(entries_, 0, sizeof(Entry) * num_entries); | 40 memset(entries_, 0, sizeof(Entry) * num_entries); |
41 | 41 |
42 // Insert the old entries into the new block. | 42 // Insert the old entries into the new block. |
43 for (size_t i = 0; i < old_size; ++i) { | 43 for (size_t i = 0; i < old_size; ++i) { |
44 Entry* old = &old_entries[i]; | 44 Entry* old = &old_entries[i]; |
45 if (old->value_) { | 45 if (old->value_) { |
46 size_t hash = hash_(old->key_); | 46 size_t hash = hash_(old->key_); |
47 size_t start = hash & (size_ - 1); | 47 size_t start = hash & (size_ - 1); |
48 size_t end = start + kLinearProbe; | 48 size_t end = start + kLinearProbe; |
49 for (size_t j = start; j < end; ++j) { | 49 for (size_t j = start; j < end; ++j) { |
50 Entry* entry = &entries_[j]; | 50 Entry* entry = &entries_[j]; |
51 if (!entry->value_) { | 51 if (!entry->value_) { |
52 entry->key_ = old->key_; | 52 entry->key_ = old->key_; |
53 entry->value_ = old->value_; | 53 entry->value_ = old->value_; |
54 break; | 54 break; |
55 } | 55 } |
56 } | 56 } |
57 } | 57 } |
58 } | 58 } |
59 return true; | 59 return true; |
60 } | 60 } |
61 | 61 |
62 | 62 |
63 template <typename Key, typename Hash, typename Pred> | 63 template <typename Key, typename Hash, typename Pred> |
64 Node** NodeCache<Key, Hash, Pred>::Find(Zone* zone, Key key) { | 64 Node** NodeCache<Key, Hash, Pred>::Find(Zone* zone, Key key) { |
65 size_t hash = hash_(key); | 65 size_t hash = hash_(key); |
66 if (!entries_) { | 66 if (!entries_) { |
67 // Allocate the initial entries and insert the first entry. | 67 // Allocate the initial entries and insert the first entry. |
68 size_t num_entries = kInitialSize + kLinearProbe; | 68 size_t num_entries = kInitialSize + kLinearProbe; |
69 entries_ = zone->NewArray<Entry>(static_cast<int>(num_entries)); | 69 entries_ = zone->NewArray<Entry>(num_entries); |
70 size_ = kInitialSize; | 70 size_ = kInitialSize; |
71 memset(entries_, 0, sizeof(Entry) * num_entries); | 71 memset(entries_, 0, sizeof(Entry) * num_entries); |
72 Entry* entry = &entries_[hash & (kInitialSize - 1)]; | 72 Entry* entry = &entries_[hash & (kInitialSize - 1)]; |
73 entry->key_ = key; | 73 entry->key_ = key; |
74 return &entry->value_; | 74 return &entry->value_; |
75 } | 75 } |
76 | 76 |
77 for (;;) { | 77 for (;;) { |
78 // Search up to N entries after (linear probing). | 78 // Search up to N entries after (linear probing). |
79 size_t start = hash & (size_ - 1); | 79 size_t start = hash & (size_ - 1); |
(...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
111 // ----------------------------------------------------------------------------- | 111 // ----------------------------------------------------------------------------- |
112 // Instantiations | 112 // Instantiations |
113 | 113 |
114 | 114 |
115 template class NodeCache<int32_t>; | 115 template class NodeCache<int32_t>; |
116 template class NodeCache<int64_t>; | 116 template class NodeCache<int64_t>; |
117 | 117 |
118 } // namespace compiler | 118 } // namespace compiler |
119 } // namespace internal | 119 } // namespace internal |
120 } // namespace v8 | 120 } // namespace v8 |
OLD | NEW |