Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(101)

Unified Diff: src/compiler/node-cache.cc

Issue 426233002: Land the Fan (disabled) (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Review feedback, rebase and "git cl format" Created 6 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/compiler/node-cache.h ('k') | src/compiler/node-matchers.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/compiler/node-cache.cc
diff --git a/src/compiler/node-cache.cc b/src/compiler/node-cache.cc
new file mode 100644
index 0000000000000000000000000000000000000000..c3ee58c5a236faac50dcd8b0e9443a0ead256890
--- /dev/null
+++ b/src/compiler/node-cache.cc
@@ -0,0 +1,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
« no previous file with comments | « src/compiler/node-cache.h ('k') | src/compiler/node-matchers.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698