[ Catalina BigSur wk1 Debug ] webrtc/datachannel/datachannel-gc.html is a flaky crash.
[WebKit-https.git] / PerformanceTests / SunSpider / tests / v8-v4 / v8-splay.js
1 // Copyright 2009 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are
4 // met:
5 //
6 //     * Redistributions of source code must retain the above copyright
7 //       notice, this list of conditions and the following disclaimer.
8 //     * Redistributions in binary form must reproduce the above
9 //       copyright notice, this list of conditions and the following
10 //       disclaimer in the documentation and/or other materials provided
11 //       with the distribution.
12 //     * Neither the name of Google Inc. nor the names of its
13 //       contributors may be used to endorse or promote products derived
14 //       from this software without specific prior written permission.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28 // This benchmark is based on a JavaScript log processing module used
29 // by the V8 profiler to generate execution time profiles for runs of
30 // JavaScript applications, and it effectively measures how fast the
31 // JavaScript engine is at allocating nodes and reclaiming the memory
32 // used for old nodes. Because of the way splay trees work, the engine
33 // also has to deal with a lot of changes to the large tree object
34 // graph.
35
36 // Configuration.
37 var kSplayTreeSize = 8000;
38 var kSplayTreeModifications = 80;
39 var kSplayTreePayloadDepth = 5;
40
41 var splayTree = null;
42
43
44 function GeneratePayloadTree(depth, key) {
45   if (depth == 0) {
46     return {
47       array  : [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ],
48       string : 'String for key ' + key + ' in leaf node'
49     };
50   } else {
51     return {
52       left:  GeneratePayloadTree(depth - 1, key),
53       right: GeneratePayloadTree(depth - 1, key)
54     };
55   }
56 }
57
58
59 function GenerateKey() {
60   // The benchmark framework guarantees that Math.random is
61   // deterministic; see base.js.
62   return Math.random();
63 }
64
65
66 function InsertNewNode() {
67   // Insert new node with a unique key.
68   var key;
69   do {
70     key = GenerateKey();
71   } while (splayTree.find(key) != null);
72   splayTree.insert(key, GeneratePayloadTree(kSplayTreePayloadDepth, key));
73   return key;
74 }
75
76
77
78 function SplaySetup() {
79   splayTree = new SplayTree();
80   for (var i = 0; i < kSplayTreeSize; i++) InsertNewNode();
81 }
82
83
84 function SplayTearDown() {
85   // Allow the garbage collector to reclaim the memory
86   // used by the splay tree no matter how we exit the
87   // tear down function.
88   var keys = splayTree.exportKeys();
89   splayTree = null;
90
91   // Verify that the splay tree has the right size.
92   var length = keys.length;
93   if (length != kSplayTreeSize) {
94     throw new Error("Splay tree has wrong size");
95   }
96
97   // Verify that the splay tree has sorted, unique keys.
98   for (var i = 0; i < length - 1; i++) {
99     if (keys[i] >= keys[i + 1]) {
100       throw new Error("Splay tree not sorted");
101     }
102   }
103 }
104
105
106 function SplayRun() {
107   // Replace a few nodes in the splay tree.
108   for (var i = 0; i < kSplayTreeModifications; i++) {
109     var key = InsertNewNode();
110     var greatest = splayTree.findGreatestLessThan(key);
111     if (greatest == null) splayTree.remove(key);
112     else splayTree.remove(greatest.key);
113   }
114 }
115
116
117 /**
118  * Constructs a Splay tree.  A splay tree is a self-balancing binary
119  * search tree with the additional property that recently accessed
120  * elements are quick to access again. It performs basic operations
121  * such as insertion, look-up and removal in O(log(n)) amortized time.
122  *
123  * @constructor
124  */
125 function SplayTree() {
126 };
127
128
129 /**
130  * Pointer to the root node of the tree.
131  *
132  * @type {SplayTree.Node}
133  * @private
134  */
135 SplayTree.prototype.root_ = null;
136
137
138 /**
139  * @return {boolean} Whether the tree is empty.
140  */
141 SplayTree.prototype.isEmpty = function() {
142   return !this.root_;
143 };
144
145
146 /**
147  * Inserts a node into the tree with the specified key and value if
148  * the tree does not already contain a node with the specified key. If
149  * the value is inserted, it becomes the root of the tree.
150  *
151  * @param {number} key Key to insert into the tree.
152  * @param {*} value Value to insert into the tree.
153  */
154 SplayTree.prototype.insert = function(key, value) {
155   if (this.isEmpty()) {
156     this.root_ = new SplayTree.Node(key, value);
157     return;
158   }
159   // Splay on the key to move the last node on the search path for
160   // the key to the root of the tree.
161   this.splay_(key);
162   if (this.root_.key == key) {
163     return;
164   }
165   var node = new SplayTree.Node(key, value);
166   if (key > this.root_.key) {
167     node.left = this.root_;
168     node.right = this.root_.right;
169     this.root_.right = null;
170   } else {
171     node.right = this.root_;
172     node.left = this.root_.left;
173     this.root_.left = null;
174   }
175   this.root_ = node;
176 };
177
178
179 /**
180  * Removes a node with the specified key from the tree if the tree
181  * contains a node with this key. The removed node is returned. If the
182  * key is not found, an exception is thrown.
183  *
184  * @param {number} key Key to find and remove from the tree.
185  * @return {SplayTree.Node} The removed node.
186  */
187 SplayTree.prototype.remove = function(key) {
188   if (this.isEmpty()) {
189     throw Error('Key not found: ' + key);
190   }
191   this.splay_(key);
192   if (this.root_.key != key) {
193     throw Error('Key not found: ' + key);
194   }
195   var removed = this.root_;
196   if (!this.root_.left) {
197     this.root_ = this.root_.right;
198   } else {
199     var right = this.root_.right;
200     this.root_ = this.root_.left;
201     // Splay to make sure that the new root has an empty right child.
202     this.splay_(key);
203     // Insert the original right child as the right child of the new
204     // root.
205     this.root_.right = right;
206   }
207   return removed;
208 };
209
210
211 /**
212  * Returns the node having the specified key or null if the tree doesn't contain
213  * a node with the specified key.
214  *
215  * @param {number} key Key to find in the tree.
216  * @return {SplayTree.Node} Node having the specified key.
217  */
218 SplayTree.prototype.find = function(key) {
219   if (this.isEmpty()) {
220     return null;
221   }
222   this.splay_(key);
223   return this.root_.key == key ? this.root_ : null;
224 };
225
226
227 /**
228  * @return {SplayTree.Node} Node having the maximum key value that
229  *     is less or equal to the specified key value.
230  */
231 SplayTree.prototype.findGreatestLessThan = function(key) {
232   if (this.isEmpty()) {
233     return null;
234   }
235   // Splay on the key to move the node with the given key or the last
236   // node on the search path to the top of the tree.
237   this.splay_(key);
238   // Now the result is either the root node or the greatest node in
239   // the left subtree.
240   if (this.root_.key <= key) {
241     return this.root_;
242   } else if (this.root_.left) {
243     return this.findMax(this.root_.left);
244   } else {
245     return null;
246   }
247 };
248
249
250 /**
251  * @return {Array<*>} An array containing all the keys of tree's nodes.
252  */
253 SplayTree.prototype.exportKeys = function() {
254   var result = [];
255   if (!this.isEmpty()) {
256     this.root_.traverse_(function(node) { result.push(node.key); });
257   }
258   return result;
259 };
260
261
262 /**
263  * Perform the splay operation for the given key. Moves the node with
264  * the given key to the top of the tree.  If no node has the given
265  * key, the last node on the search path is moved to the top of the
266  * tree. This is the simplified top-down splaying algorithm from:
267  * "Self-adjusting Binary Search Trees" by Sleator and Tarjan
268  *
269  * @param {number} key Key to splay the tree on.
270  * @private
271  */
272 SplayTree.prototype.splay_ = function(key) {
273   if (this.isEmpty()) {
274     return;
275   }
276   // Create a dummy node.  The use of the dummy node is a bit
277   // counter-intuitive: The right child of the dummy node will hold
278   // the L tree of the algorithm.  The left child of the dummy node
279   // will hold the R tree of the algorithm.  Using a dummy node, left
280   // and right will always be nodes and we avoid special cases.
281   var dummy, left, right;
282   dummy = left = right = new SplayTree.Node(null, null);
283   var current = this.root_;
284   while (true) {
285     if (key < current.key) {
286       if (!current.left) {
287         break;
288       }
289       if (key < current.left.key) {
290         // Rotate right.
291         var tmp = current.left;
292         current.left = tmp.right;
293         tmp.right = current;
294         current = tmp;
295         if (!current.left) {
296           break;
297         }
298       }
299       // Link right.
300       right.left = current;
301       right = current;
302       current = current.left;
303     } else if (key > current.key) {
304       if (!current.right) {
305         break;
306       }
307       if (key > current.right.key) {
308         // Rotate left.
309         var tmp = current.right;
310         current.right = tmp.left;
311         tmp.left = current;
312         current = tmp;
313         if (!current.right) {
314           break;
315         }
316       }
317       // Link left.
318       left.right = current;
319       left = current;
320       current = current.right;
321     } else {
322       break;
323     }
324   }
325   // Assemble.
326   left.right = current.left;
327   right.left = current.right;
328   current.left = dummy.right;
329   current.right = dummy.left;
330   this.root_ = current;
331 };
332
333
334 /**
335  * Constructs a Splay tree node.
336  *
337  * @param {number} key Key.
338  * @param {*} value Value.
339  */
340 SplayTree.Node = function(key, value) {
341   this.key = key;
342   this.value = value;
343 };
344
345
346 /**
347  * @type {SplayTree.Node}
348  */
349 SplayTree.Node.prototype.left = null;
350
351
352 /**
353  * @type {SplayTree.Node}
354  */
355 SplayTree.Node.prototype.right = null;
356
357
358 /**
359  * Performs an ordered traversal of the subtree starting at
360  * this SplayTree.Node.
361  *
362  * @param {function(SplayTree.Node)} f Visitor function.
363  * @private
364  */
365 SplayTree.Node.prototype.traverse_ = function(f) {
366   var current = this;
367   while (current) {
368     var left = current.left;
369     if (left) left.traverse_(f);
370     f(current);
371     current = current.right;
372   }
373 };
374
375 SplaySetup();
376 SplayRun();
377 SplayTearDown();