diff options
author | Rui Gonçalves <ruippeixotog@gmail.com> | 2015-07-06 22:56:02 +0100 |
---|---|---|
committer | Rui Gonçalves <ruippeixotog@gmail.com> | 2015-07-28 10:12:44 +0100 |
commit | c15259091d43c82053bcacf206eba5da6bc56fe5 (patch) | |
tree | 235d06ba881014d47c70b5e381b1c615d84e47b0 /test/files/run/t8549.scala | |
parent | 462e22d2f25bb9432c5a1e7bf20f391e6424f7a9 (diff) | |
download | scala-c15259091d43c82053bcacf206eba5da6bc56fe5.tar.gz scala-c15259091d43c82053bcacf206eba5da6bc56fe5.tar.bz2 scala-c15259091d43c82053bcacf206eba5da6bc56fe5.zip |
SI-6938 Use mutable red-black tree in TreeSet
The previous implementation of `mutable.TreeSet` uses a mutable reference to an immutable red-black tree as its underlying data structure. That leads to unnecessary objects being created, which can be a problem in systems with limited resources. It also has reduced performance when compared with common mutable implementations.
In this commit `mutable.TreeSet` is changed so that it uses the recently created `mutable.RedBlackTree` as its underlying data structure. Specialized red-black tree methods were created for working with keys for efficiency reasons. The new implementation is source-compatible with the previous one, although its serialized representation obviously changes.
Closes [SI-6938](https://issues.scala-lang.org/browse/SI-6938).
Diffstat (limited to 'test/files/run/t8549.scala')
-rw-r--r-- | test/files/run/t8549.scala | 5 |
1 files changed, 4 insertions, 1 deletions
diff --git a/test/files/run/t8549.scala b/test/files/run/t8549.scala index 2d3f33537d..0f2be6a4cd 100644 --- a/test/files/run/t8549.scala +++ b/test/files/run/t8549.scala @@ -79,7 +79,7 @@ object Test extends App { } } - // Generated on 20150330-15:20:14 with Scala version 2.12.0-20150330-143836-a91b76ea6c) + // Generated on 20150627-00:51:59 with Scala version 2.12.0-20150626-225838-66bdc5200f) overwrite.foreach(updateComment) check(Some(1))("rO0ABXNyAApzY2FsYS5Tb21lESLyaV6hi3QCAAFMAAF4dAASTGphdmEvbGFuZy9PYmplY3Q7eHIADHNjYWxhLk9wdGlvbv5pN/3bDmZ0AgAAeHBzcgARamF2YS5sYW5nLkludGVnZXIS4qCk94GHOAIAAUkABXZhbHVleHIAEGphdmEubGFuZy5OdW1iZXKGrJUdC5TgiwIAAHhwAAAAAQ==") @@ -179,6 +179,9 @@ object Test extends App { check(mutable.TreeMap())( "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuVHJlZU1hcNx8qC229ZvwAgACTAAIb3JkZXJpbmd0ABVMc2NhbGEvbWF0aC9PcmRlcmluZztMACZzY2FsYSRjb2xsZWN0aW9uJG11dGFibGUkVHJlZU1hcCQkdHJlZXQALExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUmVkQmxhY2tUcmVlJFRyZWU7eHBzcgAYc2NhbGEubWF0aC5PcmRlcmluZyRJbnQkC4BMdr1Z51wCAAB4cHNyACpzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuUmVkQmxhY2tUcmVlJFRyZWUATKc08DWmFQIAAkkABHNpemVMAARyb290dAAsTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9SZWRCbGFja1RyZWUkTm9kZTt4cAAAAABw") check(mutable.TreeMap(1 -> 1, 3 -> 6))( "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuVHJlZU1hcNx8qC229ZvwAgACTAAIb3JkZXJpbmd0ABVMc2NhbGEvbWF0aC9PcmRlcmluZztMACZzY2FsYSRjb2xsZWN0aW9uJG11dGFibGUkVHJlZU1hcCQkdHJlZXQALExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUmVkQmxhY2tUcmVlJFRyZWU7eHBzcgAYc2NhbGEubWF0aC5PcmRlcmluZyRJbnQkC4BMdr1Z51wCAAB4cHNyACpzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuUmVkQmxhY2tUcmVlJFRyZWUATKc08DWmFQIAAkkABHNpemVMAARyb290dAAsTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9SZWRCbGFja1RyZWUkTm9kZTt4cAAAAAJzcgAqc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLlJlZEJsYWNrVHJlZSROb2RlGxHsFtValgACAAZaAANyZWRMAANrZXl0ABJMamF2YS9sYW5nL09iamVjdDtMAARsZWZ0cQB+AAdMAAZwYXJlbnRxAH4AB0wABXJpZ2h0cQB+AAdMAAV2YWx1ZXEAfgAKeHAAc3IAEWphdmEubGFuZy5JbnRlZ2VyEuKgpPeBhzgCAAFJAAV2YWx1ZXhyABBqYXZhLmxhbmcuTnVtYmVyhqyVHQuU4IsCAAB4cAAAAAFwcHNxAH4ACQFzcQB+AAwAAAADcHEAfgALcHNxAH4ADAAAAAZxAH4ADg==") check(mutable.TreeMap(1 -> 1, 3 -> 6).range(1, 2))( "rO0ABXNyACxzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuVHJlZU1hcCRUcmVlTWFwVmlldx7MCZxLhVQ8AgADTAAGJG91dGVydAAiTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9UcmVlTWFwO0wABGZyb210AA5Mc2NhbGEvT3B0aW9uO0wABXVudGlscQB+AAJ4cgAgc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLlRyZWVNYXDcfKgttvWb8AIAAkwACG9yZGVyaW5ndAAVTHNjYWxhL21hdGgvT3JkZXJpbmc7TAAmc2NhbGEkY29sbGVjdGlvbiRtdXRhYmxlJFRyZWVNYXAkJHRyZWV0ACxMc2NhbGEvY29sbGVjdGlvbi9tdXRhYmxlL1JlZEJsYWNrVHJlZSRUcmVlO3hwc3IAGHNjYWxhLm1hdGguT3JkZXJpbmckSW50JAuATHa9WedcAgAAeHBzcgAqc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLlJlZEJsYWNrVHJlZSRUcmVlAEynNPA1phUCAAJJAARzaXplTAAEcm9vdHQALExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUmVkQmxhY2tUcmVlJE5vZGU7eHAAAAACc3IAKnNjYWxhLmNvbGxlY3Rpb24ubXV0YWJsZS5SZWRCbGFja1RyZWUkTm9kZRsR7BbVWpYAAgAGWgADcmVkTAADa2V5dAASTGphdmEvbGFuZy9PYmplY3Q7TAAEbGVmdHEAfgAKTAAGcGFyZW50cQB+AApMAAVyaWdodHEAfgAKTAAFdmFsdWVxAH4ADXhwAHNyABFqYXZhLmxhbmcuSW50ZWdlchLioKT3gYc4AgABSQAFdmFsdWV4cgAQamF2YS5sYW5nLk51bWJlcoaslR0LlOCLAgAAeHAAAAABcHBzcQB+AAwBc3EAfgAPAAAAA3BxAH4ADnBzcQB+AA8AAAAGcQB+ABFzcQB+AANxAH4ACHEAfgALc3IACnNjYWxhLlNvbWURIvJpXqGLdAIAAUwAAXhxAH4ADXhyAAxzY2FsYS5PcHRpb27+aTf92w5mdAIAAHhwcQB+ABFzcQB+ABZzcQB+AA8AAAAC") + check(mutable.TreeSet())( "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuVHJlZVNldM10nxFQDpt4AgACTAAIb3JkZXJpbmd0ABVMc2NhbGEvbWF0aC9PcmRlcmluZztMACZzY2FsYSRjb2xsZWN0aW9uJG11dGFibGUkVHJlZVNldCQkdHJlZXQALExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUmVkQmxhY2tUcmVlJFRyZWU7eHBzcgAYc2NhbGEubWF0aC5PcmRlcmluZyRJbnQkC4BMdr1Z51wCAAB4cHNyACpzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuUmVkQmxhY2tUcmVlJFRyZWUATKc08DWmFQIAAkkABHNpemVMAARyb290dAAsTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9SZWRCbGFja1RyZWUkTm9kZTt4cAAAAABw") + check(mutable.TreeSet(1, 3))( "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuVHJlZVNldM10nxFQDpt4AgACTAAIb3JkZXJpbmd0ABVMc2NhbGEvbWF0aC9PcmRlcmluZztMACZzY2FsYSRjb2xsZWN0aW9uJG11dGFibGUkVHJlZVNldCQkdHJlZXQALExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUmVkQmxhY2tUcmVlJFRyZWU7eHBzcgAYc2NhbGEubWF0aC5PcmRlcmluZyRJbnQkC4BMdr1Z51wCAAB4cHNyACpzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuUmVkQmxhY2tUcmVlJFRyZWUATKc08DWmFQIAAkkABHNpemVMAARyb290dAAsTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9SZWRCbGFja1RyZWUkTm9kZTt4cAAAAAJzcgAqc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLlJlZEJsYWNrVHJlZSROb2RlGxHsFtValgACAAZaAANyZWRMAANrZXl0ABJMamF2YS9sYW5nL09iamVjdDtMAARsZWZ0cQB+AAdMAAZwYXJlbnRxAH4AB0wABXJpZ2h0cQB+AAdMAAV2YWx1ZXEAfgAKeHAAc3IAEWphdmEubGFuZy5JbnRlZ2VyEuKgpPeBhzgCAAFJAAV2YWx1ZXhyABBqYXZhLmxhbmcuTnVtYmVyhqyVHQuU4IsCAAB4cAAAAAFwcHNxAH4ACQFzcQB+AAwAAAADcHEAfgALcHBw") + check(mutable.TreeSet(1, 3).range(1, 2))( "rO0ABXNyACxzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuVHJlZVNldCRUcmVlU2V0Vmlld2JdAzqy0DpGAgADTAAGJG91dGVydAAiTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9UcmVlU2V0O0wABGZyb210AA5Mc2NhbGEvT3B0aW9uO0wABXVudGlscQB+AAJ4cgAgc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLlRyZWVTZXTNdJ8RUA6beAIAAkwACG9yZGVyaW5ndAAVTHNjYWxhL21hdGgvT3JkZXJpbmc7TAAmc2NhbGEkY29sbGVjdGlvbiRtdXRhYmxlJFRyZWVTZXQkJHRyZWV0ACxMc2NhbGEvY29sbGVjdGlvbi9tdXRhYmxlL1JlZEJsYWNrVHJlZSRUcmVlO3hwc3IAGHNjYWxhLm1hdGguT3JkZXJpbmckSW50JAuATHa9WedcAgAAeHBzcgAqc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLlJlZEJsYWNrVHJlZSRUcmVlAEynNPA1phUCAAJJAARzaXplTAAEcm9vdHQALExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUmVkQmxhY2tUcmVlJE5vZGU7eHAAAAACc3IAKnNjYWxhLmNvbGxlY3Rpb24ubXV0YWJsZS5SZWRCbGFja1RyZWUkTm9kZRsR7BbVWpYAAgAGWgADcmVkTAADa2V5dAASTGphdmEvbGFuZy9PYmplY3Q7TAAEbGVmdHEAfgAKTAAGcGFyZW50cQB+AApMAAVyaWdodHEAfgAKTAAFdmFsdWVxAH4ADXhwAHNyABFqYXZhLmxhbmcuSW50ZWdlchLioKT3gYc4AgABSQAFdmFsdWV4cgAQamF2YS5sYW5nLk51bWJlcoaslR0LlOCLAgAAeHAAAAABcHBzcQB+AAwBc3EAfgAPAAAAA3BxAH4ADnBwcHNxAH4AA3EAfgAIcQB+AAtzcgAKc2NhbGEuU29tZREi8mleoYt0AgABTAABeHEAfgANeHIADHNjYWxhLk9wdGlvbv5pN/3bDmZ0AgAAeHBxAH4AEXNxAH4AFXNxAH4ADwAAAAI=") // TODO SI-8576 Uninitialized field under -Xcheckinit // check(new mutable.History())( "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuSGlzdG9yeUhuXxDIFJrsAgACSQAKbWF4SGlzdG9yeUwAA2xvZ3QAIExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUXVldWU7eHAAAAPoc3IAHnNjYWxhLmNvbGxlY3Rpb24ubXV0YWJsZS5RdWV1ZbjMURVfOuHHAgAAeHIAJHNjYWxhLmNvbGxlY3Rpb24ubXV0YWJsZS5NdXRhYmxlTGlzdFJpnjJ+gFbAAgADSQADbGVuTAAGZmlyc3QwdAAlTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9MaW5rZWRMaXN0O0wABWxhc3QwcQB+AAV4cAAAAABzcgAjc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLkxpbmtlZExpc3Sak+nGCZHaUQIAAkwABGVsZW10ABJMamF2YS9sYW5nL09iamVjdDtMAARuZXh0dAAeTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9TZXE7eHBwcQB+AApxAH4ACg==") check(mutable.LinkedHashMap(1 -> 2))( "rO0ABXNyACZzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuTGlua2VkSGFzaE1hcAAAAAAAAAABAwAAeHB3DQAAAu4AAAABAAAABABzcgARamF2YS5sYW5nLkludGVnZXIS4qCk94GHOAIAAUkABXZhbHVleHIAEGphdmEubGFuZy5OdW1iZXKGrJUdC5TgiwIAAHhwAAAAAXNxAH4AAgAAAAJ4") |