From 1836b7967563828ba7323a1ae6ec2d657351c028 Mon Sep 17 00:00:00 2001
From: Christian Heim <phreak@gentoo.org>
Date: Tue, 8 Nov 2005 15:50:19 +0000
Subject: Merging uberlord's latest changes of baselayout (r1604).

svn path=/baselayout-vserver/trunk/; revision=66
---
 sbin/rc-services.sh | 70 ++++++++++++++++++-----------------------------------
 1 file changed, 23 insertions(+), 47 deletions(-)

(limited to 'sbin/rc-services.sh')

diff --git a/sbin/rc-services.sh b/sbin/rc-services.sh
index b7e6043..a592a7e 100755
--- a/sbin/rc-services.sh
+++ b/sbin/rc-services.sh
@@ -742,69 +742,45 @@ trace_dependencies() {
 			local x="${x} $( get_net_services "${mylevel}" )"
 		[[ -n ${x} ]] && net_services="${x}"
 	fi
-	
-	local -a visited
-	for (( i=0; i<${#services[@]}; i++)); do
-		[[ ${visited[@]} == *" ${services[i]} "* ]] && continue
+
+	# OK, this is a topological sort
+	# The bonus about doing it in bash is that we can calculate our sort
+	# order as we calculate our dependencies
+	local -a visited sorted
+	visit_service() {
+		local service="$1" dep
+		local -a deps
+
+		[[ " ${visited[@]} " == *" ${service} "* ]] && return
+		visited=( "${visited[@]}" "${service}" )
+
 		if [[ -n ${deptype} ]] ; then
-			deps=( "${deps[@]}" $( "${deptype}" "${services[i]}" ) )
+			deps=( "${deps[@]}" $( "${deptype}" "${service}" ) )
 		else
 			deps=( 
-				$( ineed "${services[i]}" )
-				$( valid_iuse "${services[i]}" )
+				$( ineed "${service}" )
+				$( valid_iuse "${service}" )
 			)
 		
 			if is_runlevel_start || is_runlevel_stop ; then
-				deps=( "${deps[@]}" $( valid_iafter "${services[i]}" ) )
+				deps=( "${deps[@]}" $( valid_iafter "${service}" ) )
 			fi
 
 			local x=" ${deps[@]} "
 			deps=( ${x// net / ${net_services} } )
 		fi
-		services=( "${services[@]}" "${deps[@]}" )
-		visited=( "${visited[@]}" "${services[i]}" )
-	done
-
-	# Now, we sort our services
-	# When a service is first visited, we mark it dead and then
-	# revisit any dependencies. Finally we add ourselves to the sorted list.
-	# This should never get into an infinite loop, thanks to our dead array.
-	local -a dead=() deadname=() sorted=() 
-	for (( i=0; i<${#services[@]}; i++ )); do
-		dead[i]="false";
-		deadname[i]="${services[i]}"
-	done
-
-	after_visit() {
-		local service="$1" i
-
-		for (( i=0; i<${#deadname[@]}; i++)); do
-			[[ ${service} == ${deadname[i]} ]] && break
-		done
 
-		${dead[i]} && return
-		dead[i]="true"
-
-		local x deps=" $( ineed ${service} ) $( valid_iuse ${service} ) "
-		if is_runlevel_start || is_runlevel_stop ; then
-			deps="${deps} $( valid_iafter ${service} ) "
-		fi
-
-		if [[ -z ${deptype} ]] ; then
-			# If its a net service, just replace it with 'net'
-			deps="${deps// net / ${net_services} }"
-		fi
-
-		for x in ${deps}; do
-			after_visit "${x}"
+		services=( "${services[@]}" "${deps[@]}" )
+		for dep in ${deps[@]}; do
+			visit_service "${dep}"
 		done
-
 		sorted=( "${sorted[@]}" "${service}" )
 	}
-
-	for (( i=0; i<${#services[*]}; i++ )); do
-		after_visit "${services[i]}"
+		
+	for (( i=0; i<${#services[@]}; i++)); do
+		visit_service "${services[i]}"
 	done
+
 	services=( "${sorted[@]}" )
 
 	if [[ -n ${deptype} ]] ; then
-- 
cgit v1.2.3-65-gdbad