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 } 248