Index: sbin/rcorder/rcorder.c
===================================================================
--- sbin/rcorder/rcorder.c
+++ sbin/rcorder/rcorder.c
@@ -75,6 +75,7 @@
 
 static int exit_code;
 static int file_count;
+static int generation;
 static char **file_list;
 
 typedef int bool;
@@ -122,6 +123,7 @@
 	f_reqnode	*req_list;
 	f_provnode	*prov_list;
 	strnodelist	*keyword_list;
+	int		generation;
 };
 
 static filenode fn_head_s, *fn_head;
@@ -150,13 +152,15 @@
 static void crunch_all_files(void);
 static void initialize(void);
 static void generate_ordering(void);
+static void generate_parallel(void);
+static int parallel = 0;
 
 int
 main(int argc, char *argv[])
 {
 	int ch;
 
-	while ((ch = getopt(argc, argv, "dk:s:")) != -1)
+	while ((ch = getopt(argc, argv, "dk:ps:")) != -1)
 		switch (ch) {
 		case 'd':
 #ifdef DEBUG
@@ -168,6 +172,9 @@
 		case 'k':
 			strnode_add(&keep_list, optarg, 0);
 			break;
+		case 'p':
+			parallel = 1;
+			break;
 		case 's':
 			strnode_add(&skip_list, optarg, 0);
 			break;
@@ -186,7 +193,11 @@
 	DPRINTF((stderr, "initialize\n"));
 	crunch_all_files();
 	DPRINTF((stderr, "crunch_all_files\n"));
-	generate_ordering();
+	if (parallel) {
+		generate_parallel();
+	} else {
+		generate_ordering();
+	}
 	DPRINTF((stderr, "generate_ordering\n"));
 
 	exit(exit_code);
@@ -701,7 +712,10 @@
 static void
 do_file(filenode *fnode)
 {
-	f_reqnode *r, *r_tmp;
+	f_reqnode *r;
+#if 0
+	f_reqnode *r_tmp;
+#endif
 	f_provnode *p, *p_tmp;
 	provnode *pnode;
 	int was_set;	
@@ -719,51 +733,66 @@
 	} else
 		was_set = 0;
 
-	/* mark fnode */
-	fnode->in_progress = SET;
-
-	/*
-	 * for each requirement of fnode -> r
-	 *	satisfy_req(r, filename)
-	 */
-	r = fnode->req_list;
-	while (r != NULL) {
-		r_tmp = r;
-		satisfy_req(r, fnode->filename);
-		r = r->next;
+	if (parallel) {
+		/*
+		 * Mark node as handled in the current iteration.
+		 * When running in parallel mode, we use this mechanism
+		 * instead of removing dependencies, because in case
+		 * where we have "A" node and its dependency "B", we must
+		 * make sure we don't emit "B A", but always "B\nA".
+		 */
+		DPRINTF((stderr, "node %s done in generation %d\n",
+		    fnode->filename, generation));
+		fnode->generation = generation;
+	} else {
+		/* mark fnode */
+		fnode->in_progress = SET;
+
+		/*
+		 * for each requirement of fnode -> r
+		 *	satisfy_req(r, filename)
+		 */
+		r = fnode->req_list;
+		while (r != NULL) {
 #if 0
-		if (was_set == 0)
-			free(r_tmp);
+			r_tmp = r;
+#endif
+			satisfy_req(r, fnode->filename);
+			r = r->next;
+#if 0
+			if (was_set == 0)
+				free(r_tmp);
 #endif
-	}
-	fnode->req_list = NULL;
-
-	/*
-	 * for each provision of fnode -> p
-	 *	remove fnode from provision list for p in hash table
-	 */
-	p = fnode->prov_list;
-	while (p != NULL) {
-		p_tmp = p;
-		pnode = p->pnode;
-		if (pnode->next != NULL) {
-			pnode->next->last = pnode->last;
 		}
-		if (pnode->last != NULL) {
-			pnode->last->next = pnode->next;
+		fnode->req_list = NULL;
+
+		/*
+		 * for each provision of fnode -> p
+		 *	remove fnode from provision list for p in hash table
+		 */
+		p = fnode->prov_list;
+		while (p != NULL) {
+			p_tmp = p;
+			pnode = p->pnode;
+			if (pnode->next != NULL) {
+				pnode->next->last = pnode->last;
+			}
+			if (pnode->last != NULL) {
+				pnode->last->next = pnode->next;
+			}
+			free(pnode);
+			p = p->next;
+			free(p_tmp);
 		}
-		free(pnode);
-		p = p->next;
-		free(p_tmp);
+		fnode->prov_list = NULL;
 	}
-	fnode->prov_list = NULL;
 
 	/* do_it(fnode) */
 	DPRINTF((stderr, "next do: "));
 
 	/* if we were already in progress, don't print again */
 	if (was_set == 0 && skip_ok(fnode) && keep_ok(fnode))
-		printf("%s\n", fnode->filename);
+		printf("%s%s", fnode->filename, parallel ? " " : "\n");
 	
 	if (fnode->next != NULL) {
 		fnode->next->last = fnode->last;
@@ -781,6 +810,96 @@
 #endif
 }
 
+static bool
+unsatisfied_req(const struct filenode *fnode)
+{
+	const Hash_Entry *entry;
+	const provnode *head;
+	const f_reqnode *r;
+	int ndeps = 0;
+
+	for (r = fnode->req_list; r != NULL; r = r->next) {
+		entry = r->entry;
+		head = Hash_GetValue(entry);
+		if (head == NULL) {
+			warnx("requirement `%s' in file `%s' has no providers.",
+			    Hash_GetKey(entry), fnode->filename);
+			continue;
+		}
+
+		for (head = head->next; head != NULL; head = head->next) {
+			/*
+			 * Ignore dependencies handled in previous runs,
+			 * but not those handled in the current one.  Increase
+			 * current generation counter, emit newline, and go
+			 * around.
+			 */
+			if (head->fnode->generation != 0 &&
+			    head->fnode->generation < generation) {
+				DPRINTF((stderr, "%s had dependency %s handled "
+				    "in generation %d\n",
+				    fnode->filename, head->fnode->filename,
+				    head->fnode->generation));
+			} else {
+				DPRINTF((stderr, "%s has dependency %s\n",
+				    fnode->filename, head->fnode->filename));
+				//return (TRUE);
+				ndeps++;
+			}
+		}
+	}
+
+	if (ndeps > 0)
+		return (TRUE);
+
+	return (FALSE);
+}
+
+static void
+generate_parallel(void)
+{
+	static filenode *fnode, *fnode_next;
+	int nodes_done;
+	bool ignore_deps;
+
+	/*
+	 * Iterate over nodes, printing out leaf ones.  After each pass
+	 * emit "\n" to mark dependency of the following nodes on the
+	 * preceding ones.  Continue until there are no nodes left.
+	 */
+	ignore_deps = FALSE;
+	generation = 1;
+	do {
+		nodes_done = 0;
+		for (fnode = fn_head->next; fnode != NULL; fnode = fnode_next) {
+			fnode_next = fnode->next;
+			if (ignore_deps) {
+				warnx("cycle detected; ignoring dependencies "
+				    "for %s", fnode->filename);
+				ignore_deps = FALSE;
+			} else if (unsatisfied_req(fnode)) {
+				DPRINTF((stderr, "%s has dependencies; "
+				    "skipping\n", fnode->filename));
+				continue;
+			}
+			nodes_done++;
+			do_file(fnode);
+		}
+		generation++;
+		if (nodes_done > 0) {
+			printf("\n");
+		} else {
+			/*
+			 * There were no leaf nodes, ie nodes with no
+			 * dependencies.  This means the graph is cyclic.
+			 * It's hard to handle this in a sensible way; just
+			 * ignore dependencies for the next node and try again.
+			 */
+			ignore_deps = TRUE;
+		}
+	} while (fn_head->next != NULL);
+}
+
 static void
 generate_ordering(void)
 {