Mega Code Archive
Hash, use shift-folding snip
<![CDATA[
#include <stdio.h>
#include <error.h>
#include <string.h>
#include <stdlib.h>
#define MAXLINE 128
#define HTABSIZE 101
#define NSHIFT 3
struct hnode {
int pos;
char *key;
struct hnode *next;
};
typedef struct hnode *hashtable[HTABSIZE];
int htab_key(char *key);
int htab_getval(hashtable h, char *key);
void htab_insert(hashtable h, char *key, int pos);
void htab_dump(hashtable htab);
void htab_free(hashtable htab);
int main(int argc, char *argv[]) {
char line[MAXLINE];
hashtable htab = {0};
int len = 0;
int i = 0;
int retv = 0;
if(argc != 2)
error(1, 0, "querry < input.txt");
while(fgets(line, MAXLINE, stdin) != NULL) {
/* strip newlines */
len = strlen(line);
if(line[len - 1] == '\n')
line[--len] = '\0';
if(len > 2)
htab_insert(htab, line, i++);
}
if((retv = htab_getval(htab, argv[1])) == -1)
printf("NOT found: `%s', `%d'\n", argv[1], retv);
else
printf("FOUND: `%s' at `%d'\n", argv[1], retv);
/* htab_dump(htab); */
htab_free(htab);
return 0;
}
int htab_key(char *key) {
char *ptr = NULL;
int retv = 0;
int i = 0;
int x = 0;
for(ptr = key; *ptr; retv += x)
for(i = 0, x = 0; i < NSHIFT && *ptr; i++, ptr++)
x = x * 10 + *ptr;
retv %= HTABSIZE;
return retv;
}
void htab_insert(hashtable htab, char *key, int pos) {
struct hnode *ptr = (struct hnode *)malloc(sizeof(struct hnode));
int index = htab_key(key);
ptr->key = strdup(key);
ptr->pos = pos;
ptr->next = htab[index];
htab[index] = ptr;
return;
}
int htab_getval(hashtable htab, char *key) {
struct hnode *ptr = {0};
for(ptr = htab[htab_key(key)]; ptr && strcmp(ptr->key, key); ptr = ptr->next)
;
if(ptr)
return ptr->pos;
else
return -1;
}
void htab_dump(hashtable htab) {
struct hnode *ptr = {0};
int i = 0;
for(i = 0; i < HTABSIZE; i++) {
printf("[%02d]: ", i);
for(ptr = htab[i]; ptr; ptr = ptr->next) {
printf("[%d] -> %s", ptr->pos, ptr->key);
}
printf("\n");
}
return;
}
void htab_free(hashtable htab) {
struct hnode *ptr = {0};
struct hnode *tmp = {0};
int i = 0;
for(i = 0; i < HTABSIZE; i++) {
for(ptr = htab[i]; ptr; ptr = ptr->next) {
if(ptr->next != NULL) {
free(ptr->key), tmp = ptr->next;
free(ptr), ptr = tmp;
}
}
}
return;
}
]]>