avltree.c revision 2
1N/A/*
1N/A * CDDL HEADER START
1N/A *
1N/A * The contents of this file are subject to the terms of the
1N/A * Common Development and Distribution License, Version 1.0 only
1N/A * (the "License"). You may not use this file except in compliance
1N/A * with the License.
1N/A *
1N/A * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
1N/A * or http://www.opensolaris.org/os/licensing.
1N/A * See the License for the specific language governing permissions
1N/A * and limitations under the License.
1N/A *
1N/A * When distributing Covered Code, include this CDDL HEADER in each
1N/A * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
1N/A * If applicable, add the following below this CDDL HEADER, with the
1N/A * fields enclosed by brackets "[]" replaced with your own identifying
1N/A * information: Portions Copyright [yyyy] [name of copyright owner]
1N/A *
1N/A * CDDL HEADER END
1N/A */
1N/A/*
1N/A * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
1N/A * Use is subject to license terms.
1N/A */
1N/A
1N/A#pragma ident "%Z%%M% %I% %E% SMI"
1N/A
1N/A#include <sys/avl.h>
1N/A#include <sys/types.h>
1N/A#include <stdlib.h>
1N/A#include "libcmdutils.h"
1N/A
1N/A/*
1N/A * The following interfaces complement the interfaces available in
1N/A * libavl.
1N/A * tnode_compare() - tree node comparison routine
1N/A * add_tnode() - adds nodes to a tree
1N/A * destroy_tree() - destroys a whole tree
1N/A *
1N/A * The libavl routines are very generic and don't have any
1N/A * direct knowledge about the data being stored in the AVL tree,
1N/A * nor any of the details of the AVL tree representation.
1N/A * In addition, the libavl routines do not perform any locking
1N/A * or memory allocation. Appropriate synchronization and memory
1N/A * allocation are the responsibility of the user of the libavl
1N/A * routines.
1N/A *
1N/A * These routines, and the structures defined in "libcmdutils.h",
1N/A * provide the necessary details about the data and AVL tree
1N/A * representation. Currently, the routines available in
1N/A * libcmdutils perform necessary memory allocations, and do not
1N/A * perform locking, therefore they are not thread safe and
1N/A * should not be used by multi-threaded applications.
1N/A *
1N/A * For more information on the avl tree routines, see the well
1N/A * documented source code in avl.c, and the header files in
1N/A * <sys/avl.h> and <sys/avl_impl.h>.
1N/A *
1N/A * Note: The tree must be initialized in the calling application
1N/A * before calling these routines. An example of how this is done:
1N/A * static avl_tree_t *tree = NULL;
1N/A *
1N/A * tnode_compare() - This function is used by libavl's avl_find()
1N/A * routine to abstract out how the data structures are ordered, and
1N/A * must be an argument to libavl's avl_create() function. Therefore,
1N/A * this routine should not be called directly from the calling
1N/A * application.
1N/A *
1N/A * Input:
1N/A * const void *p1 (pointer to the 1st node to compare and
1N/A * is the node which we are try to match
1N/A * or insert into the search tree)
1N/A * const void *p2 (pointer to the 2nd node to compare and
1N/A * is a node which already exists in the
1N/A * search tree)
1N/A *
1N/A * This function returns (as required by the libavl interfaces):
1N/A * * -1 if the 1st argument node is less than the 2nd
1N/A * * 0 if the nodes are equal in value
1N/A * * +1 if the 1st node is greater than the 2nd
1N/A *
1N/A * add_tnode() - Builds a height balanced tree of nodes consisting of
1N/A * a device id and inode number provided by the calling application.
1N/A * The nodes are stored in the specified search tree by using the
1N/A * tnode_compare() routine. Duplicate nodes are not stored.
1N/A *
1N/A * If the specified search tree does not exist (is NULL), then memory
1N/A * is allocated for the tree, and libavl's avl_create() routine is
1N/A * called to initialize the tree with the comparison routine
1N/A * (tnode_compare()) which will be used to compare the tree nodes
1N/A * and populate the tree on subsequent calls by add_tnode() to
1N/A * avl_find().
1N/A *
1N/A * This routine creates a node to be added to the search tree by
1N/A * allocating memory and setting the nodes device id and inode number
1N/A * to those specified. If the node does not exist in the search tree,
1N/A * it is added. If the node already exists in the tree, it is not
1N/A * added (remember, duplicate nodes are not stored), and the node is
1N/A * freed.
1N/A *
1N/A * Input:
1N/A * avl_tree_t **stree (search tree the data is to be stored in)
1N/A * dev_t device (device id of the inode to be stored)
1N/A * ino_t inode (inode number of inode to be stored)
1N/A *
1N/A * This function returns:
1N/A * * +1 if the node was added
1N/A * * 0 if the node was not added (node already exists)
1N/A * * -1 if an error occurred (memory allocation problem)
1N/A *
1N/A * destroy_tree() - The specified tree is destroyed by calling
1N/A * libavl's avl_destroy_nodes() routine to delete a tree without
1N/A * any rebalancing. Memory is freed that had been previously allocated
1N/A * by add_tnode() for the tree's nodes and the search tree itself.
1N/A *
1N/A * Input:
1N/A * avl_tree_t *stree (search tree to destroy)
1N/A *
1N/A * This function does not return anything. Note: The calling
1N/A * application is responsible for setting the search tree to NULL upon
1N/A * return.
1N/A */
1N/A
1N/A/*
1N/A * Compare two nodes by first trying to match on the node's device
1N/A * id, then on the inode number. Return -1 when p1 < p2,
1N/A * 0 when p1 == p2, and 1 when p1 > p2. This function is invoked
1N/A * by avl_find. p1 is always the node we are trying to insert or
1N/A * match in the search database.
1N/A */
1N/Aint
1N/Atnode_compare(const void *p1, const void *p2)
1N/A{
1N/A tree_node_t *n1 = (tree_node_t *)p1;
1N/A tree_node_t *n2 = (tree_node_t *)p2;
1N/A
1N/A /* first match device id */
1N/A if (n1->node_dev < n2->node_dev) {
1N/A return (-1);
1N/A } else if (n1->node_dev == n2->node_dev) {
1N/A /* device id match, now check inode */
1N/A if (n1->node_ino < n2->node_ino) {
1N/A return (-1);
1N/A } else if (n1->node_ino == n2->node_ino) {
1N/A return (0);
1N/A } else {
1N/A return (1);
1N/A }
1N/A } else {
1N/A return (1);
1N/A }
1N/A}
1N/A
1N/A/*
1N/A * Build a height balanced tree of nodes consisting of a device id and
1N/A * an inode number. Duplicate nodes are not stored. Return 1 if
1N/A * node was added to the tree, return -1 upon error, otherwise return 0.
1N/A */
1N/Aint
1N/Aadd_tnode(avl_tree_t **stree, dev_t device, ino_t inode)
1N/A{
1N/A tree_node_t *tnode;
1N/A avl_index_t where;
1N/A
1N/A /*
1N/A * Create an AVL search tree to keep track of inodes
1N/A * visited/reported.
1N/A */
1N/A if (*stree == NULL) {
1N/A if ((*stree = calloc(1, sizeof (avl_tree_t)))
1N/A == NULL) {
1N/A return (-1);
1N/A }
1N/A avl_create(*stree,
1N/A tnode_compare,
1N/A sizeof (tree_node_t),
1N/A OFFSETOF(tree_node_t, avl_link));
1N/A }
1N/A
1N/A /* Initialize the node */
1N/A if ((tnode = calloc(1, sizeof (*tnode))) == NULL) {
1N/A return (-1);
1N/A }
1N/A tnode->node_dev = device;
1N/A tnode->node_ino = inode;
1N/A
1N/A /* If the node is not already in the tree, then insert it */
1N/A if (avl_find(*stree, tnode, &where) == NULL) {
1N/A avl_insert(*stree, tnode, where);
1N/A return (1);
1N/A }
1N/A
1N/A /* The node is already in the tree, so just free it */
1N/A free(tnode);
1N/A return (0);
1N/A}
1N/A
1N/A/*
1N/A * Destroy a search tree.
1N/A */
1N/Avoid
1N/Adestroy_tree(avl_tree_t *stree)
1N/A{
1N/A void *cookie;
1N/A tree_node_t *tnode;
1N/A
1N/A if (stree != NULL) {
1N/A
1N/A cookie = NULL;
1N/A while ((tnode = avl_destroy_nodes(stree, &cookie)) != NULL) {
1N/A free(tnode);
1N/A }
1N/A avl_destroy(stree);
1N/A free(stree);
1N/A }
1N/A}
1N/A