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
);