🚀 go-pugleaf

I have a bug-fix for GNU Make 3.57.  This fix works on BSD machines, and I don't
expect any problems with it on other machines (so long as "qsort" exists in the
standard form).  For really large makefiles (such as those sometimes automatically
generated for large projects), GNUMake spends most of its time in a procedure
calls "record files", and it spends most of its time eliminating duplicates
from lists of dependencies.  I have modified this code (in read.c) to use qsort, 
and in my case I gained a 5x performance improvement.  The diffs follow.

	Carl Staelin
	staelin@princeton.edu

% diff read.c.old read.c.new
98a99,110
> /*
>  * compare two dep's (using lexicographic comparison of the names)
>  * 
>  * used in record_files
>  */
> int dep_compare (a, b)
> char *a;
> char *b;
> {
>   return strcmp (dep_name (*(struct dep **)a), dep_name(*(struct dep **)b));
> }
> 
982c994
< 	  /* Make sure that no dependencies are repeated.  This does not
---
>  	  /* Make sure that no dependencies are repeated.  This does not
985,1006c997,1037
< 	  for (d = f->deps; d != 0; d = d->next)
< 	    {
< 	      struct dep *last, *next;
< 	      last = d;
< 	      next = d->next;
< 	      while (next != 0)
< 		if (streq (dep_name (d), dep_name (next)))
< 		  {
< 		    struct dep *n = next->next;
< 		    last->next = n;
< 		    if (next->name != 0 && next->name != d->name)
< 		      free (next->name);
< 		    if (next != d)
< 		      free ((char *) next);
< 		    next = n;
< 		  }
< 		else
< 		  {
< 		    last = next;
< 		    next = next->next;
< 		  }
< 	    }
---
> 	  {
> 	    int count;
> 	    register struct dep **array;
> 	 
> 	    for (count = 0, d = f->deps ; d ; d = d->next)
> 	      count ++;
> 
> 	    if (count)
> 	      {
> 		int dummy;
> 
> 		array = (struct dep **)xmalloc (count * sizeof (struct dep *));
> 
> 		for (dummy = 0, d = f->deps ; d ; dummy ++, d = d->next)
> 		  array[dummy] = d;
> 
> 		qsort ((char *)array, count, sizeof(struct dep *), dep_compare);
> 
> 		f->deps = d = array[0];
> 		d->next = (struct dep *)0;
> 
> 		for (dummy = 1 ; dummy < count ; dummy ++)
> 		  if (streq (dep_name(d), dep_name(array[dummy])))
> 		    {
> 		      if (array[dummy]->name && array[dummy]->name != d->name)
> 			free (array[dummy]->name);
> 		      if (array[dummy] != d)
> 			free (array[dummy]);
> 		    }
> 		  else
> 		    {
> 		      d->next = array[dummy];
> 		      d = array[dummy];
> 		      d->next = (struct dep *)0;
> 		    }
> 		
> 		free (array);
> 	      }
> 
> 	  }
>