| Index: chrome/test/data/v8_benchmark/splay.js
|
| diff --git a/chrome/test/data/v8_benchmark/splay.js b/chrome/test/data/v8_benchmark/splay.js
|
| index 53fc72793e4255ce3164194026c7c6046a978d6f..6b4f56d3213846574ca1ac3c75a52e4ae0dcc66c 100644
|
| --- a/chrome/test/data/v8_benchmark/splay.js
|
| +++ b/chrome/test/data/v8_benchmark/splay.js
|
| @@ -33,7 +33,7 @@
|
| // also has to deal with a lot of changes to the large tree object
|
| // graph.
|
|
|
| -var Splay = new BenchmarkSuite('Splay', 126125, [
|
| +var Splay = new BenchmarkSuite('Splay', 81491, [
|
| new Benchmark("Splay", SplayRun, SplaySetup, SplayTearDown)
|
| ]);
|
|
|
| @@ -46,16 +46,16 @@ var kSplayTreePayloadDepth = 5;
|
| var splayTree = null;
|
|
|
|
|
| -function GeneratePayloadTree(depth, key) {
|
| +function GeneratePayloadTree(depth, tag) {
|
| if (depth == 0) {
|
| return {
|
| array : [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ],
|
| - string : 'String for key ' + key + ' in leaf node'
|
| + string : 'String for key ' + tag + ' in leaf node'
|
| };
|
| } else {
|
| return {
|
| - left: GeneratePayloadTree(depth - 1, key),
|
| - right: GeneratePayloadTree(depth - 1, key)
|
| + left: GeneratePayloadTree(depth - 1, tag),
|
| + right: GeneratePayloadTree(depth - 1, tag)
|
| };
|
| }
|
| }
|
| @@ -74,7 +74,8 @@ function InsertNewNode() {
|
| do {
|
| key = GenerateKey();
|
| } while (splayTree.find(key) != null);
|
| - splayTree.insert(key, GeneratePayloadTree(kSplayTreePayloadDepth, key));
|
| + var payload = GeneratePayloadTree(kSplayTreePayloadDepth, String(key));
|
| + splayTree.insert(key, payload);
|
| return key;
|
| }
|
|
|
| @@ -230,8 +231,23 @@ SplayTree.prototype.find = function(key) {
|
|
|
|
|
| /**
|
| + * @return {SplayTree.Node} Node having the maximum key value.
|
| + */
|
| +SplayTree.prototype.findMax = function(opt_startNode) {
|
| + if (this.isEmpty()) {
|
| + return null;
|
| + }
|
| + var current = opt_startNode || this.root_;
|
| + while (current.right) {
|
| + current = current.right;
|
| + }
|
| + return current;
|
| +};
|
| +
|
| +
|
| +/**
|
| * @return {SplayTree.Node} Node having the maximum key value that
|
| - * is less or equal to the specified key value.
|
| + * is less than the specified key value.
|
| */
|
| SplayTree.prototype.findGreatestLessThan = function(key) {
|
| if (this.isEmpty()) {
|
| @@ -242,7 +258,7 @@ SplayTree.prototype.findGreatestLessThan = function(key) {
|
| this.splay_(key);
|
| // Now the result is either the root node or the greatest node in
|
| // the left subtree.
|
| - if (this.root_.key <= key) {
|
| + if (this.root_.key < key) {
|
| return this.root_;
|
| } else if (this.root_.left) {
|
| return this.findMax(this.root_.left);
|
|
|