Anagram

anagram.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>

#define HASH_SIZE 100000
#define WORD_SIZE 100

struct hash_node {
	char key[WORD_SIZE];
	char data[WORD_SIZE];
	struct hash_node *next;
};

struct hash {
	struct hash_node *table[HASH_SIZE];
};

size_t hash_pos(const struct hash *h, const char *key) {
	size_t x = 0;
	while(*key) {
		x += *key;
		x += (x << 10);
		x ^= (x >> 6);
		++key;
	}
	x += (x << 3);
	x ^= (x >> 11);
	x += (x << 15);
	return x % HASH_SIZE;
}

struct hash_node *hash_node_create(const char *key, const char *data) {
	struct hash_node *node = malloc(sizeof(struct hash_node));
	strcpy(node->key, key);
	strcpy(node->data, data);
	node->next = NULL;
	return node;
}

void hash_node_destroy(struct hash_node *n) {
	struct hash_node *next = n->next;
	free(n);
	if(next) {
		hash_node_destroy(next);
	}
}

struct hash *hash_create() {
	return calloc(sizeof(struct hash), 1);
}

void hash_destroy(struct hash *h) {
	size_t ii;
	for(ii = 0; ii < HASH_SIZE; ii++) {
		if(h->table[ii]) {
			hash_node_destroy(h->table[ii]);
		}
	}
	free(h);
}

void hash_push(struct hash *h, const char *key, const char *data) {
	size_t pos = hash_pos(h, key);
	struct hash_node *cur = h->table[pos];
	if(!cur) {
		h->table[pos] = hash_node_create(key, data);
		return;
	}
	while(strcmp(cur->key, key) != 0) {
		if(!cur->next) {
			cur->next = hash_node_create(key, data);
			return;
		}
		cur = cur->next;
	}
	strcpy(cur->data, data);
}

char *hash_at(struct hash *h, const char *key) {
	struct hash_node *cur = h->table[hash_pos(h, key)];
	if(!cur) {
		return NULL;
	}
	while(strcmp(cur->key, key) != 0) {
		if(!cur->next) {
			return NULL;
		}
		cur = cur->next;
	}
	return cur->data;
}

int chrcmp(const void *a, const void *b) {
	return *(char*)a - *(char*)b;
}

char *rtrim(char *s) {
	char *back = s + strlen(s);
	while(isspace(*--back));
	*(back+1) = '\0';
	return s;
}

void lower(char *s) {
	while(*s) {
		*s = tolower(*s);
		++s;
	}
}

void anagrams_load(struct hash *list, FILE *stream) {
	char buffer[WORD_SIZE];
	char key[WORD_SIZE];
	char *word;
	while(fgets(buffer, WORD_SIZE, stream)) {
		rtrim(buffer);
		strcpy(key, buffer);
		lower(key);
		qsort(key, strlen(buffer), sizeof(char), chrcmp);
		word = hash_at(list, key);
		if(word) {
			strcat(buffer, ",");
			strcat(buffer, word);
		}
		hash_push(list, key, buffer);
	}
}

void anagrams_print(const struct hash *list, FILE *stream) {
	size_t ii;
	for(ii = 0; ii < HASH_SIZE; ii++) {
		struct hash_node *cur = list->table[ii];
		while(cur) {
			if(strchr(cur->data, ',')) {
				fprintf(stream, "%s\n", cur->data);
			}
			cur = cur->next;
		}
	}
}

int main(int argc, char **argv) {
	struct hash *list;
	list = hash_create();
	anagrams_load(list, stdin);
	anagrams_print(list, stdout);
	hash_destroy(list);
	return 0;
}