xref: /illumos-gate/usr/src/lib/libcmdutils/common/avltree.c (revision d1151f9b)

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2003 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 *
 * Copyright 2017 Joyent, Inc.
 */

#include <sys/avl.h>
#include <sys/types.h>
#include <stdlib.h>
#include <stddef.h>
#include "libcmdutils.h"

/*
 * The following interfaces complement the interfaces available in
 * libavl.
 * 	tnode_compare() - tree node comparison routine
 *	add_tnode() - adds nodes to a tree
 *	destroy_tree() - destroys a whole tree
 *
 * The libavl routines are very generic and don't have any
 * direct knowledge about the data being stored in the AVL tree,
 * nor any of the details of the AVL tree representation.
 * In addition, the libavl routines do not perform any locking
 * or memory allocation.  Appropriate synchronization and memory
 * allocation are the responsibility of the user of the libavl
 * routines.
 *
 * These routines, and the structures defined in "libcmdutils.h",
 * provide the necessary details about the data and AVL tree
 * representation.  Currently, the routines available in
 * libcmdutils perform necessary memory allocations, and do not
 * perform locking, therefore they are not thread safe and
 * should not be used by multi-threaded applications.
 *
 * For more information on the avl tree routines, see the well
 * documented source code in avl.c, and the header files in
 * <sys/avl.h> and <sys/avl_impl.h>.
 *
 * Note: The tree must be initialized in the calling application
 * before calling these routines. An example of how this is done:
 *	static avl_tree_t       *tree = NULL;
 *
 * tnode_compare() - This function is used by libavl's avl_find()
 * routine to abstract out how the data structures are ordered, and
 * must be an argument to libavl's avl_create() function.  Therefore,
 * this routine should not be called directly from the calling
 * application.
 *
 * Input:
 *	const void *p1	(pointer to the 1st node to compare and
 *			 is the node which we are try to match
 *			 or insert into the search tree)
 *	const void *p2	(pointer to the 2nd node to compare and
 *			 is a node which already exists in the
 *			 search tree)
 *
 * This function returns (as required by the libavl interfaces):
 * 	* -1 if the 1st argument node is less than the 2nd
 * 	* 0 if the nodes are equal in value
 * 	* +1 if the 1st node is greater than the 2nd
 *
 * add_tnode() - Builds a height balanced tree of nodes consisting of
 * a device id and inode number provided by the calling application.
 * The nodes are stored in the specified search tree by using the
 * tnode_compare() routine. Duplicate nodes are not stored.
 *
 * If the specified search tree does not exist (is NULL), then memory
 * is allocated for the tree, and libavl's avl_create() routine is
 * called to initialize the tree with the comparison routine
 * (tnode_compare()) which will be used to compare the tree nodes
 * and populate the tree on subsequent calls by add_tnode() to
 * avl_find().
 *
 * This routine creates a node to be added to the search tree by
 * allocating memory and setting the nodes device id and inode number
 * to those specified.  If the node does not exist in the search tree,
 * it is added.  If the node already exists in the tree, it is not
 * added (remember, duplicate nodes are not stored), and the node is
 * freed.
 *
 * Input:
 *	avl_tree_t **stree 	(search tree the data is to be stored in)
 *	dev_t device		(device id of the inode to be stored)
 *	ino_t inode		(inode number of inode to be stored)
 *
 * This function returns:
 * 	* +1 if the node was added
 * 	* 0 if the node was not added (node already exists)
 * 	* -1 if an error occurred (memory allocation problem)
 *
 * destroy_tree() - The specified tree is destroyed by calling
 * libavl's avl_destroy_nodes() routine to delete a tree without
 * any rebalancing.  Memory is freed that had been previously allocated
 * by add_tnode() for the tree's nodes and the search tree itself.
 *
 * Input:
 *	avl_tree_t *stree	(search tree to destroy)
 *
 * This function does not return anything.  Note:  The calling
 * application is responsible for setting the search tree to NULL upon
 * return.
 */

/*
 * Compare two nodes by first trying to match on the node's device
 * id, then on the inode number.  Return -1 when p1 < p2,
 * 0 when p1 == p2, and 1 when p1 > p2.  This function is invoked
 * by avl_find.  p1 is always the node we are trying to insert or
 * match in the search database.
 */
int
tnode_compare(const void *p1, const void *p2)
{
	tree_node_t *n1 = (tree_node_t *)p1;
	tree_node_t *n2 = (tree_node_t *)p2;

	/* first match device id */
	if (n1->node_dev < n2->node_dev) {
		return (-1);
	} else if (n1->node_dev == n2->node_dev) {
		/* device id match, now check inode */
		if (n1->node_ino < n2->node_ino) {
			return (-1);
		} else if (n1->node_ino == n2->node_ino) {
			return (0);
		} else {
			return (1);
		}
	} else {
		return (1);
	}
}

/*
 * Build a height balanced tree of nodes consisting of a device id and
 * an inode number.  Duplicate nodes are not stored.  Return 1 if
 * node was added to the tree, return -1 upon error, otherwise return 0.
 */
int
add_tnode(avl_tree_t **stree, dev_t device, ino_t inode)
{
	tree_node_t	*tnode;
	avl_index_t	where;

	/*
	 * Create an AVL search tree to keep track of inodes
	 * visited/reported.
	 */
	if (*stree == NULL) {
		if ((*stree = calloc(1, sizeof (avl_tree_t)))
		    == NULL) {
			return (-1);
		}
		avl_create(*stree,
		    tnode_compare,
		    sizeof (tree_node_t),
		    offsetof(tree_node_t, avl_link));
	}

	/* Initialize the node */
	if ((tnode = calloc(1, sizeof (*tnode))) == NULL) {
		return (-1);
	}
	tnode->node_dev = device;
	tnode->node_ino = inode;

	/* If the node is not already in the tree, then insert it */
	if (avl_find(*stree, tnode, &where) == NULL) {
		avl_insert(*stree, tnode, where);
		return (1);
	}

	/* The node is already in the tree, so just free it */
	free(tnode);
	return (0);
}

/*
 * Destroy a search tree.
 */
void
destroy_tree(avl_tree_t *stree)
{
	void *cookie;
	tree_node_t	*tnode;

	if (stree != NULL) {

		cookie = NULL;
		while ((tnode = avl_destroy_nodes(stree, &cookie)) != NULL) {
			free(tnode);
		}
		avl_destroy(stree);
		free(stree);
	}
}