// auto generated (Mon Feb 28 11:37:56 EST 2005)
/************** main.c **************/
#include <stdio.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <ctype.h>
#include "db.h"

int load(char *szFilename) {
    char            *prgText;
    struct stat     stStat;
    FILE            *pFile;
    size_t          nSize;
    int             i;
    char            *pLeft;

	DB_Create();
    pFile = fopen(szFilename,"r");
    if (NULL==pFile)
        return 0;

    if (stat(szFilename,&stStat)) {
        printf("stat failure\n");
        return 0;
    }

    nSize = stStat.st_size;
    prgText= (char*)malloc(nSize);

    i = fread(prgText,1,nSize,pFile);
    if (i&&ferror(pFile)) {
        free(prgText);
        return 0;
    }

    pLeft = prgText;
    for (i=0;i<nSize;i++) {
        switch (prgText[i]) {
            case  ' ':
            case  ',':
            case  ':':
            case  '.':
            case '\n':
            case '\r':
            case  ';':
            case  '?':
            case '\'':
            case  '!':
            case  '(':
            case  ')':
            case  '"':
            case '\v':
            case '\t':
                prgText[i]='\0';
                if (*pLeft != '\0')
                    DB_Add(pLeft);
                pLeft = prgText+i+1;
                break;
#ifdef NOCASE
            default:
                prgText[i]=tolower(prgText[i]);
#endif
        }
    }

    DB_DisplayResult();
    DB_Destroy();
    free(prgText);

    return 1;
}

int main(int argc,char **argv) {
    if (argc < 2) {
        fprintf(stderr,"tell me the file\n");
        return 1;
    }
    load(argv[1]);
    return 0;
}
/************** db.h **************/
#ifndef _DB_H_
#define _DB_H_

#ifndef TOP_N
#define TOP_N   25
#endif

typedef struct __entry {
    char    *word;
    int     count;
} Entry;

void    DB_Create(void);
void    DB_Add(char *word);
void    DB_Destroy(void);
void    DB_DisplayResult(void);

#endif
/************** tree.c **************/
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "db.h"

typedef struct _treeentry {
    char				*word;
    int					count;
    char				c;  //0=black, 1=red
    struct _treeentry	*wr;
    struct _treeentry	*wl;
    struct _treeentry   *cr;
    struct _treeentry   *cl;
} TreeEntry;


void        WTree_Add(TreeEntry*,char*);
void        WTree_Destroy(TreeEntry*);
TreeEntry*  WTree_Find(TreeEntry*,char*);
void        WTree_Examine(TreeEntry*);
TreeEntry*  Tree_NewEntry(char* word);
void        CTree_Add(TreeEntry*);

#define ISNULL(v)       (!v)
#define ISNOTNULL(v)    (v)

static TreeEntry    *WTree_Root=NULL;
static TreeEntry    *CTree_Root=NULL;
static int          CTree_Count=0;

void _CTree_Add(TreeEntry*,TreeEntry*);
void _CTree_Build(TreeEntry*);
void _CTree_Display(TreeEntry*);

void DB_Create(void) {
}

void DB_Add(char *word) {
	if (!WTree_Root) {
        WTree_Root = Tree_NewEntry(word);
        return;
    }

    WTree_Add(WTree_Root,word);
}

TreeEntry* Tree_NewEntry(char* word) {
    TreeEntry* pEntry = (TreeEntry*)malloc(sizeof(TreeEntry));
    pEntry->word=word;
    pEntry->wl=NULL;
    pEntry->wr=NULL;
    pEntry->cl=NULL;
    pEntry->cr=NULL;
    pEntry->count=1;
    return pEntry;
}

void DB_Destroy(void) {
    if (!WTree_Root)
        return;
    WTree_Destroy(WTree_Root);
}

void WTree_Destroy(TreeEntry *root) {
    if (root->wr!=NULL)
        WTree_Destroy(root->wr);
    if (root->wl!=NULL)
        WTree_Destroy(root->wl);
    free(root);
}

