_C PROGRAMMING COLUMN_
by Al Stevens

[LISTING ONE]

/* ----------- textsrch.h ---------- */

#define OK    0
#define ERROR !OK

#define MXTOKS 25           /* maximum number of tokens */
#define MAXFILES 512        /* maximum number of files  */
#define MAPSIZE MAXFILES/16 /* number of ints/map       */

/* ---- the search decision bitmap (one bit per file) ---- */
struct bitmap {
    int map[MAPSIZE];
};

/* ------- the postfix expression structure -------- */
struct postfix  {
    char pfix;      /* tokens in postfix notation */
    char *pfixop;   /* operand strings            */
};

/* --------- the postfix stack ---------- */
extern struct postfix pftokens[];
extern int xp_offset;

/* --------- expression token values ---------- */
#define TERM     0
#define OPERAND 'O'
#define AND     '&'
#define OR      '|'
#define OPEN    '('
#define CLOSE   ')'
#define NOT     '!'
#define QUOTE   '"'

/* ---------- textsrch prototypes ---------- */
struct postfix *lexical_scan(char *expr);
struct bitmap exinterp(void);
void init_database(void);
struct bitmap search(char *word);
void process_result(struct bitmap);


[LISTING TWO]

/* ------------ exinterp.c --------------- */

/*
 * An expression interpreter that processes the
 * tokens on a postfix stack.
 */

#include "textsrch.h"

static struct postfix *pf = pftokens;

static struct bitmap pop(void);
static struct bitmap not(struct bitmap map1);
static struct bitmap and(struct bitmap map1, struct bitmap map2);
static struct bitmap or(struct bitmap map1, struct bitmap map2);

/* ----- entry to the interpreter
         returns a bitmap which indicates the files
         that match a search expression ------------- */
struct bitmap exinterp(void)
{
    /* ------- find the top of the postfix stack ------- */
    while (pf->pfix != TERM)
        pf++;
    /* ------- get the result of the expression ------- */
    return pop();
}

/* ------ pops an operand and converts it to a bit map ------ */
static struct bitmap pop(void)
{
    struct bitmap map1;
    switch ((--pf)->pfix)   {
        case OPERAND:
            map1 = search(pf->pfixop);
            break;
        case NOT:
            map1 = not(pop());
            break;
        case AND:
            map1 = and(pop(), pop());
            break;
        case OR:
            map1 = or(pop(), pop());
            break;
        default:
            break;
    }
    return map1;
}

/* ------- unary <not> operator ----------- */
static struct bitmap not(struct bitmap map1)
{
    int i;
    for (i = 0; i < MAPSIZE; i++)
        map1.map[i] = ~map1.map[i];
    return map1;
}

/* ------- binary <and> operator -------------- */
static struct bitmap and(struct bitmap map1, struct bitmap map2)
{
    int i;
    for (i = 0; i < MAPSIZE; i++)
        map1.map[i] &= map2.map[i];
    return map1;
}

/* ------- binary <or> operator -------------- */
static struct bitmap or(struct bitmap map1, struct bitmap map2)
{
    int i;
    for (i = 0; i < MAPSIZE; i++)
        map1.map[i] |= map2.map[i];
    return map1;
}


[LISTING THREE]

/* ---------- search.c ----------- */

/*
 * stub functions to simulate the TEXTSRCH retrieval process
 */

#include <stdio.h>
#include <dir.h>
#include <string.h>
#include <process.h>
#include "textsrch.h"

static char names[MAXFILES][13];
static int namect;
static void setbit(struct bitmap *map1, int bit);
static int getbit(struct bitmap *map1, int bit);

/* --------- initialize the data base environment --------- */
void init_database(void)
{
    struct ffblk ff;
    int rtn;
    rtn = findfirst("*.txt", &ff, 0);
    while (rtn != -1 && namect < MAXFILES)  {
        strcpy(names[namect++], ff.ff_name);
        rtn = findnext(&ff);
    }
}

/* ------ search the data base for a match on a word ------ */
struct bitmap search(char *word)
{
    int i;
    FILE *fp;
    char str[80];
    struct bitmap map1;

    for (i = 0; i < MAPSIZE; i++)
        map1.map[i] = 0;
    sprintf(str, "grep -l -i %s *.txt >hits", word);
    system(str);
    if ((fp = fopen("hits", "rt")) != NULL) {
        while (fgets(str, 80, fp) != NULL)  {
            *strchr(str, ':') = '\0';
            for (i = 0; i < MAXFILES; i ++) {
                if (stricmp(str+5, names[i]) == 0)  {
                    setbit(&map1, i);
                    break;
                }
            }
        }
        fclose(fp);
    }
    return map1;
}

/* ---- process the result of a query expression search ---- */
void process_result(struct bitmap map1)
{
    int i;
    for (i = 0; i < MAXFILES; i++)
        if (getbit(&map1, i))
            printf("\n%s", names[i]);
}

/* ------ sets a designated bit in the bit map ------ */
static void setbit(struct bitmap *map1, int bit)
{
    int off = bit / 16;
    int mask = 1 << (bit % 16);
    map1->map[off] |= mask;
}

/* ------ tests a designated bit in the bit map ------ */
static int getbit(struct bitmap *map1, int bit)
{
    int off = bit / 16;
    int mask = 1 << (bit % 16);
    return map1->map[off] & mask;
}


[LISTING FOUR]


/* ----------- textsrch.c ------------- */

/*
 * The TEXTSRCH program.
 */

#include <stdio.h>
#include <process.h>
#include <string.h>
#include "textsrch.h"

void main(void)
{
    char expr[80];
    /* -------- initialize the text data base --------- */
    init_database();
    do  {
        /* ----- read the expression from the console ------ */
        printf("\nEnter the search expression:\n");
        gets(expr);
        if (*expr)  {
            /* --- scan for errors and convert to postfix --- */
            if (lexical_scan(expr) == NULL) {
                /* ---- the expression is invalid ---- */
                while(xp_offset--)
                    putchar(' ');
                putchar('^');
                printf("\nSyntax Error");
                exit(1);
            }
            /* --- interpret the expression, search the data base,
                and process the hits ------- */
            process_result(exinterp());
        }
    } while (*expr);
}