#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);
}