1 /* $OpenBSD: tree.c,v 1.11 2006/03/13 19:57:42 otto Exp $ */
2
3 /* Routines for manipulating parse trees... */
4
5 /*
6 * Copyright (c) 1995, 1996, 1997 The Internet Software Consortium.
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of The Internet Software Consortium nor the names
19 * of its contributors may be used to endorse or promote products derived
20 * from this software without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE INTERNET SOFTWARE CONSORTIUM AND
23 * CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
24 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
25 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
26 * DISCLAIMED. IN NO EVENT SHALL THE INTERNET SOFTWARE CONSORTIUM OR
27 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
29 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
30 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
31 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
32 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
33 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 *
36 * This software has been written for the Internet Software Consortium
37 * by Ted Lemon <mellon@fugue.com> in cooperation with Vixie
38 * Enterprises. To learn more about the Internet Software Consortium,
39 * see ``http://www.vix.com/isc''. To learn more about Vixie
40 * Enterprises, see ``http://www.vix.com''.
41 */
42
43 #include "dhcpd.h"
44
45 static time_t tree_evaluate_recurse(int *, unsigned char **, int *,
46 struct tree *);
47 static void do_data_copy(int *, unsigned char **, int *, unsigned char *, int);
48
49 pair
cons(caddr_t car,pair cdr)50 cons(caddr_t car, pair cdr)
51 {
52 pair foo = (pair)dmalloc(sizeof *foo, "cons");
53 if (!foo)
54 error("no memory for cons.");
55 foo->car = car;
56 foo->cdr = cdr;
57 return foo;
58 }
59
60 struct tree_cache *
tree_cache(struct tree * tree)61 tree_cache(struct tree *tree)
62 {
63 struct tree_cache *tc;
64
65 tc = new_tree_cache("tree_cache");
66 if (!tc)
67 return 0;
68 tc->value = NULL;
69 tc->len = tc->buf_size = 0;
70 tc->timeout = 0;
71 tc->tree = tree;
72 return tc;
73 }
74
75 struct tree *
tree_const(unsigned char * data,int len)76 tree_const(unsigned char *data, int len)
77 {
78 struct tree *nt;
79
80 if (!(nt = new_tree("tree_const")) || !(nt->data.const_val.data =
81 (unsigned char *)dmalloc(len, "tree_const")))
82 error("No memory for constant data tree node.");
83 nt->op = TREE_CONST;
84 memcpy(nt->data.const_val.data, data, len);
85 nt->data.const_val.len = len;
86 return nt;
87 }
88
89 struct tree *
tree_concat(struct tree * left,struct tree * right)90 tree_concat(struct tree *left, struct tree *right)
91 {
92 struct tree *nt;
93
94 /*
95 * If we're concatenating a null tree to a non-null tree, just
96 * return the non-null tree; if both trees are null, return
97 * a null tree.
98 */
99 if (!left)
100 return right;
101 if (!right)
102 return left;
103
104 /* If both trees are constant, combine them. */
105 if (left->op == TREE_CONST && right->op == TREE_CONST) {
106 unsigned char *buf = dmalloc(left->data.const_val.len
107 + right->data.const_val.len, "tree_concat");
108
109 if (!buf)
110 error("No memory to concatenate constants.");
111 memcpy(buf, left->data.const_val.data,
112 left->data.const_val.len);
113 memcpy(buf + left->data.const_val.len,
114 right->data.const_val.data, right->data.const_val.len);
115 dfree(left->data.const_val.data, "tree_concat");
116 dfree(right->data.const_val.data, "tree_concat");
117 left->data.const_val.data = buf;
118 left->data.const_val.len += right->data.const_val.len;
119 free_tree(right, "tree_concat");
120 return left;
121 }
122
123 /* Otherwise, allocate a new node to concatenate the two. */
124 if (!(nt = new_tree("tree_concat")))
125 error("No memory for data tree concatenation node.");
126 nt->op = TREE_CONCAT;
127 nt->data.concat.left = left;
128 nt->data.concat.right = right;
129 return nt;
130 }
131
132 struct tree *
tree_limit(struct tree * tree,int limit)133 tree_limit(struct tree *tree, int limit)
134 {
135 struct tree *rv;
136
137 /* If the tree we're limiting is constant, limit it now. */
138 if (tree->op == TREE_CONST) {
139 if (tree->data.const_val.len > limit)
140 tree->data.const_val.len = limit;
141 return tree;
142 }
143
144 /* Otherwise, put in a node which enforces the limit on evaluation. */
145 rv = new_tree("tree_limit");
146 if (!rv)
147 return NULL;
148 rv->op = TREE_LIMIT;
149 rv->data.limit.tree = tree;
150 rv->data.limit.limit = limit;
151 return rv;
152 }
153
154 int
tree_evaluate(struct tree_cache * tree_cache)155 tree_evaluate(struct tree_cache *tree_cache)
156 {
157 unsigned char *bp = tree_cache->value;
158 int bc = tree_cache->buf_size;
159 int bufix = 0;
160
161 /*
162 * If there's no tree associated with this cache, it evaluates to a
163 * constant and that was detected at startup.
164 */
165 if (!tree_cache->tree)
166 return 1;
167
168 /* Try to evaluate the tree without allocating more memory... */
169 tree_cache->timeout = tree_evaluate_recurse(&bufix, &bp, &bc,
170 tree_cache->tree);
171
172 /* No additional allocation needed? */
173 if (bufix <= bc) {
174 tree_cache->len = bufix;
175 return 1;
176 }
177
178 /*
179 * If we can't allocate more memory, return with what we
180 * have (maybe nothing).
181 */
182 if (!(bp = (unsigned char *)dmalloc(bufix, "tree_evaluate")))
183 return 0;
184
185 /* Record the change in conditions... */
186 bc = bufix;
187 bufix = 0;
188
189 /*
190 * Note that the size of the result shouldn't change on the
191 * second call to tree_evaluate_recurse, since we haven't
192 * changed the ``current'' time.
193 */
194 tree_evaluate_recurse(&bufix, &bp, &bc, tree_cache->tree);
195
196 /*
197 * Free the old buffer if needed, then store the new buffer
198 * location and size and return.
199 */
200 if (tree_cache->value)
201 dfree(tree_cache->value, "tree_evaluate");
202 tree_cache->value = bp;
203 tree_cache->len = bufix;
204 tree_cache->buf_size = bc;
205 return 1;
206 }
207
208 static time_t
tree_evaluate_recurse(int * bufix,unsigned char ** bufp,int * bufcount,struct tree * tree)209 tree_evaluate_recurse(int *bufix, unsigned char **bufp,
210 int *bufcount, struct tree *tree)
211 {
212 int limit;
213 time_t t1, t2;
214
215 switch (tree->op) {
216 case TREE_CONCAT:
217 t1 = tree_evaluate_recurse(bufix, bufp, bufcount,
218 tree->data.concat.left);
219 t2 = tree_evaluate_recurse(bufix, bufp, bufcount,
220 tree->data.concat.right);
221 if (t1 > t2)
222 return t2;
223 return t1;
224
225 case TREE_CONST:
226 do_data_copy(bufix, bufp, bufcount, tree->data.const_val.data,
227 tree->data.const_val.len);
228 t1 = MAX_TIME;
229 return t1;
230
231 case TREE_LIMIT:
232 limit = *bufix + tree->data.limit.limit;
233 t1 = tree_evaluate_recurse(bufix, bufp, bufcount,
234 tree->data.limit.tree);
235 *bufix = limit;
236 return t1;
237
238 default:
239 warning("Bad node id in tree: %d.", tree->op);
240 t1 = MAX_TIME;
241 return t1;
242 }
243 }
244
245 static void
do_data_copy(int * bufix,unsigned char ** bufp,int * bufcount,unsigned char * data,int len)246 do_data_copy(int *bufix, unsigned char **bufp, int *bufcount,
247 unsigned char *data, int len)
248 {
249 int space = *bufcount - *bufix;
250
251 /* If there's more space than we need, use only what we need. */
252 if (space > len)
253 space = len;
254
255 /*
256 * Copy as much data as will fit, then increment the buffer index
257 * by the amount we actually had to copy, which could be more.
258 */
259 if (space > 0)
260 memcpy(*bufp + *bufix, data, space);
261 *bufix += len;
262 }
263