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