/**
* Hashing Based on devision technique, It is a generic hash table,
* applicable for storing and searching any king of data structure,
* need to do just item_t structure with any structure and have fun :)
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_HASH_INDEX 10
/* Can be any data structure */
typedef struct item_
{
int idata;
}item_t;
typedef struct hash_
{
struct hash_ *next;
void *node;
}hash_t;
typedef int (*compare_fun)(hash_t *,int);
typedef int (*key_cb)(void *);
hash_t *hash[MAX_HASH_INDEX] = {NULL};
/*
* Local compare function, it can be changed according to data structure used,
* and also what are you looking for into table
*/
static int local_compare_data_in_hash(hash_t *hnode, int data)
{
if ( ((item_t *)hnode->node)->idata == data)
{
return 0;
}
}
/*
* local key generation function, key generation technique varies on parameters used
* to determine key
*/
static int get_key(void *item)
{
item_t *temp = (item_t *)item;
return(temp->idata % MAX_HASH_INDEX);
}
/* generic hash searching */
void *hash_search(hash_t *hash[], compare_fun comp,int data)
{
int key;
hash_t *temp = NULL;
/*Calculate Key to find index*/
key = data % MAX_HASH_INDEX;
if ( NULL == hash[key])
{
return NULL;
} else {
temp = hash[key];
while ( NULL != temp )
{
/* Compare parameter to find required node in table */
if ( 0 == comp(temp,data))
{
return temp->node;
}
temp = temp->next;
}
/*Search complete, item not found */
if ( NULL == temp )
{
return NULL;
}
}
}
int hash_entry_function(hash_t *hash[],key_cb k_cb, void *item)
{
int key;
hash_t *hash_node = NULL;
/* Calculate Key*/
key = k_cb(item);
/*Prepare Node to Add*/
hash_node = malloc(sizeof(hash_t ));
hash_node->node = item;
if ( hash[key] == NULL)
{
hash[key] = hash_node;
} else {
hash_node->next = hash[key];
hash[key] = hash_node;
}
return 0;
}
void display_complete_hash(hash_t *hash[])
{
hash_t *temp ;
int i;
for( i = 0; i < MAX_HASH_INDEX; i++)
{
if ( hash[i] == NULL)
continue;
temp = hash[i];
printf("--------------------------------------\n");
while(temp != NULL )
{
printf("|%d",((item_t *)temp->node)->idata);
temp = temp->next;
}
printf("\n--------------------------------------\n");
}
}
main ()
{
item_t *item = NULL;
int data_list[] = {2,14,12,17,77,66,88,45,3,6,26,98,10};
int i,sz,num;
item_t *node = NULL;
/* Enter data into hash table */
sz = sizeof(data_list)/sizeof(data_list[0]);
for ( i = 0; i < sz; i++)
{
item = malloc(sizeof(item_t));
item->idata = data_list[i];
hash_entry_function(hash,get_key,(void *)item);
}
display_complete_hash(hash);
while(1)
{
printf("Enter Number to search:");
scanf("%d",&num);
node = hash_search(hash,local_compare_data_in_hash,num);
if ( NULL == node )
{
printf("Data not present in hash table\n");
} else {
printf("Data found : %d\n",node->idata);
}
}
}
RTOS, Linux Kernel internal, OS-Programming C & Data Structures, Debugging, Optimizations, Makefiles and Wireless Technologies (Wi-Fi ,LTE and LTE-Advanced )
Search This Blog
Saturday, June 4, 2016
Hash Table Division Method
Labels:
C,
Data Structure
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment