diff options
Diffstat (limited to 'deps/v8/src/utils')
| -rw-r--r-- | deps/v8/src/utils/OWNERS | 2 | ||||
| -rw-r--r-- | deps/v8/src/utils/allocation.cc | 4 | ||||
| -rw-r--r-- | deps/v8/src/utils/allocation.h | 11 | ||||
| -rw-r--r-- | deps/v8/src/utils/splay-tree-inl.h | 292 | ||||
| -rw-r--r-- | deps/v8/src/utils/splay-tree.h | 194 | ||||
| -rw-r--r-- | deps/v8/src/utils/utils.h | 63 | ||||
| -rw-r--r-- | deps/v8/src/utils/vector.h | 5 |
7 files changed, 24 insertions, 547 deletions
diff --git a/deps/v8/src/utils/OWNERS b/deps/v8/src/utils/OWNERS index 852d438bb0..3f9de7e204 100644 --- a/deps/v8/src/utils/OWNERS +++ b/deps/v8/src/utils/OWNERS @@ -1 +1,3 @@ file://COMMON_OWNERS + +# COMPONENT: Blink>JavaScript diff --git a/deps/v8/src/utils/allocation.cc b/deps/v8/src/utils/allocation.cc index 27db17a479..af32e90088 100644 --- a/deps/v8/src/utils/allocation.cc +++ b/deps/v8/src/utils/allocation.cc @@ -84,7 +84,7 @@ v8::PageAllocator* SetPlatformPageAllocatorForTesting( return old_page_allocator; } -void* Malloced::New(size_t size) { +void* Malloced::operator new(size_t size) { void* result = AllocWithRetry(size); if (result == nullptr) { V8::FatalProcessOutOfMemory(nullptr, "Malloced operator new"); @@ -92,7 +92,7 @@ void* Malloced::New(size_t size) { return result; } -void Malloced::Delete(void* p) { free(p); } +void Malloced::operator delete(void* p) { free(p); } char* StrDup(const char* str) { size_t length = strlen(str); diff --git a/deps/v8/src/utils/allocation.h b/deps/v8/src/utils/allocation.h index fa3e6f3d7d..2f7074acb0 100644 --- a/deps/v8/src/utils/allocation.h +++ b/deps/v8/src/utils/allocation.h @@ -29,11 +29,8 @@ class Isolate; // Superclass for classes managed with new & delete. class V8_EXPORT_PRIVATE Malloced { public: - void* operator new(size_t size) { return New(size); } - void operator delete(void* p) { Delete(p); } - - static void* New(size_t size); - static void Delete(void* p); + static void* operator new(size_t size); + static void operator delete(void* p); }; template <typename T> @@ -70,8 +67,8 @@ char* StrNDup(const char* str, int n); // and free. Used as the default policy for lists. class FreeStoreAllocationPolicy { public: - V8_INLINE void* New(size_t size) { return Malloced::New(size); } - V8_INLINE static void Delete(void* p) { Malloced::Delete(p); } + V8_INLINE void* New(size_t size) { return Malloced::operator new(size); } + V8_INLINE static void Delete(void* p) { Malloced::operator delete(p); } }; // Performs a malloc, with retry logic on failure. Returns nullptr on failure. diff --git a/deps/v8/src/utils/splay-tree-inl.h b/deps/v8/src/utils/splay-tree-inl.h deleted file mode 100644 index bda453fd8f..0000000000 --- a/deps/v8/src/utils/splay-tree-inl.h +++ /dev/null @@ -1,292 +0,0 @@ -// Copyright 2010 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. - -#ifndef V8_UTILS_SPLAY_TREE_INL_H_ -#define V8_UTILS_SPLAY_TREE_INL_H_ - -#include <vector> - -#include "src/utils/splay-tree.h" - -namespace v8 { -namespace internal { - - -template<typename Config, class Allocator> -SplayTree<Config, Allocator>::~SplayTree() { - NodeDeleter deleter; - ForEachNode(&deleter); -} - - -template<typename Config, class Allocator> -bool SplayTree<Config, Allocator>::Insert(const Key& key, - Locator* locator) { - if (is_empty()) { - // If the tree is empty, insert the new node. - root_ = new(allocator_) Node(key, Config::NoValue()); - } else { - // Splay on the key to move the last node on the search path - // for the key to the root of the tree. - Splay(key); - // Ignore repeated insertions with the same key. - int cmp = Config::Compare(key, root_->key_); - if (cmp == 0) { - locator->bind(root_); - return false; - } - // Insert the new node. - Node* node = new(allocator_) Node(key, Config::NoValue()); - InsertInternal(cmp, node); - } - locator->bind(root_); - return true; -} - - -template<typename Config, class Allocator> -void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) { - if (cmp > 0) { - node->left_ = root_; - node->right_ = root_->right_; - root_->right_ = nullptr; - } else { - node->right_ = root_; - node->left_ = root_->left_; - root_->left_ = nullptr; - } - root_ = node; -} - - -template<typename Config, class Allocator> -bool SplayTree<Config, Allocator>::FindInternal(const Key& key) { - if (is_empty()) - return false; - Splay(key); - return Config::Compare(key, root_->key_) == 0; -} - - -template<typename Config, class Allocator> -bool SplayTree<Config, Allocator>::Contains(const Key& key) { - return FindInternal(key); -} - - -template<typename Config, class Allocator> -bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) { - if (FindInternal(key)) { - locator->bind(root_); - return true; - } else { - return false; - } -} - - -template<typename Config, class Allocator> -bool SplayTree<Config, Allocator>::FindGreatestLessThan(const Key& key, - Locator* locator) { - if (is_empty()) - return false; - // Splay on the key to move the node with the given key or the last - // node on the search path to the top of the tree. - Splay(key); - // Now the result is either the root node or the greatest node in - // the left subtree. - int cmp = Config::Compare(root_->key_, key); - if (cmp <= 0) { - locator->bind(root_); - return true; - } else { - Node* temp = root_; - root_ = root_->left_; - bool result = FindGreatest(locator); - root_ = temp; - return result; - } -} - - -template<typename Config, class Allocator> -bool SplayTree<Config, Allocator>::FindLeastGreaterThan(const Key& key, - Locator* locator) { - if (is_empty()) - return false; - // Splay on the key to move the node with the given key or the last - // node on the search path to the top of the tree. - Splay(key); - // Now the result is either the root node or the least node in - // the right subtree. - int cmp = Config::Compare(root_->key_, key); - if (cmp >= 0) { - locator->bind(root_); - return true; - } else { - Node* temp = root_; - root_ = root_->right_; - bool result = FindLeast(locator); - root_ = temp; - return result; - } -} - - -template<typename Config, class Allocator> -bool SplayTree<Config, Allocator>::FindGreatest(Locator* locator) { - if (is_empty()) - return false; - Node* current = root_; - while (current->right_ != nullptr) current = current->right_; - locator->bind(current); - return true; -} - - -template<typename Config, class Allocator> -bool SplayTree<Config, Allocator>::FindLeast(Locator* locator) { - if (is_empty()) - return false; - Node* current = root_; - while (current->left_ != nullptr) current = current->left_; - locator->bind(current); - return true; -} - - -template<typename Config, class Allocator> -bool SplayTree<Config, Allocator>::Move(const Key& old_key, - const Key& new_key) { - if (!FindInternal(old_key)) - return false; - Node* node_to_move = root_; - RemoveRootNode(old_key); - Splay(new_key); - int cmp = Config::Compare(new_key, root_->key_); - if (cmp == 0) { - // A node with the target key already exists. - delete node_to_move; - return false; - } - node_to_move->key_ = new_key; - InsertInternal(cmp, node_to_move); - return true; -} - - -template<typename Config, class Allocator> -bool SplayTree<Config, Allocator>::Remove(const Key& key) { - if (!FindInternal(key)) - return false; - Node* node_to_remove = root_; - RemoveRootNode(key); - delete node_to_remove; - return true; -} - - -template<typename Config, class Allocator> -void SplayTree<Config, Allocator>::RemoveRootNode(const Key& key) { - if (root_->left_ == nullptr) { - // No left child, so the new tree is just the right child. - root_ = root_->right_; - } else { - // Left child exists. - Node* right = root_->right_; - // Make the original left child the new root. - root_ = root_->left_; - // Splay to make sure that the new root has an empty right child. - Splay(key); - // Insert the original right child as the right child of the new - // root. - root_->right_ = right; - } -} - - -template<typename Config, class Allocator> -void SplayTree<Config, Allocator>::Splay(const Key& key) { - if (is_empty()) - return; - Node dummy_node(Config::kNoKey, Config::NoValue()); - // Create a dummy node. The use of the dummy node is a bit - // counter-intuitive: The right child of the dummy node will hold - // the L tree of the algorithm. The left child of the dummy node - // will hold the R tree of the algorithm. Using a dummy node, left - // and right will always be nodes and we avoid special cases. - Node* dummy = &dummy_node; - Node* left = dummy; - Node* right = dummy; - Node* current = root_; - while (true) { - int cmp = Config::Compare(key, current->key_); - if (cmp < 0) { - if (current->left_ == nullptr) break; - if (Config::Compare(key, current->left_->key_) < 0) { - // Rotate right. - Node* temp = current->left_; - current->left_ = temp->right_; - temp->right_ = current; - current = temp; - if (current->left_ == nullptr) break; - } - // Link right. - right->left_ = current; - right = current; - current = current->left_; - } else if (cmp > 0) { - if (current->right_ == nullptr) break; - if (Config::Compare(key, current->right_->key_) > 0) { - // Rotate left. - Node* temp = current->right_; - current->right_ = temp->left_; - temp->left_ = current; - current = temp; - if (current->right_ == nullptr) break; - } - // Link left. - left->right_ = current; - left = current; - current = current->right_; - } else { - break; - } - } - // Assemble. - left->right_ = current->left_; - right->left_ = current->right_; - current->left_ = dummy->right_; - current->right_ = dummy->left_; - root_ = current; -} - - -template <typename Config, class Allocator> template <class Callback> -void SplayTree<Config, Allocator>::ForEach(Callback* callback) { - NodeToPairAdaptor<Callback> callback_adaptor(callback); - ForEachNode(&callback_adaptor); -} - - -template <typename Config, class Allocator> template <class Callback> -void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) { - if (root_ == nullptr) return; - // Pre-allocate some space for tiny trees. - std::vector<Node*> nodes_to_visit; - nodes_to_visit.push_back(root_); - size_t pos = 0; - while (pos < nodes_to_visit.size()) { - Node* node = nodes_to_visit[pos++]; - if (node->left() != nullptr) nodes_to_visit.push_back(node->left()); - if (node->right() != nullptr) nodes_to_visit.push_back(node->right()); - callback->Call(node); - } -} - - -} // namespace internal -} // namespace v8 - -#endif // V8_UTILS_SPLAY_TREE_INL_H_ diff --git a/deps/v8/src/utils/splay-tree.h b/deps/v8/src/utils/splay-tree.h deleted file mode 100644 index 47633f39db..0000000000 --- a/deps/v8/src/utils/splay-tree.h +++ /dev/null @@ -1,194 +0,0 @@ -// Copyright 2010 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. - -#ifndef V8_UTILS_SPLAY_TREE_H_ -#define V8_UTILS_SPLAY_TREE_H_ - -#include "src/utils/allocation.h" - -namespace v8 { -namespace internal { - -// A splay tree. The config type parameter encapsulates the different -// configurations of a concrete splay tree: -// -// typedef Key: the key type -// typedef Value: the value type -// static const Key kNoKey: the dummy key used when no key is set -// static Value kNoValue(): the dummy value used to initialize nodes -// static int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function -// -// The tree is also parameterized by an allocation policy -// (Allocator). The policy is used for allocating lists in the C free -// store or the zone; see zone.h. - -// Forward defined as -// template <typename Config, class Allocator = FreeStoreAllocationPolicy> -// class SplayTree; -template <typename Config, class AllocationPolicy> -class SplayTree { - public: - using Key = typename Config::Key; - using Value = typename Config::Value; - - class Locator; - - explicit SplayTree(AllocationPolicy allocator = AllocationPolicy()) - : root_(nullptr), allocator_(allocator) {} - ~SplayTree(); - - V8_INLINE void* operator new( - size_t size, AllocationPolicy allocator = AllocationPolicy()) { - return allocator.New(static_cast<int>(size)); - } - V8_INLINE void operator delete(void* p) { AllocationPolicy::Delete(p); } - // Please the MSVC compiler. We should never have to execute this. - V8_INLINE void operator delete(void* p, AllocationPolicy policy) { - UNREACHABLE(); - } - - AllocationPolicy allocator() { return allocator_; } - - // Checks if there is a mapping for the key. - bool Contains(const Key& key); - - // Inserts the given key in this tree with the given value. Returns - // true if a node was inserted, otherwise false. If found the locator - // is enabled and provides access to the mapping for the key. - bool Insert(const Key& key, Locator* locator); - - // Looks up the key in this tree and returns true if it was found, - // otherwise false. If the node is found the locator is enabled and - // provides access to the mapping for the key. - bool Find(const Key& key, Locator* locator); - - // Finds the mapping with the greatest key less than or equal to the - // given key. - bool FindGreatestLessThan(const Key& key, Locator* locator); - - // Find the mapping with the greatest key in this tree. - bool FindGreatest(Locator* locator); - - // Finds the mapping with the least key greater than or equal to the - // given key. - bool FindLeastGreaterThan(const Key& key, Locator* locator); - - // Find the mapping with the least key in this tree. - bool FindLeast(Locator* locator); - - // Move the node from one key to another. - bool Move(const Key& old_key, const Key& new_key); - - // Remove the node with the given key from the tree. - bool Remove(const Key& key); - - // Remove all keys from the tree. - void Clear() { ResetRoot(); } - - bool is_empty() { return root_ == nullptr; } - - // Perform the splay operation for the given key. Moves the node with - // the given key to the top of the tree. If no node has the given - // key, the last node on the search path is moved to the top of the - // tree. - void Splay(const Key& key); - - class Node { - public: - Node(const Key& key, const Value& value) - : key_(key), value_(value), left_(nullptr), right_(nullptr) {} - - V8_INLINE void* operator new(size_t size, AllocationPolicy allocator) { - return allocator.New(static_cast<int>(size)); - } - V8_INLINE void operator delete(void* p) { - return AllocationPolicy::Delete(p); - } - // Please the MSVC compiler. We should never have to execute - // this. - V8_INLINE void operator delete(void* p, AllocationPolicy allocator) { - UNREACHABLE(); - } - - Key key() { return key_; } - Value value() { return value_; } - Node* left() { return left_; } - Node* right() { return right_; } - - private: - friend class SplayTree; - friend class Locator; - Key key_; - Value value_; - Node* left_; - Node* right_; - }; - - // A locator provides access to a node in the tree without actually - // exposing the node. - class Locator { - public: - explicit Locator(Node* node) : node_(node) {} - Locator() : node_(nullptr) {} - const Key& key() { return node_->key_; } - Value& value() { return node_->value_; } - void set_value(const Value& value) { node_->value_ = value; } - inline void bind(Node* node) { node_ = node; } - - private: - Node* node_; - }; - - template <class Callback> - void ForEach(Callback* callback); - - protected: - // Resets tree root. Existing nodes become unreachable. - void ResetRoot() { root_ = nullptr; } - - private: - // Search for a node with a given key. If found, root_ points - // to the node. - bool FindInternal(const Key& key); - - // Inserts a node assuming that root_ is already set up. - void InsertInternal(int cmp, Node* node); - - // Removes root_ node. - void RemoveRootNode(const Key& key); - - template <class Callback> - class NodeToPairAdaptor { - public: - explicit NodeToPairAdaptor(Callback* callback) : callback_(callback) {} - void Call(Node* node) { callback_->Call(node->key(), node->value()); } - - private: - Callback* callback_; - - DISALLOW_COPY_AND_ASSIGN(NodeToPairAdaptor); - }; - - class NodeDeleter { - public: - NodeDeleter() = default; - void Call(Node* node) { AllocationPolicy::Delete(node); } - - private: - DISALLOW_COPY_AND_ASSIGN(NodeDeleter); - }; - - template <class Callback> - void ForEachNode(Callback* callback); - - Node* root_; - AllocationPolicy allocator_; - - DISALLOW_COPY_AND_ASSIGN(SplayTree); -}; - -} // namespace internal -} // namespace v8 - -#endif // V8_UTILS_SPLAY_TREE_H_ diff --git a/deps/v8/src/utils/utils.h b/deps/v8/src/utils/utils.h index 17e07d3042..20d85aae10 100644 --- a/deps/v8/src/utils/utils.h +++ b/deps/v8/src/utils/utils.h @@ -777,36 +777,16 @@ inline T truncate_to_intn(T x, unsigned n) { return (x & ((static_cast<T>(1) << n) - 1)); } -#define INT_1_TO_63_LIST(V) \ - V(1) \ - V(2) \ - V(3) \ - V(4) \ - V(5) \ - V(6) \ - V(7) \ - V(8) \ - V(9) \ - V(10) \ - V(11) \ - V(12) \ - V(13) \ - V(14) \ - V(15) \ - V(16) \ - V(17) \ - V(18) \ - V(19) \ - V(20) \ - V(21) \ - V(22) \ - V(23) \ - V(24) \ - V(25) \ - V(26) V(27) V(28) V(29) V(30) V(31) V(32) V(33) V(34) V(35) V(36) V(37) \ - V(38) V(39) V(40) V(41) V(42) V(43) V(44) V(45) V(46) V(47) V(48) V(49) \ - V(50) V(51) V(52) V(53) V(54) V(55) V(56) V(57) V(58) V(59) V(60) \ - V(61) V(62) V(63) +// clang-format off +#define INT_1_TO_63_LIST(V) \ + V(1) V(2) V(3) V(4) V(5) V(6) V(7) V(8) V(9) V(10) \ + V(11) V(12) V(13) V(14) V(15) V(16) V(17) V(18) V(19) V(20) \ + V(21) V(22) V(23) V(24) V(25) V(26) V(27) V(28) V(29) V(30) \ + V(31) V(32) V(33) V(34) V(35) V(36) V(37) V(38) V(39) V(40) \ + V(41) V(42) V(43) V(44) V(45) V(46) V(47) V(48) V(49) V(50) \ + V(51) V(52) V(53) V(54) V(55) V(56) V(57) V(58) V(59) V(60) \ + V(61) V(62) V(63) +// clang-format on #define DECLARE_IS_INT_N(N) \ inline bool is_int##N(int64_t x) { return is_intn(x, N); } @@ -875,12 +855,6 @@ class BailoutId { int ToInt() const { return id_; } static BailoutId None() { return BailoutId(kNoneId); } - static BailoutId ScriptContext() { return BailoutId(kScriptContextId); } - static BailoutId FunctionContext() { return BailoutId(kFunctionContextId); } - static BailoutId FunctionEntry() { return BailoutId(kFunctionEntryId); } - static BailoutId Declarations() { return BailoutId(kDeclarationsId); } - static BailoutId FirstUsable() { return BailoutId(kFirstUsableId); } - static BailoutId StubEntry() { return BailoutId(kStubEntryId); } // Special bailout id support for deopting into the {JSConstructStub} stub. // The following hard-coded deoptimization points are supported by the stub: @@ -905,25 +879,10 @@ class BailoutId { static const int kNoneId = -1; // Using 0 could disguise errors. - static const int kScriptContextId = 1; - static const int kFunctionContextId = 2; - static const int kFunctionEntryId = 3; - - // This AST id identifies the point after the declarations have been visited. - // We need it to capture the environment effects of declarations that emit - // code (function declarations). - static const int kDeclarationsId = 4; - - // Every FunctionState starts with this id. - static const int kFirstUsableId = 5; - - // Every compiled stub starts with this id. - static const int kStubEntryId = 6; - // Builtin continuations bailout ids start here. If you need to add a // non-builtin BailoutId, add it before this id so that this Id has the // highest number. - static const int kFirstBuiltinContinuationId = 7; + static const int kFirstBuiltinContinuationId = 1; int id_; }; diff --git a/deps/v8/src/utils/vector.h b/deps/v8/src/utils/vector.h index 5b6c878e34..dd5c59e553 100644 --- a/deps/v8/src/utils/vector.h +++ b/deps/v8/src/utils/vector.h @@ -230,6 +230,8 @@ constexpr Vector<const uint8_t> StaticCharVector(const char (&array)[N]) { return Vector<const uint8_t>::cast(Vector<const char>(array, N - 1)); } +// The resulting vector does not contain a null-termination byte. If you want +// the null byte, use ArrayVector("foo"). inline Vector<const char> CStrVector(const char* data) { return Vector<const char>(data, strlen(data)); } @@ -250,6 +252,9 @@ inline Vector<char> MutableCStrVector(char* data, size_t max) { return Vector<char>(data, strnlen(data, max)); } +// For string literals, ArrayVector("foo") returns a vector ['f', 'o', 'o', \0] +// with length 4 and null-termination. +// If you want ['f', 'o', 'o'], use CStrVector("foo"). template <typename T, size_t N> inline constexpr Vector<T> ArrayVector(T (&arr)[N]) { return Vector<T>{arr, N}; |