Back to index

cell-binutils  2.17cvs20070401
Defines | Typedefs | Enumerations | Functions | Variables
hashtab.h File Reference
#include "ansidecl.h"
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Defines

#define GTY(X)
#define HTAB_EMPTY_ENTRY   ((PTR) 0)
#define HTAB_DELETED_ENTRY   ((PTR) 1)
#define iterative_hash_object(OB, INIT)   iterative_hash (&OB, sizeof (OB), INIT)

Typedefs

typedef unsigned int hashval_t
typedef hashval_t(* htab_hash )(const void *)
typedef int(* htab_eq )(const void *, const void *)
typedef void(* htab_del )(void *)
typedef int(* htab_trav )(void **, void *)
typedef void *(* htab_alloc )(size_t, size_t)
typedef void(* htab_free )(void *)
typedef void *(* htab_alloc_with_arg )(void *, size_t, size_t)
typedef void(* htab_free_with_arg )(void *, void *)
typedef struct htab * htab_t

Enumerations

enum  insert_option { NO_INSERT, INSERT }

Functions

struct htab GTY (())
htab_t htab_create_alloc (size_t, htab_hash, htab_eq, htab_del, htab_alloc, htab_free)
htab_t htab_create_alloc_ex (size_t, htab_hash, htab_eq, htab_del, void *, htab_alloc_with_arg, htab_free_with_arg)
htab_t htab_create (size_t, htab_hash, htab_eq, htab_del)
htab_t htab_try_create (size_t, htab_hash, htab_eq, htab_del)
void htab_set_functions_ex (htab_t, htab_hash, htab_eq, htab_del, void *, htab_alloc_with_arg, htab_free_with_arg)
void htab_delete (htab_t)
void htab_empty (htab_t)
void * htab_find (htab_t, const void *)
void ** htab_find_slot (htab_t, const void *, enum insert_option)
void * htab_find_with_hash (htab_t, const void *, hashval_t)
void ** htab_find_slot_with_hash (htab_t, const void *, hashval_t, enum insert_option)
void htab_clear_slot (htab_t, void **)
void htab_remove_elt (htab_t, void *)
void htab_remove_elt_with_hash (htab_t, void *, hashval_t)
void htab_traverse (htab_t, htab_trav, void *)
void htab_traverse_noresize (htab_t, htab_trav, void *)
size_t htab_size (htab_t)
size_t htab_elements (htab_t)
double htab_collisions (htab_t)
hashval_t htab_hash_string (const void *)
hashval_t iterative_hash (const void *, size_t, hashval_t)

Variables

htab_hash htab_hash_pointer
htab_eq htab_eq_pointer

Define Documentation

#define GTY (   X)

Definition at line 42 of file hashtab.h.

#define HTAB_DELETED_ENTRY   ((PTR) 1)

Definition at line 91 of file hashtab.h.

#define HTAB_EMPTY_ENTRY   ((PTR) 0)

Definition at line 86 of file hashtab.h.

#define iterative_hash_object (   OB,
  INIT 
)    iterative_hash (&OB, sizeof (OB), INIT)

Definition at line 200 of file hashtab.h.


Typedef Documentation

Definition at line 46 of file hashtab.h.

typedef void*(* htab_alloc)(size_t, size_t)

Definition at line 74 of file hashtab.h.

typedef void*(* htab_alloc_with_arg)(void *, size_t, size_t)

Definition at line 81 of file hashtab.h.

typedef void(* htab_del)(void *)

Definition at line 62 of file hashtab.h.

typedef int(* htab_eq)(const void *, const void *)

Definition at line 58 of file hashtab.h.

typedef void(* htab_free)(void *)

Definition at line 77 of file hashtab.h.

typedef void(* htab_free_with_arg)(void *, void *)

Definition at line 82 of file hashtab.h.

typedef hashval_t(* htab_hash)(const void *)

Definition at line 51 of file hashtab.h.

typedef struct htab* htab_t

Definition at line 144 of file hashtab.h.

typedef int(* htab_trav)(void **, void *)

Definition at line 68 of file hashtab.h.


Enumeration Type Documentation

Enumerator:
NO_INSERT 
INSERT 

Definition at line 147 of file hashtab.h.


Function Documentation

struct splay_tree_s GTY ( ()  ) [read]

Definition at line 99 of file hashtab.h.

