| OLD | NEW |
| 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 library object_graph; | 5 library object_graph; |
| 6 | 6 |
| 7 import 'dart:async'; | 7 import 'dart:async'; |
| 8 import 'dart:collection'; | 8 import 'dart:collection'; |
| 9 import 'dart:typed_data'; | 9 import 'dart:typed_data'; |
| 10 | 10 |
| (...skipping 897 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 908 var w = vertex[i]; | 908 var w = vertex[i]; |
| 909 if (dom[w] != vertex[semi[w]]) { | 909 if (dom[w] != vertex[semi[w]]) { |
| 910 dom[w] = dom[dom[w]]; | 910 dom[w] = dom[dom[w]]; |
| 911 } | 911 } |
| 912 } | 912 } |
| 913 | 913 |
| 914 _doms = dom; | 914 _doms = dom; |
| 915 } | 915 } |
| 916 | 916 |
| 917 void _calculateRetainedSizes() { | 917 void _calculateRetainedSizes() { |
| 918 var N = _N; | |
| 919 var Nconnected = _Nconnected; | 918 var Nconnected = _Nconnected; |
| 920 | 919 |
| 921 var size = 0; | 920 var size = 0; |
| 922 var shallowSizes = _shallowSizes; | 921 var shallowSizes = _shallowSizes; |
| 923 var vertex = _vertex; | 922 var vertex = _vertex; |
| 924 var doms = _doms; | 923 var doms = _doms; |
| 925 | 924 |
| 926 // Sum shallow sizes. | 925 // Sum shallow sizes. |
| 927 for (var i = 1; i <= Nconnected; i++) { | 926 for (var i = 1; i <= Nconnected; i++) { |
| 928 var v = vertex[i]; | 927 var v = vertex[i]; |
| (...skipping 116 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1045 var head = _mergedDomHead; | 1044 var head = _mergedDomHead; |
| 1046 var next = _mergedDomNext; | 1045 var next = _mergedDomNext; |
| 1047 var workStack = new Uint32List(N); | 1046 var workStack = new Uint32List(N); |
| 1048 var workStackTop = 0; | 1047 var workStackTop = 0; |
| 1049 | 1048 |
| 1050 mergeChildrenAndSort(var parent1, var end) { | 1049 mergeChildrenAndSort(var parent1, var end) { |
| 1051 assert(parent1 != SENTINEL); | 1050 assert(parent1 != SENTINEL); |
| 1052 if (next[parent1] == end) return; | 1051 if (next[parent1] == end) return; |
| 1053 | 1052 |
| 1054 // Find the middle of the list. | 1053 // Find the middle of the list. |
| 1055 int cid = cids[parent1]; | |
| 1056 int slow = parent1; | 1054 int slow = parent1; |
| 1057 int fast = parent1; | 1055 int fast = parent1; |
| 1058 while (next[fast] != end && next[next[fast]] != end) { | 1056 while (next[fast] != end && next[next[fast]] != end) { |
| 1059 slow = next[slow]; | 1057 slow = next[slow]; |
| 1060 fast = next[next[fast]]; | 1058 fast = next[next[fast]]; |
| 1061 } | 1059 } |
| 1062 | 1060 |
| 1063 int parent2 = next[slow]; | 1061 int parent2 = next[slow]; |
| 1064 | 1062 |
| 1065 assert(parent2 != SENTINEL); | 1063 assert(parent2 != SENTINEL); |
| (...skipping 10 matching lines...) Expand all Loading... |
| 1076 // Children moved to parent1. | 1074 // Children moved to parent1. |
| 1077 head[parent2] = SENTINEL; | 1075 head[parent2] = SENTINEL; |
| 1078 } | 1076 } |
| 1079 | 1077 |
| 1080 // Push root. | 1078 // Push root. |
| 1081 workStack[workStackTop++] = ROOT; | 1079 workStack[workStackTop++] = ROOT; |
| 1082 | 1080 |
| 1083 while (workStackTop > 0) { | 1081 while (workStackTop > 0) { |
| 1084 var parent = workStack[--workStackTop]; | 1082 var parent = workStack[--workStackTop]; |
| 1085 | 1083 |
| 1086 var prev = SENTINEL; | |
| 1087 var child = head[parent]; | 1084 var child = head[parent]; |
| 1088 while (child != SENTINEL) { | 1085 while (child != SENTINEL) { |
| 1089 // Push child. | 1086 // Push child. |
| 1090 workStack[workStackTop++] = child; | 1087 workStack[workStackTop++] = child; |
| 1091 | 1088 |
| 1092 // Find next sibling with a different cid. | 1089 // Find next sibling with a different cid. |
| 1093 var after = child; | 1090 var after = child; |
| 1094 while (after != SENTINEL && cids[after] == cids[child]) { | 1091 while (after != SENTINEL && cids[after] == cids[child]) { |
| 1095 after = next[after]; | 1092 after = next[after]; |
| 1096 } | 1093 } |
| 1097 | 1094 |
| 1098 // From all the siblings between child and after, take their children, | 1095 // From all the siblings between child and after, take their children, |
| 1099 // merge them and given to child. | 1096 // merge them and given to child. |
| 1100 mergeChildrenAndSort(child, after); | 1097 mergeChildrenAndSort(child, after); |
| 1101 | 1098 |
| 1102 child = after; | 1099 child = after; |
| 1103 } | 1100 } |
| 1104 } | 1101 } |
| 1105 } | 1102 } |
| 1106 } | 1103 } |
| OLD | NEW |