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

Discussion in 'C Programming' started by anson, Apr 20, 2007.

  1. anson

    anson Guest

    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;
    }
     
    anson, Apr 20, 2007
    #1
    1. Advertising

  2. On 20 Apr 2007 09:19:32 -0700, anson <> wrote:

    >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
     
    Barry Schwarz, Apr 29, 2007
    #2
    1. Advertising

  3. On Sat, 28 Apr 2007 17:42:40 -0700, Barry Schwarz <>
    wrote:

    > On 20 Apr 2007 09:19:32 -0700, anson <> wrote:
    >
    > >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
     
    David Thompson, May 21, 2007
    #3
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Frank Ratzlow

    Cannot lookup DataSource from JBoss ...

    Frank Ratzlow, Jan 7, 2004, in forum: Java
    Replies:
    5
    Views:
    9,137
    John C. Bollinger
    Jan 19, 2004
  2. Mr. SweatyFinger

    why why why why why

    Mr. SweatyFinger, Nov 28, 2006, in forum: ASP .Net
    Replies:
    4
    Views:
    978
    Mark Rae
    Dec 21, 2006
  3. Mr. SweatyFinger
    Replies:
    2
    Views:
    2,221
    Smokey Grindel
    Dec 2, 2006
  4. =?ISO-8859-1?Q?Martin_J=F8rgensen?=

    cannot compile the following example code (person-pointer)

    =?ISO-8859-1?Q?Martin_J=F8rgensen?=, Mar 25, 2006, in forum: C++
    Replies:
    26
    Views:
    678
    Alex Buell
    Mar 31, 2006
  5. xie bo
    Replies:
    1
    Views:
    378
    Jim Langston
    Jul 7, 2006
Loading...

Share This Page