6.3: using linked list

4 files changed, 110 insertions, 36 deletions

diff --git a/6.3/gnu b/6.3/gnu
new file mode 100644
index 0000000..31a03be
--- /dev/null
+++ b/6.3/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.3/main.c b/6.3/main.c
index cd52cec..5c35e24 100644
--- a/6.3/main.c
+++ b/6.3/main.c
@@ -7,25 +7,20 @@
 #define MAXWORD	100
 #define ARR_SIZE(X) (sizeof(X)/sizeof(X[0]))
 
-const char *noise[] = {
-	"the",
-	"and"
-};
-
-int isnoise(char *word);
+int noiseword(char *w);
 
 int main(void)
 {
 	char word[MAXWORD];
 	struct tnode *root;
-	int line = 0;
+	int linenum = 0;
 	
 	root = NULL;
 	while (getword(word, MAXWORD) != EOF)
-		if (isalpha(word[0]) && !isnoise(word))
-			root = addtree(root, word, line);
+		if (isalpha(word[0]) && noiseword(word) == -1)
+			root = addtree(root, word, linenum);
 		else if(word[0] == '\n')
-			++line;
+			++linenum;
 
 	tprint(root);
 	tfree(root);
@@ -33,13 +28,36 @@ int main(void)
 	return 0;
 }
 
-int isnoise(char *word)
+int noiseword(char *w)
 {
-	size_t i;
-
-	for(i = 0; i < ARR_SIZE(noise); ++i)
-		if (!strcmp(word, noise[i]))
-			return 1;
-
-	return 0;
+	const char *noise[] = {
+		"a",
+		"an",
+		"and",
+		"are",
+		"in",
+		"is",
+		"of",
+		"or",
+		"that",
+		"the",
+		"this",
+		"to"
+	};
+
+	int cond, mid;
+	int low = 0;
+	int high = ARR_SIZE(noise);
+
+	while (low < high) {
+		mid = (low + high) / 2;
+		if ((cond = strcmp(w, noise[mid])) < 0)
+			high = mid;
+		else if (cond > 0)
+			low = mid + 1;
+		else
+			return mid;
+	}
+
+	return -1;
 }
diff --git a/6.3/tree.c b/6.3/tree.c
index c58da53..a83d294 100644
--- a/6.3/tree.c
+++ b/6.3/tree.c
@@ -6,55 +6,89 @@
 #include "tree.h"
 
 struct tnode *talloc(void);
+struct linklist *lalloc(void);
+void lfree(struct linklist *p);
+void addln(struct tnode *p, int linenum);
 
-struct tnode *addtree(struct tnode *p, char *w, int line)
+struct tnode *addtree(struct tnode *p, char *w, int linenum)
 {
 	int cond;
 
 	if (p == NULL) {
 		p = talloc();
 		p->word = strdup(w);
-		p->lc = 0;
-		p->lines[p->lc++] = line;
+		p->lines = lalloc();
+		p->lines->linenum = linenum;
+		p->lines->ptr = NULL;
 		p->left = p->right = NULL;
 	} else if (!(cond = strcasecmp(w, p->word))) {
-		if (p->lc < MAXLINES)
-			p->lines[p->lc++] = line;
-		else
-		 	error(EXIT_FAILURE, ENOBUFS, "addtree");
+		addln(p, linenum);
 	} else if (cond < 0) {
-		p->left = addtree(p->left, w, line);
+		p->left = addtree(p->left, w, linenum);
 	} else if (cond > 0) {
-		p->right = addtree(p->right, w, line);
+		p->right = addtree(p->right, w, linenum);
 	}
 
 	return p;
 }
 
+void addln(struct tnode *p, int linenum)
+{
+	struct linklist *temp;
+
+	temp = p->lines;
+	while (temp->ptr != NULL && temp->linenum != linenum)
+		temp = temp->ptr;
+
+	if (temp->linenum != linenum) {
+		temp->ptr = lalloc();
+		temp->ptr->linenum = linenum;
+		temp->ptr->ptr = NULL;
+	}
+}
+
 void tprint(struct tnode *p)
 {
-	int lc;
+	struct linklist *temp;
 
 	if (p != NULL) {
 		tprint(p->left);
-		printf("---> %s\n", p->word);
-		for (lc = 0; lc < p->lc; ++lc)
-			printf((lc == p->lc-1) ? "%d" : "%d, ", p->lines[lc]);
+
+		printf("%10s: ", p->word);
+		for (temp = p->lines; temp != NULL; temp = temp->ptr)
+			printf("%4d", temp->linenum);
+			// printf("%d%s", temp->linenum,
+			// 	 (temp->ptr == NULL) ? "\n" : ", ");
 		putchar('\n');
 		tprint(p->right);
 	}
 }
+
 void tfree(struct tnode *p)
 {
 	if (p != NULL) {
 		tfree(p->left);
 		tfree(p->right);
+		lfree(p->lines);
 		free(p->word);
 		free(p);
 	}
 }
 
+void lfree(struct linklist *p)
+{
+	if (p != NULL) {
+		lfree(p->ptr);
+		free(p);
+	}
+}
+
 struct tnode *talloc(void)
 {
 	return (struct tnode *) malloc(sizeof(struct tnode));
 }
+
+struct linklist *lalloc(void)
+{
+	return (struct linklist *) malloc(sizeof(struct linklist));
+}
diff --git a/6.3/tree.h b/6.3/tree.h
index c6ebc53..0b90913 100644
--- a/6.3/tree.h
+++ b/6.3/tree.h
@@ -1,18 +1,20 @@
 #ifndef TREE_H
 
-#define MAXLINES 1000
-
 struct tnode {
 	char *word;
-	int lc;
-	int lines[MAXLINES];
+	struct linklist *lines;
 	struct tnode *left;
 	struct tnode *right;
 };
 
+struct linklist {
+	int linenum;
+	struct linklist *ptr;
+};
+
 #define TREE_H
 #endif
 
-struct tnode *addtree(struct tnode *p, char *w, int line);
+struct tnode *addtree(struct tnode *p, char *w, int linenum);
 void tprint(struct tnode *p);
 void tfree(struct tnode *p);