/*
 * Copyright (c) 2002-2005 Sendmail, Inc. and its suppliers.
 *	All rights reserved.
 *
 * By using this file, you agree to the terms and conditions set
 * forth in the LICENSE file which can be found at the top level of
 * the sendmail distribution.
 */

#include "sm/generic.h"
SM_RCSID("@(#)$Id: bhtable.c,v 1.49 2006/05/02 17:13:40 ca Exp $")

#include "sm/assert.h"
#include "sm/error.h"
#include "sm/memops.h"
#include "sm/heap.h"
#include "bhtable.h"

#if SM_BHT_PERF
# include <stdio.h>	/* snprintf */
#endif

/*
**	Notes:
**	- locking must be provided by caller.
*/

/* Check whether two keys x and y of length l are equal */
#define BHT_KEY_EQ(x, y, l) ((x)[0] == (y)[0] && sm_memeq((x), (y), (l)))

/*
**  BHT_HASH -- hash a key
**
**	Parameters:
**		key -- key to hash
**		len -- len of key
**		htsize -- size of hash table
**
**	Returns:
**		hash value
**
**	Note: it might be useful to make the hash function a pointer in
**		the hash table context such that different hash functions
**		can be used.
**
**	Last code review: 2005-04-08 21:41:17
**	Last code change:
*/

static uint
bht_hash(const char *key, uint len, uint htsize)
{
	ulong h;
#if IPV4_HASH
	int c, d;
#else
	ulong g;
#endif

	SM_REQUIRE(key != NULL);

	/* From the "Dragon" book by Aho, Sethi and Ullman.  */
#if IPV4_HASH
	h = 0xABC3D20F;
#else
	h = 0;
#endif
	while (len-- > 0)
	{
#if IPV4_HASH
		d = *key++;
		c = d;
		c ^= c<<6;
		h += (c<<11) ^ (c>>1);
		h ^= (d<<14) + (d<<7) + (d<<4) + d;
#else /* IPV4_HASH */
		h = (h << 4) + *key++;
		g = h & 0xf0000000;
		if (g != 0)
		{
			h ^= (g >> 24);
			h ^= g;
		}
#endif /* IPV4_HASH */
	}
	return h % htsize;
}

/*
**  BHT_LINK -- insert element into table (prepend it)
**
**	Parameters:
**		table -- hash table
**		elem -- element
**
**	Returns:
**		It's a macro...
**
**	Last code review: 2005-04-08 22:23:11
**	Last code change:
*/

#define BHT_LINK(table, elem) do				\
	{							\
		sm_bht_entry_P *he = table->bht_data +		\
				bht_hash(elem->bhe_key,		\
					elem->bhe_len, table->bht_size);\
		elem->bhe_prev = NULL;				\
		if ((elem->bhe_next = *he) != NULL)		\
		{						\
			(*he)->bhe_prev = elem;			\
			bhtincracol(table);			\
			BHTCHAINLEN(table, elem);		\
		}						\
		*he = elem;					\
		table->bht_used++;				\
	} while (0)

#if SM_TWO_KEYS
/*
**  BHT2_LINK -- insert element into table (prepend it)
**
**	Parameters:
**		table -- hash table
**		elem -- element
**
**	Returns:
**		It's a macro...
**
**	Last code review: 2005-04-08 22:23:46
**	Last code change:
*/

#define BHT2_LINK(table, elem) do				\
	{							\
		sm_bht_entry_P *h = table->bht_data2 +		\
				bht_hash(elem->bhe_key2,	\
					elem->bhe_len2, table->bht_size);\
		elem->bhe_prev2 = NULL;				\
		if ((elem->bhe_next2 = *h) != NULL)		\
			(*h)->bhe_prev2 = elem;			\
		*h = elem;					\
	} while (0)
#endif /* SM_TWO_KEYS */

/*
**  BHT_INIT -- allocate and initialize hash table
**
**	Parameters:
**		table -- pointer to table
**		htsize -- size of hash table
**
**	Returns:
**		usual sm_error code; ENOMEM
**
**	Last code review: 2005-04-08 22:24:36
**	Last code change:
*/

