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

typedef struct node_t {
	char *lastname;
	char *firstname;
	struct node_t *next;
} node_t;

#define MULTIPLIER 31	/* for hash function */
#define N 1000
node_t *hashtable[N];

unsigned hash(const char *p);
node_t *lookup(const char *lastname);
void insert(const char *firstname, const char *lastname);
void print(node_t *starting_point);

int main()
{
	char firstname[256];
	char lastname[256];
	node_t *person;

	printf(
		"Type firstname lastname on a line by themselves.\n"
		"Press RETURN after each line,\n"
		"control-d after the RETURN after the last line.\n"
	);

	while (scanf("%s%s", firstname, lastname) == 2) {
		if (lookup(lastname) != NULL) {
			fprintf(stderr, "Sorry, the lastname \"%s\" already exists.\n",
				lastname);
			continue;
		}

		insert(firstname, lastname);
	}

	for (;;) {
		printf("Type a last name and press RETURN (or control-d to quit):\n");
		if (scanf("%s", lastname) != 1) {
			break;
		}

		person = lookup(lastname);
		if (person == NULL) {
			fprintf(stderr, "Sorry, lastname \"%s\" doesn't exist.\n", lastname);
		} else {
			printf("%s %s\n", person->firstname, person->lastname);
		}
	}

	return EXIT_SUCCESS;
}

/* Return the subscript in the hashtable where a lastname may be found. */
unsigned hash(const char *p)
{
	unsigned h = 0;

	for (; *p != '\0'; ++p) {
		h *= MULTIPLIER;
		h += (unsigned char)*p;
	}

	return h % N;
}

node_t *lookup(const char *lastname)
{
	node_t *p;

	for (p = hashtable[hash(lastname)]; p != NULL; p = p->next) {
		if (strcmp(lastname, p->lastname) == 0) {
			break;
		}
	}

	return p;
}

void insert(const char *firstname, const char *lastname)
{
	const unsigned h = hash(lastname);
	node_t *const new = malloc(sizeof(node_t));

	new->lastname = malloc(strlen(lastname) + 1);
	strcpy(new->lastname, lastname);

	new->firstname = malloc(strlen(firstname) + 1);
	strcpy(new->firstname, firstname);

	new->next = hashtable[h];
	hashtable[h] = new;
}