/* Copyright */

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

#include "macros.h"

/* Count of words found */
int num_found = 0;

/* A node in the binary tree */
struct entry
{
	struct entry *left;
	struct entry *right;
	char *word;
};
struct entry *root = NULL;

/* Enter a word into the binary tree if it doesn't
   already exist
*/
void enter(char *word, struct entry **proot)
{
	struct entry *new_entry;
	char *new_word;
	int comp;

	if (*proot == NULL) {
		new_entry = calloc(sizeof(struct entry), 1);
		new_word = malloc(strlen(word) + 1);
		strcpy(new_word, word);
		new_entry->word = new_word;
		*proot = new_entry;
	} else {
		comp = strcmp(word, (*proot)->word);
		if (comp < 0) {
			enter(word, &((*proot)->left));
		} else if (comp > 0) {
			enter(word, &((*proot)->right));
		}
	}
	return;
}

/* Look up a word in the binary tree */
int lookup(char *word, struct entry *root)
{
	int comp;

	if (root == NULL) {
		return 0;
	}
	comp = strcmp(word, root->word);
	if (comp < 0) {
		return lookup(word, root->left);
	} else if (comp > 0) {
		return lookup(word, root->right);
	} else {

		/* Multiple tasks may be running "lookup" concurrently.
		   __critical ensures updates to "num_found" are consistent.
		 */
		__critical num_found++;
		return 1;
	}
}

/* This program reads a dictionary of words from an input file.
   It creates a binary search tree from the words in the dictionary.

   Then, it reads another file of words to look up in the dictionary.
   A count of words found in the dictionary is computed and printed.
*/
int main(int argc, char *argv[])
{
	FILE *dict;
	FILE *words;
	char buffer1[256], buffer2[256];
	int found1, found2;

	if (argc < 3) {
		fprintf(stderr, "Use this form: lookup <dictionary> <words>\n");
		exit(1);
	}

	/* Open dictionary file */
	if ((dict = fopen(argv[1], "r")) == NULL) {
		fprintf(stderr, "Could not open dictionary file \"%s\"\n", argv[1]);
		exit(1);
	}
	/* Read words in dictionary and enter them into binary tree */
	while (fgets(buffer1, sizeof(buffer1)-1, dict) != NULL) {
		enter(buffer1, &root);
	}
	/* Close dictionary file */
	fclose(dict);

	/* Open file of words to look up in dictionary */
	if ((words = fopen(argv[2], "r")) == NULL) {
		fprintf(stderr, "Could not open words file \"%s\"\n", argv[2]);
		exit(1);
	}
	/* Initialize counters */
	found1 = found2 = 0;

	/* Read words to look up and look them up in dictionary */
	while (fgets(buffer1, sizeof(buffer1)-1, words) != NULL &&
			fgets(buffer2, sizeof(buffer2)-1, words) != NULL)	{
		__parallel {
			__spawn if (lookup(buffer1, root))
			{
				found1++;
			}
			__spawn if (lookup(buffer2, root))
			{
				found2++;
			}
		}
	}

	/* Close file of words to look up */
	fclose(words);

	/* Print results */
	printf("%d words found\n", found1+found2);
	printf("%d words found\n", num_found);
}