/*
 * Copyright (c) 2003, 2004 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.
 *
 *	$Id: bht-int.h,v 1.12 2005/06/16 00:09:34 ca Exp $
 */

/*
**  This file may be included multiple times! Do NOT protect against that.
*/

#include "sm/types.h"
#include "sm/error.h"

/* Structure of one hash table entry. */
typedef struct sm_bht_entry_S sm_bht_entry_T, *sm_bht_entry_P;

struct sm_bht_entry_S
{
	/*
	**  Notice: we don't copy keys (or value)!
	**	These are just pointers to the original data.
	**	Hence they must be "persistent".
	**  Question: do we want to add an option to make a copy?
	*/

	char		*bhe_key;	/* lookup key */
	uint		 bhe_len;	/* key length */
	void		*bhe_value;	/* associated value */

	/* XXX should we use something from queue.h? */
	sm_bht_entry_P	 bhe_next;	/* colliding entry */
	sm_bht_entry_P	 bhe_prev;	/* colliding entry */
#if SM_TWO_KEYS
	char		*bhe_key2;	/* lookup key */
	uint		 bhe_len2;	/* key length */
	sm_bht_entry_P	 bhe_next2;	/* colliding entry */
	sm_bht_entry_P	 bhe_prev2;	/* colliding entry */
#endif /* SM_TWO_KEYS */
};

/* Structure of one hash table. */
typedef struct sm_bht_S sm_bht_T, *sm_bht_P;
struct sm_bht_S
{
	uint		 bht_size;	/* length of entries array */
	uint		 bht_used;	/* number of entries in table */
	uint		 bht_limit;	/* max number of entries */
#if SM_BHT_PERF
	/* performance (statistics) data */
	ulong		 bht_adds;	/* */
	ulong		 bht_lookups;	/* */
	ulong		 bht_deletes;	/* */
	ulong		 bht_acollisions;	/* */
	ulong		 bht_lcollisions;	/* */
	ulong		 bht_dcollisions;	/* */
	uint		 bht_grows;	/* */
	uint		 bht_chainlen;	/* */
	uint		 bht_chainmax;	/* */
#endif /* SM_BHT_PERF */
	sm_bht_entry_P	*bht_data;	/* entries array, auto-resized */
#if SM_TWO_KEYS
	sm_bht_entry_P	*bht_data2;	/* entries array, auto-resized */
#endif /* SM_TWO_KEYS */
};

/*
**  bhfree_F should get both keys for the TWO_KEY case...
**  or none at all (which makes some it harder for some applications
**  that don't store the key in the value (struct)).
*/

typedef void		 (*sm_bhfree_F)(void *_value, void *_key, void *_ctx);
typedef sm_ret_T	 (*sm_bhwalk_F)(sm_bht_entry_P, void *);

sm_bht_P	 sm_bht_new(uint _size, uint _limit);
sm_ret_T	 sm_bht_create(sm_bht_P *_ptable);
sm_ret_T	 sm_bht_setopt(sm_bht_P _table, uint _htsize, uint _limit);
sm_ret_T	 sm_bht_getopt(sm_bht_P _table, uint *_phtsize, uint *_plimit);
sm_ret_T	 sm_bht_open(sm_bht_P *_ptable);

sm_ret_T	 sm_bht_add(sm_bht_P _bht, char *_key, uint _len,
#if SM_TWO_KEYS
				char *_key2, uint _len2,
#endif /* SM_TWO_KEYS */
				void *_value, sm_bht_entry_P *_entry);

sm_bht_entry_P	 sm_bht_locate(sm_bht_P _bht, const char *_key, uint _len);

void	*sm_bht_find(sm_bht_P _bht, const char *_key, uint _len);

void	 sm_bht_rm(sm_bht_P _bht, const char *_key, uint _len,
				sm_bhfree_F _free_fn, void *_ctx);

void	 sm_bht_rm_all(sm_bht_P _bht, const char *_key, uint _len,
				sm_bhfree_F _free_fn, void *_ctx);

void	 sm_bht_destroy(sm_bht_P _bht, sm_bhfree_F _free_fn, void *_ctx);

sm_ret_T sm_bht_walk(sm_bht_P _bht, sm_bhwalk_F _fn, void *);

#if 0
sm_bht_entry_P	*sm_bht_list(sm_bht_P _bht);
#endif /* 0 */

void	 sm_bht_stats(sm_bht_P _bht, char *_out, uint _len);

#ifndef SM_BHT_INT_H
#define SM_BHT_INT_H
/* For external access to the list */
#define bht_entry_next(bhe)	((bhe)->bhe_next)
#define bht_entry_prev(bhe)	((bhe)->bhe_prev)

#define bht_entry_key(bhe)	((bhe)->bhe_key)
#define bht_entry_keylen(bhe)	((bhe)->bhe_len)
#define bht_entry_value(bhe)	((bhe)->bhe_value)

#if SM_BHT_PERF
# define bhtincradd(table)	((table)->bht_adds++)
# define bhtincrlu(table)	((table)->bht_lookups++)
# define bhtincrdel(table)	((table)->bht_deletes++)
# define bhtincracol(table)	((table)->bht_acollisions++)
# define bhtincrlcol(table)	((table)->bht_lcollisions++)
# define BHTINCRDCOL(table, elem)	do {	\
	if ((elem)->bhe_next != NULL || (elem)->bhe_prev != NULL)	\
			(table)->bht_dcollisions++;			\
	} while (0)
# define bhtincrgrows(table)	((table)->bht_grows++)
# define bhtinitchain(table)	(table)->bht_chainlen = 0
# define BHTINCRCHAIN(table)	do {	\
					if (++(table)->bht_chainlen >	\
					    (table)->bht_chainmax)	\
						(table)->bht_chainmax =	\
							(table)->bht_chainlen;\
				} while (0)
# define BHTCHAINLEN(table, elem) do {	\
					sm_bht_entry_P h;		\
					(table)->bht_chainlen = 0;	\
					h = elem;			\
					while (h != NULL)		\
					{				\
						++(table)->bht_chainlen;\
						h = h->bhe_next;	\
					}				\
					if ((table)->bht_chainlen >	\
					    (table)->bht_chainmax)	\
						(table)->bht_chainmax =	\
							(table)->bht_chainlen;\
				} while (0)
#else /* SM_BHT_PERF */
# define bhtincradd(table)
# define bhtincrlu(table)
# define bhtincrdel(table)
# define bhtincracol(table)
# define bhtincrlcol(table)
# define BHTINCRDCOL(table, elem)
# define bhtincrgrows(table)
# define bhtinitchain(table)
# define BHTINCRCHAIN(table)
# define BHTCHAINLEN(table, elem)
#endif /* SM_BHT_PERF */

#endif /* SM_BHT_INT_H */