wierd behavior in program

[newbiegalore]

Hello everyone ,
I am facing a small problem while coding
up a relatively simple program. I am reading a file with html tags in
it and am storing them in a character stack. The input file looks like
html
head
/head
/html

I read each tag and push it on the stack (cstack) and pop it when I
find the complimentary tag (/html for html and so on). I have declared
the stack as char* cstack[MAXSDEPTH] and assign a value to this by
cstack[a]=line , where line is a char* which holds the input. As I
understand, cstack[a] points to a character string, and so I allocated
some memory to hold the character string like html etc.. When I read
in html, I create its complement, /html and push it in the stack, so
that when I read /html and match it with the top-most element, I can
pop it off the stack. In function pushtag, in my code (attached
below), the second time this function is called and an assignment made
to cstack[1]=line (line is /head), it seems that cstack[0] also
becomes /head, whereas it should remain /html. I checked using GDB,
that as soon as control enters this function for the second time, when
head has been read and /head has been constructed, but has not yet
been assigned to cstack[1], even then cstack[0] equals /head!

If someone spots an obvious pointer assignment error please help me
out. Some idea about how to proceed will be great.

Some debug output from the program.

read html
made /html
line is /html cstack[0] is /html
Stack 0 /html
read head
matching /html and head stack depth 0
line is /head cstack[1] is /head
Stack 0 /head THIS IS THE ERROR!!! cstack[0] should be /
html !!!
Stack 1 /head
read /head
matching /head and /head stack depth 1
popstack depth 2
depth reduced to 1
read /html
matching /head and /html stack depth 0
line is //html cstack[1] is //html
Stack 0 //html
Stack 1 //html
********************************************************************************************************
the actual code.
********************************************************************************************************

#include<stdlib.h>
#include<stdio.h>
#include <string.h>
#define MAXTAGLEN 40
#define MAXDEGREE 500
#define MAXSDEPTH 2500

struct node {
int degree;
char* type;
struct node* next[MAXDEGREE];
struct node* prev;
};

typedef struct node tag;

void initstack(char* cstack[]){
int a;

for(a=0;a<MAXSDEPTH;a++){
cstack[a]=(char*)malloc(sizeof(char)*MAXTAGLEN);
*cstack[a]=(char)a;
printf("init %s\n", cstack[a]);
}
}

void makeendtag(char* tag, char* endtag){
char *tmp;

tmp=(char*)malloc(sizeof(char)*MAXTAGLEN);
memmove (tmp+1,tag,strlen(tag));
*(tmp+0)='/';
strcpy(endtag,tmp);
free(tmp);
}

int checktop(int depth, char* cstack[], char* tag){
int match;

printf("matching %s and %s stack depth %d\n", cstack[depth], tag,
depth);
match=strcmp(cstack[depth], tag);
return(match);
}

void pushtag(int d, char* line, char* cstack[], tag* pointer){
int
a; //
whats going on?
cstack[d]=line;
printf("line is %s cstack[%d] is %s \n", line, d, cstack[d]);
//tstack[d]=pointer;
for(a=0;a<=d;a++)
printf("Stack %d %s\n", a, cstack[a]);
}

void poptag(int depth, char* cstack[]){
printf("popstack depth %d\n", depth);
cstack[depth-1]="000000000000000";
//tstack[depth-1]=NULL;
}

tag* initheadtag(char* line){
int a;

tag* head=(tag*)malloc(sizeof(tag));
head->degree=0;
head->type=line;
for(a=0;a<MAXDEGREE;a++){
head->next[a]=NULL;
head->prev=NULL;
return(head);
}
}

tag* inittag(char* line, int depth){
int a;

tag* curr=(tag*)malloc(sizeof(tag));
curr->degree=0;
curr->type=line;
for(a=0;a<MAXDEGREE;a++){
curr->next[a]=NULL;
/*get top addr*/
//curr->prev=tstack[depth-1];
//curr->prev->next[curr->prev->degree]=curr;
//curr->prev->degree+=1;
return(curr);
}
}