sm_ret_T
bht_init(sm_bht_P table, uint htsize)
{
	sm_bht_entry_P *h;

	htsize |= 1;	/* odd, isn't it? */
	table->bht_data = h = (sm_bht_entry_P *) sm_zalloc(htsize *
							sizeof(sm_bht_entry_P));
	if (h == NULL)
		return sm_error_temp(SM_EM_HT, ENOMEM);
#if SM_TWO_KEYS
	table->bht_data2 = h = (sm_bht_entry_P *) sm_zalloc(htsize *
							sizeof(sm_bht_entry_P));
	if (h == NULL)
	{
		sm_free(table->bht_data);
		return sm_error_temp(SM_EM_HT, ENOMEM);
	}
#endif /* SM_TWO_KEYS */
	table->bht_size = htsize;
	table->bht_used = 0;
	return SM_SUCCESS;
}

/*
**  BHT_NEW -- create initial hash table
**
**	Parameters:
**		htsize -- size of hash table
**		limit -- maximum number of entries
**
**	Returns:
**		pointer to table; NULL on error (ENOMEM)
**
**	Last code review: 2005-04-08 22:26:00
**	Last code change:
*/

sm_bht_P
sm_bht_new(uint htsize, uint limit)
{
	sm_bht_P table;
	sm_ret_T ret;

	table = (sm_bht_P) sm_zalloc(sizeof(*table));
	if (table == NULL)
		return NULL;
	ret = bht_init(table, htsize < BHT_MIN_SIZE ? BHT_MIN_SIZE : htsize);
	if (!sm_is_success(ret))
	{
		sm_free_size(table, sizeof(*table));
		return NULL;
	}
	table->bht_limit = limit;
	return table;
}

/*
**  BHT_GROW -- extend existing table (double its size)
**
**	Parameters:
**		table -- (return) pointer to table
**
**	Returns:
**		usual sm_error code; ENOMEM
**
**	Last code review: 2005-04-08 22:35:56
**	Last code change:
*/

static sm_ret_T
sm_bht_grow(sm_bht_P table)
{
	uint old_size, i;
	sm_bht_entry_P hte, hte_next, *h, *old_entries;
#if SM_TWO_KEYS
	sm_bht_entry_P *old_entries2;
#endif
	sm_ret_T ret;

	old_size = table->bht_size;
	h = table->bht_data;
	old_entries = h;
#if SM_TWO_KEYS
	old_entries2 = table->bht_data2;
#endif
	ret = bht_init(table, 2 * old_size);
	if (sm_is_err(ret))
		return ret;

	/* copy old entries into new table */
	for (i = old_size; i > 0; i--)
	{
		for (hte = *h++; hte != NULL; hte = hte_next)
		{
			hte_next = hte->bhe_next;
			BHT_LINK(table, hte);
		}
	}

#if SM_TWO_KEYS
	h = old_entries2;
	for (i = old_size; i > 0; i--)
	{
		for (hte = *h++; hte != NULL; hte = hte_next)
		{
			hte_next = hte->bhe_next2;
			BHT2_LINK(table, hte);
		}
	}
#endif /* SM_TWO_KEYS */
	sm_free((void *) old_entries);
#if SM_TWO_KEYS
	sm_free((void *) old_entries2);
#endif
	bhtincrgrows(table);
	return SM_SUCCESS;
}

/*
**  BHT_ADD -- add (key, value) pair
**	Note: this does not check whether key exists! It will simply add
**		the new pair.
**
**	Parameters:
**		table -- table
**		key -- key to hash
**		len -- len of key
**		value -- value to add
**		entry -- pointer to entry (output)
**
**	Returns:
**		usual sm_error code; ENOMEM, SM_E_FULL
**
**	Side Effects: may grow table.
**
**	Last code review: 2005-04-08 22:45:07
**	Last code change:
*/

