Crossings Minimization  1.0
hash.c File Reference

Implementation of access functions for hash table. More...

#include "defs.h"
#include "hash.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
Include dependency graph for hash.c:

Go to the source code of this file.

Macros

#define LOAD_FACTOR   0.75
 
#define POLYNOMIAL_VALUE   37
 
#define MIN_TABLE_SIZE   8
 

Functions

static unsigned int getTableSize (int entries)
 
static void reverse (char *reversed, const char *original)
 
static unsigned int hashValue (const char *name)
 
static unsigned int hashIndex (const char *name)
 
static unsigned int getIndex (const char *name)
 
void initHashTable (int number_of_items)
 
void insertInHashTable (const char *name, Nodeptr node)
 
Nodeptr getFromHashTable (const char *name)
 
void removeHashTable ()
 
double getAverageNumberOfProbes ()
 

Variables

static unsigned int modulus
 
static Nodeptrhash_table = NULL
 
static int number_of_probes = 0
 
static int number_of_accesses = 0
 

Detailed Description

Implementation of access functions for hash table.

Author
Matthias Stallmann
Date
2008/12/21
Id
hash.c 2 2011-06-07 19:50:41Z mfms

Uses a polynomial hash function.

Definition in file hash.c.

Macro Definition Documentation

◆ LOAD_FACTOR

#define LOAD_FACTOR   0.75

Definition at line 17 of file hash.c.

Referenced by getTableSize().

◆ MIN_TABLE_SIZE

#define MIN_TABLE_SIZE   8

Definition at line 19 of file hash.c.

Referenced by getTableSize().

◆ POLYNOMIAL_VALUE

#define POLYNOMIAL_VALUE   37

Definition at line 18 of file hash.c.

Referenced by hashValue().

Function Documentation

◆ getAverageNumberOfProbes()

double getAverageNumberOfProbes ( )
Returns
The average number of probes per call to insert or get.

Definition at line 111 of file hash.c.

References getIndex(), hashIndex(), hashValue(), modulus, number_of_accesses, and number_of_probes.

Referenced by printGraph().

Here is the call graph for this function:

◆ getFromHashTable()

Nodeptr getFromHashTable ( const char *  name)

Retrieves a node from the table, given its name

Returns
A pointer to a node with the given name if found, NULL otherwise.

Definition at line 100 of file hash.c.

References getIndex().

Referenced by addEdge(), and incrementDegrees().

Here is the call graph for this function:

◆ getIndex()

static unsigned int getIndex ( const char *  name)
static
Parameters
nameThe name of a node
Returns
the index of the position in the hash table where the node has been found or of the first empty position after the hash value of the name.

Definition at line 173 of file hash.c.

References hashIndex(), initHashTable(), insertInHashTable(), main(), MAX_NAME_LENGTH, modulus, node_struct::name, number_of_accesses, and number_of_probes.

Referenced by getAverageNumberOfProbes(), getFromHashTable(), and insertInHashTable().

Here is the call graph for this function:

◆ getTableSize()

static unsigned int getTableSize ( int  entries)
static

Computes a suitable table size (modulus) based on a given desired number of entries. The choice used here is a power of two minus one.

Definition at line 135 of file hash.c.

References LOAD_FACTOR, and MIN_TABLE_SIZE.

Referenced by initHashTable().

◆ hashIndex()

static unsigned int hashIndex ( const char *  name)
static

Computes an index into the table from the name.

Definition at line 168 of file hash.c.

References hashValue(), and modulus.

Referenced by getAverageNumberOfProbes(), getIndex(), and insertInHashTable().

Here is the call graph for this function:

◆ hashValue()

static unsigned int hashValue ( const char *  name)
static

Calculates the hash value of a given node name. Overflow doesn't matter because this is supposed to be 'random' anyway. The name is reversed because most node names have common prefixes.

Definition at line 155 of file hash.c.

References MAX_NAME_LENGTH, POLYNOMIAL_VALUE, and reverse().

Referenced by getAverageNumberOfProbes(), hashIndex(), and insertInHashTable().

Here is the call graph for this function:

◆ initHashTable()

void initHashTable ( int  number_of_items)

Initializes the hash table so that it can "comfortably" accommodate the given number of items

Definition at line 69 of file hash.c.

References getTableSize(), modulus, number_of_accesses, and number_of_probes.

Referenced by getIndex(), and readGraph().

Here is the call graph for this function:

◆ insertInHashTable()

void insertInHashTable ( const char *  name,
Nodeptr  node 
)

Inserts A node into the hash table. Assumes that the node is not already present (fatal error otherwise)

Definition at line 81 of file hash.c.

References getIndex(), hashIndex(), hashValue(), and node_struct::name.

Referenced by getIndex(), and makeNode().

Here is the call graph for this function:

◆ removeHashTable()

void removeHashTable ( )

Deallocates the memory used by the table

Definition at line 106 of file hash.c.

Referenced by readGraph().

◆ reverse()

static void reverse ( char *  reversed,
const char *  original 
)
static

Compute the reverse of a string

Parameters
reverseda buffer to hold the reversed version (destination)
originalthe original string

Definition at line 143 of file hash.c.

Referenced by hashValue().

Variable Documentation

◆ hash_table

Nodeptr* hash_table = NULL
static

Definition at line 27 of file hash.c.

◆ modulus

unsigned int modulus
static

2^k - 1 where k is chosen to give the right table size; this is also a the table size.

Definition at line 25 of file hash.c.

Referenced by getAverageNumberOfProbes(), getIndex(), hashIndex(), initHashTable(), and polynomial_hash().

◆ number_of_accesses

int number_of_accesses = 0
static

Definition at line 31 of file hash.c.

Referenced by getAverageNumberOfProbes(), getIndex(), and initHashTable().

◆ number_of_probes

int number_of_probes = 0
static

Definition at line 30 of file hash.c.

Referenced by getAverageNumberOfProbes(), getIndex(), and initHashTable().