[RFA:] libiberty/hashtab: Introduce "failing" memory allocation API

[Hans-Peter Nilsson <hp at bitrange dot com>]

The BFD library in binutils is by convention not allowed to use the
xmalloc and xcalloc functions; memory allocation failure should be handled
more gracefully.  While this does not seem to be slavishly followed,
introducing new offenders would just worsen the situation.  When
introducing use of hashtab, there has to be non-xcalloc allocation
machinery.  I thought for a minute about how to best augment the API to
introduce non-failing allocation, and this seemed to be the simplest way,
while having no constraining future consequences on maintenance.
There might be a better name for the creator, but to me htab_try_create
seemed to be the most appropriate while still usefully short.

Assuming the bootstrap in progress on i686-pc-linux-gnulibc1 shows no test
regressions, Ok to commit?  (To gcc *and* src of course.)

libiberty:
	* hashtab.c (htab_expand): Change to return int.  Use calloc or
 	xcalloc depending on htab->return_allocation_failure.  Return zero
 	if calloc fails.
	(htab_create): Update comment to cover memory allocation.
	(htab_try_create): New.
	(htab_find_slot_with_hash): Return NULL if htab_expand fails.
  	Update comment to cover this.
	Change all "void *" to PTR.

include:
	* hashtab.h (struct htab): Add member return_allocation_failure.
	(htab_try_create): New prototype.  Mention which functions may
	return NULL when this is used.

Index: hashtab.h
===================================================================
RCS file: /cvs/gcc/egcs/include/hashtab.h,v
retrieving revision 1.9
diff -p -c -r1.9 hashtab.h
*** hashtab.h	2000/11/03 20:23:00	1.9
--- hashtab.h	2000/11/03 21:58:29
*************** struct htab
*** 98,103 ****
--- 98,107 ----
    /* The following member is used for debugging.  Its value is number
       of collisions fixed for time of work with the hash table. */
    unsigned int collisions;
+ 
+   /* This is non-zero if we are allowed to return NULL for function calls
+      that allocate memory.  */
+   int return_allocation_failure;
  };
  
  typedef struct htab *htab_t;
*************** enum insert_option {NO_INSERT, INSERT};
*** 108,113 ****
--- 112,123 ----
  /* The prototypes of the package functions. */
  
  extern htab_t	htab_create	PARAMS ((size_t, htab_hash,
+ 					 htab_eq, htab_del));
+ 
+ /* This function is like htab_create, but may return NULL if memory
+    allocation fails, and also signals that htab_find_slot_with_hash and
+    htab_find_slot are allowed to return NULL when inserting.  */
+ extern htab_t	htab_try_create	PARAMS ((size_t, htab_hash,
  					 htab_eq, htab_del));
  extern void	htab_delete	PARAMS ((htab_t));
  extern void	htab_empty	PARAMS ((htab_t));
Index: hashtab.c
===================================================================
RCS file: /cvs/gcc/egcs/libiberty/hashtab.c,v
retrieving revision 1.17
diff -p -c -r1.17 hashtab.c
*** hashtab.c	2000/11/03 20:26:51	1.17
--- hashtab.c	2000/11/03 22:04:56
*************** Boston, MA 02111-1307, USA.  */
*** 62,68 ****
  static unsigned long higher_prime_number PARAMS ((unsigned long));
  static hashval_t hash_pointer PARAMS ((const void *));
  static int eq_pointer PARAMS ((const void *, const void *));
! static void htab_expand PARAMS ((htab_t));
  static PTR *find_empty_slot_for_expand  PARAMS ((htab_t, hashval_t));
  
  /* At some point, we could make these be NULL, and modify the
--- 62,68 ----
  static unsigned long higher_prime_number PARAMS ((unsigned long));
  static hashval_t hash_pointer PARAMS ((const void *));
  static int eq_pointer PARAMS ((const void *, const void *));
! static int htab_expand PARAMS ((htab_t));
  static PTR *find_empty_slot_for_expand  PARAMS ((htab_t, hashval_t));
  
  /* At some point, we could make these be NULL, and modify the
*************** eq_pointer (p1, p2)
*** 124,130 ****
  /* This function creates table with length slightly longer than given
     source length.  Created hash table is initiated as empty (all the
     hash table entries are EMPTY_ENTRY).  The function returns the
!    created hash table.  */
  
  htab_t
  htab_create (size, hash_f, eq_f, del_f)
--- 124,130 ----
  /* This function creates table with length slightly longer than given
     source length.  Created hash table is initiated as empty (all the
     hash table entries are EMPTY_ENTRY).  The function returns the
!    created hash table.  Memory allocation must not fail.  */
  
  htab_t
  htab_create (size, hash_f, eq_f, del_f)
