tidy hashtab.c

[Richard Henderson <rth at redhat dot com>]

No functional changes, just rearranging things such that it's
a bit clearer what's going on, and so that my next patch doesn't
have to touch as much.


r~



        * hashtab.c (htab_size): Move to top of file; mark inline.
        (htab_elements): Likewise.
        (htab_mod, htab_mod_m2): New.
        (htab_delete): Refactor htab->size and htab->entries.
        (htab_empty): Likewise.
        (find_empty_slot_for_expand): Use htab_size, htab_mod, htab_mod_m2.
        (htab_find_with_hash, htab_find_slot_with_hash): Likewise.
        (htab_clear_slot): Use htab_size, htab_elements.
        (htab_traverse_noresize, htab_traverse): Likewise.

Index: hashtab.c
===================================================================
RCS file: /cvs/gcc/gcc/libiberty/hashtab.c,v
retrieving revision 1.38
diff -c -p -d -r1.38 hashtab.c
*** hashtab.c	30 Oct 2003 17:00:51 -0000	1.38
--- hashtab.c	1 Apr 2004 01:35:15 -0000
*************** eq_pointer (p1, p2)
*** 159,164 ****
--- 159,202 ----
    return p1 == p2;
  }
  
+ /* Return the current size of given hash table. */
+ 
+ inline size_t
+ htab_size (htab)
+      htab_t htab;
+ {
+   return htab->size;
+ }
+ 
+ /* Return the current number of elements in given hash table. */
+ 
+ inline size_t
+ htab_elements (htab)
+      htab_t htab;
+ {
+   return htab->n_elements - htab->n_deleted;
+ }
+ 
+ /* Compute the primary hash for HASH given HTAB's current size.  */
+ 
+ static inline hashval_t
+ htab_mod (hash, htab)
+      hashval_t hash;
+      htab_t htab;
+ {
+   return hash % htab_size (htab);
+ }
+ 
+ /* Compute the secondary hash for HASH given HTAB's current size.  */
+ 
+ static inline hashval_t
+ htab_mod_m2 (hash, htab)
+      hashval_t hash;
+      htab_t htab;
+ {
+   return 1 + hash % (htab_size (htab) - 2);
+ }
+ 
  /* 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
*************** void
*** 282,303 ****
  htab_delete (htab)
       htab_t htab;
  {
    int i;
  
    if (htab->del_f)
!     for (i = htab->size - 1; i >= 0; i--)
!       if (htab->entries[i] != EMPTY_ENTRY
! 	  && htab->entries[i] != DELETED_ENTRY)
! 	(*htab->del_f) (htab->entries[i]);
  
    if (htab->free_f != NULL)
      {
!       (*htab->free_f) (htab->entries);
        (*htab->free_f) (htab);
      }
    else if (htab->free_with_arg_f != NULL)
      {
!       (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries);
        (*htab->free_with_arg_f) (htab->alloc_arg, htab);
      }
  }
--- 320,342 ----
  htab_delete (htab)
       htab_t htab;
  {
+   size_t size = htab_size (htab);
+   PTR *entries = htab->entries;
    int i;
  
    if (htab->del_f)
!     for (i = size - 1; i >= 0; i--)
!       if (entries[i] != EMPTY_ENTRY && entries[i] != DELETED_ENTRY)
! 	(*htab->del_f) (entries[i]);
  
    if (htab->free_f != NULL)
      {
!       (*htab->free_f) (entries);
        (*htab->free_f) (htab);
      }
    else if (htab->free_with_arg_f != NULL)
      {
!       (*htab->free_with_arg_f) (htab->alloc_arg, entries);
        (*htab->free_with_arg_f) (htab->alloc_arg, htab);
      }
  }
*************** void
*** 308,322 ****
  htab_empty (htab)
       htab_t htab;
  {
    int i;
  
    if (htab->del_f)
!     for (i = htab->size - 1; i >= 0; i--)
!       if (htab->entries[i] != EMPTY_ENTRY
! 	  && htab->entries[i] != DELETED_ENTRY)
! 	(*htab->del_f) (htab->entries[i]);
  
!   memset (htab->entries, 0, htab->size * sizeof (PTR));
  }
  
  /* Similar to htab_find_slot, but without several unwanted side effects:
--- 347,362 ----
  htab_empty (htab)
       htab_t htab;
  {
+   size_t size = htab_size (htab);
+   PTR *entries = htab->entries;
    int i;
  
    if (htab->del_f)
!     for (i = size - 1; i >= 0; i--)
!       if (entries[i] != EMPTY_ENTRY && entries[i] != DELETED_ENTRY)
! 	(*htab->del_f) (entries[i]);
  
!   memset (entries, 0, size * sizeof (PTR));
  }
  
  /* Similar to htab_find_slot, but without several unwanted side effects:
*************** find_empty_slot_for_expand (htab, hash)
*** 331,338 ****
       htab_t htab;
       hashval_t hash;
  {
!   size_t size = htab->size;
!   unsigned int index = hash % size;
    PTR *slot = htab->entries + index;
    hashval_t hash2;
  
--- 371,378 ----
       htab_t htab;
       hashval_t hash;
  {
!   hashval_t index = htab_mod (hash, htab);
!   size_t size = htab_size (htab);
    PTR *slot = htab->entries + index;
    hashval_t hash2;
  
*************** find_empty_slot_for_expand (htab, hash)
*** 341,347 ****
    else if (*slot == DELETED_ENTRY)
      abort ();
  
!   hash2 = 1 + hash % (size - 2);
    for (;;)
      {
        index += hash2;
--- 381,387 ----
    else if (*slot == DELETED_ENTRY)
      abort ();
  
!   hash2 = htab_mod_m2 (hash, htab);
    for (;;)
      {
        index += hash2;
*************** htab_find_with_hash (htab, element, hash
*** 431,452 ****
       const PTR element;
       hashval_t hash;
  {
!   unsigned int index;
!   hashval_t hash2;
    size_t size;
    PTR entry;
  
    htab->searches++;
!   size = htab->size;
!   index = hash % size;
  
    entry = htab->entries[index];
    if (entry == EMPTY_ENTRY
        || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
      return entry;
  
!   hash2 = 1 + hash % (size - 2);
! 
    for (;;)
      {
        htab->collisions++;
--- 471,490 ----
       const PTR element;
       hashval_t hash;
  {
!   hashval_t index, hash2;
    size_t size;
    PTR entry;
  
    htab->searches++;
!   size = htab_size (htab);
!   index = htab_mod (hash, htab);
  
    entry = htab->entries[index];
    if (entry == EMPTY_ENTRY
        || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
      return entry;
  
!   hash2 = htab_mod_m2 (hash, htab);
    for (;;)
      {
        htab->collisions++;
*************** htab_find_slot_with_hash (htab, element,
*** 488,504 ****
       enum insert_option insert;
  {
    PTR *first_deleted_slot;
!   unsigned int index;
!   hashval_t hash2;
    size_t size;
    PTR entry;
  
!   if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
!       && htab_expand (htab) == 0)
!     return NULL;
  
!   size = htab->size;
!   index = hash % size;
  
    htab->searches++;
    first_deleted_slot = NULL;
--- 526,544 ----
       enum insert_option insert;
  {
    PTR *first_deleted_slot;
!   hashval_t index, hash2;
    size_t size;
    PTR entry;
  
!   size = htab_size (htab);
!   if (insert == INSERT && size * 3 <= htab->n_elements * 4)
!     {
!       if (htab_expand (htab) == 0)
! 	return NULL;
!       size = htab_size (htab);
!     }
  
!   index = htab_mod (hash, htab);
  
    htab->searches++;
    first_deleted_slot = NULL;
*************** htab_find_slot_with_hash (htab, element,
*** 511,517 ****
    else if ((*htab->eq_f) (entry, element))
      return &htab->entries[index];
        
!   hash2 = 1 + hash % (size - 2);
    for (;;)
      {
        htab->collisions++;
--- 551,557 ----
    else if ((*htab->eq_f) (entry, element))
      return &htab->entries[index];
        
!   hash2 = htab_mod_m2 (hash, htab);
    for (;;)
      {
        htab->collisions++;
*************** htab_clear_slot (htab, slot)
*** 590,596 ****
       htab_t htab;
       PTR *slot;
  {
!   if (slot < htab->entries || slot >= htab->entries + htab->size
        || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
      abort ();
  
--- 630,636 ----
       htab_t htab;
       PTR *slot;
  {
!   if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
        || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
      abort ();
  
*************** htab_traverse_noresize (htab, callback, 
*** 616,622 ****
    PTR *limit;
  
    slot = htab->entries;
!   limit = slot + htab->size;
  
    do
      {
--- 656,662 ----
    PTR *limit;
  
    slot = htab->entries;
!   limit = slot + htab_size (htab);
  
    do
      {
*************** htab_traverse (htab, callback, info)
*** 638,665 ****
       htab_trav callback;
       PTR info;
  {
!   if ((htab->n_elements - htab->n_deleted) * 8 < htab->size)
      htab_expand (htab);
  
    htab_traverse_noresize (htab, callback, info);
- }
- 
- /* Return the current size of given hash table. */
- 
- size_t
- htab_size (htab)
-      htab_t htab;
- {
-   return htab->size;
- }
- 
- /* Return the current number of elements in given hash table. */
- 
- size_t
- htab_elements (htab)
-      htab_t htab;
- {
-   return htab->n_elements - htab->n_deleted;
  }
  
  /* Return the fraction of fixed collisions during all work with given
--- 678,687 ----
       htab_trav callback;
       PTR info;
  {
!   if (htab_elements (htab) * 8 < htab_size (htab))
      htab_expand (htab);
  
    htab_traverse_noresize (htab, callback, info);
  }
  
  /* Return the fraction of fixed collisions during all work with given