int main(int argc, char **argv) {

FILE *fplong, *fpshort;
int a,b,d,end,lnum,match,lineslong,linesshort;
char *line, tmp[MAXTAGLEN];
char* cstack[MAXSDEPTH];
tag* tstack[MAXSDEPTH];

line=malloc(sizeof(char)*MAXTAGLEN);
for(a=0;a<MAXSDEPTH;a++)
tstack[a]=(tag*)malloc(sizeof(tag*));
/*check input*/
if(argc!=5){
printf("you have entered %d arguments\n", argc);
printf("USAGE: binary-name long-file numoflines-in-longfile short-
file numoflines-in-shortfile\n");
exit(0);
}

/*open files*/
if((fplong=fopen(argv[1],"r"))==NULL){
printf ("Error opening long data file\n");
exit(0);
}

if((fpshort=fopen(argv[3],"r"))==NULL){
printf ("Error opening short data file\n");
exit(0);
}
/*accept inputs*/
lineslong=atoi(argv[2]);
linesshort=atoi(argv[4]);

/*start parsing*/

/*init stack*/
initstack(cstack);
d=0; //depth
end=0;
for(lnum=0;lnum<lineslong;lnum++){
/*read tag*/
fscanf(fplong, "%s", line);
printf("read %s\n", line);

/*is tag == type at top of stack with / at front*/

/*match top of stack*/
if(d>0){
match=checktop(d-1, cstack, line);
/*if match is true*/
if(!match){
/*pop stack*/
poptag(d, cstack);
/*reduce depth*/
--d;
printf("depth reduced to %d\n", d);
/*check if depth 0*/
if(d==0){
printf("reached end\n");
end=1;
}
}
else{
/*make the end tag*/
makeendtag(line, tmp);
/*push tag*/
pushtag(d, tmp, cstack, inittag(line, d));
/*increase depth*/
++d;

}
}
else{
/*make the end tag*/
makeendtag(line, tmp);
printf("made %s\n", tmp);
/*push tag*/
pushtag(d, tmp, cstack, initheadtag(line));
/*increase depth*/
++d;
}
}
return(0);
}

 

[newbiegalore]

So now it seems that the most recent tag I read, after I make the
complement of that (/tag) , this value overwrites all elements of
cstack, cstack[0], [1], [2] ... etc.

 

[newbiegalore]

fixed i1..well not really, coz I used static arrays. If anyone knows
what went wrong here, kindly let me know.

Thanks,
-A

 

[Flash Gordon]

newbiegalore wrote, On 23/02/08 06:12:

below), the second time this function is called and an assignment made
to cstack[1]=line (line is /head), it seems that cstack[0] also
becomes /head, whereas it should remain /html. I checked using GDB,
that as soon as control enters this function for the second time, when
head has been read and /head has been constructed, but has not yet
been assigned to cstack[1], even then cstack[0] equals /head!

If someone spots an obvious pointer assignment error please help me
out. Some idea about how to proceed will be great.

<snip>

In C there is no magic assignment operator for strings, so if you want
to copy strings about you should look up strcpy.

#include<stdlib.h>

They don't charge for spaces and a space would make this more readable.

#include<stdio.h>
#include <string.h>
#define MAXTAGLEN 40
#define MAXDEGREE 500
#define MAXSDEPTH 2500

struct node {
int degree;
char* type;
struct node* next[MAXDEGREE];
struct node* prev;
};

typedef struct node tag;

void initstack(char* cstack[]){
int a;

for(a=0;a<MAXSDEPTH;a++){
cstack[a]=(char*)malloc(sizeof(char)*MAXTAGLEN);

Loose the cast, it isn't needed, makes the code harder to read and on
some implementations will hide the warning/error if you fail to include
stdlib.h
cstack[a] = malloc(sizeof(char)*MAXTAGLEN);
Then be aware that this relies on you keeping types in sink. You can
reduce maintenance work by doing
cstack[a] = malloc(MAXTAGLEN * sizeof *cstack[a]);
See, you don't need to look up to check the type is correct or change
this line if the type changes. Then, of course, since this is a string
and likely to always be one, and char is 1 byte by definition in C we
can drop the sizeof completely.
cstack[a] = malloc(MAXTAGLEN);
Far simpler.

If you are always going to have a fixed size you might as well have an
array in the structure rather than a pointer. If you are going to use a
pointer you might as well initialise it to NULL and then only allocate
the space when you know how much you need and you need it.

*cstack[a]=(char)a;

Why the cast? It does you no good. It also does not magically create a
string and I'm not sure what you are trying to achieve by it.

printf("init %s\n", cstack[a]);

Given that you haven set up a string

}
}

