/*
 *	Inefficient way to reverse the characters in each input line
 *	by building linked lists.
 *
 *	When building the list of cells, each character is tacked onto
 *	the head of the list, so printing it out backwards is a doddle.
 *
 *	It almost works.  Find and fix the bug.
 *
 *	Martin Guy, University of Kent, February 1988
 */

#include <stdio.h>

/* Declare library routines who do not return the default type */
extern char *malloc();

/*
 *	A little structure to form one link of the list of chars.
 * 	The first cell in the list contains the last character received.
 */
struct clist {
	char c;
	struct clist *link;
};

/*
 * A define for a null pointer to mark the end of the list and to check
 * return values from malloc().
 */
#define NULLCLIST (struct clist *) 0

/*
 *	The pointer to the head of the linked list, initially empty.
 */
struct clist *head = NULLCLIST;

main()
{
	int ch;			/* current input char being processed */
	struct clist *newclist;	/* pointer to new cell under construction */
	struct clist *cp;	/* temporary clist pointer for loop */

	while ((ch = getchar()) != EOF) {
		switch (ch) {
		default:
			/* regular char; tack onto head of list */

			/* first, get space for a new clist */
			newclist = (struct clist *) malloc(sizeof(struct clist));
			if (newclist == NULLCLIST) {
				fputs("rev: Out of memory\n", stderr);
				exit(1);
			}

			/* fill in the new cell */
			newclist -> c = ch;
			/* and tack it onto the head of the list */
			newclist -> link = head;
			head = newclist;
			break;
		
		case '\n':
		case '\r':
			/*
			 * End of line. Regurgitate the line so far, then
			 * put out the \n or \r.
			 */
			for (cp = head; cp != NULL; /* reinit is in loop */) {
				struct clist *newcp; /* temp */

				putchar(cp->c);

				/* Free the storage for that cell.
				 * We need to copy the link field out before
				 * freeing, because free() is not guaranteed
				 * not to corrupt the contents of what it
				 * frees.
				 */
				newcp = cp->link;
				free((char *)cp);
				cp = newcp;
			}
			putchar(ch);
			break;
		}
	}
	exit(0);
}