/* Hash map ADT V1.00 25/11/05
   See hash.h for docs
   Copyright 2008 Jeffrey Lee
   This file is part of WOUM.
   WOUM 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 3 of the License, or
   (at your option) any later version.
   WOUM 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 WOUM.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef _HMAP_C
#define _HMAP_C

#include <stdlib.h>

#include "hmap.h"

typedef struct _pair {
	void *key;
	void *value;
	struct _pair *next;
} pair;

typedef struct {
	int (*cmp)(const void *a,const void *b);
	int (*hash)(const void *a);
	int tsize; /* Table size */
	int size; /* Number of entries in structure */
	pair **table;
	int killkeys;
} _hmap;

hmap hmap_create(int (*cmp)(const void *a,const void *b),int (*hash)(const void *a),int size,int killkeys)
{
	_hmap *h;
	int i;
	h = malloc(sizeof(_hmap));
	if (h == 0)
		return 0;
	h->cmp = cmp;
	h->hash = hash;
	h->tsize = size;
	h->table = malloc(4*size);
	if (h->table == 0)
	{
		free(h);
		return 0;
	}
	h->killkeys = killkeys;
	h->size = 0;
	for (i=0;i<size;i++)
		h->table[i] = 0;
	return (hmap) h;
}

void hmap_kill(hmap hh)
{
	_hmap *h;
	pair *p,*np;
	int i;
	h = (_hmap *) hh;
	for (i=0;i<h->tsize;i++)
	{
		p = h->table[i];
		while (p) {
			np = p->next;
			if (h->killkeys)
				free(p->key);
			free(p);
			p = np;
		}
	}
	free(h->table);
	free(h);
}

int hmap_size(hmap hh)
{
	_hmap *h;
	h = (_hmap *) hh;
	return h->size;
}

void **hmap_keys(hmap hh)
{
	_hmap *h;
	pair *p;
	int i,j;
	void **v;
	h = (_hmap *) hh;
	v = malloc(4*h->size);
	if (v == 0)
		return 0;
	j = 0;
	for (i=0;i<h->tsize;i++)
	{
		p = h->table[i];
		while (p)
		{
			v[j++] = p->key;
			p = p->next;
		}
	}
	return v;
}

void **hmap_values(hmap hh)
{
	_hmap *h;
	pair *p;
	int i,j;
	void **v;
	h = (_hmap *) hh;
	v = malloc(4*h->size);
	if (v == 0)
		return 0;
	j = 0;
	for (i=0;i<h->tsize;i++)
	{
		p = h->table[i];
		while (p)
		{
			v[j++] = p->value;
			p = p->next;
		}
	}
	return v;
}

int hmap_add(hmap hh,void *key,void *value)
{
	_hmap *h;
	h = (_hmap *) hh;
	pair *p,**pp;
	int i;
	i = (h->hash)(key);
	pp = &(h->table[i]);
	do {
		p = *pp;
		if (p == 0)
		{
			/* Insert here */
			p = malloc(sizeof(pair));
			if (p == 0)
				return 1;
			*pp = p;
			p->key = key;
			p->value = value;
			p->next = 0;
			h->size++;
			return 0;
		}
		if ((h->cmp)(key,p->key) == 0)
			return 1; /* Already has entry with that key */
		pp = &(p->next);
	} while (1);
}

int hmap_remove(hmap hh,void *key)
{
	_hmap *h;
	h = (_hmap *) hh;
	pair *p,**pp;
	int i;
	i = (h->hash)(key);
	pp = &(h->table[i]);
	do {
		p = *pp;
		if (p == 0)
			return 0; /* Not found */
		if ((h->cmp)(key,p->key) == 0)
		{
			*pp = p->next;
			if (h->killkeys)
				free(p->key);
			free(p);
			h->size--;
			return 1;
		}
		pp = &(p->next);
	} while (1);
}

int hmap_remove2(hmap hh,void *value)
{
	_hmap *h;
	h = (_hmap *) hh;
	pair *p,**pp;
	int i,cnt;
	cnt = 0;
	for (i=0;i<h->tsize;i++)
	{
		pp = &(h->table[i]);
		while (*pp)
		{
			p = *pp;
			if (p->value == value)
			{
				*pp = p->next;
				if (h->killkeys)
					free(p->key);
				free(p);
				h->size--;
				cnt++;
			}
			else
				pp = &(p->next);
		}
	}
	return cnt;
}

void *hmap_get(hmap hh,void *key)
{
	_hmap *h;
	h = (_hmap *) hh;
	pair *p;
	int i;
	i = (h->hash)(key);
	p = h->table[i];
	while (p) {
		if ((h->cmp)(key,p->key) == 0)
			return p->value;
		p = p->next;
	}
	return 0;
}

int hmap_contains(hmap hh,void *key)
{
	_hmap *h;
	h = (_hmap *) hh;
	pair *p;
	int i;
	i = (h->hash)(key);
	p = h->table[i];
	while (p) {
		if ((h->cmp)(key,p->key) == 0)
			return 1;
		p = p->next;
	}
	return 0;
}

#endif
