Re: parallelized 'ld'?

[DJ Delorie <dj at redhat dot com>]

Current patch.  Ok yet?

Index: bfd-in.h
===================================================================
RCS file: /cvs/uberbaum/./bfd/bfd-in.h,v
retrieving revision 1.80
diff -p -C2 -r1.80 bfd-in.h
*** bfd-in.h	21 May 2004 15:38:01 -0000	1.80
--- bfd-in.h	10 Jun 2004 19:14:12 -0000
*************** struct bfd_hash_table
*** 372,375 ****
--- 372,377 ----
    /* The number of slots in the hash table.  */
    unsigned int size;
+   /* The number of entries in the hash table.  */
+   unsigned int count;
    /* A function used to create new elements in the hash table.  The
       first entry is itself a pointer to an element.  When this
Index: bfd-in2.h
===================================================================
RCS file: /cvs/uberbaum/./bfd/bfd-in2.h,v
retrieving revision 1.279
diff -p -C2 -r1.279 bfd-in2.h
*** bfd-in2.h	28 May 2004 12:32:01 -0000	1.279
--- bfd-in2.h	10 Jun 2004 19:14:13 -0000
*************** struct bfd_hash_table
*** 379,382 ****
--- 379,384 ----
    /* The number of slots in the hash table.  */
    unsigned int size;
+   /* The number of entries in the hash table.  */
+   unsigned int count;
    /* A function used to create new elements in the hash table.  The
       first entry is itself a pointer to an element.  When this
Index: hash.c
===================================================================
RCS file: /cvs/uberbaum/./bfd/hash.c,v
retrieving revision 1.13
diff -p -C2 -r1.13 hash.c
*** hash.c	24 May 2004 07:49:10 -0000	1.13
--- hash.c	10 Jun 2004 19:14:13 -0000
*************** SUBSUBSECTION
*** 301,305 ****
  
  /* The default number of entries to use when creating a hash table.  */
! #define DEFAULT_SIZE 4051
  static size_t bfd_default_hash_table_size = DEFAULT_SIZE;
  
--- 301,371 ----
  
  /* The default number of entries to use when creating a hash table.  */
! #define DEFAULT_SIZE (4093)
! 
! /* The following function returns a nearest prime number which is
!    greater than N, and near a power of two.  Copied from libiberty.  */
! 
! static unsigned long
! higher_prime_number (n)
!      unsigned long n;
! {
!   /* These are primes that are near, but slightly smaller than, a
!      power of two.  */
!   static const unsigned long primes[] = {
!     (unsigned long) 7,
!     (unsigned long) 13,
!     (unsigned long) 31,
!     (unsigned long) 61,
!     (unsigned long) 127,
!     (unsigned long) 251,
!     (unsigned long) 509,
!     (unsigned long) 1021,
!     (unsigned long) 2039,
!     (unsigned long) 4093,
!     (unsigned long) 8191,
!     (unsigned long) 16381,
!     (unsigned long) 32749,
!     (unsigned long) 65521,
!     (unsigned long) 131071,
!     (unsigned long) 262139,
!     (unsigned long) 524287,
!     (unsigned long) 1048573,
!     (unsigned long) 2097143,
!     (unsigned long) 4194301,
!     (unsigned long) 8388593,
!     (unsigned long) 16777213,
!     (unsigned long) 33554393,
!     (unsigned long) 67108859,
!     (unsigned long) 134217689,
!     (unsigned long) 268435399,
!     (unsigned long) 536870909,
!     (unsigned long) 1073741789,
!     (unsigned long) 2147483647,
! 					/* 4294967291L */
!     ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
!   };
! 
!   const unsigned long *low = &primes[0];
!   const unsigned long *high = &primes[sizeof(primes) / sizeof(primes[0])];
! 
!   while (low != high)
!     {
!       const unsigned long *mid = low + (high - low) / 2;
!       if (n >= *mid)
! 	low = mid + 1;
!       else
! 	high = mid;
!     }
! 
!   /* If we've run out of primes, abort.  */
!   if (n > *low)
!     {
!       fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
!       abort ();
!     }
! 
!   return *low;
! }
! 
  static size_t bfd_default_hash_table_size = DEFAULT_SIZE;
  
*************** bfd_hash_table_init_n (table, newfunc, s
*** 333,336 ****
--- 399,403 ----
    memset ((PTR) table->table, 0, alloc);
    table->size = size;
+   table->count = 0;
    table->newfunc = newfunc;
    return TRUE;
*************** bfd_hash_lookup (table, string, create, 
*** 403,406 ****
--- 470,474 ----
    if (hashp == (struct bfd_hash_entry *) NULL)
      return (struct bfd_hash_entry *) NULL;
+   table->count ++;
    if (copy)
      {
*************** bfd_hash_lookup (table, string, create, 
*** 422,425 ****
--- 490,525 ----
    table->table[index] = hashp;
  
+   if (table->count > table->size * 3 / 4)
+     {
+       int newsize = higher_prime_number (table->size);
+       struct bfd_hash_entry **newtable, *he;
+       unsigned int hi;
+       unsigned int alloc;
+ 
+       alloc = newsize * sizeof (struct bfd_hash_entry *);
+ 
+       newtable = ((struct bfd_hash_entry **)
+ 		  objalloc_alloc ((struct objalloc *) table->memory, alloc));
+       memset ((PTR) newtable, 0, alloc);
+ 
+       for (hi = 0; hi < table->size; hi ++)
+ 	while (table->table[hi])
+ 	  {
+ 	    struct bfd_hash_entry *chain = table->table[hi];
+ 	    struct bfd_hash_entry *chain_end = chain;
+ 	    int index;
+ 
+ 	    while (chain_end->next && chain_end->next->hash == chain->hash)
+ 	      chain_end = chain_end->next; 
+ 
+ 	    table->table[hi] = chain_end->next;
+ 	    index = chain->hash % newsize;
+ 	    chain_end->next = newtable[index];
+ 	    newtable[index] = chain;
+ 	  }
+       table->table = newtable;
+       table->size = newsize;
+     }
+ 
    return hashp;
  }