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