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