usr/src/cmd/fm/eversholt/common/lut.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 (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  *
  25  * lut.c -- simple lookup table module
  26  *
  27  * this file contains a very simple lookup table (lut) implementation.
  28  * the tables only support insert & lookup, no delete, and can
  29  * only be walked in one order.  if the key already exists
  30  * for something being inserted, the previous entry is simply
  31  * replaced.
  32  */
  33
  34 #pragma ident   "%Z%%M% %I%     %E% SMI"
  35
  36 #include <stdio.h>
  37 #include "alloc.h"
  38 #include "out.h"
  39 #include "stats.h"
  40 #include "lut.h"
  41 #include "lut_impl.h"
  42 #include "tree.h"
  43
  44 static struct stats *Addtotal;
  45 static struct stats *Lookuptotal;
  46 static struct stats *Freetotal;
  47
  48 void
  49 lut_init(void)
  50 {
  51         Addtotal = stats_new_counter("lut.adds", "total adds", 1);
  52         Lookuptotal = stats_new_counter("lut.lookup", "total lookups", 1);
  53         Freetotal = stats_new_counter("lut.frees", "total frees", 1);
  54 }
  55
  56 void
  57 lut_fini(void)
  58 {
  59         stats_delete(Addtotal);
  60         stats_delete(Lookuptotal);
  61         stats_delete(Freetotal);
  62 }
  63
  64 /*
  65  * lut_add -- add an entry to the table
  66  *
  67  * use it like this:
  68  *      struct lut *root = NULL;
  69  *      root = lut_add(root, key, value, cmp_func);
  70  *
  71  * the cmp_func can be strcmp().  pass in NULL and instead of
  72  * calling a cmp_func the routine will just look at the difference
  73  * between key pointers (useful when all strings are kept in a
  74  * string table so they are equal if their pointers are equal).
  75  *
  76  */
  77 struct lut *
  78 lut_add(struct lut *root, void *lhs, void *rhs, lut_cmp cmp_func)
  79 {
  80         int diff;
  81         struct lut **tmp_hdl = &root, *parent = NULL, *tmp = root;
  82
  83         while (tmp) {
  84                 if (cmp_func)
  85                         diff = (*cmp_func)(tmp->lut_lhs, lhs);
  86                 else
  87                         diff = (const char *)lhs - (const char *)tmp->lut_lhs;
  88
  89                 if (diff == 0) {
  90                         /* already in tree, replace node */
  91                         tmp->lut_rhs = rhs;
  92                         return (root);
  93                 } else if (diff > 0) {
  94                         tmp_hdl = &(tmp->lut_left);
  95                         parent = tmp;
  96                         tmp = tmp->lut_left;
  97                 } else {
  98                         tmp_hdl = &(tmp->lut_right);
  99                         parent = tmp;
 100                         tmp = tmp->lut_right;
 101                 }
 102         }
 103
 104         /* either empty tree or not in tree, so create new node */
 105         *tmp_hdl = MALLOC(sizeof (*root));
 106         (*tmp_hdl)->lut_lhs = lhs;
 107         (*tmp_hdl)->lut_rhs = rhs;
 108         (*tmp_hdl)->lut_parent = parent;
 109         (*tmp_hdl)->lut_left = (*tmp_hdl)->lut_right = NULL;
 110         stats_counter_bump(Addtotal);
 111
 112         return (root);
 113 }
 114
 115 void *
 116 lut_lookup(struct lut *root, void *lhs, lut_cmp cmp_func)
 117 {
 118         int diff;
 119
 120         stats_counter_bump(Lookuptotal);
 121
 122         while (root) {
 123                 if (cmp_func)
 124                         diff = (*cmp_func)(root->lut_lhs, lhs);
 125                 else
 126                         diff = (const char *)lhs - (const char *)root->lut_lhs;
 127
 128                 if (diff == 0)
 129                         return (root->lut_rhs);
 130                 else if (diff > 0)
 131                         root = root->lut_left;
 132                 else
 133                         root = root->lut_right;
 134         }
 135         return (NULL);
 136 }
 137
 138 void *
 139 lut_lookup_lhs(struct lut *root, void *lhs, lut_cmp cmp_func)
 140 {
 141         int diff;
 142
 143         stats_counter_bump(Lookuptotal);
 144
 145         while (root) {
 146                 if (cmp_func)
 147                         diff = (*cmp_func)(root->lut_lhs, lhs);
 148                 else
 149                         diff = (const char *)lhs - (const char *)root->lut_lhs;
 150
 151                 if (diff == 0)
 152                         return (root->lut_lhs);
 153                 else if (diff > 0)
 154                         root = root->lut_left;
 155                 else
 156                         root = root->lut_right;
 157         }
 158         return (NULL);
 159 }
 160
 161 /*
 162  * lut_walk -- walk the table in lexical order
 163  */
 164 void
 165 lut_walk(struct lut *root, lut_cb callback, void *arg)
 166 {
 167         struct lut *tmp = root;
 168         struct lut *prev_child = NULL;
 169
 170         if (root == NULL)
 171                 return;
 172
 173         while (tmp->lut_left != NULL)
 174                 tmp = tmp->lut_left;
 175
 176         /* do callback on leftmost node */
 177         (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
 178
 179         for (;;) {
 180                 if (tmp->lut_right != NULL && tmp->lut_right != prev_child) {
 181                         tmp = tmp->lut_right;
 182                         while (tmp->lut_left != NULL)
 183                                 tmp = tmp->lut_left;
 184
 185                         /* do callback on leftmost node */
 186                         (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
 187                 } else if (tmp->lut_parent != NULL) {
 188                         prev_child = tmp;
 189                         tmp = tmp->lut_parent;
 190                         /*
 191                          * do callback on parent only if we're coming up
 192                          * from the left
 193                          */
 194                         if (tmp->lut_right != prev_child)
 195                                 (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
 196                 } else
 197                         return;
 198         }
 199 }
 200
 201 /*
 202  * lut_free -- free the lut
 203  */
 204 void
 205 lut_free(struct lut *root, lut_cb callback, void *arg)
 206 {
 207         struct lut *tmp = root;
 208         struct lut *prev_child = NULL;
 209
 210         if (root == NULL)
 211                 return;
 212
 213         while (tmp->lut_left != NULL)
 214                 tmp = tmp->lut_left;
 215
 216         /* do callback on leftmost node */
 217         if (callback)
 218                 (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
 219
 220         for (;;) {
 221                 if (tmp->lut_right != NULL && tmp->lut_right != prev_child) {
 222                         tmp = tmp->lut_right;
 223                         while (tmp->lut_left != NULL)
 224                                 tmp = tmp->lut_left;
 225
 226                         /* do callback on leftmost node */
 227                         if (callback)
 228                                 (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
 229                 } else if (tmp->lut_parent != NULL) {
 230                         prev_child = tmp;
 231                         tmp = tmp->lut_parent;
 232                         FREE(prev_child);
 233                         /*
 234                          * do callback on parent only if we're coming up
 235                          * from the left
 236                          */
 237                         if (tmp->lut_right != prev_child && callback)
 238                                 (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
 239                 } else {
 240                         /*
 241                          * free the root node and then we're done
 242                          */
 243                         FREE(tmp);
 244                         return;
 245                 }
 246         }
 247 }