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 2004 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 * 26 * lut.c -- simple lookup table module 27 * 28 * this file contains a very simple lookup table (lut) implementation. 29 * the tables only support insert & lookup, no delete, and can 30 * only be walked in one order. if the key already exists 31 * for something being inserted, the previous entry is simply 32 * replaced. 33 */ 34 35 #pragma ident "%Z%%M% %I% %E% SMI" 36 37 #include <stdio.h> 38 #include "alloc.h" 39 #include "out.h" 40 #include "stats.h" 41 #include "lut.h" 42 #include "tree.h" 43 44 /* info created by lut_add(), private to this module */ 45 struct lut { 46 struct lut *lut_left; 47 struct lut *lut_right; 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 90 if (root == NULL) { 91 /* not in tree, create new node */ 92 root = MALLOC(sizeof (*root)); 93 root->lut_lhs = lhs; 94 root->lut_rhs = rhs; 95 root->lut_left = root->lut_right = NULL; 96 stats_counter_bump(Addtotal); 97 return (root); 98 } 99 100 if (cmp_func) 101 diff = (*cmp_func)(root->lut_lhs, lhs); 102 else 103 diff = (const char *)lhs - (const char *)root->lut_lhs; 104 105 if (diff == 0) { 106 /* already in tree, replace node */ 107 root->lut_rhs = rhs; 108 } else if (diff > 0) 109 root->lut_left = lut_add(root->lut_left, lhs, rhs, cmp_func); 110 else 111 root->lut_right = lut_add(root->lut_right, lhs, rhs, cmp_func); 112 return (root); 113 } 114 115 /* 116 * lut_lookup -- find an entry 117 */ 118 void * 119 lut_lookup(struct lut *root, void *lhs, lut_cmp cmp_func) 120 { 121 int diff; 122 123 stats_counter_bump(Lookuptotal); 124 125 if (root == NULL) 126 return (NULL); 127 128 if (cmp_func) 129 diff = (*cmp_func)(root->lut_lhs, lhs); 130 else 131 diff = (const char *)lhs - (const char *)root->lut_lhs; 132 133 if (diff == 0) { 134 return (root->lut_rhs); 135 } else if (diff > 0) 136 return (lut_lookup(root->lut_left, lhs, cmp_func)); 137 else 138 return (lut_lookup(root->lut_right, lhs, cmp_func)); 139 } 140 141 /* 142 * lut_lookup_lhs -- find an entry, return the matched key (lut_lhs) 143 */ 144 void * 145 lut_lookup_lhs(struct lut *root, void *lhs, lut_cmp cmp_func) 146 { 147 int diff; 148 149 stats_counter_bump(Lookuptotal); 150 151 if (root == NULL) 152 return (NULL); 153 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 return (lut_lookup_lhs(root->lut_left, lhs, cmp_func)); 163 else 164 return (lut_lookup_lhs(root->lut_right, lhs, cmp_func)); 165 } 166 167 /* 168 * lut_walk -- walk the table in lexical order 169 */ 170 void 171 lut_walk(struct lut *root, lut_cb callback, void *arg) 172 { 173 if (root) { 174 lut_walk(root->lut_left, callback, arg); 175 (*callback)(root->lut_lhs, root->lut_rhs, arg); 176 lut_walk(root->lut_right, callback, arg); 177 } 178 } 179 180 /* 181 * lut_free -- free the lut 182 */ 183 void 184 lut_free(struct lut *root, lut_cb callback, void *arg) 185 { 186 if (root) { 187 lut_free(root->lut_left, callback, arg); 188 root->lut_left = NULL; 189 lut_free(root->lut_right, callback, arg); 190 root->lut_right = NULL; 191 if (callback) 192 (*callback)(root->lut_lhs, root->lut_rhs, arg); 193 FREE(root); 194 stats_counter_bump(Freetotal); 195 } 196 } 197