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

[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;
}

 

[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 ....

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);

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);

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);

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 */

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));

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;
}

Remove del for email

 

[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.

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.

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