1*0Sstevel@tonic-gate /* 2*0Sstevel@tonic-gate * CDDL HEADER START 3*0Sstevel@tonic-gate * 4*0Sstevel@tonic-gate * The contents of this file are subject to the terms of the 5*0Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only 6*0Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance 7*0Sstevel@tonic-gate * with the License. 8*0Sstevel@tonic-gate * 9*0Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10*0Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 11*0Sstevel@tonic-gate * See the License for the specific language governing permissions 12*0Sstevel@tonic-gate * and limitations under the License. 13*0Sstevel@tonic-gate * 14*0Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 15*0Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16*0Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 17*0Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 18*0Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 19*0Sstevel@tonic-gate * 20*0Sstevel@tonic-gate * CDDL HEADER END 21*0Sstevel@tonic-gate */ 22*0Sstevel@tonic-gate /* 23*0Sstevel@tonic-gate * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 24*0Sstevel@tonic-gate * Use is subject to license terms. 25*0Sstevel@tonic-gate * 26*0Sstevel@tonic-gate * lut.c -- simple lookup table module 27*0Sstevel@tonic-gate * 28*0Sstevel@tonic-gate * this file contains a very simple lookup table (lut) implementation. 29*0Sstevel@tonic-gate * the tables only support insert & lookup, no delete, and can 30*0Sstevel@tonic-gate * only be walked in one order. if the key already exists 31*0Sstevel@tonic-gate * for something being inserted, the previous entry is simply 32*0Sstevel@tonic-gate * replaced. 33*0Sstevel@tonic-gate */ 34*0Sstevel@tonic-gate 35*0Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 36*0Sstevel@tonic-gate 37*0Sstevel@tonic-gate #include <stdio.h> 38*0Sstevel@tonic-gate #include "alloc.h" 39*0Sstevel@tonic-gate #include "out.h" 40*0Sstevel@tonic-gate #include "stats.h" 41*0Sstevel@tonic-gate #include "lut.h" 42*0Sstevel@tonic-gate #include "tree.h" 43*0Sstevel@tonic-gate 44*0Sstevel@tonic-gate /* info created by lut_add(), private to this module */ 45*0Sstevel@tonic-gate struct lut { 46*0Sstevel@tonic-gate struct lut *lut_left; 47*0Sstevel@tonic-gate struct lut *lut_right; 48*0Sstevel@tonic-gate void *lut_lhs; /* search key */ 49*0Sstevel@tonic-gate void *lut_rhs; /* the datum */ 50*0Sstevel@tonic-gate }; 51*0Sstevel@tonic-gate 52*0Sstevel@tonic-gate static struct stats *Addtotal; 53*0Sstevel@tonic-gate static struct stats *Lookuptotal; 54*0Sstevel@tonic-gate static struct stats *Freetotal; 55*0Sstevel@tonic-gate 56*0Sstevel@tonic-gate void 57*0Sstevel@tonic-gate lut_init(void) 58*0Sstevel@tonic-gate { 59*0Sstevel@tonic-gate Addtotal = stats_new_counter("lut.adds", "total adds", 1); 60*0Sstevel@tonic-gate Lookuptotal = stats_new_counter("lut.lookup", "total lookups", 1); 61*0Sstevel@tonic-gate Freetotal = stats_new_counter("lut.frees", "total frees", 1); 62*0Sstevel@tonic-gate } 63*0Sstevel@tonic-gate 64*0Sstevel@tonic-gate void 65*0Sstevel@tonic-gate lut_fini(void) 66*0Sstevel@tonic-gate { 67*0Sstevel@tonic-gate stats_delete(Addtotal); 68*0Sstevel@tonic-gate stats_delete(Lookuptotal); 69*0Sstevel@tonic-gate stats_delete(Freetotal); 70*0Sstevel@tonic-gate } 71*0Sstevel@tonic-gate 72*0Sstevel@tonic-gate /* 73*0Sstevel@tonic-gate * lut_add -- add an entry to the table 74*0Sstevel@tonic-gate * 75*0Sstevel@tonic-gate * use it like this: 76*0Sstevel@tonic-gate * struct lut *root = NULL; 77*0Sstevel@tonic-gate * root = lut_add(root, key, value, cmp_func); 78*0Sstevel@tonic-gate * 79*0Sstevel@tonic-gate * the cmp_func can be strcmp(). pass in NULL and instead of 80*0Sstevel@tonic-gate * calling a cmp_func the routine will just look at the difference 81*0Sstevel@tonic-gate * between key pointers (useful when all strings are kept in a 82*0Sstevel@tonic-gate * string table so they are equal if their pointers are equal). 83*0Sstevel@tonic-gate * 84*0Sstevel@tonic-gate */ 85*0Sstevel@tonic-gate struct lut * 86*0Sstevel@tonic-gate lut_add(struct lut *root, void *lhs, void *rhs, lut_cmp cmp_func) 87*0Sstevel@tonic-gate { 88*0Sstevel@tonic-gate int diff; 89*0Sstevel@tonic-gate 90*0Sstevel@tonic-gate if (root == NULL) { 91*0Sstevel@tonic-gate /* not in tree, create new node */ 92*0Sstevel@tonic-gate root = MALLOC(sizeof (*root)); 93*0Sstevel@tonic-gate root->lut_lhs = lhs; 94*0Sstevel@tonic-gate root->lut_rhs = rhs; 95*0Sstevel@tonic-gate root->lut_left = root->lut_right = NULL; 96*0Sstevel@tonic-gate stats_counter_bump(Addtotal); 97*0Sstevel@tonic-gate return (root); 98*0Sstevel@tonic-gate } 99*0Sstevel@tonic-gate 100*0Sstevel@tonic-gate if (cmp_func) 101*0Sstevel@tonic-gate diff = (*cmp_func)(root->lut_lhs, lhs); 102*0Sstevel@tonic-gate else 103*0Sstevel@tonic-gate diff = (const char *)lhs - (const char *)root->lut_lhs; 104*0Sstevel@tonic-gate 105*0Sstevel@tonic-gate if (diff == 0) { 106*0Sstevel@tonic-gate /* already in tree, replace node */ 107*0Sstevel@tonic-gate root->lut_rhs = rhs; 108*0Sstevel@tonic-gate } else if (diff > 0) 109*0Sstevel@tonic-gate root->lut_left = lut_add(root->lut_left, lhs, rhs, cmp_func); 110*0Sstevel@tonic-gate else 111*0Sstevel@tonic-gate root->lut_right = lut_add(root->lut_right, lhs, rhs, cmp_func); 112*0Sstevel@tonic-gate return (root); 113*0Sstevel@tonic-gate } 114*0Sstevel@tonic-gate 115*0Sstevel@tonic-gate /* 116*0Sstevel@tonic-gate * lut_lookup -- find an entry 117*0Sstevel@tonic-gate */ 118*0Sstevel@tonic-gate void * 119*0Sstevel@tonic-gate lut_lookup(struct lut *root, void *lhs, lut_cmp cmp_func) 120*0Sstevel@tonic-gate { 121*0Sstevel@tonic-gate int diff; 122*0Sstevel@tonic-gate 123*0Sstevel@tonic-gate stats_counter_bump(Lookuptotal); 124*0Sstevel@tonic-gate 125*0Sstevel@tonic-gate if (root == NULL) 126*0Sstevel@tonic-gate return (NULL); 127*0Sstevel@tonic-gate 128*0Sstevel@tonic-gate if (cmp_func) 129*0Sstevel@tonic-gate diff = (*cmp_func)(root->lut_lhs, lhs); 130*0Sstevel@tonic-gate else 131*0Sstevel@tonic-gate diff = (const char *)lhs - (const char *)root->lut_lhs; 132*0Sstevel@tonic-gate 133*0Sstevel@tonic-gate if (diff == 0) { 134*0Sstevel@tonic-gate return (root->lut_rhs); 135*0Sstevel@tonic-gate } else if (diff > 0) 136*0Sstevel@tonic-gate return (lut_lookup(root->lut_left, lhs, cmp_func)); 137*0Sstevel@tonic-gate else 138*0Sstevel@tonic-gate return (lut_lookup(root->lut_right, lhs, cmp_func)); 139*0Sstevel@tonic-gate } 140*0Sstevel@tonic-gate 141*0Sstevel@tonic-gate /* 142*0Sstevel@tonic-gate * lut_lookup_lhs -- find an entry, return the matched key (lut_lhs) 143*0Sstevel@tonic-gate */ 144*0Sstevel@tonic-gate void * 145*0Sstevel@tonic-gate lut_lookup_lhs(struct lut *root, void *lhs, lut_cmp cmp_func) 146*0Sstevel@tonic-gate { 147*0Sstevel@tonic-gate int diff; 148*0Sstevel@tonic-gate 149*0Sstevel@tonic-gate stats_counter_bump(Lookuptotal); 150*0Sstevel@tonic-gate 151*0Sstevel@tonic-gate if (root == NULL) 152*0Sstevel@tonic-gate return (NULL); 153*0Sstevel@tonic-gate 154*0Sstevel@tonic-gate if (cmp_func) 155*0Sstevel@tonic-gate diff = (*cmp_func)(root->lut_lhs, lhs); 156*0Sstevel@tonic-gate else 157*0Sstevel@tonic-gate diff = (const char *)lhs - (const char *)root->lut_lhs; 158*0Sstevel@tonic-gate 159*0Sstevel@tonic-gate if (diff == 0) { 160*0Sstevel@tonic-gate return (root->lut_lhs); 161*0Sstevel@tonic-gate } else if (diff > 0) 162*0Sstevel@tonic-gate return (lut_lookup_lhs(root->lut_left, lhs, cmp_func)); 163*0Sstevel@tonic-gate else 164*0Sstevel@tonic-gate return (lut_lookup_lhs(root->lut_right, lhs, cmp_func)); 165*0Sstevel@tonic-gate } 166*0Sstevel@tonic-gate 167*0Sstevel@tonic-gate /* 168*0Sstevel@tonic-gate * lut_walk -- walk the table in lexical order 169*0Sstevel@tonic-gate */ 170*0Sstevel@tonic-gate void 171*0Sstevel@tonic-gate lut_walk(struct lut *root, lut_cb callback, void *arg) 172*0Sstevel@tonic-gate { 173*0Sstevel@tonic-gate if (root) { 174*0Sstevel@tonic-gate lut_walk(root->lut_left, callback, arg); 175*0Sstevel@tonic-gate (*callback)(root->lut_lhs, root->lut_rhs, arg); 176*0Sstevel@tonic-gate lut_walk(root->lut_right, callback, arg); 177*0Sstevel@tonic-gate } 178*0Sstevel@tonic-gate } 179*0Sstevel@tonic-gate 180*0Sstevel@tonic-gate /* 181*0Sstevel@tonic-gate * lut_free -- free the lut 182*0Sstevel@tonic-gate */ 183*0Sstevel@tonic-gate void 184*0Sstevel@tonic-gate lut_free(struct lut *root, lut_cb callback, void *arg) 185*0Sstevel@tonic-gate { 186*0Sstevel@tonic-gate if (root) { 187*0Sstevel@tonic-gate lut_free(root->lut_left, callback, arg); 188*0Sstevel@tonic-gate root->lut_left = NULL; 189*0Sstevel@tonic-gate lut_free(root->lut_right, callback, arg); 190*0Sstevel@tonic-gate root->lut_right = NULL; 191*0Sstevel@tonic-gate if (callback) 192*0Sstevel@tonic-gate (*callback)(root->lut_lhs, root->lut_rhs, arg); 193*0Sstevel@tonic-gate FREE(root); 194*0Sstevel@tonic-gate stats_counter_bump(Freetotal); 195*0Sstevel@tonic-gate } 196*0Sstevel@tonic-gate } 197