Reply to thread

Message: [QUOTE="anson, post: 2864758"] 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; }[/i][/i][/i][/i][/i][/i][/i] [/QUOTE]

Verification