17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
50d10a7a8Srobj * Common Development and Distribution License (the "License").
60d10a7a8Srobj * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate *
87c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate * and limitations under the License.
127c478bd9Sstevel@tonic-gate *
137c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate *
197c478bd9Sstevel@tonic-gate * CDDL HEADER END
207c478bd9Sstevel@tonic-gate */
217c478bd9Sstevel@tonic-gate /*
220d10a7a8Srobj * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
237c478bd9Sstevel@tonic-gate * Use is subject to license terms.
247c478bd9Sstevel@tonic-gate *
257c478bd9Sstevel@tonic-gate * lut.c -- simple lookup table module
267c478bd9Sstevel@tonic-gate *
277c478bd9Sstevel@tonic-gate * this file contains a very simple lookup table (lut) implementation.
287c478bd9Sstevel@tonic-gate * the tables only support insert & lookup, no delete, and can
297c478bd9Sstevel@tonic-gate * only be walked in one order. if the key already exists
307c478bd9Sstevel@tonic-gate * for something being inserted, the previous entry is simply
317c478bd9Sstevel@tonic-gate * replaced.
327c478bd9Sstevel@tonic-gate */
337c478bd9Sstevel@tonic-gate
347c478bd9Sstevel@tonic-gate #include <stdio.h>
357c478bd9Sstevel@tonic-gate #include "alloc.h"
367c478bd9Sstevel@tonic-gate #include "out.h"
377c478bd9Sstevel@tonic-gate #include "stats.h"
387c478bd9Sstevel@tonic-gate #include "lut.h"
39*6cb1ca52Saf #include "lut_impl.h"
407c478bd9Sstevel@tonic-gate #include "tree.h"
417c478bd9Sstevel@tonic-gate
427c478bd9Sstevel@tonic-gate static struct stats *Addtotal;
437c478bd9Sstevel@tonic-gate static struct stats *Lookuptotal;
447c478bd9Sstevel@tonic-gate static struct stats *Freetotal;
457c478bd9Sstevel@tonic-gate
467c478bd9Sstevel@tonic-gate void
lut_init(void)477c478bd9Sstevel@tonic-gate lut_init(void)
487c478bd9Sstevel@tonic-gate {
497c478bd9Sstevel@tonic-gate Addtotal = stats_new_counter("lut.adds", "total adds", 1);
507c478bd9Sstevel@tonic-gate Lookuptotal = stats_new_counter("lut.lookup", "total lookups", 1);
517c478bd9Sstevel@tonic-gate Freetotal = stats_new_counter("lut.frees", "total frees", 1);
527c478bd9Sstevel@tonic-gate }
537c478bd9Sstevel@tonic-gate
547c478bd9Sstevel@tonic-gate void
lut_fini(void)557c478bd9Sstevel@tonic-gate lut_fini(void)
567c478bd9Sstevel@tonic-gate {
577c478bd9Sstevel@tonic-gate stats_delete(Addtotal);
587c478bd9Sstevel@tonic-gate stats_delete(Lookuptotal);
597c478bd9Sstevel@tonic-gate stats_delete(Freetotal);
607c478bd9Sstevel@tonic-gate }
617c478bd9Sstevel@tonic-gate
627c478bd9Sstevel@tonic-gate /*
637c478bd9Sstevel@tonic-gate * lut_add -- add an entry to the table
647c478bd9Sstevel@tonic-gate *
657c478bd9Sstevel@tonic-gate * use it like this:
667c478bd9Sstevel@tonic-gate * struct lut *root = NULL;
677c478bd9Sstevel@tonic-gate * root = lut_add(root, key, value, cmp_func);
687c478bd9Sstevel@tonic-gate *
697c478bd9Sstevel@tonic-gate * the cmp_func can be strcmp(). pass in NULL and instead of
707c478bd9Sstevel@tonic-gate * calling a cmp_func the routine will just look at the difference
717c478bd9Sstevel@tonic-gate * between key pointers (useful when all strings are kept in a
727c478bd9Sstevel@tonic-gate * string table so they are equal if their pointers are equal).
737c478bd9Sstevel@tonic-gate *
747c478bd9Sstevel@tonic-gate */
757c478bd9Sstevel@tonic-gate struct lut *
lut_add(struct lut * root,void * lhs,void * rhs,lut_cmp cmp_func)767c478bd9Sstevel@tonic-gate lut_add(struct lut *root, void *lhs, void *rhs, lut_cmp cmp_func)
777c478bd9Sstevel@tonic-gate {
787c478bd9Sstevel@tonic-gate int diff;
790d10a7a8Srobj struct lut **tmp_hdl = &root, *parent = NULL, *tmp = root;
800d10a7a8Srobj
810d10a7a8Srobj while (tmp) {
820d10a7a8Srobj if (cmp_func)
830d10a7a8Srobj diff = (*cmp_func)(tmp->lut_lhs, lhs);
840d10a7a8Srobj else
850d10a7a8Srobj diff = (const char *)lhs - (const char *)tmp->lut_lhs;
860d10a7a8Srobj
870d10a7a8Srobj if (diff == 0) {
880d10a7a8Srobj /* already in tree, replace node */
890d10a7a8Srobj tmp->lut_rhs = rhs;
900d10a7a8Srobj return (root);
910d10a7a8Srobj } else if (diff > 0) {
920d10a7a8Srobj tmp_hdl = &(tmp->lut_left);
930d10a7a8Srobj parent = tmp;
940d10a7a8Srobj tmp = tmp->lut_left;
950d10a7a8Srobj } else {
960d10a7a8Srobj tmp_hdl = &(tmp->lut_right);
970d10a7a8Srobj parent = tmp;
980d10a7a8Srobj tmp = tmp->lut_right;
990d10a7a8Srobj }
1007c478bd9Sstevel@tonic-gate }
1017c478bd9Sstevel@tonic-gate
1020d10a7a8Srobj /* either empty tree or not in tree, so create new node */
1030d10a7a8Srobj *tmp_hdl = MALLOC(sizeof (*root));
1040d10a7a8Srobj (*tmp_hdl)->lut_lhs = lhs;
1050d10a7a8Srobj (*tmp_hdl)->lut_rhs = rhs;
1060d10a7a8Srobj (*tmp_hdl)->lut_parent = parent;
1070d10a7a8Srobj (*tmp_hdl)->lut_left = (*tmp_hdl)->lut_right = NULL;
1080d10a7a8Srobj stats_counter_bump(Addtotal);
1090d10a7a8Srobj
1107c478bd9Sstevel@tonic-gate return (root);
1117c478bd9Sstevel@tonic-gate }
1127c478bd9Sstevel@tonic-gate
1137c478bd9Sstevel@tonic-gate void *
lut_lookup(struct lut * root,void * lhs,lut_cmp cmp_func)1147c478bd9Sstevel@tonic-gate lut_lookup(struct lut *root, void *lhs, lut_cmp cmp_func)
1157c478bd9Sstevel@tonic-gate {
1167c478bd9Sstevel@tonic-gate int diff;
1177c478bd9Sstevel@tonic-gate
1187c478bd9Sstevel@tonic-gate stats_counter_bump(Lookuptotal);
1197c478bd9Sstevel@tonic-gate
1200d10a7a8Srobj while (root) {
1210d10a7a8Srobj if (cmp_func)
1220d10a7a8Srobj diff = (*cmp_func)(root->lut_lhs, lhs);
1230d10a7a8Srobj else
1240d10a7a8Srobj diff = (const char *)lhs - (const char *)root->lut_lhs;
1250d10a7a8Srobj
1260d10a7a8Srobj if (diff == 0)
1270d10a7a8Srobj return (root->lut_rhs);
1280d10a7a8Srobj else if (diff > 0)
1290d10a7a8Srobj root = root->lut_left;
1300d10a7a8Srobj else
1310d10a7a8Srobj root = root->lut_right;
1320d10a7a8Srobj }
1330d10a7a8Srobj return (NULL);
1347c478bd9Sstevel@tonic-gate }
1357c478bd9Sstevel@tonic-gate
1367c478bd9Sstevel@tonic-gate void *
lut_lookup_lhs(struct lut * root,void * lhs,lut_cmp cmp_func)1377c478bd9Sstevel@tonic-gate lut_lookup_lhs(struct lut *root, void *lhs, lut_cmp cmp_func)
1387c478bd9Sstevel@tonic-gate {
1397c478bd9Sstevel@tonic-gate int diff;
1407c478bd9Sstevel@tonic-gate
1417c478bd9Sstevel@tonic-gate stats_counter_bump(Lookuptotal);
1427c478bd9Sstevel@tonic-gate
1430d10a7a8Srobj while (root) {
1440d10a7a8Srobj if (cmp_func)
1450d10a7a8Srobj diff = (*cmp_func)(root->lut_lhs, lhs);
1460d10a7a8Srobj else
1470d10a7a8Srobj diff = (const char *)lhs - (const char *)root->lut_lhs;
1480d10a7a8Srobj
1490d10a7a8Srobj if (diff == 0)
1500d10a7a8Srobj return (root->lut_lhs);
1510d10a7a8Srobj else if (diff > 0)
1520d10a7a8Srobj root = root->lut_left;
1530d10a7a8Srobj else
1540d10a7a8Srobj root = root->lut_right;
1550d10a7a8Srobj }
1560d10a7a8Srobj return (NULL);
1577c478bd9Sstevel@tonic-gate }
1587c478bd9Sstevel@tonic-gate
1597c478bd9Sstevel@tonic-gate /*
1607c478bd9Sstevel@tonic-gate * lut_walk -- walk the table in lexical order
1617c478bd9Sstevel@tonic-gate */
1627c478bd9Sstevel@tonic-gate void
lut_walk(struct lut * root,lut_cb callback,void * arg)1637c478bd9Sstevel@tonic-gate lut_walk(struct lut *root, lut_cb callback, void *arg)
1647c478bd9Sstevel@tonic-gate {
1650d10a7a8Srobj struct lut *tmp = root;
1660d10a7a8Srobj struct lut *prev_child = NULL;
1670d10a7a8Srobj
1680d10a7a8Srobj if (root == NULL)
1690d10a7a8Srobj return;
1700d10a7a8Srobj
1710d10a7a8Srobj while (tmp->lut_left != NULL)
1720d10a7a8Srobj tmp = tmp->lut_left;
1730d10a7a8Srobj
1740d10a7a8Srobj /* do callback on leftmost node */
1750d10a7a8Srobj (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
1760d10a7a8Srobj
1770d10a7a8Srobj for (;;) {
1780d10a7a8Srobj if (tmp->lut_right != NULL && tmp->lut_right != prev_child) {
1790d10a7a8Srobj tmp = tmp->lut_right;
1800d10a7a8Srobj while (tmp->lut_left != NULL)
1810d10a7a8Srobj tmp = tmp->lut_left;
1820d10a7a8Srobj
1830d10a7a8Srobj /* do callback on leftmost node */
1840d10a7a8Srobj (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
1850d10a7a8Srobj } else if (tmp->lut_parent != NULL) {
1860d10a7a8Srobj prev_child = tmp;
1870d10a7a8Srobj tmp = tmp->lut_parent;
1880d10a7a8Srobj /*
1890d10a7a8Srobj * do callback on parent only if we're coming up
1900d10a7a8Srobj * from the left
1910d10a7a8Srobj */
1920d10a7a8Srobj if (tmp->lut_right != prev_child)
1930d10a7a8Srobj (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
1940d10a7a8Srobj } else
1950d10a7a8Srobj return;
1967c478bd9Sstevel@tonic-gate }
1977c478bd9Sstevel@tonic-gate }
1987c478bd9Sstevel@tonic-gate
1997c478bd9Sstevel@tonic-gate /*
2007c478bd9Sstevel@tonic-gate * lut_free -- free the lut
2017c478bd9Sstevel@tonic-gate */
2027c478bd9Sstevel@tonic-gate void
lut_free(struct lut * root,lut_cb callback,void * arg)2037c478bd9Sstevel@tonic-gate lut_free(struct lut *root, lut_cb callback, void *arg)
2047c478bd9Sstevel@tonic-gate {
2050d10a7a8Srobj struct lut *tmp = root;
2060d10a7a8Srobj struct lut *prev_child = NULL;
2070d10a7a8Srobj
2080d10a7a8Srobj if (root == NULL)
2090d10a7a8Srobj return;
2100d10a7a8Srobj
2110d10a7a8Srobj while (tmp->lut_left != NULL)
2120d10a7a8Srobj tmp = tmp->lut_left;
2130d10a7a8Srobj
2140d10a7a8Srobj /* do callback on leftmost node */
2150d10a7a8Srobj if (callback)
2160d10a7a8Srobj (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
2170d10a7a8Srobj
2180d10a7a8Srobj for (;;) {
2190d10a7a8Srobj if (tmp->lut_right != NULL && tmp->lut_right != prev_child) {
2200d10a7a8Srobj tmp = tmp->lut_right;
2210d10a7a8Srobj while (tmp->lut_left != NULL)
2220d10a7a8Srobj tmp = tmp->lut_left;
2230d10a7a8Srobj
2240d10a7a8Srobj /* do callback on leftmost node */
2250d10a7a8Srobj if (callback)
2260d10a7a8Srobj (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
2270d10a7a8Srobj } else if (tmp->lut_parent != NULL) {
2280d10a7a8Srobj prev_child = tmp;
2290d10a7a8Srobj tmp = tmp->lut_parent;
2300d10a7a8Srobj FREE(prev_child);
2310d10a7a8Srobj /*
2320d10a7a8Srobj * do callback on parent only if we're coming up
2330d10a7a8Srobj * from the left
2340d10a7a8Srobj */
2350d10a7a8Srobj if (tmp->lut_right != prev_child && callback)
2360d10a7a8Srobj (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
2370d10a7a8Srobj } else {
2380d10a7a8Srobj /*
2390d10a7a8Srobj * free the root node and then we're done
2400d10a7a8Srobj */
2410d10a7a8Srobj FREE(tmp);
2420d10a7a8Srobj return;
2430d10a7a8Srobj }
2447c478bd9Sstevel@tonic-gate }
2457c478bd9Sstevel@tonic-gate }
246