3 Routines for manipulating parse trees... */
6 * Copyright (c) 1995, 1996, 1997 The Internet Software Consortium.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
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.
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
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''.
44 static char copyright[] =
45 "$Id: tree.c,v 1.10 1997/05/09 08:14:57 mellon Exp $ Copyright (c) 1995, 1996, 1997 The Internet Software Consortium. All rights reserved.\n";
50 static TIME tree_evaluate_recurse PROTO ((int *, unsigned char **, int *,
52 static TIME do_host_lookup PROTO ((int *, unsigned char **, int *,
53 struct dns_host_entry *));
54 static void do_data_copy PROTO ((int *, unsigned char **, int *,
55 unsigned char *, int));
61 pair foo = (pair)dmalloc (sizeof *foo, "cons");
63 error ("no memory for cons.");
69 struct tree_cache *tree_cache (tree)
72 struct tree_cache *tc;
74 tc = new_tree_cache ("tree_cache");
77 tc -> value = (unsigned char *)0;
78 tc -> len = tc -> buf_size = 0;
84 struct tree *tree_host_lookup (name)
88 nt = new_tree ("tree_host_lookup");
90 error ("No memory for host lookup tree node.");
91 nt -> op = TREE_HOST_LOOKUP;
92 nt -> data.host_lookup.host = enter_dns_host (name);
96 struct dns_host_entry *enter_dns_host (name)
99 struct dns_host_entry *dh;
101 if (!(dh = (struct dns_host_entry *)dmalloc
102 (sizeof (struct dns_host_entry), "enter_dns_host"))
103 || !(dh -> hostname = dmalloc (strlen (name) + 1,
105 error ("Can't allocate space for new host.");
106 strcpy (dh -> hostname, name);
107 dh -> data = (unsigned char *)0;
114 struct tree *tree_const (data, len)
119 if (!(nt = new_tree ("tree_const"))
120 || !(nt -> data.const_val.data =
121 (unsigned char *)dmalloc (len, "tree_const")))
122 error ("No memory for constant data tree node.");
123 nt -> op = TREE_CONST;
124 memcpy (nt -> data.const_val.data, data, len);
125 nt -> data.const_val.len = len;
129 struct tree *tree_concat (left, right)
130 struct tree *left, *right;
134 /* If we're concatenating a null tree to a non-null tree, just
135 return the non-null tree; if both trees are null, return
142 /* If both trees are constant, combine them. */
143 if (left -> op == TREE_CONST && right -> op == TREE_CONST) {
144 unsigned char *buf = dmalloc (left -> data.const_val.len
145 + right -> data.const_val.len,
148 error ("No memory to concatenate constants.");
149 memcpy (buf, left -> data.const_val.data,
150 left -> data.const_val.len);
151 memcpy (buf + left -> data.const_val.len,
152 right -> data.const_val.data,
153 right -> data.const_val.len);
154 dfree (left -> data.const_val.data, "tree_concat");
155 dfree (right -> data.const_val.data, "tree_concat");
156 left -> data.const_val.data = buf;
157 left -> data.const_val.len += right -> data.const_val.len;
158 free_tree (right, "tree_concat");
162 /* Otherwise, allocate a new node to concatenate the two. */
163 if (!(nt = new_tree ("tree_concat")))
164 error ("No memory for data tree concatenation node.");
165 nt -> op = TREE_CONCAT;
166 nt -> data.concat.left = left;
167 nt -> data.concat.right = right;
171 struct tree *tree_limit (tree, limit)
177 /* If the tree we're limiting is constant, limit it now. */
178 if (tree -> op == TREE_CONST) {
179 if (tree -> data.const_val.len > limit)
180 tree -> data.const_val.len = limit;
184 /* Otherwise, put in a node which enforces the limit on evaluation. */
185 rv = new_tree ("tree_limit");
187 return (struct tree *)0;
188 rv -> op = TREE_LIMIT;
189 rv -> data.limit.tree = tree;
190 rv -> data.limit.limit = limit;
194 int tree_evaluate (tree_cache)
195 struct tree_cache *tree_cache;
197 unsigned char *bp = tree_cache -> value;
198 int bc = tree_cache -> buf_size;
201 /* If there's no tree associated with this cache, it evaluates
202 to a constant and that was detected at startup. */
203 if (!tree_cache -> tree)
206 /* Try to evaluate the tree without allocating more memory... */
207 tree_cache -> timeout = tree_evaluate_recurse (&bufix, &bp, &bc,
210 /* No additional allocation needed? */
212 tree_cache -> len = bufix;
216 /* If we can't allocate more memory, return with what we
217 have (maybe nothing). */
218 if (!(bp = (unsigned char *)dmalloc (bufix, "tree_evaluate")))
221 /* Record the change in conditions... */
225 /* Note that the size of the result shouldn't change on the
226 second call to tree_evaluate_recurse, since we haven't
227 changed the ``current'' time. */
228 tree_evaluate_recurse (&bufix, &bp, &bc, tree_cache -> tree);
230 /* Free the old buffer if needed, then store the new buffer
231 location and size and return. */
232 if (tree_cache -> value)
233 dfree (tree_cache -> value, "tree_evaluate");
234 tree_cache -> value = bp;
235 tree_cache -> len = bufix;
236 tree_cache -> buf_size = bc;
240 static TIME tree_evaluate_recurse (bufix, bufp, bufcount, tree)
242 unsigned char **bufp;
249 switch (tree -> op) {
251 t1 = tree_evaluate_recurse (bufix, bufp, bufcount,
252 tree -> data.concat.left);
253 t2 = tree_evaluate_recurse (bufix, bufp, bufcount,
254 tree -> data.concat.right);
259 case TREE_HOST_LOOKUP:
260 return do_host_lookup (bufix, bufp, bufcount,
261 tree -> data.host_lookup.host);
264 do_data_copy (bufix, bufp, bufcount,
265 tree -> data.const_val.data,
266 tree -> data.const_val.len);
271 limit = *bufix + tree -> data.limit.limit;
272 t1 = tree_evaluate_recurse (bufix, bufp, bufcount,
273 tree -> data.limit.tree);
278 warn ("Bad node id in tree: %d.");
284 static TIME do_host_lookup (bufix, bufp, bufcount, dns)
286 unsigned char **bufp;
288 struct dns_host_entry *dns;
295 debug ("time: now = %d dns = %d %d diff = %d",
296 cur_time, dns -> timeout, cur_time - dns -> timeout);
299 /* If the record hasn't timed out, just copy the data and return. */
300 if (cur_time <= dns -> timeout) {
302 debug ("easy copy: %x %d %x",
303 dns -> data, dns -> data_len,
304 dns -> data ? *(int *)(dns -> data) : 0);
306 do_data_copy (bufix, bufp, bufcount,
307 dns -> data, dns -> data_len);
308 return dns -> timeout;
311 debug ("Looking up %s", dns -> hostname);
314 /* Otherwise, look it up... */
315 h = gethostbyname (dns -> hostname);
321 warn ("%s: host unknown.", dns -> hostname);
325 warn ("%s: temporary name server failure",
329 warn ("%s: name server failed", dns -> hostname);
332 warn ("%s: no A record associated with address",
335 #endif /* !NO_H_ERRNO */
337 /* Okay to try again after a minute. */
338 return cur_time + 60;
342 debug ("Lookup succeeded; first address is %x",
343 h -> h_addr_list [0]);
346 /* Count the number of addresses we got... */
347 for (i = 0; h -> h_addr_list [i]; i++)
350 /* Do we need to allocate more memory? */
351 new_len = i * h -> h_length;
352 if (dns -> buf_len < i) {
354 (unsigned char *)dmalloc (new_len, "do_host_lookup");
355 /* If we didn't get more memory, use what we have. */
357 new_len = dns -> buf_len;
358 if (!dns -> buf_len) {
359 dns -> timeout = cur_time + 60;
360 return dns -> timeout;
364 dfree (dns -> data, "do_host_lookup");
366 dns -> buf_len = new_len;
370 /* Addresses are conveniently stored one to the buffer, so we
371 have to copy them out one at a time... :'( */
372 for (i = 0; i < new_len / h -> h_length; i++) {
373 memcpy (dns -> data + h -> h_length * i,
374 h -> h_addr_list [i], h -> h_length);
377 debug ("dns -> data: %x h -> h_addr_list [0]: %x",
378 *(int *)(dns -> data), h -> h_addr_list [0]);
380 dns -> data_len = new_len;
382 /* Set the timeout for an hour from now.
383 XXX This should really use the time on the DNS reply. */
384 dns -> timeout = cur_time + 3600;
387 debug ("hard copy: %x %d %x",
388 dns -> data, dns -> data_len, *(int *)(dns -> data));
390 do_data_copy (bufix, bufp, bufcount, dns -> data, dns -> data_len);
391 return dns -> timeout;
394 static void do_data_copy (bufix, bufp, bufcount, data, len)
396 unsigned char **bufp;
401 int space = *bufcount - *bufix;
403 /* If there's more space than we need, use only what we need. */
407 /* Copy as much data as will fit, then increment the buffer index
408 by the amount we actually had to copy, which could be more. */
410 memcpy (*bufp + *bufix, data, space);