/*
 * (c) Thomas Pornin 2002
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 4. The name of the authors may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 
 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

#ifndef UCPP__NHASH__
#define UCPP__NHASH__

#include "tune.h"

/*
 * Each item stored in the hash table should be a structure beginning
 * with the following header.
 */
typedef struct hash_item_header_ {
	char *ident;
	struct hash_item_header_ *left, *right;
} hash_item_header;

/*
 * This macro takes as argument a pointer to a hash table item (a
 * structure beginning with `hash_item_header') and returns a pointer to
 * the item name. This name should be considered as read-only. The
 * retrieved pointer can become invalid whenever a new item is inserted
 * in or removed from the table.
 */
#define HASH_ITEM_NAME(s) (((hash_item_header *)(s))->ident + sizeof(unsigned))

/*
 * Number of lists for the primary hash step. Can be reduced to save more
 * memory, or increased to speed things up. It should be a power of 2
 * greater or equal than 2 and smaller than UINT_MAX.
 */
#define HTT_NUM_TREES   128

/*
 * Type for a hash table.
 */
typedef struct {
	void (*deldata)(void *);
#ifdef UCPP_CLONE
	void *(*clonedata)(const void *);
#endif
	hash_item_header *tree[HTT_NUM_TREES];
} HTT;

/*
 * Type for a reduced version of HTT with only two binary trees. That
 * version has a lower initialization time and is suitable for situation
 * where only a limited number of elements will be stored, but new tables
 * need frequent initializations.
 */
typedef struct {
	void (*deldata)(void *);
#ifdef UCPP_CLONE
	void *(*clonedata)(const void *);
#endif
	hash_item_header *tree[2];
} HTT2;

#ifdef UCPP_CLONE
#define _pCLONEDATA	, void *(*clonedata)(const void *)
#define _aCLONEDATA	, clonedata
#define _aCLONE(fun)	, fun
#else
#define _pCLONEDATA
#define _aCLONEDATA
#define _aCLONE(fun)
#endif

/*
 * Initialize a hash table. The `deldata' parameter should point to a
 * function which will be invoked on any item removed from the table;
 * that function should take care of the release of memory allocated for
 * that item (except the hash_item_header contents, which are handled
 * internally).
 * The (optional) `clonedata' parameter should point to a function
 * which will be invoked on any item that is cloned to another table.
 */
#define HTT_init	UCPP_PRIVATE(HTT_init)
void HTT_init(HTT *htt, void (*deldata)(void *) _pCLONEDATA);

/*
 * Link an item into the hash table under the given name. If another
 * item of identical name is already present in the table, a pointer to
 * that item is returned; otherwise, the new item is linked into the
 * table and NULL is returned. The object pointed to by `item' is
 * linked from the table, but not the string pointed to by `name'.
 */
#define HTT_put		UCPP_PRIVATE(HTT_put)
void *HTT_put(HTT *htt, void *item, const char *name);

/*
 * Retrieve an item by name from the hash table. NULL is returned if
 * the object is not found.
 */
#define HTT_get		UCPP_PRIVATE(HTT_get)
void *HTT_get(HTT *htt, const char *name);

/*
 * Remove an item from the hash table. 1 is returned if the item was
 * removed, 0 if it was not found.
 */
#define HTT_del		UCPP_PRIVATE(HTT_del)
int HTT_del(HTT *htt, const char *name);

/*
 * For all items stored within the hash table, invoke the provided
 * function with the item as parameter. The function may abort the
 * scan by performing a longjmp() to a context encapsulating the
 * call to that function.
 */
#define HTT_scan	UCPP_PRIVATE(HTT_scan)
#define HTT_scan_arg	UCPP_PRIVATE(HTT_scan_arg)
void HTT_scan(HTT *htt, void (*action)(void *));
void HTT_scan_arg(HTT *htt, void (*action)(void *, void *), void *arg);

/*
 * Release the whole table contents. After a call to this function,
 * the table is ready to accept new items.
 */
#define HTT_kill	UCPP_PRIVATE(HTT_kill)
void HTT_kill(HTT *htt);

#ifdef UCPP_CLONE
/*
 * Clone the whole table contents.
 */
#define HTT_clone	UCPP_PRIVATE(HTT_clone)
void HTT_clone(HTT *ctt, const HTT *htt);
#endif /* UCPP_CLONE */

/*
 * The following functions are identical to the HTT_*() functions, except
 * that they operate on the reduced HTT2 tables.
 */
#define HTT2_init	UCPP_PRIVATE(HTT2_init)
#define HTT2_put	UCPP_PRIVATE(HTT2_put)
#define HTT2_get	UCPP_PRIVATE(HTT2_get)
#define HTT2_del	UCPP_PRIVATE(HTT2_del)
#define HTT2_scan	UCPP_PRIVATE(HTT2_scan)
#define HTT2_scan_arg	UCPP_PRIVATE(HTT2_scan_arg)
#define HTT2_kill	UCPP_PRIVATE(HTT2_kill)
void HTT2_init(HTT2 *htt, void (*deldata)(void *) _pCLONEDATA);
void *HTT2_put(HTT2 *htt, void *item, const char *name);
void *HTT2_get(HTT2 *htt, const char *name);
int HTT2_del(HTT2 *htt, const char *name);
void HTT2_scan(HTT2 *htt, void (*action)(void *));
void HTT2_scan_arg(HTT2 *htt, void (*action)(void *, void *), void *);
void HTT2_kill(HTT2 *htt);

#ifdef UCPP_CLONE
#define HTT2_clone	UCPP_PRIVATE(HTT_clone)
void HTT2_clone(HTT2 *ctt, const HTT2 *htt);
#endif

#endif