an example code of TPOP(the practice of programming),why cannot lookup

A

anson

this code is an example code of TPOP, i type them and can be
compiled...
but when give some input , it getting segment fault ....
i observed that when the build() initial the word table ... it invoke
next_word(in the book its name is new() )and invoke the routine
lookup ...but it cannot lookup anything ....and return NULL.

where goes wrong?

below is the code...

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


#define NPREF 2
#define NHASH 4093
#define MAXGEN 10000


struct Suffix {
char *word;
struct Suffix *next;
};

struct State {
char *pref[NPREF];
struct Suffix *suf;
struct State * next;
};


typedef struct State *state_ptr;
typedef struct State state;
typedef struct Suffix suffix;
typedef suffix * suffix_ptr;

state *statetab[NHASH];
char NOWORD[] = "\n"; /* cannot appear as real word */
/* hash: compute hash value for array of NPREF strings */
const int MULTIP = 31; /* for hash() */


void next_word(char *prefix[NPREF], char *suffix);
void addsuffix (state_ptr sp, char *suffix);


unsigned int
hash(char *s[NPREF])
{
unsigned int h;
unsigned char *str;
int i ;

for (i = 0;i < NPREF; i++)
{

for (str =(unsigned char *)s;*str != '\0' ; str++)
h = h * MULTIP + (*str);

}
return h % NHASH;
}


/* lookup: search for prefix ; create if requested */
/* returns pointer if present or created ; NULL if not.
* creation doesn't strdup so string mustn't change later.*/

state_ptr
lookup(char * prefix[NPREF], int create)
{
state_ptr sp;
int h = hash(prefix);
int i;
for (sp = statetab[h]; sp != NULL ; sp = sp->next) {
for ( i=0; i< NPREF; i++)
if (strcmp(prefix, statetab[h]->pref) !=0)
break;
if (i == NPREF) /* we found it */
return sp;
}
if (create) {
sp = (state_ptr)malloc(sizeof(state));
for (i = 0; i < NPREF; i++)
sp->pref = prefix;
sp->suf = NULL;
sp->next = statetab[h];
statetab[h] = sp;
}
return sp;

}

char *
estrdup(char s[])
{
register char *t;

if (NULL == (t = malloc(strlen(s)+1))) {
return(NULL);
}
strcpy(t, s);
return(t);
}



/* build: read input , build prefix table */
void
build (char *prefix[NPREF],FILE *f)
{
char buf[100], fmt[10];
/* create a dymatic format of fscanf */
sprintf(fmt,"%%%ds",sizeof(buf)-1);

while ( fscanf( f, fmt, buf ) != EOF)
next_word (prefix, (char *)estrdup(buf)); /* eatrdup is get a
duplacat buf */

}


/* next_word: add word to suffix list , update prefix */
void
next_word(char *prefix[NPREF], char *suffix)
{
state_ptr sp ;
sp = lookup (prefix, 1); /* create if not find */
addsuffix(sp, suffix);
memmove(prefix, prefix+1, (NPREF-1)*sizeof (prefix[0]));
prefix[NPREF-1] = suffix;

}

/* addsuffix: add to state, suffix must not change later. */
void
addsuffix (state_ptr sp, char *suffix)
{
suffix_ptr sfp;
sfp= (suffix_ptr) malloc( sizeof (suffix));
sfp->word = suffix;
sfp->next = sp->suf;
sp->suf = sfp;
/* smart manipulate of pointer */

}


/* generate: produce output , one word pre line. */
void
generate( int nwords )
{
state_ptr sp;
char *prefix[NPREF], *w;
suffix *suf;
int i , nmatch;

/* reset initial prefix */
for (i = 0 ; i < NPREF; i++)
prefix = NOWORD;

/* main loop */
for (i = 0; i < nwords; i++) {
sp = lookup(prefix, 0);
nmatch = 0;
if (sp == NULL)
fprintf(stderr,"internal error: lookup failed");
for (suf = sp->suf; suf != NULL; suf = suf->next)
if (rand() % ++nmatch == 0)
if (suf->word != NULL)
w = suf->word;
if (strcmp (w, NOWORD) == 0)
break;
printf("%s\n", w);

memmove(prefix , prefix+1, (NPREF-1)*sizeof(prefix[0]));
prefix [NPREF-1] = w;
}
}


