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[i];*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[i], statetab[h]->pref[i]) !=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[i] = prefix[i];
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[i] = 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[i] = NOWORD;
build(prefix, stdin);
next_word(prefix, NOWORD);
generate(nwords);
return 0;
}

[Barry Schwarz]

On 20 Apr 2007 09:19:32 -0700, anson <kz****@gmail.comwrote:

>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[i];*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[i], statetab[h]->pref[i]) !=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[i] = prefix[i];
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[i] = 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[i] = NOWORD;
build(prefix, stdin);
next_word(prefix, NOWORD);
generate(nwords);
return 0;
}

Remove del for email

[David Thompson]

On Sat, 28 Apr 2007 17:42:40 -0700, Barry Schwarz <sc******@doezl.net>
wrote:

On 20 Apr 2007 09:19:32 -0700, anson <kz****@gmail.comwrote:

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.

<snip mostly good comments>

int h = hash(prefix);

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.

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.

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