sm_ret_T
sm_bht_add(sm_bht_P table, char *key, uint len,
#if SM_TWO_KEYS
	char *key2, uint len2,
#endif
	void *value,
	sm_bht_entry_P *entry)
{
	sm_ret_T ret;
	sm_bht_entry_P hte;

	SM_REQUIRE(table != NULL);
	SM_REQUIRE(entry != NULL);

	if (table->bht_limit > 0 && table->bht_used >= table->bht_limit)
		return sm_error_temp(SM_EM_HT, SM_E_FULL);
	if (table->bht_used >= table->bht_size)
	{
		ret = sm_bht_grow(table);
		if (sm_is_err(ret))
			return ret;
	}
	hte = (sm_bht_entry_P) sm_malloc(sizeof(*hte));
	if (hte == NULL)
		return sm_error_temp(SM_EM_HT, ENOMEM);
	bhtincradd(table);
#if SM_TWO_KEYS
	hte->bhe_key2 = NULL;
#endif
	hte->bhe_key = key;
	hte->bhe_len = len;
#if SM_TWO_KEYS
	hte->bhe_key2 = key2;
	hte->bhe_len2 = len2;
	BHT2_LINK(table, hte);
#endif /* SM_TWO_KEYS */
	hte->bhe_value = value;
	BHT_LINK(table, hte);
	*entry = hte;
	return SM_SUCCESS;
}

/* common code for next two routines, only return type is different */
#define BHT_LOOKUP(ret)	\
	if (table == NULL)	\
		return NULL;	\
	bhtincrlu(table);	\
	bhtinitchain(table);	\
	for (hte = table->bht_data[bht_hash(key, len, table->bht_size)]; \
	     hte != NULL; hte = hte->bhe_next)				\
	{								\
		if (len == hte->bhe_len &&				\
		    BHT_KEY_EQ(key, hte->bhe_key, len))			\
			return (ret);					\
		bhtincrlcol(table);					\
		BHTINCRCHAIN(table);					\
	}	\
	return NULL

#if SM_TWO_KEYS
/* common code for next two routines, only return type is different */
#define BHT2_LOOKUP(ret)	\
	if (table == NULL)	\
		return NULL;	\
	bhtincrlu(table);	\
	bhtinitchain(table);	\
	for (hte = table->bht_data2[bht_hash(key2, len2, table->bht_size)]; \
	     hte != NULL; hte = hte->bhe_next2)				\
	{								\
		if (len2 == hte->bhe_len2 &&				\
		    BHT_KEY_EQ(key2, hte->bhe_key2, len2))		\
			return (ret);					\
		bhtincrlcol(table);					\
		BHTINCRCHAIN(table);					\
	}	\
	return NULL
#endif /* SM_TWO_KEYS */

/*
**  BHT_FIND -- lookup value
**
**	Parameters:
**		table -- pointer to table
**		key -- key to hash
**		len -- len of key
**
**	Returns:
**		pointer to value
**
**	Last code review: 2005-03-20 02:00:42
**	Last code change:
*/

void *
sm_bht_find(sm_bht_P table, const char *key, uint len)
{
	sm_bht_entry_P hte;

	BHT_LOOKUP(hte->bhe_value);
}

/*
**  BHT_LOCATE -- lookup entry
**
**	Parameters:
**		table -- pointer to table
**		key -- key to hash
**		len -- len of key
**
**	Returns:
**		pointer to entry.
**
**	Last code review: 2005-03-20 02:00:42
**	Last code change:
*/

sm_bht_entry_P
sm_bht_locate(sm_bht_P table, const char *key, uint len)
{
	sm_bht_entry_P hte;

	BHT_LOOKUP(hte);
}

#if SM_TWO_KEYS
/*
**  BHT2_FIND_FIRST -- lookup value
**
**	Parameters:
**		table -- pointer to table
**		key2 -- key to hash
**		len2 -- len of key
**
**	Returns:
**		pointer to value
**
**	Last code review: 2005-04-08 22:46:00
**	Last code change:
*/

void *
bht2_find_first(sm_bht_P table, const char *key2, uint len2)
{
	sm_bht_entry_P hte;

	BHT2_LOOKUP(hte->bhe_value);
}

/*
**  BHT2_LOCATE_FIRST -- lookup entry
**
**	Parameters:
**		table -- pointer to table
**		key2 -- key to hash
**		len2 -- len of key
**
**	Returns:
**		pointer to entry.
**
**	Last code review: 2005-04-08 22:46:07
**	Last code change:
*/

