6.4: initial comiit

9 files changed, 209 insertions, 0 deletions

diff --git a/6.4/Makefile b/6.4/Makefile
new file mode 100644
index 0000000..ca85182
--- /dev/null
+++ b/6.4/Makefile
@@ -0,0 +1,13 @@
+objects = main.o tree.o word.o getch.o
+CC = gcc
+CFLAGS = -Wvla -Wall -Wextra -Wstrict-prototypes -Wmissing-prototypes -fsanitize=address
+
+words : $(objects)
+	$(CC) $(CFLAGS) -o words $(objects)
+
+main.o : word.h tree.h
+word.o : getch.h
+
+.PHONY : clean
+clean:
+	rm words $(objects)
diff --git a/6.4/getch.c b/6.4/getch.c
new file mode 100644
index 0000000..f271434
--- /dev/null
+++ b/6.4/getch.c
@@ -0,0 +1,23 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <error.h>
+#include <errno.h>
+#include "getch.h"
+
+#define MAXBUFF 100
+
+int top;
+char buff[MAXBUFF];
+
+char getch(void)
+{
+	return (top > 0) ? buff[--top] : getchar();
+}
+
+void ungetch(char c)
+{
+	if (top < MAXBUFF)
+		buff[top++] = c;
+	else
+	 	error(EXIT_FAILURE, ENOBUFS, "getch");
+}
diff --git a/6.4/getch.h b/6.4/getch.h
new file mode 100644
index 0000000..b0e086b
--- /dev/null
+++ b/6.4/getch.h
@@ -0,0 +1,2 @@
+char getch(void);
+void ungetch(char c);
diff --git a/6.4/gnu b/6.4/gnu
new file mode 100644
index 0000000..31a03be
--- /dev/null
+++ b/6.4/gnu
@@ -0,0 +1,20 @@
+I'd just like to interject for a moment. What you're refering to as Linux, is
+in fact, GNU/Linux, or as I've recently taken to calling it, GNU plus Linux.
+Linux is not an operating system unto itself, but rather another free
+component of a fully functioning GNU system made useful by the GNU corelibs,
+shell utilities and vital system components comprising a full OS as defined
+by POSIX.
+
+Many computer users run a modified version of the GNU system every day,
+without realizing it. Through a peculiar turn of events, the version of GNU
+which is widely used today is often called Linux, and many of its users are
+not aware that it is basically the GNU system, developed by the GNU Project.
+
+There really is a Linux, and these people are using it, but it is just a part
+of the system they use. Linux is the kernel: the program in the system that
+allocates the machine's resources to the other programs that you run. The
+kernel is an essential part of an operating system, but useless by itself;
+it can only function in the context of a complete operating system. Linux is
+normally used in combination with the GNU operating system: the whole system
+is basically GNU with Linux added, or GNU/Linux. All the so-called Linux
+distributions are really distributions of GNU/Linux!
diff --git a/6.4/main.c b/6.4/main.c
new file mode 100644
index 0000000..c5a2255
--- /dev/null
+++ b/6.4/main.c
@@ -0,0 +1,28 @@
+#include <stdio.h>
+#include <ctype.h>
+#include "word.h"
+#include "tree.h"
+
+#define MAXWORD		100
+#define NDISTINCTTREE	1000
+
+struct tnode *tlist[NDISTINCTTREE];
+
+int main(void)
+{
+	char word[MAXWORD];
+	struct tnode *root;
+	int nt;
+	
+	root = NULL;
+	while (getword(word, MAXWORD) != EOF)
+		if (isalpha(word[0]))
+			root = addtree(root, word);
+
+	nt = tlstore(root, tlist, NDISTINCTTREE);
+	tlsort(tlist, nt);
+	printtl(tlist, nt);
+	tfree(root);
+
+	return 0;
+}
diff --git a/6.4/tree.c b/6.4/tree.c
new file mode 100644
index 0000000..7f12162
--- /dev/null
+++ b/6.4/tree.c
@@ -0,0 +1,85 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <error.h>
+#include <errno.h>
+#include "tree.h"
+
+struct tnode *talloc(void);
+void tlswap(struct tnode *l[], int p1, int p2);
+
+struct tnode *addtree(struct tnode *p, char *w)
+{
+	int cond;
+
+	if (p == NULL) {
+		p = talloc();
+		p->word = strdup(w);
+		p->count = 1;
+		p->left = p->right = NULL;
+	} else if (!(cond = strcasecmp(w, p->word))) {
+		p->count++;
+	} else if (cond < 0) {
+		p->left = addtree(p->left, w);
+	} else if (cond > 0) {
+		p->right = addtree(p->right, w);
+	}
+
+	return p;
+}
+
+int tlstore(struct tnode *p, struct tnode *l[], int lim)
+{
+	static int nt;
+
+	if (p != NULL && nt < lim) {
+		tlstore(p->left, l, lim);
+		l[nt++] = p;
+		tlstore(p->right, l, lim);
+	}
+
+	return nt;
+}
+
+void tlsort(struct tnode *l[], int lim)
+{
+	int gap, i, j;
+
+	for (gap = lim/2; gap > 0; gap /= 2)
+		for (i = gap; i < lim; ++i)
+			for (j = i - gap; j >= 0 &&
+				l[j]->count >= l[j+gap]->count; j -= gap)
+				tlswap(l, j, j + gap);
+}
+
+void tlswap(struct tnode *l[], int p1, int p2)
+{
+	struct tnode *temp;
+
+	temp = l[p1];
+	l[p1] = l[p2];
+	l[p2] = temp;
+}
+
+void printtl(struct tnode *l[], int lim)
+{
+	int i;
+
+	for (i = 0; i < lim; ++i)
+		printf("%4d %s\n", l[i]->count, l[i]->word);
+}
+
+void tfree(struct tnode *p)
+{
+	if (p != NULL) {
+		tfree(p->left);
+		tfree(p->right);
+		free(p->word);
+		free(p);
+	}
+}
+
+struct tnode *talloc(void)
+{
+	return (struct tnode *) malloc(sizeof(struct tnode));
+}
diff --git a/6.4/tree.h b/6.4/tree.h
new file mode 100644
index 0000000..e619127
--- /dev/null
+++ b/6.4/tree.h
@@ -0,0 +1,17 @@
+#ifndef TREE_H
+
+struct tnode {
+	char *word;
+	int count;
+	struct tnode *left;
+	struct tnode *right;
+};
+
+#define TREE_H
+#endif
+
+struct tnode *addtree(struct tnode *p, char *w);
+int tlstore(struct tnode *p, struct tnode *l[], int lim);
+void tlsort(struct tnode *l[], int lim);
+void printtl(struct tnode *l[], int lim);
+void tfree(struct tnode *p);
diff --git a/6.4/word.c b/6.4/word.c
new file mode 100644
index 0000000..c5a6381
--- /dev/null
+++ b/6.4/word.c
@@ -0,0 +1,20 @@
+#include <ctype.h>
+#include "getch.h"
+#include "word.h"
+
+char getword(char *word, int lim)
+{
+	char *w = word;
+
+	while (isblank(*w = getch()))
+		;
+	
+	if (isalpha(*w)) {
+		while ((isalnum(*++w = getch()) || *w == '_') && --lim > 0)
+			;
+		ungetch(*w--);
+	}
+
+	*++w = '\0';
+	return word[0];
+}
diff --git a/6.4/word.h b/6.4/word.h
new file mode 100644
index 0000000..96140df
--- /dev/null
+++ b/6.4/word.h
@@ -0,0 +1 @@
+char getword(char *word, int lim);