int main(void)
{
int i, nwords = MAXGEN;
char *prefix[NPREF]; /* current input prefix */

int c;
long seed;


seed = time(NULL);

srand(seed);
for (i = 0; i < NPREF; i++) /* set up initial prefix */
prefix = NOWORD;
build(prefix, stdin);
next_word(prefix, NOWORD);
generate(nwords);
return 0;
}
 
B

Barry Schwarz

this code is an example code of TPOP, i type them and can be
compiled...
but when give some input , it getting segment fault ....
Click to expand...

I don't get a seg fault but you have some undefined behavior in your
code.
i observed that when the build() initial the word table ... it invoke
next_word(in the book its name is new() )and invoke the routine
lookup ...but it cannot lookup anything ....and return NULL.

where goes wrong?

below is the code...

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


#define NPREF 2
#define NHASH 4093
#define MAXGEN 10000


struct Suffix {
char *word;
struct Suffix *next;
};

struct State {
char *pref[NPREF];
struct Suffix *suf;
struct State * next;
};


typedef struct State *state_ptr;
typedef struct State state;
typedef struct Suffix suffix;
typedef suffix * suffix_ptr;

state *statetab[NHASH];
char NOWORD[] = "\n"; /* cannot appear as real word */
/* hash: compute hash value for array of NPREF strings */
const int MULTIP = 31; /* for hash() */


void next_word(char *prefix[NPREF], char *suffix);
void addsuffix (state_ptr sp, char *suffix);


unsigned int
hash(char *s[NPREF])
{
unsigned int h;
unsigned char *str;
int i ;

for (i = 0;i < NPREF; i++)
{

for (str =(unsigned char *)s;*str != '\0' ; str++)
h = h * MULTIP + (*str);
Click to expand...


This invokes undefined behavior because the h on the right side of the
= operator has not been given a value.
}
return h % NHASH;
}


/* lookup: search for prefix ; create if requested */
/* returns pointer if present or created ; NULL if not.
* creation doesn't strdup so string mustn't change later.*/

state_ptr
lookup(char * prefix[NPREF], int create)
{
state_ptr sp;
int h = hash(prefix);
Click to expand...

Possible undefined behavior. hash() returns an unsigned int and that
value may not fit in the int h.
int i;
for (sp = statetab[h]; sp != NULL ; sp = sp->next) {
for ( i=0; i< NPREF; i++)
if (strcmp(prefix, statetab[h]->pref) !=0)
break;
if (i == NPREF) /* we found it */
return sp;
}
if (create) {
sp = (state_ptr)malloc(sizeof(state));
for (i = 0; i < NPREF; i++)
sp->pref = prefix;
sp->suf = NULL;
sp->next = statetab[h];
statetab[h] = sp;
}
return sp;

}

char *
estrdup(char s[])
{
register char *t;

if (NULL == (t = malloc(strlen(s)+1))) {
return(NULL);
}
strcpy(t, s);
return(t);
}



/* build: read input , build prefix table */
void
build (char *prefix[NPREF],FILE *f)
{
char buf[100], fmt[10];
/* create a dymatic format of fscanf */
sprintf(fmt,"%%%ds",sizeof(buf)-1);
Click to expand...


Possible undefined behavior. %d promises sprintf that the
corresponding argument is an int. sizeof evaluates to a size_t which
could be a different integer type.
while ( fscanf( f, fmt, buf ) != EOF)
next_word (prefix, (char *)estrdup(buf)); /* eatrdup is get a
duplacat buf */
Click to expand...

The cast is meaningless since the return from estrdup() is already a
char*.
}