sm_bht_entry_P
bht2_locate_first(sm_bht_P table, const char *key2, uint len2)
{
	sm_bht_entry_P hte;

	BHT2_LOOKUP(hte);
}

/*
**  BHT2_LOCATE_NEXT -- get next entry
**
**	Parameters:
**		table -- pointer to table
**		prev -- previous entry
**
**	Returns:
**		pointer to entry.
**
**	Last code review: 2005-04-08 22:46:19
**	Last code change:
*/

sm_bht_entry_P
bht2_locate_next(sm_bht_P table, sm_bht_entry_P prev)
{
	SM_REQUIRE(table != NULL);
	SM_REQUIRE(prev != NULL);

	return prev->bhe_next2;
}
#endif /* SM_TWO_KEYS */


#if SM_TWO_KEYS
# define BHT_RM_2							\
		if (hte->bhe_next2 != NULL)				\
			hte->bhe_next2->bhe_prev2 = hte->bhe_prev2;	\
		if (hte->bhe_prev2 != NULL)				\
			hte->bhe_prev2->bhe_next2 = hte->bhe_next2;	\
		else							\
		{							\
			h = table->bht_data2 +				\
				bht_hash(hte->bhe_key2,			\
					hte->bhe_len2,			\
					table->bht_size);		\
			*h = hte->bhe_next2;				\
		}
#else /* SM_TWO_KEYS */
# define BHT_RM_2
#endif /* SM_TWO_KEYS */

/*
**  Notice: we can't have a simple bht_rm_entry() function
**  since this removal requires the pointer in bht->data,
**  not just the pointer to the entry itself.
*/

#define BH_RM_FCT(one)							\
{									\
	sm_bht_entry_P hte, *h, hte_next;				\
									\
	SM_REQUIRE(table != NULL);					\
	h = table->bht_data + bht_hash(key, len, table->bht_size);	\
	bhtincrdel(table);						\
									\
	for (hte = *h; hte != NULL; hte = hte_next)			\
	{								\
		hte_next = hte->bhe_next;				\
		if (len == hte->bhe_len &&				\
		    BHT_KEY_EQ(key, hte->bhe_key, len))			\
		{							\
			BHTINCRDCOL(table, hte);			\
			/* remove element from list */			\
			if (hte->bhe_next != NULL)			\
				hte->bhe_next->bhe_prev = hte->bhe_prev; \
			if (hte->bhe_prev != NULL)			\
				hte->bhe_prev->bhe_next = hte->bhe_next; \
			else						\
				*h = hte->bhe_next;			\
			BHT_RM_2					\
			SM_ASSERT(table->bht_used > 0);			\
			table->bht_used--;				\
			if (free_fn != NULL)				\
				(*free_fn)(hte->bhe_value, hte->bhe_key, ctx); \
			sm_free_size(hte, sizeof(*hte));		\
			one;						\
		}							\
	}								\
}

/*
**  BHT_RM_ALL -- remove all entries that match key/len
**
**	Parameters:
**		table -- pointer to table
**		key -- key to look up
**		len -- len of key
**		free_fn -- function to free individual entries
**		ctx -- context for free function.
**
**	Returns:
**		Nothing. (should it return number of removed entries?)
**
**	Last code review: 2005-04-08 22:49:20
**	Last code change: 2005-03-20 02:15:08
*/

void
sm_bht_rm_all(sm_bht_P table, const char *key, uint len, sm_bhfree_F free_fn, void *ctx)
BH_RM_FCT(SM_NOOP)

/*
**  BHT_RM -- remove first entry that matches key/len
**
**	Parameters:
**		table -- pointer to table
**		key -- key to look up
**		len -- len of key
**		free_fn -- function to free individual entries
**		ctx -- context for free function.
**
**	Returns:
**		Nothing. (should it return whether an entry has been removed?)
**
**	Last code review: 2005-03-30 23:00:44
**	Last code change: 2005-03-20 02:15:08
*/

void
sm_bht_rm(sm_bht_P table, const char *key, uint len, sm_bhfree_F free_fn, void *ctx)
BH_RM_FCT(return)