TreeEntry* WTree_Find(TreeEntry *root,char* word) {
    if (!root)
        return NULL;
    int d = strcmp(word,root->word);
    if (d<0)
        return WTree_Find(root->wl,word);
    return WTree_Find(root->wr,word);
        
}

void CTree_Add(TreeEntry *newb) {
    if (ISNULL(CTree_Root)) {
        CTree_Root=newb;
        return;
    }

    _CTree_Add(CTree_Root,newb);
}

void _CTree_Add(TreeEntry *root,TreeEntry *node) {
    if (node->count < root->count) {
        if (ISNULL(root->cl)) {
            root->cl=node;
            return;
        }
        _CTree_Add(root->cl,node);
        return;
    }

    if (ISNULL(root->cr)) {
        root->cr=node;
        return;
    }

    _CTree_Add(root->cr,node);
}

void WTree_Add(TreeEntry *root,char* word) {
    int d = strcmp(word,root->word);
    if (d<0) {
        if (root->wl==NULL) {
            root->wl = Tree_NewEntry(word);
            return;
        }
        WTree_Add(root->wl,word);
        return;
    }

	if (d>0) {
		if (root->wr==NULL) {
			root->wr = Tree_NewEntry(word);
			return;
		}
		WTree_Add(root->wr,word);
		return;
	}

	root->count++;
}

void DB_DisplayResult(void) {
    _CTree_Build(WTree_Root);
    CTree_Count = 25;
    _CTree_Display(CTree_Root);
}

void _CTree_Display(TreeEntry* root) {
    if (ISNULL(root))
        return;
    _CTree_Display(root->cr);
    if (!CTree_Count)
        return;
    printf("%s    (%d)\n",root->word,root->count);
    if (--CTree_Count)
        _CTree_Display(root->cl);
}

void _CTree_Build(TreeEntry* root) {
    if (ISNULL(root))
        return;
    _CTree_Build(root->wl);
    CTree_Add(root);
    _CTree_Build(root->wr);
}
/************** hash.c **************/
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "db.h"

#define HASH        Hash_SDBM
#define HASHMASK    0xffff

typedef struct _hashentry {
    char                *word;
    int                 count;
    struct _hashentry   *next;
} Hash_Entry;



#define BLOCKSIZE		14000
#define MEMBLOCKS		10

#define	ISNULL(v)		(!v)
#define ISNOTNULL(v)	(v)

Hash_Entry*		Hash_Root[HASHMASK];
Hash_Entry*		Heap_Root[TOP_N];
unsigned int	Heap_Tail=0;
unsigned int	Heap_Minm=0;

#ifdef AVOIDMALLOC
Hash_Entry      Hash_Mem[BLOCKSIZE];
unsigned int	Hash_MemSize=0;
#endif

void			Hash_Destroy(Hash_Entry*);
unsigned int	Hash_SDBM(char*);
Hash_Entry*		Hash_NewEntry(char*);
void			Heap_Update(Hash_Entry*);
void			Heap_FixUp(int);
void			Heap_FixDn(int);

Hash_Entry* Hash_NewEntry(char* word) {
	Hash_Entry*		pEntry;

#ifdef AVOIDMALLOC
    pEntry = &(Hash_Mem[Hash_MemSize++]);
    if (Hash_MemSize==BLOCKSIZE) {
        fprintf(stderr,"OUT OF MEMORY BLOCKS\n");
        exit(1);
    }
#else
	pEntry = (Hash_Entry*)malloc(sizeof(Hash_Entry));
#endif
	pEntry->word = word;
	pEntry->count = 1;
	pEntry->next = NULL;
	return pEntry;
}

