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
tnode_compare(const void * p1,const void * p2)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
add_tnode(avl_tree_t ** stree,dev_t device,ino_t inode)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
destroy_tree(avl_tree_t * stree)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