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 |