Sample for Arnuld to compare:
Here are the exercises from Chapter 6 (except the hash table stuff
which seems out of place to me) as purloined from Richard Heathfield's
K&R2 solution site, and then made to work with arbitrary files, and
then the missing exercise was added and then I made some more icky
hacks and called it good. That didn't make it good, but that's what I
called it.
/*
Chapter 6. Structures Stuff.
Write a program that prints out the distinct words in its
input sorted into decreasing order of frequency of occurrence.
Precede each word by its count.
Authors: Bryan Williams, Ben Pfaff, and Richard Heathfield
wrote it, and then Dann Corbit poked it with a stick.
*/
#include "ch6.h"
static void my_putch(char **, int *, int);
int my_getch(FILE *);
static void my_ungetch(int);
static int skipws(FILE *);
static int getstelem(char **, int *, int, FILE *);
static int gComparisonLength = 6;
/*
Default: input is to file stdin, output to stdout.
Plan: read the words into a tree, keeping a count of how many we
have,
allocate an array big enough to hold Treecount (WORD *)'s
walk the tree to populate the array.
qsort the array, based on size.
print the array
qsort the array, based on word text.
print similarities in the array data (based on matching
<gComparisonLength> initial characters)
free the array
free the tree
free tibet (optional)
free international shipping!
*/
FILE *theFileIn(char *fname)
{
FILE *f = stdin;
FILE *ftry = NULL;
if (fname && fname[0]) {
ftry = fopen(fname, "r");
if (ftry == NULL) {
char Emess[512];
sprintf(Emess, "Failure to open %s for input.\n", fname);
perror(Emess);
puts("Error opening input file. Input stream set to
standard input.");
}
}
if (ftry) {
f = ftry;
}
return f;
}
FILE *theFileOut(char *fname)
{
FILE *f = stdin;
FILE *ftry = NULL;
if (fname && fname[0]) {
ftry = fopen(fname, "a");
if (ftry == NULL) {
char Emess[512];
sprintf(Emess, "Failure to open %s for output.\n", fname);
perror(Emess);
puts("Error opening output file. Output stream set to
standard output.");
}
}
if (ftry) {
f = ftry;
}
return f;
}
#define NONALPHA "1234567890 \v\f\n\t\r+=-*/\\,.;:'#~?<>|{}[]`!\"£$
%^&()"
int main0(int argc, char **argv)
{
int Status = SUCCESS;
WORD *Words = NULL;
size_t Treecount = 0;
WORD **WordArray = NULL;
FILE *fin = stdin;
FILE *fout = stdout;
if (argc > 1)
fin = theFileIn(argv[1]);
if (argc > 2)
fout = theFileOut(argv[2]);
if (argc > 3)
gComparisonLength = atoi(argv[3]);
gComparisonLength = gComparisonLength > 15? 15: gComparisonLength;
gComparisonLength = gComparisonLength < 1? 1: gComparisonLength;
/* Read the words into a tree */
if (SUCCESS == Status) {
Status = ReadInputToTree(&Words, &Treecount, fin);
}
/* Sanity check for no sensible input */
if (SUCCESS == Status) {
if (0 == Treecount) {
Status = NO_WORDS_ON_INPUT;
}
}
/* allocate a sufficiently large array */
if (SUCCESS == Status) {
WordArray = malloc(Treecount * sizeof *WordArray);
if (NULL == WordArray) {
Status = CANNOT_MALLOC_WORDARRAY;
}
}
/* Walk the tree into the array */
if (SUCCESS == Status) {
Status = WalkTree(WordArray, Words);
}
/* qsort the array */
if (SUCCESS == Status) {
qsort(WordArray, Treecount, sizeof *WordArray, CompareCounts);
}
/* walk down the WordArray outputting the values */
if (SUCCESS == Status) {
Status = OutputWords(fout, Treecount, WordArray);
}
/* qsort the array */
if (SUCCESS == Status) {
qsort(WordArray, Treecount, sizeof *WordArray, CompareWords);
}
/* walk down the WordArray outputting the values */
if (SUCCESS == Status) {
Status = OutputStemmedWords(fout, Treecount, WordArray);
}
/* free the word array */
if (NULL != WordArray) {
free(WordArray);
WordArray = NULL;
}
/* and free the tree memory */
if (NULL != Words) {
FreeTree(Words);
Words = NULL;
}
/* Error report and we are finshed */
if (SUCCESS != Status) {
fprintf(stderr, "Program failed with code %d\n", Status);
}
return (SUCCESS == Status ? EXIT_SUCCESS : EXIT_FAILURE);
}
void FreeTree(WORD * W)
{
if (NULL != W) {
if (NULL != W->Word) {
free(W->Word);
W->Word = NULL;
}
if (NULL != W->Left) {
FreeTree(W->Left);
W->Left = NULL;
}
if (NULL != W->Right) {
FreeTree(W->Right);
W->Right = NULL;
}
}
}
int AddToTree(WORD ** DestTree, size_t * Treecount, char
*Word)
{
int Status = SUCCESS;
int CompResult = 0;
/* safety check */
assert(NULL != DestTree);
assert(NULL != Treecount);
assert(NULL != Word);
/* ok, either *DestTree is NULL or it isn't (deep huh?) */
if (NULL == *DestTree) { /* this is the place to add it then */
*DestTree = malloc(sizeof **DestTree);
if (NULL == *DestTree) {
/* horrible - we're out of memory */
Status = NO_MEMORY_FOR_WORDNODE;
} else {
(*DestTree)->Left = NULL;
(*DestTree)->Right = NULL;
(*DestTree)->Count = 1;
(*DestTree)->Word = dupstr(Word);
if (NULL == (*DestTree)->Word) {
/* even more horrible - we've run out of memory in the
middle */
Status = NO_MEMORY_FOR_WORD;
free(*DestTree);
*DestTree = NULL;
} else {
/* everything was successful, add one to the tree
nodes count */
++*Treecount;
}
}
} else { /* we need to make a decision */
CompResult = strcmp(Word, (*DestTree)->Word);
if (0 < CompResult) {
Status = AddToTree(&(*DestTree)->Left, Treecount, Word);
} else if (0 > CompResult) {
Status = AddToTree(&(*DestTree)->Left, Treecount, Word);
} else {
/* add one to the count - this is the same node */
++(*DestTree)->Count;
}
} /* end of else we need to make a
decision */
return Status;
}
int ReadInputToTree(WORD ** DestTree, size_t * Treecount,
FILE * Input)
{
int Status = SUCCESS;
char Buf[8192] =
{0};
char *Word = NULL;
/* safety check */
assert(NULL != DestTree);
assert(NULL != Treecount);
assert(NULL != Input);
/* for every line */
while (NULL != fgets(Buf, sizeof Buf, Input)) {
/* strtok the input to get only alpha character words */
Word = strtok(Buf, NONALPHA);
while (SUCCESS == Status && NULL != Word) {
/* deal with this word by adding it to the tree */
Status = AddToTree(DestTree, Treecount, Word);
/* next word */
if (SUCCESS == Status) {
Word = strtok(NULL, NONALPHA);
}
}
}
return Status;
}
int WalkTree(WORD ** DestArray, WORD * Word)
{
int Status = SUCCESS;
static WORD **Write = NULL;
/* safety check */
assert(NULL != Word);
/* store the starting point if this is the first call */
if (NULL != DestArray) {
Write = DestArray;
}
/* Now add this node and it's kids */
if (NULL != Word) {
*Write = Word;
++Write;
if (NULL != Word->Left) {
Status = WalkTree(NULL, Word->Left);
}
if (NULL != Word->Right) {
Status = WalkTree(NULL, Word->Right);
}
}
return Status;
}
/*
CompareCounts is called by qsort. This means that it gets pointers
to the
data items being compared. In this case the data items are pointers
too.
*/
int CompareCounts(const void *vWord1, const void *vWord2)
{
int Result = 0;
WORD *const * Word1 = vWord1;
WORD *const * Word2 = vWord2;
assert(NULL != vWord1);
assert(NULL != vWord2);
/* ensure the result is either 1, 0 or -1 */
if ((*Word1)->Count < (*Word2)->Count) {
Result = 1;
} else if ((*Word1)->Count > (*Word2)->Count) {
Result = -1;
} else {
Result = 0;
}
return Result;
}
int CompareWords(const void *vWord1, const void *vWord2)
{
WORD *const * Word1 = vWord1;
WORD *const * Word2 = vWord2;
assert(NULL != vWord1);
assert(NULL != vWord2);
/* ensure the result is either 1, 0 or -1 */
return i_strcmp((*Word1)->Word, (*Word2)->Word);
}
int CompareWordStems(const void *vWord1, const void
*vWord2)
{
WORD *const * Word1 = vWord1;
WORD *const * Word2 = vWord2;
assert(NULL != vWord1);
assert(NULL != vWord2);
/* ensure the result is either 1, 0 or -1 */
return i_strncmp((*Word1)->Word, (*Word2)->Word, gComparisonLength);
}
int OutputWords(FILE * Dest, size_t Count, WORD **
WordArray)
{
int Status = SUCCESS;
size_t Pos = 0;
/* safety check */
assert(NULL != Dest);
assert(NULL != WordArray);
/* Print a header */
fprintf(Dest, "Total Words : %lu\n", (unsigned long) Count);
/* Print the words in descending order */
while (SUCCESS == Status && Pos < Count) {
fprintf(Dest, "%10lu %s\n", (unsigned long) WordArray[Pos]-
Count, WordArray[Pos]->Word);
++Pos;
}
return Status;
}
int OutputStemmedWords(FILE * Dest, size_t Count, WORD **
WordArray)
{
int Status = SUCCESS;
size_t Pos;
/* safety check */
assert(NULL != Dest);
assert(NULL != WordArray);
/* Print a header */
fprintf(Dest, "Total Words : %lu\n", (unsigned long) Count);
/* Print the words in descending order */
for (Pos = 1; Pos < Count; Pos++) {
if (CompareWordStems(&WordArray[Pos-1], &WordArray[Pos])==0 &&
CompareWords(&WordArray[Pos-1], &WordArray[Pos])!=0)
fprintf(Dest, "%s is similar to %s\n", WordArray[Pos-1]-
Word, WordArray[Pos]->Word);
}
return Status;
}
/* Write a cross-referencer program that prints a list of all words in
a
* document, and, for each word, a list of the line numbers on which
it
* occurs. Remove noise words like "the", "and," and so on.
*/
/* no such thing as strdup, so let's write one
* supplementary question: why did I call this function dupstr,
* rather than strdup?
*
*/
char *dupstr(char *s)
{
char *p = NULL;
if (s != NULL) {
p = malloc(strlen(s) + 1);
if (p) {
strcpy(p, s);
}
}
return p;
}
/* case-insensitive string comparison */
int i_strcmp(const char *s, const char *t)
{
int diff = 0;
char cs = 0;
char ct = 0;
while (diff == 0 && *s != '\0' && *t != '\0') {
cs = tolower((unsigned char) *s);
ct = tolower((unsigned char) *t);
if (cs < ct) {
diff = -1;
} else if (cs > ct) {
diff = 1;
}
++s;
++t;
}
if (diff == 0 && *s != *t) {
/* the shorter string comes lexicographically sooner */
if (*s == '\0') {
diff = -1;
} else {
diff = 1;
}
}
return diff;
}
/* case-insensitive string comparison */
int i_strncmp(const char *s, const char *t, int n)
{
int diff = 0;
int counter = 0;
char cs = 0;
char ct = 0;
while (diff == 0 && *s != '\0' && *t != '\0' && counter++ < n) {
cs = tolower((unsigned char) *s);
ct = tolower((unsigned char) *t);
if (cs < ct) {
diff = -1;
} else if (cs > ct) {
diff = 1;
}
++s;
++t;
}
if (diff == 0 && *s != *t) {
/* the shorter string comes lexicographically sooner */
if (*s == '\0') {
diff = -1;
} else {
diff = 1;
}
}
return diff;
}
void printlist(struct linelist * list, FILE *fout)
{
if (list != NULL) {
printlist(list->next, fout);
fprintf(fout,"%6d ", list->line);
}
}
void printtree(struct wordtree * node, FILE *fout)
{
if (node != NULL) {
printtree(node->left, fout);
fprintf(fout,"%18s ", node->word);
printlist(node->firstline, fout);
fprintf(fout,"\n");
printtree(node->right, fout);
}
}
struct linelist *addlink(int line)
{
struct linelist *new = malloc(sizeof *new);
if (new != NULL) {
new->line = line;
new->next = NULL;
}
return new;
}
void deletelist(struct linelist * listnode)
{
if (listnode != NULL) {
deletelist(listnode->next);
free(listnode);
}
}
void deleteword(struct wordtree ** node)
{
struct wordtree *temp = NULL;
if (node != NULL) {
if (*node != '\0') {
if ((*node)->right != NULL) {
temp = *node;
deleteword(&temp->right);
}
if ((*node)->left != NULL) {
temp = *node;
deleteword(&temp->left);
}
if ((*node)->word != NULL) {
free((*node)->word);
}
if ((*node)->firstline != NULL) {
deletelist((*node)->firstline);
}
free(*node);
*node = NULL;
}
}
}
struct wordtree *addword(struct wordtree ** node, char *word, int
line)
{
struct wordtree *wordloc = NULL;
struct linelist *newline = NULL;
struct wordtree *temp = NULL;
int diff = 0;
if (node != NULL && word != NULL) {
if (NULL == *node) {
*node = malloc(sizeof **node);
if (NULL != *node) {
(*node)->left = NULL;
(*node)->right = NULL;
(*node)->word = dupstr(word);
if ((*node)->word != NULL) {
(*node)->firstline = addlink(line);
if ((*node)->firstline != NULL) {
wordloc = *node;
}
}
}
} else {
diff = i_strcmp((*node)->word, word);
if (0 == diff) {
/* we have seen this word before! add this line number
to the
* front of the line number list. Adding to the end
would
* keep them in the right order, but would take
longer. By
* continually adding them to the front, we take less
time,
* but we pay for it at the end by having to go to the
end of
* the list and working backwards. Recursion makes
this less
* painful than it might have been. */
newline = addlink(line);
if (newline != NULL) {
wordloc = *node;
newline->next = (*node)->firstline;
(*node)->firstline = newline;
}
} else if (0 < diff) {
temp = *node;
wordloc = addword(&temp->left, word, line);
} else {
temp = *node;
wordloc = addword(&temp->right, word, line);
}
}
}
if (wordloc == NULL) {
deleteword(node);
}
return wordloc;
}
/* We can't use strchr because it's not yet been discussed, so we'll
* write our own instead.
*/
char *char_in_string(char *s, int c)
{
char *p = NULL;
/* if there's no data, we'll stop */
if (s != NULL) {
if (c != '\0') {
while (*s != '\0' && *s != c) {
++s;
}
if (*s == c) {
p = s;
}
}
}
return p;
}
/* We can't use strtok because it hasn't been discussed in the text
* yet, so we'll write our own.
* To minimise hassle at the user end, let's modify the user's pointer
* to s, so that we can just call this thing in a simple loop.
*/
char *tokenise(char **s, char *delims)
{
char *p = NULL;
char *q = NULL;
if (s != NULL && *s != '\0' && delims != NULL) {
/* pass over leading delimiters */
while (NULL != char_in_string(delims, **s)) {
++*s;
}
if (**s != '\0') {
q = *s + 1;
p = *s;
while (*q != '\0' && NULL == char_in_string(delims, *q)) {
++q;
}
*s = q + (*q != '\0');
*q = '\0';
}
}
return p;
}
/* return zero if this word is not a noise word,
* or non-zero if it is a noise word
*/
int NoiseWord(char *s)
{
int found = 0;
int giveup = 0;
static const char *const list[] = {
"$",
"0",
"1",
"2",
"3",
"4",
"5",
"6",
"7",
"8",
"9",
"a",
"a's",
"able",
"about",
"above",
"abroad",
"according",
"accordingly",
"across",
"actually",
"adj",
"after",
"afterwards",
"again",
"against",
"ago",
"ahead",
"ain't",
"all",
"allow",
"allows",
"almost",
"alone",
"along",
"alongside",
"already",
"also",
"although",
"always",
"am",
"amid",
"amidst",
"among",
"amongst",
"amoungst",
"amount",
"an",
"and",
"another",
"any",
"anybody",
"anyhow",
"anyone",
"anything",
"anyway",
"anyways",
"anywhere",
"apart",
"appear",
"appreciate",
"appropriate",
"are",
"aren't",
"around",
"as",
"aside",
"ask",
"asking",
"associated",
"at",
"available",
"away",
"awfully",
"b",
"back",
"backward",
"backwards",
"based",
"be",
"became",
"because",
"become",
"becomes",
"becoming",
"been",
"before",
"beforehand",
"begin",
"behind",
"being",
"believe",
"below",
"beside",
"besides",
"best",
"better",
"between",
"beyond",
"bill",
"both",
"bottom",
"brief",
"bring",
"but",
"by",
"c",
"c'mon",
"c's",
"call",
"came",
"can",
"can't",
"cannot",
"cant",
"caption",
"cause",
"causes",
"certain",
"certainly",
"changes",
"clearly",
"co",
"co.",
"com",
"come",
"comes",
"computer",
"con",
"concerning",
"consequently",
"consider",
"considering",
"contain",
"containing",
"contains",
"corresponding",
"could",
"couldn't",
"couldnt",
"course",
"cry",
"currently",
"d",
"dare",
"daren't",
"de",
"definitely",
"describe",
"described",
"despite",
"detail",
"did",
"didn't",
"different",
"directly",
"do",
"does",
"doesn't",
"doing",
"don't",
"done",
"down",
"downwards",
"due",
"during",
"e",
"each",
"edu",
"eg",
"eight",
"eighty",
"either",
"eleven",
"else",
"elsewhere",
"empty",
"en",
"end",
"ending",
"enough",
"entirely",
"especially",
"et",
"etc",
"even",
"ever",
"evermore",
"every",
"everybody",
"everyone",
"everything",
"everywhere",
"ex",
"exactly",
"example",
"except",
"f",
"fairly",
"far",
"farther",
"few",
"fewer",
"fifteen",
"fifth",
"fify",
"fill",
"find",
"fire",
"first",
"five",
"followed",
"following",
"follows",
"for",
"forever",
"former",
"formerly",
"forth",
"forty",
"forward",
"found",
"four",
"from",
"front",
"full",
"further",
"furthermore",
"g",
"get",
"gets",
"getting",
"give",
"given",
"gives",
"go",
"goes",
"going",
"gone",
"got",
"gotten",
"greetings",
"h",
"had",
"hadn't",
"half",
"happens",
"hardly",
"has",
"hasn't",
"hasnt",
"have",
"haven't",
"having",
"he",
"he'd",
"he'll",
"he's",
"hello",
"help",
"hence",
"her",
"here",
"here's",
"hereafter",
"hereby",
"herein",
"hereupon",
"hers",
"herself",
"hi",
"him",
"himself",
"his",
"hither",
"hopefully",
"how",
"howbeit",
"however",
"href",
"http",
"hundred",
"i",
"i'd",
"i'll",
"i'm",
"i've",
"ie",
"if",
"ignored",
"immediate",
"in",
"inasmuch",
"inc",
"inc.",
"including",
"indeed",
"indicate",
"indicated",
"indicates",
"inner",
"inside",
"insofar",
"instead",
"interest",
"into",
"inward",
"is",
"isn't",
"it",
"it'd",
"it'll",
"it's",
"its",
"itself",
"j",
"just",
"k",
"kb",
"keep",
"keeps",
"kept",
"know",
"known",
"knows",
"l",
"la",
"last",
"lately",
"later",
"latter",
"latterly",
"least",
"less",
"lest",
"let",
"let's",
"like",
"liked",
"likely",
"likewise",
"little",
"look",
"looking",
"looks",
"low",
"lower",
"ltd",
"m",
"made",
"mailto",
"mainly",
"make",
"makes",
"making",
"many",
"may",
"maybe",
"mayn't",
"mb",
"me",
"mean",
"means",
"meantime",
"meanwhile",
"merely",
"might",
"mightn't",
"mill",
"mine",
"minus",
"miss",
"more",
"moreover",
"most",
"mostly",
"move",
"mr",
"mrs",
"much",
"must",
"mustn't",
"my",
"myself",
"n",
"name",
"namely",
"nd",
"near",
"nearly",
"necessary",
"need",
"needn't",
"needs",
"neither",
"never",
"neverf",
"neverless",
"nevertheless",
"new",
"next",
"nice",
"nine",
"ninety",
"no",
"no-one",
"nobody",
"non",
"none",
"nonetheless",
"noone",
"nor",
"normally",
"not",
"nothing",
"notwithstanding",
"novel",
"now",
"nowhere",
"o",
"obviously",
"of",
"off",
"often",
"oh",
"ok",
"okay",
"old",
"on",
"once",
"one",
"one's",
"ones",
"only",
"onto",
"opposite",
"or",
"org",
"other",
"others",
"otherwise",
"ought",
"oughtn't",
"our",
"ours",
"ourselves",
"out",
"outside",
"over",
"overall",
"own",
"p",
"part",
"particular",
"particularly",
"past",
"per",
"perhaps",
"piece",
"placed",
"please",
"plus",
"possible",
"presumably",
"probably",
"provided",
"provides",
"put",
"q",
"que",
"quite",
"qv",
"r",
"rather",
"rd",
"re",
"really",
"reasonably",
"recent",
"recently",
"regarding",
"regardless",
"regards",
"relatively",
"respectively",
"right",
"round",
"s",
"said",
"same",
"saw",
"say",
"saying",
"says",
"second",
"secondly",
"see",
"seeing",
"seem",
"seemed",
"seeming",
"seems",
"seen",
"self",
"selves",
"sensible",
"sent",
"serious",
"seriously",
"seven",
"several",
"shall",
"shan't",
"she",
"she'd",
"she'll",
"she's",
"should",
"shouldn't",
"show",
"side",
"since",
"sincere",
"single",
"six",
"sixty",
"so",
"some",
"somebody",
"someday",
"somehow",
"someone",
"something",
"sometime",
"sometimes",
"somewhat",
"somewhere",
"soon",
"sorry",
"specified",
"specify",
"specifying",
"still",
"stuff",
"sub",
"such",
"sup",
"sure",
"system",
"t",
"t's",
"take",
"taken",
"taking",
"tell",
"ten",
"tends",
"th",
"than",
"thank",
"thanks",
"thanx",
"that",
"that'll",
"that's",
"that've",
"thats",
"the",
"their",
"theirs",
"them",
"themselves",
"then",
"thence",
"there",
"there'd",
"there'll",
"there're",
"there's",
"there've",
"thereafter",
"thereby",
"therefore",
"therein",
"theres",
"thereupon",
"these",
"they",
"they'd",
"they'll",
"they're",
"they've",
"thick",
"thin",
"thing",
"things",
"think",
"third",
"thirty",
"this",
"thorough",
"thoroughly",
"those",
"though",
"three",
"through",
"throughout",
"thru",
"thus",
"till",
"to",
"together",
"too",
"took",
"top",
"toward",
"towards",
"tried",
"tries",
"truly",
"try",
"trying",
"twelve",
"twenty",
"twice",
"two",
"u",
"un",
"und",
"under",
"underneath",
"undoing",
"unfortunately",
"unless",
"unlike",
"unlikely",
"until",
"unto",
"up",
"upon",
"upwards",
"us",
"use",
"used",
"useful",
"uses",
"using",
"usual",
"usually",
"v",
"value",
"various",
"ve",
"versus",
"very",
"via",
"viz",
"vs",
"w",
"want",
"wants",
"was",
"wasn't",
"way",
"we",
"we'd",
"we'll",
"we're",
"we've",
"welcome",
"well",
"went",
"were",
"weren't",
"what",
"what'll",
"what's",
"what've",
"whatever",
"when",
"whence",
"whenever",
"where",
"where's",
"whereafter",
"whereas",
"whereby",
"wherein",
"whereupon",
"wherever",
"whether",
"which",
"whichever",
"while",
"whilst",
"whither",
"who",
"who'd",
"who'll",
"who's",
"whoever",
"whole",
"whom",
"whomever",
"whose",
"why",
"will",
"willing",
"wish",
"with",
"within",
"without",
"won't",
"wonder",
"would",
"wouldn't",
"www",
"x",
"y",
"yes",
"yet",
"you",
"you'd",
"you'll",
"you're",
"you've",
"your",
"yours",
"yourself",
"yourselves",
"z",
"zero"
};
int top = sizeof list / sizeof list[0] - 1;
int bottom = 0;
int guess = top / 2;
int diff = 0;
if (s != NULL) {
while (!found && !giveup) {
diff = i_strcmp(list[guess], s);
if (0 == diff) {
found = 1;
} else if (0 < diff) {
top = guess - 1;
} else {
bottom = guess + 1;
}
if (top < bottom) {
giveup = 1;
} else {
guess = (top + bottom) / 2;
}
}
}
return found;
}
/*
* Argh! We can't use fgets()! It's not discussed until page 164.
* Oh well... time to roll our own again...
*/
char *GetLine(char *s, int n, FILE * fp)
{
int c = 0;
int done = 0;
char *p = s;
while (!done && --n > 0 && (c = getc(fp)) != EOF) {
if ((*p++ = c) == '\n') {
done = 1;
}
}
*p = '\0';
if (EOF == c && p == s) {
p = NULL;
} else {
p = s;
}
return p;
}
/*
* Ideally, we'd use a clever GetLine function which expanded its
* buffer dynamically to cope with large lines. Since we can't use
* realloc, and because other solutions would require quite hefty
* engineering, we'll adopt a simple solution - a big buffer.
*
* Note: making the buffer static will help matters on some
* primitive systems which don't reserve much storage for
* automatic variables, and shouldn't break anything anywhere.
*
*/
#define MAXLINE 8192
int main1(int argc, char **argv)
{
static char buffer[MAXLINE] =
{0};
char *s = NULL;
char *word = NULL;
int line = 0;
int giveup = 0;
struct wordtree *tree = NULL;
char *delims = " \t\n\r\a\f\v!\"%^&*()_=+{}[]\
\|/,.<>:;#~?";
FILE *fin = stdin;
FILE *fout = stdout;
if (argc > 1)
fin = theFileIn(argv[1]);
if (argc > 2)
fout = theFileOut(argv[2]);
while (!giveup && GetLine(buffer, sizeof buffer, fin) != NULL) {
++line;
s = buffer;
while (!giveup && (word = tokenise(&s, delims)) != NULL) {
if (!NoiseWord(word)) {
if (NULL == addword(&tree, word, line)) {
fprintf(fout,"Error adding data into memory.
Giving up.\n");
giveup = 1;
}
}
}
}
if (!giveup) {
fprintf(fout,"%18s Line Numbers\n", "Word");
printtree(tree, fout);
}
deleteword(&tree);
return 0;
}
/* K&R 6-1: "Our version of getword() does not properly handle
underscores, string constants, or preprocessor control lines.
Write a better version."
This is intended to be a solution to K&R 6-1 in "category 0" as
defined by the official rules given on Richard Heathfield's "The C
Programming Language Answers To Exercises" page, found at
http://users.powernet.co.uk/eton/kandr2/index.html.
For more information on the language for which this is a lexical
analyzer, please see the comment preceding getword() below.
Note that there is a small modification to my_ungetch() as defined
by
K&R. Hopefully this lies within the rules. */
/* knr61.c - answer to K&R2 exercise 6-1.
Copyright (C) 2000 Ben Pfaff <
[email protected]>.
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA. */
/* Tokens. Other non-whitespace characters self-represent themselves
as tokens. */
/* Main program for testing. */
int main2(int argc, char **argv)
{
FILE *fin = stdin;
FILE *fout = stdout;
if (argc > 1)
fin = theFileIn(argv[1]);
if (argc > 2)
fout = theFileOut(argv[2]);
my_ungetch('\n');
for (;
{
char word[64];
enum token token;
/* Get token. */
token = getword(word, sizeof word, fin);
/* Print token type. */
switch (token) {
case TOK_ID:
fprintf(fout,"id");
break;
case TOK_STRING:
fprintf(fout,"string");
break;
case TOK_CHAR:
fprintf(fout,"char");
break;
case TOK_EOF:
fprintf(fout,"eof\n");
return 0;
default:
fprintf(fout,"other");
word[0] = token;
word[1] = '\0';
break;
}
/* Print token value more or less unambiguously. */
{
const unsigned char *s;
fprintf(fout,"\t'");
for (s = word; *s != '\0'; s++)
if (isprint(*s) && *s != '\'')
fputc(*s, fout);
else if (*s == '\'')
fprintf(fout,"\\'");
else
/* Potentially wrong. */
fprintf(fout,"\\x%02x", *s);
fprintf(fout,"'\n");
}
}
}
/* Parses C-like tokens from fin:
- Parses C identifiers and string and character constants.
- Other characters, such as operators, punctuation, and digits
not part of identifiers are considered as tokens in
themselves.
- Skip comments and preprocessor control lines.
Does not handle trigraphs, line continuation with \, or numerous
other special C features.
Returns a token type. This is either one of TOK_* above, or a
single
character in the range 0...UCHAR_MAX.
If TOK_ID, TOK_STRING, or TOK_CHAR is returned, WORD[] is filled
with the identifier or string value, truncated at LIM - 1
characters and terminated with '\0'.
For other returned token types, WORD[] is indeterminate. */
enum token getword(char *word, int lim, FILE *fin)
{
int beg_line,
c;
for (;
{
beg_line = skipws(fin);
c = my_getch(fin);
if (!beg_line || c != '#')
break;
/* Skip preprocessor directive. */
do {
c = my_getch(fin);
if (c == EOF)
return TOK_EOF;
}
while (c != '\n');
my_ungetch('\n');
}
if (c == EOF)
return TOK_EOF;
else if (c == '_' || isalpha((unsigned char) c)) {
do {
my_putch(&word, &lim, c);
c = my_getch(fin);
}
while (isalnum((unsigned char) c) || c == '_');
my_ungetch(c);
return TOK_ID;
} else if (c == '\'' || c == '"') {
int quote = c;
word[0] = '\0';
while (getstelem(&word, &lim, quote, fin));
return quote == '\'' ? TOK_CHAR : TOK_STRING;
} else
return (unsigned char) c;
}
/* Skips whitespace and comments read from fin.
Returns nonzero if a newline was encountered, indicating that we're
at the beginning of a line. */
static int skipws(FILE *fin)
{
/* Either 0, if we're not inside a comment, or CLS_IN_CMT, if we
are
* inside a comment. */
enum class in_comment = 0;
/* Have we encountered a newline outside a comment? */
int beg_line = 0;
for (;
{
int c; /* Input character. */
enum class class; /* Classification of `c'. */
/* Get an input character and determine its classification. */
c = my_getch(fin);
switch (c) {
case '\n':
if (!in_comment)
beg_line = 1;
/* Fall through. */
case ' ':
case '\f':
case '\r':
case '\t':
case '\v':
class = CLS_WS;
break;
case '/':
/* Outside a comment, slash-star begins a comment. */
if (!in_comment) {
c = my_getch(fin);
if (c == '*')
class = CLS_BEG_CMT;
else {
my_ungetch(c);
c = '/';
class = CLS_OTHER;
}
} else
class = CLS_OTHER;
break;
case '*':
/* Inside a comment, star-slash ends the comment. */
if (in_comment) {
c = my_getch(fin);
if (c == '/')
class = CLS_END_CMT;
else {
my_ungetch(c);
class = CLS_OTHER;
}
} else
class = CLS_OTHER;
break;
default:
/* Other characters. */
if (c == EOF)
return 0;
class = CLS_OTHER;
}
/* Handle character `c' according to its classification and
whether
* we're inside a comment. */
switch (class |in_comment) {
case CLS_WS:
case CLS_WS | CLS_IN_CMT:
case CLS_OTHER | CLS_IN_CMT:
break;
case CLS_BEG_CMT:
in_comment = CLS_IN_CMT;
break;
case CLS_OTHER:
my_ungetch(c);
return beg_line;
case CLS_END_CMT | CLS_IN_CMT:
in_comment = 0;
break;
case CLS_BEG_CMT | CLS_IN_CMT:
case CLS_END_CMT:
default:
fprintf(stderr,"can't happen\n");
break;
}
}
}
/* Get a character inside a quoted string or character constant.
QUOTE is ' for a character constant or " for a quoted string.
*WORDP points to a string being constructed that has *LIMP bytes
available. */
static int getstelem(char **wordp, int *limp, int quote, FILE
*fin)
{
int c;
/* Handle end-of-quote and EOF. */
c = my_getch(fin);
if (c == quote || c == EOF)
return 0;
/* Handle ordinary string characters. */
if (c != '\\') {
my_putch(wordp, limp, c);
return 1;
}
/* We're in a \ escape sequence. Get the second character. */
c = my_getch(fin);
if (c == EOF)
return 0;
/* Handle simple single-character escapes. */
{
static const char escapes[] =
{"''??\"\"\\\\a\ab\bf\fn\nr\rt\tv\v"};
const char *cp = strchr(escapes, c);
if (cp != NULL) {
my_putch(wordp, limp, cp[1]);
return 1;
}
}
/* Handle hexadecimal and octal escapes. This also handles invalid
* escapes by default, doing nothing useful with them. That's okay
* because invalid escapes generate undefined behavior. */
{
unsigned char v = 0;
if (c == 'x' || c == 'X')
for (;
{
static const char hexits[] = "0123456789abcdef";
const char *p;
c = my_getch(fin);
p = strchr(hexits, tolower((unsigned char) c));
if (p == NULL)
break;
v = v * 16 + (p - hexits);
}
else {
int i;
for (i = 0; i < 3; i++) {
v = v * 8 + (c - '0');
c = my_getch(fin);
if (c < '0' || c > '7')
break;
}
}
my_putch(wordp, limp, v);
my_ungetch(c);
}
return 1;
}
/* Capacity of putback buffer. */
#define BUFSIZE 100
/* Putback buffer. */
char buf[BUFSIZE];
/* Number of characters in putback buffer. */
int bufp = 0;
/* Retrieves and returns a character from fin or from the putback
buffer.
Returns EOF if end of file is encountered. */
int my_getch(FILE *fin)
{
return bufp > 0 ? buf[--bufp] : getc(fin);
}
/* Stuffs character C into the putback buffer.
From the caller's perspective, fails silently if the putback buffer
is full. */
static void my_ungetch(int c)
{
if (c == EOF)
return;
if (bufp >= BUFSIZE)
fprintf(stderr,"my_ungetch: too many characters\n");
else
buf[bufp++] = c;
}
/* Stuffs character C into buffer *WORDP, which has *LIMP bytes
available.
Advances *WORDP and reduces *LIMP as appropriate.
Drops the character on the floor if it would overflow the buffer.
Ensures that *WORDP is null terminated if possible. */
static void my_putch(char **wordp, int *limp, int c)
{
if (*limp > 1) {
*(*wordp)++ = c;
(*limp)--;
}
if (*limp > 0)
**wordp = '\0';
}
int main(int argc, char **argv)
{
main0(argc, argv);
fflush(NULL);
main1(argc, argv);
fflush(NULL);
main2(argc, argv);
fflush(NULL);
return 0;
}
