blob: c3ee58c5a236faac50dcd8b0e9443a0ead256890 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "src/compiler/node-cache.h"
namespace v8 {
namespace internal {
namespace compiler {
#define INITIAL_SIZE 16
#define LINEAR_PROBE 5
template <typename Key>
int32_t NodeCacheHash(Key key) {
UNIMPLEMENTED();
return 0;
}
template <>
inline int32_t NodeCacheHash(int32_t key) {
return ComputeIntegerHash(key, 0);
}
template <>
inline int32_t NodeCacheHash(int64_t key) {
return ComputeLongHash(key);
}
template <>
inline int32_t NodeCacheHash(double key) {
return ComputeLongHash(BitCast<int64_t>(key));
}
template <>
inline int32_t NodeCacheHash(void* key) {
return ComputePointerHash(key);
}
template <typename Key>
bool NodeCache<Key>::Resize(Zone* zone) {
if (size_ >= max_) return false; // Don't grow past the maximum size.
// Allocate a new block of entries 4x the size.
Entry* old_entries = entries_;
int old_size = size_ + LINEAR_PROBE;
size_ = size_ * 4;
int num_entries = size_ + LINEAR_PROBE;
entries_ = zone->NewArray<Entry>(num_entries);
memset(entries_, 0, sizeof(Entry) * num_entries);
// Insert the old entries into the new block.
for (int i = 0; i < old_size; i++) {
Entry* old = &old_entries[i];
if (old->value_ != NULL) {
int hash = NodeCacheHash(old->key_);
int start = hash & (size_ - 1);
int end = start + LINEAR_PROBE;
for (int j = start; j < end; j++) {
Entry* entry = &entries_[j];
if (entry->value_ == NULL) {
entry->key_ = old->key_;
entry->value_ = old->value_;
break;
}
}
}
}
return true;
}
template <typename Key>
Node** NodeCache<Key>::Find(Zone* zone, Key key) {
int32_t hash = NodeCacheHash(key);
if (entries_ == NULL) {
// Allocate the initial entries and insert the first entry.
int num_entries = INITIAL_SIZE + LINEAR_PROBE;
entries_ = zone->NewArray<Entry>(num_entries);
size_ = INITIAL_SIZE;
memset(entries_, 0, sizeof(Entry) * num_entries);
Entry* entry = &entries_[hash & (INITIAL_SIZE - 1)];
entry->key_ = key;
return &entry->value_;
}
while (true) {
// Search up to N entries after (linear probing).
int start = hash & (size_ - 1);
int end = start + LINEAR_PROBE;
for (int i = start; i < end; i++) {
Entry* entry = &entries_[i];
if (entry->key_ == key) return &entry->value_;
if (entry->value_ == NULL) {
entry->key_ = key;
return &entry->value_;
}
}
if (!Resize(zone)) break; // Don't grow past the maximum size.
}
// If resized to maximum and still didn't find space, overwrite an entry.
Entry* entry = &entries_[hash & (size_ - 1)];
entry->key_ = key;
entry->value_ = NULL;
return &entry->value_;
}
template class NodeCache<int64_t>;
template class NodeCache<int32_t>;
template class NodeCache<void*>;
}
}
} // namespace v8::internal::compiler
|