/* next_word: add word to suffix list , update prefix */
void
next_word(char *prefix[NPREF], char *suffix)
{
state_ptr sp ;
sp = lookup (prefix, 1); /* create if not find */
addsuffix(sp, suffix);
memmove(prefix, prefix+1, (NPREF-1)*sizeof (prefix[0]));
prefix[NPREF-1] = suffix;

}

/* addsuffix: add to state, suffix must not change later. */
void
addsuffix (state_ptr sp, char *suffix)
{
suffix_ptr sfp;
sfp= (suffix_ptr) malloc( sizeof (suffix));
Click to expand...

Don't cast the return from malloc. It cannot help and is unnecessary
since you #include stdlib.h However, you do need to test the return
value to insure malloc succeeded before you attempt to access the
memory requested.
sfp->word = suffix;
sfp->next = sp->suf;
sp->suf = sfp;
/* smart manipulate of pointer */

}


/* generate: produce output , one word pre line. */
void
generate( int nwords )
{
state_ptr sp;
char *prefix[NPREF], *w;
suffix *suf;
int i , nmatch;

/* reset initial prefix */
for (i = 0 ; i < NPREF; i++)
prefix = NOWORD;

/* main loop */
for (i = 0; i < nwords; i++) {
sp = lookup(prefix, 0);
nmatch = 0;
if (sp == NULL)
fprintf(stderr,"internal error: lookup failed");
for (suf = sp->suf; suf != NULL; suf = suf->next)
if (rand() % ++nmatch == 0)
if (suf->word != NULL)
w = suf->word;
if (strcmp (w, NOWORD) == 0)
break;
printf("%s\n", w);

memmove(prefix , prefix+1, (NPREF-1)*sizeof(prefix[0]));
prefix [NPREF-1] = w;
}
}


int main(void)
{
int i, nwords = MAXGEN;
char *prefix[NPREF]; /* current input prefix */

int c;
long seed;


seed = time(NULL);

srand(seed);
for (i = 0; i < NPREF; i++) /* set up initial prefix */
prefix = NOWORD;
build(prefix, stdin);
next_word(prefix, NOWORD);
generate(nwords);
return 0;
}
Click to expand...



Remove del for email
 
D

David Thompson

I don't get a seg fault but you have some undefined behavior in your
code.


Possible undefined behavior. hash() returns an unsigned int and that
value may not fit in the int h.
Click to expand...
In C99 not actually UB; instead either an implementation-defined
conversion or an implementation-defined signal is raised. This is
still unportable, but not the full evil of UB.

Possible undefined behavior. %d promises sprintf that the
corresponding argument is an int. sizeof evaluates to a size_t which
could be a different integer type.
Click to expand...
s/could/must/ as size_t must be unsigned and %d expects signed.
However, if size_t happens to be unsigned int it _probably_ works. For
a user-written vararg function, substituting for a signed int an
unsigned int with a value in the range of signed int -- and here the
value is 99 which is portably within range -- is guaranteed. There is
no explicit provision this works for non-user-written sprintf, but
generally it uses the same mechanism(s) and does.

OTOH size_t can be an unsigned type other than (and larger than)
unsigned int, and then it probably won't work and is definitely UB.

- formerly david.thompson1 || achar(64) || worldnet.att.net
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

If(strcmp(str, "") == 0) - What does this line of code mean? 0
Adding adressing of IPv6 to program 1
Request for source code review of simple Ising model 88
In C, the longest palindromic subsequence multithread exists 0
why could not change the value of char* 17
Why does strcat mess up the tokens in strtok (and strtok_r)? 92
help with small example of file operations 9
New implementation of FSM using functions returning pointers tofunctions of the same type! 10

Members online

Total: 55 (members: 3, guests: 52)
Robots: 397

Forum statistics

Threads
473,982
Messages
2,570,186
Members
46,744
Latest member
CortneyMcK

Latest Threads

Top