Kernighan and Richie problem

[maur3r]

I was trying to improve one of the programs from ANSI C (Kernighan's book) but I have encountered a very annoying problem and can't find out what's wrong. The idea of the program is to count words in a file in such a way:
==file example:==
Hey teacher leave leave the kids alone alone
==result:==
alone - 2
hey - 2
leave - 2
kids - 1
teacher -1
the -1

The program bases on "binary tree" method but I was trying to create an array of ** to every node. But I cannot figure why it doesn't work. Here's the code

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>

struct tnode{
char *word;
int count;
struct tnode *left;
struct tnode *right;
}***fruits=NULL;

int tcurrsize=0;


void print(void)
{
int i;
for(i=0;i<tcurrsize;i++)
printf("%s\n",((**(fruits[i])).word));
printf("==========\n");
}

void localizeNewFruit(struct tnode** newFruit){
struct tnode ***tmpfruits;
tmpfruits=realloc(fruits,tcurrsize*sizeof(struct tnode **));
 if(tmpfruits)
  fruits=tmpfruits;
 else{
  perror("Memmory error");
  free(fruits);
  exit(1);
 }
fruits[tcurrsize-1]=newFruit;
}


struct tnode* addtree(struct tnode *p, char *w){
int cond;
struct tnode **new;
if(p==NULL){
 if((p=malloc(sizeof(struct tnode)))!=NULL);
 else{
 perror("M E");
 }
 p->word=w;
 p->count=1;
 p->left=p->right=NULL;
 new=&p;
 ++tcurrsize;
 localizeNewFruit(new);
 }
else if((cond=strcmp(w,p->word))==0){
 p->count++;
 free(w);
 }
else if(cond<0)
 p->left=addtree(p->left,w);
else if(cond>0)
 p->right=addtree(p->right,w);
return p;
}


char* getword (FILE* infile){
	char *word = NULL, *tmpword, ch;
	size_t currsize=1, currpos=0;
 		while ( (ch=fgetc(infile))!=EOF && (isalpha(ch)) ){
			if (currpos>=currsize-1){
				currsize *=2;
				tmpword=realloc(word, currsize);
					if (tmpword)
						word=tmpword;
					else{
					perror("Memory problem");
					free(word);
					return NULL;
					}
			}
		word[currpos++]=ch;
	}
	if (currpos){
		word[currpos]='\0';
		return word;
		}
	else if (isprint(ch) || iscntrl(ch))
		return strdup (" ");
	else
		return NULL;

}



int main(int argc, char *argv[])
{
char * word;
FILE * infile;
struct tnode *newNode=NULL;
int i;
if (argc!=2){
		printf ("Argument error \n");
		return 1;
	}

infile=fopen(argv[1],"r");
	if (!infile){
	perror("File error");
	exit(1);
	}

while ((word=getword(infile))!=NULL){
		if (!(strcmp(" ",word)))
			free(word);
		else{
		newNode=addtree(newNode,word);
		}
}
print(); /*receive Segmentation fault*/
fclose(infile);
return 0;
}

Martin

 

[GoAskAlice]

I only know this from experience - when I was working on a large file and allocating memory I received a segmentation fault because I ran out of memory.

I am only a beginner with C (started last week) but this is the problem I had when working with large files.

 

[Salem]

Get rid of everything associated with 'fruit'.
1. It's not necessary.
2. It's got at least one too many levels of unnecessary indirection.

Your print function should print a tree, using the same logic you used to build the tree in the first place.

> struct tnode **new;
You don't need this variable either - you never use it except to assign something to it.

--

 

[maur3r]

struct tnode **new;
You don't need this variable either - you never use it except to assign something to it."
Yes I know but originally I was trying to use function print in order to free allocated memory. Prototype:

void print/*rather free*/(void)
{
int i;
for(i=0;i<tcurrsize;i++){
free((**(fruits[i])).word));
free((**(fruits[i])));
}
}

But when I received Segm Fault I was trying to use printf approach to find errors because when running with gdb everything seems ok and suddenly crash occurs. I cannot find any other method to free all nodes in the tree because random freeing causes losing important left and right pointers to the next node.

Martin

 

[maur3r]

OK I fixed it.

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>

struct tnode{
char *word;
int count;
struct tnode *left;
struct tnode *right;
}**fruits=NULL;

int tcurrsize=0;


void localizeNewFruit(struct tnode* newFruit){
struct tnode **tmpfruits;
tmpfruits=realloc(fruits,tcurrsize*sizeof(struct tnode **));
 if(tmpfruits)
  fruits=tmpfruits;
 else{
  perror("Memmory error");
  free(fruits);
  exit(1);
 }
fruits[tcurrsize-1]=newFruit;
}

void rm(void)
{
int i;
for(i=0;i<tcurrsize;i++){
free(((*(fruits[i])).word));
free((fruits[i]));
}
if(fruits)
free(fruits);
}

struct tnode* addtree(struct tnode *p, char *w){
int cond;
struct tnode *new;
if(p==NULL){
 if((p=malloc(sizeof(struct tnode)))!=NULL);
 else{
 perror("M E");
 }
 p->word=w;
 p->count=1;
 p->left=p->right=NULL;
 new=p;
 ++tcurrsize;
 localizeNewFruit(new);
 }
else if((cond=strcmp(w,p->word))==0){
 p->count++;
 free(w);
 }
else if(cond<0)
 p->left=addtree(p->left,w);
else if(cond>0)
 p->right=addtree(p->right,w);
return p;
}


void treePrint(struct tnode *p){
if(p!=NULL){
treePrint(p->left);
printf("%4d  -  %s \n", p->count, p->word);
treePrint(p->right);
}
} 

char* getword (FILE* infile){
	char *word = NULL, *tmpword, ch;
	size_t currsize=1, currpos=0;
 		while ( (ch=fgetc(infile))!=EOF && (isalpha(ch)) ){
			if (currpos>=currsize-1){
				currsize *=2;
				tmpword=realloc(word, currsize);
					if (tmpword)
						word=tmpword;
					else{
					perror("Memory problem");
					free(word);
					return NULL;
					}
			}
		word[currpos++]=ch;
	}
	if (currpos){
		word[currpos]='\0';
		return word;
		}
	else if (isprint(ch) || iscntrl(ch))
		return strdup (" ");
	else
		return NULL;

}



int main(int argc, char *argv[])
{
char * word;
FILE * infile;
struct tnode *newNode=NULL;
if (argc!=2){
		printf ("Argument error \n");
		return 1;
	}

infile=fopen(argv[1],"r");
	if (!infile){
	perror("File error");
	exit(1);
	}

while ((word=getword(infile))!=NULL){
		if (!(strcmp(" ",word)))
			free(word);
		else{
		newNode=addtree(newNode,word);
		}
	}
treePrint(newNode);
rm();	/*improved free*/
fclose(infile);
return 0;
}

Still I don't know why it wasn't working when I used ***fruits. In fact it is one * more but still it should have indicated the proper block in memory.

Martin

 

[Salem]

> I cannot find any other method to free all nodes in the tree
The same way that you add stuff or print stuff.

You recurse your way down to a leaf and free that, at which point the parent becomes a leaf as well (so it can be freed) all the way back up to the root of the tree.



--