{
  /* Pointer to hash function.  */
  htab_hash hash_f;

  /* Pointer to comparison function.  */
  htab_eq eq_f;

  /* Pointer to cleanup function.  */
  htab_del del_f;

  /* Table itself.  */
  void ** GTY ((use_param, length ("%h.size"))) entries;

  /* Current size (in entries) of the hash table.  */
  size_t size;

  /* Current number of elements including also deleted elements.  */
  size_t n_elements;

  /* Current number of deleted elements in the table.  */
  size_t n_deleted;

  /* The following member is used for debugging. Its value is number
     of all calls of `htab_find_slot' for the hash table. */
  unsigned int searches;

  /* 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;

  /* Pointers to allocate/free functions.  */
  htab_alloc alloc_f;
  htab_free free_f;

  /* Alternate allocate/free functions, which take an extra argument.  */
  void * GTY((skip)) alloc_arg;
  htab_alloc_with_arg alloc_with_arg_f;
  htab_free_with_arg free_with_arg_f;

  /* Current size (in entries) of the hash table, as an index into the
     table of primes.  */
  unsigned int size_prime_index;
};
void htab_clear_slot ( htab_t  ,
void **   
)

Here is the caller graph for this function:

Definition at line 772 of file hashtab.c.

{
  if (htab->searches == 0)
    return 0.0;

  return (double) htab->collisions / (double) htab->searches;
}

Definition at line 372 of file hashtab.c.

{
  return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 288 of file hashtab.c.

{
  htab_t result;
  unsigned int size_prime_index;

  size_prime_index = higher_prime_index (size);
  size = prime_tab[size_prime_index].prime;

  result = (htab_t) (*alloc_f) (1, sizeof (struct htab));
  if (result == NULL)
    return NULL;
  result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR));
  if (result->entries == NULL)
    {
      if (free_f != NULL)
       (*free_f) (result);
      return NULL;
    }
  result->size = size;
  result->size_prime_index = size_prime_index;
  result->hash_f = hash_f;
  result->eq_f = eq_f;
  result->del_f = del_f;
  result->alloc_f = alloc_f;
  result->free_f = free_f;
  return result;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 321 of file hashtab.c.

{
  htab_t result;
  unsigned int size_prime_index;

  size_prime_index = higher_prime_index (size);
  size = prime_tab[size_prime_index].prime;

  result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab));
  if (result == NULL)
    return NULL;
  result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR));
  if (result->entries == NULL)
    {
      if (free_f != NULL)
       (*free_f) (alloc_arg, result);
      return NULL;
    }
  result->size = size;
  result->size_prime_index = size_prime_index;
  result->hash_f = hash_f;
  result->eq_f = eq_f;
  result->del_f = del_f;
  result->alloc_arg = alloc_arg;
  result->alloc_with_arg_f = alloc_f;
  result->free_with_arg_f = free_f;
  return result;
}

Here is the call graph for this function:

void htab_delete ( htab_t  )

Definition at line 387 of file hashtab.c.

{
  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] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_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);
    }
}

Here is the caller graph for this function:

Definition at line 231 of file hashtab.c.

{
  return htab_elements (htab);
}
void htab_empty ( htab_t  )

Definition at line 413 of file hashtab.c.

{
  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] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
       (*htab->del_f) (entries[i]);

  /* Instead of clearing megabyte, downsize the table.  */
  if (size > 1024*1024 / sizeof (PTR))
    {
      int nindex = higher_prime_index (1024 / sizeof (PTR));
      int nsize = prime_tab[nindex].prime;

      if (htab->free_f != NULL)
       (*htab->free_f) (htab->entries);
      else if (htab->free_with_arg_f != NULL)
       (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries);
      if (htab->alloc_with_arg_f != NULL)
       htab->entries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
                                                     sizeof (PTR *));
      else
       htab->entries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
     htab->size = nsize;
     htab->size_prime_index = nindex;
    }
  else
    memset (entries, 0, size * sizeof (PTR));
  htab->n_deleted = 0;
  htab->n_elements = 0;
}

Here is the call graph for this function:

void* htab_find ( htab_t  ,
const void *   
)

Here is the caller graph for this function:

void** htab_find_slot ( htab_t  ,
const void *  ,
enum  insert_option 
)

Here is the caller graph for this function:

void** htab_find_slot_with_hash ( htab_t  ,
const void *  ,
hashval_t  ,
enum  insert_option 
)

Here is the caller graph for this function:

void* htab_find_with_hash ( htab_t  ,
const void *  ,
hashval_t   
)

Here is the caller graph for this function:

Here is the caller graph for this function:

void htab_remove_elt ( htab_t  ,
void *   
)
void htab_remove_elt_with_hash ( htab_t  ,
void *  ,
hashval_t   
)

Here is the caller graph for this function:

Definition at line 221 of file hashtab.c.

{
  return htab_size (htab);
}
void htab_traverse ( htab_t  ,
htab_trav  ,
void *   
)

Here is the caller graph for this function:

void htab_traverse_noresize ( htab_t  ,
htab_trav  ,
void *   
)

Here is the caller graph for this function:

Definition at line 378 of file hashtab.c.

{
  return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
}

Here is the call graph for this function:

Here is the caller graph for this function:

hashval_t iterative_hash ( const void *  ,
size_t  ,
hashval_t   
)

Here is the caller graph for this function:


Variable Documentation

Definition at line 80 of file hashtab.c.

Definition at line 79 of file hashtab.c.