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