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