tpop(3.3): Building the Data Structure in C

/**
  tpop(3): Design and Implementation
  created on Jul 14, 2011
  */

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

enum {
    NPREF = 2, /* number of prefix words */
    NHASH = 4093, /* size of state hash table array */
    MAXGEN = 10000 /* maxium words generated */
};
char NONWORD[] = "\n"; /* cannot appear as real word */

typedef struct State State;
typedef struct Suffix Suffix;
struct State { /* prefix + suffix list */
    char *pref[NPREF]; /* prefix words */
    Suffix *suf; /* list of suffix */
    State *next; /* next in hash table */
};

struct Suffix { /* list of suffixes */
    char *word; /* suffix */
    Suffix *next; /* next in list of suffixes */
};

State *statetab[NHASH]; /* hash table of states */
State *lookup(char *prefix[], int create);
void build(char *prefix[], FILE*);
void generate(int nwords);
void add(char *prefix[], char *word);
void addsuffix(State *, char *);

//char NONWORD[] = "\n"; /* cannot appear as real word */
const int MULTIPLIER = 31; /* for hash() */


/* hash: compute hash value for array of NPREF strings*/
unsigned int hash(char *s[NPREF])
{
    unsigned int h;
    unsigned char *p;
    int i;

    h = 0;
    for (i = 0; i < NPREF; i++)
      for (p = (unsigned char *)s[i]; *p != '\0'; p++)// *p not  '\0'
    h = MULTIPLIER * h + *p;
    return h % NHASH;
}



/* lookup: search for prefix; create if requested.
/* returns pointer if present or created; NULL if not.
/* creation doesn't strdup so strings mustn't change later.*/
State* lookup(char *prefix[NPREF], int create)
{
    int i, h;
    State *sp;

    h = hash(prefix);
      for (sp = statetab[h]; sp != NULL; sp = sp->next) {
    for (i = 0; i < NPREF; i ++)
      if(strcmp(prefix[i], sp->pref[i]) != 0)
        break;
    if (i == NPREF)  /* found it */
      return sp;
    }
    if (create) {
    sp = (State*)emalloc(sizeof(State));
    for (i = 0; i < NPREF; i++)
      sp->pref[i] = prefix[i];
    sp->suf = NULL;
    sp->next = statetab[h];
    statetab[h] = sp;
    printf("running lookup here?\n");
    }
    return sp;
}

/* build: read input, build prefix table */
void build(char *prefix[NPREF], FILE *f)
{
    char buf[100], fmt[10];
    //* create a format string; %s could overflow buf
    sprintf(fmt, "%%%ds", sizeof(buf)-1);
    while (fscanf(f, fmt, buf) != EOF)
      add(prefix, estrdup(buf));
}

/* add: add word to suffix list, update prefix */
void add(char *prefix[NPREF], char *suffix)
{
    State *sp;

    sp = lookup(prefix, 1); /* create if not found */
    addsuffix(sp, suffix);
    /* move the words down the prefix */
    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 *sp, char *suffix)
{
    Suffix *suf;

    suf = (Suffix *)emalloc(sizeof(Suffix));
    suf->word = suffix;
    suf->next = sp->suf;
    sp->suf = suf;
}


/* generate: produce output, one word per line */
void generate(int nwords)
{
    State *sp;
    Suffix *suf;
    char *prefix[NPREF], *w;
    int i, nmatch;

    for (i = 0; i < NPREF; i++) /* reset initial prefix */
      prefix[i] = NONWORD;

    for (i = 0; i < nwords; i++) {
    sp = lookup(prefix, 0);
    if (sp == NULL)
      eprintf("internal error: lookup failed");
    nmatch = 0;
    for (suf = sp->suf; suf != NULL; suf = suf->next)
      if (rand() % ++nmatch == 0) /* prob=1/nmatch */
        w = suf->word;
    if (nmatch == 0)
      eprintf("internal error: no suffix %d %s", i, prefix[0]);
    if (strcmp(w, NONWORD) == 0)
      break;
    printf("%s\n", w);
    memmove(prefix, prefix+1, (NPREF-1)*sizeof(prefix[0]));
    prefix[NPREF-1] = w;
    }
}

/* markov main: markov-chain random text generation */
int main(void)
{
    int i, nwords = MAXGEN;
    char *prefix[NPREF]; /* current input prefix */
    long seed;

//    setprogram("markov");
    seed = time(NULL);
    srand(seed);
    for (i = 0; i < NPREF; i++) /* set up initial prefix */
      prefix[i] = NONWORD;
    build(prefix, stdin);
  //  printf("Building is done.\n");
    add(prefix, NONWORD);
    generate(nwords);
    return 0;
}///:~

Makefile:
markov: markov.o eprintf.o
    gcc -o markov markov.o eprintf.o
eprintf.o: eprintf.c eprintf.h
    gcc -c -I -o eprintf.o eprintf.c
markov.o: markov.c
    gcc -c -o markov.o markov.c
clean:
    rm -f markov *.o