/*
**  BHT_DESTROY -- destroy hash table
**
**	Parameters:
**		table -- pointer to table
**		free_fn -- function to free individual entries
**		ctx -- context for free function.
**
**	Returns:
**		Nothing.
**
**	Last code review: 2005-04-08 22:50:40
**	Last code change:
*/

void
sm_bht_destroy(sm_bht_P table, sm_bhfree_F free_fn, void *ctx)
{
	uint i;
	sm_bht_entry_P hte, hte_next, *h;

	if (table == NULL)
		return;
	i = table->bht_size;
	h = table->bht_data;
	while (i-- > 0)
	{
		for (hte = *h++; hte != NULL; hte = hte_next)
		{
			hte_next = hte->bhe_next;
			if (free_fn != NULL)
				(*free_fn)(hte->bhe_value, hte->bhe_key, ctx);
			sm_free_size(hte, sizeof(*hte));
		}
	}
	sm_free((void *) table->bht_data);
	table->bht_data = NULL;
#if SM_TWO_KEYS
	sm_free((void *) table->bht_data2);
#endif
	sm_free_size(table, sizeof(*table));
}

/*
**  BHT_WALK -- iterate over hash table, apply a function to each element
**
**	Parameters:
**		table -- pointer to table
**		action -- function to apply
**		ctx -- context for function.
**
**	Returns:
**		return value from action if not SM_SUCCESS
**
**	Last code review: 2005-03-31 04:51:42
**	Last code change:
*/

sm_ret_T
sm_bht_walk(sm_bht_P table, sm_bhwalk_F action, void *ctx)
{
	uint i;
	sm_bht_entry_P *h, hte, htn;
	sm_ret_T ret;

	SM_REQUIRE(table != NULL);
	i = table->bht_size;
	h = table->bht_data;
	while (i-- > 0)
	{
		for (hte = *h++; hte != NULL; hte = htn)
		{
			htn = hte->bhe_next;
			ret = (*action)(hte, ctx);
			if (ret != SM_SUCCESS)
				return ret;
		}
	}
	return SM_SUCCESS;
}

#if 0
///*
//**  BHT_LIST - list all table members
//**
//**	Parameters:
//**		table -- pointer to table
//**
//**	Returns:
//**		array of entries (NULL on error).
//*/
//
//sm_bht_entry_P *
//sm_bht_list(sm_bht_P table)
//{
//	uint count, i;
//	sm_bht_entry_P *list, member;
//
//	count = 0;
//	if (table != NULL)
//	{
//		list = (sm_bht_entry_P *) sm_malloc(sizeof(*list) *
//						 (table->bht_used + 1));
//		if (list == NULL)
//			return NULL;
//		for (i = 0; i < table->bht_size; i++)
//		{
//			for (member = table->bht_data[i]; member != NULL;
//			     member = member->bhe_next)
//				list[count++] = member;
//		}
//	}
//	else
//	{
//		list = (sm_bht_entry_P *) sm_malloc(sizeof(*list));
//		if (list == NULL)
//			return NULL;
//	}
//	list[count] = NULL;
//	return list;
//}
#endif /* 0 */

/*
**  BHT_STATS -- print statistics about table (if available)
**
**	Parameters:
**		table -- table
**		out -- pointer to output data
**		len -- maximum length of output data
**
**	Returns:
**		Nothing.
**
**	Last code review: 2005-04-08 22:51:19
**	Last code change:
*/

void
sm_bht_stats(sm_bht_P table, char *out, uint len)
{
	SM_REQUIRE(table != NULL);
	SM_REQUIRE(out != NULL);
	SM_REQUIRE(len > 0);
#if SM_BHT_PERF
	snprintf(out, len, "adds              %9lu\n"
		"lookups           %9lu\n"
		"deletes           %9lu\n"
		"add collisions    %9lu\n"
		"lookup collisions %9lu\n"
		"delete collisions %9lu\n"
		"max chain len     %9u\n"
		"grows             %9u\n"
		, table->bht_adds, table->bht_lookups, table->bht_deletes
		, table->bht_acollisions
		, table->bht_lcollisions, table->bht_dcollisions
		, table->bht_chainmax, table->bht_grows);
#else /* SM_BHT_PERF */
	*out = '\0';
#endif /* SM_BHT_PERF */
}