Index: test/codegen/corelib/collection_length_test.dart |
diff --git a/test/codegen/corelib/collection_length_test.dart b/test/codegen/corelib/collection_length_test.dart |
new file mode 100644 |
index 0000000000000000000000000000000000000000..3259ab258ae7cd737f725f9602c212e51e2e8047 |
--- /dev/null |
+++ b/test/codegen/corelib/collection_length_test.dart |
@@ -0,0 +1,77 @@ |
+// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file |
+// for details. All rights reserved. Use of this source code is governed by a |
+// BSD-style license that can be found in the LICENSE file. |
+ |
+library map_test; |
+import 'dart:collection'; |
+ |
+// Test that length/isEmpty opertions are constant time on |
+// maps, strings and collections. |
+ |
+void testString(int n) { |
+ String s = "x"; |
+ String string = ""; |
+ int length = n; |
+ while (true) { |
+ if ((length & 1) == 1) { |
+ string += s; |
+ } |
+ length >>= 1; |
+ if (length == 0) break; |
+ s += s; |
+ } |
+ testLength(string, n); |
+ testLength(string.codeUnits, n); |
+} |
+ |
+void testMap(Map map, int n) { |
+ for (int i = 0; i < n; i++) { |
+ map[i] = i; |
+ } |
+ testLength(map, n); |
+ testLength(map.keys, n); |
+ testLength(map.values, n); |
+} |
+ |
+void testCollection(var collection, n) { |
+ for (int i = 0; i < n; i++) { |
+ collection.add(i); |
+ } |
+ testLength(collection, n); |
+} |
+ |
+void testList(List list, n) { |
+ // Works even if list is fixed-length. |
+ for (int i = 0; i < n; i++) { |
+ list[i] = i; |
+ } |
+ testLength(list, n); |
+} |
+ |
+ |
+void testLength(var lengthable, int size) { |
+ print(lengthable.runtimeType); // Show what hangs the test. |
+ int length = 0; |
+ // If length, isEmpty or isNotEmpty is not a constant-time (or very fast) |
+ // operation, this will timeout. |
+ for (int i = 0; i < 100000; i++) { |
+ if (!lengthable.isEmpty) length += lengthable.length; |
+ if (lengthable.isNotEmpty) length += lengthable.length; |
+ } |
+ if (length != size * 200000) throw "Bad length: $length / size: $size"; |
+} |
+ |
+ |
+main() { |
+ const int N = 100000; |
+ testMap(new HashMap(), N); |
+ testMap(new LinkedHashMap(), N); |
+ testMap(new SplayTreeMap(), N); |
+ testCollection(new HashSet(), N); |
+ testCollection(new LinkedHashSet(), N); |
+ testCollection(new ListQueue(), N); |
+ testCollection(new DoubleLinkedQueue(), N); |
+ testList(new List()..length = N, N); |
+ testList(new List(N), N); |
+ testString(N); |
+} |