#include <stdlib.h>
#include <string.h>
#include "hash.h"
#include "util.h"

Include dependency graph for hash.c:

Functions
struct s_hash **	alloc_hash_table (void)

void	free_hash_table (struct s_hash **hash_table)

struct s_hash_iterator	start_hash_table_iterator (void)

struct s_hash *	get_next_hash (struct s_hash *hash_table, struct s_hash_iterator hash_iterator)

struct s_hash *	insert_in_hash_table (struct s_hash *hash_table, char name, int next_free_index)

struct s_hash *	get_hash_entry (struct s_hash *hash_table, char name)

int	hash_value (char *name)

void	get_hash_stats (struct s_hash *hash_table, char hash_table_name)

Function Documentation

struct s_hash** alloc_hash_table ( void )

Definition at line 7 of file hash.c.

                        {
 
     /* Creates a hash table with HASHSIZE different locations (hash values).   */
 
     struct s_hash **hash_table;
 
     hash_table = (struct s_hash **) my_calloc(sizeof(struct s_hash *),
             HASHSIZE);
     return (hash_table);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void free_hash_table ( struct s_hash ** hash_table )

Definition at line 18 of file hash.c.

                                                  {
 
     /* Frees all the storage associated with a hash table. */
 
     int i;
     struct s_hash *h_ptr, *temp_ptr;
 
     for (i = 0; i < HASHSIZE; i++) {
         h_ptr = hash_table[i];
         while (h_ptr != NULL) {
             free(h_ptr->name);
             temp_ptr = h_ptr->next;
             free(h_ptr);
             h_ptr = temp_ptr;
         }
     }
 
     free(hash_table);
 }

Here is the caller graph for this function:

struct s_hash* get_hash_entry	(	struct s_hash **	hash_table,
		char *	name
	)

Definition at line 119 of file hash.c.

                                                        {
 
     /* Returns the hash entry with this name, or NULL if there is no            *
      * corresponding entry.                                                     */
 
     int i;
     struct s_hash *h_ptr;
 
     i = hash_value(name);
     h_ptr = hash_table[i];
 
     while (h_ptr != NULL) {
         if (strcmp(h_ptr->name, name) == 0)
             return (h_ptr);
 
         h_ptr = h_ptr->next;
     }
 
     return (NULL);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void get_hash_stats	(	struct s_hash **	hash_table,
		char *	hash_table_name
	)

Definition at line 160 of file hash.c.

                                                                       {
 
     /* Checks to see how well elements are distributed within the hash table.     *
      * Will traverse through the hash_table and count the length of the linked    *
      * list. Will output the hash number, the number of array elements that are   *
      * NULL, the average number of linked lists and the maximum length of linked  * 
      * lists.                                     */
 
     int num_NULL = 0, total_elements = 0,  max_num = 0, curr_num;
     double avg_num = 0;
     int i;
     struct s_hash *h_ptr;
 
     for (i = 0; i<HASHSIZE; i++){
     h_ptr = hash_table[i];
     curr_num = 0;
     
     if (h_ptr == NULL)
         num_NULL++;     
     else{
         while (h_ptr != NULL){
             curr_num ++;        
             h_ptr = h_ptr->next;
         }
     }
 
     if (curr_num > max_num)
         max_num = curr_num;
     
     total_elements = total_elements + curr_num;
     }
 
     avg_num = (float) total_elements / ((float)HASHSIZE - (float)num_NULL);
     
     vpr_printf(TIO_MESSAGE_INFO, "\n");
     vpr_printf(TIO_MESSAGE_INFO, "The hash table '%s' is of size %d.\n",
         hash_table_name, HASHSIZE);
     vpr_printf(TIO_MESSAGE_INFO, "It has: %d keys that are never used; total of %d elements; an average linked-list length of %.1f; and a maximum linked-list length of %d.\n", 
         num_NULL, total_elements, avg_num, max_num); 
     vpr_printf(TIO_MESSAGE_INFO, "\n");
 }

Here is the caller graph for this function:

struct s_hash* get_next_hash	(	struct s_hash **	hash_table,
		struct s_hash_iterator *	hash_iterator
	)

Definition at line 51 of file hash.c.

                                                                                  {
 
     /* Returns the next occupied hash entry, and moves the iterator structure    *
      * forward so the next call gets the next entry.                             */
 
     int i;
     struct s_hash *h_ptr;
 
     i = hash_iterator->i;
     h_ptr = hash_iterator->h_ptr;
 
     while (h_ptr == NULL) {
         i++;
         if (i >= HASHSIZE)
             return (NULL); /* End of table */
 
         h_ptr = hash_table[i];
     }
 
     hash_iterator->h_ptr = h_ptr->next;
     hash_iterator->i = i;
     return (h_ptr);
 }

Here is the caller graph for this function:

int hash_value ( char * name )

Definition at line 140 of file hash.c.

                            {
     /* Creates a hash key from a character string.  The absolute value is taken  *
      * for the final val to compensate for long strlen that cause val to         *
      * overflow.                                     */
 
     int i;
     int val = 0, mult = 1;
 
     i = strlen(name);
     for (i = strlen(name) - 1; i >= 0; i--) {
         val += mult * ((int) name[i]);
         mult *= 7;
     }
     val += (int) name[0];
     val %= HASHSIZE;
     
     val = abs(val);
     return (val);
 }

Here is the caller graph for this function:

struct s_hash* insert_in_hash_table	(	struct s_hash **	hash_table,
		char *	name,
		int	next_free_index
	)

Definition at line 76 of file hash.c.

                              {
 
     /* Adds the string pointed to by name to the hash table, and returns the    *
      * hash structure created or updated.  If name is already in the hash table *
      * the count member of that hash element is incremented.  Otherwise a new   *
      * hash entry with a count of zero and an index of next_free_index is       *
      * created.                                                                 */
 
     int i;
     struct s_hash *h_ptr, *prev_ptr;
 
     i = hash_value(name);
     prev_ptr = NULL;
     h_ptr = hash_table[i];
 
     while (h_ptr != NULL) {
         if (strcmp(h_ptr->name, name) == 0) {
             h_ptr->count++;
             return (h_ptr);
         }
 
         prev_ptr = h_ptr;
         h_ptr = h_ptr->next;
     }
 
     /* Name string wasn't in the hash table.  Add it. */
 
     h_ptr = (struct s_hash *) my_malloc(sizeof(struct s_hash));
     if (prev_ptr == NULL) {
         hash_table[i] = h_ptr;
     } else {
         prev_ptr->next = h_ptr;
     }
     h_ptr->next = NULL;
     h_ptr->index = next_free_index;
     h_ptr->count = 1;
     h_ptr->name = (char *) my_malloc((strlen(name) + 1) * sizeof(char));
     strcpy(h_ptr->name, name);
     return (h_ptr);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

struct s_hash_iterator start_hash_table_iterator ( void )

Definition at line 38 of file hash.c.

                                                        {
 
     /* Call this routine before you start going through all the elements in    *
      * a hash table.  It sets the internal indices to the start of the table.  */
 
     struct s_hash_iterator hash_iterator;
 
     hash_iterator.i = -1;
     hash_iterator.h_ptr = NULL;
     return (hash_iterator);
 }

Here is the caller graph for this function:

Functions

Function Documentation