#include <stdio.h> // for printf(), putchar(), NULL
#include <string.h> // for strcmp(), strlen(), strcpy()
#include <stdlib.h> // for malloc(), free()
struct nlist // hash table entry
{
struct nlist *next; // next entry in the chain
char *name; // defined name
char *defn; // replacement text
};
#define HASHSIZE 101 // array size
static struct nlist *
hashtab[HASHSIZE]; // pointer hash table
unsigned hash(char *); // return hash value for string
struct nlist *
lookup(char *); // look for string in hashtab[]
struct nlist * // put (name, defn) in hashtab[]
install(char *name, char *defn);
void printht(); // print hashtab[]
int main()
{ // all values of hashtab[] initialized to NULL:
printht(); // print nothing
install("LENGTH", "100");
install("HASHSIZE", "101");
install("NULL", "0");
install("EOF", "-1");
install("FALSE", "0");
install("TRUE", "1");
install("MAXLINE", "1000");
install("MAXWORD", "100");
install("ARGSEP", ",");
printht();
putchar('\n');
install("HASHSIZE", "100");
install("ARGSEP", "COMMA");
install("COMMA", ",");
printht();
return 0;
}
unsigned hash(char *s) // return hash value for string s
{
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
{hashval = *s + 31 * hashval;}
return hashval % HASHSIZE;
}
struct nlist *
lookup(char *s) // look for string s in hashtab[]
{
struct nlist *np;
for (np = hashtab[hash(s)]; np != NULL; np = np->next)
{
if (strcmp(s, np->name) == 0)
{return np;} // found
}
return NULL; // not found
}
// strdup() is declared by string.h
char * strDup(char *); // duplicate string
struct nlist * // put (name, defn) in hashtab[]
install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;
if ((np = lookup(name)) == NULL) // not found
{
np = (struct nlist *) malloc(sizeof(*np)); // sizeof(struct nlist)
if (np == NULL || (np->name = strDup(name)) == NULL)
{return NULL;}
hashval = hash(name);
np->next = hashtab[hashval]; // old value (previous pointer or NULL)
hashtab[hashval] = np; // update (insert new value into linked list)
} // np is now the beginning of the linked list
else // already there
{free((void *)np->defn);} // free previous defn
if((np->defn = strDup(defn)) == NULL) // update (replace) defn
{return NULL;}
return np;
}
char * strDup(char *s) // make a duplicate of s
{
char *p;
// we assume a char is stored on a byte
p = (char *) malloc (strlen(s) + 1); // +1 for ending '\0'
if (p != NULL)
{strcpy(p, s);}
return p;
}
void printht() // print hashtab[]
{
int i;
struct nlist *np;
for (i = 0; i < HASHSIZE; i++)
{
if (hashtab[i] != NULL)
{
np = hashtab[i];
printf("%d: ", i); // hash value
do
{
printf("(%s, %s), ", np->name, np->defn);
np = np->next;
} while(np != NULL);
putchar('\n');
}
}
}
/*
gcc hash.c -o hash
./hash
36: (ARGSEP, ,), (HASHSIZE, 101),
47: (EOF, -1),
60: (MAXWORD, 100),
67: (TRUE, 1),
73: (MAXLINE, 1000),
74: (LENGTH, 100),
76: (NULL, 0),
78: (FALSE, 0),
36: (ARGSEP, COMMA), (HASHSIZE, 100),
47: (EOF, -1),
54: (COMMA, ,),
60: (MAXWORD, 100),
67: (TRUE, 1),
73: (MAXLINE, 1000),
74: (LENGTH, 100),
76: (NULL, 0),
78: (FALSE, 0),
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
Exercise 6-5. Write a function undef() that will remove a name and definition from the table maintained by lookup() and install().
#include <stdio.h> // for printf(), putchar(), NULL
#include <string.h> // for strcmp(), strlen(), strcpy()
#include <stdlib.h> // for malloc(), free()
struct nlist // hash table entry
{
struct nlist *next; // next entry in the chain
char *name; // defined name
char *defn; // replacement text
};
#define HASHSIZE 101 // array size
static struct nlist *
hashtab[HASHSIZE]; // pointer hash table
unsigned hash(char *); // return hash value for string
struct nlist *
lookup(char *); // look for string in hashtab[]
struct nlist * // put (name, defn) in hashtab[]
install(char *name, char *defn);
void undef(char *name); // remove (name, defn) from hashtab[]
void printht(); // print hashtab[]
int main()
{ // all values of hashtab[] initialized to NULL:
printht(); // print nothing
install("LENGTH", "100");
install("HASHSIZE", "101");
install("NULL", "0");
install("EOF", "-1");
install("FALSE", "0");
install("TRUE", "1");
install("MAXLINE", "1000");
install("MAXWORD", "100");
install("ARGSEP", ",");
printht();
putchar('\n');
undef("FUNCTION");
undef("ARGSEP");
undef("ARGSEP");
undef("MAXLINE");
install("COMMA", ",");
printht();
putchar('\n');
install("FUNCTION", "()");
install("BRACKETS", "[]");
install("BRACES", "{}");
install("ARGSEP", "COMMA");
install("MAXLINE", "1000");
printht();
return 0;
}
unsigned hash(char *s) // return hash value for string s
{
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
{hashval = *s + 31 * hashval;}
return hashval % HASHSIZE;
}
struct nlist *
lookup(char *s) // look for string s in hashtab[]
{
struct nlist *np;
for (np = hashtab[hash(s)]; np != NULL; np = np->next)
{
if (strcmp(s, np->name) == 0)
{return np;} // found
}
return NULL; // not found
}
// strdup() is declared by string.h
char * strDup(char *); // duplicate string
struct nlist * // put (name, defn) in hashtab[]
install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;
if ((np = lookup(name)) == NULL) // not found
{
np = (struct nlist *) malloc(sizeof(*np)); // sizeof(struct nlist)
if (np == NULL || (np->name = strDup(name)) == NULL)
{return NULL;}
hashval = hash(name);
np->next = hashtab[hashval]; // old value (previous pointer or NULL)
hashtab[hashval] = np; // update (insert new value into linked list)
} // np is now the beginning of the linked list
else // already there
{free((void *)np->defn);} // free previous defn
if((np->defn = strDup(defn)) == NULL) // update (replace) defn
{return NULL;}
return np;
}
char * strDup(char *s) // make a duplicate of s
{
char *p;
// we assume a char is stored on a byte
p = (char *) malloc (strlen(s) + 1); // +1 for ending '\0'
if (p != NULL)
{strcpy(p, s);}
return p;
}
void undef(char *name) // remove (name, defn) from hashtab[]
{
struct nlist *np, *prev;
unsigned hashval = hash(name);
if (hashtab[hashval] == NULL) // not found
{
printf("%s is not defined\n", name);
return;
}
// else
np = prev = hashtab[hashval];
if (strcmp(name, np->name) == 0)
{ // found it on the first position in the linked list
free((void *)np->name);
free((void *)np->defn);
hashtab[hashval] = np->next; // could be NULL
return;
}
// else
np = np->next;
while (np != NULL)
{
if (strcmp(name, np->name) == 0) // found it
{
free((void *)np->name);
free((void *)np->defn);
prev->next = np->next; // could be NULL
return;
}
prev = np; // penultimate node read
np = np->next;
}
if (np == NULL) // not found
{
printf("%s is not defined\n", name);
return;
}
}
void printht() // print hashtab[]
{
int i;
struct nlist *np;
for (i = 0; i < HASHSIZE; i++)
{
if (hashtab[i] != NULL)
{
np = hashtab[i];
printf("%d: ", i); // hash value
do
{
printf("(%s, %s), ", np->name, np->defn);
np = np->next;
} while(np != NULL);
putchar('\n');
}
}
}
/*
gcc undef.c -o undef
./undef
36: (ARGSEP, ,), (HASHSIZE, 101),
47: (EOF, -1),
60: (MAXWORD, 100),
67: (TRUE, 1),
73: (MAXLINE, 1000),
74: (LENGTH, 100),
76: (NULL, 0),
78: (FALSE, 0),
FUNCTION is not defined
ARGSEP is not defined
36: (HASHSIZE, 101),
47: (EOF, -1),
54: (COMMA, ,),
60: (MAXWORD, 100),
67: (TRUE, 1),
74: (LENGTH, 100),
76: (NULL, 0),
78: (FALSE, 0),
33: (BRACES, {}),
36: (ARGSEP, COMMA), (HASHSIZE, 101),
47: (EOF, -1),
54: (COMMA, ,),
60: (MAXWORD, 100),
67: (TRUE, 1),
73: (MAXLINE, 1000),
74: (LENGTH, 100),
76: (NULL, 0),
78: (FALSE, 0),
88: (FUNCTION, ()),
92: (BRACKETS, []),
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
Exercise 6-6. Implement a simple version of the #define processor (i.e. no arguments) suitable for use with C programs, based on the routines of this section. You may also find getch() and ungetch() helpful.
As an alternative, we use our own program for macro expansion.
First, we use nocomment from Exercise_1-23, Chapter_1, to remove comments from the test file (test.c), creating the file copy1.c.
Then we use the program define presented below to read the macros and then to expand them in the text, in main(), creating the file copy2.c (preprocessing).
We compile and run the result C file (copy2.c), saving the output to a text file (out2.txt).
At the end, we compare the two output text files (out1.txt and out2.txt) for differences.
#include <stdio.h> // for printf()
#define HASHSIZE 101 // hash size
#define ARRAYSIZE 100 // array size
#define MAXLINE 1000 // max line length
#define MAXWORD 100 // max word length
#define FALSE 0
#define TRUE 1
#define FUNCTION "()"
#define BRACKETS "[]"
#define BRACES "{}"
#define COMMA ','
#define ARGSEP COMMA
#define GREETING "hello"
int main()
{
char word[MAXWORD] = GREETING;
printf("HASHSIZE: %d\n", HASHSIZE);
printf("ARRAYSIZE: %d\n", ARRAYSIZE);
printf("MAXLINE: %d\n", MAXLINE);
printf("GREETING: %s\n", word);
printf("ARGSEP: %c\n", ARGSEP);
printf("FUNCTION: %s\n", FUNCTION);
printf("BRACKETS: %s\n", BRACKETS);
printf("BRACES: %s\n", BRACES);
if (TRUE == FALSE) {printf("True Lies\n");}
return 0;
}
/*
gcc test.c -o test
./test > out1.txt
gcc nocomment.c -o nocomment
./nocomment < test.c > copy1.c
gcc define.c -o define
./define < copy1.c > copy2.c
gcc copy2.c -o copy2
./copy2 > out2.txt
diff -s out1.txt out2.txt
// Files out1.txt and out2.txt are identical
meld out1.txt out2.txt
// Files are identical
rm copy* out* // clean
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
HASHSIZE: 101
ARRAYSIZE: 100
MAXLINE: 1000
GREETING: hello
ARGSEP: ,
FUNCTION: ()
BRACKETS: []
BRACES: {}
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#include <stdio.h> // for getchar(), putchar(), printf(), EOF, NULL
#include <string.h> // for strcmp(), strlen(), strcpy()
#include <stdlib.h> // for malloc(), free()
#include <ctype.h> // for isspace(), isalpha(), isalnum()
#define MAXWORD 100 // max word length
struct nlist // hash table entry
{
struct nlist *next; // next entry in the chain
char *name; // defined name
char *defn; // replacement text
};
#define HASHSIZE 101 // array size
static struct nlist *
hashtab[HASHSIZE]; // pointer hash table
// all values of hashtab[] are initialized to NULL
unsigned hash(char *); // return hash value for string
struct nlist *
lookup(char *); // look for string in hashtab[]
struct nlist * // put (name, defn) in hashtab[]
install(char *name, char *defn);
int main()
{
int i, c1, c2;
char word[MAXWORD], name[MAXWORD], defn[MAXWORD];
struct nlist *np;
while ((c1 = getchar()) != EOF)
{
if (c1 == '#') // include or define
{
c2 = getchar(); // ungetch()
if (c2 == 'i') // include
{
putchar(c1);
putchar(c2);
while((c1 = getchar()) != '\n' && c1 != EOF)
{putchar(c1);}
putchar(c1); // putchar('\n');
}
else // define
{
i = 0;
word[i++] = c1;
word[i++] = c2;
while((c1 = getchar()) != ' ' && c1 != '\t')
{word[i++] = c1;}
word[i] = '\0'; // end string
if(strcmp(word, "#define") == 0)
{ // don't print line
while((c1 = getchar()) == ' ' || c1 == '\t')
{} // skip whitespace
i = 0;
name[i++] = c1;
while(!isspace(c1 = getchar())) // ' '. '\t', '\n'
{name[i++] = c1;}
name[i] = '\0'; // end string
while((c1 = getchar()) == ' ' || c1 == '\t')
{} // skip whitespace
i = 0;
defn[i++] = c1;
while(!isspace(c1 = getchar())) // ' '. '\t', '\n'
{defn[i++] = c1;}
defn[i] = '\0'; // end string
np = lookup(defn);
if (np != NULL) // we should do this repeatedly
{ // until np->defn is no longer in hashtab[]
install(name, np->defn);
}
else {install(name, defn);}
if (c1 != '\n' && c1 != EOF)
{
while((c1 = getchar()) != '\n' && c1 != EOF)
{} // don't print the rest of line
}
}
else // print line
{
printf("%s", word);
putchar(c1);
if (c1 != '\n' && c1 != EOF)
{
while((c1 = getchar()) != '\n' && c1 != EOF)
{putchar(c1);}
putchar(c1); // putchar('\n');
}
}
}
}
else if (c1 == '\"') // skip string (don't process it)
{ // print string
putchar(c1); // putchar('\"');
while ((c1 = getchar()) != '\"')
{putchar(c1);} // here c1 == '\"'
putchar(c1); // putchar('\"');
}
else if (isalpha(c1) || c1 == '_')
{ // possible macro expansion
i = 0;
word[i++] = c1;
while (isalnum(c1 = getchar()))
{word[i++] = c1;}
word[i] = '\0'; // end string
np = lookup(word);
if(np!= NULL)
{printf("%s", np->defn);}
else {printf("%s", word);}
putchar(c1);
}
else {putchar(c1);}
}
return 0;
}
unsigned hash(char *s) // return hash value for string s
{
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
{hashval = *s + 31 * hashval;}
return hashval % HASHSIZE;
}
struct nlist *
lookup(char *s) // look for string s in hashtab[]
{
struct nlist *np;
for (np = hashtab[hash(s)]; np != NULL; np = np->next)
{
if (strcmp(s, np->name) == 0)
{return np;} // found
}
return NULL; // not found
}
// strdup() is declared by string.h
char * strDup(char *); // duplicate string
struct nlist * // put (name, defn) in hashtab[]
install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;
if ((np = lookup(name)) == NULL) // not found
{
np = (struct nlist *) malloc(sizeof(*np)); // sizeof(struct nlist)
if (np == NULL || (np->name = strDup(name)) == NULL)
{return NULL;}
hashval = hash(name);
np->next = hashtab[hashval]; // old value (previous pointer or NULL)
hashtab[hashval] = np; // update (insert new value into linked list)
} // np is now the beginning of the linked list
else // already there
{free((void *)np->defn);} // free previous defn
if((np->defn = strDup(defn)) == NULL) // update (replace) defn
{return NULL;}
return np;
}
char * strDup(char *s) // make a duplicate of s
{
char *p;
// we assume a char is stored on a byte
p = (char *) malloc (strlen(s) + 1); // +1 for ending '\0'
if (p != NULL)
{strcpy(p, s);}
return p;
}
/*
gcc define.c -o define
gcc test.c -o test
./test > out1.txt
gcc nocomment.c -o nocomment
./nocomment < test.c > copy1.c
./define < copy1.c > copy2.c
gcc copy2.c -o copy2
./copy2 > out2.txt
diff -s out1.txt out2.txt
// Files out1.txt and out2.txt are identical
meld out1.txt out2.txt
// Files are identical
rm copy* out* // clean
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#include <stdio.h>
int main()
{
char word[100] = "hello";
printf("HASHSIZE: %d\n", 101);
printf("ARRAYSIZE: %d\n", 100);
printf("MAXLINE: %d\n", 1000);
printf("GREETING: %s\n", word);
printf("ARGSEP: %c\n", ',');
printf("FUNCTION: %s\n", "()");
printf("BRACKETS: %s\n", "[]");
printf("BRACES: %s\n", "{}");
if (1 == 0) {printf("True Lies\n");}
return 0;
}