From 83df736b84b6eda5c2e81ced09a9934264cadb51 Mon Sep 17 00:00:00 2001
From: "jun.wang" <junbill.wang@samsung.com>
Date: Mon, 4 Jul 2016 13:45:41 +0800
Subject: [PATCH] Reorder the building dependence: 1.The packages which are
 been depended most ,build them first. 2.The packages which have no dependence
 ,build them later.

These ways can imporve the building speed for multiple packages.

Change-Id: I5165c41016c301064d0f6746be947632863daaaf
---
 depanneur | 98 ++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 79 insertions(+), 19 deletions(-)

diff --git a/depanneur b/depanneur
index d0f0ed1..0edfbac 100755
--- a/depanneur
+++ b/depanneur
@@ -162,7 +162,8 @@ my %tmp_expansion_errors = ();
 my $packages_built :shared  = 0; # if there's package build succeeded
 my %build_status_json = ();      # final json report data
 my %workers = ();                # build workers: { 'state' => 'idle'|'busy' , 'tid' => undef|$tid };
-
+my @build_order = ();  #The build order for all packages
+my $get_order = 0; #Bool :  @build_order is empty
 
 GetOptions (
     "repository=s" => \@repos,
@@ -1260,12 +1261,36 @@ sub check_circle {
     return 0;
 }
 
+#---------------------------------------------------------------------
+#Get one package's dependence
+#Eg: A->B->C->(D H)
+#if we get_ddeps_list(A) ,will get @{D H C B}
+#---------------------------------------------------------------------
+sub get_ddeps_list {
+     my $pack = shift;
+     my @list = ();
+
+     if (! defined($pkgddeps{$pack}) ||
+	scalar $pkgddeps{$pack} == 0
+     ) {
+	return @list;
+     }
+
+     for my $name  (@{ $pkgddeps{$pack} }) {
+		push @list, get_ddeps_list($name);
+		push @list, $name;
+     }
+
+     return @list;
+}
+
 #---------------------------------------------------------------------
 # generate topological sort sequence from global %pkgddeps
 #---------------------------------------------------------------------
 sub get_top_order {
     my @top_order = ();
     my %ref = ();
+    my $max = 0;
 
     for my $pack (sort keys %pkgddeps) {
         $ref{$pack} = 0;
@@ -1278,24 +1303,48 @@ sub get_top_order {
         }
     }
 
+    for my $pkg (sort keys %ref) {
+	if ($max < ($ref{$pkg})) {
+		$max = ($ref{$pkg});
+	}
+    }
+
     while (@top_order != scalar (keys %pkgddeps)) {
-        my @candlist = ();
+
         for my $pkg (sort keys %ref) {
-            if ($ref{$pkg} == 0) {
-                push @candlist, $pkg;
+            if ($ref{$pkg} == $max) {
                 push @top_order, $pkg;
                 delete $ref{$pkg};
-            }
-        }
-        for (@candlist) {
-            next if (! defined($pkgddeps{$_}));
-            for (@{$pkgddeps{$_} }) {
-                $ref{$_} -= 1;
-            }
+            } else {
+		$ref{$pkg} += 1;
+	    }
         }
     }
 
-    return @top_order;
+    my @final_order = ();
+    for my $name (@top_order) {
+	next if (! defined($pkgddeps{$name}));
+	next if ( grep $_ eq $name,  @final_order) ;
+	my @cnt = @{$pkgddeps{$name} };
+	if (scalar(@cnt) == 0) {
+		push @final_order, $name;
+	} else {
+		for my $list_pk (@cnt){
+			next if ( grep $_ eq $list_pk,  @final_order);
+
+			my @tmp_order = get_ddeps_list($list_pk);
+			for my $pk (@tmp_order) {
+				if (! grep $_ eq $pk,  @final_order) {
+					push @final_order, $pk;
+				}
+			}
+			push @final_order, $list_pk;
+		}
+		push @final_order, $name;
+	}
+    }
+
+     return @final_order;
 }
 
 
@@ -1385,6 +1434,10 @@ sub update_pkgddeps {
     # pkgddeps  => pkgdeps
     # pkgrddeps => pkgrdeps
     my @top_order = get_top_order();
+    if ($get_order == 0) {
+    	@build_order = @top_order;
+	$get_order = 0;
+    }
 
     %pkgdeps = ();
     %pkgrdeps = ();
@@ -2261,14 +2314,15 @@ while (! $TERM) {
             refresh_repo();
             update_pkgdeps();
             update_pkgddeps();
-            if (check_circle() == 1) {
-                info("circle found, exit...");
-                exit 1;
-            }
+            #if (check_circle() == 1) {
+            #    info("circle found, exit...");
+            #    exit 1;
+            #}
 
             $dirty = 0;
         }
-        foreach my $name (keys %to_build) {
+
+        foreach my $name (@build_order) {
             # skip the followint packages:
             #  - packages already done (in @done list)
             #  - packages skipped (in @skipped list)
@@ -2348,8 +2402,14 @@ while (! $TERM) {
         }
 
         for (; $needed && ! $TERM; $needed--) {
-            my $job = shift(@order);
-            last if (! $job);
+
+	    my $job ;
+	    if (scalar (@order) != 0) {
+		$job = shift(@order);
+	    }
+	    else {
+		last ;
+	    }
 
             my $worker = find_idle();
             my $index;
-- 
2.34.1