usr/src/lib/libcmdutils/common/avltree.c

   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 }