/*
** Character Hash Functions
**
** Copyright (C) 1996-2005 Herbert Poetzl
*/


#include <string.h>
#include <stdlib.h>

#include "chash.h"
#include "helper.h"
#include "conf.h"

#ifndef TRUE
#define	TRUE 	(0==0)
#endif
#ifndef FALSE
#define	FALSE	(1==0)
#endif

#define	DELETED	((char *)-1)

#ifdef	IGNORE_CASE
#define CHFOLD(c)   toupper(c)
#define STRCMP(a,b) strcasecmp((a),(b))
#else
#define CHFOLD(c)   (c) 
#define STRCMP(a,b) strcmp((a),(b))
#endif

#define _copy_string	scopy
#define _key_free   	sfree


long	_hashcode_ascii(const char *key)
{  
	long h, c;
	h = 0;
	while ((c = CHFOLD(*key++))) {
	    h += c + (c<<5) + (h<<3);
	}
	return h;
}


struct 	hash_entry *_hash_find(hash table, const char *key)
{
	long pos, hashcode;
	struct hash_entry *place, *start;
	hashcode = _hashcode_ascii(key);
	pos = (table->mask & hashcode);
	place = &(table->data[pos]);
	start = place;
	while (place->key != NULL) {
	    if (hashcode == place->hashcode) {
		if (place->key != DELETED) {
		    if (STRCMP(key, place->key) == 0) {
			return place;
		    }
		}
	    }
	    place++;
	    if (place == table->wall) place = table->data;
	    if (place == start) break;
	}
	return NULL;
}


int	_hash_place(hash table, struct hash_entry *entry, int check)
{
	long pos;
	struct hash_entry *place;
	pos = (table->mask & entry->hashcode);
	place = &(table->data[pos]);
	while (place->key != NULL) {
	    if (place->key == DELETED) break;
	    if (check) {
	    	if (entry->hashcode == place->hashcode) {
		    if (STRCMP(entry->key, place->key) == 0) {
			place->value = entry->value;
			return (TRUE);
		    }
		}
	    }
	    place++;
	    if (place == table->wall) place = table->data;
	}
	table->entries++;
	memcpy(place, entry, sizeof(struct hash_entry));
	return (FALSE);
}

int	_hash_grow(hash table)
{
	struct hash_control *new;
	new = hash_new(2<<table->sizelog);
	if (new) {
	    long i,n;
	    for (i=0, n=1<<table->sizelog; i<n; i++) {
		if (table->data[i].key != NULL)
		    _hash_place(new, &(table->data[i]), FALSE); 
	    }
	    free(table->data);
	    memcpy(table, new, sizeof(struct hash_control));
	    free(new);			
	    return (TRUE);
	}
	return (FALSE);
}

int	_hash_cramped(hash table)
{
	long bound;
	bound = 101*(1 << table->sizelog)/143;
	if (table->entries > bound) return (TRUE);	
	return (FALSE);
}



hash	hash_new(long capacity)
{
	struct hash_control *new;
	long n,s;
	new = (struct hash_control *)
	    malloc(sizeof(struct hash_control));
	if (new) {
	    for (n=0,s=1; s<capacity; n++,s <<= 1);
	    new->sizelog = n;
	    new->mask = s-1;
	    new->memsize = sizeof(struct hash_entry)*s;
	    new->data = (struct hash_entry *)
		calloc(new->memsize, 1);
	    if (new->data) {
	    	new->wall = new->data+s;
		new->entries = 0;
	    }
	    else {
	    	free(new);
		new = NULL;
	    }
	}	
	return (hash)new;
}

void	hash_free(hash table)
{
	if (table) {
	    free(table->data);
	    free(table);
	}
	return;
}

void	hash_free_keys(hash table)
{
    	if (table) {
	    long pos, max = (1 << table->sizelog);
	    char *lkey;
	
	    for (pos = 0; pos < max; pos++) {
 	    	lkey = table->data[pos].key;
	    	if ((lkey) && (lkey != DELETED)) {
	    	    _key_free(lkey);
	    	    table->data[pos].key = 0;
	    	}
	    }
	    table->entries = 0;
	}
}

void	hash_empty(hash table)
{
	table->entries = 0;
	memset(table->data, 0, table->memsize);
	return;
}


int	hash_inject(hash table, const char *key, void *value)
{
	if (table && key) {
	    struct hash_entry place;
	    if (_hash_cramped(table)) {
		_hash_grow(table);
	    }
	    place.key = (char *)key;
	    place.value = value;
	    place.hashcode = _hashcode_ascii(key);
	    _hash_place(table, &place, (FALSE));
	    return (TRUE);
	}
	return (FALSE);
}

int	hash_insert(hash table, const char *key, void *value, char copy)
{
	if (table && key) {
	    struct hash_entry place;
	    char replaced;
	    if (_hash_cramped(table)) {
		_hash_grow(table);
	    }
	    if (copy) place.key = _copy_string(key);
	    else place.key = (char *)key;
	    place.value = value;
	    place.hashcode = _hashcode_ascii(key);
	    replaced = _hash_place(table, &place, (TRUE));
	    if (copy && replaced) _key_free(place.key);
	    return (TRUE);
	}
	return (FALSE);
}


void *	hash_replace(hash table, const char *key, void *value)
{
	void *oldvalue;
	struct hash_entry *entry;
	if (key) {
	    entry = _hash_find(table, key);
	    if (entry) {
	    	oldvalue = entry->value;
		entry->value = value;
		return oldvalue;
	    }
	}
	return NULL;	
}

void *	hash_delete(hash table, const char *key, const char **oldkey)
{
	void *oldvalue = NULL;
	struct hash_entry *entry;
	if (key) {
	    entry = _hash_find(table, key);
	    if (entry) {
		oldvalue = entry->value;
		if (oldkey) *oldkey = entry->key;
		entry->key = DELETED;
		table->entries--;
	    }
	}
	return oldvalue;
}


void *	hash_lookup(hash table, const char *key)
{
	struct hash_entry *entry;
	if (key) {
	    entry = _hash_find(table, key);
	    if (entry) {
		return entry->value;
	    }
	}
	return NULL;
}


hstate	hash_state(hash table)
{
	hstate state;
	state.hashpos = 0;
	state.table = table;
	state.sflags.active = TRUE;
	return state;
}

void *	hash_next(hstate *state, char **key)
{
	long pos;
	char *lkey;
	void *value = NULL;
	if (state) {
	    hash table = state->table;
	    if (state->sflags.active) { 
		while ((pos = state->hashpos++) 
		    < (1 << table->sizelog)) {
		    lkey = table->data[pos].key;
		    if ((lkey != DELETED) && (lkey)) {
			value = table->data[pos].value;
			if (key) *key = lkey;
			break;
		    } 
		}
		if (pos == (1 << table->sizelog)) 
		    state->sflags.active = FALSE; 
	    }
	}
	return value;
}

int	hash_count(hash table)
{
	if (table) return table->entries;
	return 0;
}