Crossings Minimization  1.0
check_edge_duplication.c File Reference

utility that uses hashing to check whether an edge already exists More...

#include "check_edge_duplication.h"
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
Include dependency graph for check_edge_duplication.c:

Go to the source code of this file.

Macros

#define LOAD_FACTOR   0.1
 
#define HASH_VALUE_ONE   37
 
#define HASH_VALUE_TWO   113
 

Functions

static unsigned long polynomial_hash (const char *start_ptr, unsigned int length, unsigned int x, unsigned long range_size)
 
void create_hash_table_for_pairs (int expected_number_of_pairs)
 
void destroy_hash_table_for_pairs (void)
 
bool pair_already_exists (int first_int, int second_int)
 

Variables

static unsigned char * pairs_bit_vector
 
static size_t bit_vector_length
 
static int collisions
 
static size_t bits_per_pair
 
static size_t bytes_per_pair
 

Detailed Description

utility that uses hashing to check whether an edge already exists

Id
check_edge_duplication.c 2 2011-06-07 19:50:41Z mfms

Definition in file check_edge_duplication.c.

Macro Definition Documentation

◆ HASH_VALUE_ONE

#define HASH_VALUE_ONE   37

two prime numbers that give good results for polynomial hashing

Definition at line 30 of file check_edge_duplication.c.

Referenced by pair_already_exists().

◆ HASH_VALUE_TWO

#define HASH_VALUE_TWO   113

Definition at line 31 of file check_edge_duplication.c.

Referenced by pair_already_exists().

◆ LOAD_FACTOR

#define LOAD_FACTOR   0.1

Load factor for the bit vector, roughly the likelihood of a collision between distinct edges; also determines the size of the bit vector; small load factor implies large bit vector

Definition at line 20 of file check_edge_duplication.c.

Referenced by create_hash_table_for_pairs().

Function Documentation

◆ create_hash_table_for_pairs()

void create_hash_table_for_pairs ( int  expected_number_of_pairs)

Allocates the hash table based on the expected number of pairs

Definition at line 68 of file check_edge_duplication.c.

References bit_vector_length, bits_per_pair, bytes_per_pair, LOAD_FACTOR, and pairs_bit_vector.

Referenced by add_edges(), and create_random_dag().

◆ destroy_hash_table_for_pairs()

void destroy_hash_table_for_pairs ( void  )

Deallocates the hash table

Definition at line 79 of file check_edge_duplication.c.

References collisions, and pairs_bit_vector.

Referenced by add_edges(), and create_random_dag().

◆ pair_already_exists()

bool pair_already_exists ( int  first_int,
int  second_int 
)
Parameters
first_intindex of a node in the master_node_list
second_intindex of another node in the master_node_list
Returns
true if an edge between the given nodes already exists This function is oblivious to the fact that we are dealing with a random dag - it applies to any collection of pairs of integers

Definition at line 93 of file check_edge_duplication.c.

References bit_vector_length, collisions, HASH_VALUE_ONE, HASH_VALUE_TWO, pairs_bit_vector, and polynomial_hash().

Referenced by add_edges(), create_random_dag(), and make_all_current_edges_exist().

Here is the call graph for this function:

◆ polynomial_hash()

static unsigned long polynomial_hash ( const char *  start_ptr,
unsigned int  length,
unsigned int  x,
unsigned long  range_size 
)
static

Uses a polynomial hash function to compute a hash value for a sequence of bytes. If the k bytes are b_{k-1}, ..., b_0 the polynomial P(x) is (b_{k-1} x^{k-1} + ... + b_0 x^0) mod z. The hash function evaluates P(x) at x = some suitably chosen prime number and maps the result to an integer in the range [0,max-1]; the modulus z should be >= max and relatively prime to x (otherwise some integers in the range will never be mapped to)

Parameters
start_ptrpointer to b_{k-1}, the first byte in the sequence
lengthnumber of bytes in the sequence, i.e., k
xthe prime number at which P(x) is evaluated
range_sizethe number of integers in the range, i.e., max
Returns
an (somewhat random) integer in the interval [0,max-1]; a particular sequence of bytes always gives the same return value

Definition at line 48 of file check_edge_duplication.c.

References modulus.

Referenced by pair_already_exists().

Variable Documentation

◆ bit_vector_length

size_t bit_vector_length
static

Definition at line 24 of file check_edge_duplication.c.

Referenced by create_hash_table_for_pairs(), and pair_already_exists().

◆ bits_per_pair

size_t bits_per_pair
static

Definition at line 26 of file check_edge_duplication.c.

Referenced by create_hash_table_for_pairs().

◆ bytes_per_pair

size_t bytes_per_pair
static

Definition at line 27 of file check_edge_duplication.c.

Referenced by create_hash_table_for_pairs().

◆ collisions

int collisions
static

Definition at line 25 of file check_edge_duplication.c.

Referenced by destroy_hash_table_for_pairs(), and pair_already_exists().

◆ pairs_bit_vector

unsigned char* pairs_bit_vector
static

each pair corresponds to a single bit

Definition at line 23 of file check_edge_duplication.c.

Referenced by create_hash_table_for_pairs(), destroy_hash_table_for_pairs(), and pair_already_exists().