Upgrade to 3.29
Update V8 to 3.29.88.17 and update makefiles to support building on
all the relevant platforms.
Bug: 17370214
Change-Id: Ia3407c157fd8d72a93e23d8318ccaf6ecf77fa4e
diff --git a/src/splay-tree.h b/src/splay-tree.h
index 72231e4..30e5d67 100644
--- a/src/splay-tree.h
+++ b/src/splay-tree.h
@@ -1,34 +1,11 @@
// Copyright 2010 the V8 project authors. All rights reserved.
-// Redistribution and use in source and binary forms, with or without
-// modification, are permitted provided that the following conditions are
-// met:
-//
-// * Redistributions of source code must retain the above copyright
-// notice, this list of conditions and the following disclaimer.
-// * Redistributions in binary form must reproduce the above
-// copyright notice, this list of conditions and the following
-// disclaimer in the documentation and/or other materials provided
-// with the distribution.
-// * Neither the name of Google Inc. nor the names of its
-// contributors may be used to endorse or promote products derived
-// from this software without specific prior written permission.
-//
-// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
-// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
-// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
-// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
-// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
-// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
-// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
#ifndef V8_SPLAY_TREE_H_
#define V8_SPLAY_TREE_H_
-#include "allocation.h"
+#include "src/allocation.h"
namespace v8 {
namespace internal {
@@ -39,9 +16,9 @@
//
// typedef Key: the key type
// typedef Value: the value type
-// static const kNoKey: the dummy key used when no key is set
-// static const kNoValue: the dummy value used to initialize nodes
-// int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function
+// 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
@@ -50,7 +27,7 @@
// Forward defined as
// template <typename Config, class Allocator = FreeStoreAllocationPolicy>
// class SplayTree;
-template <typename Config, class Allocator>
+template <typename Config, class AllocationPolicy>
class SplayTree {
public:
typedef typename Config::Key Key;
@@ -58,13 +35,26 @@
class Locator;
- SplayTree() : root_(NULL) { }
+ explicit SplayTree(AllocationPolicy allocator = AllocationPolicy())
+ : root_(NULL), allocator_(allocator) {}
~SplayTree();
- INLINE(void* operator new(size_t size)) {
- return Allocator::New(static_cast<int>(size));
+ INLINE(void* operator new(size_t size,
+ AllocationPolicy allocator = AllocationPolicy())) {
+ return allocator.New(static_cast<int>(size));
}
- INLINE(void operator delete(void* p, size_t)) { return Allocator::Delete(p); }
+ INLINE(void operator delete(void* p)) {
+ AllocationPolicy::Delete(p);
+ }
+ // Please the MSVC compiler. We should never have to execute this.
+ 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
@@ -96,6 +86,9 @@
// 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_ == NULL; }
// Perform the splay operation for the given key. Moves the node with
@@ -112,11 +105,16 @@
left_(NULL),
right_(NULL) { }
- INLINE(void* operator new(size_t size)) {
- return Allocator::New(static_cast<int>(size));
+ INLINE(void* operator new(size_t size, AllocationPolicy allocator)) {
+ return allocator.New(static_cast<int>(size));
}
- INLINE(void operator delete(void* p, size_t)) {
- return Allocator::Delete(p);
+ INLINE(void operator delete(void* p)) {
+ return AllocationPolicy::Delete(p);
+ }
+ // Please the MSVC compiler. We should never have to execute
+ // this.
+ INLINE(void operator delete(void* p, AllocationPolicy allocator)) {
+ UNREACHABLE();
}
Key key() { return key_; }
@@ -184,7 +182,7 @@
class NodeDeleter BASE_EMBEDDED {
public:
NodeDeleter() { }
- void Call(Node* node) { delete node; }
+ void Call(Node* node) { AllocationPolicy::Delete(node); }
private:
DISALLOW_COPY_AND_ASSIGN(NodeDeleter);
@@ -194,6 +192,7 @@
void ForEachNode(Callback* callback);
Node* root_;
+ AllocationPolicy allocator_;
DISALLOW_COPY_AND_ASSIGN(SplayTree);
};