aboutsummaryrefslogtreecommitdiff
path: root/ch6/6-02_common-prefix-printer.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--ch6/6-02_common-prefix-printer.c239
1 files changed, 239 insertions, 0 deletions
diff --git a/ch6/6-02_common-prefix-printer.c b/ch6/6-02_common-prefix-printer.c
new file mode 100644
index 0000000..fedb389
--- /dev/null
+++ b/ch6/6-02_common-prefix-printer.c
@@ -0,0 +1,239 @@
+#include <stdio.h>
+#include <string.h>
+#include <ctype.h>
+#include <stdlib.h>
+
+/* The C Programming Language: 2nd Edition
+ *
+ * Exercise 6-2: Write a program that reads a C program and prints in
+ * alphabetical order each group of variable names that are identical in the
+ * first 6 characters, but different somewhere thereafter. Don't count words
+ * within string and comments. Make 6 a parameter that can be set from the
+ * command line.
+ *
+ * Notes: First off, "variable names" should be "words". It doesn't make sense
+ * otherwise.
+ *
+ * The trick to this is we can traverse the tree with no problem, but to do
+ * comparisons on the words, we need to know the last one we worked with. With
+ * two additional static variables in treeprint(), we have all we need to
+ * manipulate what we're outputting.
+ */
+
+#define BUFSIZE 1000
+#define MAXWORD 100
+#define DEF_PRE_LEN 6
+
+struct key {
+ char *word;
+ int count;
+};
+struct tnode {
+ char *word;
+ int count;
+ struct tnode *left;
+ struct tnode *right;
+};
+
+enum states {
+ NORMAL,
+ INQUOTE,
+ INCOMMENT
+};
+char buf[BUFSIZE];
+int bufp = 0;
+int state = NORMAL;
+int minlen;
+
+int getch(void);
+void ungetch(int);
+int getword(char *, int);
+struct key *binsearch(char *, struct key *, int);
+struct tnode *addtree(struct tnode *, char *);
+void treeprint(struct tnode *, int);
+struct tnode *talloc(void);
+char *mystrdup(char *);
+int check_prefix(char *, char*, int);
+
+int main(int argc, char *argv[]) {
+ switch (argc) {
+ case 1:
+ minlen = DEF_PRE_LEN;
+ break;
+ case 2:
+ minlen = strtol(argv[1], NULL, 10);
+ break;
+ default:
+ printf("Too many arguments.\n");
+ return 1;
+ }
+ struct tnode *root;
+ char word[MAXWORD];
+ root = NULL;
+ while (getword(word, MAXWORD) != EOF) {
+ /* Only add the words we need to the tree */
+ if (isalpha(word[0]) && strlen(word) > minlen) {
+ root = addtree(root, word);
+ if (root == NULL) {
+ printf("No words at that length or greater were found.\n");
+ return 1;
+ }
+ }
+ }
+ treeprint(root, minlen);
+ return 0;
+}
+
+int getword(char *word, int lim) {
+ int c;
+ char *w = word;
+ while (isspace(c = getch())) {
+ }
+ if (c != EOF && c != '#' && c != '"' && c != '/' && c != '*') {
+ *w++ = c;
+ }
+ if (c == '*' && state == INCOMMENT) {
+ if ((c = getch()) == '/') {
+ state == NORMAL;
+ return '/';
+ }
+ }
+ /* Ignore comments */
+ if (c == '/') {
+ c = getch();
+ if (c == '/') {
+ while ((c = getch()) != EOF && c != '\n') {
+ }
+ return '*';
+ }
+ if (c == '*') {
+ state = INCOMMENT;
+ return '*';
+ }
+ }
+ /* Handle quotes */
+ if (c == '"') {
+ state = INQUOTE;
+ }
+ if (state == INQUOTE) {
+ while ((c = getch()) != '"' && c != EOF) {
+ }
+ state = NORMAL;
+ }
+ /* Ignore preprocessor lines */
+ if (c == '#') {
+ while ((c = getch()) != '\n' && c != EOF) {
+ }
+ }
+ /* Add exceptions for underscores */
+ if (!isalpha(c) && c != '_') {
+ *w = '\0';
+ return c;
+ }
+ for ( ; --lim > 0; w++) {
+ if (!isalnum(*w = getch()) && *w != '_') {
+ ungetch(*w);
+ break;
+ }
+ }
+ *w = '\0';
+ return word[0];
+}
+
+struct key *binsearch(char *word, struct key *tab, int n) {
+ int cond;
+ struct key *low = &tab[0];
+ struct key *high = &tab[n];
+ struct key *mid;
+ while (low < high) {
+ mid = low + (high-low) / 2;
+ if ((cond = strcmp(word, mid->word)) < 0) {
+ high = mid;
+ } else if (cond > 0) {
+ low = mid + 1;
+ } else {
+ return mid;
+ }
+ }
+ return NULL;
+}
+
+int getch(void) {
+ return (bufp > 0) ? buf[--bufp] : getchar();
+}
+
+void ungetch(int c) {
+ if (bufp >= BUFSIZE) {
+ printf("ungetch: Too many characters.\n");
+ } else {
+ buf[bufp++] = c;
+ }
+}
+
+struct tnode *addtree(struct tnode *p, char *w) {
+ int cond;
+ if (p == NULL) {
+ p = talloc();
+ p->word = mystrdup(w);
+ p->count = 1;
+ p->left = p->right = NULL;
+ } else if ((cond = strcmp(w, p->word)) == 0) {
+ p->count++;
+ } else if (cond < 0) {
+ p->left = addtree(p->left, w);
+ } else {
+ p->right = addtree(p->right, w);
+ }
+ return p;
+}
+
+int check_prefix(char *s1, char *s2, int len) {
+ int i;
+ if (len == 0) {
+ return 1;
+ }
+ for (i == 0; *s1 == *s2 && *s1 != '\0' && i < len; i++, *s1++, *s2++) {
+ }
+ if (i == len) {
+ return 1;
+ }
+ return 0;
+}
+
+void treeprint(struct tnode *p, int len) {
+ static struct tnode *last; /* The last word we saw */
+ static int output = 1; /* Controls whether we output 'last' or not */
+ if (p != NULL) {
+ treeprint(p->left, len);
+ if (len == 0) {
+ printf("%4d %s\n", p->count, p->word);
+ } else {
+ if (last != NULL) {
+ if (check_prefix(last->word, p->word, len)) {
+ if (output) {
+ printf("%4d %s\n", last->count, last->word);
+ output = 0;
+ }
+ printf("%4d %s\n", p->count, p->word);
+ } else {
+ output = 1;
+ }
+ }
+ last = p;
+ }
+ treeprint(p->right, len);
+ }
+}
+
+struct tnode *talloc(void) {
+ return (struct tnode *) malloc(sizeof(struct tnode));
+}
+
+char *mystrdup(char *s) {
+ char *p;
+ p = (char *) malloc(strlen(s)+1);
+ if (p != NULL) {
+ strcpy(p , s);
+ }
+ return p;
+}