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