-
hashing with linked list
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
typedef struct List { char *word; struct List *next; } List;
#define HASHSIZE 65536
#define LEN 50
static struct List *hashtab[HASHSIZE];
static FILE *open_file (char *file, char *mode)
{
FILE *fp = fopen (file, mode);
if (fp == NULL){
perror ("Unable to open file");
exit (EXIT_FAILURE);
}
return fp;
}
int is_punctuation (int a)
{
return a == ' ' || a == '\n' ||
a == EOF || a == ',' ||
a ==';' || a =='.'||
a =='!' || a =='?' ||
a ==':' || a =='`';
}
unsigned rot_hash (void *key, int len) // Rotating hash
{
unsigned char *p = key;
unsigned h = 0;
int i;
for (i = 0; i < len; i++)
h = (h << 4) ^ (h >> 28) ^ p[i];
return h % HASHSIZE;
}
struct List *lookup (char *s, int x)
{
struct List *np;
for (np = hashtab[rot_hash(s, x)]; np != NULL; np = np -> next)
if (strcmp (s, np -> word) == 0)
return np;
return NULL;
}
int install (char *name, int x)
{
struct List *current_list;
struct List *new_list;
unsigned int h = rot_hash (name, x);
if ((new_list = malloc (sizeof (List))) == NULL)
return 1;
current_list = lookup (name, x);
if (current_list != NULL)
return 2;
new_list -> word = strdup (name);
new_list -> next = hashtab[h];
hashtab[h] = new_list;
return 0;
}
int main (int argc, char *argv[])
{
int x, i, k, count, comp;
char a, ans, word[LEN];
x = 0;
k = 0;
FILE *fp = open_file (argv[1], "r");
do{
a = fgetc (fp);
if (is_punctuation(a)){
if (x != 0){
word[x] = '\0';
k = install (word, x);
printf ("%d\n", k);
x = 0;
}
}else{
word[x] = tolower(a);
x++;
}
} while (a != EOF);
fclose (fp);
return 0;
}
i need it to read in a value into a hashtable and if there is a collision it inserts the word into a linked list. can anyone tell me if my install func is correct as i can't think of a way of testing it until i do search function later.
-
Your lookup function is correctly written, but not correctly indented (the return NULL statement is not part of the for loop). Otherwise, everything looks fine.