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 "tree.h" 42 43 /* info created by lut_add(), private to this module */ 44 struct lut { 45 struct lut *lut_left; 46 struct lut *lut_right; 47 struct lut *lut_parent; 48 void *lut_lhs; /* search key */ 49 void *lut_rhs; /* the datum */ 50 }; 51 52 static struct stats *Addtotal; 53 static struct stats *Lookuptotal; 54 static struct stats *Freetotal; 55 56 void 57 lut_init(void) 58 { 59 Addtotal = stats_new_counter("lut.adds", "total adds", 1); 60 Lookuptotal = stats_new_counter("lut.lookup", "total lookups", 1); 61 Freetotal = stats_new_counter("lut.frees", "total frees", 1); 62 } 63 64 void 65 lut_fini(void) 66 { 67 stats_delete(Addtotal); 68 stats_delete(Lookuptotal); 69 stats_delete(Freetotal); 70 } 71 72 /* 73 * lut_add -- add an entry to the table 74 * 75 * use it like this: 76 * struct lut *root = NULL; 77 * root = lut_add(root, key, value, cmp_func); 78 * 79 * the cmp_func can be strcmp(). pass in NULL and instead of 80 * calling a cmp_func the routine will just look at the difference 81 * between key pointers (useful when all strings are kept in a 82 * string table so they are equal if their pointers are equal). 83 * 84 */ 85 struct lut * 86 lut_add(struct lut *root, void *lhs, void *rhs, lut_cmp cmp_func) 87 { 88 int diff; 89 struct lut **tmp_hdl = &root, *parent = NULL, *tmp = root; 90 91 while (tmp) { 92 if (cmp_func) 93 diff = (*cmp_func)(tmp->lut_lhs, lhs); 94 else 95 diff = (const char *)lhs - (const char *)tmp->lut_lhs; 96 97 if (diff == 0) { 98 /* already in tree, replace node */ 99 tmp->lut_rhs = rhs; 100 return (root); 101 } else if (diff > 0) { 102 tmp_hdl = &(tmp->lut_left); 103 parent = tmp; 104 tmp = tmp->lut_left; 105 } else { 106 tmp_hdl = &(tmp->lut_right); 107 parent = tmp; 108 tmp = tmp->lut_right; 109 } 110 } 111 112 /* either empty tree or not in tree, so create new node */ 113 *tmp_hdl = MALLOC(sizeof (*root)); 114 (*tmp_hdl)->lut_lhs = lhs; 115 (*tmp_hdl)->lut_rhs = rhs; 116 (*tmp_hdl)->lut_parent = parent; 117 (*tmp_hdl)->lut_left = (*tmp_hdl)->lut_right = NULL; 118 stats_counter_bump(Addtotal); 119 120 return (root); 121 } 122 123 void * 124 lut_lookup(struct lut *root, void *lhs, lut_cmp cmp_func) 125 { 126 int diff; 127 128 stats_counter_bump(Lookuptotal); 129 130 while (root) { 131 if (cmp_func) 132 diff = (*cmp_func)(root->lut_lhs, lhs); 133 else 134 diff = (const char *)lhs - (const char *)root->lut_lhs; 135 136 if (diff == 0) 137 return (root->lut_rhs); 138 else if (diff > 0) 139 root = root->lut_left; 140 else 141 root = root->lut_right; 142 } 143 return (NULL); 144 } 145 146 void * 147 lut_lookup_lhs(struct lut *root, void *lhs, lut_cmp cmp_func) 148 { 149 int diff; 150 151 stats_counter_bump(Lookuptotal); 152 153 while (root) { 154 if (cmp_func) 155 diff = (*cmp_func)(root->lut_lhs, lhs); 156 else 157 diff = (const char *)lhs - (const char *)root->lut_lhs; 158 159 if (diff == 0) 160 return (root->lut_lhs); 161 else if (diff > 0) 162 root = root->lut_left; 163 else 164 root = root->lut_right; 165 } 166 return (NULL); 167 } 168 169 /* 170 * lut_walk -- walk the table in lexical order 171 */ 172 void 173 lut_walk(struct lut *root, lut_cb callback, void *arg) 174 { 175 struct lut *tmp = root; 176 struct lut *prev_child = NULL; 177 178 if (root == NULL) 179 return; 180 181 while (tmp->lut_left != NULL) 182 tmp = tmp->lut_left; 183 184 /* do callback on leftmost node */ 185 (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg); 186 187 for (;;) { 188 if (tmp->lut_right != NULL && tmp->lut_right != prev_child) { 189 tmp = tmp->lut_right; 190 while (tmp->lut_left != NULL) 191 tmp = tmp->lut_left; 192 193 /* do callback on leftmost node */ 194 (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg); 195 } else if (tmp->lut_parent != NULL) { 196 prev_child = tmp; 197 tmp = tmp->lut_parent; 198 /* 199 * do callback on parent only if we're coming up 200 * from the left 201 */ 202 if (tmp->lut_right != prev_child) 203 (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg); 204 } else 205 return; 206 } 207 } 208 209 /* 210 * lut_free -- free the lut 211 */ 212 void 213 lut_free(struct lut *root, lut_cb callback, void *arg) 214 { 215 struct lut *tmp = root; 216 struct lut *prev_child = NULL; 217 218 if (root == NULL) 219 return; 220 221 while (tmp->lut_left != NULL) 222 tmp = tmp->lut_left; 223 224 /* do callback on leftmost node */ 225 if (callback) 226 (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg); 227 228 for (;;) { 229 if (tmp->lut_right != NULL && tmp->lut_right != prev_child) { 230 tmp = tmp->lut_right; 231 while (tmp->lut_left != NULL) 232 tmp = tmp->lut_left; 233 234 /* do callback on leftmost node */ 235 if (callback) 236 (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg); 237 } else if (tmp->lut_parent != NULL) { 238 prev_child = tmp; 239 tmp = tmp->lut_parent; 240 FREE(prev_child); 241 /* 242 * do callback on parent only if we're coming up 243 * from the left 244 */ 245 if (tmp->lut_right != prev_child && callback) 246 (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg); 247 } else { 248 /* 249 * free the root node and then we're done 250 */ 251 FREE(tmp); 252 return; 253 } 254 } 255 } 256