void DB_Add(char* word) {
	Hash_Entry*		p;
	unsigned int	h;

	h = HASH(word);
	if (ISNULL(Hash_Root[h])) {
		Hash_Root[h]=Hash_NewEntry(word);
		return;
	}

	p=Hash_Root[h];
	do {
		if (!strcmp(p->word,word)) {
			p->count++;
			return;
		}
		if (ISNULL(p->next)) {
			p->next = Hash_NewEntry(word);
			return;
		}
		p= p->next;
	} while (1);

}

void Heap_FixUp(int i) {
	int p;
	Hash_Entry* t;

	if (!i)
		return;

	p=(2>>1); //parent;

	if (Heap_Root[p]->count>Heap_Root[i]->count) {
		t=Heap_Root[p];
		Heap_Root[p]=Heap_Root[i];
		Heap_Root[i]=t;
		Heap_FixUp(p);
	}
}

void Heap_FixDn(int i) {
	int l,r,m;
	Hash_Entry*	t;

	l = (i<<1)+1;
	r = l+1;

	if (l>=Heap_Tail)
		return;

	if (r<Heap_Tail)
		m=(Heap_Root[l]->count<Heap_Root[r]->count)?l:r;
	else
		m=l;

	if (Heap_Root[i]->count<Heap_Root[m]->count)
		return;

	t = Heap_Root[m];
	Heap_Root[m]=Heap_Root[i];
	Heap_Root[i]=t;
	Heap_FixDn(m);
}

void Heap_Update(Hash_Entry* e) {
	if ((e->count<=Heap_Minm) && (Heap_Tail==TOP_N))
		return;

    if (Heap_Tail<TOP_N) {
        Heap_Root[Heap_Tail]=e;
        Heap_FixUp(Heap_Tail++);
    }
    else {
        Heap_Root[0]=e;
        Heap_FixDn(0);
    }

	Heap_Minm=Heap_Root[0]->count;
}

void DB_Create(void) {
	memset(Hash_Root,NULL,HASHMASK);
}

void DB_Destroy(void) {
#ifndef AVOIDMALLOC
	int i;
	for (i=0;i<HASHMASK;i++)
		if ISNOTNULL(Hash_Root[i])
			Hash_Destroy(Hash_Root[i]);
#endif
}

void Hash_Destroy(Hash_Entry* p) {
	if (ISNOTNULL(p->next))
		Hash_Destroy(p->next);
	free(p);
		
}

void DB_DisplayResult(void) {
	int i;
    Hash_Entry *e;
    for (i=0;i<HASHMASK;i++) {
        e = Hash_Root[i];
        while (ISNOTNULL(e)) {
            Heap_Update(e);
            e=e->next;
        }
    }

	for (i=0;i<Heap_Tail;i++)
		printf("%s (%d)\n",Heap_Root[i]->word,Heap_Root[i]->count);
}

/**	HASHING METHODS	 **/
unsigned int Hash_SDBM(char* key) {
	unsigned int hash = 0;
	while (*key)
		hash = (*key++)+(hash<<6)+(hash<<16)-hash;
	return (hash & HASHMASK);
}

/************** Makefile **************/
#G5FLAGS=-mcpu=970 -mtune=970 -mpowerpc64 -mpowerpc-gpopt -falign-loops=16 -falign-functions=16 -falign-labels=16 -falign-jumps=16 -ffast-math -funroll-loops -finline -mno-update -mno-multiple -fstrict-aliasing -fsched-interblock
FLAGS=-Wall -O3 $(G5FLAGS) -DAVOIDMALLOC -DNOCASE

default:with-tree with-hash

with-tree:main.o tree.o
	gcc $(FLAGS) -o  with-tree main.o tree.o

with-hash:main.o hash.o
	gcc $(FLAGS) -o with-hash main.o hash.o

main.o:main.c db.h
	gcc $(FLAGS) -c main.c

hash.o:hash.c db.h
	gcc $(FLAGS) $(HASHFLAGS) -c hash.c

tree.o:tree.c db.h
	gcc $(FLAGS) -c tree.c

clean:
	rm -f with-tree
	rm -f with-hash
	rm -f *.o