/*
 * Copyright (c) 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.
 */

#include "sm/generic.h"
SM_RCSID("@(#)$Id: example-bsd-tree-list.c,v 1.3 2004/12/26 04:15:55 ca Exp $")

/*
**  Example program how to use RB_ tree as imported from OpenBSD tree(3)
**  All nodes in a RB_ tree must have unique keys, however, this
**  is an extended version in which each node is a list of entries
**  with the same key. This is similar to a hash table where colliding
**  entries are put into a list.
**
**  XXX NOT YET COMPLETE!
**  Which APIs do we want here?  Check application requirements!
**
**  Current problem: tnode and node are different, should a tnode be
**  integrated into node?
**  How to minmize the overhead? RB_ENTRY is 3 pointers + 1 int!
**  Make it a union with list pointers? doesn't help much...: list head
*/

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

#include "sm/bsd-tree.h"
#include "sm/queue.h"

#include <stdio.h>

/* forward declaration of tree node struct (for tree) */
typedef struct tnode_S		tnode_T, *tnode_P;

/* forward declaration of node struct (in list) */
typedef struct node_S		node_T, *node_P;

/* tree itself, this struct is defined in the include file */
typedef struct tree_S		tree_T, *tree_P;

/* declare tree structure with reference to tree node */
RB_HEAD(tree_S, tnode_S);

/*
**  tree node struct:
**  first entry required by RB_,
**  next entry for list,
*/

typedef TAILQ_HEAD(, node_S)	tn_hd_T, *tn_hd_P;
struct tnode_S
{
	RB_ENTRY(tnode_S)	 tn_entry;	/* tree organization data */
	tn_hd_T			 tn_hd;		/* head of list */
};

/*
**  tree node struct:
**  next entry for list,
**  rest application specific
*/

struct node_S
{
	TAILQ_ENTRY(node_S)	 n_link;	/* link to next elem */
	uint		 n_key;		/* key (does not need to be unique) */
	long		 n_value;	/* some values ... */
};

/*
Summary:  a tree consists of tree nodes (tnode_T)
                tree
      tnode_T       tnode_T  
tnode_T  tnode_T         tnode_T  

a tnode_T is the head of a list.

Design decisions:
the list organization depends on the access features that are
required by the application. it doesn't seem to be simple to
write a generic abstraction for this...

can we at least write an abstraction for one type?

*/

/* comparison function for tree nodes, required */
static int
compare_tnodes(tnode_P tnode_a, tnode_P tnode_b)
{
	uint a;
	uint b;

	a = TAILQ_FIRST(&(tnode_a->tn_hd))->n_key;
	b = TAILQ_FIRST(&(tnode_b->tn_hd))->n_key;
	if (a < b)
		return -1;
	else if (a == b)
		return 0;
	else
		return 1;
}

/* comparison function for nodes, required */
static int
compare_nodes(node_P node_a, node_P node_b)
{
	uint a;
	uint b;

	a = node_a->n_key;
	b = node_b->n_key;
	if (a < b)
		return -1;
	else if (a == b)
		return 0;
	else
		return 1;
}

/*
**  Generate code for tree: tree struct, tree node struct,
**  RB_ENTRY in tree node struct, comparison function.
**  For an include file, use RB_PROTOTYPE() with the same arguments
**  to specify the functions prototypes.
*/

RB_GENERATE(tree_S, tnode_S, tn_entry, compare_tnodes)

/* turn the following functions into macros? */

/* find a node in a tree */
static node_P
tl_find(tree_P tree, node_P node)
{
	tnode_T tnode;
	tnode_P tnode_ret;
	node_P node_h;

	SM_REQUIRE(tree != NULL);
	SM_REQUIRE(node != NULL);

	/* create a tree node, add the node which contains the key to it */
	sm_memzero(&tnode, sizeof(tnode));
	TAILQ_INIT(&(tnode.tn_hd));
	TAILQ_INSERT_TAIL(&(tnode.tn_hd), node, n_link);
	tnode_ret = RB_FIND(tree_S, tree, &tnode);
	if (tnode_ret == NULL)
		return NULL;

	/* loop through list to find match */
	TAILQ_FOREACH(node_h, &(tnode.tn_hd), n_link)
	{
		if (compare_nodes(node, node_h) == 0)
			return node_h;
	}
	return NULL;
}

/* insert a node in a tree */
static sm_ret_T
tl_insert(tree_P tree, node_P node)
{
	tnode_T tnode;
	tnode_P tnode_ret;

	SM_REQUIRE(tree != NULL);
	SM_REQUIRE(node != NULL);

	/* create a tree node, add the node which contains the key to it */
	sm_memzero(&tnode, sizeof(tnode));
	TAILQ_INIT(&(tnode.tn_hd));
	TAILQ_INSERT_TAIL(&(tnode.tn_hd), node, n_link);
	tnode_ret = RB_FIND(tree_S, tree, &tnode);
	if (tnode_ret == NULL)
	{
		tnode_P tnode_h;

		tnode_h = (tnode_P) sm_zalloc(sizeof(*tnode_h));
		if (tnode_h == NULL)
			return ENOMEM;

		tnode_ret = RB_INSERT(tree_S, tree, tnode_h);
		if (tnode_ret == NULL)
			return EINVAL;	/* OOPS! */
		return SM_SUCCESS;
	}
	/* just append... all keys are identical in this list */
	/* later enhancement: secondary keys... */
	TAILQ_INSERT_TAIL(&(tnode_ret->tn_hd), node, n_link);
	return SM_SUCCESS;
}

static sm_ret_T
tl_rm(tree_P tree, node_P node)
{
	tnode_T tnode;
	tnode_P tnode_ret;

	SM_REQUIRE(tree != NULL);
	SM_REQUIRE(node != NULL);

	/* create a tree node, add the node which contains the key to it */
	sm_memzero(&tnode, sizeof(tnode));
	TAILQ_INIT(&(tnode.tn_hd));
	TAILQ_INSERT_TAIL(&(tnode.tn_hd), node, n_link);
	tnode_ret = RB_FIND(tree_S, tree, &tnode);
	if (tnode_ret == NULL)
		return sm_err_perm(SM_E_NOTFOUND);

	TAILQ_REMOVE(&(tnode_ret->tn_hd), node, n_link);
	sm_free(node);
	if (TAILQ_EMPTY(&(tnode_ret->tn_hd)))
	{
		if (RB_REMOVE(tree_S, tree, tnode_ret) == NULL)
		{
			/* shouldn't happen! */
			SM_ASSERT(tnode_ret == NULL);
			return sm_err_perm(EINVAL);
		}
		sm_free(tnode_ret);
	}
	return SM_SUCCESS;
}

int
main(int argc, char **argv)
{
	sm_ret_T ret;
	tree_T tree;	/* a tree */
	tnode_P tnode;
	tnode_T telm;
	node_P node;
	node_T elm;

	/* initialize tree */
	RB_INIT(&tree);

	/*
	**  Find a node in a tree: tree struct, head of tree, node.
	**  Note: this requires a full node, even though only the key
	**  is used for comparisons!
	*/

	node = tl_find(&tree, &elm);
	if (node == NULL)
	{

		/*
		**  Insert a node in a tree: tree struct, head of tree, node.
		*/

		ret = tl_insert(&tree, node);
	}
	ret = tl_rm(&tree, node);

	return 0;
}