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