File: [local] / src / usr.sbin / dhcpd / tree.c (download)
Revision 1.11, Mon Mar 13 19:57:42 2006 UTC (18 years, 2 months ago) by otto
Branch: MAIN
CVS Tags: OPENBSD_4_6_BASE, OPENBSD_4_6, OPENBSD_4_5_BASE, OPENBSD_4_5, OPENBSD_4_4_BASE, OPENBSD_4_4, OPENBSD_4_3_BASE, OPENBSD_4_3, OPENBSD_4_2_BASE, OPENBSD_4_2, OPENBSD_4_1_BASE, OPENBSD_4_1, OPENBSD_4_0_BASE, OPENBSD_4_0 Changes since 1.10: +1 -32 lines
tiny bit of delinting; ok krw@
|
/* $OpenBSD: tree.c,v 1.11 2006/03/13 19:57:42 otto Exp $ */
/* Routines for manipulating parse trees... */
/*
* Copyright (c) 1995, 1996, 1997 The Internet Software Consortium.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. Neither the name of The Internet Software Consortium nor the names
* of its contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE INTERNET SOFTWARE CONSORTIUM AND
* CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE INTERNET SOFTWARE CONSORTIUM OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
* This software has been written for the Internet Software Consortium
* by Ted Lemon <mellon@fugue.com> in cooperation with Vixie
* Enterprises. To learn more about the Internet Software Consortium,
* see ``http://www.vix.com/isc''. To learn more about Vixie
* Enterprises, see ``http://www.vix.com''.
*/
#include "dhcpd.h"
static time_t tree_evaluate_recurse(int *, unsigned char **, int *,
struct tree *);
static void do_data_copy(int *, unsigned char **, int *, unsigned char *, int);
pair
cons(caddr_t car, pair cdr)
{
pair foo = (pair)dmalloc(sizeof *foo, "cons");
if (!foo)
error("no memory for cons.");
foo->car = car;
foo->cdr = cdr;
return foo;
}
struct tree_cache *
tree_cache(struct tree *tree)
{
struct tree_cache *tc;
tc = new_tree_cache("tree_cache");
if (!tc)
return 0;
tc->value = NULL;
tc->len = tc->buf_size = 0;
tc->timeout = 0;
tc->tree = tree;
return tc;
}
struct tree *
tree_const(unsigned char *data, int len)
{
struct tree *nt;
if (!(nt = new_tree("tree_const")) || !(nt->data.const_val.data =
(unsigned char *)dmalloc(len, "tree_const")))
error("No memory for constant data tree node.");
nt->op = TREE_CONST;
memcpy(nt->data.const_val.data, data, len);
nt->data.const_val.len = len;
return nt;
}
struct tree *
tree_concat(struct tree *left, struct tree *right)
{
struct tree *nt;
/*
* If we're concatenating a null tree to a non-null tree, just
* return the non-null tree; if both trees are null, return
* a null tree.
*/
if (!left)
return right;
if (!right)
return left;
/* If both trees are constant, combine them. */
if (left->op == TREE_CONST && right->op == TREE_CONST) {
unsigned char *buf = dmalloc(left->data.const_val.len
+ right->data.const_val.len, "tree_concat");
if (!buf)
error("No memory to concatenate constants.");
memcpy(buf, left->data.const_val.data,
left->data.const_val.len);
memcpy(buf + left->data.const_val.len,
right->data.const_val.data, right->data.const_val.len);
dfree(left->data.const_val.data, "tree_concat");
dfree(right->data.const_val.data, "tree_concat");
left->data.const_val.data = buf;
left->data.const_val.len += right->data.const_val.len;
free_tree(right, "tree_concat");
return left;
}
/* Otherwise, allocate a new node to concatenate the two. */
if (!(nt = new_tree("tree_concat")))
error("No memory for data tree concatenation node.");
nt->op = TREE_CONCAT;
nt->data.concat.left = left;
nt->data.concat.right = right;
return nt;
}
struct tree *
tree_limit(struct tree *tree, int limit)
{
struct tree *rv;
/* If the tree we're limiting is constant, limit it now. */
if (tree->op == TREE_CONST) {
if (tree->data.const_val.len > limit)
tree->data.const_val.len = limit;
return tree;
}
/* Otherwise, put in a node which enforces the limit on evaluation. */
rv = new_tree("tree_limit");
if (!rv)
return NULL;
rv->op = TREE_LIMIT;
rv->data.limit.tree = tree;
rv->data.limit.limit = limit;
return rv;
}
int
tree_evaluate(struct tree_cache *tree_cache)
{
unsigned char *bp = tree_cache->value;
int bc = tree_cache->buf_size;
int bufix = 0;
/*
* If there's no tree associated with this cache, it evaluates to a
* constant and that was detected at startup.
*/
if (!tree_cache->tree)
return 1;
/* Try to evaluate the tree without allocating more memory... */
tree_cache->timeout = tree_evaluate_recurse(&bufix, &bp, &bc,
tree_cache->tree);
/* No additional allocation needed? */
if (bufix <= bc) {
tree_cache->len = bufix;
return 1;
}
/*
* If we can't allocate more memory, return with what we
* have (maybe nothing).
*/
if (!(bp = (unsigned char *)dmalloc(bufix, "tree_evaluate")))
return 0;
/* Record the change in conditions... */
bc = bufix;
bufix = 0;
/*
* Note that the size of the result shouldn't change on the
* second call to tree_evaluate_recurse, since we haven't
* changed the ``current'' time.
*/
tree_evaluate_recurse(&bufix, &bp, &bc, tree_cache->tree);
/*
* Free the old buffer if needed, then store the new buffer
* location and size and return.
*/
if (tree_cache->value)
dfree(tree_cache->value, "tree_evaluate");
tree_cache->value = bp;
tree_cache->len = bufix;
tree_cache->buf_size = bc;
return 1;
}
static time_t
tree_evaluate_recurse(int *bufix, unsigned char **bufp,
int *bufcount, struct tree *tree)
{
int limit;
time_t t1, t2;
switch (tree->op) {
case TREE_CONCAT:
t1 = tree_evaluate_recurse(bufix, bufp, bufcount,
tree->data.concat.left);
t2 = tree_evaluate_recurse(bufix, bufp, bufcount,
tree->data.concat.right);
if (t1 > t2)
return t2;
return t1;
case TREE_CONST:
do_data_copy(bufix, bufp, bufcount, tree->data.const_val.data,
tree->data.const_val.len);
t1 = MAX_TIME;
return t1;
case TREE_LIMIT:
limit = *bufix + tree->data.limit.limit;
t1 = tree_evaluate_recurse(bufix, bufp, bufcount,
tree->data.limit.tree);
*bufix = limit;
return t1;
default:
warning("Bad node id in tree: %d.", tree->op);
t1 = MAX_TIME;
return t1;
}
}
static void
do_data_copy(int *bufix, unsigned char **bufp, int *bufcount,
unsigned char *data, int len)
{
int space = *bufcount - *bufix;
/* If there's more space than we need, use only what we need. */
if (space > len)
space = len;
/*
* Copy as much data as will fit, then increment the buffer index
* by the amount we actually had to copy, which could be more.
*/
if (space > 0)
memcpy(*bufp + *bufix, data, space);
*bufix += len;
}