*************** htab_create (size, hash_f, eq_f, del_f)
*** 142,150 ****
--- 142,185 ----
    result->hash_f = hash_f;
    result->eq_f = eq_f;
    result->del_f = del_f;
+   result->return_allocation_failure = 0;
    return result;
  }
  
+ /* This function creates table with length slightly longer than given
+    source length.  The created hash table is initiated as empty (all the
+    hash table entries are EMPTY_ENTRY).  The function returns the created
+    hash table.  Memory allocation may fail; it may return NULL.  */
+ 
+ htab_t
+ htab_try_create (size, hash_f, eq_f, del_f)
+      size_t size;
+      htab_hash hash_f;
+      htab_eq eq_f;
+      htab_del del_f;
+ {
+   htab_t result;
+ 
+   size = higher_prime_number (size);
+   result = (htab_t) calloc (1, sizeof (struct htab));
+   if (result == NULL)
+     return NULL;
+ 
+   result->entries = (PTR *) calloc (size, sizeof (PTR));
+   if (result->entries == NULL)
+     {
+       free (result);
+       return NULL;
+     }
+ 
+   result->size = size;
+   result->hash_f = hash_f;
+   result->eq_f = eq_f;
+   result->del_f = del_f;
+   result->return_allocation_failure = 1;
+   return result;
+ }
+ 
  /* This function frees all memory allocated for given hash table.
     Naturally the hash table must already exist. */
  
*************** find_empty_slot_for_expand (htab, hash)
*** 216,224 ****
     entries and repeatedly inserts the table elements.  The occupancy
     of the table after the call will be about 50%.  Naturally the hash
     table must already exist.  Remember also that the place of the
!    table entries is changed.  */
  
! static void
  htab_expand (htab)
       htab_t htab;
  {
--- 251,261 ----
     entries and repeatedly inserts the table elements.  The occupancy
     of the table after the call will be about 50%.  Naturally the hash
     table must already exist.  Remember also that the place of the
!    table entries is changed.  If memory allocation failures are allowed,
!    this function will return zero, indicating that the table could not be
!    expanded.  If all goes well, it will return a non-zero value.  */
  
! static int
  htab_expand (htab)
       htab_t htab;
  {
*************** htab_expand (htab)
*** 230,236 ****
    olimit = oentries + htab->size;
  
    htab->size = higher_prime_number (htab->size * 2);
!   htab->entries = (PTR *) xcalloc (htab->size, sizeof (PTR *));
  
    htab->n_elements -= htab->n_deleted;
    htab->n_deleted = 0;
--- 267,282 ----
    olimit = oentries + htab->size;
  
    htab->size = higher_prime_number (htab->size * 2);
! 
!   if (htab->return_allocation_failure)
!     {
!       PTR *nentries = (PTR *) calloc (htab->size, sizeof (PTR *));
!       if (nentries == NULL)
! 	return 0;
!       htab->entries = nentries;
!     }
!   else
!     htab->entries = (PTR *) xcalloc (htab->size, sizeof (PTR *));
  
    htab->n_elements -= htab->n_deleted;
    htab->n_deleted = 0;
*************** htab_expand (htab)
*** 252,257 ****
--- 298,304 ----
    while (p < olimit);
  
    free (oentries);
+   return 1;
  }
  
  /* This function searches for a hash table entry equal to the given
*************** htab_find (htab, element)
*** 308,314 ****
     equal to the given element.  To delete an entry, call this with
     INSERT = 0, then call htab_clear_slot on the slot returned (possibly
     after doing some checks).  To insert an entry, call this with
!    INSERT = 1, then write the value you want into the returned slot.  */
  
  PTR *
  htab_find_slot_with_hash (htab, element, hash, insert)
--- 355,363 ----
     equal to the given element.  To delete an entry, call this with
     INSERT = 0, then call htab_clear_slot on the slot returned (possibly
     after doing some checks).  To insert an entry, call this with
!    INSERT = 1, then write the value you want into the returned slot.
!    When inserting an entry, NULL may be returned if memory allocation
!    fails.  */
  
  PTR *
  htab_find_slot_with_hash (htab, element, hash, insert)
*************** htab_find_slot_with_hash (htab, element,
*** 322,329 ****
    hashval_t hash2;
    size_t size;
  
!   if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4)
!     htab_expand (htab);
  
    size = htab->size;
    hash2 = 1 + hash % (size - 2);
--- 371,379 ----
    hashval_t hash2;
    size_t size;
  
!   if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
!       && htab_expand (htab) == 0)
!     return NULL;
  
    size = htab->size;
    hash2 = 1 + hash % (size - 2);

brgds, H-P