void makeendtag(char* tag, char* endtag){
char *tmp;

tmp=(char*)malloc(sizeof(char)*MAXTAGLEN);
memmove (tmp+1,tag,strlen(tag));

This won't copy the nul termination so it won't be a string

*(tmp+0)='/';
strcpy(endtag,tmp);

Making this strcpy invalid.

In any case, you could have avoided the extra allocation by simply doing
endtag[0] = '/';
strcpy(endtag+1,tag);

free(tmp);
}

int checktop(int depth, char* cstack[], char* tag){
int match;

printf("matching %s and %s stack depth %d\n", cstack[depth], tag,
depth);
match=strcmp(cstack[depth], tag);
return(match);
}

void pushtag(int d, char* line, char* cstack[], tag* pointer){
int
a; //
whats going on?

Please don't use stupidly long lines and don't use // style comments
when posting to news groups. It meant that rather than being able to
copy/paste and then compile you code I first had to fix the
line-wrapping which made the program invalid.

cstack[d]=line;

This does not copy the contents of the line array to cstack[d], rather
it overwrites the pointer to your allocated space with a pointer to
line. You know about strcpy as you used it earlier so why did you not
use it here?

printf("line is %s cstack[%d] is %s \n", line, d, cstack[d]);
//tstack[d]=pointer;
for(a=0;a<=d;a++)
printf("Stack %d %s\n", a, cstack[a]);
}

void poptag(int depth, char* cstack[]){
printf("popstack depth %d\n", depth);
cstack[depth-1]="000000000000000";
//tstack[depth-1]=NULL;
}

tag* initheadtag(char* line){
int a;

tag* head=(tag*)malloc(sizeof(tag));

Again, it would be simpler to use
tag *head = malloc(sizeof *tag);
Note also the change to the spacing. This is because if you do
tag* head,foo;
foo will NOT be a pointer but a variable of type tag.

head->degree=0;
head->type=line;
for(a=0;a<MAXDEGREE;a++){
head->next[a]=NULL;
head->prev=NULL;
return(head);

You do not need the parenthesis
return head;

}
}

tag* inittag(char* line, int depth){
int a;

tag* curr=(tag*)malloc(sizeof(tag));

See previous comment.

curr->degree=0;
curr->type=line;
for(a=0;a<MAXDEGREE;a++){
curr->next[a]=NULL;
/*get top addr*/
//curr->prev=tstack[depth-1];
//curr->prev->next[curr->prev->degree]=curr;
//curr->prev->degree+=1;
return(curr);
}
}

int main(int argc, char **argv) {

FILE *fplong, *fpshort;
int a,b,d,end,lnum,match,lineslong,linesshort;
char *line, tmp[MAXTAGLEN];
char* cstack[MAXSDEPTH];
tag* tstack[MAXSDEPTH];

line=malloc(sizeof(char)*MAXTAGLEN);

Why bother making line malloc'd rather than a simple array?

for(a=0;a<MAXSDEPTH;a++)
tstack[a]=(tag*)malloc(sizeof(tag*));
/*check input*/
if(argc!=5){
printf("you have entered %d arguments\n", argc);
printf("USAGE: binary-name long-file numoflines-in-longfile short-
file numoflines-in-shortfile\n");
exit(0);
}

/*open files*/
if((fplong=fopen(argv[1],"r"))==NULL){
printf ("Error opening long data file\n");
exit(0);

It would be more conventional to return an error, i.e.
exit(EXIT_FAILURE);
Or
return EXIT_FAILURE;

}

if((fpshort=fopen(argv[3],"r"))==NULL){
printf ("Error opening short data file\n");
exit(0);
}
/*accept inputs*/
lineslong=atoi(argv[2]);
linesshort=atoi(argv[4]);

atoi is generally bad. Look up the strto functions which allow you to do
some error checking.

/*start parsing*/

/*init stack*/
initstack(cstack);
d=0; //depth
end=0;
for(lnum=0;lnum<lineslong;lnum++){
/*read tag*/
fscanf(fplong, "%s", line);

<snip>

NEVER use fscanf like that. In the same vain, NEVER use gets. Either use
fgets or use a length specifier if you use fscanf. Note that the scanf
family is tricky to use correctly when you are inexperienced.

I've not checked the rest of your code.

 

[newbiegalore]

wow thanks a ton for the detailed and extremely helpful
commentary..super!!

I'll make an effort to be a better coder.

Thanks for your time,
-A