Source code ch.01 code example: mkndx & find in C

Source Code & Software Patents: A Guide to Software & Internet Patent Litigation for Attorneys & Experts
by Andrew Schulman (http://www.SoftwareLitigationConsulting.com)

Code example for Chapter 1: What’s so special (or not so special) about source code?

Code example: mkndx & find in C

mkndx creates an index of lines of source code; find searches in indices created by mkndx

[TODO: show how to use, what output looks like, what index files look like]

[TODO: use strhash.c below to explain data structures, e.g. linked list, table, etc.; note that VBS and awk code merely assume the presence of associated arrays; strhash.c implements them, and strhash.h provides an interface]

[TODO: link to executable files for Windows, Mac OSX; show portion of disassembly; show portion of hexdump]

========

// ndx.c

// TODO:
// change strhash so val is (void *) to be determined by user
// error if can't open file?
// output current count to stderr
// show ls equiv to "dir /s/b /a-d"

#include <stdlib.h>
#include <stdio.h>
#include "strhash.h"

void fail(char *s) { puts(s); exit(1); }

void *alloc(int size)
{
        void *p = calloc(size, 1); // 0-init
        if (! p) fail("insufficient memory");
        return p;
}

HASHTAB files = (HASHTAB) 0;

int get_files(char *s)
{
        static int cnt = 0; // only init once!
        int this_cnt = 0; // init each time
        char *cmd, *buf;
        FILE *f;
        
        if (! files) // one-time init
                if (! (files = MakeHashTab()))
                        fail("Can't create files list");

        if (*s == '@')
        {
            f = fopen(s+1, "r");
            if (! f) fail("can't open @file"); 
        }
        else
        {
            cmd = alloc(1024);
            cmd[0] = '\0';
            strcpy(cmd, "dir /s/b /a-d ");
            strcat(cmd, s);
            strcat(cmd, " > __tmp.tmp"); // TODO: make temp file

            //fprintf(stderr, "get_files: %s\n", cmd);
            system(cmd);
            free(cmd);

            f = fopen("__tmp.tmp", "r");
            if (! f) fail("can't open __tmp.tmp");
        }

       buf = alloc(2048);
       while (fgets(buf, 2047, f))
       {
        if ((! *buf) || (*buf == '#')) // comments in @file
            continue;
        buf[strlen(buf)-1] = '\0'; // remove \n
        cnt++;
        this_cnt++;
        //fprintf(stderr, "get_files: <%s> [%u]\n", buf, cnt);
        SetHashTab(files, buf, cnt); // cnt = fnum
       }
       fclose(f);
       free(buf);

       return this_cnt;
}

int print_func(char *s, int count, int val, unsigned *p)
{
       if (count == 1)
        printf("%u\t%s\t[%u,]\n", count, s, val);
       else
       {
        int i, top;
        printf("%u\t%s\t[", count, s);
        top = min(50, count);
        for (i=0; i<top; i++)
        {
           printf("%u,", p[i]);
        }
        printf("]\n");
       }
       return 1;
}

HASHTAB strings = (HASHTAB) 0;

static int gcnt = 0;

int do_file(char *fname, int count, int fnum, unsigned *p)
{
    static int fcnt = 0;
    int cnt = 0;
    FILE *f;
    char *buf;

    fcnt++;
    fprintf(stderr, "%u (%u%%)\t%s\t%u\n", fcnt, 
       (100*fcnt) / (1+gcnt), fname, fnum);
    printf("%u\t%s\n", fnum, fname);
    f = fopen(fname, "r");
    // if (! f) fail("can't open file"); // no, keep going
    if (! f) { fprintf(stderr, "\nCan't open <%s>\n\n", fname); return 0; }
    buf = alloc(10240);

    // TODO: need to create temp hashtab, so can do 1 entry per file
    // TODO: maybe change MakeHashTab to take param with tab_size, store

    while (fgets(buf, 10239, f))
    {
        char *s = buf;
        buf[strlen(buf)-1] = '\0'; // remove \n
        while (*s == ' ' || *s == '\t') s++; // remove leading spaces
        if (*s)
        {
            cnt++;
            SetHashTab(strings, s, fnum); // will keep count
        }
    }
    fclose(f);
    free(buf);
    return 1;
}

main(int argc, char *argv[])
{
    unsigned i;

    if (argc < 2)
        fail("usage: ndx [file*.ext or @file]");

    for (i=1; i<argc; i++)
        gcnt += get_files(argv[i]);

    printf("%u files\n", gcnt);

    // ForXInHashtab(files, print_func);

    puts("Files\n");

    strings = MakeHashTab();

    ForXInHashtab(files, do_file);

    fputs("Generating output...\n", stderr);
    puts("\nStrings\n");

    ForXInHashtab(strings, print_func);

    FreeHashTab(files);
    FreeHashTab(strings);
}

==========

strhash.h:

// strhash.h
typedef void *HASHTAB ;

HASHTAB MakeHashTab(void);
void FreeHashTab(HASHTAB hashtab);
void SetHashTab(HASHTAB hashtab, char *s, unsigned val);
int GetHashTab(HASHTAB hashtab, char *s);

typedef int (*FORIN_FUNC)(char *s, int count, unsigned val, unsigned *p);
void ForXInHashtab(HASHTAB hashtab, FORIN_FUNC func);

==========

// strhash.c
// TODO: replace val with count and union of val and void*
// use val when count == 1; in one test (Firefox source), 80% of
// entries appeared only 1x

#include <stdlib.h>
#include <stdio.h>
#include "strhash.h"

typedef struct _node {
    struct _node *next;
    char *s;
    unsigned val;
    } NODE;

void _fail(const char *s) { puts(s); exit(1); }

void *my_alloc(int x, int y)
{
    void *p = calloc(x,y); // zero init
    if (! p)
        _fail("Error: insufficient memory");
    return p;
}

void insert(NODE **list, char *s, unsigned val)
{
    NODE *node;
    NODE *l2 = *list;
    while (l2)
    {
        if (strcmp(l2->s, s) == 0) // could do case-insensitive
        {
                l2->val = val; // took 1 hr. to find bug where omitted this
                return; // already in list
        }
        else
            l2 = l2->next;
    }

    node = (NODE *) my_alloc(1, sizeof(NODE));
    node->next = *list;
    *list = node;
    node->s = my_alloc(1, strlen(s)+1);
    strcpy(node->s, s);
    node->val = val;
}

int find(NODE *list, char *s)
{
    while (list)
    {
       if (*s == *(list->s))
       {
        static int num_strcmp = 0;
        num_strcmp++;
        if ((num_strcmp % 1000000) == 0)
            fprintf(stderr, "\n\n!! %u calls to strcmp\n\n\n", num_strcmp);
        if (strcmp(list->s, s) == 0)
            return list->val;
        else
            list = list->next;
       }
       else
          list = list->next;
    }
    return 0; // valid val begins with 1
}

// prime numbers: 9973 11113 13997 16943 18917
// TODO: do TAB_SIZE and hash make sense together? 
#define TAB_SIZE 11113

// see http://www.cs.yorku.ca/~oz/hash.html
unsigned long HASH(unsigned char *s)
{
    unsigned long hash = 5381;
    int c;
    while (c = *s++) {
            hash = ((hash << 5) + hash) + c;
    }       
    return (hash % TAB_SIZE);
}

NODE **mk_hashtab(void) {
    return (NODE **) my_alloc(TAB_SIZE, sizeof(NODE *));
}

HASHTAB MakeHashTab(void) {
    return (HASHTAB) mk_hashtab();
}

void FreeHashTab(HASHTAB hashtab) {
    free(hashtab);
}

void set(NODE **hashtab, char *s, unsigned val) {
    insert(&hashtab[HASH(s)], s, val);
}

void SetHashTab(HASHTAB hashtab, char *s, unsigned val) {
    set((NODE**) hashtab, s, val);
}

int get(NODE **hashtab, char *s) {
    return find(hashtab[HASH(s)], s);
}

int GetHashTab(HASHTAB hashtab, char *s) {
    return get((NODE**)hashtab, s);
}

typedef int (*FORIN_FUNC)(char *s, unsigned val);

void for_in(NODE **hashtab, FORIN_FUNC func)
{
    NODE *list;
    int i;
   for (i=0; i<TAB_SIZE; i++)
   {
    if (list = hashtab[i])
    {
        while (list)
        {
        if (! (*func)(list->s, list->count, list->val, list->p))
            return; // done if func returns 0
        list = list->next;
        }
    }
   }
}

void ForXInHashtab(HASHTAB hashtab, FORIN_FUNC func)
{
    for_in((NODE**) hashtab, func);
}

#ifdef TESTING
int print_func(char *s, unsigned val)
{
    printf("%u\t%s\n", val, s);
    return 1;
}

main(int argc, char *argv[])
{
    NODE **hashtab;
    char buf[10240];
    int i, cnt=0;
    
    hashtab = mk_hashtab();

    while (gets(buf)) // only get up to buf size
    {
        char *s = buf;
        while (*s == ' ' || *s == '\t') s++; // remove leading spaces
        if (*s)
            set(hashtab, s, ++cnt);
    }

    for_in(hashtab, print_func);
}
#endif

=======

find.c:

// find.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "strhash.h"

void fail(char *s) { puts(s); exit(1); }

int case_sensitive = 0;

char *strlower(char *s) // not in place; make copy
{
        char *s2 = malloc(strlen(s)+1);
        char *p;
        if (! s2) fail("insufficient memory");
        s2[0] = '\0';
        strcpy(s2, s); // unsafe
        for (p=s2; *p; p++) {
                if ((*p >= 'A') && (*p <= 'Z'))
                        *p = *p += 0x20; // 'a' - 'A'
        }
        return s2; // caller responsibility to free
}

char *match(char *str1, char *str2)
{
    if (case_sensitive)
        return strstr(str1, str2);
    else
    {
        static char *s2 = (char *) 0;
        char *s1 = strlower(str1);
        char *ret;
        if (! s2) // one time, not going to change
            s2 = strlower(str2);
        ret = strstr(s1, s2);
        free(s1);
        // free(s2);
        return ret;
    }
}

main(int argc, char *argv[])
{
    HASHTAB hashtab;
    FILE *f;
    char *pat, *ndxfile, *buf, *s;
    typedef char *STRING;
    STRING arr[3];
    int i, cnt;
    int in_files = 0, in_strings = 0;

    if (argc < 3)
        fail("usage: find [pat] [ndxfile]");

    pat = argv[1];
    printf("pat: <%s>\n", pat);
    ndxfile = argv[2];

    if (! (f = fopen(ndxfile, "r"))) fail("can't open ndxfile");
    if (! (hashtab = MakeHashTab())) fail("can't allocate hashtab");
    if (! (buf = calloc(10240, 1)))  fail("insufficient memory");

    while (fgets(buf, 10239, f))
    {
        s = buf;
        if ((! *s) || (*s == '#') || (*s == '\n')) // comments or blank lines
            continue;
        s[strlen(s)-1] = '\0'; // remove \n
        while (*s == ' ' || *s == '\t') s++; // remove leading spaces
        if (! *s)
            continue;

        if (arr[0] = strtok(s, "\t")) cnt = 1;
        if (arr[1] = strtok(NULL, "\t")) cnt = 2;
        if (arr[2] = strtok(NULL, "\t")) cnt = 3;

       if (cnt == 1)
       {
        if (strcmp(arr[0], "Files") == 0) // doh, remember match ret 0
        {
            in_files = 1;
        }
        else if (strcmp(arr[0], "Strings") == 0)
        {
            in_files = 0;
            in_strings = 1;
            fputs("Done with files\n", stderr);
        }
       }

       if (in_files && (cnt == 2)) // TODO: error msg if cnt != 2
       {
        // TODO: need ability to do val -> str,
        // following is hack
        // could also use first line with "%u files" to alloc array
        char *s = malloc(strlen(arr[1])+1);
        if (! s) fail("insufficient memory");
        s[0] = '\0';
        strcpy(s, arr[1]);
        SetHashTab(hashtab, arr[0], (unsigned) s); // not atoi
        //SetHashTab(hashtab, arr[1], atoi(arr[0])); //TODO: need ability to do val->str
       }

       if (in_strings && (cnt == 3) && match(arr[1], pat)) //TODO: err msg if cnt!=3
       {
        int fcount = atoi(arr[0]);
        char *str = arr[1];
        char *fnums = arr[2];
        int len = strlen(fnums);
        int fnum;

        if (*fnums == '[') fnums++;
        if (fnums[len-2] == ']') fnums[len-2] = '\0' ;
        if ((fcount == 1) && (fnums[len-3] == ','))
        {
            fnums[len-3] = '\0';
            printf("%s\n\t%s\n", str, GetHashTab(hashtab, fnums));

        }
        else if (fcount > 1)
        {
            char *fnumstr;
            printf("%s\n", str);
            if (fcount >= 50)
                printf("COMMON STRING: in %u files, including:\n", fcount);
            fnumstr = strtok(fnums, ",");
            do {
                printf("\t%s\n", GetHashTab(hashtab, fnumstr));
            } while (fnumstr = strtok(NULL, ","));
        }
       }
    }

    fclose(f);
    free(buf);
}