Make JetStream 2
[WebKit-https.git] / PerformanceTests / JetStream2 / simple / hash-map.js
1 /*
2  *  Licensed to the Apache Software Foundation (ASF) under one or more
3  *  contributor license agreements.  See the NOTICE below for additional
4  *  information regarding copyright ownership.
5  *  The ASF licenses this file to You under the Apache License, Version 2.0
6  *  (the "License"); you may not use this file except in compliance with
7  *  the License.  You may obtain a copy of the License at
8  *
9  *     http://www.apache.org/licenses/LICENSE-2.0
10  *
11  *  Unless required by applicable law or agreed to in writing, software
12  *  distributed under the License is distributed on an "AS IS" BASIS,
13  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  *  See the License for the specific language governing permissions and
15  *  limitations under the License.
16  */
17
18 /******* NOTICE *********
19
20 Apache Harmony
21 Copyright 2006, 2010 The Apache Software Foundation.
22
23 This product includes software developed at
24 The Apache Software Foundation (http://www.apache.org/).
25
26 Portions of Apache Harmony were originally developed by
27 Intel Corporation and are licensed to the Apache Software
28 Foundation under the "Software Grant and Corporate Contribution
29 License Agreement" and for which the following copyright notices
30 apply
31          (C) Copyright 2005 Intel Corporation
32          (C) Copyright 2005-2006 Intel Corporation
33          (C) Copyright 2006 Intel Corporation
34
35
36 The following copyright notice(s) were affixed to portions of the code
37 with which this file is now or was at one time distributed
38 and are placed here unaltered.
39
40 (C) Copyright 1997,2004 International Business Machines Corporation.
41 All rights reserved.
42
43 (C) Copyright IBM Corp. 2003. 
44
45
46 This software contains code derived from UNIX V7, Copyright(C)
47 Caldera International Inc.
48
49 ************************/
50
51 // This code is a manual translation of Apache Harmony's HashMap class to
52 // JavaScript.
53
54 var HashMap = (function() {
55     var DEFAULT_SIZE = 16;
56     
57     function calculateCapacity(x)
58     {
59         if (x >= 1 << 30)
60             return 1 << 30;
61         if (x == 0)
62             return 16;
63         x = x - 1;
64         x |= x >> 1;
65         x |= x >> 2;
66         x |= x >> 4;
67         x |= x >> 8;
68         x |= x >> 16;
69         return x + 1;
70     }
71     
72     function computeHashCode(key)
73     {
74         switch (typeof key) {
75         case "undefined":
76             return 0;
77         case "object":
78             if (!key)
79                 return 0;
80         case "function":
81             return key.hashCode();
82         case "boolean":
83             return key | 0;
84         case "number":
85             if ((key | 0) == key)
86                 return key;
87             key = "" + key; // Compute string hash of the double. It's the best we can do.
88         case "string":
89             // source: http://en.wikipedia.org/wiki/Java_hashCode()#Sample_implementations_of_the_java.lang.String_algorithm
90             var h = 0;
91             var len = key.length;
92             for (var index = 0; index < len; index++) {
93                 h = (((31 * h) | 0) + key.charCodeAt(index)) | 0;
94             }
95             return h;
96         default:
97             throw new Error("Internal error: Bad JavaScript value type");
98         }
99     }
100     
101     function equals(a, b)
102     {
103         if (typeof a != typeof b)
104             return false;
105         switch (typeof a) {
106         case "object":
107             if (!a)
108                 return !b;
109         case "function":
110             switch (typeof b) {
111             case "object":
112             case "function":
113                 return a.equals(b);
114             default:
115                 return false;
116             }
117         default:
118             return a == b;
119         }
120     }
121     
122     function Entry(key, hash, value)
123     {
124         this._key = key;
125         this._value = value;
126         this._origKeyHash = hash;
127         this._next = null;
128     }
129
130     Entry.prototype = {
131         clone: function()
132         {
133             var result = new Entry(this._key, this._hash, this._value);
134             if (this._next)
135                 result._next = this._next.clone();
136             return result;
137         },
138         
139         toString: function()
140         {
141             return this._key + "=" + this._value;
142         },
143         
144         get key()
145         {
146             return this._key;
147         },
148         
149         get value()
150         {
151             return this._value;
152         }
153     };
154     
155     function AbstractMapIterator(map)
156     {
157         this._associatedMap = map;
158         this._expectedModCount = map._modCount;
159         this._futureEntry = null;
160         this._currentEntry = null;
161         this._prevEntry = null;
162         this._position = 0;
163     }
164     
165     AbstractMapIterator.prototype = {
166         hasNext: function()
167         {
168             if (this._futureEntry)
169                 return true;
170             while (this._position < this._associatedMap._elementData.length) {
171                 if (!this._associatedMap._elementData[this._position])
172                     this._position++;
173                 else
174                     return true;
175             }
176             return false;
177         },
178         
179         _checkConcurrentMod: function()
180         {
181             if (this._expectedModCount != this._associatedMap._modCount)
182                 throw new Error("Concurrent HashMap modification detected");
183         },
184         
185         _makeNext: function()
186         {
187             this._checkConcurrentMod();
188             if (!this.hasNext())
189                 throw new Error("No such element");
190             if (!this._futureEntry) {
191                 this._currentEntry = this._associatedMap._elementData[this._position++];
192                 this._futureEntry = this._currentEntry._next;
193                 this._prevEntry = null;
194                 return;
195             }
196             if (this._currentEntry)
197                 this._prevEntry = this._currentEntry;
198             this._currentEntry = this._futureEntry;
199             this._futureEntry = this._futureEntry._next;
200         },
201         
202         remove: function()
203         {
204             this._checkConcurrentMod();
205             if (!this._currentEntry)
206                 throw new Error("Illegal state");
207             if (!this._prevEntry) {
208                 var index = this._currentEntry._origKeyHash & (this._associatedMap._elementData.length - 1);
209                 this._associatedMap._elementData[index] = this._associatedMap._elementData[index]._next;
210             } else
211                 this._prevEntry._next = this._currentEntry._next;
212             this._currentEntry = null;
213             this._expectedModCount++;
214             this._associatedMap._modCount++;
215             this._associatedMap._elementCount--;
216         }
217     };
218     
219     function EntryIterator(map)
220     {
221         AbstractMapIterator.call(this, map);
222     }
223     
224     EntryIterator.prototype = {
225         next: function()
226         {
227             this._makeNext();
228             return this._currentEntry;
229         }
230     };
231     EntryIterator.prototype.__proto__ = AbstractMapIterator.prototype;
232     
233     function KeyIterator(map)
234     {
235         AbstractMapIterator.call(this, map);
236     }
237     
238     KeyIterator.prototype = {
239         next: function()
240         {
241             this.makeNext();
242             return this._currentEntry._key;
243         }
244     };
245     KeyIterator.prototype.__proto__ = AbstractMapIterator.prototype;
246     
247     function ValueIterator(map)
248     {
249         AbstractMapIterator.call(this, map);
250     }
251     
252     ValueIterator.prototype = {
253         next: function()
254         {
255             this.makeNext();
256             return this._currentEntry._value;
257         }
258     };
259     ValueIterator.prototype.__proto__ = AbstractMapIterator.prototype;
260     
261     function EntrySet(map)
262     {
263         this._associatedMap = map;
264     }
265     
266     EntrySet.prototype = {
267         size: function()
268         {
269             return this._associatedMap._elementCount;
270         },
271         
272         clear: function()
273         {
274             this._associatedMap.clear();
275         },
276         
277         remove: function(object)
278         {
279             var entry = this._associatedMap._getEntry(object.key);
280             if (!entry)
281                 return false;
282             if (!equals(entry._value, object.value))
283                 return false;
284             this._associatedMap._removeEntry(entry);
285             return true;
286         },
287         
288         contains: function(object)
289         {
290             var entry = this._associatedMap._getEntry(object.key);
291             if (!entry)
292                 return false;
293             return equals(entry._value, object.value);
294         },
295         
296         iterator: function()
297         {
298             return new EntryIterator(this._associatedMap);
299         }
300     };
301     
302     function KeySet(map)
303     {
304         this._associatedMap = map;
305     }
306     
307     KeySet.prototype = {
308         contains: function(object)
309         {
310             return this._associatedMap.contains(object);
311         },
312         
313         size: function()
314         {
315             return this._associatedMap._elementCount;
316         },
317         
318         clear: function()
319         {
320             this._associatedMap.clear();
321         },
322         
323         remove: function(key)
324         {
325             return !!this._associatedMap.remove(key);
326         },
327         
328         iterator: function()
329         {
330             return new KeyIterator(this._associatedMap);
331         }
332     };
333     
334     function ValueCollection(map)
335     {
336         this._associatedMap = map;
337     }
338     
339     ValueCollection.prototype = {
340         contains: function(object)
341         {
342             return this._associatedMap.containsValue(object);
343         },
344         
345         size: function()
346         {
347             return this._associatedMap._elementCount;
348         },
349         
350         clear: function()
351         {
352             this._associatedMap.clear();
353         },
354         
355         iterator: function()
356         {
357             return new ValueIterator(this._associatedMap);
358         }
359     };
360     
361     function HashMap(capacity, loadFactor)
362     {
363         if (capacity == null)
364             capacity = DEFAULT_SIZE;
365         if (loadFactor == null)
366             loadFactor = 0.75;
367         
368         if (capacity < 0)
369             throw new Error("Invalid argument to HashMap constructor: capacity is negative");
370         if (loadFactor <= 0)
371             throw new Error("Invalid argument to HashMap constructor: loadFactor is not positive");
372         
373         this._capacity = calculateCapacity(capacity);
374         this._elementCount = 0;
375         this._elementData = new Array(this.capacity);
376         this._loadFactor = loadFactor;
377         this._modCount = 0;
378         this._computeThreshold();
379     }
380     
381     HashMap.prototype = {
382         _computeThreshold: function()
383         {
384             this._threshold = (this._elementData.length * this._loadFactor) | 0;
385         },
386         
387         clear: function()
388         {
389             if (!this._elementCount)
390                 return;
391             
392             this._elementCount = 0;
393             for (var i = this._elementData.length; i--;)
394                 this._elementData[i] = null;
395             this._modCount++;
396         },
397         
398         clone: function()
399         {
400             var result = new HashMap(this._elementData.length, this._loadFactor);
401             result.putAll(this);
402             return result;
403         },
404         
405         containsKey: function(key)
406         {
407             return !!this._getEntry(key);
408         },
409         
410         containsValue: function(value)
411         {
412             for (var i = this._elementData.length; i--;) {
413                 for (var entry = this._elementData[i]; entry; entry = entry._next) {
414                     if (equals(value, entry._value))
415                         return true;
416                 }
417             }
418             return false;
419         },
420         
421         entrySet: function()
422         {
423             return new EntrySet(this);
424         },
425         
426         get: function(key)
427         {
428             var entry = this._getEntry(key);
429             if (entry)
430                 return entry._value;
431             return null;
432         },
433         
434         _getEntry: function(key)
435         {
436             var hash = computeHashCode(key);
437             var index = hash & (this._elementData.length - 1);
438             return this._findKeyEntry(key, index, hash);
439         },
440         
441         _findKeyEntry: function(key, index, keyHash)
442         {
443             var entry = this._elementData[index];
444             while (entry && (entry._origKeyHash != keyHash || !equals(key, entry._key)))
445                 entry = entry._next;
446             return entry;
447         },
448         
449         isEmpty: function()
450         {
451             return !this._elementCount;
452         },
453         
454         keySet: function()
455         {
456             return new KeySet(this);
457         },
458         
459         put: function(key, value)
460         {
461             var hash = computeHashCode(key);
462             var index = hash & (this._elementData.length - 1);
463             var entry = this._findKeyEntry(key, index, hash);
464             if (!entry) {
465                 this._modCount++;
466                 entry = this._createHashedEntry(key, index, hash);
467                 if (++this._elementCount > this._threshold)
468                     this._rehash();
469             }
470             
471             var result = entry._value;
472             entry._value = value;
473             return result;
474         },
475         
476         _createHashedEntry: function(key, index, hash)
477         {
478             var entry = new Entry(key, hash, null);
479             entry._next = this._elementData[index];
480             this._elementData[index] = entry;
481             return entry;
482         },
483         
484         putAll: function(map)
485         {
486             if (map.isEmpty())
487                 return;
488             for (var iter = map.entrySet().iterator(); iter.hasNext();) {
489                 var entry = iter.next();
490                 put(entry.key, entry.value);
491             }
492         },
493         
494         _rehash: function(capacity)
495         {
496             if (capacity == null)
497                 capacity = this._elementData.length;
498             
499             var length = calculateCapacity(!capacity ? 1 : capacity << 1);
500             var newData = new Array(length);
501             for (var i = 0; i < this._elementData.length; ++i) {
502                 var entry = this._elementData[i];
503                 this._elementData[i] = null;
504                 while (entry) {
505                     var index = entry._origKeyHash & (length - 1);
506                     var next = entry._next;
507                     entry._next = newData[index];
508                     newData[index] = entry;
509                     entry = next;
510                 }
511             }
512             this._elementData = newData;
513             this._computeThreshold();
514         },
515         
516         remove: function(key)
517         {
518             var entry = this._removeEntryForKey(key);
519             if (!entry)
520                 return null;
521             return entry._value;
522         },
523         
524         _removeEntry: function(entry)
525         {
526             var index = entry._origKeyHash & (this._elementData.length - 1);
527             var current = this._elementData[index];
528             if (current == entry)
529                 this._elementData[index] = entry._next;
530             else {
531                 while (current._next != entry)
532                     current = current._next;
533                 current._next = entry._next;
534             }
535             this._modCount++;
536             this._elementCount--;
537         },
538         
539         _removeEntryForKey: function(key)
540         {
541             var hash = computeHashCode(key);
542             var index = hash & (this._elementData.length - 1);
543             var entry = this._elementData[index];
544             var last = null;
545             while (entry != null && !(entry._origKeyHash == hash && equals(key, entry._key))) {
546                 last = entry;
547                 entry = entry._next;
548             }
549             if (!entry)
550                 return null;
551             if (!last)
552                 this._elementData[index] = entry._next;
553             else
554                 last._next = entry._next;
555             this._modCount++;
556             this._elementCount--;
557             return entry;
558         },
559         
560         size: function()
561         {
562             return this._elementCount;
563         },
564         
565         values: function()
566         {
567             return new ValueCollection(this);
568         }
569     };
570     
571     return HashMap;
572 })();
573
574 function run() {
575     var map = new HashMap();
576     var COUNT = 90000;
577
578     for (var i = 0; i < COUNT; ++i)
579         map.put(i, 42);
580
581     var result = 0;
582     for (var j = 0; j < 5; ++j) {
583         for (var i = 0; i < COUNT; ++i)
584             result += map.get(i);
585     }
586
587     var keySum = 0;
588     var valueSum = 0;
589     for (var iterator = map.entrySet().iterator(); iterator.hasNext();) {
590         var entry = iterator.next();
591         keySum += entry.key;
592         valueSum += entry.value;
593     }
594
595     if (result !== 42 * COUNT * 5)
596         throw "Error: result = " + result;
597     if (keySum !== ((COUNT * (COUNT + 1) / 2) - COUNT))
598         throw "Error: keySum = " + keySum;
599     if (valueSum !== 42 * COUNT)
600         throw "Error: valueSum = " + valueSum;
601 }
602
603 class Benchmark {
604     runIteration() {
605         run();
606     }
607 }
608