lut.c revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (the "License"). You may not use this file except in compliance
* with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* or http://www.opensolaris.org/os/licensing.
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2004 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*
* lut.c -- simple lookup table module
*
* this file contains a very simple lookup table (lut) implementation.
* the tables only support insert & lookup, no delete, and can
* only be walked in one order. if the key already exists
* for something being inserted, the previous entry is simply
* replaced.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
#include <stdio.h>
#include "alloc.h"
#include "out.h"
#include "stats.h"
#include "lut.h"
#include "tree.h"
/* info created by lut_add(), private to this module */
struct lut {
struct lut *lut_left;
struct lut *lut_right;
void *lut_lhs; /* search key */
void *lut_rhs; /* the datum */
};
static struct stats *Addtotal;
static struct stats *Lookuptotal;
static struct stats *Freetotal;
void
lut_init(void)
{
Addtotal = stats_new_counter("lut.adds", "total adds", 1);
Lookuptotal = stats_new_counter("lut.lookup", "total lookups", 1);
Freetotal = stats_new_counter("lut.frees", "total frees", 1);
}
void
lut_fini(void)
{
stats_delete(Addtotal);
stats_delete(Lookuptotal);
stats_delete(Freetotal);
}
/*
* lut_add -- add an entry to the table
*
* use it like this:
* struct lut *root = NULL;
* root = lut_add(root, key, value, cmp_func);
*
* the cmp_func can be strcmp(). pass in NULL and instead of
* calling a cmp_func the routine will just look at the difference
* between key pointers (useful when all strings are kept in a
* string table so they are equal if their pointers are equal).
*
*/
struct lut *
lut_add(struct lut *root, void *lhs, void *rhs, lut_cmp cmp_func)
{
int diff;
if (root == NULL) {
/* not in tree, create new node */
root = MALLOC(sizeof (*root));
root->lut_lhs = lhs;
root->lut_rhs = rhs;
root->lut_left = root->lut_right = NULL;
stats_counter_bump(Addtotal);
return (root);
}
if (cmp_func)
diff = (*cmp_func)(root->lut_lhs, lhs);
else
diff = (const char *)lhs - (const char *)root->lut_lhs;
if (diff == 0) {
/* already in tree, replace node */
root->lut_rhs = rhs;
} else if (diff > 0)
root->lut_left = lut_add(root->lut_left, lhs, rhs, cmp_func);
else
root->lut_right = lut_add(root->lut_right, lhs, rhs, cmp_func);
return (root);
}
/*
* lut_lookup -- find an entry
*/
void *
lut_lookup(struct lut *root, void *lhs, lut_cmp cmp_func)
{
int diff;
stats_counter_bump(Lookuptotal);
if (root == NULL)
return (NULL);
if (cmp_func)
diff = (*cmp_func)(root->lut_lhs, lhs);
else
diff = (const char *)lhs - (const char *)root->lut_lhs;
if (diff == 0) {
return (root->lut_rhs);
} else if (diff > 0)
return (lut_lookup(root->lut_left, lhs, cmp_func));
else
return (lut_lookup(root->lut_right, lhs, cmp_func));
}
/*
* lut_lookup_lhs -- find an entry, return the matched key (lut_lhs)
*/
void *
lut_lookup_lhs(struct lut *root, void *lhs, lut_cmp cmp_func)
{
int diff;
stats_counter_bump(Lookuptotal);
if (root == NULL)
return (NULL);
if (cmp_func)
diff = (*cmp_func)(root->lut_lhs, lhs);
else
diff = (const char *)lhs - (const char *)root->lut_lhs;
if (diff == 0) {
return (root->lut_lhs);
} else if (diff > 0)
return (lut_lookup_lhs(root->lut_left, lhs, cmp_func));
else
return (lut_lookup_lhs(root->lut_right, lhs, cmp_func));
}
/*
* lut_walk -- walk the table in lexical order
*/
void
lut_walk(struct lut *root, lut_cb callback, void *arg)
{
if (root) {
lut_walk(root->lut_left, callback, arg);
(*callback)(root->lut_lhs, root->lut_rhs, arg);
lut_walk(root->lut_right, callback, arg);
}
}
/*
* lut_free -- free the lut
*/
void
lut_free(struct lut *root, lut_cb callback, void *arg)
{
if (root) {
lut_free(root->lut_left, callback, arg);
root->lut_left = NULL;
lut_free(root->lut_right, callback, arg);
root->lut_right = NULL;
if (callback)
(*callback)(root->lut_lhs, root->lut_rhs, arg);
FREE(root);
stats_counter_bump(Freetotal);
}
}