1*0Sstevel@tonic-gate /* 2*0Sstevel@tonic-gate * CDDL HEADER START 3*0Sstevel@tonic-gate * 4*0Sstevel@tonic-gate * The contents of this file are subject to the terms of the 5*0Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only 6*0Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance 7*0Sstevel@tonic-gate * with the License. 8*0Sstevel@tonic-gate * 9*0Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10*0Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 11*0Sstevel@tonic-gate * See the License for the specific language governing permissions 12*0Sstevel@tonic-gate * and limitations under the License. 13*0Sstevel@tonic-gate * 14*0Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 15*0Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16*0Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 17*0Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 18*0Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 19*0Sstevel@tonic-gate * 20*0Sstevel@tonic-gate * CDDL HEADER END 21*0Sstevel@tonic-gate */ 22*0Sstevel@tonic-gate /* 23*0Sstevel@tonic-gate * Copyright 2003 Sun Microsystems, Inc. All rights reserved. 24*0Sstevel@tonic-gate * Use is subject to license terms. 25*0Sstevel@tonic-gate */ 26*0Sstevel@tonic-gate 27*0Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 28*0Sstevel@tonic-gate 29*0Sstevel@tonic-gate #include <sys/avl.h> 30*0Sstevel@tonic-gate #include <sys/types.h> 31*0Sstevel@tonic-gate #include <stdlib.h> 32*0Sstevel@tonic-gate #include "libcmdutils.h" 33*0Sstevel@tonic-gate 34*0Sstevel@tonic-gate /* 35*0Sstevel@tonic-gate * The following interfaces complement the interfaces available in 36*0Sstevel@tonic-gate * libavl. 37*0Sstevel@tonic-gate * tnode_compare() - tree node comparison routine 38*0Sstevel@tonic-gate * add_tnode() - adds nodes to a tree 39*0Sstevel@tonic-gate * destroy_tree() - destroys a whole tree 40*0Sstevel@tonic-gate * 41*0Sstevel@tonic-gate * The libavl routines are very generic and don't have any 42*0Sstevel@tonic-gate * direct knowledge about the data being stored in the AVL tree, 43*0Sstevel@tonic-gate * nor any of the details of the AVL tree representation. 44*0Sstevel@tonic-gate * In addition, the libavl routines do not perform any locking 45*0Sstevel@tonic-gate * or memory allocation. Appropriate synchronization and memory 46*0Sstevel@tonic-gate * allocation are the responsibility of the user of the libavl 47*0Sstevel@tonic-gate * routines. 48*0Sstevel@tonic-gate * 49*0Sstevel@tonic-gate * These routines, and the structures defined in "libcmdutils.h", 50*0Sstevel@tonic-gate * provide the necessary details about the data and AVL tree 51*0Sstevel@tonic-gate * representation. Currently, the routines available in 52*0Sstevel@tonic-gate * libcmdutils perform necessary memory allocations, and do not 53*0Sstevel@tonic-gate * perform locking, therefore they are not thread safe and 54*0Sstevel@tonic-gate * should not be used by multi-threaded applications. 55*0Sstevel@tonic-gate * 56*0Sstevel@tonic-gate * For more information on the avl tree routines, see the well 57*0Sstevel@tonic-gate * documented source code in avl.c, and the header files in 58*0Sstevel@tonic-gate * <sys/avl.h> and <sys/avl_impl.h>. 59*0Sstevel@tonic-gate * 60*0Sstevel@tonic-gate * Note: The tree must be initialized in the calling application 61*0Sstevel@tonic-gate * before calling these routines. An example of how this is done: 62*0Sstevel@tonic-gate * static avl_tree_t *tree = NULL; 63*0Sstevel@tonic-gate * 64*0Sstevel@tonic-gate * tnode_compare() - This function is used by libavl's avl_find() 65*0Sstevel@tonic-gate * routine to abstract out how the data structures are ordered, and 66*0Sstevel@tonic-gate * must be an argument to libavl's avl_create() function. Therefore, 67*0Sstevel@tonic-gate * this routine should not be called directly from the calling 68*0Sstevel@tonic-gate * application. 69*0Sstevel@tonic-gate * 70*0Sstevel@tonic-gate * Input: 71*0Sstevel@tonic-gate * const void *p1 (pointer to the 1st node to compare and 72*0Sstevel@tonic-gate * is the node which we are try to match 73*0Sstevel@tonic-gate * or insert into the search tree) 74*0Sstevel@tonic-gate * const void *p2 (pointer to the 2nd node to compare and 75*0Sstevel@tonic-gate * is a node which already exists in the 76*0Sstevel@tonic-gate * search tree) 77*0Sstevel@tonic-gate * 78*0Sstevel@tonic-gate * This function returns (as required by the libavl interfaces): 79*0Sstevel@tonic-gate * * -1 if the 1st argument node is less than the 2nd 80*0Sstevel@tonic-gate * * 0 if the nodes are equal in value 81*0Sstevel@tonic-gate * * +1 if the 1st node is greater than the 2nd 82*0Sstevel@tonic-gate * 83*0Sstevel@tonic-gate * add_tnode() - Builds a height balanced tree of nodes consisting of 84*0Sstevel@tonic-gate * a device id and inode number provided by the calling application. 85*0Sstevel@tonic-gate * The nodes are stored in the specified search tree by using the 86*0Sstevel@tonic-gate * tnode_compare() routine. Duplicate nodes are not stored. 87*0Sstevel@tonic-gate * 88*0Sstevel@tonic-gate * If the specified search tree does not exist (is NULL), then memory 89*0Sstevel@tonic-gate * is allocated for the tree, and libavl's avl_create() routine is 90*0Sstevel@tonic-gate * called to initialize the tree with the comparison routine 91*0Sstevel@tonic-gate * (tnode_compare()) which will be used to compare the tree nodes 92*0Sstevel@tonic-gate * and populate the tree on subsequent calls by add_tnode() to 93*0Sstevel@tonic-gate * avl_find(). 94*0Sstevel@tonic-gate * 95*0Sstevel@tonic-gate * This routine creates a node to be added to the search tree by 96*0Sstevel@tonic-gate * allocating memory and setting the nodes device id and inode number 97*0Sstevel@tonic-gate * to those specified. If the node does not exist in the search tree, 98*0Sstevel@tonic-gate * it is added. If the node already exists in the tree, it is not 99*0Sstevel@tonic-gate * added (remember, duplicate nodes are not stored), and the node is 100*0Sstevel@tonic-gate * freed. 101*0Sstevel@tonic-gate * 102*0Sstevel@tonic-gate * Input: 103*0Sstevel@tonic-gate * avl_tree_t **stree (search tree the data is to be stored in) 104*0Sstevel@tonic-gate * dev_t device (device id of the inode to be stored) 105*0Sstevel@tonic-gate * ino_t inode (inode number of inode to be stored) 106*0Sstevel@tonic-gate * 107*0Sstevel@tonic-gate * This function returns: 108*0Sstevel@tonic-gate * * +1 if the node was added 109*0Sstevel@tonic-gate * * 0 if the node was not added (node already exists) 110*0Sstevel@tonic-gate * * -1 if an error occurred (memory allocation problem) 111*0Sstevel@tonic-gate * 112*0Sstevel@tonic-gate * destroy_tree() - The specified tree is destroyed by calling 113*0Sstevel@tonic-gate * libavl's avl_destroy_nodes() routine to delete a tree without 114*0Sstevel@tonic-gate * any rebalancing. Memory is freed that had been previously allocated 115*0Sstevel@tonic-gate * by add_tnode() for the tree's nodes and the search tree itself. 116*0Sstevel@tonic-gate * 117*0Sstevel@tonic-gate * Input: 118*0Sstevel@tonic-gate * avl_tree_t *stree (search tree to destroy) 119*0Sstevel@tonic-gate * 120*0Sstevel@tonic-gate * This function does not return anything. Note: The calling 121*0Sstevel@tonic-gate * application is responsible for setting the search tree to NULL upon 122*0Sstevel@tonic-gate * return. 123*0Sstevel@tonic-gate */ 124*0Sstevel@tonic-gate 125*0Sstevel@tonic-gate /* 126*0Sstevel@tonic-gate * Compare two nodes by first trying to match on the node's device 127*0Sstevel@tonic-gate * id, then on the inode number. Return -1 when p1 < p2, 128*0Sstevel@tonic-gate * 0 when p1 == p2, and 1 when p1 > p2. This function is invoked 129*0Sstevel@tonic-gate * by avl_find. p1 is always the node we are trying to insert or 130*0Sstevel@tonic-gate * match in the search database. 131*0Sstevel@tonic-gate */ 132*0Sstevel@tonic-gate int 133*0Sstevel@tonic-gate tnode_compare(const void *p1, const void *p2) 134*0Sstevel@tonic-gate { 135*0Sstevel@tonic-gate tree_node_t *n1 = (tree_node_t *)p1; 136*0Sstevel@tonic-gate tree_node_t *n2 = (tree_node_t *)p2; 137*0Sstevel@tonic-gate 138*0Sstevel@tonic-gate /* first match device id */ 139*0Sstevel@tonic-gate if (n1->node_dev < n2->node_dev) { 140*0Sstevel@tonic-gate return (-1); 141*0Sstevel@tonic-gate } else if (n1->node_dev == n2->node_dev) { 142*0Sstevel@tonic-gate /* device id match, now check inode */ 143*0Sstevel@tonic-gate if (n1->node_ino < n2->node_ino) { 144*0Sstevel@tonic-gate return (-1); 145*0Sstevel@tonic-gate } else if (n1->node_ino == n2->node_ino) { 146*0Sstevel@tonic-gate return (0); 147*0Sstevel@tonic-gate } else { 148*0Sstevel@tonic-gate return (1); 149*0Sstevel@tonic-gate } 150*0Sstevel@tonic-gate } else { 151*0Sstevel@tonic-gate return (1); 152*0Sstevel@tonic-gate } 153*0Sstevel@tonic-gate } 154*0Sstevel@tonic-gate 155*0Sstevel@tonic-gate /* 156*0Sstevel@tonic-gate * Build a height balanced tree of nodes consisting of a device id and 157*0Sstevel@tonic-gate * an inode number. Duplicate nodes are not stored. Return 1 if 158*0Sstevel@tonic-gate * node was added to the tree, return -1 upon error, otherwise return 0. 159*0Sstevel@tonic-gate */ 160*0Sstevel@tonic-gate int 161*0Sstevel@tonic-gate add_tnode(avl_tree_t **stree, dev_t device, ino_t inode) 162*0Sstevel@tonic-gate { 163*0Sstevel@tonic-gate tree_node_t *tnode; 164*0Sstevel@tonic-gate avl_index_t where; 165*0Sstevel@tonic-gate 166*0Sstevel@tonic-gate /* 167*0Sstevel@tonic-gate * Create an AVL search tree to keep track of inodes 168*0Sstevel@tonic-gate * visited/reported. 169*0Sstevel@tonic-gate */ 170*0Sstevel@tonic-gate if (*stree == NULL) { 171*0Sstevel@tonic-gate if ((*stree = calloc(1, sizeof (avl_tree_t))) 172*0Sstevel@tonic-gate == NULL) { 173*0Sstevel@tonic-gate return (-1); 174*0Sstevel@tonic-gate } 175*0Sstevel@tonic-gate avl_create(*stree, 176*0Sstevel@tonic-gate tnode_compare, 177*0Sstevel@tonic-gate sizeof (tree_node_t), 178*0Sstevel@tonic-gate OFFSETOF(tree_node_t, avl_link)); 179*0Sstevel@tonic-gate } 180*0Sstevel@tonic-gate 181*0Sstevel@tonic-gate /* Initialize the node */ 182*0Sstevel@tonic-gate if ((tnode = calloc(1, sizeof (*tnode))) == NULL) { 183*0Sstevel@tonic-gate return (-1); 184*0Sstevel@tonic-gate } 185*0Sstevel@tonic-gate tnode->node_dev = device; 186*0Sstevel@tonic-gate tnode->node_ino = inode; 187*0Sstevel@tonic-gate 188*0Sstevel@tonic-gate /* If the node is not already in the tree, then insert it */ 189*0Sstevel@tonic-gate if (avl_find(*stree, tnode, &where) == NULL) { 190*0Sstevel@tonic-gate avl_insert(*stree, tnode, where); 191*0Sstevel@tonic-gate return (1); 192*0Sstevel@tonic-gate } 193*0Sstevel@tonic-gate 194*0Sstevel@tonic-gate /* The node is already in the tree, so just free it */ 195*0Sstevel@tonic-gate free(tnode); 196*0Sstevel@tonic-gate return (0); 197*0Sstevel@tonic-gate } 198*0Sstevel@tonic-gate 199*0Sstevel@tonic-gate /* 200*0Sstevel@tonic-gate * Destroy a search tree. 201*0Sstevel@tonic-gate */ 202*0Sstevel@tonic-gate void 203*0Sstevel@tonic-gate destroy_tree(avl_tree_t *stree) 204*0Sstevel@tonic-gate { 205*0Sstevel@tonic-gate void *cookie; 206*0Sstevel@tonic-gate tree_node_t *tnode; 207*0Sstevel@tonic-gate 208*0Sstevel@tonic-gate if (stree != NULL) { 209*0Sstevel@tonic-gate 210*0Sstevel@tonic-gate cookie = NULL; 211*0Sstevel@tonic-gate while ((tnode = avl_destroy_nodes(stree, &cookie)) != NULL) { 212*0Sstevel@tonic-gate free(tnode); 213*0Sstevel@tonic-gate } 214*0Sstevel@tonic-gate avl_destroy(stree); 215*0Sstevel@tonic-gate free(stree); 216*0Sstevel@tonic-gate } 217*0Sstevel@tonic-gate } 218