/*
 * 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.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.
*/

#include "sm/bsd-tree.h"

#include <stdio.h>

/* forward declaration of node struct (for tree) */
typedef struct node_S		node_T, *node_P;

/* tree itself, this struct is defined in the include file */
typedef struct t_tree_S		t_tree_T, *t_tree_P;

/* declare tree structure with reference to node */
RB_HEAD(t_tree_S, node_S);

/* node struct: first entry required by RB_, rest application specific */
struct node_S
{
	RB_ENTRY(node_S)	n_entry;	/* tree organization data */
	uint			n_key;		/* unique key */
	long			n_value;	/* some values ... */
};

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

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

/*
**  Generate code for tree: tree struct, node struct, RB_ENTRY in node struct,
**  comparison function. That's it, now the functions can be used.
**  For an include file, use RB_PROTOTYPE() with the same arguments
**  to specify the functions prototypes.
*/

RB_GENERATE(t_tree_S, node_S, n_entry, compare_nodes)

int
main(int argc, char **argv)
{
	t_tree_T tree;	/* a tree */
	node_P tree_node, node, result;
	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!
	*/

	tree_node = RB_FIND(t_tree_S, &tree, &elm);
	if (tree_node == NULL)
	{

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

		result = RB_INSERT(t_tree_S, &tree, node);
		if (result == NULL)
		{
			/* OK */
		}
		else
		{
			/* collision! */
		}
	}

	return 0;
}