V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
node-cache.cc
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
3 // found in the LICENSE file.
4 
5 #include "src/compiler/node-cache.h"
6 
7 #include <cstring>
8 
9 #include "src/globals.h"
10 #include "src/zone/zone-containers.h"
11 #include "src/zone/zone.h"
12 
13 namespace v8 {
14 namespace internal {
15 namespace compiler {
16 
17 namespace {
18 
19 enum { kInitialSize = 16u, kLinearProbe = 5u };
20 
21 } // namespace
22 
23 
24 template <typename Key, typename Hash, typename Pred>
25 struct NodeCache<Key, Hash, Pred>::Entry {
26  Key key_;
27  Node* value_;
28 };
29 
30 
31 template <typename Key, typename Hash, typename Pred>
33  if (size_ >= max_) return false; // Don't grow past the maximum size.
34 
35  // Allocate a new block of entries 4x the size.
36  Entry* old_entries = entries_;
37  size_t old_size = size_ + kLinearProbe;
38  size_ *= 4;
39  size_t num_entries = size_ + kLinearProbe;
40  entries_ = zone->NewArray<Entry>(num_entries);
41  memset(static_cast<void*>(entries_), 0, sizeof(Entry) * num_entries);
42 
43  // Insert the old entries into the new block.
44  for (size_t i = 0; i < old_size; ++i) {
45  Entry* old = &old_entries[i];
46  if (old->value_) {
47  size_t hash = hash_(old->key_);
48  size_t start = hash & (size_ - 1);
49  size_t end = start + kLinearProbe;
50  for (size_t j = start; j < end; ++j) {
51  Entry* entry = &entries_[j];
52  if (!entry->value_) {
53  entry->key_ = old->key_;
54  entry->value_ = old->value_;
55  break;
56  }
57  }
58  }
59  }
60  return true;
61 }
62 
63 
64 template <typename Key, typename Hash, typename Pred>
65 Node** NodeCache<Key, Hash, Pred>::Find(Zone* zone, Key key) {
66  size_t hash = hash_(key);
67  if (!entries_) {
68  // Allocate the initial entries and insert the first entry.
69  size_t num_entries = kInitialSize + kLinearProbe;
70  entries_ = zone->NewArray<Entry>(num_entries);
71  size_ = kInitialSize;
72  memset(static_cast<void*>(entries_), 0, sizeof(Entry) * num_entries);
73  Entry* entry = &entries_[hash & (kInitialSize - 1)];
74  entry->key_ = key;
75  return &entry->value_;
76  }
77 
78  for (;;) {
79  // Search up to N entries after (linear probing).
80  size_t start = hash & (size_ - 1);
81  size_t end = start + kLinearProbe;
82  for (size_t i = start; i < end; i++) {
83  Entry* entry = &entries_[i];
84  if (pred_(entry->key_, key)) return &entry->value_;
85  if (!entry->value_) {
86  entry->key_ = key;
87  return &entry->value_;
88  }
89  }
90 
91  if (!Resize(zone)) break; // Don't grow past the maximum size.
92  }
93 
94  // If resized to maximum and still didn't find space, overwrite an entry.
95  Entry* entry = &entries_[hash & (size_ - 1)];
96  entry->key_ = key;
97  entry->value_ = nullptr;
98  return &entry->value_;
99 }
100 
101 
102 template <typename Key, typename Hash, typename Pred>
103 void NodeCache<Key, Hash, Pred>::GetCachedNodes(ZoneVector<Node*>* nodes) {
104  if (entries_) {
105  for (size_t i = 0; i < size_ + kLinearProbe; i++) {
106  if (entries_[i].value_) nodes->push_back(entries_[i].value_);
107  }
108  }
109 }
110 
111 
112 // -----------------------------------------------------------------------------
113 // Instantiations
114 
115 template class V8_EXPORT_PRIVATE NodeCache<int32_t>;
116 template class V8_EXPORT_PRIVATE NodeCache<int64_t>;
117 
118 template class V8_EXPORT_PRIVATE NodeCache<RelocInt32Key>;
119 template class V8_EXPORT_PRIVATE NodeCache<RelocInt64Key>;
120 
121 } // namespace compiler
122 } // namespace internal
123 } // namespace v8
Definition: libplatform.h:13