I am trying to do Exercise 6-2 of K&R, the text of the exercise is:
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 strings and comments. Make 6 a parameter that can be set from the command line.
The way I tried to resolve this is by having two structures, a structure group which will contain groups of words with identical 6 first characters:
struct group {
struct group *left;
struct group *right;
struct word *word;
};
left and right point to the groups immediately preceding and immediately following the current one alphabetically, the structure word:
struct word{
char *value;
struct word *left;
struct word *right;
};
will contain the string for a word read on the input in value, left and right point to the words immediately preceding and immediately following the current one alphabetically.
I use the functions addgroupand addword to allocate memory for new groups/words :
struct word *addword(struct word *w, char *s)
{
printf("[START]: addword(%s, %s)\n", (w == NULL ? "(null)": w->value), s);
if(w == NULL){
struct word *new_word = (struct word *) malloc(sizeof(struct word));
if(new_word) {
printf("[START]: Creating new word %s \n", s);
new_word->left = NULL;
new_word->right = NULL;
new_word->value = strdup(s);
printf("[END]: Created new word %s \n", new_word->value);
return new_word;
}
else{
printf("ERROR: Couldn't allocate memory for %s\n", s);
return NULL;
}
}
else if(strcmp(s, w->value) < 0){
printf("[START]: Adding %s to left of %s\n", s, w->value);
w->left = addword(w->left, s);
printf("[END]: Added %s to left of %s\n", s, w->value);
}
else if(strcmp(s, w->value) > 0){
printf("[START]: Adding %s to right of %s\n", s, w->value);
w->right = addword(w->right, s);
printf("[END]: Added %s to right of %s\n", s, w->value);
}
return w;
}
struct group *galloc()
{
return (struct group *) malloc(sizeof(struct group));
}
struct group *addgroup(struct group *g, char *s)
{
char *temp;
if(g == NULL)
{
temp = strndup(s, 6);
printf("[START]: creating new group %s\n", temp);
struct group *new_group = galloc();
if(new_group) {
new_group->left = NULL;
new_group->right = NULL;
new_group->word = addword(NULL, s);
printf("[END]: created new group %s\n", temp);
return new_group;
}
else{
printf("[ERROR]: Could not allocate space to new group\n");
return NULL;
}
}
else if(strncmp(s, (g->word)->value, 6) < 0) {
printf("[START]: Adding word %s to left of group %s \n", s, strncpy(temp, (g->word)->value, 6));
g->left = addgroup(g->left, s);
printf("[END]: Added word %s to left of group %s \n", s, strncpy(temp, (g->word)->value, 6));
}
else if(strncmp(s, (g->word)->value, 6) > 0) {
printf("[START]: Adding word %s to right of group %s \n", s, strncpy(temp, (g->word)->value, 6));
g->right = addgroup(g->right, s);
printf("[END]: Added word %s to right of group %s \n", s, strncpy(temp, (g->word)->value, 6));
}
else {
printf("[START]: Adding word %s to group %s \n", s, strncpy(temp, (g->word)->value, 6));
g->word = addword(g->word, s);
printf("[END]: Added word %s to group %s \n", s, strncpy(temp, (g->word)->value, 6));
}
return g;
}
My problem: The code works for the first 3 words and then crashes with a segmentation fault (core dumped) error, here's an example of output (in my main function I print the whole tree of groups after each new word):
> Falsefiable
[START]: creating new group Falsef
[START]: addword((null), Falsefiable)
[START]: Creating new word Falsefiable
[END]: Created new word Falsefiable
[END]: created new group Falsef
Falsefiable
...After adding words Falsefact, Falsefiable, and Printingpress, all without a problem...
Falsefact
Falsefiable
Printingpress
> Printing
[START]: Adding word Printing to right of group Falsef
[START]: Adding word Printing to group Printi
[START]: addword(Printingpress, Printing)
[START]: Adding Printing to left of Printingpress
[START]: addword((null), Printing)
[START]: Creating new word Printing
[END]: Created new word Printing
[END]: Added Printing to left of Printingpress
[END]: Added word Printing to group Printi
[END]: Added word Printing to right of group Falsef
Segmentation fault (core dumped)
Using valgrind all I could learn was that the problem is caused by Access not within mapped region at address
Any idea what I am doing wrong ?
EDIT 1: my main function
#define MAXWORD 100
int main(int agrc, char *argv[])
{
char word[MAXWORD];
struct group *root = NULL;
while( getword(word, MAXWORD) != EOF)
if(isalpha(word[0])){
root = addgroup(root, word);
printgroup(root);
}
return 0;
}
functions getword:
char getword(char *word, int l)
{
int c, i;
while(isspace(c = getch()))
;
i = 0;
word[i++] = c;
if(!isalpha(c)){
word[i] = '\0';
return c;
}
while(isalnum(c = getch()) && i < l-1)
word[i++] = c;
word[i] = '\0';
ungetch(c);
return word[0];
}
and getch/ungetch:
#define BUFFSIZE 100
int buffer[BUFFSIZE];
int buffp = 0;
int getch(void)
{
if(buffp > 0)
return buffer[--buffp];
else
return getchar();
}
void ungetch(int c)
{
if(buffp < BUFFSIZE - 1)
buffer[buffp++] = c;
else
printf("ERROR: Not enough space in buffer\n");
}
EDIT 2: cleaning question and adding valgrindoutput
This is what valgrind's output right after the last line of the program's output when crash happens :
[END]: Added word Printing to right of group Falsef
==13993== Invalid write of size 8
==13993== at 0x1090CB: main (in /home/me/The C Programming Language/Chapter 6/6-2/main)
==13993== Address 0x69746e6971d8 is not stack'd, malloc'd or (recently) free'd
==13993==
==13993==
==13993== Process terminating with default action of signal 11 (SIGSEGV): dumping core
==13993== Access not within mapped region at address 0x69746E6971D8
==13993== at 0x1090CB: main (in /home/me/The C Programming Language/Chapter 6/6-2/main)
==13993== If you believe this happened as a result of a stack
==13993== overflow in your program's main thread (unlikely but
==13993== possible), you can try to increase the size of the
==13993== main thread stack using the --main-stacksize= flag.
==13993== The main thread stack size used in this run was 8720384.
==13993==
==13993== HEAP SUMMARY:
==13993== in use at exit: 203 bytes in 12 blocks
==13993== total heap usage: 14 allocs, 2 frees, 2,251 bytes allocated
==13993==
==13993== LEAK SUMMARY:
==13993== definitely lost: 14 bytes in 2 blocks
==13993== indirectly lost: 0 bytes in 0 blocks
==13993== possibly lost: 0 bytes in 0 blocks
==13993== still reachable: 189 bytes in 10 blocks
==13993== suppressed: 0 bytes in 0 blocks
==13993== Rerun with --leak-check=full to see details of leaked memory
==13993==
==13993== For counts of detected and suppressed errors, rerun with: -v
==13993== Use --track-origins=yes to see where uninitialised values come from
==13993== ERROR SUMMARY: 315 errors from 67 contexts (suppressed: 0 from 0)
Segmentation fault (core dumped)
There is at least one problem here:
struct group *addgroup(struct group *g, char *s)
{
char *temp;
if (g == NULL)
{
temp = strndup(s, 6);
...
}
else if (strncmp(s, (g->word)->value, 6) < 0) {
printf("[START]: Adding word %s to left of group %s \n", s, strncpy(temp, (g->word)->value, 6));
... ^
|
temp may be uninitialized here |
If g is not NULL, then temp is not initialized and dereferencing an uninitialized pointer will result in all sorts of nasty things AKA undefined behaviour.