/*
 * Copyright (C) 2000, Matias Atria
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include "mdvi.h"

/* simple hash tables for MDVI */


struct _DviHashBucket {
	DviHashBucket *next;
	DviHashKey	key;
	Ulong	hvalue;
	void	*data;
};

static Ulong hash_string(DviHashKey key)
{
	Uchar	*p;
	Ulong	h, g;
	
	for(h = 0, p = (Uchar *)key; *p; p++) {
		h = (h << 4UL) + *p;
		if((g = h & 0xf0000000L) != 0) {
			h ^= (g >> 24UL);
			h ^= g;
		}
	}
		
	return h;
}

static int hash_compare(DviHashKey k1, DviHashKey k2)
{
	return strcmp((char *)k1, (char *)k2);
}

void	mdvi_hash_init(DviHashTable *hash)
{
	hash->buckets = NULL;
	hash->nbucks  = 0;
	hash->nkeys   = 0;
	hash->hash_func = NULL;
	hash->hash_comp = NULL;
	hash->hash_free = NULL;
}

void	mdvi_hash_create(DviHashTable *hash, int size)
{
	int	i;
	
	hash->nbucks = size;
	hash->buckets = xnalloc(DviHashBucket *, size);
	for(i = 0; i < size; i++)
		hash->buckets[i] = NULL;
	hash->hash_func = hash_string;
	hash->hash_comp = hash_compare;
	hash->hash_free = NULL;
	hash->nkeys = 0;
}

static DviHashBucket *hash_find(DviHashTable *hash, DviHashKey key)
{
	Ulong	hval;
	DviHashBucket *buck;
	
	hval = (hash->hash_func(key) % hash->nbucks);
	
	for(buck = hash->buckets[hval]; buck; buck = buck->next)
		if(hash->hash_comp(buck->key, key) == 0)
			break;
	return buck;
}

/* Neither keys nor data are duplicated */
int	mdvi_hash_add(DviHashTable *hash, DviHashKey key, void *data, int rep)
{
	DviHashBucket *buck = NULL;
	Ulong	hval;
	
	if(rep != MDVI_HASH_UNCHECKED) {
		buck = hash_find(hash, key);
		if(buck != NULL) {
			if(buck->data == data)
				return 0;
			if(rep == MDVI_HASH_UNIQUE)
				return -1;
			if(hash->hash_free != NULL)
				hash->hash_free(buck->key, buck->data);
		}
	}
	if(buck == NULL) {
		buck = xalloc(DviHashBucket);
		buck->hvalue = hash->hash_func(key);
		hval = (buck->hvalue % hash->nbucks);
		buck->next = hash->buckets[hval];
		hash->buckets[hval] = buck;
		hash->nkeys++;
	}
	
	/* save key and data */
	buck->key = key;
	buck->data = data;
	
	return 0;
}

void	*mdvi_hash_lookup(DviHashTable *hash, DviHashKey key)
{
	DviHashBucket *buck = hash_find(hash, key);

	return buck ? buck->data : NULL;
}

static DviHashBucket *hash_remove(DviHashTable *hash, DviHashKey key)
{
	DviHashBucket *buck, *last;
	Ulong	hval;
	
	hval = hash->hash_func(key);
	hval %= hash->nbucks;
	
	for(last = NULL, buck = hash->buckets[hval]; buck; buck = buck->next) {
		if(hash->hash_comp(buck->key, key) == 0)
			break;
		last = buck;
	}
	if(buck == NULL)
		return NULL;
	if(last)
		last->next = buck->next;
	else
		hash->buckets[hval] = buck->next;
	hash->nkeys--;
	return buck;
}

void	*mdvi_hash_remove(DviHashTable *hash, DviHashKey key)
{
	DviHashBucket *buck = hash_remove(hash, key);
	void	*data = NULL;

	if(buck) {
		data = buck->data;
		xfree(buck);
	}
	return data;
}

void	*mdvi_hash_remove_ptr(DviHashTable *hash, DviHashKey key)
{
	DviHashBucket *buck, *last;
	Ulong	hval;
	void	*ptr;
	
	hval = hash->hash_func(key);
	hval %= hash->nbucks;
	
	for(last = NULL, buck = hash->buckets[hval]; buck; buck = buck->next) {
		if(buck->key == key)
			break;
		last = buck;
	}
	if(buck == NULL)
		return NULL;
	if(last)
		last->next = buck->next;
	else
		hash->buckets[hval] = buck->next;
	hash->nkeys--;
	/* destroy the bucket */
	ptr = buck->data;
	xfree(buck);
	return ptr;
}

int	mdvi_hash_destroy_key(DviHashTable *hash, DviHashKey key)
{
	DviHashBucket *buck = hash_remove(hash, key);
	
	if(buck == NULL)
		return -1;
	if(hash->hash_free)
		hash->hash_free(buck->key, buck->data);
	xfree(buck);
	return 0;	
}

void	mdvi_hash_reset(DviHashTable *hash, int reuse)
{
	int	i;
	DviHashBucket *buck;
	
	/* remove all keys in the hash table */
	for(i = 0; i < hash->nbucks; i++) {
		for(; (buck = hash->buckets[i]); ) {
			hash->buckets[i] = buck->next;
			if(hash->hash_free)
				hash->hash_free(buck->key, buck->data);
			xfree(buck);
		}
	}
	hash->nkeys = 0;
	if(!reuse && hash->buckets) {
		xfree(hash->buckets);
		hash->buckets = NULL;
		hash->nbucks = 0;
	} /* otherwise, it is left empty, ready to be reused */
}