| 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 |
| 11 import 'package:logging/logging.dart'; | |
| 12 | |
| 13 class _JenkinsSmiHash { | 11 class _JenkinsSmiHash { |
| 14 static int combine(int hash, int value) { | 12 static int combine(int hash, int value) { |
| 15 hash = 0x1fffffff & (hash + value); | 13 hash = 0x1fffffff & (hash + value); |
| 16 hash = 0x1fffffff & (hash + ((0x0007ffff & hash) << 10)); | 14 hash = 0x1fffffff & (hash + ((0x0007ffff & hash) << 10)); |
| 17 return hash ^ (hash >> 6); | 15 return hash ^ (hash >> 6); |
| 18 } | 16 } |
| 19 | 17 |
| 20 static int finish(int hash) { | 18 static int finish(int hash) { |
| 21 hash = 0x1fffffff & (hash + ((0x03ffffff & hash) << 3)); | 19 hash = 0x1fffffff & (hash + ((0x03ffffff & hash) << 3)); |
| 22 hash = hash ^ (hash >> 11); | 20 hash = hash ^ (hash >> 11); |
| (...skipping 469 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 492 stream.skipUnsigned(); // cid | 490 stream.skipUnsigned(); // cid |
| 493 | 491 |
| 494 firstSuccs[id] = edge; | 492 firstSuccs[id] = edge; |
| 495 | 493 |
| 496 stream.readUnsigned(); | 494 stream.readUnsigned(); |
| 497 while (!stream.isZero) { | 495 while (!stream.isZero) { |
| 498 var childId = addrToId.get(stream.high, stream.mid, stream.low); | 496 var childId = addrToId.get(stream.high, stream.mid, stream.low); |
| 499 if (childId != null) { | 497 if (childId != null) { |
| 500 succs[edge] = childId; | 498 succs[edge] = childId; |
| 501 edge++; | 499 edge++; |
| 502 } else { | 500 } else { |
| 503 // Reference into VM isolate's heap. | 501 // Reference into VM isolate's heap. |
| 504 } | 502 } |
| 505 stream.readUnsigned(); | 503 stream.readUnsigned(); |
| 506 } | 504 } |
| 507 id++; | 505 id++; |
| 508 } | 506 } |
| 509 firstSuccs[id] = edge; // Extra entry for cheap boundary detection. | 507 firstSuccs[id] = edge; // Extra entry for cheap boundary detection. |
| 510 | 508 |
| 511 assert(id == N + 1); | 509 assert(id == N + 1); |
| 512 assert(edge <= E); // edge is smaller because E was computed before we knew | 510 assert(edge <= E); // edge is smaller because E was computed before we knew |
| 513 // if references pointed into the VM isolate | 511 // if references pointed into the VM isolate |
| 514 | 512 |
| 515 _E = edge; | 513 _E = edge; |
| 516 _firstSuccs = firstSuccs; | 514 _firstSuccs = firstSuccs; |
| 517 _succs = succs; | 515 _succs = succs; |
| 518 } | 516 } |
| 519 | 517 |
| 520 void _dfs() { | 518 void _dfs() { |
| 521 var N = _N; | 519 var N = _N; |
| 522 var E = _E; | |
| 523 var firstSuccs = _firstSuccs; | 520 var firstSuccs = _firstSuccs; |
| 524 var succs = _succs; | 521 var succs = _succs; |
| 525 | 522 |
| 526 var stackNodes = new Uint32List(N); | 523 var stackNodes = new Uint32List(N); |
| 527 var stackCurrentEdgePos = new Uint32List(N); | 524 var stackCurrentEdgePos = new Uint32List(N); |
| 528 | 525 |
| 529 var vertex = new Uint32List(N + 1); | 526 var vertex = new Uint32List(N + 1); |
| 530 var semi = new Uint32List(N + 1); | 527 var semi = new Uint32List(N + 1); |
| 531 var parent = new Uint32List(N + 1); | 528 var parent = new Uint32List(N + 1); |
| 532 var dfsNumber = 0; | 529 var dfsNumber = 0; |
| 533 | 530 |
| 534 var dfsCount = 0; | |
| 535 var stackTop = 0; | 531 var stackTop = 0; |
| 536 var root = 1; | 532 var root = 1; |
| 537 | 533 |
| 538 // Push root. | 534 // Push root. |
| 539 stackNodes[0] = root; | 535 stackNodes[0] = root; |
| 540 stackCurrentEdgePos[0] = firstSuccs[root]; | 536 stackCurrentEdgePos[0] = firstSuccs[root]; |
| 541 | 537 |
| 542 while (stackTop >= 0) { | 538 while (stackTop >= 0) { |
| 543 var v = stackNodes[stackTop]; | 539 var v = stackNodes[stackTop]; |
| 544 var edgePos = stackCurrentEdgePos[stackTop]; | 540 var edgePos = stackCurrentEdgePos[stackTop]; |
| (...skipping 271 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 816 for (var i = N; i > 1; i--) { | 812 for (var i = N; i > 1; i--) { |
| 817 var v = vertex[i]; | 813 var v = vertex[i]; |
| 818 assert(v != 1); | 814 assert(v != 1); |
| 819 retainedSizes[doms[i]] += retainedSizes[i]; | 815 retainedSizes[doms[i]] += retainedSizes[i]; |
| 820 } | 816 } |
| 821 | 817 |
| 822 _retainedSizes = retainedSizes; | 818 _retainedSizes = retainedSizes; |
| 823 _size = size; | 819 _size = size; |
| 824 } | 820 } |
| 825 } | 821 } |
| OLD | NEW |